Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 16, 2017 | Published
Journal Article Open

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

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.

Additional Information

© 2017 Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans. Licensed under a Creative Commons Attribution License (CC-BY). Received 17 August 2016; Revised 5 January 2017; Published 16 January 2017. Supported by NSF grant DMS-14071174. Supported by NSF grant DMS-1350138, the Alfred P. Sloan Foundation, and the Frederick E. Terman Fellowship. Supported by a Santa Fe Institute Omidyar Fellowship. Supported by Ben Green's ERC Starting Grant 279438, Approximate Algebraic Structure and Applications. Supported by NSF grant DGE-1148900, Dr. Max Rössler, the Walter Haefner Foundation, and the ETH Zürich Foundation. Supported by NSF grant CCF-1423544 and a Simons Foundation Investigator grant. We thank the AIM SQuaRE program, the Santa Fe Institute, and Microsoft Research for hosting visits.

Attached Files

Published - 1605.06702v4.pdf

Files

1605.06702v4.pdf
Files (407.7 kB)
Name Size Download all
md5:4edc09ea93fdcc0fbb3e282860b3a443
407.7 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 25, 2023