0
$\begingroup$

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

Thanks,

Clément

$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 21:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.