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$?

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
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)/2O(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.

$\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 KimVu inequality and see if it works. $\endgroup$ – user36212 Feb 9 '16 at 12:27