Cap set problem
Solved, 2016Combinatorics and discrete mathematics
Statement
Determine whether the maximum size of a cap set—a subset containing no three-term arithmetic progression (no three distinct elements with )—grows exponentially with a base strictly less than , i.e., for some constant .
In May 2016, Ernie Croot, Vsevolod Lev, and Péter Pál Pach introduced a breakthrough polynomial method to bound progression-free sets in . Within days, Jordan Ellenberg and Dion Gijswijt adapted their technique to , proving that every cap set in has size at most with (equivalently ). 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 () and remains open.
References
- Jordan S. Ellenberg, Dion Gijswijt (2017). On large subsets of 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 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