Four days back Jordan Ellenberg posted the following on his blog:

Briefly: it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term arithmetic progression! Such a set has size at most (2.756)^n. (There’s actually a closed form for the constant, I think, but I haven’t written it down yet.)

Here’s the preprint. It’s very short. I’ll post this to the arXiv in a day or two, assuming I (or you) don’t find anything wrong with it, so comment if you have comments!

Then two days later Dion Gijswijt made this comment on Ellenberg’s post:

What a nice result, congratulations!

Last week, I’ve also been writing a proof of an upper bound O(p^{cn}), c<1 for progression-free sets, in Z_p^n based on the same paper of Croot, Lev and Pach, see

http://homepage.tudelft.nl/64a8q/progressions.pdf

So I guess, you beat me to it! Also, your constant for the case p=3 is better than mine (O(2.76^n) vs O(2.84^n)). I think the CLP-paper is a real gem in its simplicity.

This is a true breakthrough, settling an important open problem in combinatorics that survived even after a lot of effort from several mathematicians (see this, this, this and this). Ultimately, just like the finite field Kakeya problem, it succumbed to the polynomial method. I really like the following comment by Ben Green on a Facebook post: “*It’s amazing how the polynomial method seems to be so orthogonal to other methods. It’s a bit like Dvir’s proof of the finite field Kakeya – in a couple of pages, it sweeps aside a large body of partial results using complicated combinatorial and analytic methods to get much weaker statements.”*

**Problem statement**: Find the maximum possible size of a subset of which does not contain any three distinct elements in arithmetic progression.

A set with such a property is known as a *cap set*, a name probably inspired from the fact that the early examples of such sets in three dimension came from elliptic quadrics over finite fields, which look like hats (or caps) in real spaces. The elliptic quadrics are 3-dimensional examples of *affine caps*; sets of points which do not contain any three points collinear with the same line (this condition is stronger than the condition above when as it says that for any three distinct elements we have for all .). The oldest reference that I could find mentioning the term “cap” for such sets is this 1958 paper by Segre: On Galois Geometries. When , affine caps are related to the game SET and you can read the following brilliant paper by B. L. Davis and D. Maclagan which explains this connnection: The card game SET.

Ellenberg and Gijswijt have proved that *a cap set in has size at most a constant times the number of monomials of total degree at most that satisfy for all . *

Understanding their beautiful proof requires only some knowledge of basic linear algebra and polynomials. I’ll try to explain the main arguments here. Ultimately, one also needs to estimate the total number of monomials that satisfy the conditions above, for which I will refer to the preprints of Ellenberg and Gijswijt, and to the comments section of the blog post by Ellenberg. One crucial thing to note about the estimates is that this bound is good only because is strictly less than the mean .

Let be an odd prime power and let denote the set of all polynomials in that satisfy and for all , aka, the set of reduced polynomials of degree at most . The set of all reduced polynomials with no restriction on the total degree is simply denoted by . There is a vector space isomorphism between and the space of all -valued functions on given by evaluating the polynomials. Let denote the dimension of , which is equal to the total number of integral solutions of and . Clearly, via the bijection .

For a -term arithmetic progression free subset of , the sets and are disjoint as otherwise we will have three distinct elements in satisfying .

Let be the subspace of consisting of all polynomials that vanish on the complement of .

Then (since is odd) and thus we try to find upper bounds on .

For any integer let be the intersection of with .

Then since the span is a subspace of , by the dimension formula we have , or equivalently,

Now the crux of the proof is Proposition 1 in Jordan’s preprint, which is essentially equivalent to Lemma 1 of Croot-Lev-Pach’s paper, and says that *every (reduced) polynomial of degree at most which vanishes on has at most non-zeros in *. The proof of this is an interesting dimension argument which I will skip for now (also see this old mathoverflow question by Seva).

Since is a subset of the complement of , the above proposition implies that every element of , when seen as an element of via the evaluation isomorphism, has at most non-zero coordinates. I leave it as an exercise to show that a vector subspace of with the property that every element of has at most non-zero coordinates must have its dimension less than or equal to (hint: row reduction). And thus .

Therefore, from the earlier inequality on , we get .

Finally, observe that when , which gives us the bound (whenever is an integer).

The reason why this is a good bound is that is bounded above by for some whenever (see the preprints).

**Some questions:**

(1) Can we obtain a better bound on affine caps since they are much more restrictive than cap sets?

(2) Do these techniques say anything about sets which do not contain any full line, i.e., the complements of affine blocking sets with respect to lines? As Ferdinand has pointed out in this comment, we have a general upper bound of the form there.

(3) What about sets which do not contain any terms in arithmetic progression, for ?

**Further Reading:**

[1] Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem! by Gil Kalai

[2] Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven. by Gil Kalai

[3] A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound by Terence Tao

[4] Many Zero Divisors in a Group Ring Imply Bounds on Progression–Free Subsets by Fedor Petrov

[5] Large caps in projective Galois spaces, by Jürgen Bierbrauer and Yves Edel

[6] Zero-sum problems in finite abelian groups and affine caps, by Edel et al.

[7] Sumsets and sumsets of subsets, by Jordan Ellenberg.

[8] Bounds for sum free sets in prime power cyclic groups – three ways, by David speyer.

[9] Talk by Jordan Ellenberg at Discrete Math Seminar in IAS, Princeton.

This is really helpful, thanks!

I think you are missing a factor of 3 in your paragraph “Ellenberg and Gijswijt proved that a cap set in has size at most the number of monomials of total degree at most that satisfy for all . ” The bound you give at the end is , not .

You are welcome! And thanks for pointing that out, I’ll correct it.

An alternate proof of a bound which has better constants (2 instead of 3) has been given by Fedor Petrov: https://dl.dropboxusercontent.com/u/15433464/f3_eng.pdf. See his comment: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/#comment-468759.

Pingback: Applications of Alon-Furedi to finite geometry | Anurag's Math Blog

Pingback: Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem! | Combinatorics and more

Pingback: Notes of the seminar ‘On the slice rank of functions’ | Points And Lines