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}/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. |
Year | Venue | Field |
---|---|---|
2017 | arXiv: Group Theory | Abelian group,Combinatorics,Embedding,Symmetric group,Algebra,Exponent,Group algebra,Representation theory,Augmentation ideal,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1712.02302 | 2 |
PageRank | References | Authors |
0.47 | 7 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jonah Blasiak | 1 | 13 | 3.22 |
Thomas Church | 2 | 2 | 0.81 |
Henry Cohn | 3 | 192 | 20.23 |
Joshua A. Grochow | 4 | 138 | 14.90 |
Christopher Umans | 5 | 879 | 55.36 |