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.

IMS, NUS, Singapore

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 3n. The set of all vectors with coordinates 0 and 1 only is a cap of size 2n. So it is not unreasonable to assume that the largest cap has size about cn for some constant c. But before two weeks ago, nothing much better than Roy Meshulam’s upper bound of c.3n/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.756n, 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 Fn 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 xik 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.756n, but hopefully you now believe that it is at least exponentially smaller than 3n.

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 …

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in Uncategorized and tagged , , , , , , , , . Bookmark the permalink.

7 Responses to Caps in AG(n,3)

  1. I guess one can call a subset of Z_m^n which does not contain a three term arithmetic progression, capset, while retaining the term caps for sets of points which do not contain any three collinear points. Also, you should check out the proof by Fedor Petrov which uses different ideas and improves the bound to 2D: His ideas can also be used to prove the Croot-Lev-Pach lemma in a different way, see and

    • Dear Anurag, Thanks for this. I am not too worried what things are called. My guess is that they chose the name “capset” by analogy with “sumset”, although there really isn’t an analogy at all. But I expect the name “capset” will prevail, since finite geometers hadn’t done much with this problem for a long time, and the momentum is now with the additive combinatorialists.
      I meant to say, and forgot, that, in tribute to Ben Green, he is giving a four and a half hour course on finite field methods in additive combinatorics, and he had to completely re-do his first lecture in the last couple of weeks before the conference.

      • Dear Peter, I am not too worried about the terminology either, but I have never seen the term capsets being used for general affine caps over \mathbb{F}_q. It’s only when q = 3, and both the notions coincide that we see capsets being a more prevalent terminology. For q > 3, it makes sense to call these sets in \mathbb{F}_q^n which do not contain a three term arithmetic progression capsets, and the more restrictive sets which do not contain three elements lying on a common line as affine caps. Also, I guess in principle it is still possible that much better upper bounds on affine caps can be obtained for q > 3 when compared to the bounds on capsets.

  2. Anon says:

    Many thanks for this interesting post. It seems to me that the expected degree of the random monomial is n. May I ask what was the result you say that Ben Green mentioned?

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

  4. Pingback: Polynomial Prestidigitation | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.