# Does $|A+A|$ concentrate near its mean?

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

• 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. – Seva Feb 7 '16 at 20:27
• Not quite. See below. – 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|)/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.
• 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}$. – user36212 Feb 8 '16 at 10:54
• @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. – George Shakan Feb 8 '16 at 15:11
• 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. – user36212 Feb 9 '16 at 12:27