Cap set problem

Solved, 2016Combinatorics and discrete mathematics

Statement

Determine whether the maximum size $r_3(\mathbb{F}_3^n)$ of a cap set—a subset $A \subseteq \mathbb{F}_3^n$ containing no three-term arithmetic progression (no three distinct elements $x, y, z \in A$ with $x + y + z = 0$ )—grows exponentially with a base strictly less than $3$ , i.e., $r_3(\mathbb{F}_3^n) \le c^n$ for some constant $c < 3$ .

In May 2016, Ernie Croot, Vsevolod Lev, and Péter Pál Pach introduced a breakthrough polynomial method to bound progression-free sets in $(\mathbb{Z}/4\mathbb{Z})^n$ . Within days, Jordan Ellenberg and Dion Gijswijt adapted their technique to $\mathbb{F}_q^n$ , proving that every cap set in $\mathbb{F}_3^n$ has size at most $O(c^n)$ with $c = 3(8^{-1/3})(1+8^{-1/3}+8^{-2/3}) / 2 \approx 2.7552 < 3$ (equivalently $\frac{3}{8^{1/3}} \cdot \dots \approx 2.756$ ). Terence Tao reformulated the argument cleanly via the slice rank of tensors. While this settled the qualitative exponential-saving conjecture, pinning down the exact exponential base between the best lower bound ( $\approx 2.220^n$ ) and $2.7552^n$ remains open.

In the popular card game Set, a deck has $81 = 3^4$ cards and a 'Set' is a line in $\mathbb{F}_3^4$ ; the maximum number of cards with no Set is $r_3(\mathbb{F}_3^4) = 20$ . The slice-rank polynomial method sparked immediate breakthroughs on the Erdős–Szemerédi sunflower problem, matrix multiplication barriers, and chromatic numbers of algebraic hypergraphs.

References

Jordan S. Ellenberg, Dion Gijswijt (2017). On large subsets of $\mathbb{F}_q^n$ with no three-term arithmetic progression · DOI:10.4007/annals.2017.185.1.8 · arXiv:1605.09223
Ernie Croot, Vsevolod F. Lev, Péter Pál Pach (2017). Progression-free sets in $\mathbb{Z}_4^n$ are exponentially small · DOI:10.4007/annals.2017.185.1.7 · arXiv:1605.01506
Fred Tyrrell (2023). New lower bounds for cap sets · arXiv:2209.10045

History of the problem

1995Roy Meshulam adapts Roth's Fourier-analytic method to finite fields, proving $r_3(\mathbb{F}_3^n) = O(3^n / n)$ and popularizing the problem of whether an exponential bound $c^n$ ( $c < 3$ ) holds.
2004Yves Edel constructs high-dimensional cap sets via product codes, establishing a long-standing asymptotic lower bound of $r_3(\mathbb{F}_3^n) = \Omega(2.217389^n)$ .
2012Michael Bateman and Nets Hawk Katz break the $3^n / n$ barrier using additive-combinatorial structure theory, proving $r_3(\mathbb{F}_3^n) = O(3^n / n^{1+\varepsilon})$ .
2016Following Croot, Lev, and Pach's polynomial method in $(\mathbb{Z}/4\mathbb{Z})^n$ , Ellenberg and Gijswijt prove $r_3(\mathbb{F}_3^n) = O(2.756^n)$ , and Terence Tao formulates the slice-rank method.Terence Tao
2022Fred Tyrrell improves Edel's lower bound to $\Omega(2.218^n)$ via SAT solvers, followed by further constructions (including FunSearch and Naslund) pushing the lower bound above $2.220^n$ .