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

As the subject says, I have some questions about some Ruzsa-type inequalities for additive-energy. It would be wonderful if anyone could shed some light.

First, the definition: let $E(A,B)$ be the number of all quadruples $(a,a',b,b') \in A \times A \times B \times B$ such that $a+b = a' + b'$ denote the additive energy of the sets $A$, $B$, and let $F(A,B)= \frac{|A|^{2}|B|^{2}}{E(A,B)}$.

Now let $A, B, C \subset G$ be subsets of an additive group $G$ so that $|A|=|B|=|C|=N$. Do the following inequalities hold?

1) If $F(A,B), F(A,C) \leq K\cdot N$, then $\min{(F(A, B+C), F(B, C+A), F(C, A+B))} \leq K^{c} N$, for some constant $c$.

2) If $F(A,A) \leq K\cdot N$, then for all non-negative integers $k,l$ there's a constant $c$ depending on them such that $F(k \cdot A, l \cdot A) \leq K^{c} N$.

share|cite|improve this question
Counting the trivial solutions only, you get $E(A,B)\ge|A||B|$ for any $A$ and $B$. Hence, for $|A|=|B|=N$, you cannot have $E(A,B)\le KN$, unless $K\ge N$. This implies that the answers to your questions are positive, for a trivial reason. – Seva Apr 9 '12 at 6:53
I meant something else, apologies. I edited now and it should make sense. – Cosmin Pohoata Apr 9 '12 at 7:13
up vote 4 down vote accepted

1) No. Let $A=B=C$ be a set that is a union of interval $\{1,\dots,N\}$ and $N$ random elements from $\{1,\dotsc,N^2\}$. Then $F(A,A)=KN$ for some constant $K$. On the other hand, $A+A$ is basically the interval $\{1,\dotsc,N^2\}$. So, $F(A,A+A)\approx N^2$.

2) Example above show that it fails for $k=1$ and $l=2$ (from the context I assume that $k\cdot A$ means $k$-fold sumset $A+\dotsb+A$, not the $k$-dilate $\{ka:a\in A\}$. If dilates were meant, then the assertion is true, and one can deduce this from the Balog–Szemerédi–Gowers theorem).

I want to add that there do exist Ruzsa-type inequalities for additive energy. Instead of sumsets, they involve a suitable extension of additive energy to more than two sets. See Razborov's paper on the product theorem in the free group (in section 6), for example.

share|cite|improve this answer
This, by the way, is the solution to Exercise 2.3.21 of my book with Van Vu. – Terry Tao Apr 9 '12 at 19:15
@Boris Bukh: Thanks a lot! I was actually trying something earlier today with sets of the form $n^{\alpha} \left\{1,\ldots,n\right\}$... – Cosmin Pohoata Apr 10 '12 at 4:53

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.