[proofplan] We prove the Ellenberg-Gijswijt polynomial-method bound in a self-contained form. First we construct a polynomial tensor on $\mathbb{F}_3^n \times \mathbb{F}_3^n \times \mathbb{F}_3^n$ that detects the equation $x+y+z=0$ and becomes a diagonal tensor when restricted to a cap set. The diagonal tensor has slice rank $|A|$, while the polynomial has slice rank at most three times the number of monomials of degree at most $2n/3$ with each exponent at most $2$. An exponential estimate for that monomial count gives $|A| \leq 3\alpha^n$ for some $\alpha<3$; a finite adjustment of the constant gives a uniform bound $|A|\le c^n$ with $c<3$ for all $n\ge 1$. [/proofplan]

[step:Define slice rank and compute the rank of a diagonal tensor] Let $X$ be a finite set and let \begin{align*} T:X \times X \times X &\to \mathbb{F}_3 \end{align*} be a function. We say that $T$ has slice rank at most $r$ if it can be written as a sum of $r$ functions, each of one of the three forms \begin{align*} (x,y,z) &\mapsto f(x)g(y,z),\\ (x,y,z) &\mapsto f(y)g(x,z),\\ (x,y,z) &\mapsto f(z)g(x,y), \end{align*} where the displayed functions have values in $\mathbb{F}_3$. The slice rank of $T$, denoted $\operatorname{srank}(T)$, is the least such $r$. Let $B$ be a finite set, and let \begin{align*} D:B \times B \times B &\to \mathbb{F}_3 \end{align*} be the diagonal tensor defined by $D(a,b,c)=1$ if $a=b=c$ and $D(a,b,c)=0$ otherwise. We claim that \begin{align*} \operatorname{srank}(D)=|B|. \end{align*} The inequality $\operatorname{srank}(D)\le |B|$ follows from \begin{align*} D(a,b,c)=\sum_{u\in B}\mathbb{1}_{\{u\}}(a)\mathbb{1}_{\{(u,u)\}}(b,c). \end{align*} For the reverse inequality, suppose $D$ has slice rank $r$. By grouping the terms according to the singled-out variable, write \begin{align*} D(a,b,c)=\sum_{i=1}^{r_1} f_i(a)g_i(b,c)+\sum_{j=1}^{r_2} h_j(b)k_j(a,c)+\sum_{\ell=1}^{r_3} p_\ell(c)q_\ell(a,b), \end{align*} where $r_1+r_2+r_3=r$, where $f_i,h_j,p_\ell:B\to\mathbb{F}_3$ are functions, and where $g_i,k_j,q_\ell:B\times B\to\mathbb{F}_3$ are functions. Define the [vector space](/page/Vector%20Space) \begin{align*} V:=\left\{\lambda:B\to\mathbb{F}_3 : \sum_{a\in B}\lambda(a)f_i(a)=0\text{ for every }1\le i\le r_1\right\}. \end{align*} Since $V$ is the kernel of a [linear map](/page/Linear%20Map) from $\mathbb{F}_3^B$ to $\mathbb{F}_3^{r_1}$, the [rank-nullity theorem](/theorems/916) gives \begin{align*} \dim_{\mathbb{F}_3}V\ge |B|-r_1. \end{align*} We use the elementary support bound that every $d$-dimensional subspace of $\mathbb{F}_3^B$ contains a vector whose support has cardinality at least $d$. Indeed, choose a basis of the subspace and row-reduce the corresponding $d\times |B|$ matrix; the sum of the row-reduced basis vectors has nonzero entries in all pivot columns. Hence there exists $\lambda\in V$ such that, with \begin{align*} S:=\{b\in B:\lambda(b)\ne 0\}, \end{align*} one has $|S|\ge |B|-r_1$. Contract the decomposition of $D$ against $\lambda$ in the first variable, obtaining a function \begin{align*} M:B\times B&\to\mathbb{F}_3\\ (b,c)&\mapsto \sum_{a\in B}\lambda(a)D(a,b,c). \end{align*} Because $D$ is diagonal, $M(b,c)=\lambda(b)$ when $b=c$ and $M(b,c)=0$ when $b\ne c$. Thus, as the matrix indexed by $B\times B$, $M$ is diagonal with precisely $|S|$ nonzero diagonal entries, so $\operatorname{rank}(M)=|S|$. The same contraction applied to the right-hand side annihilates the first group by the definition of $V$. The remaining terms have the form \begin{align*} M(b,c)=\sum_{j=1}^{r_2}h_j(b)K_j(c)+\sum_{\ell=1}^{r_3}p_\ell(c)Q_\ell(b), \end{align*} where the functions $K_j:B\to\mathbb{F}_3$ and $Q_\ell:B\to\mathbb{F}_3$ are defined by \begin{align*} K_j(c)&:=\sum_{a\in B}\lambda(a)k_j(a,c),\\ Q_\ell(b)&:=\sum_{a\in B}\lambda(a)q_\ell(a,b). \end{align*} Each summand $h_j(b)K_j(c)$ or $Q_\ell(b)p_\ell(c)$ is a rank-one matrix, so subadditivity of matrix rank gives \begin{align*} |S|=\operatorname{rank}(M)\le r_2+r_3. \end{align*} Combining $|S|\ge |B|-r_1$ with this inequality yields $|B|\le r_1+r_2+r_3=r$. Therefore every slice decomposition of $D$ has at least $|B|$ slices, and hence $\operatorname{srank}(D)=|B|$. [/step]

[step:Build a polynomial tensor that becomes diagonal on a cap set] Let $A\subset \mathbb{F}_3^n$ be a cap set. For $x=(x_1,\dots,x_n)$, $y=(y_1,\dots,y_n)$, and $z=(z_1,\dots,z_n)$ in $\mathbb{F}_3^n$, define \begin{align*} P:(\mathbb{F}_3^n)^3 &\to \mathbb{F}_3\\ (x,y,z) &\mapsto \prod_{i=1}^{n}\left(1-(x_i+y_i+z_i)^2\right). \end{align*} In $\mathbb{F}_3$, an element $t$ satisfies $t^2=0$ if $t=0$ and $t^2=1$ if $t\ne 0$. Hence each factor $1-(x_i+y_i+z_i)^2$ equals $1$ exactly when $x_i+y_i+z_i=0$, and equals $0$ otherwise. Therefore \begin{align*} P(x,y,z)=1 \iff x+y+z=0. \end{align*} Restrict $P$ to $A\times A\times A$, and denote the restricted tensor by \begin{align*} P_A:A\times A\times A &\to \mathbb{F}_3. \end{align*} If $a,b,c\in A$ and $a+b+c=0$, then either $a=b=c$ or $a,b,c$ are three distinct elements forming a nontrivial three-term arithmetic progression in $\mathbb{F}_3^n$. Since $A$ is a cap set, the second possibility is excluded. Thus $P_A(a,b,c)=1$ exactly when $a=b=c$, and $P_A$ is the diagonal tensor on $A$. By the previous step, \begin{align*} |A|=\operatorname{srank}(P_A). \end{align*} [/step]

[step:Bound the slice rank by counting low-degree monomials] Let $M(n,d)$ denote the number of monomials \begin{align*} x_1^{\alpha_1}\cdots x_n^{\alpha_n} \end{align*} with each $\alpha_i\in\{0,1,2\}$ and $\alpha_1+\cdots+\alpha_n\le d$. We claim that \begin{align*} \operatorname{srank}(P_A)\le 3M(n,2n/3). \end{align*} Expand $P$ as a polynomial in the $3n$ variables $x_i,y_i,z_i$. Since every factor has total degree at most $2$, every monomial in the expansion has total degree at most $2n$. For any monomial appearing in the expansion, write its degree in the $x$-variables, $y$-variables, and $z$-variables as $d_x,d_y,d_z$. Then \begin{align*} d_x+d_y+d_z\le 2n. \end{align*} Hence at least one of $d_x,d_y,d_z$ is at most $2n/3$. Group the expanded monomials according to one chosen variable block whose degree is at most $2n/3$. The terms assigned to the $x$-block have the form \begin{align*} m(x)G_m(y,z), \end{align*} where $m$ ranges over monomials in $x_1,\dots,x_n$ of degree at most $2n/3$ with exponents at most $2$. There are at most $M(n,2n/3)$ such monomials. Thus all $x$-assigned terms contribute slice rank at most $M(n,2n/3)$. The $y$-assigned terms are grouped as functions of the form $m(y)G_m(x,z)$ with $m$ ranging over at most $M(n,2n/3)$ monomials, and the $z$-assigned terms are grouped as functions of the form $m(z)H_m(x,y)$ with $m$ ranging over at most $M(n,2n/3)$ monomials. Therefore \begin{align*} |A|=\operatorname{srank}(P_A)\le \operatorname{srank}(P)\le 3M(n,2n/3). \end{align*} [/step]

[step:Estimate the monomial count exponentially below $3^n$] Fix a real number $\rho$ with $0<\rho<1$. Since every monomial counted by $M(n,2n/3)$ has degree at most $2n/3$, we have \begin{align*} M(n,2n/3)\rho^{2n/3} &\le \sum_{\alpha\in\{0,1,2\}^n}\rho^{\alpha_1+\cdots+\alpha_n}\\ &=(1+\rho+\rho^2)^n. \end{align*} Thus \begin{align*} M(n,2n/3)\le \left(\frac{1+\rho+\rho^2}{\rho^{2/3}}\right)^n. \end{align*} Choose, for instance, $\rho=1/2$, and define \begin{align*} \alpha:=\frac{1+1/2+1/4}{(1/2)^{2/3}}. \end{align*} Then $\alpha<3$, because \begin{align*} \alpha<3 \iff \frac{7}{4}<3\cdot 2^{-2/3} \iff 7\cdot 2^{2/3}<12, \end{align*} and cubing the positive quantities gives \begin{align*} 7^3\cdot 2^2=1372<1728=12^3. \end{align*} Combining this estimate with the slice-rank bound gives \begin{align*} |A|\le 3\alpha^n. \end{align*} [/step]

[step:Absorb the fixed prefactor into a uniform constant below $3$] The preceding estimate gives exponential growth rate at most $\alpha<3$, but it contains the fixed prefactor $3$. Choose a real number $\beta$ with $\alpha<\beta<3$. Then there exists an integer $N\ge 1$ such that \begin{align*} 3\alpha^n\le \beta^n \end{align*} for every $n\ge N$. For the finitely many dimensions $1\le n<N$, every cap set $A\subset \mathbb{F}_3^n$ satisfies the strict inequality $|A|<3^n$. Indeed, $\mathbb{F}_3^n$ itself is not a cap set, since it contains the three distinct points $0,e_1,-e_1$, where $e_1=(1,0,\dots,0)$. Define \begin{align*} \gamma:=\max_{1\le n<N}\ \max\left\{|A|^{1/n}: A\subset \mathbb{F}_3^n \text{ is a cap set}\right\}. \end{align*} The maximum is taken over finitely many finite sets, so it exists, and the preceding strict inequality gives $\gamma<3$. Now define \begin{align*} c:=\max\{\beta,\gamma\}. \end{align*} Then $c<3$. If $n\ge N$, the estimate $|A|\le \beta^n\le c^n$ applies. If $1\le n<N$, the definition of $\gamma$ gives $|A|\le \gamma^n\le c^n$. Hence, for every $n\ge 1$ and every cap set $A\subset\mathbb{F}_3^n$, \begin{align*} |A|\le c^n \end{align*} with $c<3$, as required. [/step]