Preprint
Which groups are amenable to proving exponent two for matrix multiplication?
arXiv.org
06 Dec 2017
Abstract
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}/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
$\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.
Metrics
13 Record Views
Details
- Title
- Which groups are amenable to proving exponent two for matrix multiplication?
- Creators
- Jonah BlasiakThomas ChurchHenry CohnJoshua A GrochowChris Umans
- Publication Details
- arXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021862255704721