Cap set

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

The 9 points and 12 lines of ${\displaystyle \mathbb {Z} _{3}^{2}}$, and a 4-element cap set (the four yellow points) in this space

Cap sets may be defined more generally as subsets of finite affine or projective spaces with no three in line, where these objects are simply called caps.[2] 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[3] as well as from compact convex co-convex subsets of a convex set.[4]

Example

A complete set of 81 cards isomorphic with those of the game Set showing all possible combinations of the four features. Considering each 3×3 group as a plane aligned in 4-dimensional space, a set comprises 3 cards in a (4-dimensional) row, with wrap-around. An example 20-card cap set is shaded yellow.

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.[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. 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 1971, 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.

Maximum size

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,[7] there has been a significant line of research on how large they may be.

Lower bounds

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 were further improved by Edel (2004) to approximately ${\displaystyle 2.2174^{n}}$.[2]

Upper bounds

In 1984, Tom Brown and Joe Buhler[8] 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[9] 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[10] published by Noga Alon and Moshe Dubiner in 1995. In the same year, Roy Meshulam proved[11] that the size of a cap set does not exceed ${\displaystyle 2\cdot 3^{n}/n}$.

Determining whether Meshulam's bound can be improved to ${\displaystyle c^{n}}$ with ${\displaystyle c<3}$ 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[12] and Terence Tao.[13] 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 ${\displaystyle p}$, a subset ${\displaystyle S\subset F_{p}^{n}}$ that contains no arithmetic progression of length ${\displaystyle 3}$ has size at most ${\displaystyle c_{p}^{n}}$ for some ${\displaystyle c_{p}<p}$.[13]

In 2011, Michael Bateman and Nets Katz[14] improved the bound to ${\displaystyle O(3^{n}/n^{1+\varepsilon })}$ with a positive constant ${\displaystyle \varepsilon }$. The cap set conjecture was solved in 2016, when Ernie Croot, Vsevolod Lev, and Péter Pál Pach posted a preprint on a tightly related problem, that was quickly used by Jordan Ellenberg and Dion Gijswijt to prove an upper bound of ${\displaystyle 2.756^{n}}$ on the cap set problem.[5][6][15][16][17] In 2019, Sander Dahmen, Johannes Hölzl and Rob Lewis formalised the proof of this upper bound in the Lean theorem prover.[18]

Applications

Sunflower conjecture

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 ${\displaystyle n}$-element set has no three subsets whose pairwise intersections are all equal, then the number of subsets in the family is at most ${\displaystyle c^{n}}$ for a constant ${\displaystyle c<2}$.[5][19][6][20]

Matrix multiplication algorithms

The upper bounds on cap sets imply lower bounds on certain types of algorithms for matrix multiplication.[21]

Strongly regular graphs

The Games graph is a strongly regular graph with 729 vertices. 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).[22]

See also

• No-three-in-line problem, a problem of avoiding three elements in a line in a two-dimensional grid

References

1. Austin, David (August 2016), "Game. SET. Polynomial.", Feature column, American Mathematical Society.
2. Edel, Yves (2004), "Extensions of generalized product caps", Designs, Codes and Cryptography, 31 (1): 5–14, doi:10.1023/A:1027365901231, MR 2031694.
3. See, e.g., Chapman, T. A. (1971), "Dense sigma-compact subsets of infinite-dimensional manifolds", Transactions of the American Mathematical Society, 154: 399–426, doi:10.1090/s0002-9947-1971-0283828-7, MR 0283828.
4. See, e.g., Minʹkova, R. M. (1979), "Weak Korovkin spaces", Akademiya Nauk Soyuza SSR, 25 (3): 435–443, 477, MR 0534099.
5. Klarreich, Erica (May 31, 2016), "Simple Set Game Proof Stuns Mathematicians", Quanta
6. Grochow, Joshua A. (2019), "New applications of the polynomial method: The cap set conjecture and beyond", Bulletin of the American Mathematical Society, 56: 29–64, doi:10.1090/bull/1648, MR 3886143
7. Brown, T. C; Buhler, J. P (1984-03-01). "Lines imply spaces in density Ramsey theory". Journal of Combinatorial Theory, Series A. 36 (2): 214–220. doi:10.1016/0097-3165(84)90006-2.
8. Brown, T. C; Buhler, J. P (1984-03-01). "Lines imply spaces in density Ramsey theory". Journal of Combinatorial Theory, Series A. 36 (2): 214–220. doi:10.1016/0097-3165(84)90006-2.
9. Frankl, P.; Graham, R. L.; Rödl, V. (1987). "On subsets of abelian groups with no 3-term arithmetic progression". Journal of Combinatorial Theory. Series A. 45 (1): 157–161. doi:10.1016/0097-3165(87)90053-7. MR 0883900.
10. Alon, Noga; Dubiner, Moshe (1995). "A lattice point problem and additive number theory". Combinatorica. 15 (3): 301–309. doi:10.1007/BF01299737. ISSN 0209-9683.
11. Meshulam, Roy (1995-07-01). "On subsets of finite abelian groups with no 3-term arithmetic progressions". Journal of Combinatorial Theory, Series A. 71 (1): 168–172. doi:10.1016/0097-3165(95)90024-1.
12. "What is difficult about the cap-set problem?". Gowers's Weblog. 2011-01-11. Retrieved 2016-11-26.
13. "Open question: best bounds for cap sets". What's new. 2007-02-23. Retrieved 2016-11-26.
14. Bateman, Michael; Katz, Nets (2012-01-01). "New bounds on cap sets". Journal of the American Mathematical Society. 25 (2): 585–613. arXiv:1101.5851. doi:10.1090/S0894-0347-2011-00725-X. ISSN 0894-0347.
15. Editors (June 5, 2016), "An exponential upper bound for the cap-set problem", Editorial, Discrete AnalysisCS1 maint: extra text: authors list (link).
16. Croot, Ernie; Lev, Vsevolod; Pach, Peter (2017), "Progression-free sets in ${\displaystyle Z_{4}^{n}}$ are exponentially small", Annals of Mathematics, 185 (1): 331–337, arXiv:1605.01506, Bibcode:2016arXiv160501506C, doi:10.4007/annals.2017.185.1.7.
17. Ellenberg, Jordan S.; Gijswijt, Dion (2017), "On large subsets of ${\displaystyle \mathbb {F} _{q}^{n}}$ with no three-term arithmetic progression", Annals of Mathematics, Second Series, 185 (1): 339–343, arXiv:1605.09223, doi:10.4007/annals.2017.185.1.8, MR 3583358
18. Dahmen, Sander; Hölzl, Johannes; Lewis, Robert (2019), Formalizing the Solution to the Cap Set Problem, arXiv:1907.01449, doi:10.4230/LIPIcs.ITP.2019.15.
19. Hartnett, Kevin. "Mathematicians Begin to Tame Wild 'Sunflower' Problem". Quanta Magazine. Retrieved 2019-10-22.
20. Kalai, Gil (May 17, 2016), "Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven", Combinatorics and more.
21. Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; Umans, Chris (2016), "On cap sets and the group-theoretic approach to matrix multiplication", Discrete Analysis, arXiv:1605.06702, Bibcode:2016arXiv160506702B, doi:10.19086/da.1245.
22. Hill, Raymond (1978), "Caps and codes", Discrete Mathematics, 22 (2): 111–137, doi:10.1016/0012-365X(78)90120-6, MR 0523299.