New applications of the polynomial method: The cap set conjecture and beyond

Abstract:

The cap set problem asks how large can a subset of $(\mathbb {Z}/3\mathbb {Z})^n$ be and contain no lines or, more generally, how can large a subset of $(\mathbb {Z}/p\mathbb {Z})^n$ be and contain no arithmetic progressions. This problem was motivated by deep questions about structure in the prime numbers, the geometry of lattice points, and the design of statistical experiments. In 2016, Croot, Lev, and Pach solved the analogous problem in $(\mathbb {Z}/4\mathbb {Z})^n$, showing that the largest set without arithmetic progressions had size at most $c^n$ for some $c < 4$. Their proof was as elegant as it was unexpected, being a departure from the tried and true methods of Fourier analysis that had dominated the field for half a century. Shortly thereafter, Ellenberg and Gijswijt leveraged their method to resolve the original cap set problem. This expository article covers the history and motivation for the cap set problem and some of the many applications of the technique: from removing triangles from graphs, to rigidity of matrices, and to algorithms for matrix multiplication. The latter application turns out to give back to the original problem, sharpening our understanding of the techniques involved and of what is needed for showing that the current bounds are tight. Most of our exposition assumes only familiarity with basic linear algebra, polynomials, and the integers modulo $N$.