Caps in AG(n,3)

For the past week and a half I have done little but mark exam papers. At some point during this, I looked at Tim Gowers’ blog, and read that a very significant improvement had very recently been made on the bound for the size of a cap in affine space over the field GF(3) of three elements. Tim claimed that “the papers are so short, and the ideas so transparent”, that I was tempted to read them, but decided to put off reading what he said until I had time to do it properly.

Then on Saturday I flew one-third of the way round the world, to the meeting on New directions in combinatorics at the Institute for Mathematical Sciences of the National University of Singapore. The meeting started at 9am yesterday; by 9.40, I had seen the entire proof (apart from a messy calculation I will mention below), and by 9.50 the outline of a slightly different proof, all thanks to a beautiful talk by the first speaker, Ben Green.

A cap in a finite geometry is a set of points with the property that no three are collinear; thus it is simply a higher-dimensional version of an arc, and the name is intended to suggest this. Caps have been studied for some time in finite geometry, and many beautiful examples exist, including Hill’s 56-point example in PG(5,3) which forms half of the elliptic quadric. Not so much attention was paid to asymptotics, though.

Consider caps in AG(n,3), the affine space over GF(3) (the vector space without a distinguished origin). It has the lovely property that a line is just a set of three vectors which add up to 0. (In general a line consists of all points of the form a+tb, where a and b are fixed and t runs through the field; the fact that 1+1+1 = 0+1+2 = 0 shows that this is equivalent to the sum-0 property.

A curious point of terminology. Finite geometers always called these objects caps. But people in additive combinatorics seem to have re-named them “capsets”. I shall be conservative and stick to my heritage.

Clearly a cap cannot be larger than 3ⁿ. The set of all vectors with coordinates 0 and 1 only is a cap of size 2ⁿ. So it is not unreasonable to assume that the largest cap has size about cⁿ for some constant c. But before two weeks ago, nothing much better than Roy Meshulam’s upper bound of c.3ⁿ/n was known. (Roy’s proof uses discrete harmonic analysis, aka characters of finite abelian groups.) But now the bound has been brought down to about 2.756ⁿ, by Ellenberg and Gijswijt (independently), by adapting a brilliant lemma from a slightly different context by Croot, Lev and Pach.

Let F denote the field GF(3). Every function from Fⁿ to F is uniquely representable by a cube-free polynomial in n variables over F. Such a polynomial is a linear combination of monomials, each of which is a product of terms x_i^k for k taking the values 0, 1 or 2. The degree of a random monomial is thus the sum of n random variables each taking the value 0, 1 or 2 with equal probability, and so the expected degree is n, [corrected from earlier version] and the probability that the degree differs from this by a linear amount is exponentially small.

The precise statement of the theorem is that the size of a cap is bounded by 3D, where D is the dimension of the space of cubefree polynomials of degree 2n/3. A long and messy calculation is required to show that D is about 2.756ⁿ, but hopefully you now believe that it is at least exponentially smaller than 3ⁿ.

The proof involves two results, of which Ben gave complete proofs.

The first says that a set A in the affine space which has size larger than 3D contains a subset of size at least |A|−D which is the support of a polynomial of degree at most 4n/3. The proof is just linear algebra.

The second, the Croot–Lev–Pach principle, is also just linear algebra. It says that if p is a cubefree polynomial of degree d, B and C two subsets, and M the |B|×|C| matrix with (b,c) entry p(b+c), then the rank of M is at most twice the degree of the space of polynomials of degree d/2. It really is a great idea, and depends on the fact that row rank is equal to column rank!

The relevance of this to caps is obvious. If we have a large cap, the first result gives us a still large cap which supports a polynomial; the values of this polynomial on b, c, and b+c cannot all be non-zero.

I won’t give more detail. You should have been there!

As a pointer to the future, Ben mentioned at the end of this exposition a result which he only learned on Sunday when he saw it on Facebook. Time for we old dinosaurs to trundle off to bed …