New lower bounds for cap sets

New lower bounds for cap sets, Discrete Analysis 2023:20, 18 pp.

One of the best known problems in additive combinatorics, the cap set problem, asks how large a subset of $\mathbb F_3^n$ can be if it contains no non-trivial solutions to the equation $x+y+z=0$. (A trivial solution is one where $x=y=z$.) Such sets are known as cap sets. For a long time, the best known upper bound was due to Meshulam, who adapted the proof of Roth’s theorem on sets of integers without arithmetic progressions of length 3 to this context, obtaining a bound of $O(n^{-1}3^n)$. In the other direction, the set $\{0,1\}^n$ gives a lower bound of $2^n$, which had been improved to $c^n$ for a constant $c$ that is a little bigger than 2. In 2011 there was a breakthrough when the upper bound was improved by Bateman and Katz to one of the form $O(n^{-(1+c)}3^n)$, but this still left a big gap. Then in 2016, Croot, Lev and Pach posted a paper to arXiv obtaining an exponential improvement to the upper bound for an analogous problem in $\mathbb F_4^n$, which was followed swiftly by a paper by Ellenberg and Gijswijt that obtained an upper bound of the form $C^n$ for a constant $C<3$, showing that the best known lower bound was at least of the right form.

This paper concerns the lower bound. It is simple to show that if $A$ and $B$ contain no non-trivial solution to $x+y+z=0$, then neither does $A\times B$. Thus, to obtain a lower bound of $c^n$, it is enough to find some $k$ and a subset $A\subset\mathbb F_3^k$ such that $|A|\geq c^k$. Then $A^m\subset\mathbb F_3^{mk}$, so this gives a lower bound of $c^n$ when $n$ is a multiple of $k$ (and more generally it gives a lower bound of $(c-o(1))^k$). The example of $\{0,1\}^n$ mentioned above is of course the special case $k=1$ and $A=\{0,1\}$.

It is not all that easy to find a better example, but, as already mentioned, they exist. For instance, in 1970, Pellegrino found a subset of $\mathbb F_3^4$ of size 20, and since $20>2^4$, this is an improvement – it leads to a lower bound of $c^n$, where $c\approx 2.115$. Soon after that, it was shown by various authors that a construction from design theory yielded a cap set in $\mathbb F_3^6$ of size 112, which gave $c\approx 2.1955$. In 1994 this was improved by Calderbank and Fishburn, who used the same design theory construction but did not simply take a Cartesian product of many copies of it. They showed that one could take $c\approx 2.210147$.

In 2004, Edel improved further the methods of Calderbank and Fishburn, introducing a more complicated product construction that could be used to create larger examples. Edel reached $c\approx 2.217389$. Very roughly, Edel showed that under certain conditions a union of cap sets would be a cap set, and that cap sets satisfying the necessary conditions could sometimes be obtained.

This paper contains the first improvement to Edel’s bound, and thus the first improvement in nearly 20 years. In the first part of the paper, the author follows Edel’s methods closely, and obtains a new example in dimension 396, which already yields an improvement to $c\approx 2.2179$. Then in the second part, a new construction is introduced, which leads to a further improvement, this time to $c\approx 2.218$. The proof is obtained with the help of a SAT solver. The code that was used is available here.

It seems likely that for every $k$ and every set $A\subset\mathbb F_p^k$ there exists $r$ and a set $B\subset\mathbb F_p^r$ such that $|B|^{1/r}>|A|^{1/k}$, in which case the process of identifying better and better “starting examples” could never end. It would, however, be interesting if one could actually prove this, perhaps by finding some clever “twisted product” that takes an arbitrary example and produces a new example that does very slightly better than the more obvious Cartesian product. While this paper does not give a general construction of that type, it represents the first progress on the problem for a long time, and some of the ideas it introduces may turn out to be more generally useful.

Update (14/12/2023): A team based at DeepMind has developed a method called FunSearch, which uses large language models to write short computer programs that generate solutions to mathematical problems and searches for good ones. With this method, they have improved the constant to 2.2202.