Fact-checked by Grok 2 weeks ago

Cap set

In mathematics, a cap set is a subset of the n-dimensional affine space \mathbb{F}_3^n over the finite field with three elements such that no three distinct points are collinear, or equivalently, no three distinct elements x, y, z \in \mathbb{F}_3^n satisfy x + y + z = 0.^[1] This condition ensures the set avoids three-term arithmetic progressions, a core prohibition in the structure.^[1] The cap set problem seeks to determine the maximum cardinality of such a set, denoted r_3(n), and has been a cornerstone of additive combinatorics since its origins in the 1950s as an extension of Roth's theorem on arithmetic progressions in the integers.^[2] Early bounds, such as Meshulam's 1995 result showing r_3(n) = O(3^n / n), highlighted the challenge of obtaining strong upper limits in finite fields.^[2] A major breakthrough came in 2016 with the work of Ellenberg and Gijswijt, who used the polynomial method to prove r_3(n) = O(2.756^n), asymptotically improving prior upper estimates.^[1] Lower bounds have also advanced, with constructions yielding sets of size at least approximately $2.22^n for large n, including improvements to about $2.2208^n in 2023 using AI-assisted methods like FunSearch, as shown in recent combinatorial analyses.^[3]^[4] Beyond pure theory, cap sets connect to practical domains: in coding theory, 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.^[5] Notably, the problem models the card game SET, where the 81-card deck corresponds to \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.^[6] Ongoing research explores generalizations to other fields \mathbb{F}_q and dimensions, with recent 2023–2024 advances tightening bounds via algebraic and probabilistic techniques.^[2]

Fundamentals

Definition

The finite field \mathbb{Z}/3\mathbb{Z}, often denoted \mathbb{F}_3, consists of the elements \{0, 1, 2\} under addition and multiplication modulo 3, forming the ground field for the relevant vector space. The space (\mathbb{Z}/3\mathbb{Z})^n is the n-dimensional vector space over this field, comprising all n-tuples with entries from \{0, 1, 2\} and componentwise operations, which has total cardinality $3^n. A cap set in (\mathbb{Z}/3\mathbb{Z})^n is defined as a subset S containing no three distinct elements x, y, z \in S such that x + z = 2y, where addition is componentwise modulo 3; this prohibits three-term arithmetic progressions within S. ^[7] Equivalently, no three distinct elements of S sum to the zero vector, i.e., x + y + z = 0. ^[7] This algebraic condition aligns with the geometric notion that no affine line in the space AG(n,3) contains exactly three points from S. The maximum cardinality of a cap set in (\mathbb{Z}/3\mathbb{Z})^n is denoted r_3(n). ^[7] Trivial examples of cap sets include the empty set, 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 affine geometry over the finite field GF(3), denoted AG(n,3), the ambient space consists of the vector space (GF(3))^n, where points are identified with vectors having coordinates in {0,1,2}.^[8] 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.^[9] This structure endows AG(n,3) with a rich geometric framework, where the total number of points is 3^n, and lines capture the affine dependencies inherent to the vector space. A cap set in AG(n,3) is geometrically interpreted as a subset 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 hyperplane at infinity emphasizes translational symmetries.^[10] 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 incidence geometry. 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.^[10] The vector space structure of AG(n,3) directly informs the geometric notion of collinearity: 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 arithmetic progression condition in characteristic 3).^[8] This equation arises because lines are precisely the cosets of one-dimensional subspaces, and the three points on a line sum to zero modulo 3, reflecting the field's additive group properties.^[9] 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 Paul Erdős and collaborators on related extremal problems in finite fields and combinatorial geometry.^[10]^[8]

Examples and Constructions

Small-Dimensional Examples

In dimension 1, the space (\mathbb{Z}/3\mathbb{Z})^1 consists of three points: 0, 1, and 2, which form a single line since their sum is 0 modulo 3. Thus, the maximum cap set has size 2, for example the set \{0, 1\} or \{1, 2\}, as adding the third point creates a line.^[11] In dimension 2, the affine geometry 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)\}. To verify it is a cap, note that the sum of any three distinct points is nonzero modulo 3—for instance, (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.^[11]^[11] In dimension 3, the space (\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) \mid z = xy \pmod{3}, \, x,y \in \{0,1,2\}\}, which yields the points (0,0,0), (0,1,0), (0,2,0), (1,0,0), (1,1,1), (1,2,2), (2,0,0), (2,1,2), (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.^[12]

Explicit Constructions

Explicit constructions of large cap sets in (\mathbb{Z}/3\mathbb{Z})^n have been developed using algebraic and recursive techniques, providing lower bounds on the maximum size r_3(n). One fundamental method is the direct product construction, where if A \subseteq (\mathbb{Z}/3\mathbb{Z})^k and B \subseteq (\mathbb{Z}/3\mathbb{Z})^m are cap sets, then their direct product A \times B \subseteq (\mathbb{Z}/3\mathbb{Z})^{k+m} is also a cap set of size |A| \cdot |B|.^[3] This follows because if three points (a_1, b_1), (a_2, b_2), (a_3, b_3) in A \times B form a line, then the projections a_1, a_2, a_3 form a line in A and b_1, b_2, b_3 in B, contradicting the assumption that A and B are caps.^[3] 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) \mid x, y \in \mathbb{Z}/3\mathbb{Z}\}, which has size 9 and contains no three points in line.^[13] 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 S. Generalizations to higher dimensions use polynomial maps, such as embedding via quadratic or higher-degree forms over \mathbb{F}_3, to construct caps avoiding lines while maintaining substantial size, though these often require additional constraints to ensure no three-term progressions.^[13] 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 = 3^k, this yields caps of size roughly $2.2^n, specifically improving to at least (2.217389)^n o(1) in general n.^[14] 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 in dimensions up to 56,232.^[3] A further improvement in 2023, using automated program search with large language models, raised the lower bound to approximately $2.2184^n.^[4] Meshulam's 1995 result, while primarily an upper bound of O(3^n / n), inspired inductive techniques for lower bounds through combinatorial arguments that can be adapted for constructions via density increments.^[15] Improvements using exponential sums, as in related works, have explored regimes where lower bounds approach $2.75^n asymptotically, though these are not yet explicit for all n.^[16] To verify that a proposed construction 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.^[13] 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.^[3]

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 Rödl showed using hypergraph methods that r_3(n) = o(3^n), proving cap sets have zero asymptotic density.^[17] A further advance came in 1995 with Meshulam's result r_3(n) = O(3^n / n) using Fourier analysis. This was refined in 2012 by Bateman and Katz to O(3^n / n^{1+\epsilon}) for some \epsilon > 0.^[8] 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 indicator function of a cap set vanishes on certain high-degree polynomials, limiting the dimension 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 indicator function 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 the equation 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 (\mathbb{F}_3)^n, denoted r_3(n), satisfies the trivial lower bound r_3(n) \geq 2^n. This follows from the explicit construction consisting of all vectors with coordinates in \{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.^[18] For small n, exact values provide stronger lower bounds that match the maximum: r_3(1) = 2, r_3(2) = 4, r_3(3) = 9, r_3(4) = 20, r_3(5) = 45, and r_3(6) = 112. These were established through exhaustive computational searches and classifications of maximal caps in low dimensions.^[19] For larger n, recursive product constructions yield asymptotic lower bounds superior to $2^n. In 2004, Edel introduced a generalized product method that produces cap sets of size at least (2.217147)^n for sufficiently large n, improving on prior recursive techniques by optimizing the base cases and recursion parameters.^[12] 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 r_3(n) \geq (2.218021)^n.^[18] Subsequent improvements include Romera-Paredes et al. (2023) achieving approximately $2.220^n using large language models for program search in admissible set constructions, and Naslund (2024) further to approximately $2.2208^n.^[4] ^[8] Non-constructive methods, such as the probabilistic deletion technique applied to random subsets, can guarantee existence of cap sets larger than $2^n but yield weaker asymptotics than the above explicit constructions, typically on the order of c \cdot 2^n for some c > 1 depending on the probability parameters.^[20] The current lower bounds lag behind the best upper bounds of o(2.756^n), a gap narrowed significantly by the 2016 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 (\mathbb{Z}/3\mathbb{Z})^n into k disjoint cap sets is a decomposition of the entire space into k subsets, each of which is a cap (i.e., contains no three points in arithmetic progression). The minimal such k is known as the cap set covering number, denoted here as \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 (\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=2, the space (\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=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=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.^[21] In general, the cap set covering number satisfies \chi((\mathbb{Z}/3\mathbb{Z})^n) \geq 3^n / r_3(n), where r_3(n) is the size of the largest cap in (\mathbb{Z}/3\mathbb{Z})^n. Seminal upper bounds on r_3(n) imply exponential growth in this lower bound; for instance, the classical construction using subsets with coordinates in \{0,1\} gives r_3(n) \geq 2^n, so \chi((\mathbb{Z}/3\mathbb{Z})^n) \geq (3/2)^n. A breakthrough result shows r_3(n) = O(2.756^n), yielding \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 \chi((\mathbb{Z}/3\mathbb{Z})^n) \leq 3^n, but constructive decompositions using known caps suggest improvements, though optimal values for large n 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 Cartesian product 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 \subseteq (\mathbb{Z}/3\mathbb{Z})^k and an admissible set S \subseteq \{0,1,2\}^m—a subset where no three elements sum to zero modulo 3—one can form the set \bigcup_{s \in S} (A + e_s), where e_s embeds s into the higher dimension, yielding a cap set of size |A| \cdot |S| in (\mathbb{Z}/3\mathbb{Z})^{k+m}. This approach ensures lines are either contained within a single slice or blocked by the admissibility of S. 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 $2^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 \binom{11}{7} \cdot 6^4 \cdot 12^4 \cdot 112^{62}, establishing a lower bound of approximately $2.218^n. Further recursion yields even larger examples, such as in dimension 56232 with size \binom{11}{7}^{141} \cdot 6^{572} \cdot 12^{572} \cdot 112^{8800} \cdot 37 \cdot 142, improving the bound to $2.218021^n. These constructions generalize earlier recursive techniques and represent the first major asymptotic advances since 2004.^[18] A simple algebraic construction provides a baseline cap set of size exactly $2^n: the subset of all vectors in (\mathbb{Z}/3\mathbb{Z})^n with coordinates restricted to \{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 coding theory, where cap sets correspond to ternary constant-weight codes over GF(3) with forbidden configurations equivalent to no three codewords satisfying x + y + z = 0 for distinct x, 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.^[8] Multidimensional product constructions extend these ideas to (\mathbb{Z}/3\mathbb{Z})^{nk} by taking k-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 n via admissible multi-indices yields sizes scaling as |A|^k under suitable restrictions. The cap set problem generalizes to (\mathbb{Z}/p\mathbb{Z})^n for primes p > 3, where similar product and algebraic techniques apply, though the focus remains on p=3 due to its ties to the original problem; recent results confirm asymptotic densities below p^{n(1 - \epsilon)} for some \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.2202^n.^[8]^[4] A 2024 survey summarizes further progress on these bounds and constructions.^[8]

Applications

Sunflower Conjecture

A sunflower, also known as a Δ-system, is a collection of r distinct sets S₁, ..., S_r such that the intersection S_i ∩ S_j is the same set C (called the core) for all i ≠ j; the sets S_i \ 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ℤ)ⁿ.^[22] The cap set lemma links these structures: in the vector space (ℤ/3ℤ)ⁿ, 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 r₃(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) ≤ r₃(n) for n = O(k).^[23]^[22]^[24] In the 1990s, Zoltán Füredi utilized upper bounds on cap set sizes (then around 2.217ⁿ) to derive improved estimates for sunflower-free families, showing that the growth rate constant c_k in the Erdős–Szemerédi variant (maximum 3-sunflower-free family over [n] has size at most c_kⁿ) satisfies c_k < 2.2 for large k. The 2016 breakthrough by Jordan Ellenberg and Dion Gijswijt, using the slice-rank polynomial method, established that r₃(n) ≤ 2.755ⁿ, which directly implies c_k ≤ 1.938 for the Erdős–Szemerédi sunflower conjecture, proving that any 3-sunflower-free family of subsets of [n] has size at most (1.938)ⁿ 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 c_k ≤ 1.89.^[25]^[26]

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 matrix multiplication operation, viewed as a bilinear map between pairs of n \times n matrices over a field, is embedded into the group algebra \mathbb{C}[G] of a finite abelian group G, such as (\mathbb{Z}/3\mathbb{Z})^n. The multiplication tensor, a 3-linear form in (n^2)^3 space, is then decomposed using the irreducible representations (characters) of G, yielding an algorithm whose complexity depends on the dimensions of these representations and the growth rate of |G|.^[27] For groups of exponent 3, the key combinatorial object is a tricolored cap set—a triple of subsets (S, T, U) \subseteq (\mathbb{Z}/3\mathbb{Z})^n with no elements x \in S, y \in T, z \in U satisfying x + y + z = 0. Such a cap set enables a decomposition of the tensor into |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 computation. Assuming balanced sizes |S| = |T| = |U| = \delta \cdot 3^n, this yields matrix multiplication in O(n^\omega) time with \omega = 3 \log_3 3 / \log_3 (3 / \delta), which is strictly less than 3 for \delta > 1/3. Recent AI-assisted constructions from 2023 have improved lower bounds on cap set sizes to approximately $2.22^n, enabling refined tensor decompositions that push toward \omega < 2.37.^[28]^[29]^[4] 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 \mathrm{GF}(3). Cap sets in (\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 \omega \approx 2.373 from known cap set constructions of size roughly $2.2^n.^[28]^[29] Advances in the 2010s, building on the Ellenberg-Gijswijt upper bound of 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 \omega = 2, but confirming potential for \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.^[25]^[28]

Strongly Regular Graphs

A strongly regular graph is a connected, regular graph of degree k on v 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 \mathbb{F}_3. One prominent construction uses a cap S in the projective space \mathrm{PG}(n-1, 3) to define edges in the affine space \mathrm{AG}(n, 3). The vertices of the graph are the $3^n points of \mathrm{AG}(n, 3), and two distinct points u, v are adjacent if the projective point corresponding to the direction of the vector v - u (i.e., the equivalence class under scalar multiplication by nonzero elements of \mathbb{F}_3) lies in S. Since there are q-1 = 2 nonzero scalars in \mathbb{F}_3, the degree is k = 2 |S|. For the graph to be strongly regular, S 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 \mathrm{AG}(n, 3), with the adjacency eigenvalues determined by the character sums over S.^[30]^[31] A notable example is the Games graph, constructed using a unique 56-point cap in \mathrm{PG}(5, 3), yielding a strongly regular graph with parameters (v, k, \lambda, \mu) = (729, 112, 1, 20) on the points of \mathrm{AG}(6, 3). This graph is distance-regular with intersection array \{112, 110; 1, 20\} and spectrum $112^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 \mathrm{AG}(3, 3) admits a field model over \mathbb{F}_9 \cong \mathbb{F}_3^2 \times \{\text{basis}\}, inducing the Paley graph of order 9 with parameters (9, 4, 1, 2), where edges connect elements whose difference is a quadratic residue in \mathbb{F}_9. In general, parameters of these graphs are tied to the cap size r_3(n), with v = 3^n, k = 2 r_3(n-1), and \lambda, \mu computed from the cap's intersection properties with lines and planes.^[30] 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 $3^d - m_i for code dimension d and intersections m_i), and the corresponding strongly regular graphs via Delsarte's correspondence, where the graph on the ambient space has eigenvalues r = 3 m_1 - |S| and 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.^[32]

Additive Combinatorics

Cap sets in the affine space \mathbb{A}^n(\mathbb{F}_3), or equivalently in the abelian group (\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 \subseteq (\mathbb{Z}/3\mathbb{Z})^n satisfies |A| = o(3^n) as n \to \infty. This result, proved by Meshulam using Fourier analysis over \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 (\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 $3^{n(1 - c/\log n)}, but more sophisticated Behrend-type constructions, adapted to \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 n times a subpolynomial factor better than earlier bounds, enhancing the lower bounds for the maximum size of k-AP-free subsets in \mathbb{F}_q^n for fixed k \geq 3.^[33] The absence of three-term progressions in a cap set S \subseteq (\mathbb{Z}/3\mathbb{Z})^n implies strong growth properties for its sumset S + S. Specifically, |S + S| \geq \min(3^n, c |S|^{3/2}) for some absolute constant c > 0, reflecting the structural rigidity 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 Szemerédi's theorem, applies directly to cap sets: any sufficiently dense subset of (\mathbb{Z}/3\mathbb{Z})^n contains many translates of a large cap set. This connection ties into Gowers uniformity norms over \mathbb{F}_3, where sets with small U^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 (\mathbb{Z}/9\mathbb{Z})^n, exploring quasirandom subsets without generalized progressions and yielding improved density bounds. Additionally, post-2016 advances using the polynomial method from the cap set breakthrough have resolved potential counterexamples to the polynomial density 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]
None
### Definition and Main Theorem Summary
[2]
None
### Definition of a Cap Set
[3]
New lower bounds for cap sets | Published in Discrete Analysis
Dec 13, 2023 · One of the best known problems in additive combinatorics, the cap set problem, asks how large a subset of F 3 n can be if it contains no non- ...Missing: definition | Show results with:definition
[4]
[PDF] ON THE CAP SET PROBLEM upper bounds on maximal ...
As became clear in Chapter 1, the cap set problem is defined in affine geometry. Therefore, it is important to understand the basics of affine geometry. In ...
[5]
[PDF] SET AND AFFINE CAPS Contents 1. Introduction Marsha Falco ...
Aug 22, 2008 · SET is a game of patterns played with cards. Each card has a either one two or three shapes on it. The shapes are either diamonds, squiggles, or ...
[6]
[PDF] On large subsets of Fqn with no three-term arithmetic progression
The problem of arithmetic progressions in (Z/3Z)n has sometimes been seen as a model for the corresponding problem in Z/NZ. We know (for in- stance, by a ...
[7]
[2408.02328] Past and future of the cap set problem - arXiv
Aug 5, 2024 · We survey the history of the capset problem in the context of related results on progression-free sets, discuss recent progress, and mention further directions ...
[8]
[PDF] set and finite affine geometry - UChicago Math
Sep 1, 2021 · An n-cap, also referred to as simply a cap, is a subset of points in. AG(n, 3) that does not contain any lines. For example, the four cards ...Missing: interpretation GF(
[9]
Extremal problems in finite geometry - Anurag's Math Blog
Oct 9, 2017 · On sets of vectors of a finite vector space in which every subset of basis size ... This is the origin of the cap-set problem which has been ...
[10]
[PDF] arXiv:1302.4703v1 [math.CO] 19 Feb 2013
Feb 19, 2013 · In AG(2, 3), a maximal cap has 4 points and consists of two lines through an anchor point, with the anchor removed; all maximal caps are ...
[11]
[PDF] Large caps in projective Galois spaces - Yves Edel's
A cap in a projective or affine geometry over a finite field is a set of points no three of which are collinear. The most natural question to ask is:.Missing: F_3 | Show results with:F_3
[12]
[PDF] New Lower Bounds for Cap Sets - arXiv
Dec 13, 2023 · In this paper, we obtain the first new lower bound for nearly two decades, and prove that a maximal cap set has size at least (2.218021...)n.
[13]
[PDF] past and future of the cap set problem - ernie croot, vsevolod f. lev ...
Meshulam's proof uses Fourier methods, but in [30] Lev developed a purely combinatorial approach to achieve the same bounds. Significantly improving upon ...
[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]
Cap set - Wikipedia
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 ...
[18]
Caps and progression-free sets in $${{\mathbb {Z}}}_m^n
Jun 16, 2020 · ... oval). $n=3:$ one has $m^2$ points ... http://gilkalai.wordpress.com/2009/02/07/frankl-rodls-theorem-and-variations-on-the-cap-set ...<|control11|><|separator|>
[19]
[2209.10045] New lower bounds for cap sets - arXiv
Sep 20, 2022 · In this paper, we provide a new lower bound on the size of a maximal cap set. Building on a construction of Edel, we use improved computational methods and new ...Missing: Burr Grinberg Sloane
[20]
Open question: best bounds for cap sets - Terry Tao - WordPress.com
Feb 23, 2007 · The best bounds on the cap set problem in small dimensions are the ones cited in the Edel paper mentioned above.Missing: Heisenberg (F_3)^
[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]
A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt ...
May 18, 2016 · A capset in the vector space {{\bf F}_3^n} over the finite field {{\bf F}_3} of three elements is a subset {A} of {{\bf F}_3^n} that does not contain any lines.
[25]
[1606.09575] Upper bounds for sunflower-free sets - arXiv
Jun 30, 2016 · A collection of k sets is said to form a k-sunflower, or \Delta-system, if the intersection of any two sets from the collection is the same, and ...Missing: Füredi cap
[26]
On large subsets of $F_q^n$ with no three-term arithmetic progression
May 30, 2016 · This paper supersedes arXiv:1605.05492 and combines the solutions to the cap set problem independently obtained by the two authors. Subjects ...
[27]
[PDF] Erd˝os-Szemerédi Sunflower conjecture 1 Recap - CWI
The cap-set bound gives ck ≤ 1.938 (see [5, Theorem 8]). Naslund and Sawin [5] apply the slice rank method directly to the Erd˝os-Szemerédi Sunflower conjecture ...
[28]
A group-theoretic approach to fast matrix multiplication - math - arXiv
Jul 24, 2003 · We develop a new, group-theoretic approach to bounding the exponent of matrix multiplication. There are two components to this approach.
[29]
On cap sets and the group-theoretic approach to matrix multiplication
May 21, 2016 · In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent \omega of matrix multiplication by reducing matrix ...
[30]
Group-theoretic algorithms for matrix multiplication - math - arXiv
Nov 18, 2005 · Abstract: We further develop the group-theoretic approach to fast matrix multiplication introduced by Cohn and Umans, and for the first time ...
[31]
Games Graph -- from Wolfram MathWorld
The Games graph is a strongly regular graph on 729 vertices with parameters (nu,k,lambda,mu)=(729112,1,20). It is distance-regular but not ...
[32]
[PDF] Chapter 1 - Two-weight Codes - Andries E. Brouwer
sets that meet the hyperplanes in two cardinalities (these are known as 2- character sets), and strongly regular graphs defined on a vector space by a.
[33]
[PDF] Strongly Regular Graphs and Partial Geometries - CORE
A regular connected graph is strongly regular if its adja- cency matrix has three eigenvalues. We shall call a parameter set (v,k,A,µ) feasible if the necessary.
[34]
[PDF] ON SUBSETS OF Fn q CONTAINING NO k-TERM PROGRESSIONS ...
Introduction. A central result in arithmetic combinatorics is Szemerédi's theorem, which states that for every positive integer k, every sufficiently dense ...