Finite Matrix Multiplication Algorithms from Infinite Groups

In this paper, one of our main innovations is to extend the group-theoretic framework [14] to allow finite matrix multiplication algorithms from constructions in arbitrary – even infinite – groups. To achieve this, rather than using the entire group algebra $ℂ[G]$, which is infinite-dimensional when $G$ is infinite, we focus only on sets of functions $G\to ℂ$ that (1) are linearly computable from a finite set of finite-dimensional representations of $G$ (even when $G$ is infinite) and (2) “separate” the elements in the group algebra that are in the linear span of $X{Y}^{-1}Y{Z}^{-1}$ (the support of (1.1)), in a sense made precise below (Definition 2.1). Our first main theorem in this generalized framework is then:

It is even conceivable that this result could be used to improve the bounds from known constructions of TPPs in finite groups, by using only a subset of the group’s irreducible representations rather than all of them.

But perhaps the main payoff of Theorem A is that it allows, for the first time, the derivation of matrix multiplication algorithms from infinite groups. This opens a huge variety of potential constructions to explore, even beyond those in Lie groups that will be the focus of the rest of the paper.

Another main contribution in this paper is to develop a series of tools and techniques, and to identify key targets to aim for, for getting good constructions using Theorem A in Lie groups such as ${\text{GL}}_n(ℝ)$, ${\text{GL}}_n(ℂ)$, or the unitary group ${\text{U}}_n$. Lie groups are defined as groups that are also smooth manifolds, and where the group multiplication and inverse are continuous in terms of the manifold topology. In fact, all of our constructions in this paper will be in one of these three groups, though much of the machinery we develop works for general matrix Lie groups, and it would be interesting to explore constructions in other Lie groups such as symplectic groups, orthogonal groups, exceptional simple Lie groups, or nilpotent or solvable Lie groups.

Before coming to the constructions, we highlight how the framework of Theorem A allows us to take the analogy from [14, 9], and turn it into a formal implication whose conclusion is a bound on $\omega$. To briefly recall the analogy: elementary arguments show that any TPP triple in a finite group must satisfy $|X||Y||Z|\le {|G|}^{3/2}$, called the packing bound because of the nature of the proof. Because $\sum d_i^2=|G|$ in finite groups, it follows that any sequence of constructions that achieves $\omega =2$ via Theorem 1.1 (not our new Theorem A) must asymptotically meet the packing bound, in the sense that $|X||Y||Z|\ge {|G|}^{3/2-o(1)}$. The analogy studied in [14, 9] is to think of Lie subgroups of dimension $d$ as “roughly corresponding” to finite subsets of size $q^d$. Under this analogy, if $X_n,Y_n,Z_n$ are families of Lie subgroups of Lie groups $G_n$ that satisfy the TPP, then meeting the packing bound is analogous to the condition

A simple construction in the original Cohn–Umans paper [14, Theorem 6.1] shows this is indeed possible (with additional such constructions developed in [9]), and this construction forms the basis for a running example we will use throughout this paper to illustrate the development of our new framework.

• Running example in ${\text{GL}}_{𝒏}\mathbf{(}ℝ\mathbf{)}$

  Theorem 1.2 ([14, Theorem 6.1]).

  Let $G={\text{GL}}_n(ℝ)$ and let $X$ be the subgroup of lower unitriangular matrices, $Y={\text{O}}_n(ℝ)$ (the orthogonal matrices), and $Z$ be the subgroup of upper unitriangular matrices. Then the triple $X,Y,Z$ satisfies the TPP.

  The dimension of $G$ is $n^2$, and the dimension of each of the three subgroups is $n^2/2-n/2$, so this construction meets the packing bound in the sense of (1.2) [9].

But there still remains the issue of how to use such a construction, even in concert with Theorem A, to get upper bounds on $\omega$. And for this we require a deeper dive into representation theory, which will lead us to the key quantitative goals for these constructions.

In the case of the groups ${\text{GL}}_n(ℝ)$, ${\text{GL}}_n(ℂ)$, and ${\text{U}}_n$, rather than focusing on choosing arbitrary collections of representations to play the role of $R_{\text{sep}}$ in Theorem A, we can exploit a relationship between the representations of these groups and the set of all degree-$d$ polynomials. Namely, the irreducible representations of these groups are indexed by integer partitions into at most $n$ parts, and the matrix entries of the representations corresponding to partitions of $d$, taken all together, span precisely the set of all degree-$d$ polynomial functions on the group. Careful quantitative estimates then lead us to key targets for the degree of functions that separate out the elements of $X{Y}^{-1}Y{Z}^{-1}$ compared to the size of the finite TPP construction:

Note how our new framework (Theorem A) has allowed us to take the analogy above whereby $d$-dimensional subgroups correspond to finite sets of size $q^d$, and turn it into a theorem that actually implies a bound on $\omega$ out of any such construction, rather than merely being an analogy. However, in this setup, as $dimG=n^2$, we see that the bound we need on the size of the TPP triple is not $|X||Y||Z|\ge q^{(3/2-o_n(1))dimG}$ as suggested in the previous Lie analogy of the packing bound [14, 9], but is slightly tighter, of the form $q^{(3/2-o_n(1/n))dimG}$, and the example in Theorem 1.2 above falls short of this latter bound.

Our challenge is thus to find TPP constructions in ${\text{GL}}_n$ or ${\text{U}}_n$ that meet the bounds of Theorem B: three subsets in ${\text{GL}}_n$ or ${\text{U}}_n$ satisfying the TPP, of size at least $q^{n^2/2-o_n(n)}$, and admitting separating polynomials of degree at most $q^{1+o_q(1)}$.

Our third main contribution is to show how to very nearly meet the conditions of Theorem B, using border rank, Lie algebras, and invariant theory. We also believe these techniques will have further uses. Our main theorem coming out of these constructions is:

Note that this falls short of the conditions needed for Theorem B in only two ways: we get a construction of size $q^{(1/2)dimG-\mathrm{\Theta }(n)}$ where $G={\text{U}}_n$, whereas Theorem B would require both that the construction be in ${\text{GL}}_n$, and that it approach half the dimension just slightly faster, with sets of size $q^{(1/2)dim{\text{GL}}_n-o_n(n)}$, rather than our current $q^{(1/2)dim{\text{U}}_n-\mathrm{\Theta }(n)}$. In addition to the sizes being very nearly right, the degree bound does satisfy the degree bound required by Theorem B (even slightly better than is needed: we get $O(q)$ whereas Theorem B only needs degree at most $q^{1+o_q(q)}$).

While in principle all one needs here is a sequence of finite sets $X_q,Y_q,Z_q$ for infinitely many $q$, an appealing way to get such a sequence is to find Lie subgroups or submanifolds $X,Y,Z\subseteq {\text{GL}}_n(ℂ)$ – as in Theorem 1.2 – and then let $X_q$ be some nicely constructed finite subset of $X$, etc. For example, when $X$ is the subgroup of lower unitriangular matrices, we can take $X_q$ to be the the lower unitriangular matrices with entries in $[0,q]\cap \mathbb{Z}$. And indeed, this is how the construction of Theorem C proceeds.

To get our constructions, we will combine three additional ingredients on top of Theorems A and B: Lie algebras, border rank, and invariant theory. Here we give a brief overview of these ingredients and how they mix together.

If we restrict our attention to polynomials $p(M)$ that are invariant under left multiplication by $X$ and right multiplication by $Z^{-1}$, that is, $p(xM{z}^{-1})=p(M)$ for all $x\in X,z\in Z$, we can get direct access to the $B^{\prime }-B$ term above. Namely, if $p$ is such an invariant polynomial, then

where the first equality occurs because $\exp (\epsilon A)$ is in $X$ and $\exp (\epsilon C)$ is in $Z$, and $p$ is invariant under the action of $X$ and $Z$. We codify this idea into the following key lemma, which is used in the proof of Theorem C. We state it in a simplified form, which is not correct as stated but captures the spirit of a special case. See Lemma 2.11 for the full and correct statement.

Thus, once we have a TPP construction of the “right” dimension (e. g., according to Theorem B), Lemma D implies that instead of finding appropriate finite subsets of $X,Y,Z$ and a set of separating polynomials, to get $\omega =2$ all we have to do is find an appropriate finite subset of $Y$ and a single polynomial $p$ as in the lemma, whose degree is $O(q)$.

When $X$ and $Z$ are well-studied subgroups, the ring of their invariant polynomials is often well understood, and this represents a significant simplification of the construction problem. The full detail of Lemma 2.11 is more complicated, but the additional complications in the statement of the lemma give us even further simplifications of the construction problem, which we take advantage of in our constructions in the running example and in Section 3. We also expect the techniques of this lemma to have further uses for additional constructions in the future.

In Section 2.1 we give the necessary definitions and proof of Theorem A, and in Section 2.2 we give its border rank version. In Section 2.3 we discuss the needed background on the representation theory of ${\text{GL}}_n(ℂ)$ – much of which we can use in a black-box fashion – and prove Theorem B. In Section 2.4 we show how to combine invariant theory, border rank, and Lie algebras to simplify the construction task; the key here is Lemma 2.11. In Section 3 we use the preceding ideas to give the construction that proves Theorem C. Finally, in Section 4 we conclude with our outlook and several open problems suggested by our framework.

Throughout the development of the framework in Section 2, we continue the example from Theorem 1.2 as a running example, and we show how each piece of the framework can be realized in that case.

The full version of the paper contains complete proofs of all claims [10].

Let $G$ be a group – not necessarily finite – with finite subsets $X,Y,Z$ satisfying the TPP. Then we can embed matrix multiplication into the group algebra $ℂ[G]$ as in the case of finite groups. Note that $ℂ[G]$, where $G$ may be infinite, consists of formal sums ${\sum }_{g\in G}{\alpha }_{g}g$, but now where each such sum has at most finitely many nonzero terms. Multiplication is as in the finite case.

To multiply a complex matrix $A$ of size $|X|\times |Y|$ by a complex matrix $B$ of size $|Y|\times |Z|$, we follow the approach described in the introduction. Indexing $A$ by $X\times Y$ and $B$ by $Y\times Z$, we define elements

of $ℂ[G]$ and observe that, as in the finite group case, the TPP implies that

where $E\in ℂ[G]$ is supported on $X{Y}^{-1}Y{Z}^{-1}\setminus X{Z}^{-1}$.

However, as the group algebra is no longer finite-dimensional when $G$ is infinite, it is not immediately clear that the multiplication in the group algebra expressed in (2.1) can be carried out by a finite algorithm, even despite the fact that all the sums involved are themselves finite. One of our key new innovations is to introduce a new viewpoint on such a construction that will enable us to get a finite bilinear algorithm out of the above construction.

Such functions always exist, but for them to be useful in matrix multiplication algorithms we need them to be in some sense “simple.” To formulate the relevant notion – in which “simple” will ultimately imply “computable by smaller matrix multiplications” – we recall a standard definition from representation theory. Given a finite-dimensional representation $\rho :G\to {\text{GL}}_n(ℂ)$, a representative function of $G$ associated to $\rho$ (see, e. g., Procesi’s book [23, §8.2]¹¹1The notion of representative function we use here is fairly standard; if one consults Procesi’s book, one will see that his book works in the setting where $G$ is a topological group, and requires the representations involved to be continuous, but the definition we use here works just as well. When $G$ is a Lie group, as in our constructions later in the paper, the representations we use will in fact be continuous in the natural manifold topology on $G$ rather than the discrete topology.) is any function $G\to ℂ$ that is in the linear span of the functions $\{(g\mapsto \rho {(g)}_{i,j})\mid i,j\in [n]\}$. Note that if $\rho ,{\rho }^{\prime }$ are equivalent representations, they have the same set of representative functions. If $ℐ$ is a set of representations, we write $\text{RepFun}(ℐ)$ for the $ℂ$-linear span of all the representative functions of the representations in $ℐ$.

If $G$ is a finite group, we may take $R_{\text{sep}}=\text{Irr}(G)$, the set of all irreducible representations of $G$, as $\text{RepFun}(\text{Irr}(G))$ is the collection of all functions $G\to ℂ$ when $G$ is finite. In that case, we also have $D=|G|$, recovering the original theorem for finite groups [14, Theorem 4.1] as a special case of Theorem 2.2.

For this section, let $G$ be a (real or complex) Lie group. This includes familiar groups such as ${\text{GL}}_n(ℝ)$, ${\text{GL}}_n(ℂ)$, the orthogonal group ${\text{O}}_n$, and the unitary group ${\text{U}}_n$. Indeed, these examples will be the primary groups we use in our constructions later in the paper, although the framework laid out in this section is by no means limited to these particular examples.

For the purposes of this section, by a 1-parameter family of elements of $G$ we mean an analytic function $x:(0,\alpha )\to G$ for some $\alpha >0$. If $X=\{x_1,\mathrm{\dots },x_k\}$ is a collection of 1-parameter families $x_i$ and $\epsilon$ is in their domain of definition, then we write $X(\epsilon )=\{x_1(\epsilon ),\mathrm{\dots },x_k(\epsilon )\}$, which is just a finite subset of $G$.

Now, we take our representative functions to come from analytic representations of our Lie group, and, as in most things related to border rank, allow ourselves 1-parameter families of representative functions. Let ${ℂ}^{(0,\alpha )}$ denote the set of analytic functions $(0,\alpha )\to ℂ$. Given a set $ℐ$ of analytic representations of $G$, we write ${\text{RepFun}}_{\text{fam}}(ℐ)$ for the ${ℂ}^{(0,\alpha )}$-linear span of all the representative functions associated to any $\rho \in ℐ$.

Given three sets $X,Y,Z$ of 1-parameter families of elements of $G$, we say they satisfy the TPP if $X(\epsilon ),Y(\epsilon ),Z(\epsilon )$ satisfy the TPP for all $\epsilon$ in their domain of definition. Given such $X,Y,Z$, we may encode $\epsilon$-approximate matrix multiplication (à la border rank) into the group ring $ℂ[G]$ in a similar manner as before, but now parameterized by $\epsilon \in (0,\alpha )$. For an $|X|\times |Y|$ matrix $A$ and $|Y|\times |Z|$ matrix $B$, we define the following functions $(0,\alpha )\to ℂ[G]$:

Then

where $E(\epsilon )\in ℂ[G]$ is supported on $X(\epsilon )Y{(\epsilon )}^{-1}Y(\epsilon )Z{(\epsilon )}^{-1}\setminus X(\epsilon )Z{(\epsilon )}^{-1}$.

The proof is very similar to Theorem 2.2, but using border rank instead of rank, so we postpone it to the full version of the paper [10].

An appealing way to use the freedom of border rank is to first find a TPP construction of Lie subgroups $X,Y,Z$, and then to define finite subsets of those three using their Lie algebras, viz.:

where $\epsilon \to 0$ is the parameter we use for border rank. We will in fact show how to do this in a fairly generic way in Lemma 2.11 below, using some additional machinery that we develop first.

In this paper, our constructions will all take place in ${\text{GL}}_n$ or (slight variants of) the unitary group ${\text{U}}_n$, although the framework of Theorems 2.2 and 2.6 is much more general. These groups have some useful properties that will motivate some of the machinery we develop below – even though that machinery will also end up being more general – so we take a brief interlude to highlight the relevant properties of ${\text{GL}}_n$, before returning to the general abstract framework in the next section.

For both ${\text{GL}}_n$ and ${\text{U}}_n$, there is a natural correspondence between representations and polynomials of a given degree. By focusing on separating polynomials (instead of more general separating functions), this correspondence will allow our constructions to focus only on the degree of the separating polynomials. The upshot is that instead of thinking directly about what representations will comprise $R_{\text{sep}}$, we can focus solely on the degree of our separating polynomials when working in these groups.

In the rest of this section we review the relevant aspects of the representation theory of ${\text{GL}}_n$ and ${\text{U}}_n$, and extract from those the relevant target bounds on degree to get bounds on $\omega$. A standard reference for the representation theory of these groups is [19]. It is a standard fact in representation theory that the finite-dimensional representation theory of these two groups are essentially the same, and everything we say in this section will apply to both groups.

The irreducible polynomial representations $\rho$ of ${\text{GL}}_n(ℂ)$ and ${\text{U}}_n$ – where the entries of the matrix $\rho (g)$ are polynomials in the entries of the matrix $g$ – are indexed by integer partitions $\lambda =({\lambda }_1,\mathrm{\dots },{\lambda }_n)$ with at most $n$ parts, where ${\lambda }_1\ge {\lambda }_2\ge \mathrm{\cdots }\ge {\lambda }_n\ge 0$. The matrix coefficients of the irreducible representations indexed by partitions of $s$ span the functions from $G$ to $ℂ$ that are expressible as degree $s$ polynomials in the entries of ${\text{GL}}_n$. We write ${\text{Irr}}_s(G)$ to denote the set of (pairwise non-isomorphic) irreducible representations of $G$ indexed by partitions of the integer $s$.

The following bound will determine the target degree of the separating polynomials in our constructions, as in Corollary 2.8 below.

Although the result follows from some simple asymptotic analysis of standard results about the representation theory of ${\text{GL}}_n$, we could not find it in the literature, so we provide a full proof in [10].

Here and below it is helpful to think of $n$ as large but fixed, and $s$ growing independently of $n$.

Equivalently, if $|X|,|Y|,|Z|\ge q^{n^2/2-o_n(n)}$ and there are (border-)separating polynomials of degree at most $q^{1+o_q(1)}$, then $\omega =2$. See the full version of the paper for a proof [10].

Next we show that the Lie TPP construction of [14] (Theorem 1.2 above) in fact admits separating polynomials of degree $O(q^2)$. In Section 2.4, we will show how to use a border-rank version of our framework to construct finite sets $X,Y,Z$, whose size we can then compare to the degree of the separating polynomials as in Corollary 2.8.

• Separating polynomials for the running example in ${\text{GL}}_{𝒏}\mathbf{(}ℝ\mathbf{)}$

  We begin by describing a finite subset $Y_q$ of the orthogonal group ${\text{O}}_n$, with the property that the diagonal entries of matrices in the quotient set $Q(Y_q)$ have a limited number of possible values, in the sense formalized in the following lemma. Here we treat $n$ as fixed, so the implicit constant in $O(q^2)$ can depend on $n$.

  Lemma 2.9.

  For each positive integer $q$, there exists a subset $Y_q\subseteq {\text{O}}_n$ of cardinality at least $q^{n^2/2-(5/2)n}$, with the following property: for all $y,y^{\prime }\in Y_q$, if $y$ and $y^{\prime }$ agree in their first $i$ columns, then

  $$(y^T{y}^{\prime })[i+1,i+1]\in W_q,$$

  where $W_q\subseteq ℝ$ is a fixed finite set of cardinality $O(q^2)$.

  For a proof, see the full version of the paper [10].

  We remark that one might hope to improve the cardinality of $W_q$ to $O(q^{2-\epsilon })$ by replacing $V_i$ with a more cleverly chosen set of unit vectors with fewer distinct pairwise inner products. This would lead to an improved bound on the degree of the separating polynomials described in the following theorem, and if one could take $\epsilon =1$ this would yield separating polynomials of optimal degree. Unfortunately, this is impossible by the solution to the high-dimensional version of the Erdős distinct distances problem [25].

  Theorem 2.10.

  Let $G,X,Y,Z$ be as in Theorem 1.2, let $X_q\subseteq X$ be those lower unitriangular matrices whose below-diagonal entries are integers in $\{1,2,\mathrm{\dots },q\}$, let $Z_q\subseteq Z$ be those upper unitriangular matrices whose above-diagonal entries are integers in $\{1,2,\mathrm{\dots },q\}$, and let $Y_q\subseteq Y$ be the set of orthogonal matrices guaranteed by Lemma 2.9. Then there are separating polynomials for $X_q,Y_q,Z_q$ of degree $O(q^2).$

  For a proof, see the full version of the paper [10].

  Note that here we have $dimX=dimY=dimZ=(n^2-n)/2$, but for Corollary 2.8 we would need them to have dimension $n^2/2-o_n(n)$, and the separating polynomial we get has degree $O_q(q^2)$, but Corollary 2.8 needs degree at most $q^{1+o_q(1)}$. In Section 3 we give a construction of the same relative dimension (namely, $\frac{dimG}{2}-\mathrm{\Theta }(n)$) but with separating polynomials of degree $O(q)$, meeting the degree bound of Corollary 2.8.

In this section, we return to the case of a general matrix Lie group $G\subseteq {\text{GL}}_n(ℂ)$ or ${\text{GL}}_n(ℝ)$, and we show how to leverage invariant theory to construct separating polynomials whose degree is not too large, and that thus have a hope of meeting the degree bound of Corollary 2.8 in the case of $G={\text{GL}}_n(ℂ)$ or $G={\text{U}}_n$.

The key result in this section, Lemma 2.11, combines border rank and Lie algebras, as suggested at the end of Section 2.2, with a new ingredient from invariant theory. The lemma lets us “split” the construction of sets satisfying the TPP and (border-)separating polynomials into two parts: the first part only involves the first and third sets $X$ and $Z$ (essentially, a separating polynomial version of the “double product property” (DPP), which is that $x^{-1}{x}^{\prime }{z}^{-1}{z}^{\prime }=1$ iff $x=x^{\prime }$ and $z=z^{\prime }$)), and the second part involves only the middle set $Y$ and the ring of $XZ$-invariant polynomials. From one view, this lets us start with a $Y$, and “work backwards,” shifting the design task onto $X$, $Z$, and their invariant polynomials.

More specifically, Lemma 2.11 instantiates the following idea. Roughly, we would like to construct the separating polynomial $f_{x,z}$ as a product of three factors: one that is the indicator function of $x$ among the set $X$ (1 on $x$, zero on all other elements of $X$), one that is the indicator function of $z^{-1}$ among $Z^{-1}$, and one on that is the indicator function $p_0$ of $I$ among $Y^{-1}Y$. However, the issue here is that $f_{x,z}$, and hence these factors, does not really have separate access to these three parts: it only gets as input the product $x{y}^{-1}{y}^{\prime }{z}^{-1}$. Our initial motivation to use invariant polynomials was that if $p_0$ has the property that $p_0(x{y}^{-1}{y}^{\prime }{z}^{-1})=p_0(y^{-1}{y}^{\prime })$ for all $x\in X,z\in Z$, then it in fact does get direct access to only the $Y$-part of the input. Lemma 2.11 then gives generic machinery that, from such an $XZ$-invariant $p_0$, constructs a full set of (border-)separating polynomials, which have the correct degree if $p_0$ has the correct degree.

One advantage of this approach, in addition to separating out the design task associated with $Y$ more from the specification of $X$ and $Z$, is that it only necessitates the construction of at most three polynomials $p_0,p_X,p_Z$, rather than a whole set $\{f_{x,z}\}$ of $|X||Z|$-many polynomials, and the $p_X,p_Z$ polynomials are usually easy to construct if $X$ and $Z$ satisfy the DPP.

We now proceed with the technical details. By a polynomial on a matrix Lie group $G\subseteq {\text{GL}}_n(ℂ)$ or $G\subseteq {\text{GL}}_n(ℝ)$, we mean a function $G\to ℂ$ that can be expressed as a polynomial in the $n^2$ matrix entries $x_{ij}$ of elements of $G$, with complex coefficients,³³3Warning: for readers familiar with algebraic geometry, if $G$ is an algebraic group our definition here is not quite the same thing as an element of the coordinate ring of $G$. For example, when $G={\text{U}}_n$, we view $G$ as a subset of ${\text{GL}}_n(ℂ)$ and want to consider polynomials only in the $n^2$ matrix entries of these complex matrices, but as an algebraic group $G$ is a real algebraic group, with twice as many (real) coordinates, and this difference of a factor of 2 can actually be important. We believe there is a modification of our framework that works in the setting of algebraic groups, but leave that for future work. and similarly for a polynomial on the Lie algebra $\text{Lie}(G)\subseteq M_n(ℂ)$. By a 1-parameter family of polynomials we mean a polynomial in the $n^2$ matrix entries $x_{ij}$ of elements of $G$, with coefficients in ${ℂ}^{(0,\alpha )}$ for some $\alpha >0$.

Because we will use it frequently, we introduce the notation