Cap set

Last updated
The 9 points and 12 lines of Z 3 2 {\displaystyle \mathbb {Z} _{3}^{2}} , and a 4-element cap set (the four yellow points) in this space Cap set.svg
The 9 points and 12 lines of , 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 (the -dimensional affine space over the 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 . [1] The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ... (sequence A090245 in the OEIS ).

Contents

Caps are defined more generally as subsets of a finite affine or projective space with no three in a line. [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 3x3 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. Set isomorphic cards.svg
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 , 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 of size . However, in 1970, Giuseppe Pellegrino proved that four-dimensional cap sets have maximum size 20. [7] 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.) [8]

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, [9] 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 for any higher dimension, which was further improved to by Edel (2004) [2] and then to by Tyrrell (2022). [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]

Upper bounds

In 1984, Tom Brown and Joe Buhler [9] proved that the largest possible size of a cap set in is as 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 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 [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 with a positive constant .

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, 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 , a subset that contains no arithmetic progression of length has size at most for some . [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 on the cap set problem. [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 . [22] This saving occurs for the same reasons that there is a 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 can be partitioned into disjoint cap sets. [23] They reported that it is possible to use four different cap sets of size 20 in 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

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

Matrix multiplication algorithms

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

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). [27]

See also

Related Research Articles

In mathematics, a real interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity, indicating the interval extends without a bound. A real interval can contain neither endpoint, either endpoint, or both endpoints, excluding any endpoint which is infinite.

In mathematics, Hilbert's Nullstellensatz is a theorem that establishes a fundamental relationship between geometry and algebra. This relationship is the basis of algebraic geometry. It relates algebraic sets to ideals in polynomial rings over algebraically closed fields. This relationship was discovered by David Hilbert, who proved the Nullstellensatz in his second major paper on invariant theory in 1893.

<span class="mw-page-title-main">Algebraic variety</span> Mathematical object studied in the field of algebraic geometry

Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Modern definitions generalize this concept in several different ways, while attempting to preserve the geometric intuition behind the original definition.

The theory of functions of several complex variables is the branch of mathematics dealing with functions defined on the complex coordinate space, that is, n-tuples of complex numbers. The name of the field dealing with the properties of these functions is called several complex variables, which the Mathematics Subject Classification has as a top-level heading.

<span class="mw-page-title-main">Birational geometry</span> Field of algebraic geometry

In mathematics, birational geometry is a field of algebraic geometry in which the goal is to determine when two algebraic varieties are isomorphic outside lower-dimensional subsets. This amounts to studying mappings that are given by rational functions rather than polynomials; the map may fail to be defined where the rational functions have poles.

In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.

<span class="mw-page-title-main">Arrangement of hyperplanes</span> Partition of space by a hyperplanes

In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set A of hyperplanes in a linear, affine, or projective space S. Questions about a hyperplane arrangement A generally concern geometrical, topological, or other properties of the complement, M(A), which is the set that remains when the hyperplanes are removed from the whole space. One may ask how these properties are related to the arrangement and its intersection semilattice. The intersection semilattice of A, written L(A), is the set of all subspaces that are obtained by intersecting some of the hyperplanes; among these subspaces are S itself, all the individual hyperplanes, all intersections of pairs of hyperplanes, etc. (excluding, in the affine case, the empty set). These intersection subspaces of A are also called the flats ofA. The intersection semilattice L(A) is partially ordered by reverse inclusion.

In mathematics, in the theory of several complex variables and complex manifolds, a Stein manifold is a complex submanifold of the vector space of n complex dimensions. They were introduced by and named after Karl Stein. A Stein space is similar to a Stein manifold but is allowed to have singularities. Stein spaces are the analogues of affine varieties or affine schemes in algebraic geometry.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

In additive combinatorics, a discipline within mathematics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if is small, then can be contained in a small generalized arithmetic progression.

In mathematics, more precisely in the theory of functions of several complex variables, a pseudoconvex set is a special type of open set in the n-dimensional complex space Cn. Pseudoconvex sets are important, as they allow for classification of domains of holomorphy.

<span class="mw-page-title-main">Corners theorem</span> Statement in arithmetic combinatorics

In arithmetic combinatorics, the corners theorem states that for every , for large enough , any set of at least points in the grid contains a corner, i.e., a triple of points of the form with . It was first proved by Miklós Ajtai and Endre Szemerédi in 1974 using Szemerédi's theorem. In 2003, József Solymosi gave a short proof using the triangle removal lemma.

Nets Hawk Katz is the W.L. Moody Professor of Mathematics at Rice University. He was a professor of mathematics at Indiana University Bloomington until March 2013 and the IBM Professor of Mathematics at the California Institute of Technology until 2023. He is currently the W. L. Moody Professor of Mathematics at Rice University.

In algebraic geometry, an affine GIT quotient, or affine geometric invariant theory quotient, of an affine scheme with an action by a group scheme G is the affine scheme , the prime spectrum of the ring of invariants of A, and is denoted by . A GIT quotient is a categorical quotient: any invariant morphism uniquely factors through it.

In algebraic geometry, an exotic affine space is a complex algebraic variety that is diffeomorphic to for some n, but is not isomorphic as an algebraic variety to . An example of an exotic is the Koras–Russell cubic threefold, which is the subset of defined by the polynomial equation

The Lieb–Robinson bound is a theoretical upper limit on the speed at which information can propagate in non-relativistic quantum systems. It demonstrates that information cannot travel instantaneously in quantum theory, even when the relativity limits of the speed of light are ignored. The existence of such a finite speed was discovered mathematically by Elliott H. Lieb and Derek W. Robinson in 1972. It turns the locality properties of physical systems into the existence of, and upper bound for this speed. The bound is now known as the Lieb–Robinson bound and the speed is known as the Lieb–Robinson velocity. This velocity is always finite but not universal, depending on the details of the system under consideration. For finite-range, e.g. nearest-neighbor, interactions, this velocity is a constant independent of the distance travelled. In long-range interacting systems, this velocity remains finite, but it can increase with the distance travelled.

<span class="mw-page-title-main">Flip graph</span> A graph that encodes local operations in mathematics

In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of geometric graphs.

<span class="mw-page-title-main">Ruzsa–Szemerédi problem</span>

In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number of edges in a balanced bipartite graph whose edges can be partitioned into a linear number of induced matchings, or the maximum number of triples one can choose from points so that every six points contain at most two triples. The problem is named after Imre Z. Ruzsa and Endre Szemerédi, who first proved that its answer is smaller than by a slowly-growing factor.

Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers. It was first proven by Klaus Roth in 1953. Roth's theorem is a special case of Szemerédi's theorem for the case .

In mathematics, the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties. Recently, the polynomial method has led to the development of remarkably simple solutions to several long-standing open problems. The polynomial method encompasses a wide range of specific techniques for using polynomials and ideas from areas such as algebraic geometry to solve combinatorics problems. While a few techniques that follow the framework of the polynomial method, such as Alon's Combinatorial Nullstellensatz, have been known since the 1990s, it was not until around 2010 that a broader framework for the polynomial method has been developed.

References

  1. 1 2 Austin, David (August 2016), "Game. SET. Polynomial.", Feature column, American Mathematical Society .
  2. 1 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. 1 2 3 Klarreich, Erica (May 31, 2016), "Simple Set Game Proof Stuns Mathematicians", Quanta, archived from the original on December 24, 2016, retrieved August 2, 2016
  6. 1 2 3 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. ↑ Pellegrino, Giuseppe (1970). "Sul massimo ordine delle calotte in \(S_4,3\)" [The maximal order of the spherical cap in \(S_4,3\)]. Le Matematiche (in Italian). 25: 149–157. ISSN   0373-3505.
  8. ↑ Hill, R. (1983-01-01), Barlotti, A.; Ceccherini, P. V.; Tallini, G. (eds.), "On Pellegrino's 20-Caps in S4, 3", North-Holland Mathematics Studies, Combinatorics '81 in honour of Beniamino Segre, vol. 78, North-Holland, pp. 433–447, doi:10.1016/S0304-0208(08)73322-X, ISBN   978-0-444-86546-5 , retrieved 2023-12-16
  9. 1 2 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 .
  10. ↑ Tyrrell, Fred (2022). "New lower bounds for cap sets". Discrete Analysis. 2023 (20). arXiv: 2209.10045 . doi:10.19086/da.91076 (inactive 1 November 2024). Retrieved 9 January 2024.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)
  11. ↑ Romera-Paredes, Bernardino; Barekatain, Mohammadamin; Novikov, Alexander; Balog, Matej; Kumar, M. Pawan; Dupont, Emilien; Ruiz, Francisco J. R.; Ellenberg, Jordan S.; Wang, Pengming; Fawzi, Omar; Kohli, Pushmeet; Fawzi, Alhussein (2023-12-14). "Mathematical discoveries from program search with large language models". Nature. 625 (7995): 468–475. doi: 10.1038/s41586-023-06924-6 . ISSN   1476-4687. PMC   10794145 . PMID   38096900.
  12. ↑ 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.
  13. ↑ 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.
  14. ↑ 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 .
  15. ↑ 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.
  16. ↑ "What is difficult about the cap-set problem?". Gowers's Weblog. 2011-01-11. Retrieved 2016-11-26.
  17. 1 2 Tao, Terence (2007-02-23). "Open question: best bounds for cap sets". What's new. Retrieved 2016-11-26.
  18. ↑ "An exponential upper bound for the cap-set problem", Editorial, Discrete Analysis , June 5, 2016.
  19. ↑ Croot, Ernie; Lev, Vsevolod; Pach, Peter (2017), "Progression-free sets in are exponentially small", Annals of Mathematics, 185 (1): 331–337, arXiv: 1605.01506 , Bibcode:2016arXiv160501506C, doi:10.4007/annals.2017.185.1.7 .
  20. ↑ Ellenberg, Jordan S.; Gijswijt, Dion (2017), "On large subsets of 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
  21. ↑ Dahmen, Sander R.; Hölzl, Johannes; Lewis, Robert Y. (2019), "Formalizing the solution to the cap set problem", in Harrison, John; O'Leary, John; Tolmach, Andrew (eds.), 10th International Conference on Interactive Theorem Proving, ITP 2019, September 9-12, 2019, Portland, OR, USA, LIPIcs, vol. 141, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 15:1–15:19, arXiv: 1907.01449 , doi: 10.4230/LIPIcs.ITP.2019.15
  22. ↑ Jiang, Zhi (2021), Explicit Upper Bounds for the Cap Set Problem, arXiv: 2103.06481
  23. ↑ Follett, Michael; Kalail, Kyle; McMahon, Elizabeth; Pelland, Catherine; Won, Robert (2014), "Partitions of into maximal caps", Discrete Mathematics , 337: 1–8, arXiv: 1302.4703 , doi: 10.1016/j.disc.2014.08.002 , MR   3262358
  24. ↑ Hartnett, Kevin (21 October 2019). "Mathematicians Begin to Tame Wild 'Sunflower' Problem". Quanta Magazine. Retrieved 2019-10-22.
  25. ↑ Kalai, Gil (May 17, 2016), "Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven", Combinatorics and more.
  26. ↑ 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 .
  27. ↑ Hill, Raymond (1978), "Caps and codes", Discrete Mathematics , 22 (2): 111–137, doi: 10.1016/0012-365X(78)90120-6 , MR   0523299 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.