On cap sets and the group-theoretic approach to matrix multiplication

Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, Chris Umans

Research output: Contribution to journalArticlepeer-review

70 Scopus citations

Abstract

In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent ω of matrix multiplication by reducing matrix multiplication to group algebra multiplication, and in 2005 Cohn, Kleinberg, Szegedy, and Umans proposed specific conjectures for how to obtain ω = 2. In this paper we rule out obtaining ω = 2 in this framework from abelian groups of bounded exponent. To do this we bound the size of tricolored sum-free sets in such groups, extending the breakthrough results of Croot, Lev, Pach, Ellenberg, and Gijswijt on cap sets. As a byproduct of our proof, we show that a variant of tensor rank due to Tao gives a quantitative understanding of the notion of unstable tensor from geometric invariant theory.

Original languageEnglish (US)
Pages (from-to)1-27
Number of pages27
JournalDiscrete Analysis
Volume3
Issue number2017
DOIs
StatePublished - 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On cap sets and the group-theoretic approach to matrix multiplication'. Together they form a unique fingerprint.

Cite this