Cap-set problem — max progression-free subset of F_3^n

Statement

A cap set in $\mathbb F_3^n$ is a subset $A\subseteq\mathbb F_3^n$ containing no three distinct points $x,y,z\in A$ in arithmetic progression, i.e. no solution to $x+y+z=0$ (equivalently $x+z=2y$) with $x,y,z\in A$ not all equal. Let $r_3(\mathbb F_3^n)$ denote the maximum size of a cap set. The problem, going back to work motivated by the card game SET and studied extensively by Erdős and others in the finite-field analogue of Roth's/Szemerédi's theorem programme, asks for the growth rate of $r_3(\mathbb F_3^n)$ as $n\to\infty$. More generally, for $A\subseteq\mathbb F_q^n$ ($q$ fixed, $n\to\infty$) with no nontrivial 3-term progression, what is the exponential growth rate of the max size?

Before 2016 the state of the art was $r_3(\mathbb F_3^n) = O(3^n/n^{1+\epsilon})$ (Bateman–Katz, building on Croot–Lev–Sisask-style Fourier methods), i.e. only a barely-below-$3^n$ saving, while the best lower bound (construction) was $\Omega(2.2^n)$-type (Edel). The huge gap between $3^n/n^{1+\epsilon}$ and $\sim2.2^n$ was the open problem.

Facts

- Trivial upper bound: $r_3(\mathbb F_3^n) \le 3^n$ (whole space). Trivial-ish improvements pre-2016 only shaved off polylog/polynomial factors from $3^n$ (Meshulam 1995: $O(3^n/n)$; Bateman–Katz 2012: $O(3^n/n^{1+\epsilon})$), leaving an exponential gap versus the best known constructions ($\gtrsim 2.2^n$, Edel 2004). - Solved May 2016 by two nearly-simultaneous papers using the same new technique (the "polynomial method" / slice rank), which together give the answer up to the base of the exponent: - Ernie Croot, Vsevolod F. Lev, Péter Pál Pach, "Progression-free sets in $\mathbb Z_4^n$ are exponentially small," arXiv:1605.01506 (submitted 2016-05-05) — proved the analogous statement for $\mathbb Z_4^n$ first: any 3-AP-free $A\subseteq\mathbb Z_4^n$ has $|A|\le 4^{\gamma n}$ with $\gamma\approx 0.926 < 1$, via a genuinely new polynomial argument (not Fourier analysis). - Jordan S. Ellenberg, Dion Gijswijt, "On large subsets of $\mathbb F_q^n$ with no three-term arithmetic progression," arXiv:1605.09223 (submitted 2016-05-30) — adapted the Croot–Lev–Pach method to $\mathbb F_q^n$ directly, proving $r_3(\mathbb F_q^n) \le c^n$ for an explicit $c<q$; this paper explicitly states it "combines the solutions to the cap set problem independently obtained by the two authors" (Ellenberg and Gijswijt arrived at essentially the same bound within days of each other and of Croot–Lev–Pach). - Answer (case $q=3$, the classical cap-set problem): $r_3(\mathbb F_3^n) = O(c^n)$ with $c = \left(\frac{5589+891\sqrt{33}}{8}\right)^{1/3} = 2.75510461\ldots$, i.e. the base is strictly below $3$. Combined with the pre-existing lower bound $r_3(\mathbb F_3^n) = \Omega(2.2\ldots^n)$ (Edel), this pins the exponential growth rate to lie in $[2.2,\,2.7551]^n$ — the qualitative question ("is it $c^n$ for some $c<3$?") is fully resolved; the exact constant $c$ remains open (later work sharpened the upper-bound constant further, e.g. Kleinberg–Sawin–Speyer arXiv:1610.03740 "The growth rate of tri-colored sum-free sets" and follow-ups such as arXiv:2103.06481; the problem of finding the exact/optimal base is a separate, still-open descendant). - Same method gives, for general prime power $q$: $r_3(\mathbb F_q^n) = O(c_q^n)$ with explicit $c_q < q$ (Ellenberg–Gijswijt, arXiv:1605.09223), and for $\mathbb Z_4^n$: $\Theta(\text{exponentially smaller than } 4^n)$ (Croot–Lev–Pach, arXiv:1605.01506). - Reformulated by Terence Tao within days as the "slice rank" method for tensors, giving a cleaner, more general framework — terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound. - Popular/expository accounts confirming the timeline and correctness: gilkalai.wordpress.com/2016/05/15 (Gil Kalai, "Mind Boggling"), anuragbishnoi.wordpress.com/2016/05/18, quomodocumque.wordpress.com/2016/05/12+05/13 (Ellenberg's own blog).

The transferable idea — polynomial method via (slice) rank of a diagonal tensor

1. Encode the forbidden configuration as a low-degree polynomial identity. For $A\subseteq\mathbb F_3^n$ cap-set-free of 3-APs, the indicator that "$x+y+z=0 \Rightarrow x=y=z$" is captured by a symmetric trilinear form / degree-$\le 2(q-1)$ polynomial $\delta_0(x+y+z)$ over the grid $\{0,\dots,q-1\}^n$ (via the standard trick $\delta_0(t) = \prod$ over field elements, expressed as a polynomial of bounded total degree, expanded and truncated by pigeonhole into a sum of $\le n$-degree-split monomials in disjoint variable blocks).

2. Two contradictory ways to bound the "rank" of this same tensor/polynomial: - *Lower bound on rank*: Restricted to the diagonal $x=y=z\in A$ (using that $A$ has no other solutions), the associated 3-tensor is essentially a diagonal matrix on $|A|$ points with all-nonzero diagonal entries, which forces its rank (in the relevant sense — Croot–Lev–Pach's "rank" of a function, later identified by Tao as slice rank of a 3-tensor) to be $\ge |A|$. - *Upper bound on rank*: Because the polynomial has bounded total degree $d = O(n)$ (specifically degree $\le (q-1)n$, roughly $2n/3$ after optimizing), the number of monomials of degree $\le d/2$ that a low-degree polynomial can be split into (by pigeonholing each monomial's total degree into one of the three variable blocks $x,y,z$) is a sub-$q^n$ count $N$ controlled by the number of lattice points in a simplex, bounded via an entropy/generating-function estimate — giving rank $\le 3N = O(c^n)$ for explicit $c<q$. - Chaining the two bounds: $|A| \le \text{rank} \le 3N = O(c^n)$.

3. Why this cracked the problem after Fourier methods stalled: Fourier-analytic / density-increment arguments (Roth-, Meshulam-, Bateman–Katz-style) inherently only remove a sub-polynomial or barely-superpolynomial factor from the trivial bound $q^n$, because they iterate a "density increment" that improves the density by only a small additive amount at each step. The polynomial-rank argument instead directly bounds a *global algebraic invariant* (rank of the tensor encoding the whole configuration) using nothing but a *pointwise degree bound* and elementary linear algebra over any field — no iteration, no Fourier decay estimates, no arithmetic-regularity machinery. This is a genuinely different mechanism, and it is short: the original Ellenberg–Gijswijt note is 4 pages (arxiv.org/abs/1605.09223).

4. The technique is domain-general — it transfers whenever "no nontrivial solution to a linear equation" can be encoded as a bounded-degree polynomial vanishing off a diagonal. Concretely it has been reused to bound: tri-colored sum-free sets (Kleinberg–Sawin–Speyer, arXiv:1605.08416/1610.03740), difference sets in polynomial rings (arXiv:1803.05308), and — the case most relevant to this wiki — sunflower-free families, via Naslund & Sawin, "Upper bounds for sunflower-free sets," arXiv:1606.09575: they encode a sunflower-free family $\mathcal F\subseteq 2^{[n]}$ as a 3-AP-free-style configuration over $(\mathbb Z/3\mathbb Z)^n$ (identifying sets with $\{0,1\}$-vectors and using that a sunflower with 3 petals corresponds to a specific linear relation), apply the same slice-rank machinery, and get $|\mathcal F| \le (3/2^{2/3})^{n(1+o(1))} \approx 1.88988^{n(1+o(1))}$ — sharper than the earlier polynomial-method bound of Alon–Shpilka–Umans-style reductions. Naslund–Sawin further show that if the analogous constant $c_D$ for the $(\mathbb Z/D\mathbb Z)^n$ generalization could be made bounded independent of $D$, this would resolve the Erdős–Rado sunflower conjecture itself — i.e. the cap-set technique gives the best known attack line on weak/strong sunflower bounds. (A recent polynomial-factor sharpening of the Naslund–Sawin bound via "triangular tensors" is arXiv:2606.30593.)

Bottom line for downstream use: the "cap-set trick" = (i) write the forbidden pattern as a symmetric low-degree polynomial vanishing except on the diagonal, (ii) sandwich $|A|$ between a diagonal-rank lower bound and a monomial-count upper bound, (iii) optimize the monomial split via a simplex/entropy estimate. This is the concept page to link as `concept/slice-rank-polynomial-method`.

Related

- concept/slice-rank-polynomial-method — the transferable technique itself (Croot–Lev–Pach lemma + Tao's slice-rank reformulation). - concept/sunflower-free-sets — Naslund–Sawin's direct application of the same method, arXiv:1606.09575. - erdos/sunflower — the (weak/strong) Erdős–Rado sunflower conjecture; Naslund–Sawin note that a $D$-uniform-in-$D$ version of their capset-derived bound would resolve it. - concept/roth-theorem / concept/szemeredi-theorem — the classical (integer / general-progression-length) analogues this finite-field problem was modeling; the polynomial method is specific to the fixed-short-progression, growing-dimension regime and does *not* directly transfer back to improve Roth/Szemerédi bounds over $\mathbb Z$. - concept/tri-colored-sum-free-sets — Kleinberg–Sawin–Speyer's refinement of the same slice-rank argument, giving the currently best-known explicit constant improvements (arXiv:1610.03740, arXiv:2103.06481).