Konyagin-Shkredov Clustering

The goal of this note is to outline Solymosi’s sum–product argument and the first step in the recent Konyagin–Shkredov improvement.

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

Recall the famous Erdős–Szemerédi sum–product conjecture

Conjecture (ESconj): Fix ${\delta < 1}$. Then there exists a ${c_{\delta} >0}$ such that for any finite ${A \subset \mathbb{Z}}$, one has

$\displaystyle |A+A| + |A A| \geq c_{\delta} |A|^{1 + \delta}.$ ♠

We begin with Solymosi’s argument, but first we need to recall a couple definitions. We 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) }$. Cauchy–Schwarz implies the following relations

$\displaystyle|A|^4 \leq |A+A| E^{+}(A) , \ \ |A|^4 \leq |AA| E^{\times}(A).$

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

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

$\displaystyle E^{\times}(A) \lesssim |A+A|^2.$ ♠

Observe that Theorem (Sol) easily implies any ${\delta < 1/3}$ is admissible in Conjecture (ESconj).

Proof: Wlog, we may assume ${A \subset \mathbb{R}_{>0}}$. Consider ${A\times A \subset \mathbb{R}^2}$. For

$\displaystyle \lambda \in A/ A : = \{a/b : a , b \in A\},$

we let ${\ell_{\lambda}}$ be the ray

$\displaystyle \{(x,y) : y = \lambda x , \ x > 0 \}.$

So ${r_{A/A}(x) = |\ell_{\lambda} \cap (A \times A)|}$. Let ${t}$ be a parameter to be chosen later and

$\displaystyle A_t = \{ \lambda : t \leq r_{A/A}(\lambda) < 2t\} = \{\lambda_1 < \cdots < \lambda_r\}.$

Thus ${A_t}$ is the set of rays emanating from the origin that contain ${\approx t}$ points of ${A \times A}$. Let

$\displaystyle \ell_i := \ell_{\lambda_i}.$

Here are the two key observations.

• The sets ${\{(a, b) + (c,d) : (a,b) \in \ell_{i} , \ (c,d) \in \ell_{{i+1}}\}}$ are disjoint for ${1 \leq i \leq \ell - 1}$.
• Any element ${(x,y)}$ in the open cone generated by ${\ell_{i}}$ and ${\ell_{i+1}}$,

$\displaystyle \{r \ell_i + s \ell_{i+1} : r, s >0\},$

can be written uniquely as ${(a,b) + (c,d)}$ where ${(a,b) \in \ell_i}$ and ${(c,d) \in \ell_{i+1}}$.

Thus

$\displaystyle |A+A|^2 \geq \sum_{i=1}^{r-1} r_{A/A}(\lambda_i)r_{A/A}(\lambda_{i+1}) \geq t^2 (|A_t| - 1).$

To choose ${t}$, note that

$\displaystyle 4 |A_t| t^2 \geq \sum_{\lambda \in A_t} r_{A/A}(\lambda)^2,$

and so by a dyadic decomposition, we may choose a ${t}$ such that

$\displaystyle |A_t|t^2 \gtrsim E^{\times}(A).$

This yields the desired result. $\Box$

Remark: One can modify the above argument to show

$\displaystyle |A+AA| \geq |A| (|A| - 1),$

as was observed by Antal Balog. This was recently improved to

$\displaystyle |A+AA| \gtrsim |A|^{3/2 + c}$

for some fixed ${c >0}$. One of their main tools was the Konyagin–Shkredov clustering below. ♠

Konyagin and Shkredov recently improved upon Solymosi’s estimate for Conjecture (ESconj). Note that in the proof of Theorem (Sol) we were only able to count sums from adjacent lines, ${\ell_i}$ and ${\ell_{i+1}}$, above. If we could somehow count sums from all pairs, we would obtain the estimate

$\displaystyle |A+A|^2 \gtrsim |A|^4,$

which is of course too strong to hope for in general. When can we not do this? Well, this argument actually works, unless there is a “collision” of the form

$\displaystyle (a_{i_1} , \lambda_{i_1} a_{i_1}) + (a_{i_2} , \lambda_{i_2} a_{i_2} ) = (a_{i_3} , \lambda_{i_3} a_{i_3}) + (a_{i_4} , \lambda_{i_4} a_{i_4}), \ \ \ i_1 \neq i_2 , \ i_3 \neq i_4 ,\ \ \ \ \ (1)$

where each tuple lies in ${A \times A}$. It is easy to check, after relabeling, that we may assume ${\lambda_4 \neq \lambda_1 , \lambda_2 , \lambda_3}$. For ease of exposition, we set

$\displaystyle A_{\lambda} := A \cap \lambda^{-1} A.$

The two equations in (1) together imply

$\displaystyle (\lambda_1 - \lambda_4)a_1 + (\lambda_2 - \lambda_4) a_2 = (\lambda_3 - \lambda_4) a_3 , \ \ \ a_i \in A_{\lambda_i} .$

So we are motivated to define

$\displaystyle \sigma(X,Y,Z) := \max_{\sigma_1 , \sigma_2 , \sigma_3 \neq 0} \{ (x,y,z) \in X \times Y \times Z : \sigma_1 x + \sigma_2 y + \sigma_3 z = 0\}.$

After accounting for collisions, we find that

$\displaystyle |A+A|^2 \gtrsim (t |A_t|)^2- |A_t|^4 \max_{\lambda_1 , \lambda_2 , \lambda_3 \in A_t} \sigma(A_{\lambda_1} , A_{\lambda_2} ,A_{\lambda_3} ).$

We cannot use this argument as is, since we have no way to bound the number of collisions for that many ${\lambda_1 , \lambda_2 , \lambda_3 , \lambda_4}$. The idea is to partition ${\ell_1 , \ldots , \ell_r}$ into ${\approx \frac{|A_t|}{M}}$ disjoint sets of ${M}$ consecutive lines. For ${\ell_{i} , \ldots , \ell_{i + M - 1}}$, we may apply the above argument to get that the number of elements of ${(A+A) \times (A+A)}$ in the open cone generated by ${\ell_i}$ and ${\ell_{i+M-1}}$ is

$\displaystyle \gtrsim M^2 t^2 - M^4\max_{\lambda_1 , \lambda_2 , \lambda_3 \in A_t} \sigma(A_{\lambda_1} , A_{\lambda_2} ,A_{\lambda_3}).$

Summing over ${\lfloor \frac{|A_t|}{M} \rfloor}$ disjoint sets of ${M}$ consecutive lines we ultimately find

$\displaystyle |A+A|^2 \gtrsim \frac{|A_t|}{M} \left( M^2 t^2 - M^4\max_{\lambda_1 , \lambda_2 , \lambda_3 \in A_t} \sigma(A_{\lambda_1} , A_{\lambda_2} ,A_{\lambda_3})\right) .$

So we take

$\displaystyle M = \lfloor \frac{t}{10 \sigma^{1/2}} \rfloor,$

where $\sigma$ is any quantity satisfying

$\displaystyle \max_{\lambda_1 , \lambda_2 , \lambda_3 \in A_t} \sigma(A_{\lambda_1} , A_{\lambda_2} ,A_{\lambda_3}) \leq \sigma .$

Thus we have improved Solymosi’s argument from ${t^2 |A_t|}$ to ${Mt^2 |A_t|}$, as long as

$\displaystyle 2 \leq M \leq |A_t| / 2.$

Thus we hope to be able to take ${M}$ to be a power of ${|A|}$. The bad cases are when $M$ is smaller than some fixed power of $|A|$ and $M \geq |A_t| / 2$. It turns out to be relatively easy to handle the case ${M \geq |A_t| / 2}$, so the key case to analyze is when $M$ is smaller than some fixed power of $|A|$ and

$\displaystyle \max_{\lambda_1 , \lambda_2 , \lambda_3 \in A_t} \sigma(A_{\lambda_1} , A_{\lambda_2} ,A_{\lambda_3}) \geq \frac{t^2}{2 M^2}.$

In light of the trivial bound

$\displaystyle \max_{\lambda_1 , \lambda_2 , \lambda_3 \in A_t} \sigma(A_{\lambda_1} , A_{\lambda_2} ,A_{\lambda_3}) \leq t^2,$

this should impose additive structure on ${A_{\lambda_1}, A_{\lambda_2}}$, and ${A_{\lambda_3}}$. Konyagin and Shkredov were able to successfully analyze this case as well in order to, at the time, obtain further progress towards Conjecture (ESconj).