Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt)

Statement

The polynomial method (broad sense) is a proof strategy: encode a combinatorial configuration or constraint as a polynomial (or system of polynomials) of *bounded degree*, then deduce combinatorial bounds from algebraic facts about that polynomial (its degree, its zero set, its rank as a tensor, or a linear-algebra dimension count). Per en.wikipedia.org/wiki/Polynomial_method_in_combinatorics, the generic recipe has three steps: (1) embed the combinatorial objects into a vector space, (2) construct a low-degree polynomial that vanishes on (or otherwise encodes) the structure of interest, (3) deduce the combinatorial conclusion from an algebraic property of that polynomial (degree bound, Nullstellensatz-type non-vanishing, rank bound, etc.).

The specific instance this page centers on — slice rank (Croot–Lev–Pach / Ellenberg–Gijswijt, 2016):

*Slice rank* (terminology due to Terence Tao, terrytao.wordpress.com/2016/05/18/…): for a function $F : A^k \to \mathbb F$ ($k\ge2$ variables ranging over a set $A$, values in a field $\mathbb F$), a *rank-one slice* is a function of the form $$(x_1,\dots,x_k) \mapsto f(x_i)\,g(x_1,\dots,x_{i-1},x_{i+1},\dots,x_k)$$ for some fixed coordinate $i$. The slice rank of $F$ is the minimum number of rank-one slices needed to write $F$ as a sum.

Lemma 1 (diagonal lower bound, Tao's restatement of Croot–Lev–Pach's rank lemma)

if $F(x_1,\dots,x_k) = \sum_{a\in A} c_a\,\delta_a(x_1)\cdots\delta_a(x_k)$ (a "diagonal" tensor, $\delta_a$ the Kronecker delta at $a$) with all $c_a\neq0$, then $\operatorname{slice-rank}(F) = |A|$.

Croot–Lev–Pach / Ellenberg–Gijswijt theorem

let $A\subseteq \mathbb F_q^n$ contain no non-trivial 3-term arithmetic progression (i.e. no $x,y,z\in A$, not all equal, with $x+y+z=0$). Then $|A| \le c^n$ for an explicit constant $c<q$ depending only on $q$ — arxiv.org/abs/1605.09223 abstract: "the method of Croot, Lev, and Pach can be used to bound the size of a subset of $F_q^n$ with no three terms in arithmetic progression by $c^n$ with $c<q$." For $q=3$ (the classical cap-set problem, see Cap-set problem — max progression-free subset of F_3^n) the explicit bound is $c = \left(\frac{5589+891\sqrt{33}}{8}\right)^{1/3} = 2.75510461\ldots < 3$ (en.wikipedia.org/wiki/Cap_set gives the popular rounding "$2.756^n$"). Croot–Lev–Pach (arXiv:1605.01506) proved the analogous statement first for $\mathbb Z_4^n$: any 3-AP-free $A\subseteq\mathbb Z_4^n$ has $|A|\le 4^{\gamma n}$, $\gamma\approx0.926<1$.

Facts

- Timeline: Croot–Lev–Pach post arXiv:1605.01506 on 2016-05-05 for $\mathbb Z_4^n$; Ellenberg and Gijswijt independently and near-simultaneously adapt the method to $\mathbb F_q^n$ within days, merging into the joint note arXiv:1605.09223 (submitted 2016-05-30, "combines the solutions to the cap set problem independently obtained by the two authors"). Tao reformulates both as the single unifying "slice rank" framework within about two weeks (terrytao.wordpress.com, 2016-05-18). - Pre-2016 state of the art was exponentially worse: Meshulam (1995) $O(3^n/n)$; Bateman–Katz (2012) $O(3^n/n^{1+\epsilon})$ — both Fourier/density-increment arguments giving only sub-polynomial savings off the trivial $3^n$. Best lower-bound construction (Edel, 2004) was $\Omega(2.2^n)$-type. The slice-rank bound $c\approx2.7551^n$ was the first *exponential* improvement over the trivial bound, closing (up to the exact base) a gap that had stood since the 1990s. - Mechanistic reason Fourier methods stalled and slice rank didn't: density-increment arguments iterate a small additive density gain at each step, structurally capped at sub-polynomial total savings; the slice-rank argument instead bounds a *global algebraic invariant* (rank of a tensor encoding the whole configuration) in one shot via elementary linear algebra plus a pointwise degree bound — no iteration, no Fourier decay estimates. The original Ellenberg–Gijswijt note is only 4 pages. - Domain restriction: the technique needs a *fixed finite alphabet* $\mathbb F_q$ (or $\mathbb Z_4$) with dimension $n\to\infty$ — the degree-truncation / monomial-counting step is what produces the exponential saving, and this mechanism does not transfer back to give new bounds for Roth's/Szemerédi's theorem over $\mathbb Z$ (infinite alphabet), per wiki/problems/cap-set-problem.md §Related. - Extensions using the same slice-rank machinery: - Tri-colored sum-free sets in $(\mathbb Z/2\mathbb Z)^n$-style groups — Kleinberg, Sawin, Speyer, arXiv:1605.08416 / arXiv:1610.03740 "The growth rate of tri-colored sum-free sets," sharpening the explicit constant further; see also arXiv:2103.06481. - Sunflower-free families: Naslund & Sawin, "Upper bounds for sunflower-free sets," arXiv:1606.09575 — encode a sunflower-free family $\mathcal F \subseteq 2^{[n]}$ as a 3-AP-style configuration over $(\mathbb Z/3\mathbb Z)^n$ and get $|\mathcal F| \le 3(n+1)(3/2^{2/3})^n$, $3/2^{2/3}\approx1.88988$ — this is the *weak* (arbitrary-subset) sunflower conjecture, fully resolved by this method; the *uniform* $k$-set version (Erdős #20 — sunflower conjecture, exponential bound for f(n,k)) remains open, and Naslund–Sawin note that a $D$-uniform-in-$D$ generalization of their bound would resolve the full Erdős–Rado sunflower conjecture. - A later polynomial-factor sharpening of the Naslund–Sawin sunflower bound via "triangular tensors": arXiv:2606.30593. - Matrix-multiplication complexity: Blasiak, Church, Cohn, Grochow, Naslund, Sawin, "On cap sets and the group-theoretic approach to matrix multiplication," arXiv:1605.06702 — uses the same cap-set-type bound to show a whole natural family of group-theoretic approaches (via the "cap-set-like" obstruction) cannot prove the matrix-multiplication exponent $\omega=2$, i.e. the technique also gives *impossibility* results outside additive combinatorics (survey context: arxiv.org/pdf/2408.02328, "Past and future of the cap set problem," referenced in wiki/problems/cap-set-problem.md provenance). - The polynomial method is a broader family than just slice rank. Sibling branches sharing the "low-degree polynomial encodes structure" philosophy but using different algebraic mechanisms (per en.wikipedia.org/wiki/Polynomial_method_in_combinatorics): - Combinatorial Nullstellensatz (Alon, 1999) — a Nullstellensatz-flavored non-vanishing lemma for polynomials over a grid; ancestor tool for many finite-field constructions. - Frankl–Wilson-type eigenvalue/algebraic bounds (1981) — mod-$p$ polynomial constructions for set-intersection theorems (Oddtown/Eventown-style linear algebra bound), cited in wiki/problems/78.md as concept/frankl-wilson-polynomial-method, an early precursor of the "polynomial as algebraic certificate" idea, distinct machinery from slice rank. - Dvir's finite-field Kakeya theorem (2008) — polynomial vanishing on a Kakeya set forces low degree, contradiction via counting; different from slice rank (uses a single vanishing polynomial + degree/dimension counting, not a tensor-rank sandwich). - Guth–Katz polynomial partitioning (2010 joints problem; 2015 Erdős distinct-distances theorem, arXiv:1011.4105) — uses the *polynomial ham-sandwich theorem* to cell-decompose space, then algebraic-geometry incidence bounds on the cells; resolved Erdős #89 — distinct distances in the plane up to a $\sqrt{\log n}$ factor and is referenced from wiki/problems/89.md and wiki/problems/132.md as Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt). This is a geometric/cell-decomposition branch, mechanistically different from the CLP/EG diagonal-rank sandwich, but both are commonly filed under the umbrella term "polynomial method" in the literature (2016 is cited as the moment the umbrella term gained prominence, per Wikipedia).

Technique

How to apply the CLP/EG slice-rank recipe to a new problem (concrete, reusable steps — this is the recombination-ready part):

1. Identify a forbidden fixed-length linear pattern over a bounded finite alphabet with growing dimension $n$: e.g. "no 3 points $x,y,z$ (not all equal) with $x+y+z=0$" in $\mathbb F_q^n$, or "no 3-petal sunflower" in a set family encoded as $\{0,1,2\}^n$-style vectors. 2. Encode the "forbidden = has a solution" condition as a bounded-total-degree polynomial vanishing off the diagonal. Use the standard trick $\delta_0(t) = \prod_{s\in\mathbb F_q,\,s\neq0}(1-t/s)$ (degree $q-1$ in $t$) to build a degree-$O(n)$ polynomial $P(x,y,z)$ that equals $1$ exactly when $x+y+z=0$ and the configuration is trivial (diagonal), $0$ otherwise, for $x,y,z\in A$. 3. Lower-bound the slice rank of $P$ restricted to $A^3$ by $|A|$. Because $A$ has *no other* solutions to the linear relation besides the trivial diagonal ones, $P|_{A^3}$ equals $\sum_{a\in A}\delta_a(x)\delta_a(y)\delta_a(z)$ exactly — a diagonal tensor with $|A|$ nonzero coefficients — so by Lemma 1, $\operatorname{slice-rank}(P|_{A^3}) = |A|$. 4. Upper-bound the slice rank of $P$ by a monomial count. Expand $P$ as a sum of monomials of total degree $\le d = O(n)$; pigeonhole each monomial's degree into whichever of the three variable blocks ($x$, $y$, or $z$) holds at least $d/3$ of the total degree — this splits $P$ into at most $3N$ rank-one slices, where $N$ = number of monomials in $n$ variables of degree $\le d/3$ (or the appropriate threshold), each variable's individual degree capped at $q-1$. 5. Bound $N$ via an entropy/generating-function (simplex lattice-point) estimate, giving $N = O(c^n)$ for an explicit $c<q$ computable by optimizing the degree split (this is where the exact constant like $2.7551$ comes from — a calculus optimization over the simplex of degree-distribution weights). 6. Chain the two bounds: $|A| = \operatorname{slice-rank}(P|_{A^3}) \le 3N = O(c^n)$. Done — no Fourier analysis, no iteration.

WHEN it applies: the pattern must be (a) a *fixed number* of points (here 3) satisfying (b) a *linear* relation, (c) over a set of *bounded-size alphabet* $\mathbb F_q$ or $\mathbb Z/D\mathbb Z$ with the ambient dimension $n\to\infty$ being the asymptotic parameter, and (d) the "trivial solution" set must be exactly the diagonal (or a low-complexity variety) so that a diagonal-tensor rank lower bound is available. It does *not* directly give new bounds for the same patterns over $\mathbb Z$ (unbounded alphabet) — the degree-truncation trick loses its power without a bounded alphabet, per wiki/problems/cap-set-problem.md.

WHY it works (the mechanism, for recombination): it replaces an *iterative, lossy* argument (density increment / Fourier peeling, which only ever removes a sub-polynomial fraction per step) with a *single global algebraic identity* — the same object (a diagonal tensor) is bounded from below by a combinatorial count (via linear independence of point-masses) and from above by an analytic/algebraic count (via bounded degree ⇒ few monomials). Whenever a combinatorics problem can be phrased as "this tensor is diagonal-of-size-$|A|$ AND has bounded-degree polynomial structure," the same two-sided sandwich is available — this is the reusable derivation move, independent of the specific application (3-APs, sunflowers, tri-colored sum-free triples, matrix-multiplication obstructions).

Related

- Cap-set problem — max progression-free subset of F_3^n — the founding application; full worked proof sketch and provenance for the exact constant $c=2.75510461\ldots$ lives there. - Erdős #20 — sunflower conjecture, exponential bound for f(n,k) — uniform-size sunflower conjecture; the *weak* (non-uniform) sibling was fully resolved by Naslund–Sawin's direct application of this method (arXiv:1606.09575), but the uniform version Erdős #20 — sunflower conjecture, exponential bound for f(n,k) itself has not been cracked by this technique — a concrete open transfer target. - Erdős #89 — distinct distances in the plane — Erdős distinct-distances problem, resolved up to a $\sqrt{\log n}$ factor by Guth–Katz's *different* branch of the polynomial method (ham-sandwich cell decomposition, not slice rank). - Erdős #132 — a second low-multiplicity distance — references the Guth–Katz polynomial-method machinery for distance-counting. - Erdős #78 — constructive proof that $R(k)>C^k$ — cites the earlier Frankl–Wilson polynomial/eigenvalue method (1981), a related but mechanistically distinct ancestor technique (mod-$p$ linear-algebra bound, not slice rank), later superseded by extractor-based methods for that specific problem (BRSW 2012). - concept/tri-colored-sum-free-sets — Kleinberg–Sawin–Speyer's refinement of the identical slice-rank argument, currently the best explicit constants (arXiv:1610.03740, arXiv:2103.06481). - concept/sunflower-free-sets — Naslund–Sawin's direct transfer of the method (arXiv:1606.09575). - concept/combinatorial-nullstellensatz — Alon's 1999 non-vanishing polynomial lemma, the older sibling tool in the same broad polynomial-method family, mechanistically different (non-vanishing certificate vs. tensor-rank sandwich). - concept/frankl-wilson-polynomial-method — 1981 eigenvalue/mod-$p$ set-intersection technique, earliest major named "polynomial method" instance, precursor to but distinct from slice rank.