Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



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

Author: Joshua A. Grochow
Journal: Bull. Amer. Math. Soc. 56 (2019), 29-64
MSC (2010): Primary 11B25, 51E22
Published electronically: October 1, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 11B25, 51E22

Retrieve articles in all journals with MSC (2010): 11B25, 51E22

Additional Information

Joshua A. Grochow
Affiliation: Department of Computer Science and Department of Mathematics, University of Colorado Boulder, Boulder, Colorado

Received by editor(s): April 22, 2018
Published electronically: October 1, 2018
Article copyright: © Copyright 2018 Joshua A. Grochow

American Mathematical Society