Lower bounds

Pellegrino's solution for the four-dimensional cap-set problem also leads to larger lower bounds than ${\displaystyle 2^{n}}$ for any higher dimension, which was further improved to ${\displaystyle 2.2173^{n}}$ by Edel (2004)^[2] and then to ${\displaystyle 2.2180^{n}}$ by Tyrrell (2022).^[9] In December 2023, a team of researchers from Google's DeepMind published a paper where they paired a large language model (LLM) with an evaluator and managed to improve the bound to ${\displaystyle 2.2202^{n}}$.^[10]

Upper bounds

In 1984, Tom Brown and Joe Buhler^[8] proved that the largest possible size of a cap set in ${\displaystyle \mathbb {Z} _{3}^{n}}$ is ${\displaystyle o(3^{n})}$ as ${\displaystyle n}$ grows; loosely speaking, this means that cap sets have zero density. Péter Frankl, Ronald Graham, and Vojtěch Rödl have shown^[11] in 1987 that the result of Brown and Buhler follows easily from the Ruzsa - Szemerédi triangle removal lemma, and asked whether there exists a constant ${\displaystyle c<3}$ such that, indeed, for all sufficiently large values of ${\displaystyle n}$, any cap set in ${\displaystyle \mathbb {Z} _{3}^{n}}$ has size at most ${\displaystyle c^{n}}$; that is, whether any set in ${\displaystyle \mathbb {Z} _{3}^{n}}$ of size exceeding ${\displaystyle c^{n}}$ contains an affine line. This question also appeared in a paper^[12] published by Noga Alon and Moshe Dubiner in 1995. In the same year, Roy Meshulam proved^[13] that the size of a cap set does not exceed ${\displaystyle 2\cdot 3^{n}/n}$. Michael Bateman and Nets Katz^[14] improved the bound to ${\displaystyle O(3^{n}/n^{1+\varepsilon })}$ with a positive constant ${\displaystyle \varepsilon }$.

Determining whether Meshulam's bound can be improved to ${\displaystyle c^{n}}$ with ${\displaystyle c<3}$ was considered one of the most intriguing open problems in additive combinatorics and Ramsey theory for over 20 years, highlighted, for instance, by blog posts on this problem from Fields medalists Timothy Gowers^[15] and Terence Tao.^[16] In his blog post, Tao refers to it as "perhaps, my favorite open problem" and gives a simplified proof of the exponential bound on cap sets, namely that for any prime power ${\displaystyle p}$, a subset ${\displaystyle S\subset F_{p}^{n}}$ that contains no arithmetic progression of length ${\displaystyle 3}$ has size at most ${\displaystyle c_{p}^{n}}$ for some ${\displaystyle c_{p}<p}$.^[16]

The cap set conjecture was solved in 2016 due to a series of breakthroughs in the polynomial method. Ernie Croot, Vsevolod Lev, and Péter Pál Pach posted a preprint on the related problem of progression-free subsets of ${\displaystyle \mathbb {Z} _{4}^{n}}$, and the method was used by Jordan Ellenberg and Dion Gijswijt to prove an upper bound of ${\displaystyle 2.756^{n}}$ on the cap set problem.^{[5][6][17][18][19]} In 2019, Sander Dahmen, Johannes Hölzl and Rob Lewis formalised the proof of this upper bound in the Lean theorem prover.^[20]

As of March 2023, there is no exponential improvement to Ellenberg and Gijswijt's upper bound. Jiang showed that by precisely examining the multinomial coefficients that come out of Ellenberg and Gijswijt's proof, one can gain a factor of ${\displaystyle {\sqrt {n}}}$.^[21] This saving occurs for the same reasons that there is a ${\displaystyle {1/{\sqrt {n}}}}$ factor in the central binomial coefficient.

Sunflower conjecture

The solution to the cap set problem can also be used to prove a partial form of the sunflower conjecture, namely that if a family of subsets of an ${\displaystyle n}$-element set has no three subsets whose pairwise intersections are all equal, then the number of subsets in the family is at most ${\displaystyle c^{n}}$ for a constant ${\displaystyle c<2}$.^{[5][23][6][24]}

Matrix multiplication algorithms

The upper bounds on cap sets imply lower bounds on certain types of algorithms for matrix multiplication.^[25]

Strongly regular graphs

The Games graph is a strongly regular graph with 729 vertices. Every edge belongs to a unique triangle, so it is a locally linear graph, the largest known locally linear strongly regular graph. Its construction is based on the unique 56-point cap set in the five-dimensional ternary projective space (rather than the affine space that cap-sets are commonly defined in).^[26]