MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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