Category Archives: Additive Combinatorics

Exponential Sums over Small Subgroups

The purpose of the post is to recall a theorem of Bourgain and Konyagin that shows cancellation in exponential sums over multiplicative subgroups of {\mathbb{F}_p}, incorporating the point–plane bound incidence bound due to Rudnev. It is notoriously hard to find cancellation in short exponential sums in {\mathbb{F}_p}, for instance improving the Burgess bound is a fundamental open problem in number theory (see this previous blog post for discussion). Bourgain and Konyagin were able to leverage the sum–product phenomenon to show cancellation in certain sums with as few as {p^{\delta}} terms, improving upon the previous best of { p^{1/4+\epsilon}} due to Konyagin (incidentally the Burgess bound relies on a simpler sum–product type bound).

Let {H \leq \mathbb{F}_p^{\times}} be a multiplicative subgroup. We define the Fourier transform of {H} via

\displaystyle \widehat{1_H}(\xi) : = \frac{1}{p} \sum_{h \in H} e_p(-\xi h) , \ \ \ e_p(\theta) : = e^{2 \pi i \theta / p}. \ \ \ \ \ (1)

In (1) and what follows we adopt the notation of Chapter 4 in Tao and Vu (see also my previous blog post for some basic discussion on the discrete Fourier transform).

For any {\xi \in \mathbb{F}_p}, we have the trivial bound

\displaystyle |\widehat{1_H}(\xi)| \leq \mathbb{P}(H) : = |H| / p,

which is obtained at the zero frequency. On the other hand, {1_H} has multiplicative structure and we expect it cannot correlate with an additive character in light of the sum–product phenomenon. This was verified by Bourgain and Konyagin (see also these notes of Green).

Theorem 1 (Bourgain-Glibichuk-Konyagin): Let {H \leq \mathbb{F}_p^{\times}} of size at least {p^{\delta}}. Then

\displaystyle \sup_{\xi \in \mathbb{F}_p^{\times}}|\widehat{1_H}(\xi)| \leq \mathbb{P}(H) p^{-\epsilon}. \ \ \ \spadesuit

Theorem 1 should be compared to the famous Gauss sum estimate (see for instance this previous blog post), but applies to much smaller multiplicative subgroups. The proof relies on three ideas. The first is that if {|\widehat{1_H}(\xi) |} is large for one {\xi \in \mathbb{F}_p^{\times}}, then it is large for many {\xi \in \mathbb{F}_p^{\times}}. Indeed it follows from (1) that

\displaystyle \widehat{1_H}(h \xi) = \widehat{1_H}(\xi) , \ \ h \in H \ \ \ \ \ (2)

We define the spectrum (see Chapter 4 of Tao and Vu for detailed discussion, as well as these notes of Green) via

\displaystyle {\rm Spec}_{\alpha}(H) : = \{\xi \in \mathbb{F}_p : |\widehat{1_H}(\xi) | \geq \alpha \mathbb{P}(H) \}.

By Parseval’s identity of the form

\displaystyle \sum_{\xi \in \mathbb{F}_p} |\widehat{1_H}(\xi)|^2 = \mathbb{P}(H),

and (2), we find

\displaystyle |H| \leq | {\rm Spec}_{\alpha}(H)| \leq \mathbb{P}(H)^{-1} \alpha^{-2}.\ \ \ \ \ (3)

If {|H| = p^{\delta}}, this gives

\displaystyle \alpha \leq p^{1/2 - \delta},

which is only useful for {\delta > 1/2} (for instance this works quite well for Gauss sums). Thus we need new ideas to handle the case {\delta \leq 1/2}. Note this is in alignment with the principle that basic Fourier techniques intrinsically have a “square root barrier.”

The second idea we will use is that {H} has little additive structure in the following form. Recall the additive energy of {A} and {B} is defined via

\displaystyle E^+(A,B) = \{(a,a' , b , b' ) \in A^2 \times B^2 : a + b = a' + b' \}.

Note that

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

Proposition 1 (Sum–Product): Let {H \leq \mathbb{F}_p^{\times}} and {|H|^2 |A| \leq p^2}. Then

\displaystyle E^+(H ,A) \leq |H| |A|^{3/2} \ \ \ \spadesuit

Proposition 1 should be compared to the trivial bound {E^+(H,A) \leq |H| |A|^2}.

Proof: We will use Rudnev’s point–plane incidence bound (Theorem 3 in this paper). To do so, we note that {E^+(H,A)} counts the number of solutions to

\displaystyle h + a = h' + a' , \ \ \ a , a' \in A , \ h, h' \in H.

Since {H} is a multiplicative subgroup, {|H|^2 E^+(H,A)} is the number of solutions to

\displaystyle hh_1 + a = h' h_1' + a' , \ \ \ a , a' \in A , \ h, h' , h_1 , h_1' \in H.

This is precisely the number of incidences between the point set {H \times H \times A} and planes of the form {h x + a = h' y + z}. Thus by Rudnev’s point–plane incidence bound of the form (note there is a condition on the number of maximum colinnear planes which is trivially satisfied in our cartesian product set–up)

\displaystyle I(P , \Pi) \ll n^{3/2} , \ \ \ |P| = |\Pi| = n,

we find

\displaystyle |H|^2 E^+(H,A) \ll |H|^3 |A|^{3/2} . \ \ \ \spadesuit

We now move onto the third idea and general principle is that {{\rm Spec}_{\alpha}(H)} is additively structured. The following Lemma is due to Bourgain and can be found in Lemma 4.37 in Tao and Vu.

Lemma 1 (Additive Structure in Spectrum): Let {A \subset \mathbb{F}_p} and {0 < \alpha \leq 1}. Then for any {S \subset {\rm Spec}_{\alpha}(A)}, one has

\displaystyle \#\{ (\xi_1 , \xi_2) \in S \times S : \xi_1 - \xi_2 \in {\rm Spec}_{\alpha^2/2}(A) \} \geq \frac{\alpha^2}{2} |S|^2. \ \ \ \spadesuit

Lemma 1 roughly asserts that the spectrum is closed under addition. For example, consider the example {A = \{1 , \ldots , K\}} where {K = o(p)}. Here {{\rm Spec}_{\alpha}(A)} is an interval of length {\asymp \alpha^{-1}} (there are more sophisticated examples, see this paper of Green).

Proof of Lemma 1: We set {f = 1_A}. By assumption we have

\displaystyle \alpha \mathbb{P}(A) |S| \leq \sum_{\xi \in S} |\widehat{f}(\xi)| = \sum_{\xi \in S} c(\xi) \widehat{f}(\xi) = \frac{1}{p} \sum_{\xi \in S} \sum_{a \in A} c(\xi) e_p(\xi a),

for some {c(\xi) \in \mathbb{C}} of modulus 1. By changing the order of summation and Cauchy Schwarz,

\displaystyle \mathbb{P}(A)^2 \alpha^2 |S|^2 \leq \frac{|A|}{p^2} \sum_{a\in A} \sum_{\xi , \xi' \in S} c(\xi) c(\xi') e((\xi - \xi') a) \leq \mathbb{P}(A) \sum_{\xi , \xi' \in S} |\widehat{f}(\xi - \xi')|.

Lemma 1 follows from pigeon holing {\spadesuit}.

Suppose, for the sake of discussion, that for all {\alpha}, {S \subset {\rm Spec}_{\alpha}(A)} does not have additive structure in the strong form form {r_{S-S}(x) \ll 1} for all {x}. Then we conclude

\displaystyle \{ (\xi_1 , \xi_2) \in S \times S : \xi_1 - \xi_2 \in T \} \ll |T|,\ \ \ \ \ (4)

and so by Lemma 1 we have a significant growth from {{\rm Spec}_{\alpha}(A)} to {{\rm Spec}_{\alpha^2/2}(A)}. But then applying this again to {{\rm Spec}_{\alpha^2/2}(A)} we have significant growth to {{\rm Spec}_{\alpha^4/8}(A)} and repeating this procedure will eventually contradict the trivial bound

\displaystyle |{\rm Spec}_{\alpha}(A)| \leq p.

When {H} is a multiplicative subgroup, we can show a weaker version of (4) using that {{\rm Spec}_{\alpha}(H)} is a union of cosets of {H} via (2) and Proposition 1. We turn to the details.

Proof of Theorem 1: Fix {0 < \alpha \leq 1} be chosen small enough so that {S_{\alpha} : = {\rm spec}_{\alpha}(H)} is nonempty. By Lemma 1,

\displaystyle \#\{ (\xi_1 , \xi_2) \in S_{\alpha} \times S_{\alpha} : \xi_1 - \xi_2 \in {\rm Spec}_{\alpha^2/2}(H) \} \geq \frac{\alpha^2}{2} |S_{\alpha}|^2,

that is

\displaystyle \frac{\alpha^4}{4} |S_{\alpha}|^4\leq \left( \sum_{z \in {\rm Spec}_{\alpha^2/2}((A)(H) } r_{S_{\alpha} - S_{\alpha}}(z) \right)^2 \leq | {\rm Spec}_{\alpha^2/2}(H)| E^+(S_{\alpha} , S_{\alpha}).\ \ \ \ \ (5)

Now we use Proposition 1 to provide an upper bound for {E^+(S_{\alpha} , S_{\alpha})}. By (2), {S'_{\alpha} : = S_{\alpha} \setminus \{0\}} is a union of cosets of {H}, say {S'_{\alpha} = \cup_{x \in C} Hx}. Thus by the triangle inequality in {\ell^2} and Proposition 1,

\displaystyle E^+(S'_{\alpha} )^{1/2} \leq \sum_{x \in C} E^+(S'_{\alpha} , Hx)^{1/2} = \sum_{x \in C} E^+(S'_{\alpha}x^{-1} , H)^{1/2} \ll \frac{|S_{\alpha}|}{|H|}|H|^{1/2} |S'_{\alpha}|^{3/4}.

Combining with (5), we find

\displaystyle \alpha^4 |H| | {\rm Spec}_{\alpha}(H)|^{1/2} \ll | {\rm Spec}_{\alpha^2/2}(H)| .

By (3), we find that {|{\rm Spec}_{\alpha}(H)| > |H| + 1} and so

\displaystyle \alpha^4 p^{\delta / 2} \leq \alpha^4 |H|^{1/2} \ll \frac{| {\rm Spec}_{\alpha^2/2}(H)|}{|{\rm Spec}_{\alpha}(H)|} .\ \ \ \ \ (6)

Now we let {1 > \alpha_1 > \alpha_2 > \ldots > \alpha_{J+1} > 0}, where {\alpha_{i+1} = \alpha_i^2 / 2} and {\alpha_1 = p^{-\epsilon}}. Thus {{\rm Spec}_{\alpha_1}(H)} contains more than 0 or immediately conclude Theorem 1. Thus (6) holds for all {\alpha_i} since {{\rm Spec}_{\alpha_i}(H)} increases in size as {i} increases. We have

\displaystyle \prod_{i = 1}^{J} \frac{| {\rm Spec}_{\alpha_{i+1}}(H)|}{|{\rm Spec}_{\alpha_i}(H)|} = \frac{| {\rm Spec}_{\alpha_{J+1}}(H)|}{|{\rm Spec}_{\alpha_1}(H)|} \leq p ,

and so there is a {1 \leq j \leq J} such that

\displaystyle \frac{| {\rm Spec}_{\alpha_{j+1}}(H)|}{|{\rm Spec}_{\alpha_j}(H)|} \leq p^{1/J}.

Combining with (6), we find

\displaystyle p^{- 2^J \epsilon + \delta /2} \frac{1}{2^{J}} \ll \alpha_j^4 p^{\delta/2} \ll p^{1/J}.

Choosing {2^J \epsilon \asymp 1}, we find that

\displaystyle p^{\delta / 2} \ll \epsilon^{-1} p^{1 / \log \epsilon^{-1}},

which is a contradiction for {p} large as long as {\delta \ll \log^{-1} \epsilon^{-1}}. {\spadesuit}

As we saw in the proof, the sum–product phenomenon asserts that {H} has little additive structure which is in tension with the general property that {{\rm Spec}_{\alpha}(A)} is additively structured.


Entropy and Sumsets: An example

The following post is a result of a discussion with Imre Ruzsa. Motivated by the following easy inequality in additive combinatorics

\displaystyle A+2 \cdot A \subset A+A+A , \ \ q \cdot A := \{qa : a \in A\},

I asked if the following was true for a finitely valued random variable {X}:

\displaystyle H(X+2 \cdot X) \leq H(X+X+X), \ H(X) := -\sum_{x \in X} \mathbb{P}(X = x) \log_2 \mathbb{P}(X = x).\ \ \ \ \ (1)

Here all sums are of independent copies of the random variables. The idea is that one might expect {X+X} to be a bit more uniform than {2 \cdot X}.

First Imre provided a counterexample to the question

\displaystyle H(X+ 2\cdot Y) \leq H(X+Y+Y).

I find this example is particularly elegant. Let {X} be uniform on {\{0,1\}} and {Y} be uniform on {\{0 , \ldots , n\}}. Then {X+2 \cdot Y} is uniform on {\{0 , \ldots , 2n+1\}}, while the support of {X + Y + Y} is {\{0 , \ldots , 2n+1\}} but is not uniform (there is concentration in the middle thanks to the distribution of {Y+Y}).

We then seriously questioned the validity (1). After some discussion, Imre eventually said something about higher dimensional concentration that made me think one should check (1) for the “Gaussian.” The reason Gaussian is in quotes is that it is not finitely valued as assumed in (1), so strictly speaking we cannot check it for the Gaussian. To see if there was hope, I looked at the differential entropy of a real valued random variable {G} with density {p} defined via

\displaystyle H(G) := -\int_{-\infty}^{\infty} p(x) \log p(x) dx.

Let us take {G} to be the Gaussian with mean zero (this is irrelevant for entropy) and variance 1. Recall some basic properties of variance:

\displaystyle {\rm Var}(aG) = a^2 {\rm Var}(G) , \ \ {\rm Var}(G+G) = 2 {\rm Var}(G),

where {a \in \mathbb{R}} and {G+G} is understood to be the sum of two independent copies of {G}. Thus

\displaystyle {\rm Var}(G + 2 \cdot G) = 5 , \ \ {\rm Var}(G + G +G ) = 3.

So we indeed see that (1) is not true for the Gaussian. To construct a finitely valued random variable that does not satisfy (1), we can convolve a Bernoulli random variable with itself until (1) is not satisfied (assuming that going from discrete to continuous does not destroy (1) which is not obvious without checking as {2 \cdot X} has a strange support condition, for instance the same argument would prove H(2 \cdot G) \geq H(G+G) which is clearly not true for discrete random variables). Anyways, I wrote some quick python code to check this and found that for {X = B + B + B} where {B} is the random variable of a fair coin flip, we have

\displaystyle H(X+2 \cdot X) \approx 2.984 , \ \ H(X+X+X) \approx 2.623.

Here {X+ 2 \cdot X} and {X+X+X} are supported on {\{0 , \ldots , 9\}} and so their entropies are bounded by the entropy of uniform distribution on 10 elements which is

\displaystyle \log_2 10 \approx 3.322.

Sometimes entropy analogs of sumset inequalities hold and sometimes they do not (see this paper of Ruzsa or this paper of Tao, or a host of work by Madiman and coauthors).

Sum of a set and its dilate

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 2 |A| - 3}
  • (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

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.

Covering sumsets and Plünnecke’s inequality

Recall Plünnecke’s inequality which states the following. We write {mA} for all of the {m}–fold sums of {A}.

Theorem (Plun): Let {A} be a finite subset of an abelian group. Let {K = |A+A| |A|^{-1}} be the doubling constant. Then

\displaystyle |mA | \leq K^{m}|A|. \ \ \ \spadesuit

We describe one natural attempt to prove Theorem (Plun). Suppose that

\displaystyle A+A \subset A+X,

for some small {X}. Then

\displaystyle A+A+A \subset A+X+X.\ \ \ \ \ (1)

and so

\displaystyle |A+A+A| \leq |A| |X|^2.

This motivates the following definition.

Definition (Cov): Let {A} be a finite subset of an abelian group. We let

\displaystyle C(A) = \min \{|X| : A+A \subset A+X , \ X \subset A\}. \ \ \ \spadesuit

Clearly {C(A) \leq |A|}, since we may choose {|X| = |A|}. Note that

\displaystyle C(A) \geq |A+A| |A|^{-1},\ \ \ \ \ (2)

since if {A+A \subset A+X}, then {|A+A| \leq |A| |X|}. One natural question is to what extent can one reverse (2). By the argument in (1),

\displaystyle |mA| \leq C(A)^{m-1} |A|,

and so this would have implications to Plünnecke’s inequality.

The truth is one cannot reverse (2). We give an example due to Ruzsa.

Example: We construct a set {Y} in {\mathbb{Z}^3} via

\displaystyle Y := \left( [n] \cdot e_1 \times [n] \cdot e_2 \times [n] \cdot e_3 \right) \cup [n^2] e_1 \cup [n^2] e_2 \cup [n^2] e_3.


We have the following properties of {Y}:

\displaystyle |Y| \asymp n^3 , \ \ |Y+Y| \asymp n^4 = n |Y| , \ \ C(Y) \asymp n^2 \asymp n |Y+Y| |Y|^{-1}.

Note that {|Y+Y|} comes from the sum of a line of size {n^2} with the box, while {C(Y)} comes from the sum of two perpendicular lines of size {n^2}. The point is that one cannot efficiently cover a two dimensional object with either a one dimensional object or a three dimensional object, even in the presence of additive structure. {\spadesuit}

We do have {C(A) \lesssim |A+A| |A|^{-1}} statistically in the following sense.

Proposition (Stat): Let

\displaystyle S = \{x \in A+A : r_{A+A}(x) \geq |A|^2 |A+A|^{-1}\}.


\displaystyle S \subset A+X, \ \ \ |X| \leq 3|A+A| |A|^{-1} \log |A|. \ \ \spadesuit

This should be compared to this post of Tao, where he talks about an entropy version of Plünnecke’s inequality.

Proof: We choose {X} uniformly at random of size {p |A|}. Let {d = |A|^2 |A+A|^{-1}}. Then for {s \in S},

\displaystyle \mathbb{P}(s \notin A+X) = (1-p)^{r_{A+A}(s)} \leq (1-p)^{d} \leq \exp{(-pd)}.

We choose {p = 3d^{-1} \log |A| =3 |A+A| |A|^{-2} \log |A|}. If {p > 1}, the Proposition follows from taking {X=A} and so we assume the opposite. Let {Z} be the random variable that denotes the number of {s \in S} not covered by {A+X}. By the union bound,

\displaystyle \mathbb{E}[|Z|] \leq |A+A| \exp{(-pd)} \leq |A|^{-1}.

Thus there is a choice of {X} so that {Z = 0} and thus {S \subset A+X} {\spadesuit}

On the other hand, we can bound {C(A)} in terms of the doubling constant if we are allowed to take {X} a subset of the smoother {A+A-A}.

Proposition (Smooth): Let {A} be a finite subset of an abelian group. Then {A+A \subset A+X} where {X \subset A+A-A} and {|X| \ll |A+A-A||A|^{-1} \log |A|}. Thus {A+A} can be covered by {\ll K^3 \log |A|} translates of {A}.

The proof of Proposition (Smooth) is similar to that of Proposition (Stat), so we omit it.

This is related to the following annoying question. We let {m \cdot A} be the dilate of {A} by {m}. We know from Plünnecke’s inequality that

\displaystyle |A+ 2 \cdot A| \leq |A+A+A| \leq K^3 |A| , \ \ K = |A+A| |A|^{-1}.\ \ \ \ \ (3)

This inequality came up in Lemma 5.1 of the almost periodicity paper of Croot and Sisask.

Question (aplus2a): Does there exist a {\delta < 3} such that

\displaystyle |A+2 \cdot A| \leq K^{ \delta} |A|? \ \ \ \spadesuit

This was asked in a paper of Bukh and appears on his website. Note that both of the inequalities in (3) can be basically tight. For the first one, consider and arithmetic progression, and for the second, the example given above.

We now give a construction that shows one cannot take {\delta} too small in Question (aplus2a), even for large {A}, using the tensor power trick.

Example: Consider {A = \{0,1\}}. Then {|A+A| = 3} and {|A+2 \cdot A| = 4}. This example shows that one cannot take {\delta} smaller than

\displaystyle \log (2) / \log (3/2) \approx 1.71.

To make large examples, consider {A = \{0,1\}^d} for some large {d}.

Monochromatic Hilbert cubes and arithmetic progressions

József Balogh, Misha Lavrov, Adam Wagner, and I recently uploaded our paper “Monochromatic Hilbert cubes and arithmetic progressions” to the arXiv.

Van der Waerden’s theorem is a central question in arithmetic Ramsey theory. The goal is to find bounds for {W(k,r)}, which is the least integer such that any {r}–coloring of {1 , \ldots , W(k,r)} contains a {k}–term arithmetic progression. The current records are of the form

\displaystyle c\cdot r^{k-1} \leq W(k,r) \leq 2^{2^{r^{2^{2^{k+9}}}}}.

The upper bound is due to Gowers, while the lower bound is due to Kozik and Shabanov (see also Blankenship, Cummings, and Taranchuk for the prime case).

A Hilbert cube, or affine {k}–cube, is a subset of the integers of the form

\displaystyle \left\{x_0 + \sum_{b \in B} b : B \subseteq A\right\} =: x_0 + \Sigma^* A,

for some {|A|=k} and {x_0 \in \mathbb{Z}}. Hilbert cubes are an important substructure in arithmetic Ramsey theory, coming up in the Gower’s uniformity norm, the density Hales Jewett theorem, and Szemerédi’s original proof of his theorem. We set {h(k,r)} to be the least integer such that any {r}–coloring of {1 , \ldots , W(k,r)} contains an affine {k}–cube. The current records are of the form

\displaystyle r^{ck^2} \leq h(k,r) \leq O(r)^k.

The lower bound is due to Conlon, Fox, and Sudakov, while the upper bound was originally due to Szemerédi and is the so–called Szemerédi cube lemma. Note that the gap in bounds for Hilbert cubes is much less than the gap in Van der Waerden’s problem.

Improving the upper bound would be of interest, and there are a plethora of proofs for it. For instance, one nice geometric proof can be found in this paper of Graham and Solymosi and a standard averaging can be found in these notes of Zeeuw.

We instead consider improving the lower bound. A first try is to randomly {r}–color the integers {1 ,\ldots , n} and show that with high probability there are no monochromatic affine {k}–cubes. An affine {k}–cube of the form {x_0 + \Sigma^* A} is not monochromatic with probability

\displaystyle \frac{2}{2^{\Sigma A}}.

It turns out if every {A} was disassociated, that is having {|\Sigma^* A| = 2^k}, then we could complete this argument and greatly improved upon the Conlon, Fox, Sudakov bound. The problem is with sets of the form {x_0 + \Sigma^* A}, where {\Sigma^* A} is small. The question is how small. It turns out that {|\Sigma^* A| \geq {k +1 \choose 2}}. To make improvements, we must consider the case {|\Sigma^* A| \leq k^{2 + \delta}}. But then, in light of Littlewood–Offord theory, one might expect {A} to look a lot like an arithmetic progression. Thus {\Sigma^* A} should also be like an arithmetic progression. Thus we are lead back to Van der Waerden’s problem. Our main tools for making this precise are this paper of Nguyen and Vu and this paper of Szemerédi and Vu.

Our main theorem is the following.

Theorem 1: Let {k \geq 3} be an integer. Then for every {\epsilon >0}, there is a {c > 0} such that

\displaystyle h(k,4) \ge \min\{W(\lfloor c k^2 \rfloor, 2), 2^{k^{2.5-\epsilon}}\}.

Theorem 1 asserts that either

  • (i) the best lower bound for {W(k,2)} is far from sharp and {h(k,4)} is larger than the Conlon, Fox, Sudakov bound,
  • (ii) the best lower bound for {W(k,2)} is nearly sharp and so the Hilbert cube number is very close to the Van der Waerden number.

Graham conjectured that {W(k,2)} should be closer to the lower bound as opposed to the tower type upper bound. One dream would be to use this to prove a $1000 conjecture of Graham, by showing a bound of the form {h(k,4) \leq 2^{k^{2.5 - \delta}}}. Needless to say, this is likely hard.

Convex sets have many differences

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},


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


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


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