on cap sets and the polynomial method

Overview

Ellenberg and Gijswijt proved that every subset of ${\mathbb{F}}_q^n$ with no nontrivial three-term arithmetic progression has size at most $c_q^n$ for some $c_q<q$ (Ellenberg & Gijswijt, 2017). For $q=3$, this gives the cap-set bound

$$r_3({\mathbb{F}}_3^n)=o(2.756^n),$$

a qualitative change from the earlier Fourier-analytic bounds of Meshulam and Bateman-Katz (Meshulam, 1995; Bateman & Katz, 2012).

The proof is compressed because it isolates the correct finite-dimensional linear algebra. A low-degree polynomial on ${\mathbb{F}}_q^n$ is controlled by a small set of monomials. If such a polynomial vanishes on all off-diagonal additive configurations from a set $A$, then the associated evaluation matrix has small rank. The progression-free hypothesis makes that matrix diagonal on $A\times A$, so its rank counts the nonzero diagonal entries. A dimension argument then forces $|A|$ to be at most a low-degree monomial count.

Progression-Free Sets in Finite Vector Spaces

For a finite abelian group $G$, let

$$r_3(G)$$

denote the largest size of a subset of $G$ containing no nontrivial three-term arithmetic progression. In an abelian group, a three-term progression is a triple

$$a,b,c$$

with

$$a+c=2b.$$

The triple is trivial if $a=b=c$.

The finite-field cap-set problem is the case

$$G={\mathbb{F}}_3^n.$$

Since $2=-1$ in ${\mathbb{F}}_3$, the equation $a+c=2b$ is equivalent to

$$a+b+c=0.$$

Moreover, if two of $a,b,c$ are equal and $a+b+c=0$, then all three are equal. Thus a cap set in ${\mathbb{F}}_3^n$ is exactly a set $A$ for which

$$a+b+c=0,a,b,c\in A,$$

only occurs when $a=b=c$.

Before Ellenberg-Gijswijt, the best upper bound for ${\mathbb{F}}_3^n$ was

$$r_3({\mathbb{F}}_3^n)\ll \frac{3^n}{n^{1+\epsilon }}$$

for some absolute $\epsilon >0$, due to Bateman and Katz (Bateman & Katz, 2012), improving Meshulam’s bound $O(3^n/n)$ (Meshulam, 1995). The known lower bound was exponential, roughly $2.2^n$, from constructions of Edel and related product-cap methods (Edel, 2004). The open question was whether the upper bound could be made exponentially smaller than $3^n$.

Ellenberg and Gijswijt proved that it can. Their argument extends the polynomial method introduced by Croot, Lev, and Pach for progression-free subsets of ${\mathbb{Z}}_4^n$ (Croot, Lev & Pach, 2017).

Polynomial Functions on ${\mathbb{F}}_q^n$

The finite-field polynomial method begins with a basic representation fact. Let $M_n$ be the set of monomials

$$x_1^{e_1}\cdots x_n^{e_n}$$

with

$$0\le e_i\le q-1(1\le i\le n),$$

and let $S_n$ be their ${\mathbb{F}}_q$-span.

Polynomial Representatives

The evaluation map

$$S_n\to {\mathbb{F}}_q^{{\mathbb{F}}_q^n},P\mapsto (P(a){)}_{a\in {\mathbb{F}}_q^n},$$

is a linear isomorphism.

Both vector spaces have dimension $q^n$, and surjectivity is explicit. For each point $a=(a_1,\dots ,a_n)$, the polynomial

$$\prod _{i=1}^n\left(1-(x_i-a_i{)}^{q-1}\right)$$

is the indicator function of the point $a$. Indeed, for $u\in {\mathbb{F}}_q$, Fermat’s theorem gives

$$u^{q-1}=\{\begin{array}{ll}0,& u=0,\\ 1,& u\ne 0,\end{array}$$

so each factor is $1$ at $x_i=a_i$ and $0$ otherwise.

Equivalently, every function on ${\mathbb{F}}_q^n$ has a unique representative in the quotient ring

$${\mathbb{F}}_q[x_1,\dots ,x_n]/(x_1^q-x_1,\dots ,x_n^q-x_n),$$

written with individual degrees at most $q-1$.

For a real number $d$, let $M_n^d$ be the set of monomials in $M_n$ of total degree at most $d$, and let

$$S_n^d={\mathrm{span}}_{{\mathbb{F}}_q}{M}_n^d.$$

Write

$$m_d=\dim S_n^d=|M_n^d|.$$

These numbers are the only quantitative input in the proof.

Rank Lemma

The key proposition is a rank statement. It is the finite-field version of the Croot-Lev-Pach lemma.

Ellenberg-Gijswijt rank lemma

Let $A\subset {\mathbb{F}}_q^n$, and let $\alpha ,\beta ,\gamma \in {\mathbb{F}}_q$ satisfy

$$\alpha +\beta +\gamma =0.$$

Suppose $P\in S_n^d$ satisfies

$$P(\alpha a+\beta b)=0$$

for every distinct pair $a,b\in A$. Then the number of $a\in A$ for which

$$P(-\gamma a)\ne 0$$

is at most

$$2m_{d/2}.$$

The proof is pure linear algebra. Consider the $A\times A$ matrix

$$B_{a,b}=P(\alpha a+\beta b).$$

Since $P$ has total degree at most $d$, the polynomial $P(\alpha x+\beta y)$ can be expanded as a sum of terms

$$C_{u,v}{x}^u{y}^v$$

with

$$|u|+|v|\le d.$$

In each such term, at least one of $|u|$ and $|v|$ is at most $d/2$. Therefore the expansion can be reorganized as

$$P(\alpha x+\beta y)=\sum _{m\in M_n^{d/2}}m(x)F_m(y)+\sum _{m\in M_n^{d/2}}{G}_m(x)m(y)$$

for suitable functions $F_m,G_m$.

After evaluation on $A\times A$, each summand of the form $m(a)F_m(b)$ or $G_m(a)m(b)$ is a rank-one matrix. Hence

$$\mathrm{rank}B\le 2m_{d/2}.$$

The vanishing hypothesis says that $B$ is diagonal. Its diagonal entry at $a$ is

$$B_{a,a}=P((\alpha +\beta )a)=P(-\gamma a).$$

A diagonal matrix has rank equal to the number of nonzero diagonal entries, which proves the lemma.

The important idea is the degree split: low total degree in two groups of variables forces every monomial to be low-degree in at least one group. This converts polynomial degree into matrix rank.

Vanishing Polynomial and Support

Now assume $A\subset {\mathbb{F}}_q^n$ has no nontrivial solutions to

$$\alpha a_1+\beta a_2+\gamma a_3=0,a_1,a_2,a_3\in A,$$

where

$$\alpha +\beta +\gamma =0,\gamma \ne 0.$$

For ordinary three-term progressions over fields of odd characteristic, one takes

$$(\alpha ,\beta ,\gamma )=(1,-2,1).$$

For cap sets in ${\mathbb{F}}_3^n$, one takes

$$(\alpha ,\beta ,\gamma )=(1,1,1).$$

Fix $d$. Let $V$ be the space of polynomials in $S_n^d$ which vanish outside the set

$$-\gamma A=\{-\gamma a:a\in A\}.$$

Since $S_n^d$ has dimension $m_d$, while the space of all functions supported on $-\gamma A$ has dimension $|A|$ inside the $q^n$-dimensional function space on ${\mathbb{F}}_q^n$, the dimension estimate

$$\dim (U\cap W)\ge \dim U+\dim W-q^n$$

gives

$$\dim V\ge m_d-q^n+|A|.$$

For distinct $a_1,a_2\in A$, the point

$$\alpha a_1+\beta a_2$$

does not lie in $-\gamma A$. If it did, then

$$\alpha a_1+\beta a_2+\gamma a_3=0$$

for some $a_3\in A$, giving a nontrivial forbidden configuration. Therefore every $P\in V$ satisfies

$$P(\alpha a_1+\beta a_2)=0(a_1\ne a_2).$$

The rank lemma applies to every $P\in V$.

Choose $P\in V$ with maximal support, and let

$$\Sigma =\{x\in {\mathbb{F}}_q^n:P(x)\ne 0\}.$$

The support is contained in $-\gamma A$. Since $\gamma \ne 0$, the map $a\mapsto -\gamma a$ is a bijection from $A$ to $-\gamma A$, so the rank lemma gives

$$|\Sigma |\le 2m_{d/2}.$$

On the other hand,

$$|\Sigma |\ge \dim V.$$

Indeed, if $|\Sigma |<\dim V$, then there is a nonzero $Q\in V$ vanishing on all of $\Sigma$. Since $Q$ is nonzero somewhere outside $\Sigma$, the support of $P+Q$ strictly contains the support of $P$, contradicting maximality.

Thus

$$m_d-q^n+|A|\le \dim V\le 2m_{d/2},$$

and hence

$$|A|\le 2m_{d/2}+q^n-m_d.$$

This inequality is the proof’s central output.

Monomial Complement Symmetry

It remains to choose $d$. The term $q^n-m_d$ counts monomials in $M_n$ of total degree greater than $d$. The map

$$x_1^{e_1}\cdots x_n^{e_n}\mapsto x_1^{q-1-e_1}\cdots x_n^{q-1-e_n}$$

is a bijection from monomials of degree greater than $d$ to monomials of degree less than

$$(q-1)n-d.$$

Therefore

$$q^n-m_d\le m_{(q-1)n-d}.$$

The previous inequality becomes

$$|A|\le 2m_{d/2}+m_{(q-1)n-d}.$$

Balance the two terms by taking

$$d=\frac{2(q-1)n}{3}.$$

Then

$$\frac{d}{2}=(q-1)n-d=\frac{(q-1)n}{3},$$

so

$$|A|\le 3m_{(q-1)n/3}.$$

When the displayed threshold is not an integer, one inserts floors or ceilings; this only changes the bound by subexponential factors. The structural theorem is:

Ellenberg-Gijswijt bound

Let $A\subset {\mathbb{F}}_q^n$ have no nontrivial solutions to

$$\alpha a_1+\beta a_2+\gamma a_3=0,$$

where $\alpha +\beta +\gamma =0$ and $\gamma \ne 0$. Then

$$|A|\le 3m_{(q-1)n/3}.$$

At this stage the additive-combinatorial input has been fully converted into linear algebra. The remaining problem is to estimate a monomial count.

Exponential Monomial Estimate

The generating function for the monomial counts is

$$(1+t+\cdots +t^{q-1}{)}^n.$$

For $0<t<1$, every monomial of degree at most $D$ contributes at least $t^D$ to this generating function, so

$$m_D{t}^D\le (1+t+\cdots +t^{q-1}{)}^n.$$

Thus

$$m_D\le {\left(\frac{1+t+\cdots +t^{q-1}}{t^{D/n}}\right)}^n.$$

With

$$D=\frac{(q-1)n}{3},$$

we obtain

$$m_{(q-1)n/3}\le {\left(\frac{1+t+\cdots +t^{q-1}}{t^{(q-1)/3}}\right)}^n.$$

Define

$$c_q=\underset{0<t<1}{\inf }\frac{1+t+\cdots +t^{q-1}}{t^{(q-1)/3}}.$$

Since the threshold $(q-1)/3$ lies below the mean $(q-1)/2$ of the uniform distribution on $\{0,1,\dots ,q-1\}$, the minimizing value has $t<1$, and therefore

$$c_q<q.$$

This is the large-deviation calculation invoked by Ellenberg and Gijswijt, with Rassoul-Agha and Seppalainen as a reference for the general framework (Rassoul-Agha & Seppalainen, 2015). Consequently

$$|A|\le 3c_q^n,$$

and the harmless factor $3$ can be absorbed into $(c_q+\epsilon {)}^n$ for asymptotic statements.

For $q=3$,

$$c_3=\underset{0<t<1}{\inf }\frac{1+t+t^2}{t^{2/3}}.$$

Differentiating the logarithm gives

$$\frac{1+2t}{1+t+t^2}-\frac{2}{3t}=0,$$

so

$$4t^2+t-2=0,t=\frac{\sqrt{33}-1}{8}.$$

Substitution gives

$$c_3<\mathrm{2.756.}$$

Therefore

$$r_3({\mathbb{F}}_3^n)=o(2.756^n).$$

Structural Interpretation

The proof is not a density-increment argument. It never finds a large subspace on which $A$ has increased density, and it does not use Fourier analysis. Its engine is the interaction of three finite-dimensional facts.

First, every function on ${\mathbb{F}}_q^n$ has a unique reduced polynomial representative. This makes polynomial degree a meaningful notion for arbitrary functions.

Second, low degree implies low rank after separating variables. The inequality

$$|u|+|v|\le d$$

forces at least one side to have degree at most $d/2$, so the associated matrix decomposes into few rank-one pieces.

Third, the progression-free hypothesis turns the matrix into a diagonal matrix. Rank then counts surviving diagonal entries, converting a combinatorial prohibition into a dimension bound.

The proof can be summarized as

$$\text{large }A\Rightarrow \text{many low-degree functions supported on }A\Rightarrow \text{one has large support}\Rightarrow \text{diagonal matrix of large rank},$$

but the same polynomial also yields a low-rank decomposition. The contradiction is quantitative, and the monomial count supplies the exponential constant.

Scope and Limitations

The bound is an exponential improvement, but it is not believed to be sharp. The result closed the exponential upper-bound question while leaving a large gap from Edel-type lower-bound constructions, which are around $2.2^n$ (Edel, 2004).

The argument also uses the finite-field model in an essential way. In $\mathbb{Z}/N\mathbb{Z}$, Behrend’s construction gives progression-free sets of size

$$N\exp (-C\sqrt{\log N}),$$

which is larger than $N^{1-\epsilon }$ for every fixed $\epsilon >0$ (Behrend, 1946). Thus no direct analogue of an exponentially small cap-set bound can hold for intervals or cyclic groups of large prime order.

The broader lesson is that the polynomial method becomes strongest when the ambient space has a finite algebraic coordinate system and when the forbidden configuration makes an evaluation matrix diagonal. In this sense, the Croot-Lev-Pach and Ellenberg-Gijswijt arguments introduced a mechanism distinct from the Roth-Meshulam Fourier-density-increment method (Croot, Lev & Pach, 2017; Ellenberg & Gijswijt, 2017; Meshulam, 1995).

Transferable Mechanisms

The reusable idea is rank from degree splitting. Whenever a polynomial in several groups of variables has low total degree, each monomial must be low-degree in at least one group. This converts degree constraints into rank constraints, exactly as in the Croot-Lev-Pach lemma and its Ellenberg-Gijswijt extension (Croot, Lev & Pach, 2017; Ellenberg & Gijswijt, 2017).

A second reusable idea is support through dimension. The proof does not explicitly construct a special polynomial by interpolation. It compares the low-degree space with the space of functions supported on $A$ and uses a maximal-support element. This is a useful way to turn dimension inequalities into a certificate.

A third reusable idea is diagonalization by forbidden configurations. The set $A$ is hard to count directly. Instead, the forbidden equation forces off-diagonal entries to vanish in a matrix indexed by $A$. Once the matrix is diagonal, rank becomes cardinality.

A fourth reusable idea is entropy after algebra. The algebraic part gives $|A|\le 3m_D$. The analytic part is only the coefficient estimate for $(1+t+\cdots +t^{q-1}{)}^n$, equivalently a large-deviation bound. This separation makes the proof portable: improve the algebraic certificate or improve the monomial count, and the final estimate changes transparently.

See Also

• on Green-Tao theorem: Another example where a sparse additive-combinatorial problem is solved by changing the ambient structure before invoking the central counting mechanism.
• on sum-product in finite fields via entropy: Shares the finite-field theme and the use of entropy-like inequalities to quantify algebraic expansion.
• on lower bounds for incidences: A contrasting polynomial-method setting where geometric incidence structure, rather than additive diagonalization, drives the argument.

References

🐻  Bateman, M. & Katz, N.H. 2012. New bounds on cap sets. Journal of the American Mathematical Society 25(2), 585–613.

🐻  Behrend, F.A. 1946. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America 32(12), 331–332.

🐻  Croot, E., Lev, V.F. & Pach, P.P. 2017. Progression-free sets in \mathbb Z₄ⁿ are exponentially small. Annals of Mathematics 185(1), 331–337.

🐻  Edel, Y. 2004. Extensions of generalized product caps. Designs, Codes and Cryptography 31(1), 5–14.

🐻  Ellenberg, J.S. & Gijswijt, D. 2017. On large subsets of \mathbb F_qⁿ with no three-term arithmetic progression. Annals of Mathematics 185(1), 339–343.

🐻  Meshulam, R. 1995. On subsets of finite abelian groups with no 3-term arithmetic progressions. Journal of Combinatorial Theory, Series A 71(1), 168–172.

🐻  Rassoul-Agha, F. & Seppalainen, T. 2015. A Course on Large Deviations with an Introduction to Gibbs Measures, American Mathematical Society,p.