Hubbry Logo
Cap setCap setMain
Open search
Cap set
Community hub
Cap set
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Cap set
Cap set
Cap set
View on Wikipedia
from Wikipedia
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).

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

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

[edit]

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

[edit]

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

[edit]

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

[edit]

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

[edit]

Sunflower conjecture

[edit]
Main article: Sunflower (mathematics)

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

[edit]

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

Strongly regular graphs

[edit]
Main article: 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).[27]

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Cap set

View on Grokipedia
from Grokipedia
In , a cap set is a of the nn-dimensional F3n\mathbb{F}_3^n over the with three elements such that no three distinct points are collinear, or equivalently, no three distinct elements x,y,z∈F3nx, y, z \in \mathbb{F}_3^n satisfy x+y+z=0x + y + z = 0. This condition ensures the set avoids three-term arithmetic progressions, a core prohibition in the structure. The cap set problem seeks to determine the maximum cardinality of such a set, denoted r3(n)r_3(n), and has been a cornerstone of additive combinatorics since its origins in the as an extension of on arithmetic progressions in the integers. Early bounds, such as Meshulam's 1995 result showing r3(n)=O(3n/n)r_3(n) = O(3^n / n), highlighted the challenge of obtaining strong upper limits in finite fields. A major breakthrough came in 2016 with the work of Ellenberg and Gijswijt, who used the polynomial method to prove r3(n)=O(2.756n)r_3(n) = O(2.756^n), asymptotically improving prior upper estimates. Lower bounds have also advanced, with constructions yielding sets of size at least approximately 2.22n2.22^n for large nn, including improvements to about 2.2208n2.2208^n in 2023 using AI-assisted methods like FunSearch, as shown in recent combinatorial analyses. Beyond pure theory, cap sets connect to practical domains: in , they inform constructions of error-correcting codes with certain distance properties, while in finite geometry, they relate to blocking sets and designs in affine spaces. Notably, the problem models the SET, where the 81-card deck corresponds to F34\mathbb{F}_3^4, and a "set" of three cards forms a line (i.e., sums to zero), making a maximal cap set a largest collection without such a triple—known to have size 20. Ongoing explores generalizations to other fields Fq\mathbb{F}_q and dimensions, with recent 2023–2024 advances tightening bounds via algebraic and probabilistic techniques.

Fundamentals

Definition

The finite field Z/3Z\mathbb{Z}/3\mathbb{Z}, often denoted F3\mathbb{F}_3, consists of the elements {0,1,2}\{0, 1, 2\} under and multiplication 3, forming the ground field for the relevant . The space (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n is the nn-dimensional over this field, comprising all nn-tuples with entries from {0,1,2}\{0, 1, 2\} and componentwise operations, which has total cardinality 3n3^n. A cap set in (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n is defined as a SS containing no three distinct elements x,y,z∈Sx, y, z \in S such that x+z=2yx + z = 2y, where addition is componentwise 3; this prohibits three-term arithmetic progressions within SS. Equivalently, no three distinct elements of SS sum to the zero vector, i.e., x+y+z=0x + y + z = 0. This algebraic condition aligns with the geometric notion that no affine line in the space AG(n,3)(n,3) contains exactly three points from SS. The maximum of a cap set in (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n is denoted r3(n)r_3(n). Trivial examples of cap sets include the , any singleton, and any pair of distinct points, as these contain fewer than three elements and thus satisfy the no-three-in-progression property vacuously.

Geometric Interpretation

In over the GF(3), denoted AG(n,3), the ambient space consists of the (GF(3))^n, where points are identified with vectors having coordinates in {0,1,2}. Lines in this geometry are defined parametrically as the sets {a + t b | t ∈ GF(3)}, where a ∈ (GF(3))^n is a fixed point and b ∈ (GF(3))^n \ {0} is a direction vector; each such line contains exactly three points due to the field's order. This endows AG(n,3) with a rich framework, where the total number of points is 3^n, and lines capture the affine dependencies inherent to the . A set in AG(n,3) is geometrically interpreted as a of points that intersects every line in at most two points, ensuring no three points are collinear. This property positions cap sets as "caps" in the finite geometric sense, analogous to caps in projective geometries over finite fields, but adapted to the affine setting over GF(3), where the absence of a at emphasizes translational symmetries. Unlike blocking sets, which are designed to intersect every line at least once, cap sets prioritize avoiding full lines entirely, highlighting a complementary extremal role in . Similarly, while ovals in projective planes represent maximal point sets with no three collinear (achieving size q+1 in PG(2,q) for q odd), cap sets extend this concept to higher-dimensional affine spaces, focusing on maximality under the no-three-collinear constraint. The structure of AG(n,3) directly informs the geometric notion of : three distinct points x, y, z ∈ (GF(3))^n are collinear if and only if they satisfy the equation 2y = x + z (equivalently, x + y + z = 0 in GF(3), since multiplication by 2 corresponds to the condition in characteristic 3). This equation arises because lines are precisely the cosets of one-dimensional subspaces, and the three points on a line sum to zero 3, reflecting the field's additive group properties. The term "cap set" originates from studies in finite geometry dating to the mid-20th century, with foundational work by Beniamino Segre in 1955 on projective caps, and further development in the 1960s by and collaborators on related extremal problems in finite fields and combinatorial geometry.

Examples and Constructions

Small-Dimensional Examples

In dimension 1, the space (Z/3Z)1(\mathbb{Z}/3\mathbb{Z})^1 consists of three points: 0, 1, and 2, which form a single line since their sum is 0 3. Thus, the maximum cap set has size 2, for example the set {0,1}\{0, 1\} or {1,2}\{1, 2\}, as adding the third point creates a line. In dimension 2, the AG(2,3) can be visualized as a 3×3 toroidal grid, where lines include rows, columns, and diagonals that wrap around the edges (totaling 12 lines, each with 3 points). The maximum cap set has size 4; one explicit example is the set of "corner" points {(0,0),(0,2),(2,0),(2,2)}\{(0,0), (0,2), (2,0), (2,2)\}. To verify it is a , note that the sum of any three distinct points is nonzero modulo 3—for instance, (0,0)+(0,2)+(2,0)=(2,2)≢(0,0)(0,0) + (0,2) + (2,0) = (2,2) \not\equiv (0,0), and similarly for the other triples. This configuration avoids three points on any row, column, or wrapped diagonal. All maximal caps of size 4 in this space are affinely equivalent, meaning they can be transformed into one another via affine transformations. In dimension 3, the space (Z/3Z)3(\mathbb{Z}/3\mathbb{Z})^3 has 27 points. The maximum cap set has size 9; a standard construction is the "Heisenberg cap" given by the quadratic surface {(x,y,z)∣z=xy(mod3), x,y∈{0,1,2}}\{(x,y,z) \mid z = xy \pmod{3}, \, x,y \in \{0,1,2\}\}, which yields the points (0,0,0)(0,0,0), (0,1,0)(0,1,0), (0,2,0)(0,2,0), (1,0,0)(1,0,0), (1,1,1)(1,1,1), (1,2,2)(1,2,2), (2,0,0)(2,0,0), (2,1,2)(2,1,2), (2,2,1)(2,2,1). This set contains no three collinear points, as verified by exhaustive checking that no three sum to the zero vector modulo 3. It can be interpreted geometrically as a curved surface avoiding lines in the 3-dimensional affine space.

Explicit Constructions

Explicit constructions of large cap sets in (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n have been developed using algebraic and recursive techniques, providing lower bounds on the maximum size r3(n)r_3(n). One fundamental method is the construction, where if A⊆(Z/3Z)kA \subseteq (\mathbb{Z}/3\mathbb{Z})^k and B⊆(Z/3Z)mB \subseteq (\mathbb{Z}/3\mathbb{Z})^m are cap sets, then their A×B⊆(Z/3Z)k+mA \times B \subseteq (\mathbb{Z}/3\mathbb{Z})^{k+m} is also a cap set of size ∣A∣⋅∣B∣|A| \cdot |B|. This follows because if three points (a1,b1)(a_1, b_1), (a2,b2)(a_2, b_2), (a3,b3)(a_3, b_3) in A×BA \times B form a line, then the projections a1,a2,a3a_1, a_2, a_3 form a line in AA and b1,b2,b3b_1, b_2, b_3 in BB, contradicting the assumption that AA and BB are caps. Iterating this product over known small-dimensional caps yields larger caps in higher dimensions, though the growth rate depends on the base sizes. A classic algebraic construction in dimension 3 is the quadratic cap S={(x,y,xy)∣x,y∈Z/3Z}S = \{(x, y, xy) \mid x, y \in \mathbb{Z}/3\mathbb{Z}\}, which has size 9 and contains no three points in line. This set can be verified by direct enumeration, as the affine geometry AG(3,3) has only 27 points, and checking all potential lines shows no three lie in SS. Generalizations to higher dimensions use polynomial maps, such as embedding via quadratic or higher-degree forms over F3\mathbb{F}_3, to construct caps avoiding lines while maintaining substantial size, though these often require additional constraints to ensure no three-term progressions. Edel's construction provides a significant lower bound using iterated products of "admissible sets," which are collections of slices (affine hyperplanes) that form caps when combined. For dimensions of the form n=3kn = 3^k, this yields caps of size roughly 2.2n2.2^n, specifically improving to at least (2.217389)no(1)(2.217389)^n o(1) in general nn. The method involves building from small admissible sets, such as those of size 9 in dimension 3 and 20 in dimension 6, and recursively extending via products that preserve the no-three-in-line property. Recent refinements, using computational searches for larger admissible sets verified via SAT solvers, have slightly improved this to (2.218021)n(2.218021)^n in dimensions up to 56,232. A further improvement in 2023, using automated program search with large language models, raised the lower bound to approximately 2.2184n2.2184^n. Meshulam's 1995 result, while primarily an upper bound of O(3n/n)O(3^n / n), inspired inductive techniques for lower bounds through combinatorial arguments that can be adapted for constructions via increments. Improvements using exponential sums, as in related works, have explored regimes where lower bounds approach 2.75n2.75^n asymptotically, though these are not yet explicit for all nn. To verify that a proposed avoids three-in-line configurations, generating functions can be employed to count the number of lines intersecting the set. Specifically, inclusion-exclusion over potential lines can bound the intersection sizes to zero. For larger constructions like Edel's, computational tools such as SAT solvers encode the no-line condition as CNF clauses on admissible slices, confirming the cap property exhaustively.

Bounds on Maximum Size

Upper Bounds

Early efforts to establish upper bounds on the size of cap sets, denoted r_3(n), focused on basic combinatorial arguments. These classical results provided the first subexponential bounds relative to the trivial r_3(n) ≤ 3^n. In 1987, Frankl, Graham, and showed using methods that r_3(n) = o(3^n), proving cap sets have zero asymptotic density. A further advance came in 1995 with Meshulam's result r_3(n) = O(3^n / n) using . This was refined in 2012 by Bateman and Katz to O(3^n / n^{1+\epsilon}) for some \epsilon > 0. The major breakthrough occurred in 2016 when Ellenberg and Gijswijt applied the polynomial method to obtain r_3(n) = o(2.756^n). Their approach relies on the observation that the of a cap set vanishes on certain high-degree polynomials, limiting the of the space of polynomials of degree at most d that vanish on the cap, thereby bounding its size. This result dramatically improved upon previous bounds and resolved long-standing conjectures about the subexponential growth of r_3(n). Tao reformulated the Ellenberg-Gijswijt argument using the slice rank method in the same year, providing an alternative perspective through tensor analysis. For a cap set S ⊆ (ℤ/3ℤ)^n, the 1_S can be viewed as a 3-way tensor, and its slice rank is at most |S|. Since the slice rank of the tensor corresponding to x + y + z = 0 is bounded, this implies |S| ≤ 3^{n(1 - 1/d)} for polynomials of degree d. This tensor-based view has facilitated extensions to other problems in additive combinatorics. Prior to 2016, the best upper bounds came from Fourier analytic methods, such as Bateman and Katz's (2012) O(3^n / n^{1+\epsilon}). No significant improvements to the Ellenberg-Gijswijt bound have been made since.

Lower Bounds

The maximum size of a cap set in (F3)n(\mathbb{F}_3)^n, denoted r3(n)r_3(n), satisfies the trivial lower bound r3(n)≥2nr_3(n) \geq 2^n. This follows from the explicit construction consisting of all vectors with coordinates in {0,1}\{0,1\}, which forms a cap set because no three distinct such vectors sum to the zero vector modulo 3: in each coordinate, the possible sums are 0, 1, 2, or 3 (equivalent to 0 modulo 3), but achieving 0 modulo 3 in every coordinate would require the three vectors to agree in every position, contradicting distinctness. For small n, exact values provide stronger lower bounds that match the maximum: r3(1)=2r_3(1) = 2, r3(2)=4r_3(2) = 4, r3(3)=9r_3(3) = 9, r3(4)=20r_3(4) = 20, r3(5)=45r_3(5) = 45, and r3(6)=112r_3(6) = 112. These were established through exhaustive computational searches and classifications of maximal caps in low dimensions. For larger n, recursive product constructions yield asymptotic lower bounds superior to 2n2^n. In 2004, Edel introduced a generalized product method that produces cap sets of size at least (2.217147)n(2.217147)^n for sufficiently large n, improving on prior recursive techniques by optimizing the base cases and recursion parameters. This bound stood as the best known for nearly two decades until a 2023 refinement by Tyrrell, building on Edel's approach with enhanced computational searches for base constructions in dimensions up to 396 and theoretical optimizations, established r3(n)≥(2.218021)nr_3(n) \geq (2.218021)^n. Subsequent improvements include Romera-Paredes et al. (2023) achieving approximately 2.220n2.220^n using large language models for program search in admissible set constructions, and Naslund (2024) further to approximately 2.2208n2.2208^n. Non-constructive methods, such as the probabilistic deletion technique applied to random subsets, can guarantee existence of cap sets larger than 2n2^n but yield weaker asymptotics than the above explicit constructions, typically on the order of c⋅2nc \cdot 2^n for some c > 1 depending on the probability parameters. The current lower bounds lag behind the best upper bounds of o(2.756^n), a gap narrowed significantly by the breakthrough using the polynomial method, though the optimal growth rate remains open.

Partitioning and Extensions

Mutually Disjoint Cap Sets

A partition of the vector space (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n into kk disjoint cap sets is a decomposition of the entire space into kk subsets, each of which is a cap (i.e., contains no three points in arithmetic progression). The minimal such kk is known as the cap set covering number, denoted here as χ((Z/3Z)n)\chi((\mathbb{Z}/3\mathbb{Z})^n), representing the smallest number of cap sets needed to partition the space. This number provides a measure of how efficiently the space can be decomposed into line-free subsets and is closely related to the chromatic number of the 3-uniform hypergraph on (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n where the hyperedges are the 3-term arithmetic progressions; a proper coloring of this hypergraph corresponds to a partition into cap sets, with no monochromatic progression. This connection echoes Roth's theorem on arithmetic progressions in the integers, where the density of progression-free sets is analyzed, but here it quantifies the global decomposition rather than individual subset sizes. For small dimensions, explicit partitions are known and illustrate the covering number. In dimension n=2n=2, the space (Z/3Z)2(\mathbb{Z}/3\mathbb{Z})^2 has 9 points, and the maximum cap size is 4. It can be partitioned into two disjoint maximal caps of size 4 each, leaving a single point (which is trivially a cap), so the covering number is 3. In dimension n=3n=3, the space has 27 points, with maximum cap size 9, and it admits a partition into three disjoint maximal caps of size 9. In dimension n=4n=4, the space has 81 points, with maximum cap size 20; a partition exists into four disjoint maximal caps of size 20 each, plus one anchor point, yielding a covering number of 5. These constructions highlight that perfect partitions (without leftovers) are not always possible, but the anchor point ensures the decomposition covers the space using caps. In general, the cap set covering number satisfies χ((Z/3Z)n)≥3n/r3(n)\chi((\mathbb{Z}/3\mathbb{Z})^n) \geq 3^n / r_3(n), where r3(n)r_3(n) is the size of the largest cap in (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n. Seminal upper bounds on r3(n)r_3(n) imply exponential growth in this lower bound; for instance, the classical construction using subsets with coordinates in {0,1}\{0,1\} gives r3(n)≥2nr_3(n) \geq 2^n, so χ((Z/3Z)n)≥(3/2)n\chi((\mathbb{Z}/3\mathbb{Z})^n) \geq (3/2)^n. A breakthrough result shows r3(n)=O(2.756n)r_3(n) = O(2.756^n), yielding χ((Z/3Z)n)≥Ω(1.088n)\chi((\mathbb{Z}/3\mathbb{Z})^n) \geq \Omega(1.088^n). Upper bounds on the covering number remain larger; trivial partitions into singletons give χ((Z/3Z)n)≤3n\chi((\mathbb{Z}/3\mathbb{Z})^n) \leq 3^n, but constructive decompositions using known caps suggest improvements, though optimal values for large nn are open.

Product and Tensor Constructions

Product constructions play a central role in building large cap sets by combining smaller ones across dimensions, often with restrictions to preserve the no-three-in-line property. The direct of two cap sets may introduce arithmetic progressions spanning both components, but refined versions using slice restrictions or admissible index sets avoid this issue. For instance, given a cap set A⊆(Z/3Z)kA \subseteq (\mathbb{Z}/3\mathbb{Z})^k and an admissible set S⊆{0,1,2}mS \subseteq \{0,1,2\}^m—a subset where no three elements sum to zero 3—one can form the set ⋃s∈S(A+es)\bigcup_{s \in S} (A + e_s), where ese_s embeds ss into the higher , yielding a cap set of size ∣A∣⋅∣S∣|A| \cdot |S| in (Z/3Z)k+m(\mathbb{Z}/3\mathbb{Z})^{k+m}. This approach ensures lines are either contained within a single slice or blocked by the admissibility of SS. Recursive applications of such product constructions enable significant improvements to lower bounds on cap set sizes. By iteratively combining optimal low-dimensional caps with carefully chosen admissible sets, one obtains explicit cap sets with asymptotic density exceeding 2n2^n. A notable example is the extended product method, which uses extendable collections of caps across coordinates to construct a cap set in dimension 396 of size (117)⋅64⋅124⋅11262\binom{11}{7} \cdot 6^4 \cdot 12^4 \cdot 112^{62}, establishing a lower bound of approximately 2.218n2.218^n. Further recursion yields even larger examples, such as in dimension 56232 with size (117)141⋅6572⋅12572⋅1128800⋅37⋅142\binom{11}{7}^{141} \cdot 6^{572} \cdot 12^{572} \cdot 112^{8800} \cdot 37 \cdot 142, improving the bound to 2.218021n2.218021^n. These constructions generalize earlier recursive techniques and represent the first major asymptotic advances since 2004. A simple algebraic construction provides a baseline cap set of size exactly 2n2^n: the subset of all vectors in (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n with coordinates restricted to {0,1}\{0,1\}. This set avoids three-term arithmetic progressions because the sum of any three distinct such vectors cannot be zero modulo 3 without forcing identical entries in every coordinate, violating distinctness. This construction connects to , where cap sets correspond to ternary constant-weight codes over GF(3) with forbidden configurations equivalent to no three codewords satisfying x+y+z=0x + y + z = 0 for distinct x,y,zx, y, z. More advanced algebraic methods, drawing from generalized Reed-Muller codes over GF(3), inspire recursive tensor-like builds by evaluating low-degree polynomials to define subsets free of lines, though explicit sizes often rely on the product framework above. Multidimensional product constructions extend these ideas to (Z/3Z)nk(\mathbb{Z}/3\mathbb{Z})^{nk} by taking kk-fold products with adjustments, such as projecting onto subspaces or using orthogonal slices to prevent progressions across multiple factors. For example, combining caps in base dimension nn via admissible multi-indices yields sizes scaling as ∣A∣k|A|^k under suitable restrictions. The cap set problem generalizes to (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^n for primes p>3p > 3, where similar product and algebraic techniques apply, though the focus remains on p=3p=3 due to its ties to the original problem; recent results confirm asymptotic densities below pn(1−ϵ)p^{n(1 - \epsilon)} for some ϵ>0\epsilon > 0. In 2023, machine learning-aided searches discovered improved low-dimensional caps (e.g., size 512 in dimension 8), which, via recursive products, boosted the best known lower bound to over 2.2202n2.2202^n. A survey summarizes further progress on these bounds and constructions.

Applications

Sunflower Conjecture

A sunflower, also known as a Δ-system, is a collection of r distinct sets S1, ..., Sr such that the Si ∩ Sj is the same set C (called the core) for all i ≠ j; the sets Si \ C are called the petals and are pairwise disjoint. The Erdős–Rado sunflower conjecture states that for any integers r ≥ 3 and k ≥ 1, every k-uniform family of more than (r−1)k sets contains an r-sunflower. Cap sets provide key insights into this conjecture, especially for r=3, by establishing upper bounds on the size of sunflower-free families through connections to additive combinatorics in (ℤ/3ℤ)n. The cap set lemma links these structures: in the vector space (ℤ/3ℤ)n, a subset without three elements x, y, z satisfying x + y + z = 0 (a cap set) corresponds to a family where no three vectors form a 3-sunflower, as a sunflower would require coordinates where the values are either all equal (in the core) or all distinct (summing to 0 mod 3). Thus, the maximum size of a 3-sunflower-free family embeds into the cap set size r3(n), implying uniform intersection theorems that prevent large sunflowers in certain k-uniform families over universes of size related to n. In particular, the sunflower number τ(k,r) (the maximum size of an r-sunflower-free k-uniform family) satisfies τ(k,3) ≤ r3(n) for n = O(k). In the 1990s, Zoltán Füredi utilized upper bounds on cap set sizes (then around 2.217n) to derive improved estimates for sunflower-free families, showing that the growth rate constant ck in the Erdős–Szemerédi variant (maximum 3-sunflower-free family over [n] has size at most ckn) satisfies ck < 2.2 for large k. The 2016 breakthrough by Jordan Ellenberg and Dion Gijswijt, using the slice-rank polynomial method, established that r3(n) ≤ 2.755n, which directly implies ck ≤ 1.938 for the Erdős–Szemerédi sunflower , proving that any 3-sunflower-free family of subsets of [n] has size at most (1.938)n and confirming the existence of 3-sunflowers in sufficiently large triple systems via cap set obstructions. Subsequent work by Eric Naslund and Will Sawin applied slice rank directly to sunflower families, yielding even tighter bounds like ck ≤ 1.89.

Matrix Multiplication Algorithms

Cap sets contribute to faster matrix multiplication algorithms by providing structured tensor decompositions in the group-theoretic framework developed by Cohn and Umans. In this approach, the operation, viewed as a between pairs of n×nn \times n matrices over a field, is embedded into the group algebra C[G]\mathbb{C}[G] of a finite GG, such as (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n. The multiplication tensor, a 3-linear form in (n2)3(n^2)^3 space, is then decomposed using the irreducible representations (characters) of GG, yielding an whose depends on the dimensions of these representations and the growth rate of ∣G∣|G|. For groups of exponent 3, the key combinatorial object is a tricolored cap set—a triple of subsets (S,T,U)⊆(Z/3Z)n(S, T, U) \subseteq (\mathbb{Z}/3\mathbb{Z})^n with no elements x∈Sx \in S, y∈Ty \in T, z∈Uz \in U satisfying x+y+z=0x + y + z = 0. Such a cap set enables a decomposition of the tensor into ∣S∣⋅∣T∣⋅∣U∣|S| \cdot |T| \cdot |U| rank-1 bilinear maps, where the no-three-in-line condition prevents "collisions" that would introduce extraneous terms or increase the rank during . Assuming balanced sizes ∣S∣=∣T∣=∣U∣=δ⋅3n|S| = |T| = |U| = \delta \cdot 3^n, this yields matrix multiplication in O(nω)O(n^\omega) time with ω=3log⁡33/log⁡3(3/δ)\omega = 3 \log_3 3 / \log_3 (3 / \delta), which is strictly less than 3 for δ>1/3\delta > 1/3. Recent AI-assisted constructions from 2023 have improved lower bounds on cap set sizes to approximately 2.22n2.22^n, enabling refined tensor decompositions that push toward ω<2.37\omega < 2.37. This method connects to the Coppersmith-Winograd tensor approach, which seeks low-rank approximations of the matrix multiplication tensor via powers of a base tensor over finite fields like GF(3)\mathrm{GF}(3). Cap sets in (GF(3))n(\mathrm{GF}(3))^n supply explicit structured approximations by embedding the tensor slices into sum-free supports, avoiding low-rank dependencies that plague unstructured decompositions and achieving exponents like ω≈2.373\omega \approx 2.373 from known cap set constructions of size roughly 2.2n2.2^n. Advances in the 2010s, building on the Ellenberg-Gijswijt upper bound of O(2.755n)O(2.755^n) for cap set sizes via the polynomial method, have refined this framework by extending the bound to tricolored sum-free sets. This adaptation improves analysis of tensor slicing in the group-theoretic method, demonstrating that abelian groups of bounded exponent cannot yield ω=2\omega = 2, but confirming potential for ω<2.4\omega < 2.4 with existing constructions while highlighting the need for better explicit cap sets to push closer to 2. The bound thus establishes theoretical limits on the approach, reducing the naive exponent of 3 to values informed by cap set geometry.

Strongly Regular Graphs

A strongly regular graph is a connected, regular graph of degree kk on vv vertices such that every pair of adjacent vertices has exactly λ\lambda common neighbors, and every pair of non-adjacent vertices has exactly μ\mu common neighbors, where the graph is neither complete nor null. Cap sets provide constructions of strongly regular graphs through geometric and coding-theoretic methods in finite affine and projective spaces over F3\mathbb{F}_3. One prominent construction uses a cap SS in the projective space PG(n−1,3)\mathrm{PG}(n-1, 3) to define edges in the affine space AG(n,3)\mathrm{AG}(n, 3). The vertices of the graph are the 3n3^n points of AG(n,3)\mathrm{AG}(n, 3), and two distinct points u,vu, v are adjacent if the projective point corresponding to the direction of the vector v−uv - u (i.e., the equivalence class under scalar multiplication by nonzero elements of F3\mathbb{F}_3) lies in SS. Since there are q−1=2q-1 = 2 nonzero scalars in F3\mathbb{F}_3, the degree is k=2∣S∣k = 2 |S|. For the graph to be strongly regular, SS must satisfy specific intersection properties with subspaces, ensuring constant numbers of common neighbors; such caps often arise from quadratic hypersurfaces or other algebraic varieties. The eigenvalues of the graph derive from the association scheme structure of the translation group acting on AG(n,3)\mathrm{AG}(n, 3), with the adjacency eigenvalues determined by the character sums over SS. A notable example is the Games graph, constructed using a unique 56-point cap in PG(5,3)\mathrm{PG}(5, 3), yielding a strongly regular graph with parameters (v,k,λ,μ)=(729,112,1,20)(v, k, \lambda, \mu) = (729, 112, 1, 20) on the points of AG(6,3)\mathrm{AG}(6, 3). This graph is distance-regular with intersection array {112,110;1,20}\{112, 110; 1, 20\} and spectrum 11214616(−23)112112^1 4^{616} (-23)^{112}, and it belongs to the family of conference graphs related to lattice constructions from caps. Smaller examples include graphs from quadratic caps in lower dimensions; for instance, the maximum 9-point cap in AG(3,3)\mathrm{AG}(3, 3) admits a field model over F9≅F32×{basis}\mathbb{F}_9 \cong \mathbb{F}_3^2 \times \{\text{basis}\}, inducing the Paley graph of order 9 with parameters (9,4,1,2)(9, 4, 1, 2), where edges connect elements whose difference is a quadratic residue in F9\mathbb{F}_9. In general, parameters of these graphs are tied to the cap size r3(n)r_3(n), with v=3nv = 3^n, k=2r3(n−1)k = 2 r_3(n-1), and λ,μ\lambda, \mu computed from the cap's intersection properties with lines and planes. These constructions originated in the 1970s within finite geometry, particularly through explorations of caps yielding optimal codes and symmetric designs. Seminal work established the link between caps with two hyperplane intersection sizes, projective two-weight ternary codes (e.g., weights derived as 3d−mi3^d - m_i for code dimension dd and intersections mim_i), and the corresponding strongly regular graphs via Delsarte's correspondence, where the graph on the ambient space has eigenvalues r=3m1−∣S∣r = 3 m_1 - |S| and s=3m2−∣S∣s = 3 m_2 - |S|. Quadratic caps, defined as intersections of quadrics avoiding three collinear points, frequently produce such graphs with integral eigenvalues and high symmetry, often appearing in association schemes from classical groups acting on the space.

Additive Combinatorics

Cap sets in the affine space An(F3)\mathbb{A}^n(\mathbb{F}_3), or equivalently in the abelian group (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n, are subsets with no three points in arithmetic progression, making them a finite-field analogue of progression-free sets in the integers. Roth's theorem, which asserts that any subset of the integers with positive upper density contains a three-term arithmetic progression, has a direct counterpart in this setting: any 3-AP-free subset A⊆(Z/3Z)nA \subseteq (\mathbb{Z}/3\mathbb{Z})^n satisfies ∣A∣=o(3n)|A| = o(3^n) as n→∞n \to \infty. This result, proved by Meshulam using Fourier analysis over F3\mathbb{F}_3, establishes that cap sets achieve the maximal possible size among such progression-free sets, providing the best-known lower bound for the density of 3-AP-free subsets in (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n. Constructions of large cap sets serve as explicit examples of dense 3-AP-free sets, offering improvements to the quantitative bounds in Szemerédi's theorem within finite fields. Traditional random methods or product constructions yield cap sets of size roughly 3n(1−c/log⁡n)3^{n(1 - c/\log n)}, but more sophisticated Behrend-type constructions, adapted to Fqn\mathbb{F}_q^n, produce denser progression-free sets by exploiting spherical or geometric configurations to avoid progressions. For instance, these methods achieve sizes exponential in nn times a subpolynomial factor better than earlier bounds, enhancing the lower bounds for the maximum size of kk-AP-free subsets in Fqn\mathbb{F}_q^n for fixed k≥3k \geq 3. The absence of three-term progressions in a cap set S⊆(Z/3Z)nS \subseteq (\mathbb{Z}/3\mathbb{Z})^n implies strong growth properties for its sumset S+SS + S. Specifically, ∣S+S∣≥min⁡(3n,c∣S∣3/2)|S + S| \geq \min(3^n, c |S|^{3/2}) for some absolute constant c>0c > 0, reflecting the imposed by progression-freeness in groups of exponent 3. This bound arises from additive energy estimates and the fact that small sumsets would force arithmetic progressions via Plünnecke-Ruzsa inequalities adapted to progression-free sets. Varnavides' theorem, a density increment argument extending , applies directly to cap sets: any sufficiently dense subset of (Z/3Z)n(\mathbb{Z}/3\mathbb{Z})^n contains many translates of a large cap set. This connection ties into Gowers uniformity norms over F3\mathbb{F}_3, where sets with small U2U^2-norm exhibit pseudorandom behavior and thus many structured subsets like caps, facilitating proofs of multidimensional progression theorems in finite fields. Recent developments since 2022 have extended cap set techniques to groups with higher torsion, such as (Z/9Z)n(\mathbb{Z}/9\mathbb{Z})^n, exploring quasirandom subsets without generalized progressions and yielding improved bounds. Additionally, post-2016 advances using the polynomial method from the cap set breakthrough have resolved potential counterexamples to the polynomial Hales-Jewett theorem, linking combinatorial line avoidance in {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}}^n to tensor rank bounds and uniformity in higher dimensions.

References

  1. https://arxiv.org/pdf/1605.09223
  2. https://arxiv.org/pdf/2408.02328
  3. https://arxiv.org/pdf/2209.10045
  4. https://www.nature.com/articles/s41586-023-06924-6
  5. https://repository.tudelft.nl/file/File_03ab6991-f67e-48c7-87cd-bf4f2a0237d4
  6. http://www.math.uchicago.edu/~may/VIGRE/VIGRE2008/REUPapers/McCullagh.pdf
  7. https://annals.math.princeton.edu/wp-content/uploads/annals-v185-n1-p08-p.pdf
  8. https://arxiv.org/abs/2408.02328
  9. https://math.uchicago.edu/~may/REU2021/REUPapers/Carney.pdf
  10. https://anuragbishnoi.wordpress.com/wp-content/uploads/2017/10/bms_bgs17.pdf
  11. https://arxiv.org/pdf/1302.4703
  12. http://www.yvesedel.de/Papers/CapSurvey.pdf
  13. https://math.haifa.ac.il/seva/Papers/CapsetSurvey.pdf
  14. http://www.mathi.uni-heidelberg.de/~yves/Matritzen/CAPs/Is/Iindex.html
  15. https://doi.org/10.1016/0097-3165(95)90012-9
  16. https://doi.org/10.1090/S0894-0347-2011-00727-5
  17. https://www.sciencedirect.com/science/article/pii/009731658790118X
  18. https://arxiv.org/abs/2209.10045
  19. https://link.springer.com/article/10.1007/s10623-020-00769-0
  20. https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/
  21. https://doi.org/10.1016/j.disc.2014.08.002
  22. https://doi.org/10.1090/bull/1648
  23. https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/
  24. https://arxiv.org/abs/1606.09575
  25. https://arxiv.org/abs/1605.09223
  26. https://homepages.cwi.nl/~lex/files/ESsunflowerconjectureCarla.pdf
  27. https://arxiv.org/abs/math/0307321
  28. https://arxiv.org/abs/1605.06702
  29. https://arxiv.org/abs/math/0511460
  30. https://mathworld.wolfram.com/GamesGraph.html
  31. https://aeb.win.tue.nl/preprints/2wt.pdf
  32. https://core.ac.uk/download/pdf/301667654.pdf
  33. https://www.juliawolf.org/research/preprints/kbehrendweb.pdf
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.