Maximum size of cap sets in F₃ⁿ

A cap set in F₃ⁿ contains no nontrivial three-term arithmetic progression. How large can such a set be in a fixed dimension, and how quickly can the maximum size grow with n?

Why it matters and what counts as progress

Why it matters: The gap between cap-set constructions and upper bounds leaves a basic extremal question in additive combinatorics unresolved.

What counts as progress: Construct larger finite cap sets, improve exponential lower bounds or prove smaller upper bounds; these are distinct forms of progress.

How the problem developed

30 May 2016 · Upper bound [1]
Jordan Ellenberg and Dion Gijswijt Used the polynomial method to prove an exponential upper bound with base strictly below 3 for cap sets in F₃ⁿ.
20 Sept 2022 · Lower bound [2]
Fred Tyrrell Improved the known exponential lower bound for cap-set size to at least 2.218ⁿ.
14 Dec 2023 · Construction [3]
DeepMind FunSearch team Found cap-set constructions improving the capacity lower bound to 2.2202 and a 512-element cap in dimension eight.

AI contribution

Mathematical discoveries from program search with large language models

Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi

The FunSearch paper reports new large cap-set constructions improving the authors’ stated finite-dimensional and asymptotic baselines.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (exact computation)

Human understandingFull