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

Frequently asked questions

Did this resolve the exact value of

r_3(\mathbb{F}_3^n)

, or just its exponential rate?

Only the exponential rate: the theorem pins down that $r_3(\mathbb{F}_3^n)^{1/n}$ is bounded away from $3$ , closing a long-open qualitative question, but the precise constant in the exponent (between the $2.2^n$ lower-bound construction and the $c \approx 2.756$ upper bound) remains open.

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 7 of 7: Closing the loop: exponentially fewer cap sets than expected

Previous step Next step

In plain words

Putting Steps 5 and 6 together settles the exponential-rate question that had been open for decades: no cap set in $\mathbb{F}_3^n$ can have more than roughly $2.756^n$ elements, decisively less than the trivial $3^n$ . The same polynomial-method idea, discovered independently within days by two separate teams, also gave much better bounds for the related problem over $\mathbb{F}_q^n$ for every prime power $q$ .

|A| \le 3 \cdot (2.756)^n

Detailed analysis

Combining Step 5's inequality $|A| \le 3\, m_{(q-1)n/3}$ with Step 6's estimate $3e^{-I(2/3)} < 2.756$ of $m_{(q-1)n/3}$ at $q=3$ gives the final theorem: every cap set $A$ in $\mathbb{F}_3^n$ satisfies $|A| \le 3 \cdot (2.756)^n$ , resolving the exponential-rate question negatively (the rate is not $3$ ). Ellenberg and Gijswijt's short note (2017) formalises and generalises, to arbitrary finite fields $\mathbb{F}_q$ , the breakthrough polynomial method that Croot, Lev, and Pach (2016) had introduced weeks earlier for the closely related group $(\mathbb{Z}/4\mathbb{Z})^n$ ; Remark 1 of the paper notes the two authors developed the cap-set argument independently and essentially simultaneously.