Cap sets in 𝔽₃ⁿ: the growth constant, between 2.2202 and 2.7552
Both sides have moved since 2016 only by computer search (lower) or sub-exponential factors (upper), and slice rank is provably exhausted, so 58: below union-closed sets (66) because the lower side is open to search, and above r(4,t) (55). Application value 9 is indirect (limits on group-theoretic matrix multiplication). Leverage 34 reaches additive combinatorics and the ω programme.
The problem
How many cards from a special deck can you hold with no three forming a 'set'? The growth rate is between about 2.22 and 2.76.
- 1Cap set: no three cards form a line
- 2How large as dimensions grow?
- 3Polynomial method: growth at most 2.76
- 4Constructions: growth at least 2.22
Setting. A cap set is a subset of (vectors with coordinates in , added mod 3) containing no three distinct points on a line, which is equivalent to no solutions of other than . In the card game Set, each card is a vector in and a 'set' is a line. Let be the maximum size of a cap set and (the limit exists because is supermultiplicative). The accepted bounds are , where the upper constant is the Ellenberg–Gijswijt number with . The problem: determine , or improve either bound.
Built from
earlier problems → this oneThe problems this one is built from: progress or tools it needs (builds on), special cases that come first (generalizes), and weaker results on the way (implies). On the right, what builds on it.
- Start with
- Cap sets in 𝔽₃ⁿ: the growth constant, between 2.2202 and 2.7552This problem
- Then
- Matrix multiplication exponent: is ω = 2, i.e. n^(2+o(1)) operations for n×n products?Complexity Theory · D82
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- Cap sets in 𝔽₃ⁿ: the growth constant, between 2.2202 and 2.7552The problem
State of the art
Partially resolved. Ellenberg and Gijswijt (arXiv:1605.09223, 2016), building on Croot–Lev–Pach, proved r₃(n) ≤ 2.7552…^n by the polynomial (slice-rank) method; Jiang (arXiv:2103.06481) improved this by a factor √n without changing the base. On the lower side, Edel's product constructions gave 2.2174^n; Tyrrell (arXiv:2209.10045, Discrete Analysis 2023) raised the base to 2.218; FunSearch (Romera-Paredes et al., Nature, December 2023) found new admissible sets giving 2.2202, and also a cap set of size 512 in dimension 8; X-evolve (arXiv:2508.07932, preprint) reports a larger partial admissible set giving 2.2203. Kleinberg–Sawin–Speyer, with Norin and Pebody, showed that the slice-rank bound is the exact answer for tri-coloured sum-free sets, so slice rank alone cannot improve the cap-set upper base. Blasiak et al. connected cap-set bounds to the Cohn–Umans group-theoretic approach to matrix multiplication.
Realistic applications
Indirect: cap-set upper bounds limit certain group-theoretic algorithms for matrix multiplication, and finite-field bounds feed coding theory and additive combinatorics. The 2023 FunSearch result is also an example of machine-guided search for combinatorial constructions.
What counts as solved
A refereed upper bound with base below 2.7552…, or a verified construction with base above 2.2203, or the exact value of c.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: the growth constant c of the largest cap set in F_3^n, currently between 2.2202 and 2.7552 per the pack. A lower-bound improvement comes with an explicit cap set in some dimension n (a list of vectors) that anyone can verify has no three collinear points; an upper-bound improvement needs a refereed proof. Record the dimension, the set size, and the verification script.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Lower bounds benefit strongly from computer search; upper bounds need new algebraic ideas.
Bottlenecks
ranked by votes- #1TheorySlice rank is tight for related problems
Kleinberg–Sawin–Speyer show slice rank gives sharp results for tri-colored sum-free sets, so improvements need a method beyond slice rank.
Community grades
Sign in to add your own grade.