Concept

Cap set

A set of points in (Z/3)ⁿ with no three on a line — equivalently, no three distinct points adding to nought, and no three-term arithmetic progression. In four dimensions it is a hand of SET cards with no set; the largest possible size is known only up to dimension six.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Eighty-one cards and twenty with no SET among them. A three-by-three arrangement of three-by-three grids covering the eighty-one points of four-dimensional space modulo three, with twenty cells marked that contain no three on a line.

Twenty cards with no set among them

The card game SET is a four-dimensional space over the integers mod 3, and a set is a line in it. Twenty cards can avoid every line and twenty-one cannot — a fact that took a proof in 1970 — while laying cards down at random and stopping when nothing more fits reaches twenty about once in two thousand tries.

computation · Finite fields

The polynomial bound falls exponentially behind the space. A log-scale plot against the dimension of the number of points of the space, the polynomial method's bound on a cap, and the known largest caps: the bound's line is less steep than the space's and pulls away from it.

The polynomial that bounds the caps

For forty years the best bound on a set of SET cards with no set among them shrank only like one over the dimension. In 2016 a two-page argument made it shrink exponentially, and the whole proof is a count of monomials: a table that is diagonal on a cap, one polynomial that describes it, and the fact that three parts of a degree cannot all be large.

computation · Finite fields

Named alongside it

The objects these essays reach for when they reach for this one.

Counting argument Finite field Pigeonhole principle Affine plane Arithmetic progression Exhaustive search Greedy algorithm Large deviations Normal distribution Polynomial method Rank

All concepts