8
$\begingroup$

Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My question is what kind of concentration inequalities do we have for the random variable $|A+A|$?

$\endgroup$
  • 4
    $\begingroup$ You have $|A+A|=I_0+I_1+\dotsb+I_N$, where $I_z$ is the indicator random variable of the event $z\in A+A$. It may be a little technical, but should not be difficult in principle to show that the $I_z$ are "almost independent", the exact meaning of which is that the pair correlations of $I_u$ and $I_v$ are small for $u\ne v$. As a result, $|A+A|$ should have a distribution close to the binomial. $\endgroup$ – Seva Feb 7 '16 at 20:27
  • 4
    $\begingroup$ Not quite. See below. $\endgroup$ – Yuval Peres Feb 8 '16 at 2:33
8
$\begingroup$

If $\epsilon>1/6$ then $|A+A|=N$ with high probability. Suppose that $\epsilon<1/6$. Call a pair $(x,y) \in {\mathbb Z}/N{\mathbb Z} \times {\mathbb Z}/N{\mathbb Z} $ "bad" if $(x,y) \in A \times A $ and there is another pair $(z,w) \in A \times A $ (also different from $(y,x)$), such that $z+w=x+y$. The probability that a particular pair $(x,y) \in {\mathbb Z}/N{\mathbb Z} \times {\mathbb Z}/N{\mathbb Z} $ will be "bad" is at most $Np^4$ so the expected number of "bad" pairs is at most $N^3 p^4$. Every good pair $(x,y)$ contributes one element to $|A+A|$, with $(y,x)$ yielding the same eklement. By Markov's inequality, $|A+A| \ge (|A|^2+|A|)/2-O(N^3 p^4)$ with high probability. Under the assumption $\epsilon<1/6$, we have that $N^3p^4$ is negligible compared to $N^2p^2$ so $|A+A|$ will be well approximated by $|A|^2/2$, which is half the square of a Binomial variable.

$\endgroup$
  • $\begingroup$ Thanks! Do you think it's possible to prove with probability one minus something exponential in N, as suggested by the distribution? $\endgroup$ – George Shakan Feb 8 '16 at 4:42
  • $\begingroup$ No, you'll get tails (for $\varepsilon<1/6$) with measure something like $e^{-pN}$. The probability that you pick a set $A$ which happens to have additive structure is really tiny, so you can assume that $|A+A|$ is more or less $|A|^2/2$ (the difference to Peres' answer is because we are in a commutative group). The main contribution to the tails of $|A+A|$ is the event that $|A|$ is far from its mean. If you let $\varepsilon$ go above $1/6$, this doesn't change much: the expectation of $|A+A|$ becomes $N$, there is no upper tail, but the lower tail will still have weight $e^{-pN}$. $\endgroup$ – user36212 Feb 8 '16 at 10:54
  • $\begingroup$ @user36212 Assume $\epsilon$ is tiny. Then you are saying one should expect $|A+A|$ is close to it's average with probability approximately $1- e^{N^{1/3+\epsilon}}$? This is not clear to me, in particular how do you show that $|A+A|$ has size $\geq |A|^2/2 - p^4N^3$ with extremely high probability. $\endgroup$ – George Shakan Feb 8 '16 at 15:11
  • $\begingroup$ The p^4n^3 term is pretty irrelevant here, as it's much less than p^2n^2. So you want to know something about the probability of it being below $(1-\delta)p^2n^2/2$. The lower tail for $|A|$ is binomial, so you want to know how likely it is that there are $o(\delta p^2n^2)$ solutions to $a+b=c+d$ in $A$. This is an upper tail, and as usual proving things is a pain. I would try the Kim-Vu inequality and see if it works. $\endgroup$ – user36212 Feb 9 '16 at 12:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.