MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$)).



share|cite|improve this question
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? – Seva Jan 28 '14 at 20:30
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) – Clement C. Jan 28 '14 at 20:37
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). – Seva Jan 28 '14 at 20:42
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$? – Clement C. Jan 28 '14 at 20:49
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$. – Seva Jan 28 '14 at 21:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.