Worked solution: The polynomial method resolves the cap set problem (Croot-Lev-Pach, Ellenberg-Gijswijt, 2016)

Frequently asked questions

Why cap each variable's degree at

q-1

instead of allowing arbitrary powers?

Because $t^3 = t$ -type identities (more generally $t^q=t$ ) mean any higher power of a variable can be rewritten using lower powers when evaluated on $\mathbb{F}_q^n$ , so degree $q-1$ in each variable already captures every function; keeping this cap makes the evaluation map an exact isomorphism instead of merely surjective.

Source

Ernie Croot, Vsevolod Lev, Péter Pál Pach; Jordan Ellenberg and Dion Gijswijt; slice-rank reformulation by Terence Tao, 2016

On large subsets of $\mathbb{F}_q^n$ with no three-term arithmetic progression

arXiv:1605.09223v1

Step 2 of 7: Sets as polynomials: the polynomial method's dictionary

Previous step Next step

In plain words

Over the field $\mathbb{F}_3$ , every element satisfies $t^3 = t$ (a tiny instance of Fermat's little theorem), so any function on $\mathbb{F}_3^n$ can be written uniquely as a polynomial where each variable's exponent is capped at $2$ . This turns a purely combinatorial question about a subset $A$ into an algebraic one about polynomials of a certain degree, opening the door to linear-algebra tools like rank and dimension.

m_d = \dim S_n^{\le d}

Detailed analysis

Ellenberg and Gijswijt (2017, opening lemma, generalising Croot-Lev-Pach) let $M_n$ be the set of monomials in $x_1,\ldots,x_n$ of degree at most $q-1$ in each variable, and $S_n$ the vector space they span; the evaluation map $S_n \to \mathbb{F}_q^{\mathbb{F}_q^n}$ sending a polynomial to its table of values is a linear isomorphism, since both sides have dimension $q^n$ . Restricting to total degree at most $d$ gives the subspace $S_n^{\le d}$ of dimension $m_d = \dim S_n^{\le d}$ , the key quantity that will measure how many polynomials of bounded complexity are available.

Terms in this step

Monomial space $S_n^{\le d}$: The vector space spanned by all monomials $x_1^{e_1}\cdots x_n^{e_n}$ with each $e_i \le q-1$ and total degree $\sum e_i \le d$ , of dimension $m_d = \dim S_n^{\le d}$ .