Ellenberg’s announcement of a solution to the cap-set problem

Jordan Ellenberg has just announced a resolution of the “cap problem” using techniques of Croot, Lev and Pach, in a self-contained three-page paper. This is a quite unexpected development for a long-standing open problem in the core of additive combinatorics.

Perhaps the right starting point for this story is 1936, when Erdos and Turan conjectured that, for every , if is a subset of without -terms arithmetic progressions, then , or, equivalently, that if is a subset of the integers of positive density, then it must have arbitrarily long arithmetic progressions. Their goal in stating this conjecture was that resolving it would be a stepping stone to proving that the prime numbers have arbitrarily long arithmetic progressions. This vision came true several decades later. Szemeredi proved the conjecture in 1975, and Green and Tao proved that the primes contain arbitrarily long arithmetic progressions in 2004, with Szemeredi’s theorem being a key ingredient in their proof.

Rewinding a bit, the first progress on the Erdos-Turan conjecture came from Roth, who proved the case In 1955. Roth’s proof establishes that if does not have length-3 arithmetic progressions, then is at most, roughly . Erdos also conjectured that the bound should be , and if this were true it would imply that the primes have infinitely many length-3 arithmetic progressions simply because of their density.

Roth’s proof uses Fourier analysis, and Meshulam, in 1995, noted that the proof becomes much cleaner, and it leads to better bounds, if one looks at the analog problem in , where is a finite field (of characteristic different from 2). In this case, the question is how big can be if it does not have three points on a line. An adaptation of Roth’s techniques gives an upper bound of the order of , which, for constant , is of the order of if is the size of the universe of which is a subset.

Bourgain introduced a technique to work on “as if” it where a vector space over a finite field, and proved upper bounds of the order of and then to the size of a subset of without length-3 arithmetic progressions. The latest result in this line is by Sanders, who proved a bound of , very close to Erdos’s stronger conjecture.

How far can these results be pushed? A construction of Behrend’s shows that there is a set with no length-3 arithmetic progression and size roughly . The construction is simple (it is a discretization of a sphere in dimensions) and it has some unexpected other applications. This means that the right bound in Roth’s theorem is of the form and that the “only” question is what is the term.

In the finite vector space case, there is no analog of Behrend’s construction, and so the size of say, the largest subset of without three points on a line, was completely open, with an upper bound of the order of and lower bounds of the order of for some constant . The cap problem was the question of whether the right bound is of the form or not.

Two weeks ago, Croot, Lev and Pach proved that if is a subset of without length-3 arithmetic progressions, then is at most of the order of . This was a strong indication that the right bound in the cap problem should be sub-exponential.

This was done a couple of days ago by Ellenberg, who proved an upper bound of the form holds in . The proof is not specific to and generalizes to all finite fields.

Both proofs use the polynomial method. Roughly speaking, the method is to associate a polynomial to a set of interest (for example, by finding a non-zero low-degree polynomial that is zero for all points in the set), and then to proceed with the use of simple properties of polynomials (such as the fact that the space of polynomials of a certain degree has a bounded dimension, or that the set of zeroes of a univariate non-zero polynomial is at most the degree) applied either to the polynomial that we constructed or to the terms of its factorization.

Let be the vector space of -variate polynomials over of total degree that are cube-free (that is, such that all variables occur in monomials with degree 0, 1, or 2), and let be its dimension.

If is a set such that there are no distinct such that (a different property from being on a line, but the draft claims that the same argument works for the property of not having three points on a line as well), then Ellenberg shows that

then the bound follows from computing that and for .

The finite field Kakeya problem is another example of a problem that had resisted attacks from powerful Fourier-analytic proofs, and was solved by Zeev Dvir with a relatively simple application of the polynomial method. One may hope that the method has not yet exhausted its applicability.

Gil Kalai has posted about further consequence of the results of Croot, Lev, Pach and Ellenberg.