Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

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|improve this answer
1  
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
add comment

Your Answer

 
discard

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.