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


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



1 thought on “Konyagin-Shkredov Clustering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s