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|$?
$\begingroup$
$\endgroup$
2
-
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$– SevaCommented Feb 7, 2016 at 20:27
-
4$\begingroup$ Not quite. See below. $\endgroup$– Yuval PeresCommented Feb 8, 2016 at 2:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Feb 8, 2016 at 2:31
-
$\begingroup$ Thanks! Do you think it's possible to prove with probability one minus something exponential in N, as suggested by the distribution? $\endgroup$ Commented Feb 8, 2016 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$ Commented Feb 8, 2016 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$ Commented Feb 8, 2016 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$ Commented Feb 9, 2016 at 12:27