PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1712.02302v1math.GRcs.DSmath.CO

TL;DR

The paper asks which groups might support a group-theoretic proof that ω = 2, a search motivated by the approach's ability to capture known matrix-multiplication bounds. It develops slice-rank techniques using augmentation-ideal powers and rules out ω = 2 for bounded-exponent nilpotent groups under an additional condition. Its results narrow the search, while the bounded-exponent scope leaves large cyclic groups or their powers beyond these methods.

  • Problem

    The group-theoretic approach captures known upper bounds on ω, but identifying host groups and embeddings that prove ω = 2 remains elusive.

    Source: §1 · p. 2

  • Method

    The paper applies slice rank and treats powers of the augmentation ideal as a nonabelian replacement for degree-graded polynomial spaces.

    Source: §1.1 · p. 3

  • Results

    STPP constructions in bounded-exponent nilpotent groups satisfying a mild additional condition cannot prove ω = 2.

    Source: §1 · p. 2

  • Takeaways & Limitations

    These negative results narrow the search for groups amenable to proving ω = 2 through the group-theoretic approach.

    Source: §1 · p. 2

    The nilpotent-group result assumes bounded exponent; the methods do not rule out large cyclic groups or their powers.

    Source: §1 · p. 2

Abstract

from arXiv · show

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.

1. Introduction

The paper narrows the search for groups that could prove ω = 2 through the group-theoretic approach, which captures known matrix-multiplication bounds but leaves nonabelian hosts largely unexplored. It rules out important families and develops slice-rank and augmentation-ideal techniques for further bounds.

1. Introduction

  • The group-theoretic approach captures known upper bounds on ω, but finding nonabelian host groups for an embedding remains an open search problem.Earlier work ruled out STPP constructions in abelian groups of bounded exponent as a route to ω = 2.Source: §1 · p. 2
  • STPP constructions in bounded-exponent nilpotent groups satisfying a mild additional condition cannot prove ω = 2.The paper bounds their size by |G|^(1−ε) for a constant ε > 0; the bounded-exponent condition reflects limits in ruling out large cyclic groups or their powers.Source: §1 · p. 2

1.2. Related work.

  • The authors frame the negative results as narrowing the search while leaving extension to solvable groups an open problem.Nilpotent groups are just short of solvable groups in the taxonomy discussed; the paper describes interplay between positive and negative results as a research program.Source: §1 · pp. 2–3

1. Introduction

  • The paper also rules out proving ω = 2 in symmetric or alternating groups using three Young subgroups, without ruling out all STPP constructions there.This rules out a natural construction type rather than all constructions via the group-theoretic approach.Source: §1 · p. 3

1.1. Techniques.

  • Powers of the augmentation ideal serve as a nonabelian analogue of degree-graded polynomial spaces for bounding slice rank and STPP size.The dimensions of successive quotients I^k/I^(k+1) are key; a concentration inequality for these dimensions yields the nilpotent-group theorem.Source: §1.1 · p. 3

1.2. Related work.

  • The approach identifies bounded nilpotency class and p-degree growth as structural properties that can rule out ω = 2 for qualifying p-groups.The paper also extends slice-rank upper bounds from a normal subgroup to its parent group, applying this tool from p-groups to nilpotent groups.Source: §1.2 · p. 3

2. Preliminaries

The preliminaries connect group-algebra embeddings and STPP constructions to matrix-multiplication bounds, then use multiplicative matchings and slice rank to derive necessary conditions for proving ω = 2.

2.1. Multiplicative matchings.

  • A multiplicative matching comprises three indexed sequences of group elements, and its cardinality is the number n of indexed triples.The paper adopts “matching” terminology for the nonabelian setting.Source: §2.1 · p. 4

2.2. The group-theoretic approach.

  • A triple product property lets subsets S, T, and U reduce |S| × |T| by |T| × |U| matrix multiplication to multiplication in C[G], whose irreducible-representation dimensions govern the resulting bound on ω.The group algebra decomposes into matrix algebras corresponding to the irreducible representations.Source: §2.2 · p. 4
  • STPP constructions combine several independent matrix multiplications in one group-algebra multiplication and capture the Coppersmith–Winograd result and its cited improvements [LG14].STPP generalizes the triple product property; packing bounds provide a necessary condition for proving ω = 2.Source: §2.2 · p. 5
  • An STPP family that misses the packing bound cannot imply ω = 2, while one meeting it yields nearly maximal multiplicative matchings in powers of its groups.The matching cardinality is |G|^N(1−ε) for arbitrarily small ε when |G| and N are sufficiently large.Source: §2.2 · pp. 5–6

2.3. Slice rank of tensors.

  • If a family’s group-multiplication tensors have slice rank at most |G|^(1−Ω(1)), its STPP constructions cannot prove ω = 2.Multiplicative matchings give a lower bound on slice rank, connecting the tensor criterion to the group-theoretic approach.Source: §2.3 · p. 6

3. Ruling out a large class of nilpotent groups

This section rules out exponent-two STPP constructions for several classes of bounded-exponent nilpotent groups, including groups satisfying conditions on their Sylow subgroups or bounded nilpotency class. Its arguments relate augmentation-ideal powers to slice-rank bounds, extending those bounds from normal subgroups to the whole group using characteristic ideals.

3.1. Slice rank of algebras.

  • STPP constructions in bounded-exponent p-group families cannot achieve ω = 2 when their p-degrees have bounded variance or linear expectation; bounded p-lower central series length also suffices.The bounded-length condition is a corollary of the bounded-variance result.Source: §3.1.1 · p. 8
  • For a p-group, dim(I^k) counts weighted-degree monomials of degree at least k, and slice rank is bounded by codim(I^a) + codim(I^b) + dim(I^(a+b)).The monomial weights are determined by the p-degrees; this links augmentation-ideal shrinkage to polynomial degree counts.Source: §3.1.1 · pp. 7–8
  • The bounds rule out ω = 2 for vector spaces (Z/pZ)^n, but do not rule it out for cyclic groups Z/p^nZ or (Z/p^kZ)^m when k grows.For Z/p^nZ the bound is only p^n/e^Ω(1), while the cited discussion says the bound is sharp; for (Z/p^kZ)^m, the e^Ω(m) factor is also sharp.Source: §3.1.1 · p. 9

3.3. Proof of the main p-group theorem (Theorem 3.8).

  • Under either p-degree condition, the proof obtains δG = Ω(n), making the general p-group slice-rank bound |G|^(1−Ω(1)) when the exponent is bounded.For p-degrees of length ℓ, the section also gives δG = Ω(n/ℓ), tight up to a log^2 ℓ factor.Source: §3.3 · pp. 10–11

3.4. General nilpotent groups: extending from normal subgroups.

  • For bounded-exponent nilpotent-group families, STPP constructions cannot achieve ω = 2 if every Sylow subgroup has p-degrees of bounded variance or linear expectation.The family-level conditions are required for each Sylow p-subgroup.Source: §3.4 · p. 11
  • STPP constructions in families of nilpotent groups of bounded exponent and bounded nilpotency class cannot achieve ω = 2.For such groups, each Sylow p-subgroup has bounded p-lower-central-series length, so Theorem 3.19 applies; the proof obtains a sublinear slice-rank bound and invokes Corollary 2.11.Source: §3.4 · pp. 11–12
  • Characteristic right ideals let slice-rank bounds transfer from a normal subgroup to its parent group.The proof extends subspaces across coset representatives and bounds the product space using the corresponding product inside the normal subgroup.Source: §3.4 · p. 12
  • The proof selects a Sylow subgroup whose order is at least |G|^Ω(1), then applies the relevant p-degree hypothesis to obtain characteristic augmentation-ideal powers with small codimensions and product dimension.The stated cases require either bounded variance or linear expectation of the p-degrees.Source: §3.4 · p. 12

4. Ruling out constructions using Young subgroups

The section examines whether three Young subgroups of S_n can support the group-theoretic approach to matrix multiplication. Pairwise-trivial intersections alone rule out reaching the sizes needed for ω = 2, while the hexagon construction improves on the triangle construction without overcoming that barrier.

4. Ruling out constructions using Young subgroups

  • For a triangular array with n = m(m + 1)/2 points, the three Young subgroups preserve lines parallel to its three sides.This construction satisfies the Triple Product Property.Source: §4 · p. 13
  • The triangle construction satisfies the Triple Product Property with three Young subgroups of size |S_n|^1/2−o(1), yet does not prove a nontrivial bound on ω.The groups are slightly too small for the relevant threshold, given the number of conjugacy classes of S_n.Source: §4 · p. 13
  • For equal-sized arrays of 91 points, the hexagon construction yields Young subgroups at least 1.869 times as large as those from the triangle construction.The hexagon has side length 6 and the triangle side length 13.Source: §4 · p. 13
  • The section leaves open whether the obstruction extends beyond Young subgroups or whether another construction in S_n can prove ω = 2.The proof also fails for a small change of setting: three largest-possible subgroups in S_n × S_n have pairwise trivial intersections.Source: §4 · pp. 13, 15
  • Pairwise-trivial intersections alone rule out three Young subgroups reaching the sizes needed for ω = 2.The required sets must each have size at least |G|^1/2−o(1).Source: §4 · pp. 12–13

5. Future directions

The future directions ask how far the negative results can extend and which groups might still host successful constructions. They also propose intermediate targets for both ruling out and finding constructions that could prove ω = 2.

5. Future directions

  • For bounded-exponent groups, a major negative-direction target is a slice-rank bound of |G|^(1−ε), first for solvable groups and ultimately for all finite groups.The paper identifies extending its nilpotent results beyond their additional hypotheses as a possible first step.Source: §5 · p. 15
  • A key open problem is extending the nilpotent-group results to groups without bounded nilpotency class, bounded variance, or linear expectation.Another proposed extension concerns solvable groups whose p-Sylow subgroups satisfy Theorem 3.8's hypothesis.Source: §5 · p. 15
  • The authors ask whether natural p-group families lacking bounded variance and linear expectation could still support large slice rank, multiplicative matchings, or TPP constructions.They also ask what bounds such constructions would give on ω.Source: §5 · p. 15
  • For S_n, proposed positive-direction steps range from slice-rank lower bounds to large multiplicative matchings and then TPP constructions.The suggested target set sizes are n!/e^o(√n) for slice rank and multiplicative matchings, and n!^1/2/e^o(√n) for TPP constructions.Source: §5 · p. 16

Appendix A. Tightness of slice rank bounds

The appendix establishes that the paper's slice-rank bounds are tight by relating border multiplicative matchings to slice rank and constructing such matchings in p-groups and nilpotent groups.

Appendix A. Tightness of slice rank bounds

  • The appendix states that the bounds in Theorems 3.8 and 3.19 are tight.It constructs large border multiplicative matchings to establish tightness.Source: Appendix A · pp. 17–18
  • A border multiplicative matching of cardinality m gives slice rank at least m for the group-multiplication tensor.The same lower bound holds in any characteristic.Source: Appendix A · p. 17
  • Every group of order p^n contains a border multiplicative matching of cardinality at least p^n/2^n.The construction uses a chain of normal subgroups with successive quotients isomorphic to Z/pZ.Source: Appendix A · p. 18
  • For nilpotent groups of order p^n r with gcd(p,r)=1, the slice rank in characteristic p is at least 3p^n r/2^(n+2).The proof combines a matching in the p-Sylow factor with one in the complement factor.Source: Appendix A · p. 18

Appendix B. Other results on slice rank of groups

This section introduces tools for studying slice rank in groups and identifies several settings where the rank is full. It also states that nontrivial upper bounds require working in characteristic dividing the group order.

Appendix B. Other results on slice rank of groups

  • The section introduces flat rank, a stronger variant of slice rank that is exactly additive.The stated results include full slice rank for matrix multiplication, semisimple group algebras, and cyclic groups in all characteristics.Source: Appendix B · p. 18
  • Matrix multiplication has full slice rank n^2, and every semisimple group algebra has full slice rank |G|.The section concludes that nontrivial upper bounds require working in characteristic dividing |G|.Source: Appendix B · p. 18
  • Every cyclic group has full slice rank in all characteristics.Source: Appendix B · p. 18

B.1. Flat rank.

Flat rank formalizes a lower-bound method based on restricting a tensor to a subspace and measuring the ranks of the resulting matrices. It is additive under direct sums and is full for diagonal tensors, square matrix multiplication tensors, and semisimple group algebras.

B.1. Flat rank.

  • Flat rank is the minimum of r + c over codimension-c subspaces on which every restricted tensor has matrix rank at most r.The section also characterizes it through decompositions with r + c bounded by the rank parameter.Source: §B.1 · p. 19
  • Flat rank is at most slice rank for every tensor.Source: §B.1 · p. 19
  • Flat rank is additive under direct sums of tensors.The proof combines representations for the upper bound and uses subspace projections and intersecting Zariski-open sets for the lower bound.Source: §B.1 · p. 20
  • The additivity argument’s latter part requires an infinite field, but the slice-rank bounds can be proved over an algebraically closed field without loss.The authors expect quantitative estimates to extend the argument to relevant finite-field settings.Source: §B.1 · p. 20
  • Diagonal tensors, square matrix multiplication tensors, and direct sums of matrix multiplication tensors have full flat rank and slice rank.In particular, for a semisimple group algebra F[G], both ranks equal |G|.Source: §B.1 · pp. 20–21
  • To obtain nontrivial upper bounds on slice-rank(MG), the field’s characteristic must divide |G|.Source: §B.1 · p. 21

B.2. The slice rank of cyclic groups is full.

Cyclic group algebras have full flat rank and slice rank in every characteristic. For cyclic p-groups, this makes the earlier slice-rank bound exact.

B.2. The slice rank of cyclic groups is full.

  • For every cyclic group G = Z/nZ, flat-rank(MG) = slice-rank(MG) = |G| in any characteristic.Source: §B.2 · p. 21
  • For cyclic p-groups, the earlier slice-rank bound is exactly correct.The earlier bound was already within a factor of 2.Source: §B.2 · p. 21
  • For G = Z/p^rZ over F_p, the flat rank of F_p[G] equals |G|.The proof uses the augmentation-ideal basis and shows that a codimension-c subspace contains a matrix of rank at least p^r − c.Source: §B.2 · pp. 21–22
  • The cyclic-group result follows from semisimplicity when the characteristic is coprime to n and additivity when it divides n.In the latter case, the group splits as Z/p^eZ × Z/mZ with p coprime to m.Source: §B.2 · p. 22
Loading 1712.02302v1…