Tag Archives: sum product

Sum of a set and its dilate

June 24, 2018Additive Combinatoricssum of dilates, sum product, Sumset inequalitiesGeorge Shakan

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

June 20, 2018Additive Combinatoricsfinite fields, sum product, Sumset inequalitiesGeorge Shakan

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

May 16, 2018Additive Combinatoricsconvex sets, Erdos Szemeredi conjecture, sum product, Sumset inequalitiesGeorge Shakan

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

Convex sumsets and sum-product estimates

April 20, 2018Additive Combinatoricsconvex sets, Erdos, sum product, sumsetsGeorge Shakan

Thanks to Junxian Li for carefully reading and providing useful suggestions.

Here we advertise a conjecture that would have consequences to two major problems in additive combinatorics and provide a proof of the state of the art progress towards them. In this 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 beautiful sum–product conjecture of Erdős and Szemerédi.

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$

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 (ESconj) for an 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. Indeed ${d^+(A)}$ is a higher order analog of the more common additive energy of a set. An application of Cauchy–Schwarz implies, as explain in equation (2) of this paper, reveals

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

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 (ESconj) 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. We remark that the rest of the post is technical in nature. Please see this survey of de Zeeuw and the introduction of this paper of mine for background. Also, one can see this paper of Murphy, Rudnev, Shkredov, and Shteinikov for another perspective (thanks to Sophie Stevens for pointing this reference out to me).

Theorem 1: (Shkredov) Let ${A \subset \mathbb{R}}$ be finite. Then

$\displaystyle |A+A| \gtrsim |A|^{58/37} d^+(A)^{-21/37} . \ \ \spadesuit$

His idea is to analyze spectral and combinatorial properties of an associated matrix: the spectral properties depend on ${|A+A|}$ , while the combinatorial properties depend on ${d^+(A)}$ . One of the simplest versions of this idea is that the number of ${k}$ –walks in a graph is the sum of the the ${k^{\rm th}}$ powers of the eigenvalues of the graph, which plays a crucial role in the theory of expander graphs.

For a function ${g : \mathbb{R} \rightarrow \mathbb{C}}$ , we define the following ${|A| \times |A|}$ matrices

$\displaystyle T_A^g(x,y) : = 1_A(x)1_A(y) g(x-y), \ \ S_A^g(x,y) : = 1_A(x)1_A(y) g(x+y).$

We set

$\displaystyle E^+(A , B) := \sum_x r_{A-B}(x)^2 , \ \ \ E^+(A) : = E^+(A,A),$

$\displaystyle E_3^+(A, B , C) := \sum_x r_{A-A}(x) r_{B-B}(x) r_{C-C}(x) , \ \ E_3^+(A) : = E_3^+(A, A , A) .$

Theorem 1 follows from the following two propositions.

Proposition 1: Let

$\displaystyle S = \{x \in A+A : r_{A+A}(x) \geq \frac{ |A|^2 }{2|A+A|}\},$

be a set of popular sums of ${A}$ and ${g = 1_S}$ . Let ${\mu_1 , \ldots , \mu_{|A|}}$ be the eigenvalues of ${S_A^g}$ with associated orthonormal eigenvectors ${f_j : A \rightarrow \mathbb{R}}$ . Then

$\displaystyle \frac{|A|^5}{2^5 |S|} \leq \frac{\mu_1^5}{||g||_2^2 ||g||_{\infty}} \leq \mu_1^2 \langle T_A^{r_{A-A}} f_1 , f_1 \rangle \leq \sum_{j=1}^{|A|} \mu_j^2 \langle T_A^{r_{A-A}} f_j , f_j \rangle \leq d^+(A)^{1/2} |A|^{3/2}E_3^+(A,A,S)^{1/2} . \ \ \ \spadesuit$

The second and third inequality hold for general ${g}$ . The right hand side arises from combinatorial properties of ${T_A^{r_{A-A}}}$ , while the left hand side comes from spectral properties. Before proving Proposition 1, we note that in order to apply Proposition 1, we need a bound for ${E_3^+(A,A,S)}$ , which is slightly different than what is considered in the definition of ${d^+(A)}$ . This is handled by the following.

Proposition 2: Let ${A \subset \mathbb{R}}$ be finite and

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

Then

$\displaystyle E_3^+(A,A,S) \lesssim d^+(A)^{11/10} |A|^{6/5} |A+A|^{17/10}. \ \ \ \spadesuit$

Theorem 1 follows immediately from combining Proposition 1 and Proposition 2. We start with the proof of Proposition 2.

Proof of Proposition 2: The idea is to bound ${E_3^+(A,A,S)}$ by various second moment estimates and then use the fact that ${a - a' = b - b'}$ if and only if ${a + b' = b + a'}$ . By a dyadic decomposition, there is a set ${Q \subset A-A}$ such that

$\displaystyle E_3^+(A,A,S) \gtrsim \sum_{x \in Q} r_{A-A}(x)^2 r_{S-S}(x) , \ \ Q = \{x : q \leq r_{A-A}(x) \leq 2q \}.$

We have

$\displaystyle E_3^+(A,A,S) \lesssim q E(A,S).\ \ \ \ \ (2)$

On the other hand,

$\displaystyle E_3^+(A,A,S) \lesssim q^2 \sum_x 1_Q(x) \sum_y 1_S(y) 1_S(x+ y)$

$\displaystyle \lesssim \frac{|A+A|}{|A|^2} q^2 \sum_y r_{A+A}(y)\sum_x 1_Q(x) 1_S(x+y)$

$\displaystyle = \frac{|A+A|}{|A|^2} q^2 \sum_y r_{A+A}(y)r_{S-Q}(y) \leq \frac{|A+A|}{|A|^2} q^2 E^+(A,S)^{1/2} E^+(A,Q)^{1/2}.\ \ \ \ \ (3)$

By the asymmetric version of (1), we have

$\displaystyle E^+(A,Q) \leq d^+(A)^{1/2} |A| |Q|^{3/2},$

and we also have

$\displaystyle |Q| \leq \#\{x : r_{A-A} (x) \geq q\} \leq E_3^+(A) q^{-3} \leq d^+(A) |A|^3 q^{-3}.$

Combining these two, we find

$\displaystyle E^+(A,Q) \leq \frac{d^+(A)^2 |A|^{11/2}}{q^{9/2}}.$

Using (3), we find

$\displaystyle E_3^+(A,A,S) \lesssim E^+(A,S)^{1/2} |A+A| d^+(A) |A|^{3/4} q^{-1/4} \ \ \ \ \ (4)$

Combining (2) and (4) yields

$\displaystyle E_3^+(A,A,S) \lesssim E^+(A,S)^{1/2} \min \{ q E^+(A,S)^{1/2} , |A+A| d^+(A) |A|^{3/4} q^{-1/4}. \}.$

This quantity is minimized when

$\displaystyle q^{5/4} = \frac{|A+A| d^+(A) |A|^{3/4}}{E^+(A,S)^{1/2}},$

and so

$\displaystyle E_3^+(A,A,S) \lesssim E^+(A,S)^{1/10} \left( |A+A| d^+(A) |A|^{3/4} \right)^{4/5}$

The result follows from

$\displaystyle E^+(A,S) \leq d^+(A)^{1/2} |A| |S|^{3/2}, \ \ |S| \leq |A+A|,$

and simplification.

Proof of Proposition 1: Note that ${T_A^{r_{A-A}}}$ is a symmetric, positive–semidefinite matrix. To see the second point, note

$\displaystyle T_A^{r_{A-A}}(x,y) = \langle 1_{A - x} , 1_{A - y} \rangle.$

Thus ${\langle T_A^{r_{A-A}} h , h \rangle \geq 0}$ for any ${h : A \rightarrow \mathbb{C}}$ . This proves the third inequality

Now, we show the first inequality. We have ${||1_S||_2^2 = |S|}$ and by a popularity argument

$\displaystyle \langle S_A^{1_S} 1 , 1 \rangle = \sum_{x \in S} r_{A+A}(x) \geq |A|^2 / 2,$

and so ${\mu_1 \geq |A| / 2}$ , since

$\displaystyle \mu_1 \geq \sup_{||f||_2 = 1} \frac{\langle T_A^{r_{A-A}} f , f \rangle}{||f||_2}.$

We now prove the fourth inequality. Since ${f_1 , \ldots , f_{|A|}}$ are an orthonormal basis of eigenvectors for ${S_A^{1_S}}$ ,

$\displaystyle \sum_{j=1}^{|A|} \mu_j^2 \langle T_A^{r_{A-A}} f_j , f_j \rangle = \sum_{x,y , j } T_A^{r_{A-A}}(x,y) \mu_j f_j(x) \mu_j f_j(y) = \sum_{x,y , j , i} T_A^{r_{A-A}}(x,y) \mu_i f_i(x) \mu_j f_j(y) \sum_z f_j(z) f_i(z)$

$\displaystyle = \sum_{x,y , z } T_A^{r_{A-A}}(x,y) \sum_i \mu_i f_i(x) f_i(z) \sum_j \mu_j f_j(y) f_j(z) = \sum_{x, y , z} T_A^{r_{A-A}}(x,y) S_A^{1_S} (x,z) S_A^{1_S} (y , z),$

where in the final equality, we used that

$\displaystyle S_A^{1_S} = \sum_j \mu_j f_j f_j^T,$

from the spectral theorem of self adjoint matrices. Now we have

$\displaystyle \sum_{x, y , z} T_A^{r_{A-A}}(x,y) S_A^{1_S} (x,z) S_A^{1_S} (y , z) = \sum_{x, y , z \in A} T_A^{r_{A-A}}(x,y) 1_S(x+z) 1_S(y+z).$

Using the change of variables ${\alpha = x+z}$ and ${\beta = y+z}$ , we have this is equal to

$\displaystyle \sum_{z, \alpha , \beta} r_{A-A}(\alpha - \beta ) 1_S(\alpha) 1_S (\beta) \sum_z 1_A (z) 1_A(\alpha - z) 1_A( \beta - z).$

By Cauchy–Schwarz and simplification, we get this is

$\displaystyle \leq \left( \left( \sum_{\alpha , \beta} r_{A-A} (\alpha - \beta)^2 1_S(\alpha) 1_S(\beta) \right) \sum_{\alpha , \beta} |\sum_z 1_A(z) 1_A(\alpha - z) 1_A( \beta - z) |^2 \right)^{1/2}$

$\displaystyle = E_3^+(A)^{1/2} E_3^+(A, A , S)^{1/2}.$

The inequality follows from

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

We now prove the second inequality. It is enough to show

$\displaystyle \mu_1 \leq ||g||_{\infty}\left( \sum_z f_1(z) \right)^2, \ \ \ \left( \sum_z \mu_1 f_1(z) \right)^2 \leq ||g||_2^2 \langle T_A^{r_{A-A}} f_1 , f_1 \rangle .$

We start with the first inequality. Since ${f_1}$ is a unit vector and ${S_A^g f_1 = \mu_1 f_1}$ ,

$\displaystyle \mu_1 = \sum_x f_1(x) \mu_1 f_1(x) = \sum_{x,y} f_1(x) g(x +y) f_1(y) \leq ||g||_{\infty} \left( \sum_{x} f_1(x) \right)^2.$

In the last inequality, we used that we may choose ${f_1 \geq 0}$ entry–wise by the Perron–Frobenius theorem. We move onto the second inequality. Using the change of variables ${w = x+y}$ we find

$\displaystyle \sum_{x \in A} \mu_1 f_1(x) = \sum_{x,y} g(x+y) f_1(y) 1_A(x) = \sum_{w , x} g(w) f_1(w-x) 1_A(x) .$

By Cauchy–Schwarz and a modest computation, we find this is

$\displaystyle \leq ||g||_2 \left( \sum_w \left( \sum_x f_1(w-x) 1_A(x) \right)^2 \right)^{1/2} = ||g||_2 \langle T_A^{r_{A-A}} f_1 , f_1 \rangle^{1/2}. \ \ \spadesuit$

We end by mentioning that

$\displaystyle |A-A| \gtrsim |A|^{8/5} d^+(A)^{-3/5},$

can be inferred from this paper of Schoen and Shkredov, which is stronger than the plus version discussed in this blog post (see this post). Any improvement to either bound would be of interest.

On higher energy decompositions and the sum-product phenomenon

March 14, 2018Additive Combinatoricsenergy decomposition, Erdos Szemeredi conjecture, sum productGeorge Shakan

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.

	George Shakan on Can Chat-GPT Do Math?
	J.C Vega on Can Chat-GPT Do Math?
	Carnival of Mathemat… on Carnival Of Mathematics
	Playful Math Educati… on Carnival Of Mathematics
	Carnival of Mathemat… on Carnival Of Mathematics