OpenFrontiers
Join
← Back to the index
OP-11999OpenCombinatorics

Cap set constant (C4aC_{4a})

Cap set constant: determine C4aC_{4a} or improve its bounds; the repository records 2.2203 (lower) and 2.756 (upper).

MSC 05D05 · Extremal set theoryMSC 11B25 · Arithmetic progressions

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Let r(n)r(n) be the size of the largest cap set in F3n\mathbb{F}_{3}^{n}, i.e., a set that does not contain any lines (length three progressions). C4C_{4} is the largest constant such that r(n)≤C4(1+o(1))nr(n) \leq C_{4}^{(1+o(1)) n}.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • Any cap set AA in F3n\mathbb F_{3}^n gives a lower bound C4≥∣A∣1/nC_{4} \geq \lvert A\rvert^{1/n} by taking Cartesian powers. For similar reason, the limit lim⁡n→∞r(n)1/n\lim_{n \to \infty} r(n)^{1/n} exists and equals C4C_{4}.
  • Wikipedia page on cap sets
  • Also connected to the sunflower conjecture; see [NS2016].

References (from the repository page)

  • [CF1994] Calderbank, A. Robert; Fishburn, Peter C. Maximal three-independent subsets of {0,1,2}n\{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)AG(4, 3). Des. Codes Cryptogr. 33, No. 1-3, 149-160 (2004).
  • [EG2016] Ellenberg, Jordan S.; Gijswijt, Dion. On large subsets of FqnF^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 S4,3S_{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).
  • [ZWLPLZJZZZ2025] Zhai, Y., Wei, Z., Li, R., Pan, K., Liu, S., Zhang, L., Ji, J., Zhang, W., Zhang, Y. and Zhang, Y., 2025. (X)-evolve: Solution space evolution powered by large language models. arXiv preprint [arXiv:2508.07932].
  • [T2023] Tyrrell, Fred. New lower bounds for cap sets. Discrete Analysis. 2023 (20). arXiv:2209.10045.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 2.2203; best known upper bound 2.756. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
33 Trivial
2.7562.756 [EG2016]

Known lower bounds

Bound Reference Comments
22 Trivial
2.11462.1146 [P1970]
2.21012.2101 [CF1994]
2.21732.2173 [E2004]
2.21802.2180 [T2023]
2.22022.2202 [RBNBKDREWFKF2023] Funsearch
2.22032.2203 [ZWLPLZJZZZ2025] X-evolve
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Cap set constant ($C_{4a}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.