The Cohn-Umans group-theoretic approach to matrix multiplication suggests embedding matrix multiplication into group algebra multiplication, and bounding $omega$ in terms of the representation theory of the host group. This framework is general enough to capture the best known upper bounds on $omega$ and is conjectured to be powerful enough to prove $omega = 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 $omega = 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 $omega = 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 $(mathbb{Z}/pmathbb{Z})^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 $omega$ when the embedding is via three Young subgroups---subgroups of the form $S_{k_1} times S_{k_2} times dotsb times S_{k_ell}$---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 $omega$ and methods for ruling them out.
Download