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

Preprint · Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans

- Archive id: arxiv:1712.02302
- Published: 2017-12-06
- arXiv: https://arxiv.org/abs/1712.02302
- Source URL: https://arxiv.org/abs/1712.02302
- PDF: https://arxiv.org/pdf/1712.02302
- Provenance: arxiv

## 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 $(\\mathbb{Z}/p\\mathbb{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 $ω$ 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 $ω$ and methods for ruling them out.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.