Tag Archives: Sumset inequalities

An Analytic Approach to the Cardinality of Sumsets

Additive Combinatorics, Uncategorized,

Dávid Matolcsi, Imre Ruzsa, Dmitrii Zhelezov and I just uploaded our paper, “An analytic approach to cardinalities of sumsets” to the arXiv. Alongside Ben Green, we also uploaded a follow up paper, “A weighted Prékopa-Leindler inequality and sumsets with quasi-cubes.”

Our focus is sumsets of finite subsets of {\mathbb{Z}^d}. For instance, if {A \subset \mathbb{Z}} and {d} is a positive integer, we have 

\displaystyle |A^d + A^d| =|A+A|^d.

If {A} is not an arithmetic progression, it is known that 

\displaystyle |A+A| \geq 2|A|,

and so we obtain 

\displaystyle |A^d + A^d| \geq 2^d |A|.\ \ \ \ \ (1)

It is natural to look to obtain analogs of (1) for more general subsets of {\mathbb{Z}^d}. For instance, the Brunn-Minkowski inequality implies the continuous analog, 

\displaystyle \mu(X+X) \geq 2^d \mu(X),

whenever {X} is a compact subset of {\mathbb{R}^d}. In the discrete setting such a result is not true. First of all, the notion of cardinality does not distinguish dimension. Thus we can take a one dimensional arithmetic progression and place in {\mathbb{Z}^d}, which will not obtain the growth in (1). For a legitimate {d} dimensional set, one can take an arithmetic progression alongside {d-1} random points and {|A+A| / |A|} will grow only linearly in {d}. There are some situations when we can establish (1). For instance, if {A} contains {\{0,1\}^d}, then Green and Tao showed

\displaystyle |A+A| \geq 2^{d/2} |A|.

Freiman (see chapter 5 of Tao and Vu) also showed if {A \subset \mathbb{Z}^d} such that every hyperplane intersects {A} in {\ll_{d, \epsilon} |A|} points, then 

\displaystyle |A+A| \geq (2^d - \epsilon) |A|.

We also mention the work of Gardner and Gronchi, who prove inequalities for general {d}-dimensional sets. The drawback there is that the extremal examples are nearly one dimensional, and particular they only derive growth that is linear in the dimension. We provide a result in a similar spirt to Green and Tao. To state our result, we need a definition. We define a quasi-cube inductively (on the dimension). Any two point set is a 1-dimensional quasi-cube. A {d} dimensional set {U} is a quasi-cube if {U = U_0 \cup U_1} where {U_0 ,U_1}, where {U_j = (x_j + L_j) \cap U}, with {x_j \in \mathbb{Z}^d}, {L_j} a hyperplane and {U_0,U_1} are themselves quasi-cubes. A cube is a quasi-cube. Also, the trapezoid: 

\displaystyle U = \{(0,0) , (1,0), (0,1) , (1,x)\} , \ \ \ \text{with} \ \ x \neq 0,

is a quasi-cube.

{\ } Theorem 1: Let {A \subset \mathbb{Z}^d} be finite. Suppose that A contains U which a subset of a quasi-cube. Then 

\displaystyle |A+A| \geq |U|^{1/2} |A|, \ \ \ \spadesuit.{\ }

This has applications to the sum-product problem via the Bourgain-Chang argument and will be explored in a future paper of Pálvölgyi and Zhelezov. We discuss some of the ideas. As mentioned above, Theorem 1 can be thought of as a discrete analog of the Brunn-Minkowski inequality. The Brunn-Minksowski inequality can be proved using the Prékopa-Leindler inequality, and this is the viewpoint we adopt. 

To start, for {A,B \subset \mathbb{Z}}, we have 

\displaystyle |A+B| \geq |A| + |B| - 1,\ \ \ \ \ (2)

and for {X,Y \subset \mathbb{R}^d} are compact, we have 

\displaystyle \mu(X+Y) \geq \mu(X) + \mu(Y).\ \ \ \ \ (3)

Both can be proved in the same way: by finding a translate of {X} and a translate of {Y} in {X+Y} that are almost disjoint. In the continuous setting (3) is used to establish a functional analog. For compactly support and bounded {f,g:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}} we define

\displaystyle f \mathbin{\overline *} g(z) : = \sup_{x+y =z} f(x) g(y).

Then the Prékopa-Leindler inequality implies that

\displaystyle \int f \mathbin{\overline *} g \geq ||f||_2 ||g||_2.\ \ \ \ \ (4)

When {f=1_X} and {g=1_Y}, we obtain a weaker variant of (3):

\displaystyle \mu(X+Y) \geq 2 \mu(X)^{1/2} \mu(Y)^{1/2}.

To go in the other direction, one applies (3) to the level sets of {f} and {g}. Gardner’s survey provides more accurate implications along these lines. Thus it is natural to ask for a functional analog of (2). Indeed, we let {a,b: \mathbb{Z} \rightarrow \mathbb{R}_{\geq 0}} be compactly supported. Then Prékopa showed that

\displaystyle ||a \mathbin{\overline *} b|| \geq 2 ||a||_2 ||b||_2 - 1.\ \ \ \ \ (5)

We invite the reader to try to discover a proof, it is rather non-trivial! In any case, the next step in Prékopa-Leindler is to tensorize, as is explained in this blog post of Tao or section 4 of the aforementioned survey of Gardner. The point is the integral inequality (4) can be obtained by induction on the dimension by applying the lower dimensional analog of (4) to functions such as {f(x_1 , \ldots , x_{d-1} , x_d)} with {x_d} fixed. Doing this, one obtains, for compactly support and bounded {f,g:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}} 

\displaystyle \int f \mathbin{\overline *} g \geq ||f||_2 ||g||_2.

A slight generalization of this inequality quickly implies the Brunn-Minkowski inequality. In the discrete setting, the {-1} present in both (2) and (5) are quite a nuisance, particularly in the tensorization step. To get around this, we observe that 

\displaystyle |A+B+U| \geq |A|+|B| \geq 2 |A|^{1/2} |B|^{1/2},

{U \subset \mathbb{Z}} of size 2. It turns out one has 

\displaystyle ||a \mathbin{\overline *} b \mathbin{\overline *} 1_U|| \geq 2 ||a||_2 ||b||_2 ,

as was originally observed by Prékopa himself. One has an easier time tensorizing this, and following this one can obtain 

\displaystyle |A+B+\{0,1\}^d| \geq |A|^{1/2} |B|^{1/2}.

In our work, we take an abstract approach, defining

\displaystyle \beta(U) = \inf_{A,B \neq \emptyset} \frac{|A+B+U|}{|A|^{1/2} |B|^{1/2}}.

Note that {\beta(U) \leq |U+U+U|/|U|}. Indeed, {\beta} is intended to be a replacement of the usual notion of the doubling constant, {|U+U|/|U|}. It turns out for certain large dimensional sets, we can accurately estimate {\beta}. For instance, we show that if {U} is a subset of a quasi-cube then

\displaystyle \beta(U) = |U|,

which quickly implies Theorem 1. The upper bound follows immediately from the definition of {\beta}, it is the lower bound that takes some work. To do this, we show that this is the same as a functional analog and that tensorization occurs in general. We also explore general properties (for instance {\beta} is independent of the ambient group) and present a bunch of conjectures (which may be interpreted as things we were unable to prove or disprove). 

The above outline nearly works for subsets of quasi-cubes, though it turns out one needs a stronger 1 dimensional inequality of the form

\displaystyle ||f \mathbin{\overline *} g \mathbin{\overline *} h_{\delta}||_1 \geq (1+\delta) ||f||_2 ||g||_2,

where {h = (1,\delta)}. The cases {\delta = 0,1} were already known but for other values of {\delta} it is tricker. There are now two proofs: in the original paper we use a variational argument while in the follow up paper we derive it from the Prékopa-Leindler inequality.

This is a sort of “tensorization plus two point inequality argument,” which is present in other works (i.e. Beckner’s inequality).

Sum of a set and its dilate

Additive Combinatorics, ,

Let {A, B \subset \mathbb{Z}} be finite and nonempty. One of the first things we learn in additive combinatorics is

\displaystyle |A+B| \geq |A| +|B| - 1. \ \ \ \ \ (1)

There are a host of results improving on (1) when {B} has certain structure. For instance, all of the following have an short and elementary proof. Here {q \cdot A := \{qa : a \in A\}}.

  • (1) {|A+2\cdot A| \geq 3 |A| - 2}
  • (2) {|A+A -A| \gg |A|^2}, for {A} convex,
  • (3) {|A+AA| \geq |A|^2 + |A| - 1},
  • (4) {|A + A^{-1}| \geq |A|^2}.

Let’s see one way to prove (1). After translation and dilation, we may suppose that {A} contains both even and odd numbers. Let {A_0} be the even numbers in {A} and {A_1} be the odd numbers in {A}. By (1),

\displaystyle |A+2 \cdot A| = |A_0 + 2 \cdot A| + |A_1 + 2 \cdot A| \geq |A_0| + |A| - 1 + |A_1| + |A| - 1 = 3 |A| - 2.

We remark that there is another proof of this in which one picks {2 |A| - 3} elements of {A+2 \cdot A} in increasing order.

Antal Balog and I considered the question of improving (1) when {B = q \cdot A }. We proved the following.

Theorem 1: Let {q\geq 1} be an integer and {A \subset \mathbb{Z}} be finite. Then

\displaystyle |A+q \cdot A| \geq (q + 1) |A| - O_q(1). \ \ \ \spadesuit

This is best possible up to the constant as can be seen by taking {A} to be an arithmetic progression. Below in the fold, we will a proof in the case where {q} is a prime. This case is technically easier, and was first handled by Cilleruelo, Hamidoune, and Serra. Already the case {q=3} is non–trivial, though a proof of {|A+3 \cdot A| \geq 4 |A| - 4} had appeared several times in the literature. We adopt the proof from our paper, which can be modified to handle the general case.

We partition {A} into residue classes modulo {q} as follows:

\displaystyle A = \displaystyle \bigcup_{j = 1}^s A_j , \ \ A_j = a_j + q \cdot A_j^{\prime}, \ \ A_j \neq \emptyset ,\ \ 0 \leq a_j < q.\ \ \ \ \ (2)

We say {A} is fully–distributed mod {q} (FD) if {s=q} or equivalently {A} intersects every residue class modulo {q}. The key fact is that not only the sets {A_i} are disjoint, but so are the sets {A_i + q \cdot A} and we have

\displaystyle A + q \cdot A= \coprod_{i =1}^s A_i + q \cdot A.\ \ \ \ \ (3)

As long as {|A| \geq 2}, we may assume that {s \geq 2} since we may replace {A} with {\frac{1}{q} \cdot (A - x)}. This is actually a key point: Theorem 1 is translation and dilation invariant. We first show that Theorem 1 is true for random sets.

Lemma (FD): Suppose {A} is FD. Then

\displaystyle |A+q \cdot A| \geq (q+1)|A| - q. \ \ \ \spadesuit

Proof: By (1) and (3), we have

\displaystyle |A+q \cdot A| = \sum_{j=1}^q |A_j + q \cdot A| \geq \sum_{j=1}^q \left(|A_j |+ |A| - 1 \right) = (q + 1)|A| - q. \ \ \ \spadesuit

Now we are in a position to prove Theorem 1.

Proof of Theorem 1: We prove

\displaystyle |A+q \cdot A| \geq \frac{m}{q} |A| - C_m,\ \ \ \ \ (4)

by induction on {m}. For {m = 2q}, this follows from (1) with {C_m = 1}. We now assume (4) holds for some {m < q(q+1)} and show it for {m+1}.

Suppose that there is some {1 \leq i \leq s} such that {|A_i| \leq q^{-1} |A|}. Then by (1), (4) and {m < q(q+1)}, we have

\displaystyle |A+q \cdot A| \geq |A_i + q \cdot A| + |(A \setminus A_i) + q \cdot (A \setminus A_i)|

\displaystyle \geq |A_i| + |A| - 1 + \frac{m}{q} (|A| - |A_i|) - C_m \geq \frac{m+1}{q} |A| - C_m - 1.

Suppose now that {A_i'}, as defined in (2) is FD for all {1 \leq i \leq s}. By (3) and translation and dilation invariance of {|X+ q \cdot X|}, we have

\displaystyle |A+q \cdot A| \geq \sum_{j=1}^s |A_j + q \cdot A_j| = \sum_{j=1}^s |A'_j + q \cdot A'_j| \geq (q+1) |A| - q^2.

Thus we may suppose that

\displaystyle |A_i| \geq \frac{|A|}{q} , \ \ 1 \leq i \leq s,\ \ \ \ \ (5)

and there is some {k} such that {A'_k} is not FD. We then apply the following lemma.

Lemma (not FD): Suppose {A_k'} is not FD. Then

\displaystyle |A_j+ q \cdot A| \geq |A_j + q \cdot A_j| + \min_{1 \leq m \leq s} |A_m|. \ \ \ \spadesuit

Let’s use Lemma (not FD) to finish the proof. By Lemma (not FD), (4) twice and (5) we have

\displaystyle |A+q \cdot A| \geq |A_k + q \cdot A| + |(A \setminus A_k) + q \cdot (A \setminus A_k)|

\displaystyle \geq |A_k + q \cdot A_k| + \min_{1 \leq m \leq s} |A_m| + \frac{m}{q} (|A| - |A_k|) - C_m

\displaystyle \geq \frac{m}{q} |A_k| - C_m + \frac{|A|}{q} + \frac{m}{q} (|A| - |A_k|) - C_m

\displaystyle = \frac{m+1}{q} |A| - 2 C_m.

This completes the proof modulo Lemma (not FD).

Proof of Lemma (not FD): Suppose

\displaystyle |A_k + q \cdot A| < |A_k + q \cdot A_k| + \displaystyle \min_{1 \leq m \leq s} |Q_m|.

Then for any {1\leq m \leq s}, we have

\displaystyle |A_m^{\prime}| = |A_m| > |(A_k+ q \cdot A_m )\setminus (A_k+ q \cdot A_k) | = |(a_m - a_k + A_k^{\prime} + q \cdot A_m^{\prime}) \setminus (A_k^{\prime} + q \cdot A_k^{\prime})|.

It follows that for every {x \in A_k^{\prime}} there is a {y \in A_m^{\prime}} such that {a_m-a_k+x+qy\in A'_k + q\cdot A'_k}, and so there is an {x'\in A'_k} such that

\displaystyle a_m - a_k + x \equiv x' \pmod q.

We may repeat this argument with {x'} in place of {x} and so on to get that for every {x \in A'_k} and {w \in \mathbb{Z}}, there is {z \in A'_k} such that

\displaystyle w(a_m - a_k) + x = z \pmod q.

Since {q} is prime, we get that {A'_k} is FD, as desired. {\spadesuit}

Since this work, I worked out the general case of sum of many dilates. After that, Antal Balog and I worked on the analogous problem in vector spaces. Both papers contain several open problems and one of them appears on my problems page. Further, there is a paper of Breuillard and Green on contraction maps, for which sum of dilates is a special case. Also, feel free to see my short video I made on the topic, which highlights some of the problems.

One natural generalization that remains open is

\displaystyle |A+q \cdot A| \geq (|q| + 2d -1)|A| - O_{d , q}(1),

where {A \subset \mathbb{Z}^d} and not contained in any {d-1} dimensional subspace. The cases {d=2} and {d=3} are known to hold.

Breaking the 6/5 threshold for sums and products modulo a prime

Additive Combinatorics, ,

Ilya Shkredov and I just released our preprint, “Breaking the 6/5 threshold for sums and products modulo a prime.”

Since this paper of Roche–Newton, Rudnev, and Shkredov, the best bound for the sum–product problem in {\mathbb{F}_p} was given by the following.

Theorem (Sum–Product): Let {A \subset \mathbb{F}_p} of size at most {p^{5/8}}. Then

\displaystyle |A+A| + |AA| \gg |A|^{6/5}. \ \ \spadesuit

The major breakthrough was a point–plane incidence theorem of Rudnev. Let us recall their proof, which has been simplified since their original.

We consider the set of points and lines

\displaystyle P = (A+A) \times (AA), \ \ \ \mathcal{L} = \{(u,v) \in \mathbb{F}_p^2 : v = a(u - c)\}_{a , c \in A}.

Note that each line contains the points {(b + c , ab)} and so there are at least {|A|^3} incidences. On the other hand, one may apply a point–line incidence, for instance the cartesian version found in Theorem 4 of this paper of Stevens and Zeeuw to obtain an upper bound for the number of incidences between {P} and {\mathcal{L}}. Combining these two bounds gives Theorem 1.

We are able to make the following improvement.

Theorem 1: Let {A \subset \mathbb{F}_p} of size at most {p^{3/5}}. Then

\displaystyle |A+A| + |AA| \gg |A|^{6/5 + c}, \ \ \ c = 4/305. \ \ \spadesuit

We can improve this application of a Szemerédi–Trotter type bound in the specific case of the sum–product problem. The basic idea is to evaluate the above proof and obtain a bound for the {\tau}–rich lines, instead of incidences. We then obtain the bound for the higher order energy:

\displaystyle d_4^+(A) \lesssim |AA|^2 |A|^{-2} , \ \ d_4^+(A) := E_4^+(A,B) |A|^{-1} |B|^{-3}.\ \ \ \ \ (1)

A simple application of Cauchy–Schwarz gives

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

Combining (1) and (2) recovers Theorem 1. We are able to make an improvement to (2) and in turn to the sum–product problem.

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