Exponential bound on capsets

In affine geometry, a cap set is a subset of $\mathbb {Z} _{3}^{n}$ (an $n$-dimensional affine space over a three-element field) with no three elements in a line. See cap set for an introduction to the definitions and history of the problem. The cap set problem is the problem of finding the size of the largest possible cap set, as a function of $n$. The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ... (sequence A090245 in the OEIS).

Cap sets may be defined more generally as subsets of finite affine or projective spaces with no three in line, where these objects are simply called caps.

We prove here that for any prime power $p$, a subset $S\subset F_{p}^{n}$ that contains no arithmetic progression of length $3$ has size at most $c_{p}^{n}$ for some $c_{p}<p$. Thus we prove that caps are small. The proof is taken from

Tao, Terry (May 2016). "Symmetric version of capset". 

who reformulated the original argument which not only simplified the proof but also helped generalize it to many other results.

Proof idea

The method is reminiscent of the linear algebra or polynomial method in combinatorics. We will use the property of $S$ to build a function that on the one is as complicated as $S$, but on the other hand show it is not complicated, and thus conclude $S$ is small.

Fix a field $F$. Recall that for any set $X$ and $m\in X$, $\delta _{m}(x):X\to F$ is the function returning $1$ if $x=m$ and $0$ otherwise.

If $S\subset F^{n}$ contains no $3-AP$, then as functions $S\times S\times S\to F$

${\begin{aligned}\delta _{0^{n}}(x+z-2y)=\sum _{s\in S}\delta _{s}(x)\times \delta _{s}(y)\times \delta _{s}(z)\end{aligned}}$

The proof is then composed of showing the right side is as "complicated" as $S$, which we do in the next subsection, and later that the left side is simple, and thus concluding $S$ is small.

Slice rank

Fix a field $F$, and suppose we have arbitary finite sets $A_{1},..,A_{n}$. We can imagine any function $f:A_{1}\times A_{2}...\times A_{n}\to F$ as an $n$ dimensional cube containing elements of $F$, its sides being indexed by $A_{1},..,A_{n}$, and the value at $(a_{1},..,a_{n})$ being $f(a_{1},..,a_{n})$.

In the case $n=2$ this is a matrix, and we have its rank which measures its "complexity". One of the definitions of the rank of a matrix $A$ is the minimal $r$ so that $A$ can be written as the sum of $r$ rank 1 matrices. Translating this to our correspondence of matrices indexed by $X\times Y$ with functions $X\times Y\to F$, for $n=2$, a rank $1$ function $X\times Y\to F$ is one of the form $f(x,y)=s(x)t(y)$ for some functions $s:X\to F$, $t:Y\to F$. Thus rank for a function is the minimal $r$ so that

${\begin{aligned}f=\sum _{i=1}^{r}s_{i}(x)t_{i}(y)\end{aligned}}$

for functions $s_{i}:X\to F$, $t_{i}:Y\to F$.

If we try to generalize rank to larger $n$, a reasonable offer is to say the rank of $f:A_{1}\times ..\times A_{n}\to F$ is the minimal $r$ so that there is a decomposition

${\begin{aligned}f=\sum _{i=1}^{r}f_{i,1}(x_{1})f_{i,2}(x_{2})...f_{i,n}(x_{n})\end{aligned}}$

and indeed usually one refers to this as rank. It turns out we'll be interested in a similiar notion, that of slice rank, which is the minimal $r$ so that there is a decomposition

${\begin{aligned}f=\sum _{i=1}^{r}f_{i}(x_{j_{i}})g_{i}(x_{1},..,x_{j_{i}-1},x_{j_{i}+1},..x_{n})\end{aligned}}$

for $f_{i}:A_{i_{j}}\to F$, $g_{i}:A_{1}\times ..\times A_{j_{i}-1}\times A_{j_{i}+1}...\times A_{n}\to F$

Thus the meaning is that we're allowed separate one variable in each summand. Thus for $n=2$ this is the usual rank, but for larger $n$ it's at most the regular rank, but can be smaller.

We let $SR(f)$ denote the slice rank of $f$.

Lemma 1 - the function is complicated

Suppose $n\geq 2,A=A_{1}=A_{2}...=A_{n}$, and $f$ is a diagonal function, that is $f=\sum _{a\in A}c_{a}\delta _{a}(x_{1})\delta _{a}(x_{2})...\delta _{a}(x_{n})$ for constants $c_{a}\in F$, then $SR(f)=|\{c_{a}|c_{a}\neq 0\}|$.

Proof of Lemma 1

We may assume without loss of generality that all $c_{a}\neq 0$. The proof is by induction on $n$. The case $n=2$ is well known from linear algebra.

Suppose $f=\sum _{i=1}^{r}f_{i}(x_{j_{i}})g_{i}(x_{1},..,x_{j_{i}-1},x_{j_{i}+1},..x_{n})$, and let $I_{1},...,I_{n}\subset [r]=\{1,2,3..,r\}$ be the sets indicating for each variable which summands separated it so that $f=\sum _{j=1}^{n}\sum _{i\in I_{j}}f_{i}(x_{j})g_{i}(x_{1},..,x_{j-1},x_{j+1},..x_{n})$.

Suppose without loss of generality $|I_{n}|>0$. We can view each of $\{f_{i}|i\in I_{n}\}$ as vectors in $F^{|A|}$, and so we have an at least $|A|-|I_{n}|$ dimensional perpendicular vector space to $\{f_{i}|i\in I_{n}\}$. But if we have a $|A|-|I_{n}|\times |A|$ matrix of full rank, there is a $|A|-|I_{n}|\times |A|-|I_{n}|$ minor that is of full rank, and so we can find a vector that has at least $|A|-|I_{n}|$ nonzero entries in the perpendicular space. Call this vector\function $h:A\to F$.

Then take the equality ${\begin{aligned}\sum _{j=1}^{n}\sum _{i\in I_{j}}f_{i}(x_{j})g_{i}(x_{1},..,x_{j-1},x_{j+1},..x_{n})=\sum _{a\in A}c_{a}\delta _{a}(x_{1})\delta _{a}(x_{2})...\delta _{a}(x_{n})\end{aligned}}$

Now multiply both sides by $h(x_{n})$ and sum over $x_{n}\in A$, we then win by induction.

In particular we see

${\begin{aligned}\sum _{s\in S}\delta _{s}(x)\times \delta _{s}(y)\times \delta _{s}(z)\end{aligned}}$

has slice rank at least $|S|$

Lemma 2 - the function is simple

This is a beautiful and simple argument. We claim that

${\begin{aligned}\delta _{0^{n}}(x+z-2y)\end{aligned}}$

as a function $F_{p}^{n}\times F_{p}^{n}\times F_{p}^{n}\to F_{p}$ has low slice rank, and in particular it follows that the restriction to $S\times S\times S\to F_{p}$ has low slice rank. By low we mean $O(c_{p}^{n})$ for some $c_{p}<p$.

Proof of Lemma 2

We have in $F_{p}$ the identity $\delta _{0}(x)=1-x^{p-1}$.

Thus,

${\begin{aligned}\delta _{0^{n}}(x+z-2y)=\prod _{i=1}^{n}(1-(x_{i}+z_{i}-2y_{i})^{p-1})\end{aligned}}$

Opening the right side, we get a polynomial of degree $(p-1)n$ of degree at most $(p-1)$ in each variable. For each monomial, by an averaging argument it is of degree at most $(p-1)n/3$ in at least one of the three sets of variables $\{x_{1},..,x_{n}\},\{y_{1},..,y_{n}\},\{z_{1},..,z_{n}\}$.

Thus if we take for instance monomials of degree at most $(p-1)n/3$ in $\{x_{1},..,x_{n}\}$ we can group them by the exact $\{x_{1},..,x_{n}\}$ part of the monomial, and each of those becomes a function of the form $f(x)g(y,z)$. Thus we if we let $N$ be the number of those monomials of degree at most $(p-1)n/3$ in $\{x_{1},..,x_{n}\}$, then doing the same for $\{y_{1},..,y_{n}\},\{z_{1},..,z_{n}\}$, we find the slice rank of the function is at most $3\times N$ (for monomials who have degree less than $(p-1)n/3$ in more than on set of variables, arbitarily choose which one to use). Finally, the point is that $N\ll p^{n}$; we're trying to count integer solutions $a_{1}+a_{2}+...+a_{n}\leq {\frac {n(p-1)}{3}}$ with $0\leq a_{i}\leq p-1$. The total number of potential substitutions is $p^{n}$, and most substitutions don't work since if we take a random substitution one the expectation of $a_{1}+a_{2}+...+a_{n}$ is ${\frac {n(p-1)}{2}}$. This is formalized by using a concrete large deviation bound such as Chernoff bound.

Finishing the proof

The two lemmas together show $|S|\leq 3\times N=C\times c_{p}^{n}$ for some $c_{p}<p,0<C$.

As a remark, by a tensor argument one may obtain $|S|\leq c_{p}^{n}$; indeed if one has some $S\subset F_{p}^{n}$ that is 3-progression free, then so is $S^{m}\subset F_{p}^{nm}$, and thus $|S|^{m}\leq C\times c_{p}^{mn}$, taking the mth root we get $|S|\leq C^{\frac {1}{m}}c_{p}^{n}$, now take $m\to \infty$

See also

• Sunflower