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 .