A Caltech Library Service

Which groups are amenable to proving exponent two for matrix multiplication?

Blasiak, Jonah and Church, Thomas and Cohn, Henry and Grochow, Joshua A. and Umans, Chris (2017) Which groups are amenable to proving exponent two for matrix multiplication? . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The Cohn-Umans group-theoretic approach to matrix multiplication suggests embedding matrix multiplication into group algebra multiplication, and bounding ω in terms of the representation theory of the host group. This framework is general enough to capture the best known upper bounds on ω and is conjectured to be powerful enough to prove ω=2, although finding a suitable group and constructing such an embedding has remained elusive. Recently it was shown, by a generalization of the proof of the Cap Set Conjecture, that abelian groups of bounded exponent cannot prove ω=2 in this framework, which ruled out a family of potential constructions in the literature. In this paper we study nonabelian groups as potential hosts for an embedding. We prove two main results: (1) We show that a large class of nonabelian groups---nilpotent groups of bounded exponent satisfying a mild additional condition---cannot prove ω=2 in this framework. We do this by showing that the shrinkage rate of powers of the augmentation ideal is similar to the shrinkage rate of the number of functions over (Z/pZ)^n that are degree d polynomials; our proof technique can be seen as a generalization of the polynomial method used to resolve the Cap Set Conjecture. (2) We show that symmetric groups S_n cannot prove nontrivial bounds on ω when the embedding is via three Young subgroups---subgroups of the form S_(k₁)×S_(k₂)×⋯×S_(kℓ)---which is a natural strategy that includes all known constructions in S_n. By developing techniques for negative results in this paper, we hope to catalyze a fruitful interplay between the search for constructions proving bounds on ω and methods for ruling them out.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Additional Information:J.B.: Supported by NSF grant DMS-1600391. All authors also thank AIM for hosting a SQuaRE, during which this work was developed. T.C.: Supported by NSF grant DMS-1350138, the Alfred P. Sloan Foundation, and the Frederick E. Terman Fellowship. J.A.G.: Supported by a Santa Fe Institute Omidyar Fellowship and NSF grant DMS-1750319. C.U.: Supported by NSF grant CCF-1423544 and a Simons Foundation Investigator grant.
Funding AgencyGrant Number
Alfred P. Sloan FoundationUNSPECIFIED
Frederick E. Terman FellowshipUNSPECIFIED
Santa Fe InstituteUNSPECIFIED
Simons FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20191118-072853843
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99881
Deposited By: Tony Diaz
Deposited On:18 Nov 2019 16:22
Last Modified:18 Nov 2019 16:22

Repository Staff Only: item control page