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

where

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

We set

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

Then

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

By the asymmetric version of (1), we have

and we also have

Combining these two, we find

Using (3), we find

This quantity is minimized when

and so

The result follows from

and simplification.

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

## 2 thoughts on “Convex sumsets and sum-product estimates”