# Additive energy of random sets

Given two random sets $A,B$ in a finite field (say $x\in A$ independently and with probability $1/2$), what is known about the additive energy $E(A,B)=|\{(a,a',b,b')\in A\times A\times B\times B: a+b=a'+b'\}|$?

Equivalently, what is the distribution of the random variable $\|1_A*1_B\|_2$? I'm mostly interested in asap (as sharp as possible) upper bounds for the probability of it being large.

-
The expectation of $E(A, B)$ is $N^3/16$, where $N$ is the number of elements in the field. Each quadruple interferes with only $O(N^2)$ other quadruples, so the standard deviation will be a $o(1)$ fraction of the mean and Chebyshev will give you concentration. I don't know offhand how sharp the concentration is in this case. –  Ben Barber Nov 26 '12 at 17:31

Expanding on my earlier comment, the concentration has to be really quite good: at least exponential in $N$, the order of the additive group. (Edit: and you can't get better concentration because the state space is only exponentially large.)
Recall the following variant of the Hoeffding-Azuma martingale concentration inequality. Let $\Omega = \Omega_1 \times \cdots \times \Omega_n$ be a product space, and let $X$ be a random variable on $\Omega$ such that $X(\omega)$ changes by at most $k$ if we change a single coordinate of $\omega$. Then $$\mathbb{P}(X \geq (1+t)\mu) \leq \exp (-2t^2\mu^2/nk^2),$$ where $\mu=\mathbb{E}(X)$.
Apply this with $n=2N$, $\Omega$ the space of coin flips determining membership of each element of the group in $A$ and $B$, and $X=E(A,B)$. We have $\mu = N^3/16$ and $k = O(N^2)$ (as each element of the group is in $O(N^2)$ additive quadruples), which gives $$\mathbb{P}(X \geq (1+t)\mu) \leq \exp(-ct^2N),$$ for some absolute constant $c$.
An alternative viewpoint as to why the bound here is essentially tight: A random set $A$ will have size at least $(\frac{1}{2}+t)N$ with probability at least $\exp(-c_0 t^2 N)$ for some $c_0$. Whenever this happens, the energy is likely to increase by a constant factor as well. –  Kevin P. Costello Nov 30 '12 at 22:32