A cap set is a subset of the affine space containing no three distinct collinear points, where is a positive integer and is the finite field with three elements. Equivalently, the only solutions in to

have . This is also the condition that contain no nonconstant three-term arithmetic progression, since is the same equation over (Davis and Maclagan 2003, Ellenberg and Gijswijt 2017).

The set is a cap set of size . Indeed, three entries from can have sum zero modulo 3 only when they are all equal, so the vector equation forces equality in every coordinate.

Let be the maximum size of a cap set in . The first few values, beginning at , are 2, 4, 9, 20, 45, 112, ... (OEIS A090245). Ellenberg and Gijswijt (2017) proved that there is a constant , independent of , such that

Since , this is exponentially smaller than the points of the full affine space.

In dimension four, (Davis and Maclagan 2003). Under the SET game correspondence, this means that 20 cards can contain no valid triple, whereas every collection of 21 cards contains one.

In an example of AI-assisted mathematics, Romera-Paredes et al. (2024) used program search to find a construction of a cap set of size 512 in dimension eight, giving .

See also

Affine Space, Arithmetic Progression, SET Game

Explore with Wolfram|Alpha

References

Davis, B. L. and Maclagan, D. "The Card Game SET." Math. Intelligencer 25, 33-40, 2003. https://doi.org/10.1007/BF02984846.Ellenberg, J. S. and Gijswijt, D. "On Large Subsets of with No Three-Term Arithmetic Progression." Ann. Math. 185, 339-343, 2017. https://doi.org/10.4007/annals.2017.185.1.8.Romera-Paredes, B.; Barekatain, M.; Novikov, A.; Balog, M.; Kumar, M. P.; Dupont, E.; Ruiz, F. J. R.; Ellenberg, J. S.; Wang, P.; Fawzi, O.; Kohli, P.; and Fawzi, A. "Mathematical Discoveries from Program Search with Large Language Models." Nature 625, 468-475, 2024. https://doi.org/10.1038/s41586-023-06924-6.Sloane, N. J. A. Sequence A090245 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Cap Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CapSet.html

Subject classifications