Cap set

A cap set is a subset $A\subseteq {\mathbb{F}}_3^n$ containing no three distinct points $x,y,z$ satisfying $x+y+z=0$. Equivalently, it contains no nonconstant three-term arithmetic progression.

A cap set in ${\mathbb{F}}_3^n$ has subset density $O(1/n)$. A Fourier analysis on a finite abelian group proof uses a hyperplane density increment for cap sets repeatedly: absence of nondiagonal zero-sum triples forces a large finite abelian Fourier coefficient, and hence a denser slice. This is a weaker bound than the Ellenberg–Gijswijt cap-set bound, but illustrates the density increment method.

Every Cartesian product of cap sets is a cap set. In characteristic three, $x+y+z=0$ with any two equal forces all three equal. A zero-sum triple in a Cartesian product of cap sets is therefore diagonal in every coordinate block, hence diagonal overall.

Suppose every cap set in ${\mathbb{F}}_3^n$ has cardinality at most $K{\theta }^n$, with $K$ independent of $n$. Applying this to the $k$-fold Cartesian product of a fixed cap set $A$ gives $|A{|}^k\le K{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves $|A|\le {\theta }^n$. More generally this argument applies to any class of finite objects closed under products with multiplicative size and additive dimension.

There is a constant $C<3$ such that every cap set in ${\mathbb{F}}_3^n$ has cardinality less than $C^n$.

For the polynomial method in combinatorics, useOver ${\mathbb{F}}_3$, this is the indicator function of $x+y+z=0$. On $A^3$ it is therefore a diagonal tensor with $|A|$ nonzero diagonal entries. Every monomial in its expansion has individual exponents at most two and total degree at most $2n$, so one of its three variable blocks has degree at most $2n/3$. Grouping terms according to such a block and using the slice rank of a diagonal tensor giveswhere $m_n$ is the number of $\alpha \in \{0,1,2{\}}^n$ with ${\sum }_i{\alpha }_i\le 2n/3$. If $X_i=1-{\alpha }_i$ are independent random variables uniform on $\{-1,0,1\}$, thenAny exponential upper bound for this tail probability gives $m_n\le (3-ϵ{)}^n$ and hence the result after absorbing the factor three and finitely many small dimensions into $C<3$.

The number $m_n$ of monomials in $n$ variables with each exponent at most two and total polynomial degree at most $\lfloor 2n/3\rfloor$ satisfiesFor each exponent vector $a$ counted on the left, $1\le 2^{2n/3-{\sum }_i{a}_i}$. Summing and then allowing all $a\in \{0,1,2{\}}^n$ gives $m_n\le 2^{2n/3}(1+1/2+1/4{)}^n$. The base has cube $343/16<27$, so it is strictly less than three. This elementary weighted count gives the exponential saving in the polynomial method in combinatorics without an unstated probability estimate.