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

Frequently asked questions

Why work over

\mathbb{F}_3

instead of ordinary integers?

The finite-field model $\mathbb{F}_3^n$ is a well-studied simplified analogue of $\mathbb{Z}/N\mathbb{Z}$ where the algebra is cleaner (every nonzero scalar is invertible), so progress here has historically guided, and been guided by, the harder integer case of Roth's theorem and Szemeredi's theorem.

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 1 of 7: The cap set problem: how big can a progression-free set be?

Previous step Next step

In plain words

Think of the game SET, played on cards described by $n$ ternary features: a cap set is a collection of cards with no three that form a legal "set" (the pattern that is forbidden is exactly a 3-term arithmetic progression $x+y+z=0$ in $\mathbb{F}_3^n$ ). For decades the best known upper and lower bounds on the largest possible cap set were painfully far apart, leaving open whether cap sets could occupy almost all of $\mathbb{F}_3^n$ or only an exponentially tiny sliver of it.

A \subseteq \mathbb{F}_3^n,\ \nexists\, x,y,z \in A \text{ distinct with } x+y+z=0 \implies |A| \le O(c^n),\ c < 3

Detailed analysis

Ellenberg and Gijswijt (2017, Introduction) study subsets $A$ of $\mathbb{F}_3^n$ that contain no three-term arithmetic progression, i.e. no distinct $x,y,z \in A$ with $x+y+z=0$ ; the maximal size of such a set is denoted $r_3(\mathbb{F}_3^n)$ . The trivial bound is $|A| \le 3^n$ , and the best previous upper bound, due to Bateman and Katz (2012), was only $O(3^n / n^{1+\epsilon})$ -- barely better than trivial, while the best lower-bound constructions gave sets of size around $2.2^n$ . The paper resolves the long-standing question of the exponential growth rate: it proves $|A| \le O(c^n)$ for an explicit constant $c \approx 2.756$ , strictly less than $3$ .

Terms in this step

Cap set: A subset $A$ of $\mathbb{F}_3^n$ containing no three distinct points $x,y,z$ with $x+y+z=0$ , i.e. no non-trivial three-term arithmetic progression.
Three-term arithmetic progression: Three elements $x,y,z$ with $y$ the average of $x$ and $z$ ; over $\mathbb{F}_3$ this is exactly the equation $x+y+z=0$ .

Knowledge used in this step

Szemerédi's theorem