View source for Cap set

{{Short description|Points with no three in a line}}
[[File:Cap set.svg|thumb|right|The 9 points and 12 lines of <math>\mathbb{Z}_3^2</math>, and a 4-element cap set (the four yellow points) in this space]]
In [[affine geometry]], a '''cap set''' is a subset of the affine space <math>\mathbb{Z}_3^n</math> (the <math>n</math>-dimensional [[affine space]] over the [[finite field|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 <math>n</math>.<ref name="austin">{{citation|url=https://www.ams.org/samplings/feature-column/fc-2016-08|title=Game. SET. Polynomial.|work=Feature column|publisher=[[American Mathematical Society]]|first=David|last=Austin|date=August 2016}}.</ref> The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ... {{OEIS|A090245}}.

'''Caps''' are defined more generally as subsets of a finite affine or [[projective space]] with no three in a line.<ref name="edel"/> 

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 space]]s<ref>See, e.g., {{citation
 | last = Chapman | first = T. A.
 | journal = Transactions of the American Mathematical Society
 | mr = 0283828
 | pages = 399–426
 | title = Dense sigma-compact subsets of infinite-dimensional manifolds
 | volume = 154
 | year = 1971
 | doi = 10.1090/s0002-9947-1971-0283828-7| doi-access = free
 }}<!--https://digitalcommons.lsu.edu/gradschool_disstheses/1831
 }}-->.</ref> as well as from compact convex co-convex subsets of a convex set.<ref>See, e.g., {{citation
 | last = Minʹkova | first = R. M.
 | issue = 3
 | journal = Akademiya Nauk Soyuza SSR
 | mr = 534099
 | pages = 435–443, 477
 | title = Weak Korovkin spaces
 | volume = 25
 | year = 1979}}.</ref>

==Example==
{{Set_isomorphic_cards.svg}}
An example of cap sets comes from the card game [[Set (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 <math>\mathbb{Z}_3^4</math>, 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.<ref name="austin"/><ref name="quanta">{{citation|title=Simple Set Game Proof Stuns Mathematicians|magazine=Quanta|first=Erica|last=Klarreich|date=May 31, 2016|url=https://www.quantamagazine.org/20160531-set-proof-stuns-mathematicians/|access-date=August 2, 2016|archive-date=December 24, 2016|archive-url=https://web.archive.org/web/20161224083619/https://www.quantamagazine.org/20160531-set-proof-stuns-mathematicians/|url-status=dead}}</ref><ref name="bulletin">{{citation|last=Grochow | first = Joshua A. | doi = 10.1090/bull/1648 | volume = 56 | journal = Bulletin of the American Mathematical Society | mr = 3886143 | pages = 29–64 | title = New applications of the polynomial method: The cap set conjecture and beyond | year = 2019 | doi-access = free }}</ref>

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 <math>\mathbb{Z}_3^n</math> of size <math>2^n</math>. However, in 1970, Giuseppe Pellegrino proved that four-dimensional cap sets have maximum size 20.<ref>{{Cite journal |last=Pellegrino |first=Giuseppe |date=1970 |title=Sul massimo ordine delle calotte in \(S_4,3\) |trans-title=The maximal order of the spherical cap in \(S_4,3\) |url=https://zbmath.org/0223.50020 |journal=Le Matematiche |language=Italian |volume=25 |pages=149–157 |issn=0373-3505}}</ref> 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.)<ref>{{Citation |last=Hill |first=R. |title=On Pellegrino's 20-Caps in S4, 3 |date=1983-01-01 |url=https://www.sciencedirect.com/science/article/pii/S030402080873322X |work=North-Holland Mathematics Studies |volume=78 |pages=433–447 |editor-last=Barlotti |editor-first=A. |access-date=2023-12-16 |series=Combinatorics '81 in honour of Beniamino Segre |publisher=North-Holland |doi=10.1016/S0304-0208(08)73322-X |isbn=978-0-444-86546-5 |editor2-last=Ceccherini |editor2-first=P. V. |editor3-last=Tallini |editor3-first=G.}}</ref>

==Maximum size==
Since the work of Pellegrino in 1971, and of [[Tom Brown (mathematician)|Tom Brown]] and Joe Buhler, who in 1984 proved that cap-sets cannot constitute any constant proportion of the whole space,<ref name="Brown 214–220">{{Cite journal|last1=Brown|first1=T. C|authorlink1=Tom Brown (mathematician)|last2=Buhler|first2=J. P|date=1984-03-01|title=Lines imply spaces in density Ramsey theory|journal=[[Journal of Combinatorial Theory]] | series=Series A|volume=36|issue=2|pages=214–220|doi=10.1016/0097-3165(84)90006-2|doi-access=free}}</ref> 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 <math>2^n</math> for any higher dimension, which was further improved to <math>2.2173^{n}</math> by {{harvtxt|Edel|2004}}<ref name="edel">{{citation
 | last = Edel | first = Yves
 | doi = 10.1023/A:1027365901231
 | issue = 1
 | journal = Designs, Codes and Cryptography
 | mr = 2031694
 | pages = 5–14
 | title = Extensions of generalized product caps
 | volume = 31
 | year = 2004}}.</ref>
and then to <math>2.2180^{n}</math> by {{harvtxt|Tyrrell|2022}}.<ref name="tyrrell">{{cite journal |last1=Tyrrell |first1=Fred |date=2022 |title=New lower bounds for cap sets |url=https://discreteanalysisjournal.com/article/91076-new-lower-bounds-for-cap-sets |journal=Discrete Analysis |volume=2023 |issue=20 |pages= |doi=10.19086/da.91076 |doi-broken-date=1 November 2024 |access-date=9 January 2024 |arxiv=2209.10045}}</ref> 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 <math>2.2202^{n}</math>.<ref>{{Cite journal |last1=Romera-Paredes |first1=Bernardino |last2=Barekatain |first2=Mohammadamin |last3=Novikov |first3=Alexander |last4=Balog |first4=Matej |last5=Kumar |first5=M. Pawan |last6=Dupont |first6=Emilien |last7=Ruiz |first7=Francisco J. R. |last8=Ellenberg |first8=Jordan S. |last9=Wang |first9=Pengming |last10=Fawzi |first10=Omar |last11=Kohli |first11=Pushmeet |last12=Fawzi |first12=Alhussein |date=2023-12-14 |title=Mathematical discoveries from program search with large language models |journal=Nature |volume=625 |issue=7995 |language=en |pages=468–475 |doi=10.1038/s41586-023-06924-6 |issn=1476-4687|doi-access=free |pmid=38096900 |pmc=10794145 }}</ref>

===Upper bounds===
In 1984, [[Tom Brown (mathematician)|Tom Brown]] and Joe Buhler<ref name="Brown 214–220"/> proved that the largest possible size of a cap set in <math>\mathbb{Z}_3^n</math> is <math>o(3^n)</math> as <math>n</math> grows; loosely speaking, this means that cap sets have zero density. [[Péter Frankl]], [[Ronald Graham]], and [[Vojtěch Rödl]] have shown<ref>{{cite journal|last1=Frankl|first1=P.|author1-link=Peter Frankl|last2=Graham|first2=R. L.|author2-link=Ronald Graham|last3=Rödl|first3=V.|author3-link=Vojtěch Rödl|doi=10.1016/0097-3165(87)90053-7|issue=1|journal=[[Journal of Combinatorial Theory]]|mr=883900|pages=157–161|series=Series A|title=On subsets of abelian groups with no 3-term arithmetic progression|volume=45|year=1987|doi-access=free}}</ref> in 1987 that the result of Brown and Buhler follows easily from the [[Imre Z. Ruzsa|Ruzsa]] - [[Endre Szemerédi|Szemerédi]] [[triangle removal lemma]], and asked whether there exists a constant  <math>c<3</math> such that, indeed, for all sufficiently large values of  <math>n</math>, any cap set in <math>\mathbb{Z}_3^n</math> has size at most <math>c^n</math>; that is, whether any set in <math>\mathbb{Z}_3^n</math> of size exceeding <math>c^n</math> contains an affine line. This question also appeared in a paper<ref>{{Cite journal|last1=Alon|first1=Noga|last2=Dubiner|first2=Moshe|title=A lattice point problem and additive number theory|journal=Combinatorica|language=en|volume=15|issue=3|pages=301–309|doi=10.1007/BF01299737|issn=0209-9683|year=1995}}</ref> published by [[Noga Alon]] and Moshe Dubiner in 1995. In the same year, Roy Meshulam proved<ref>{{Cite journal|last=Meshulam|first=Roy|date=1995-07-01|title=On subsets of finite abelian groups with no 3-term arithmetic progressions|journal=[[Journal of Combinatorial Theory]] | series=Series A|volume=71|issue=1|pages=168–172|doi=10.1016/0097-3165(95)90024-1|doi-access=free}}</ref> that the size of a cap set does not exceed  <math>2\cdot3^n/n</math>. Michael Bateman and [[Nets Katz]]<ref>{{Cite journal|last1=Bateman|first1=Michael|last2=Katz|first2=Nets|date=2012-01-01|title=New bounds on cap sets|journal=Journal of the American Mathematical Society|volume=25|issue=2|pages=585–613|doi=10.1090/S0894-0347-2011-00725-X|issn=0894-0347|arxiv=1101.5851}}</ref> improved the bound to <math>O(3^n/n^{1+\varepsilon})</math> with a positive constant <math>\varepsilon</math>. 

Determining whether Meshulam's bound can be improved to  <math>c^n</math> with  <math>c<3</math> was considered one of the most intriguing open problems in [[Arithmetic combinatorics|additive combinatorics]] and [[Ramsey theory]] for over 20 years, highlighted, for instance, by blog posts on this problem from [[Fields Medal|Fields medalists]] [[Timothy Gowers]]<ref>{{Cite web|url=https://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem/|title=What is difficult about the cap-set problem?|date=2011-01-11|website=Gowers's Weblog|access-date=2016-11-26}}</ref> and [[Terence Tao]].<ref name="tao">{{Cite web|url=https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/|title=Open question: best bounds for cap sets|last=Tao |first=Terence|date=2007-02-23|website=What's new|access-date=2016-11-26}}</ref> 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 <math>p</math>, a subset <math>S \subset F_p^n</math> that contains no arithmetic progression of length <math>3</math> has size at most <math>c_p^n</math> for some <math>c_p<p</math>.<ref name="tao" />

The cap set conjecture was solved in 2016 due to a series of breakthroughs in the polynomial method. [[Ernest S. Croot III|Ernie Croot]], Vsevolod Lev, and Péter Pál Pach posted a preprint on the related problem of progression-free subsets of <math>\mathbb{Z}_4^n</math>, and the method was used by [[Jordan Ellenberg]] and [[Dion Gijswijt]] to prove an upper bound of <math>2.756^n</math> on the cap set problem.<ref name="quanta"/><ref name="bulletin"/><ref>{{citation|title=An exponential upper bound for the cap-set problem|journal=[[Discrete Analysis]]|department=Editorial|date=June 5, 2016|url=http://discreteanalysisjournal.com/post/45-an-exponential-upper-bound-for-the-cap-set-problem}}.</ref><ref>{{citation
 | last1 = Croot | first1 = Ernie | author1-link = Ernest S. Croot III
 | last2 = Lev | first2 = Vsevolod
 | last3 = Pach | first3 = Peter
 | arxiv = 1605.01506
|doi=10.4007/annals.2017.185.1.7
 | title = Progression-free sets in <math>Z_4^n</math> are exponentially small
 | year = 2017|volume=185|issue=1|pages=331–337|journal=Annals of Mathematics| bibcode = 2016arXiv160501506C}}.</ref><ref>{{citation|last1=Ellenberg|first1=Jordan S.|author1-link=Jordan Ellenberg|last2=Gijswijt|first2=Dion|arxiv=1605.09223|doi=10.4007/annals.2017.185.1.8|issue=1|journal=[[Annals of Mathematics]]|mr=3583358|pages=339–343|series=Second Series|title=On large subsets of <math>\mathbb{F}^n_q</math> with no three-term arithmetic progression|volume=185|year=2017}}</ref> In 2019, Sander Dahmen, Johannes Hölzl and Rob Lewis formalised the proof of this upper bound in the [[Lean (proof assistant)|Lean theorem prover]].<ref>{{citation | last1 = Dahmen | first1 = Sander R. | last2 = Hölzl | first2 = Johannes | last3 = Lewis | first3 = Robert Y. | editor1-last = Harrison | editor1-first = John | editor2-last = O'Leary | editor2-first = John | editor3-last = Tolmach | editor3-first = Andrew | arxiv = 1907.01449 | contribution = Formalizing the solution to the cap set problem | doi = 10.4230/LIPIcs.ITP.2019.15 | pages = 15:1–15:19 | publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik | series = LIPIcs | title = 10th International Conference on Interactive Theorem Proving, ITP 2019, September 9-12, 2019, Portland, OR, USA | volume = 141 | year = 2019| doi-access = free | isbn = 978-3-95977-122-1 }}</ref>

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 <math>{\sqrt{n}}</math>.<ref>{{citation
 | last = Jiang | first = Zhi
 | arxiv = 2103.06481
 | title = Explicit Upper Bounds for the Cap Set Problem
 | year = 2021}}</ref> This saving occurs for the same reasons that there is a <math>{1/\sqrt{n}}</math> factor in the [[central binomial coefficient]].

==Mutually disjoint cap sets==
In 2013, five researchers together published an analysis of all the ways in which spaces of up to the size of <math>\mathbb{Z}_3^4</math> can be partitioned into disjoint cap sets.<ref name=disjoint>{{citation | last1 = Follett | first1 = Michael | last2 = Kalail | first2 = Kyle | last3 = McMahon | first3 = Elizabeth | last4 = Pelland | first4 = Catherine | last5 = Won | first5 = Robert | doi = 10.1016/j.disc.2014.08.002 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | mr = 3262358 | pages = 1–8 | title = Partitions of <math>AG(4,3)</math> into maximal caps | volume = 337 | year = 2014| doi-access = free | arxiv = 1302.4703 }}</ref> They reported that it is possible to use four different cap sets of size 20 in <math>\mathbb{Z}_3^4</math> 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. Results for larger sizes are still open as of 2021.

==Applications==
===Sunflower conjecture===
{{Main|Sunflower (mathematics)}}
The solution to the cap set problem can also be used to prove a partial form of the [[Sunflower (mathematics)|sunflower conjecture]], namely that if a family of subsets of an <math>n</math>-element set has no three subsets whose pairwise intersections are all equal, then the number of subsets in the family is at most <math>c^n</math> for a constant <math>c<2</math>.<ref name="quanta"/><ref>{{Cite web|url=https://www.quantamagazine.org/mathematicians-begin-to-tame-wild-sunflower-problem-20191021/|title=Mathematicians Begin to Tame Wild 'Sunflower' Problem|last=Hartnett|first=Kevin|website=Quanta Magazine|date=21 October 2019 |access-date=2019-10-22}}</ref><ref name="bulletin"/><ref>{{citation|url=https://gilkalai.wordpress.com/2016/05/17/polymath-10-emergency-post-5-the-erdos-szemeredi-sunflower-conjecture-is-now-proven/|title=Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven|first=Gil|last=Kalai|author-link=Gil Kalai|date=May 17, 2016|work=Combinatorics and more}}.</ref>

===Matrix multiplication algorithms===
The upper bounds on cap sets imply lower bounds on certain types of algorithms for [[Computational complexity of matrix multiplication#Group theory reformulation of matrix multiplication algorithms|matrix multiplication]].<ref>{{citation
 | last1 = Blasiak | first1 = Jonah
 | last2 = Church | first2 = Thomas
 | last3 = Cohn | first3 = Henry
 | last4 = Grochow | first4 = Joshua A.
 | last5 = Umans | first5 = Chris | author5-link = Chris Umans
 | arxiv = 1605.06702
 | title = On cap sets and the group-theoretic approach to matrix multiplication
 | journal = Discrete Analysis
 | year = 2016| bibcode = 2016arXiv160506702B| doi = 10.19086/da.1245
 }}.</ref>

===Strongly regular graphs===
{{main|Games graph}}
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).<ref>{{citation
 | last = Hill | first = Raymond
 | doi = 10.1016/0012-365X(78)90120-6
 | issue = 2
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 523299
 | pages = 111–137
 | title = Caps and codes
 | volume = 22
 | year = 1978| doi-access = free
 }}.</ref>

==See also==
*[[No-three-in-line problem]], a problem of avoiding three elements in a line in a two-dimensional grid
*[[Ruzsa–Szemerédi problem]]

==References==
{{reflist|30em}}

[[Category:Ramsey theory]]