On higher energy decompositions and the sum-product phenomenon

Additive Combinatorics, ,

I just uploaded my paper On higher energy decompositions and the sum–product phenomenon to the arXiv. In this paper we make progress on the Erdős–Szemerédi sum–product conjecture and the Balog–Wooley decomposition.

Let {A, B \subset \mathbb{R}} be finite. We define the sumset and product set via

\displaystyle A+B := \{a + b : a \in A , b \in B\} , \ \ \ \ \ \ AB := \{ab : a \in A , b \in B\}.

In this post, we adopt the convention {b \gtrsim a} if {a = O(b \log^c |A|)} for some {c >0} and {a \sim b} if {b \gtrsim a} and {a \gtrsim b}.

Conjecture (ESconj): Let {\delta < 1}. Then for any finite {A \subset \mathbb{Z}} one has

\displaystyle |A+A| + |A A| \gtrsim |A|^{1 + \delta}. \ \ \spadesuit

To state the Balog–Wooley decomposition we recall the additive and multiplicative energy. Define two representation functions of {x \in \mathbb{R}}:

\displaystyle r_{A-B}(x) = \#\{(a,b) \in A \times B : x = a - b\} ,

\displaystyle r_{A/B}(x) = \#\{(a,b) \in A \times B : a = xb\} .

The additive energy and multiplicative energy of {A} and {B} are defined via

\displaystyle E^{+}(A,B) = \sum_x r_{A-B}(x)^2 , \ \ \ \ \ \ \ \ E^{\times}(A,B) = \sum_x r_{A/B}(x)^2.

We set {E^{+}(A) = E^{+}(A,A) } and {E^{\times}(A) = E^{\times}(A,A) }.

Theorem (BW): Let {A} be a finite subset of the real numbers and {\delta = 2/33}. Then there exist {B,C} that partition {A} satisfying

\displaystyle {\rm max}\{ E^{+}(B) , E^{\times}(C) \} \lesssim |A|^{3-\delta}, \ \ \ \ {\rm max} \{ E^{+}(B,C) , E^{\times}(B,C) \}\lesssim |A|^{3-\delta/2}. \ \ \spadesuit

Thus any set can be decomposed into two sets, one with little additive structure and the other with little multiplicative structure. The Balog–Wooley decomposition was improved by Konyagin and Shkredov, and later by Rudnev, Shkredov and Stevens. In this paper we make further improvements. To do this, we provide higher order energy decomposition results. To state our results, for a positive real number {k}, we define the {k^{\rm th}}–order energy via

\displaystyle E_k^{+}(A,B) = \sum_x r_{A-B}(x)^k , \ \ \ \ \ \ \ \ E_k^{\times}(A,B) = \sum_x r_{A/B}(x)^k.

Our main contributions are the following.

Theorem 1: Let {A \subset \mathbb{R}} be finite. Then there exists {X , Y \subset A} such that {A = X \cup Y}, {|X| ,|Y| \geq |A| /2}, and

\displaystyle \max_{B \neq \emptyset} \frac{E_3^+(X, B)}{|X| |B|^2} \max_{C \neq \emptyset} \frac{E_3^{\times}(Y, C)}{|Y| |C|^2} \lesssim |A|. \ \ \spadesuit

Theorem 2: Let {A \subset \mathbb{R}} be finite. Then there exists {X , Y \subset A} such that {A = X \cup Y}, {|X| ,|Y| \geq |A| /2}, and

\displaystyle \max_{B \neq \emptyset} \frac{E_4^+(X, B)}{|X| |B|^3} E^{\times}(Y)\lesssim |A|^3. \ \ \spadesuit

Theorem 1 and Theorem 2 are best possible, as can be seen by taking {A} to be an arithmetic or geometric progression. Both of these theorems would by implied by the following.

Conjecture 1: Let {A \subset \mathbb{R}} be finite. Then there exists {X , Y \subset A} such that {A = X \cup Y}, {|X| ,|Y| \geq |A| /2}, and

\displaystyle \max_{B \neq \emptyset} \frac{E^+(X, B)}{|X| |B|} \max_{C \neq \emptyset} \frac{E^{\times}(Y, C)}{|Y| |C|} \lesssim |A|.\ \ \spadesuit

By Cauchy–Schwarz, Conjecture 1 would imply that

\displaystyle |A+A||AA| \gtrsim |A|^3,

which would be a major breakthrough.

Nevertheless, we are able to use Theorem 1 and Theorem 2 to make improvements in various sum–product problems, including Conjecture (ESconj).

Theorem 3: Let {A \subset \mathbb{R}} be finite. Then

\displaystyle |AA| + |A+A| \gtrsim |A|^{4/3 + 5/5277}. \ \ \spadesuit

We adopt the approach of Konyagin and Shkredov, as outlined in this previous blog post, and use Theorem 2 to make a technical improvement.

The skeletons of the proofs of Theorem 1 and Theorem 2 are identical. They both adopt the Balog–Wooley strategy, that is use an iterative argument to combine two key lemmas. The first is a rather easy lemma concerning how the multiplicative and additive energy behaves with respect to unions. The second is at the heart of the proof, which says if the additive energy is large, then there is a large subset that has small multiplicative energy. Note it is the second lemma that relates addition to multiplication. It is the second lemma that is significantly different in both Theorem 1 and Theorem 2.

In Theorem 1, we use an argument of Konyagin and Shkredov, which relies on the Szemerédi–Trotter theorem. This can be thought of a more sophisticated version of Elekes’ original half page argument that showed {\delta = 1/4} is admissible in Conjecture (ESconj).

In Theorem 2, we modify an argument used in this recent paper of Rudnev, Shkredov, and Stevens. Their argument hinges on bounding the number of solutions to

\displaystyle \frac{p+b}{q + c} = \frac{p' + b'}{q' + c'} , \ \ \ p , q , p' , q' \in P , \ \ b , c , b' , c' \in B,

which appeared in this paper of Murphy, Roche–Newton, and Shkredov.

Leave a Reply