← mino.mobi

capset

cap-set problem in 𝔽₃ⁿ Β· Ellenberg–Gijswijt 2016

↑ geometry pack Β· erdΕ‘s Β· guthkatz Β· hadwiger Β· runner Β· kakeya Β· szemerΓ©di–trotter Β· heilbronn Β· borsuk Β· viazovska

dimension Β· n
Cells live in 𝔽₃ⁿ β€” coordinate triples (or pairs) with entries in {0, 1, 2}. Three cells form a line when they sum to (0, 0, …) modulo 3. A cap set contains no such line. Try to build a maximum cap set; any line in your set is highlighted in red and marks a forbidden three-term arithmetic progression.

The cap-set problem

Take 𝔽₃ⁿ, the n-dimensional vector space over the field with three elements. A subset S βŠ† 𝔽₃ⁿ is a cap set if it contains no three-term arithmetic progression β€” equivalently, no three distinct elements that sum to zero. The cap-set problem asks: how large can a cap set be?

The cardinality of the largest cap set is denoted r₃(n) (or sometimes f(n) in the literature). The trivial upper bound is |𝔽₃ⁿ| = 3ⁿ. The question is how much less.

The SET game

Cap sets in 𝔽₃⁴ are exactly collections of cards from the game SET with no valid SET. A SET card has four attributes (colour, shape, shading, number), each in three values β€” a vector in 𝔽₃⁴. A SET is three cards that, in each attribute, are either all the same or all different β€” i.e. three cards summing to (0, 0, 0, 0) in 𝔽₃⁴. The famous result r₃(4) = 20 says you can lay out 20 cards on the table with no valid SET (and 21 is impossible). Players sometimes hit this configuration in real games and stare in dismay.

Small known values:

For larger n the exact value is unknown.

The long climb

Upper bounds on r₃(n) drifted down over decades:

Then May 2016 happened. Croot, Lev, and Pach posted an arXiv preprint proving an analogous bound for 𝔽₄ⁿ using a clever polynomial argument. Within ten days, Ellenberg and Gijswijt adapted the technique to 𝔽₃ⁿ and proved:

r₃(n) ≀ O(2.756ⁿ).

This is exponentially better than the 3ⁿ / poly bound β€” the base of the exponent dropped from 3 to a number strictly less than 3 β€” and constituted one of the largest single-step improvements in combinatorics in a generation. The exact constant is

Ξ“ β‰ˆ 2.7551 = 3 Β· (the unique root of a specific cubic in (1, 3)),

and the proof, in the original Ellenberg–Gijswijt version, fits in three pages.

The polynomial method, again

The strategy is the same one we saw in Dvir's kakeya proof and Guth–Katz's distinct-distances proof: count polynomials, restrict to lines, force a contradiction.

  1. For a cap set S βŠ† 𝔽₃ⁿ, consider polynomials in n variables over 𝔽₃ of bounded degree.
  2. If |S| is too large, there's a non-zero polynomial P of low degree vanishing on S. Linear algebra: a polynomial space of dimension > |S| can hit a non-zero solution to the |S| linear conditions "P(x) = 0 for each x ∈ S."
  3. The trick is to construct P from a tensor-rank computation that's specific to 𝔽₃ and to the three-term-progression structure. The "slice rank" of a matrix factorisation drives the exponent down from 3 to 2.756.
  4. The bound follows from comparing slice rank to dimension.

The slice-rank technique introduced here has since proliferated through additive combinatorics β€” Naslund's bounds on Hales–Jewett, Kleinberg's tight bound on the four-term variant, and others all use it.

What's still open

Is the new bound tight? Probably not. The largest known cap sets (Edel 2004, Calderbank–Fishburn 1994) achieve only ~2.217ⁿ asymptotically, leaving a gap with 2.756ⁿ. Closing this gap β€” finding the true exponent of r₃(n) β€” is the cap-set problem's current frontier.

What's in this site

Polynomial-method trilogy, closed

kakeya (2008, Dvir, 𝔽qⁿ) β†’ guthkatz (2015, ℝ²) β†’ capset (2016, 𝔽₃ⁿ). Eight years, three theorems, one method. The pattern is now textbook: count low-degree polynomials, exploit their vanishing on a sparse set, restrict to algebraic curves, force contradiction. The method continues to surprise β€” every few years, a long-standing problem in extremal combinatorics or harmonic analysis falls to a clever application of it.

sources