Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 147 / 4 / Solution

Assume first that $A\subseteq {\mathbb{F}}_3^n$ is a cap set. Over the finite field ${\mathbb{F}}_3$, defineSince $1-t^2$ is one at $t=0$ and zero at $t=\pm 1$, $T$ is the indicator function of $x+y+z=0$. If $x,y,z\in A$ satisfy this equation, then either they are all equal or they are three distinct points; the latter is excluded. Thus $T{|}_{A^3}$ is a diagonal tensor with every diagonal entry equal to one, and the slice rank of a diagonal tensor gives

Expand $T$ as a polynomial. Every variable has exponent at most two, and every monomial has total degree at most $2n$. Splitting a monomial's degree among its $x$-, $y$-, and $z$-blocks, at least one block has degree at most $2n/3$. Assign each monomial to one such block and group together terms with the same low-degree block monomial. Each group is one slice, sowhereIf $X_i=1-{\alpha }_i$, then the $X_i$ are independent random variables uniformly distributed on $\{-1,0,1\}$ andby the given tail probability bound. Consequently every cap set satisfies

Put $C_0=3e^{-1/24}<3$. For $n\ge 27$, the preceding bound is at most $C_0^n$. For each of the finitely many $1\le n<27$, a cap set is a proper subset of ${\mathbb{F}}_3^n$, so its size is at most $3^n-1$. We may therefore chooseEvery cap set then has size strictly below $C^n$. Equivalently,