Cap set problem

Remarks

This bound is due to Ellenberg and Gijswijt, following a method of Croot, Lev and Pach for $(\Z/4\Z)^n$. The proof is an instance of the linear algebra method. The function $T(x, y, z) = 1$ if $x + y + z = 0$ and $0$ otherwise, restricted to $A \times A \times A$, is diagonal with $|A|$ nonzero entries, so its slice rank is $|A|$. Writing $T(x, y, z) = \prod_{i} \left(1 - (x_i + y_i + z_i)^2\right)$ and expanding, each monomial has degree at most $2n/3$ in one of the three variables, which gives slice rank at most $3 m_n$. Earlier bounds, by Fourier methods, were of the form $3^n / n^{1 + c}$.

Example: in $\F_3^2$ the set $\set{(0,0), (0,1), (1,0), (1,1)}$ is a cap set of size $4$. The sums of its four triples of distinct points are $(1,1)$, $(1,2)$, $(2,1)$ and $(2,2)$, none of which is $0$. Cap sets of size larger than $2.2^n$ are known for large $n$, so the base of the exponential lies between $2.2$ and $2.756$.

Going deeper

For a student

The cap set problem is the analogue in $\F_3^n$ of Roth's theorem on three-term arithmetic progressions, since three distinct points $x, y, z$ with $x + y + z = 0$ form an arithmetic progression in $\F_3^n$. The polynomial proof is very short and gives a power saving, which Fourier methods could not. It introduced the slice rank of tensors and led to new bounds on related problems, such as sunflower-free families and matrix multiplication barriers. In the integers, by contrast, there are sets without three-term progressions of size $N^{1 - o(1)}$, so the polynomial method does not transfer directly.