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

arXiv: https://arxiv.org/abs/1712.02302 · HTML: https://mlsanity.com/paper/1712.02302/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2017.

## Built on by (most cited first, 2 of 2)

- [Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles](https://mlsanity.com/paper/2301.00074/) (2022)
- [Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication](https://mlsanity.com/paper/2307.06463/) (2023)

## Abstract (arXiv)

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 (mathbbZ/pmathbbZ)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 Sn cannot prove nontrivial bounds on ω when the embedding is via three Young subgroups---subgroups of the form Sk1 × Sk2 × dotsb × Skℓ---which is a natural strategy that includes all known constructions in Sn. 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.