The cap set constant
Description of constant
Let $r(n)$ be the size of the largest cap set in $\mathbb{F}_{3}^{n}$, i.e., a set that does not contain any lines (length three progressions). $C_{4}$ is the largest constant such that $r(n) \leq C_{4}^{(1+o(1)) n}$.
Known upper bounds
| Bound |
Reference |
Comments |
| $3$ |
Trivial |
|
| $2.756$ |
[EG2016] |
|
Known lower bounds
| Bound |
Reference |
Comments |
| $2$ |
Trivial |
|
| $2.1146$ |
[P1970] |
|
| $2.2101$ |
[CF1994] |
|
| $2.2173$ |
[E2004] |
|
| $2.2180$ |
[T2002] |
|
| $2.2202$ |
[RBNBKDREWFKF2023] |
Funsearch |
- Any cap set $A$ in $\mathbb F_{3}^n$ gives a lower bound $C_{4} \geq \lvert A\rvert^{1/n}$ by taking Cartesian powers. For similar reason, the limit $\lim_{n \to \infty} r(n)^{1/n}$ exists and equals $C_{4}$.
- Wikipedia page on cap sets
- Also connected to the sunflower conjecture; see [NS2016].
References
- [CF1994] Calderbank, A. Robert; Fishburn, Peter C. Maximal three-independent subsets of ${0,1,2}^n$. Des. Codes Cryptogr. 4, No. 3, 203-211 (1994).
- [E2004] Edel, Y. New lower bounds for caps in $AG(4, 3)$. Des. Codes Cryptogr. 33, No. 1-3, 149-160 (2004).
- [EG2016] Ellenberg, Jordan S.; Gijswijt, Dion. On large subsets of $F^n_q$ with no three-term arithmetic progression. Ann. of Math. (2) 185 (2017), no. 1, 339–343. arXiv:1605.09223
- [NS2016] Naslund, Eric; Sawin, William F. Upper bounds for sunflower-free sets. arXiv:1606.09575
- [P1970] Pellegrino, Giuseppe. Sul massimo ordine delle calotte in $S_{4,3}$. Matematiche (Catania) 25 (1970), no. 10, 1–9.
- [RBNBKDREWFKF2023] 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. Mathematical discoveries from program search with large language models. Nature. 625 (7995): 468–475 (2023).
- [T2002] Tyrrell, Fred. New lower bounds for cap sets. Discrete Analysis. 2023 (20). arXiv:2209.10045.