MathLabs

Cap set problem

Solved, 2016Combinatorics and discrete mathematics
Statement

Determine whether the maximum size r3(F3n)r_3(\mathbb{F}_3^n) of a cap set—a subset A⊆F3nA \subseteq \mathbb{F}_3^n containing no three-term arithmetic progression (no three distinct elements x,y,z∈Ax, y, z \in A with x+y+z=0x + y + z = 0)—grows exponentially with a base strictly less than 33, i.e., r3(F3n)≤cnr_3(\mathbb{F}_3^n) \le c^n for some constant c<3c < 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 (Z/4Z)n(\mathbb{Z}/4\mathbb{Z})^n. Within days, Jordan Ellenberg and Dion Gijswijt adapted their technique to Fqn\mathbb{F}_q^n, proving that every cap set in F3n\mathbb{F}_3^n has size at most O(cn)O(c^n) with c=3(8−1/3)(1+8−1/3+8−2/3)/2≈2.7552<3c = 3(8^{-1/3})(1+8^{-1/3}+8^{-2/3}) / 2 \approx 2.7552 < 3 (equivalently 381/3⋅⋯≈2.756\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 (≈2.220n\approx 2.220^n) and 2.7552n2.7552^n remains open.

  1. The polynomial method resolves the cap set problem (Croot-Lev-Pach, Ellenberg-Gijswijt, 2016)Ernie Croot, Vsevolod Lev, Péter Pál Pach; Jordan Ellenberg and Dion Gijswijt; slice-rank reformulation by Terence Tao, 2016Difficulty 4/5Advanced

References

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