Cap set

The 9 points and 12 lines of $\mathbb {Z} _{3}^{2}$, and a 4-element cap set (the four yellow points) in this space

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. 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.

A complete set of 81 cards isomorphic with those of the game Set showing all possible combinations of the four features. Considering each 3×3 group as a plane aligned in 4-dimensional space, a set comprises 3 cards in a (4-dimensional) row, with wrap-around. An example 20-card cap set is shaded yellow.

An example of this problem comes from the card game Set, a card game in which each card has four features (its number, symbol, shading, and color), each of which can take one of three values. The cards of this game can be interpreted as representing points of the four-dimensional affine space $\mathbb {Z} _{3}^{4}$, where each coordinate of a point specifies the value of one of the features. A line, in this space, is a triple of cards that, in each feature, are either all the same as each other or all different from each other. The game play consists of finding and collecting lines among the cards that are currently face up, and a cap set describes an array of face-up cards in which no lines may be collected..

One way to construct a large cap set in the game Set would be to choose two out of the three values for each feature, and place face up each of the cards that uses only one of those two values in each of its features. The result would be a cap set of 16 cards. More generally, the same strategy would lead to cap sets in $\mathbb {Z} _{3}^{n}$ of size $2^{n}$. However, in 1971, Giuseppe Pellegrino proved that Set has larger cap sets, consisting of up to 20 cards, and that this is the largest possible size for these sets. Pellegrino's solution for the four-dimensional cap-set problem also leads to larger lower bounds than $2^{n}$ for any higher dimension, which were further improved by Edel (2004) to approximately $2.2174^{n}$.

In 1984, Tom Brown and Joe Buhler proved that the largest possible size of a cap set in $\mathbb {Z} _{3}^{n}$ is $o(3^{n})$ as $n$ grows; loosely speaking, this means that cap sets have zero density. Péter Frankl, Ronald Graham, and Vojtěch Rödl have shown in 1987 that the result of Brown and Buhler follows easily from the Ruzsa - Szemerédi triangle removal lemma, and asked whether there exists a constant $c<3$ such that, indeed, for all sufficiently large values of $n$, any cap set in $\mathbb {Z} _{3}^{n}$ has size at most $c^{n}$; that is, whether any set in $\mathbb {Z} _{3}^{n}$ of size exceeding $c^{n}$ contains an affine line. This question also appeared in a paper published by Noga Alon and Moshe Dubiner in 1995. Same year, Roy Meshulam proved that the size of a cap set does not exceed $2\cdot 3^{n}/n$. Determining whether Meshulam's bound can be improved to $c^{n}$ with $c<3$ was considered one of the most intriguing open problems in additive combinatorics and Ramsey theory for over 20 years; see, for instance, blog posts on this problem by the Fields medalists Timothy Gowers and Terence Tao (in the latter post, Tao refers to this problem as "perhaps, my favorite open problem"). It was considered a major breakthrough when in 2011, Michael Bateman and Nets Katz improved the bound to $O(3^{n}/n^{1+\varepsilon })$ with a positive constant $\varepsilon$. The cap set conjecture was solved in 2016, when Ernie Croot, Vsevolod Lev, and Péter Pál Pach posted a preprint on a tightly related problem, that was quickly used by Jordan Ellenberg and Dion Gijswijt to prove an upper bound of $2.756^{n}$ on the cap set problem.

The solution to the cap set problem can also be used to prove a partial form of the sunflower conjecture, namely that if a family of subsets of an $n$-element set has no three subsets whose pairwise intersections are all equal, then the number of subsets in the family is at most $c^{n}$ for a constant $c<2$. The new upper bounds also imply lower bounds on certain types of algorithms for matrix multiplication.

The "cap set" terminology should be distinguished from other unrelated mathematical objects with the same name, and in particular from sets with the compact absorption property in function spaces as well as from compact convex co-convex subsets of a convex set.

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$. The proof is taken from

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

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.

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 just 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$

So the meaning is 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

• Games graph, a strongly regular graph derived from a five-dimensional projective cap set
• No-three-in-line problem, a problem of avoiding three elements in a line in a two-dimensional grid