Cap set

-dimensional affine space over the three-element field) where no three elements sum to the zero vector.

[1] 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 cards of this game can be interpreted as representing points of the four-dimensional affine space

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.

[1][5][6] 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.

However, in 1970, Giuseppe Pellegrino proved that four-dimensional cap sets have maximum size 20.

)[8] 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,[9] 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

[10] 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

[11] In 1984, Tom Brown and Joe Buhler[9] proved that the largest possible size of a cap set in

grows; loosely speaking, this means that cap sets have zero density.

Péter Frankl, Ronald Graham, and Vojtěch Rödl have shown[12] 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

This question also appeared in a paper[13] published by Noga Alon and Moshe Dubiner in 1995.

In the same year, Roy Meshulam proved[14] that the size of a cap set does not exceed

Michael Bateman and Nets Katz[15] improved the bound to

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[16] and Terence Tao.

[17] 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

[17] 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

, and the method was used by Jordan Ellenberg and Dion Gijswijt to prove an upper bound of

[5][6][18][19][20] In 2019, Sander Dahmen, Johannes Hölzl and Rob Lewis formalised the proof of this upper bound in the Lean theorem prover.

[21] 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

In 2013, five researchers together published an analysis of all the ways in which spaces of up to the size of

that between them cover 80 different cells; the single cell left uncovered is called the anchor of each of the four cap sets, the single point that when added to the 20 points of a cap set makes the entire sum go to 0 (mod 3).

All cap sets in such a disjoint collection share the same anchor.

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

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).