The Ellenberg-Gijswijt bound on cap sets

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 \mathbb{F}_q^n 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 q > 3 as it says that for any three distinct elements a, b, c we have c - b \neq \lambda (b -a) for all \lambda \in \mathbb{F}_q \setminus \{0, -1\}.). The oldest reference that I could find mentioning the term “cap” for such sets is this 1958 paper by Segre: On Galois Geometries. When q = 3, 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 \mathbb{F}_q^n has size at most a constant times the number of monomials x_1^{e_1}x_2^{e_2}\cdots x_n^{e_n} of total degree at most (q-1)n/3 that satisfy 0 \leq e_i \leq q - 1 for all i.

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 (q-1)n/3 is strictly less than the mean (q-1)n/2.

Let q be an odd prime power and let \mathcal{P}_d(n, q) denote the set of all polynomials f in \mathbb{F}_q[x_1, \dots, x_n] that satisfy \deg f \leq d and \deg_{x_i} f \leq q - 1 for all i, aka, the set of reduced polynomials of degree at most d. The set of all reduced polynomials with no restriction on the total degree is simply denoted by \mathcal{P}(n, q). There is a vector space isomorphism between \mathcal{P}(n, q) and the space of all \mathbb{F}_q-valued functions on \mathbb{F}_q^n given by evaluating the polynomials. Let k_d denote the dimension of \mathcal{P}_d(n, q), which is equal to the total number of integral solutions of e_1 + \dots + e_n \leq d and 0 \leq e_i \leq q - 1. Clearly, k_{n(q - 1) - d} = q^n - k_d via the bijection (e_1, \dots, e_n) \mapsto (q - 1 - e_1, \dots, q - 1 - e_n).

For a 3-term arithmetic progression free subset A of \mathbb{F}_q^n, the sets A + A = \{a + a' : a, a' \in A, a \neq a'\} and 2A = \{a + a : a \in A\} are disjoint as otherwise we will have three distinct elements a, b, c in A satisfying a + c = 2b.
Let U be the subspace of \mathcal{P}(n, q) consisting of all polynomials that vanish on the complement of 2A.
Then \dim U = |2A| = |A| (since q is odd) and thus we try to find upper bounds on \dim U.
For any integer d \in \{0, 1, \dots, n(q - 1)\} let U_d be the intersection of \mathcal{P}_d(n, q) with U.
Then since the span \langle U, \mathcal{P}_d(n, q) \rangle is a subspace of  \mathcal{P}(n, q), by the dimension formula we have \dim U \leq \dim \mathcal{P}(n, q) - \dim \mathcal{P}_d(n, q) + \dim U_d, or equivalently, |A| \leq q^n - k_d + \dim U_d = k_{n(q - 1) - d} + \dim U_d.

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 d which vanishes on A + A has at most 2 k_{d/2} non-zeros in 2A. The proof of this is an interesting dimension argument which I will skip for now (also see this old mathoverflow question by Seva).

Since A + A is a subset of the complement of 2A, the above proposition implies that every element of U_d, when seen as an element of \mathbb{F}_q^{\mathbb{F}_q^n} via the evaluation isomorphism, has at most 2 k_{d/2} non-zero coordinates. I leave it as an exercise to show that a vector subspace V of F^n with the property that every element of V has at most k non-zero coordinates must have its dimension less than or equal to k (hint: row reduction). And thus \dim U_d \leq 2 k_{d/2}.

Therefore, from the earlier inequality on |A|, we get |A| \leq k_{n(q - 1) - d} + 2k_{d/2}.
Finally, observe that n(q - 1) - d = d/2 when d = 2(q - 1)n/3, which gives us the bound |A| \leq 3 k_{(q - 1)n/3} (whenever (q - 1)n/3 is an integer).
The reason why this is a good bound is that k_{d} is bounded above by q^{\lambda n} for some \lambda < 1 whenever d < (q - 1)n/2 (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 q^n - 2q^{n - 1} + 1 there.
(3) What about sets which do not contain any k terms in arithmetic progression, for k > 3?

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.

Advertisements

About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics, Finite Geometry, Polynomial Method and tagged , , , , , . Bookmark the permalink.

6 Responses to The Ellenberg-Gijswijt bound on cap sets

  1. David Speyer says:

    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 \mathbb{F}_q^n has size at most the number of monomials x_1^{e_1}x_2^{e_2}\cdots x_n^{e_n} of total degree at most (q-1)n/3 that satisfy 0 \leq e_i \leq q - 1 for all i. ” The bound you give at the end is 3 k_{(q - 1)n/3}(n, q), not k_{(q - 1)n/3}(n, q).

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

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

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

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s