Tag Archives: Erdos Szemeredi conjecture

Convex sets have many differences

Additive Combinatorics, , ,

Thanks to Sophie Stevens for helpful discussions at the Georgia discrete analysis conference leading to this post. We show that if {A} has small (slightly generalized) third order energy, then {A} has a large difference set. We present an argument due to Shkredov and Schoen. This has the advantage of being drastically simpler (and slightly stronger) than the analog for sumsets, which was discussed in this previous blog post. We say {b \gtrsim a} if {a = O(b \log^c |A|)} for some {c >0}.

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\}.

We have the following difference–product conjecture.

Conjecture 1: Let {\delta \leq 1}. Then for any finite {A \subset \mathbb{Z}} one has

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

We say a finite {A = \{a_1 < \ldots < a_k\} \subset \mathbb{R}} is convex if

\displaystyle a_{i+1} - a_i > a_i - a_{i-1}, \ \ \ 2 \leq i \leq k-1.

The following conjecture is due to Erdős.

Conjecture (Convex): Suppose {A \subset \mathbb{R}} is convex. Then

\displaystyle |A-A| \gtrsim |A|^2. \ \ \spadesuit

Study of the quantity {d^+(A)} has played a crucial role in recent progress on both conjectures, which we define now. For {A \subset \mathbb{R}} finite, we define

\displaystyle d^{+}(A) := \sup_{B \neq \emptyset}\frac{ E_3^+(A,B) }{|A| |B|^2},

where

\displaystyle E_3^+(A,B) = \sum_x r_{A- B}(x)^3 , \ \ \ \ r_{A-B}(x) = \#\{(a, b ) \in A \times B : x = a - b\}.

See my recent paper on Conjecture 1 for a lengthy introduction to {d^+(A)}. We mention here that {1 \leq d^+(A) \leq |A|} and intuitively the larger {d^+(A)} is the more additive structure {A} has. For instance, we have

\displaystyle E_3^+(A) \leq d^+(A) |A|^3. \ \ \ \ \ (1)

Indeed {d^+(A)} is a higher order analog of the more common additive energy of a set, where we have some flexibility in choosing {B} (for instance, we choose {B = A-A} below).

An application of Cauchy–Schwarz, as explained in equation 2 of this paper, reveals

\displaystyle |A|^{3/2} \leq |A-A| d^+(A)^{1/2}.\ \ \ \ \ (2)

Thus if {d^+(A) \lesssim 1}, we have that {|A+A| \gtrsim |A|^{3/2}}. We conjecture that this can be improved.

Conjecture (dplus): Let {A \subset \mathbb{R}} be finite. Then

\displaystyle |A-A| \gtrsim |A|^2 d^+(A)^{-1}. \ \ \ \ \spadesuit

This would imply Conjecture (Convex) and Conjecture 1 for {\delta = 1/2}. The goal of the rest of this post is to prove the current state of the art progress due to Shkredov and Schoen. The proof of Theorem 1 is simple enough that we compute the constant.

Theorem 1: Let {A} be a subset of any additive group. Then

\displaystyle |A-A| > \frac{|A|^{8/5}}{4d^+(A)^{3/5}}. \ \ \ \spadesuit

We will use

\displaystyle E_3^+(A) = \sum_x E^+(A, A_x) ,\ \ \ \ \ (3)

as is explained using a simple geometric argument in equation 9 of this paper of Murphy, Rudnev, Shkredov, and Shteinikov. For {x \in A-A}, let

\displaystyle A_x := A \cap (A + x).

Thus

\displaystyle |A_x| = r_{A-A}(x).

Let

\displaystyle P =\{x \in A-A : r_{A-A}(x) \geq \frac{|A|^2}{2|A-A|}\},

be the set of popular differences. Thus

\displaystyle \sum_{x \in P} r_{A-A}(x) \geq (1/2) |A|^2.\ \ \ \ \ (4)

By two applications of Cauchy–Schwarz,

\displaystyle \sum_{x \in P} |A_x| |A| = \sum_{x \in P } \sum_y r_{A - A_x}(y) \leq \sum_{x\in P} E^+(A,A_x)^{1/2} |A - A_x|^{1/2} \leq \left(\sum_x E^+(A,A_x) \sum_{x \in P} |A- A_x| \right)^{1/2} .

Combining this with (3) and (4), we find

\displaystyle \frac{|A|^6}{4E_3^+(A)} \leq \sum_{x \in P} |A - A_x|.

Now we use Katz–Koelster inclusion of the form

\displaystyle A- A_x \subset (A-A) \cap (A - A -x),

to find

\displaystyle \frac{|A|^6}{4E_3^+(A)} \leq \sum_{x \in P} |D \cap (D - x) |, \ \ \ D := A- A.

Since {x \in P}, we have {(1/2) |A|^2 |A-A|^{-1} \leq r_{A-A}(x)}, and so 

\displaystyle \frac{|A|^6}{4E_3^+(A)} \leq \frac{2 |A-A|}{|A|^2} \sum_{x \in P} r_{D-D}(x)r_{A-A}(x) \leq \frac{2|A-A|}{|A|^2} E^+(A,D).\ \ \ \ \ (5)

By Cauchy–Schwarz (interpolating {\ell_2} between {\ell_3} and {\ell_1}), we have

\displaystyle E^+(A,D)^2 \leq E_3^+(A,D) |A||D|,

and so by the definition of {d^+(A)}, (2), and (5), we arrive at

\displaystyle \frac{|A|^{15}}{64|D|^{3}} \leq E_3^+(A)^2 E_3^+(A,D) \leq d^+(A)^3 |A|^7 |D|^2.

Simplifying gives the (slightly stronger) desired

\displaystyle \frac{|A|^8}{64 d^+(A)^3} \leq |A-A|^5. \ \ \ \spadesuit

Developing a fourth moment analog of the above result would be worthwhile as it would have applications to finite field sum-product problem (edit: Ilya Shkredov and I pursued this idea further in a recent preprint).

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.