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

	Temperature in Natur… on How Does ChatGPT read?
	Eva Tutor on Truthfulness of AI models like…
	David Burns on Can Chat-GPT Do Math?
	Azzouzi Marouan on Can Chat-GPT Do Math?
	khiannaian on Can Chat-GPT Do Math?

George Shakan

Data Science and Math Blog

Konyagin-Shkredov Clustering

Related

1 thought on “Konyagin-Shkredov Clustering”

Leave a ReplyCancel reply