Cap Sets

This chapter uses the counting lemma (2.2(a)) in the form of a dimension count on reduced polynomials, the rank lemma with the Croot–Lev–Pach expansion (2.9, 2.10), the support lemma (2.11), and the uniqueness of reduced representatives (Lemma 2.1(b)). It uses neither Schwartz–Zippel nor multiplicity. The bridge is the observation that on a cap set the matrix $(P(\mathbf x+\mathbf y))$ is diagonal.

6.1 The problem

Definition 6.1. A cap set in $\mathbb F_3^n$ is a subset containing no three distinct collinear points.

A line in $\mathbb F_3^n$ is a set $\{\mathbf a,\mathbf a+\mathbf r,\mathbf a+2\mathbf r\}$ with $\mathbf r\ne\mathbf 0$, so a cap set is the same as a set with no nontrivial three-term arithmetic progression, and the cap-set problem is the $\mathbb F_3^n$ analogue of Roth's problem on progressions in the integers. Its popular form is the card game Set, whose $81$ cards are the points of $\mathbb F_3^4$ and whose "sets" are the lines.

Lemma 6.2. Three points $\mathbf x,\mathbf y,\mathbf z\in\mathbb F_3^n$ are collinear if and only if $\mathbf x+\mathbf y+\mathbf z=\mathbf 0$. Moreover, if $\mathbf x+\mathbf y+\mathbf z=\mathbf 0$ and two of the three points coincide, then all three coincide.

Proof. If $\{\mathbf x,\mathbf y,\mathbf z\}=\{\mathbf a,\mathbf a+\mathbf r,\mathbf a+2\mathbf r\}$ then the sum is $3\mathbf a+3\mathbf r=\mathbf 0$. Conversely if $\mathbf x+\mathbf y+\mathbf z=\mathbf 0$ with $\mathbf x\ne\mathbf y$, put $\mathbf a=\mathbf x$, $\mathbf r=\mathbf y-\mathbf x\ne\mathbf 0$; then $\mathbf a+2\mathbf r=2\mathbf y-\mathbf x=-\mathbf y-\mathbf x=\mathbf z$, using $2=-1$ in $\mathbb F_3$. For the last assertion, if $\mathbf x=\mathbf y$ then $\mathbf z=-2\mathbf x=\mathbf x$. ∎

Thus $A$ is a cap set iff the only solutions of $\mathbf x+\mathbf y+\mathbf z=\mathbf 0$ with $\mathbf x,\mathbf y,\mathbf z\in A$ are the trivial ones $\mathbf x=\mathbf y=\mathbf z$.

Let $r(n)$ be the largest size of a cap set in $\mathbb F_3^n$. The trivial bounds are $2^n\le r(n)\le3^n$ (the lower bound from $\{0,1\}^n$, §6.5). Meshulam (1995) proved $r(n)=O(3^n/n)$ by adapting Roth's Fourier argument, and Bateman and Katz (2012) improved this to $O(3^n/n^{1+\varepsilon})$ with considerable effort. Whether $r(n)\le(3-\delta)^n$ for some $\delta>0$ was a well-known open problem until Croot, Lev, and Pach (2017) proved the analogous statement for $\mathbb Z_4^n$ in May 2016 and Ellenberg and Gijswijt (2017) adapted their argument to $\mathbb F_q^n$ within days. The proof below follows the symmetric formulation of Tao (2016).

6.2 The diagonal matrix

Let $V_d$ denote the space of reduced polynomials in $\mathbb F_3[x_1,\dots,x_n]$ of degree at most $d$, i.e. linear combinations of monomials $\mathbf x^{\boldsymbol\alpha}$ with $\boldsymbol\alpha\in\{0,1,2\}^n$ and $|\boldsymbol\alpha|\le d$. Its dimension is

$$m_d=\#\{\boldsymbol\alpha\in\{0,1,2\}^n:\ |\boldsymbol\alpha|\le d\},$$

with $m_d=0$ for $d<0$ and $m_d=3^n$ for $d\ge2n$. The set of reduced monomials is closed under division, so Lemma 2.10 applies to $V_d$ with $M_e=m_e$.

Lemma 6.3 (Symmetry). For every integer $d$, $3^n-m_d=m_{2n-d-1}$.

Proof. The map $\boldsymbol\alpha\mapsto(2,\dots,2)-\boldsymbol\alpha$ is a bijection of $\{0,1,2\}^n$ sending $|\boldsymbol\alpha|$ to $2n-|\boldsymbol\alpha|$; it carries $\{|\boldsymbol\alpha|\ge d+1\}$ onto $\{|\boldsymbol\alpha|\le2n-d-1\}$. ∎

Lemma 6.4. Let $A\subseteq\mathbb F_3^n$ be a cap set and let $P\in\mathbb F_3[\mathbf x]$ vanish at every point of $\mathbb F_3^n\setminus(-A)$, where $-A=\{-\mathbf a:\mathbf a\in A\}$. Then the matrix $M=\big(P(\mathbf x+\mathbf y)\big)_{\mathbf x,\mathbf y\in A}$ is diagonal, with diagonal entries $M_{\mathbf x\mathbf x}=P(-\mathbf x)$.

Proof. Let $\mathbf x\ne\mathbf y$ in $A$. If $\mathbf x+\mathbf y\in-A$, say $\mathbf x+\mathbf y=-\mathbf z$ with $\mathbf z\in A$, then $\mathbf x+\mathbf y+\mathbf z=\mathbf 0$ with $\mathbf x\ne\mathbf y$, so by Lemma 6.2 the three points are distinct and collinear, contradicting that $A$ is a cap set. Hence $\mathbf x+\mathbf y\notin-A$ and $P(\mathbf x+\mathbf y)=0$. On the diagonal, $\mathbf x+\mathbf x=2\mathbf x=-\mathbf x$. ∎

6.3 The Ellenberg–Gijswijt bound

Theorem 6.5 (Ellenberg and Gijswijt 2017; per-degree form). Let $A\subseteq\mathbb F_3^n$ be a cap set. Then for every integer $d$ with $0\le d\le2n$,

$$|A|\le m_{2n-d-1}+m_{\lfloor d/2\rfloor}+m_{\lceil d/2\rceil-1}\le m_{2n-d-1}+2m_{\lfloor d/2\rfloor}.$$

Proof. Let $W\subseteq V_d$ be the subspace of reduced polynomials of degree at most $d$ that vanish at every point of $\mathbb F_3^n\setminus(-A)$. Vanishing at a point is one linear condition, and there are $3^n-|A|$ points, so

$$\dim W\ge m_d-(3^n-|A|)=|A|-m_{2n-d-1}$$

by Lemma 6.3. Consider the evaluation map $W\to\mathbb F_3^{-A}$, $P\mapsto(P(\mathbf u))_{\mathbf u\in-A}$. It is injective: a $P\in W$ in its kernel vanishes on $-A$ and on the complement of $-A$, hence on all of $\mathbb F_3^n$, hence is zero by Lemma 2.1(b) since $P$ is reduced. So the image is a subspace of $\mathbb F_3^{-A}$ of dimension $\dim W$, and by Lemma 2.11 there is $P\in W$ with $P(\mathbf u)\ne0$ for at least $\dim W$ points $\mathbf u\in-A$.

By Lemma 6.4 the matrix $M=(P(\mathbf x+\mathbf y))_{\mathbf x,\mathbf y\in A}$ is diagonal with entries $P(-\mathbf x)$, so

$$\operatorname{rank}M=\#\{\mathbf x\in A:P(-\mathbf x)\ne0\}=\#\{\mathbf u\in-A:P(\mathbf u)\ne0\}\ge\dim W\ge|A|-m_{2n-d-1}.$$

By Lemma 2.10, $\operatorname{rank}M\le m_{\lfloor d/2\rfloor}+m_{\lceil d/2\rceil-1}$. Combining the two inequalities gives the theorem. ∎

Corollary 6.6 (Ellenberg and Gijswijt 2017). Every cap set $A\subseteq\mathbb F_3^n$ satisfies $|A|\le3\,m_{\lfloor2n/3\rfloor}$.

Proof. Put $D=\lfloor2n/3\rfloor$ and $d=2n-1-D$ in Theorem 6.5, so that $2n-d-1=D$. It remains to check $\lfloor d/2\rfloor\le D$ and $\lceil d/2\rceil-1\le D$, since $m_e$ is nondecreasing in $e$. Write $n=3k+r$ with $r\in\{0,1,2\}$. If $r=0$: $D=2k$, $d=4k-1$, $\lfloor d/2\rfloor=\lceil d/2\rceil-1=2k-1$. If $r=1$: $D=2k$, $d=4k+1$, both quantities equal $2k$. If $r=2$: $D=2k+1$, $d=4k+2$, $\lfloor d/2\rfloor=2k+1$ and $\lceil d/2\rceil-1=2k$. In every case both are at most $D$, so $|A|\le m_D+m_D+m_D$. ∎

Remark 6.7. The per-degree form is slightly sharper than the corollary in small dimensions. The values of $\min_d\big(m_{2n-d-1}+m_{\lfloor d/2\rfloor}+m_{\lceil d/2\rceil-1}\big)$ and of $3m_{\lfloor2n/3\rfloor}$ for $n\le12$ are tabulated in Appendix A (Table A.4); for $n=6$ they are $324$ and $504$, against the true value $r(6)=112$. The two coincide when $n\equiv1\pmod3$. Asymptotically the difference is a constant factor and does not affect the base of the exponential.

6.4 The constant

Lemma 6.8. For every $t\in(0,1]$ and every $D\le2n/3$,

$$m_D\le t^{-2n/3}(1+t+t^2)^n.$$

Proof. Since $t\le1$, for every $\boldsymbol\alpha$ with $|\boldsymbol\alpha|\le D$ we have $t^{|\boldsymbol\alpha|}\ge t^{D}\ge t^{2n/3}$. Hence

$$m_D=\sum_{|\boldsymbol\alpha|\le D}1\le t^{-2n/3}\sum_{|\boldsymbol\alpha|\le D}t^{|\boldsymbol\alpha|}\le t^{-2n/3}\sum_{\boldsymbol\alpha\in\{0,1,2\}^n}t^{|\boldsymbol\alpha|}=t^{-2n/3}(1+t+t^2)^n.\qquad\blacksquare$$

Theorem 6.9. Every cap set $A\subseteq\mathbb F_3^n$ satisfies $|A|\le3c^n$, where

$$c=\min_{0<t\le1}\frac{1+t+t^2}{t^{2/3}}=\frac{1+t_0+t_0^2}{t_0^{2/3}},\qquad t_0=\frac{\sqrt{33}-1}{8}=0.59307\ldots,\qquad c=2.755105\ldots$$

Proof. By Corollary 6.6 and Lemma 6.8, $|A|\le3\big(t^{-2/3}(1+t+t^2)\big)^n$ for every $t\in(0,1]$. Let $g(t)=\ln(1+t+t^2)-\tfrac23\ln t$ on $(0,1]$. Then

$$g'(t)=\frac{1+2t}{1+t+t^2}-\frac{2}{3t}=\frac{3t(1+2t)-2(1+t+t^2)}{3t(1+t+t^2)}=\frac{4t^2+t-2}{3t(1+t+t^2)},$$

which is negative for $0<t<t_0$ and positive for $t_0<t\le1$, where $t_0=(\sqrt{33}-1)/8$ is the positive root of $4t^2+t-2$. So $g$ has its minimum on $(0,1]$ at $t_0$, and $c=e^{g(t_0)}$. Numerically $t_0=0.593070\ldots$, $1+t_0+t_0^2=1.944803\ldots$, $t_0^{-2/3}=1.416650\ldots$, and $c=2.755105\ldots$ ∎

Remark 6.10. The bound of Lemma 6.8 is the Chernoff bound for the number of $\boldsymbol\alpha$ with $|\boldsymbol\alpha|\le2n/3$, and standard local limit estimates show it is sharp up to a factor $\Theta(\sqrt n)$: $m_{\lfloor2n/3\rfloor}=c^n\,\Theta(n^{-1/2})$. So Corollary 6.6 is $\Theta(c^n/\sqrt n)$ and the exponential base $c$ is exactly what the argument gives; the choice of $d$ in Corollary 6.6 is asymptotically optimal among all choices in Theorem 6.5, since $m_{2n-d-1}$ and $m_{d/2}$ are balanced precisely at $d\approx4n/3$. It is known that the base $c$ cannot be improved by the slice-rank method alone (Blasiak et al. 2017; Tao 2016).

6.5 Constructions and small cases

Lemma 6.11. $\{0,1\}^n$ is a cap set in $\mathbb F_3^n$, so $r(n)\ge2^n$. If $A\subseteq\mathbb F_3^a$ and $B\subseteq\mathbb F_3^b$ are cap sets, so is $A\times B\subseteq\mathbb F_3^{a+b}$; hence $r(a+b)\ge r(a)r(b)$.

Proof. If $\mathbf x,\mathbf y,\mathbf z\in\{0,1\}^n$ satisfy $\mathbf x+\mathbf y+\mathbf z=\mathbf 0$, then in each coordinate $x_i+y_i+z_i\in\{0,1,2,3\}$ is divisible by $3$, so it is $0$ or $3$, so $x_i=y_i=z_i$; thus $\mathbf x=\mathbf y=\mathbf z$ and the solution is trivial. For the product, suppose $(\mathbf a_j,\mathbf b_j)\in A\times B$ ($j=1,2,3$) are distinct with zero sum. Then $\mathbf a_1+\mathbf a_2+\mathbf a_3=\mathbf 0$ and $\mathbf b_1+\mathbf b_2+\mathbf b_3=\mathbf 0$. By Lemma 6.2 each of these triples is either all-equal or all-distinct; an all-distinct triple would be three collinear points of $A$ or of $B$, so both triples are all-equal, and then the three pairs coincide, a contradiction. ∎

The product construction from the known small values gives $r(n)\ge112^{n/6}\approx2.1955^n$. Edel (2004) obtained $2.2174^n$ by a more elaborate product of caps in $\mathbb F_3^{62}$ and $\mathbb F_3^{480}$, Tyrrell (2023) improved this to $2.218^n$, and a computer search guided by a language model (Romera-Paredes et al. 2024) found constructions giving $2.2202^n$. The exact values of $r(n)$ are known for $n\le6$:

The values $r(n)$ for $n\le5$ are surveyed by Bierbrauer and Edel (2002) and Edel, Ferret, Landjev, and Storme (2002); $r(6)=112$ is due to Potechin (2008). The values for $n\le3$ were reproduced by exhaustive search (Appendix A), and for $n=4$ the search found a cap of size $20$ without completing (Table A.3). The gap between the polynomial bound and the truth is a factor of about three at $n=6$, and it grows like $(c/2.2202)^n\approx1.24^n$ if the best constructions are near the truth.

6.6 Beyond $\mathbb F_3$

Ellenberg and Gijswijt prove the analogous bound over every finite field: for $q=p^k$ and $A\subseteq\mathbb F_q^n$ containing no three-term progression $\mathbf x,\mathbf x+\mathbf r,\mathbf x+2\mathbf r$ with $\mathbf r\ne\mathbf 0$, $|A|\le c_q^{\,n}$ for an explicit $c_q<q$. For odd $q$ the proof above transfers with one change: a progression is a solution of $\mathbf x+\mathbf z=2\mathbf y$, so one takes $P$ vanishing outside $2A$ instead of $-A$; the matrix $(P(\mathbf x+\mathbf z))_{\mathbf x,\mathbf z\in A}$ is then diagonal with entries $P(2\mathbf x)$, reduced polynomials have exponents in $\{0,\dots,q-1\}$, $m_d$ counts $\boldsymbol\alpha\in\{0,\dots,q-1\}^n$ with $|\boldsymbol\alpha|\le d$, and Lemma 6.3 becomes $q^n-m_d=m_{(q-1)n-d-1}$. The optimal $d$ is about $\tfrac23(q-1)n$ and the constant is $c_q=\min_{0<t\le1}t^{-(q-1)/3}(1+t+\dots+t^{q-1})$. In characteristic $2$ the equation $\mathbf x+\mathbf z=2\mathbf y$ degenerates and a different encoding is needed; Croot, Lev, and Pach's original argument for $\mathbb Z_4^n$ and Ellenberg and Gijswijt's treatment of $\mathbb F_{2^k}$ handle it, and I do not reproduce them.

The wider significance of the argument is that it bounds not only cap sets but the rank of a three-variable tensor, the indicator of $\mathbf x+\mathbf y+\mathbf z=\mathbf 0$, in the sense of slice rank introduced by Tao (2016); any set on which such a tensor is diagonal with nonzero diagonal has size at most the slice rank. This reformulation has since been applied to sunflower-free sets, to the group-theoretic approach to matrix multiplication (Blasiak et al. 2017), and elsewhere. The three-lemma architecture of this dissertation covers it exactly: the slice rank bound is Lemma 2.10, the diagonal structure is the bridge, and the counting is the dimension of $V_d$.