“Cap set”的意思、由来-开放百科全书

In affine geometry, a cap set is a subset of

(an

-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

.^[1] The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ... {{OEIS|A090245}}.

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]

An example of this problem 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

, 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]^[2]

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

of size

. However, in 1971, Giuseppe Pellegrino proved that Set has larger cap sets, consisting of up to 20 cards, and that this is the largest possible size for these sets. Pellegrino's solution for the four-dimensional cap-set problem also leads to larger lower bounds than

for any higher dimension, which were further improved by {{harvtxt|Edel|2004}} to approximately

.^[3]

In 1984, Tom Brown and Joe Buhler^[4] 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^[5] 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

such that, indeed, for all sufficiently large values of

, any cap set in

has size at most

; that is, whether any set in

of size exceeding

contains an affine line. This question also appeared in a paper^[6] published by Noga Alon and Moshe Dubiner in 1995. Same year, Roy Meshulam proved^[7] that the size of a cap set does not exceed

. Determining whether Meshulam's bound can be improved to

with

was considered one of the most intriguing open problems in additive combinatorics and Ramsey theory for over 20 years; see, for instance, blog posts on this problem by the Fields medalists Timothy Gowers^[8] and Terence Tao^[9] (in the latter post, Tao refers to this problem as "perhaps, my favorite open problem"). It was considered a major breakthrough when in 2011, Michael Bateman and Nets Katz^[10] improved the bound to

with a positive constant

. The cap set problem 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

on the cap set problem.^[2]^[11]^[12]^[13]

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

-element set has no three subsets whose pairwise intersections are all equal, then the number of subsets in the family is at most

for a constant

.^[2]^[14] The new upper bounds also imply lower bounds on certain types of algorithms for matrix multiplication.^[15]

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^[16] as well as from compact convex co-convex subsets of a convex set.^[17]

See also

References

1. ^¹{{citation|url=http://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}}.
2. ^¹²{{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/}}.
3. ^¹{{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}}.
4. ^{{Cite journal|last=Brown|first=T. C|last2=Buhler|first2=J. P|date=1984-03-01|title=Lines imply spaces in density Ramsey theory|url=http://www.sciencedirect.com/science/article/pii/0097316584900062|journal=Journal of Combinatorial Theory, Series A|volume=36|issue=2|pages=214–220|doi=10.1016/0097-3165(84)90006-2}}
5. ^{{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}}
6. ^{{Cite journal|last=Alon|first=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}}
7. ^{{Cite journal|last=Meshulam|first=Roy|date=1995-07-01|title=On subsets of finite abelian groups with no 3-term arithmetic progressions|url=http://www.sciencedirect.com/science/article/pii/0097316595900241|journal=Journal of Combinatorial Theory, Series A|volume=71|issue=1|pages=168–172|doi=10.1016/0097-3165(95)90024-1}}
8. ^{{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}}
9. ^{{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|date=2007-02-23|website=What's new|access-date=2016-11-26}}
10. ^{{Cite journal|last=Bateman|first=Michael|last2=Katz|first2=Nets|date=2012-01-01|title=New bounds on cap sets|url=http://www.ams.org/jams/2012-25-02/S0894-0347-2011-00725-X/|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}}
11. ^{{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|author=Editors}}.
12. ^{{citation | last1 = Croot | first1 = Ernie | author1-link = Ernest S. Croot III | last2 = Lev | first2 = Vsevolod | last3 = Pach | first3 = Peter | arxiv = 1605.01506 | title = Progression-free sets in

are exponentially small | year = 2016| bibcode = 2016arXiv160501506C}}.
13. ^{{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

with no three-term arithmetic progression|volume=185|year=2017}}
14. ^{{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|authorlink=Gil Kalai|date=May 17, 2016|work=Combinatorics and more}}.
15. ^{{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 }}.
16. ^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}}.
17. ^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}}.