Reading Seva's answer to this question, I got lost at the line relating $\sum_{a\in A} r(a)$ to $|A\cap 2A|$. More precisely, restating the problem:

Let $A\subseteq\mathbb{Z}_n$ be an set of consecutive elements of size $|A|=\delta n$, for some $\delta > \frac{1}{3}$. Defining $r(x)$ to be the number of representations of $x\in\subseteq\mathbb{Z}_n$ as the sum of two elements of $A$, that is $$ r(x)\stackrel{\rm{}def}{=}\left|\{(a_1,a_2)\in A^2 : a_1+a_2 = x\}\right| $$ What is the best expression/approximation one can get for $\sum_{a\in A} r(a)$? And in particular, assuming one gets an expression for $|A\cap 2A|$, how is it related to the former quantity?

Through a rather ad hoc argument involving a distinction of cases, I (thanks to a friend of mine) convinced myself that $$|A\cap 2A| = \begin{cases} (3\delta-1)n + O(1) & \delta\in\left(\frac{1}{3},\frac{1}{2}\right] \\ |A|=\delta n & \delta>\frac{1}{2} \\ \end{cases} $$ but do not know how to get to $\sum_{a\in A} r(a)$ from there.

(Rk: for the application I'm thinking of, $\delta=1-\epsilon$ for small constant $\epsilon$ (still $\gg\frac{1}{n}$)).



  • $\begingroup$ I do not quite understand exactly what are you asking here. The question you refer to does not relate the sum $\sum_a r(a)$ to the size of the intersection $2A\cap A=S_1\cap A$. Exactly what line in my solution is unclear? $\endgroup$ – Seva Jan 28 '14 at 20:30
  • $\begingroup$ Oh -- I might have misunderstood the argument there, then. I had the impression that it used the expression found for $|A\cap 2A|$ to get the sum: "[it makes] the intersection of $A$ and $2A$ to be of size about $(3\delta-1)p$, and the sum in question about $2(1+2+\dotsb+((3\delta-1)/2)p)\approx\frac14(3\delta-1)^2p^2$" (I'm actually interested only in the sum, as it turns out) $\endgroup$ – Clement C. Jan 28 '14 at 20:37
  • 1
    $\begingroup$ Ok, this computation is related only to the special case under consideration. In this case two elements of the intersection have one representation (as a two elements of $A$), two elements have two representations, etc. In the general case, the sum $\sum_a r(a)$ is estimated using the identity $\sum_a r(a)=\sum_i |S_i\cap A|$, which follows by a simple ``double-counting'' (essentially, changing the order of summation). $\endgroup$ – Seva Jan 28 '14 at 20:42
  • $\begingroup$ I think I see... however, in the special case, you still need to know the max index for the summation (which happened to be $(3\delta-1)n/2=|A\cap 2A|/2$, right?). Does it also hold for "bigger" $\delta$'s, greater than $1/2$? $\endgroup$ – Clement C. Jan 28 '14 at 20:49
  • $\begingroup$ Not exactly. In this case, I think, there will be exactly two elements with $(2\delta-1)p$ representations, two elements with $(2\delta-1)p+1$ representations, etc (up to rounding). You can easily figure it out as we are speaking about the special case where $A$ is centered around $p/2$ and has size $\delta p$. $\endgroup$ – Seva Jan 28 '14 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.