What this calculator does
A cap set is a collection of points in a grid of side three, in n dimensions, with no three of them in a line. In the card game Set, which is exactly this question in four dimensions, it is the largest collection of cards containing no valid set. The answer there is 20 cards out of 81.
What makes the problem interesting is what happens as the dimension grows. A cap set in dimension n can be multiplied with itself to give one in dimension 2n, squaring the size, which means a single good construction propagates upwards forever. The figure that matters is therefore not the size but the size to the power one over the dimension: the growth rate per dimension.
The formula
If you have a cap set of size S in dimension n, taking all pairs gives a cap set of size S² in dimension 2n, and generally S^(D/n) in dimension D. The rate per dimension is S^(1/n), and a larger rate beats a smaller one in every sufficiently high dimension regardless of where it was found. The whole space holds 3^n points, so the trivial rate is 3 and the question is how close you can get.
| Term | Meaning |
|---|---|
| Cap set | A subset of the n-dimensional grid of side 3 with no three points in a line, equivalently no three summing to zero modulo 3. |
| Growth rate | S^(1/n). The per-dimension multiplier the construction implies. |
| Product construction | Combining a cap set with itself to get one in twice the dimension, with the size squared. |
| Density | The share of the whole space the cap set occupies, which falls away quickly as the dimension rises. |
The inputs explained
| Field | What to enter |
|---|---|
| Dimension found in | The dimension the construction was found in. |
| Cap set size | How many points it contains. The exact maxima for the first few dimensions are 2, 4, 9, 20, 45, 112 and 236. |
| Target dimension | A higher dimension to project into. The product construction is exact when D is a multiple of n. |
When to use it
Comparing constructions across dimensions
A cap set of 512 in dimension 8 and one of 112 in dimension 6 are not directly comparable by size. By rate they are: 2.1810 against 2.1955. The smaller construction in the lower dimension actually implies more in the limit, which is not obvious until you take the root.
Seeing how fast the density collapses
In dimension 4 a maximal cap set occupies about a quarter of the space. By dimension 24 the implied density is well under a tenth of a per cent. The sets keep growing, and the space grows faster.
Checking a claimed record
Enter the size and dimension and compare the rate against 2.2180, which is the best asymptotic rate known. A record in a single low dimension is usually a long way short of that, because the asymptotic constructions come from somewhere else entirely.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
What is a dimension-8 cap set worth?
The size found in dimension 8 rises down the rows.
| Cap set size | Growth rate per dimension | Density in that dimension | Implied size in the target dimension |
|---|---|---|---|
| 256 | 2.0000 | 3.90% | 16,777,216 |
| 400 | 2.1147 | 6.10% | 64,000,000 |
| 448 | 2.1449 | 6.83% | 89,915,392 |
| 496 | 2.1724 | 7.56% | 122,023,936 |
| 512 | 2.1810 | 7.80% | 134,217,728 |
How far does the product construction reach?
The same construction projected into higher and higher dimensions.
| Target dimension | Implied size in the target dimension | Points in the target dimension | Density in the target dimension |
|---|---|---|---|
| 8 | 512 | 6,561 | 7.80% |
| 16 | 262,144 | 43,046,721 | 0.609% |
| 24 | 134,217,728 | 282,429,536,500 | 0.048% |
| 32 | 68,719,476,740 | 1,853,020,189,000,000 | 0.004% |
Questions
What is the largest cap set in each dimension?
The exact maxima are known only up to dimension 6: 2, 4, 9, 20, 45 and 112. Dimension 7 is 236. Dimension 8 is not settled, and the best known construction is the 512-point one FunSearch found in 2023, improving on 496.
How fast can cap sets grow?
Ellenberg and Gijswijt proved in 2016 that they are at most 2.756^n, using the polynomial method. The best known lower bound is 2.2180^n, due to Tyrrell in 2023 improving on Edel's 2.2173^n from 2004. The truth is somewhere between.
Why does the dimension-8 record not improve the asymptotic bound?
Because its rate of 2.1810 is below what is already known. Dimension 6 alone gives 2.1955, and the record asymptotic constructions come from admissible sets in much higher dimensions. The dimension-8 result is a record for that dimension, not a new asymptotic bound.
What does this have to do with the card game Set?
Set is the dimension-4 case with three values on each of four attributes. The largest collection of cards with no set in it is 20, which is the cap set maximum in dimension 4.
Is the product construction optimal?
No, it is just a reliable floor. Combining two cap sets always gives a valid one, but better constructions in the higher dimension usually exist, which is why the exact maxima exceed what the product rule predicts.
For the counting of the underlying space see permutations and combinations and exponents and roots. How the dimension-8 record was found is in the piece on FunSearch and the cap set problem.