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

Abstract

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.

Files

Additional details