In affine geometry, a cap set is a subset of the affine space ${\displaystyle \mathbb {Z} _{3}^{n}}$ (the ${\displaystyle n}$-dimensional affine space over the three-element field) where no three elements sum to the zero vector. The cap set problem is the problem of finding the size of the largest possible cap set, as a function of ${\displaystyle n}$. The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ... (sequence A090245 in the OEIS).

Caps are defined more generally as subsets of a finite affine or projective space with no three in a line.

The "cap set" terminology should be distinguished from other unrelated mathematical objects with the same name, and in particular from sets with the compact absorption property in function spaces as well as from compact convex co-convex subsets of a convex set.

An example of cap sets comes from the card game Set, a card game in which each card has four features (its number, symbol, shading, and color), each of which can take one of three values. The cards of this game can be interpreted as representing points of the four-dimensional affine space ${\displaystyle \mathbb {Z} _{3}^{4}}$, where each coordinate of a point specifies the value of one of the features. A line, in this space, is a triple of cards that, in each feature, are either all the same as each other or all different from each other. The game play consists of finding and collecting lines among the cards that are currently face up, and a cap set describes an array of face-up cards in which no lines may be collected.

One way to construct a large cap set in the game Set would be to choose two out of the three values for each feature, and place face up each of the cards that uses only one of those two values in each of its features. The result would be a cap set of 16 cards. More generally, the same strategy would lead to cap sets in ${\displaystyle \mathbb {Z} _{3}^{n}}$ of size ${\displaystyle 2^{n}}$. However, in 1970, Giuseppe Pellegrino proved that four-dimensional cap sets have maximum size 20. In terms of Set, this result means that some layouts of 20 cards have no line to be collected, but that every layout of 21 cards has at least one line. (The dates are not a typo: the Pellegrino cap set result from 1970 really does predate the first publication of the Set game in 1974.)

Since the work of Pellegrino in 1971, and of Tom Brown and Joe Buhler, who in 1984 proved that cap-sets cannot constitute any constant proportion of the whole space, there has been a significant line of research on how large they may be.

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) and then to ${\displaystyle 2.2180^{n}}$ by Tyrrell (2022). 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}}$.

In 1984, Tom Brown and Joe Buhler 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 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 published by Noga Alon and Moshe Dubiner in 1995. In the same year, Roy Meshulam proved that the size of a cap set does not exceed ${\displaystyle 2\cdot 3^{n}/n}$. Michael Bateman and Nets Katz improved the bound to ${\displaystyle O(3^{n}/n^{1+\varepsilon })}$ with a positive constant ${\displaystyle \varepsilon }$.