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

  • $\begingroup$ 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. $\endgroup$
    – Seva
    Apr 9, 2012 at 6:53
  • $\begingroup$ I meant something else, apologies. I edited now and it should make sense. $\endgroup$ Apr 9, 2012 at 7:13

1 Answer 1


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.

  • 2
    $\begingroup$ This, by the way, is the solution to Exercise 2.3.21 of my book with Van Vu. $\endgroup$
    – Terry Tao
    Apr 9, 2012 at 19:15
  • $\begingroup$ @Boris Bukh: Thanks a lot! I was actually trying something earlier today with sets of the form $n^{\alpha} \left\{1,\ldots,n\right\}$... $\endgroup$ Apr 10, 2012 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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