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 if for some . Let be finite. We define the sumset and product set via
We have the beautiful sum–product conjecture of Erdős and Szemerédi.
Conjecture (ESconj): Let . Then for any finite one has
We say a finite is convex if
The following conjecture is due to Erdős.
Conjecture (Convex) Suppose is convex. Then
Study of the quantity has played a crucial role in recent progress on both conjectures, which we define now. For finite, we define
See my recent paper on Conjecture (ESconj) for an introduction to . We mention here that and intuitively the larger is the more additive structure has. Indeed 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
Thus if , we have that . We conjecture that this can be improved.
Conjecture (dplus): Let be finite. Then
This would imply Conjecture (Convex) and Conjecture (ESconj) for . 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 be finite. Then
His idea is to analyze spectral and combinatorial properties of an associated matrix: the spectral properties depend on , while the combinatorial properties depend on . One of the simplest versions of this idea is that the number of –walks in a graph is the sum of the the powers of the eigenvalues of the graph, which plays a crucial role in the theory of expander graphs.
For a function , we define the following matrices
Theorem 1 follows from the following two propositions.
Proposition 1: Let
be a set of popular sums of and . Let be the eigenvalues of with associated orthonormal eigenvectors . Then
The second and third inequality hold for general . The right hand side arises from combinatorial properties of , 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 , which is slightly different than what is considered in the definition of . This is handled by the following.
Proposition 2: Let be finite and
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 by various second moment estimates and then use the fact that if and only if . By a dyadic decomposition, there is a set such that
On the other hand,
By the asymmetric version of (1), we have
and we also have
Combining these two, we find
Using (3), we find
Combining (2) and (4) yields
This quantity is minimized when
The result follows from
Proof of Proposition 1: Note that is a symmetric, positive–semidefinite matrix. To see the second point, note
Thus for any . This proves the third inequality
Now, we show the first inequality. We have and by a popularity argument
and so , since
We now prove the fourth inequality. Since are an orthonormal basis of eigenvectors for ,
where in the final equality, we used that
from the spectral theorem of self adjoint matrices. Now we have
Using the change of variables and , we have this is equal to
By Cauchy–Schwarz and simplification, we get this is
The inequality follows from
We now prove the second inequality. It is enough to show
We start with the first inequality. Since is a unit vector and ,
In the last inequality, we used that we may choose entry–wise by the Perron–Frobenius theorem. We move onto the second inequality. Using the change of variables we find
By Cauchy–Schwarz and a modest computation, we find this is
We end by mentioning that
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.