Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Introduction

Almost $50$ years have passed since Strassen [Str69] first showed that $\omega\leq 2.81<3$. Since then, an impressive toolbox of techniques has been developed to obtain faster MM algorithms, culminating in the current best bound $\omega<2.373$ [LG14, Wil12]. Unfortunately, this bound is far from $2$, and the current methods seem to have reached a standstill. Recent research has turned to proving limitations on the two main MM techniques: the Laser method of Strassen [Str86] and the Group theoretic method of Cohn and Umans [CU03].

Both Coppersmith and Winograd [CW90] and Cohn et al. [CKSU05] proposed conjectures which, if true, would imply that $\omega=2$. The first conjecture works in conjunction with the Laser method, and the second with the Group-theoretic method. The first “technique limitation” result was by Alon, Shpilka and Umans [ASU13] who showed that both conjectures would contradict the widely believed Sunflower conjecture of Erdös and Rado.

Ambainis, Filmus and Le Gall [AFLG15] formalized the specific implementation of the Laser method proposed by Coppersmith and Winograd [CW90] which is used in the recent papers on MM. They gave limitations of this implementation, and in particular showed that the exact approach used in [CW90, DS13, LG14, Wil12] cannot achieve a bound on $\omega$ better than $2.3078$. The analyzed approach, the “Laser Method with Merging”, is a bit more general than the approaches in [CW90, DS13, LG14, Wil12]: in a sense it corresponds to a dream implementation of the exact approach.

Blasiak et al. [BCC+17a] considered the group theoretic framework for developing MM algorithms proposed by Cohn and Umans [CU03], and showed that this approach cannot prove $\omega=2$ using any fixed abelian group. In follow-up work, Sawin [Saw17] extended this to any fixed non-abelian group, and Blasiak et al. [BCC+17b] extended it to a host of families of non-abelian groups.

All limitations proven so far suffer from several weaknesses:

All three of [BCC+17a], [BCC+17b] and [AW18] show how some approach that can yield the current best bounds on $\omega$ cannot give $\omega=2$. None of the three works actually prove that one cannot use the particular tensor $CW_{q}$ used in recent work [CW90, DS13, Wil12, LG14] to show $\omega=2$. [AW18] proved this limitation for a rotated version of $CW_{q}$, but only for small $q$. Although [BCC+17a] and [BCC+17b] do not say which version their proofs apply to, in this paper we give evidence that $CW_{q}$ does not embed easily in a group tensor, and so it is likely that their proofs could also only apply to a rotated version of $CW_{q}$, and not to $CW_{q}$ itself. Moreover, even for the Coppersmith-Winograd-like tensors for which the known limitations do apply, it is only shown that for a fixed $q$ one cannot derive $\omega=2$. In particular, so far the lower bounds $\omega_{q}$ on what $\omega$ one can achieve for a value $q$ approached $2$. This left open the possibility to prove $\omega=2$ by analyzing $CW_{q}$ in the limit as $q\rightarrow\infty$.

All limitations proven so far are for very specific attacks on proving $\omega=2$. While the proofs of [AFLG15] apply directly to $CW_{q}$, they only apply to the restricted Laser Method with Merging, and no longer apply to slight changes to this. The proofs in [BCC+17a] and [BCC+17b] are tailored to the group theoretic approach and do not apply (for instance) to the Laser method on “non-group” tensors. While the limits in [AW18] do apply to a more general method than both the group theoretic approach and the Laser method, they only work for specific types of tensors, which in particular do not include $CW_{q}$.

All known approaches to matrix multiplication follow the following outline. First, obtaining a bound on $\omega$ corresponds to determining the asymptotic rank of the matrix multiplication tensor $\langle N,N,N\rangle$ (see the Preliminaries for a formal definition). Because getting a handle on this asymptotic rank seems difficult, one typically works with a tensor $t$ (or a tensor family) whose asymptotic rank $r$ is known. Then, to analyze the asymptotic rank of matrix multiplication, one considers large tensor powers $t^{\otimes n}$ of $t$ and attempts to “embed” $\langle N,N,N\rangle$ into $t^{\otimes n}$ for large $N$ without increasing the asymptotic rank. In effect, one is showing that the recursive $O(r^{n})$ time algorithm for computing $t^{\otimes n}$ can be used to multiply $N\times N$ matrices. This gives a bound on $\omega$ from $N^{\omega}\leq r^{n}$. The larger $N$ is in terms of $n$, the smaller the bound on $\omega$.

When embedding matrix multiplication into a tensor power $t^{\otimes n}$, we would like the embedding to have the property that if $a$ embeds in $b$, then the asymptotic rank of $a$ is upper bounded by the asymptotic rank of $b$. This way, our embedding gives an upper bound on the asymptotic rank of matrix multiplication, and hence on $\omega$. The most general type of embedding that preserves asymptotic rank in this way is a so called degeneration of the tensor $t^{\otimes n}$. A more restricted type of rank-preserving embedding is a so called monomial degeneration. The embeddings used in all known approaches for upper bounding $\omega$ so far are even more restricted zeroing outs. The laser method is a restricted type of zeroing out that has only been applied so far to tensors that look like matrix multiplication tensors or to ones related to the Coppersmith-Winograd tensor. The group theoretic approach gives clean definitions that imply the existence of a zeroing out of a group tensor into a matrix multiplication tensor. (See the preliminaries for formal definitions.)

We define three very general methods of analyzing tensors. There are no known techniques to analyze tensors in this generality.

The Solar Method applied to a tensor $t$ of asymptotic rank $r$ considers $t^{\otimes n}$ for large $n$, then considers all possible ways to zero out $t^{\otimes n}$ into a disjoint sum $\langle a_{1},b_{1},c_{1}\rangle\oplus\cdots\oplus\langle a_{m},b_{m},c_{m}\rangle$ of matrix multiplication tensors, giving a bound on $\omega$ from the asymptotic sum inequality of $\sum_{i=1}^{m}(a_{i}b_{i}c_{i})^{\omega/3}\leq r^{n}$, and then takes the minimum (or $\liminf$) of all bounds on $\omega$ which can be achieved in this way. This method already subsumes both the group theoretic method and the laser method. It is also much more general, as it is unclear whether the two known techniques produce the best possible zeroing outs even for specific tensors.

The Galactic Method replaces the zeroing out in the Solar Method with more powerful monomial degenerations. Since monomial degenerations are strictly more powerful than zeroing outs in general, this leads to even more possible embeddings of disjoint sums of matrix multiplication tensors.

The Universal Method again replaces the monomial degenerations of the Galactic Method with the even more powerful degenerations.

We note that the methods only differ when they are applied to the same tensor $t$. Trivially, any one of the methods can find the best bound on $\omega$ if it is “applied” to $t=\langle n,n,n\rangle$ itself. Starting with the same tensor $t$, however, the Universal method can in principle give much better bounds on $\omega$ than the Solar or Galactic methods applied to the same $t$.

For a tensor $T$, let $\omega_{g}(T)$ be the best bound on $\omega$ that one can obtain by applying the Galactic method to $T$. We define a class of generalized $CW_{q}$ tensors that contain $CW_{q}$ and many more tensors related to it, such as the rotated tensor used in [AW18]. Our main result is:

Thus, if one uses a generalized CW tensor, even in the limit and even if one uses the Galactic method subsuming all known approaches, one cannot prove $\omega=2$.

To prove this result, we develop several tools for proving lower bounds on $\omega_{g}(T)$ for structured tensors. Most are relatively simple combinatorial arguments but are still powerful enough to show strong lower bounds on $\omega_{g}(T)$.

We also study the relationship between the generalized $CW$ tensors and the structure tensors of group algebras. We show several new results:

New Tri-Colored Sum-Free Set Constructions. For every finite group $G$, there is a constant $c_{|G|}>2/3$ depending only on $|G|$ such that its $n$th tensor power $G^{n}$ has a tri-colored sum-free set of size at least $|G|^{c_{|G|}n-o(n)}$. For moderate $|G|$, the constant $c_{|G|}$ is quite a bit larger than $2/3$. To our knowledge, such a general result was not known until now.

For more details on our results, see Section 2 below.

Overview of Results and Proofs

In this section, we give an outline of our techniques which are used to prove our main result: that there exists a universal constant $c>2$ such that the Galactic method, when applied to any generalized Coppersmith-Winograd tensor, cannot prove a better upper bound on $\omega$ than $c$. We will assume familiarity with standard notions and notation about tensors related to matrix multiplication algorithms in this section; we refer the reader to the Preliminaries, in Section 3, where these are defined. For a tensor $T$, we will write $\omega_{g}(T)$ to denote the best upper bound on $\omega$ which can be achieved using the Galactic method applied to $T$.

These ‘corner terms’ are actually quite common in tensors which have been analyzed with the Laser Method. For instance, one of the main improvements of Coppersmith-Winograd [CW90] over Strassen [Str86] was noticing that the border rank expression of Strassen could be augmented by adding in three corner terms, resulting in the Coppersmith-Winograd tensor.

We give this proof in Section 6. In that section, we also show that there are natural tensors, like the Coppersmith-Winograd tensors used to give the best known upper bounds on $\omega$, which cannot even be written as sub-tensors of relatively small group tensors. In other words, the high-powered hammer that $\omega_{g}(T_{G})>2$ cannot be used to give lower bound for every tensor of interest, and other techniques like the combinatorial partitioning techniques from step 2 above are needed.

We show in Theorem 7.2 that for any finite group $G$, there is a monomial degeneration of $T_{G}$ into a generalized Coppersmith-Winograd tensor of parameter $|G|-2$. We will see that the Laser method applies just as well to any generalized Coppersmith-Winograd tensor of parameter $|G|-2$ as it does to the original $CW_{|G|-2}$, and so the best-known approach for finding matrix multiplication tensors as monomial degenerations of a tensor can be applied to any group tensor $T_{G}$ as well. Two important consequences of this are:

Preliminaries

Let $X=\{x_{1},\ldots,x_{q}\}$, $Y=\{y_{1},\ldots,y_{r}\}$, and $Z=\{z_{1},\ldots,z_{s}\}$ be three sets of formal variables. A tensor over $X,Y,Z$ is a trilinear form

The $n$th tensor power of a tensor $A$, denoted $A^{\otimes n}$, is the result of tensoring $n$ copies of $A$ together, so $A^{\otimes 1}=A$, and $A^{\otimes n}=A\otimes A^{\otimes(n-1)}$.

Intuitively, if $A$ is over $X,Y,Z$ and $B$ is over $X^{\prime},Y^{\prime},Z^{\prime}$, then the variables $\bar{x}_{ii^{\prime}},\bar{y}_{jj^{\prime}},\bar{z}_{kk^{\prime}}$ of $A\otimes B$ can be viewed as pairs of the original variables $(x_{i},x^{\prime}_{i^{\prime}})(y_{j},y^{\prime}_{j^{\prime}})(z_{k},z^{\prime}_{k^{\prime}})$. We will use this view in some of our proofs. For instance, when considering $A^{\otimes n}$ we will often view the $x$,$y$ and $z$ variables of $A^{\otimes n}$ as ordered $n$-tuples of $x$,$y$ and $z$ variables of $A$. Then we can discuss for instance, in how many positions of an $x$ variable of $A^{\otimes n}$, the variable $x_{i}$ of $A$ appears.

More generally, the rank of $T$, denoted $R(T)$, is the smallest nonnegative integer $m$ such that $T$ can be written as the sum of $m$ rank-one tensors.

and that each of these inequalities can be strictFor example, the first inequality is strict for the Coppersmith-Winograd tensor, and the second inequality is strict for the $2\times 2\times 2$ matrix multiplication tensor. Both of these tensors will be defined shortly.. One of the most common ways to show asymptotic rank upper bounds is to give border rank upper bounds, frequently using a tool called a ‘monomial degeneration’ which we will define shortly.

1.2 Sub-Tensors and Degenerations

We call a tensor $t$ a sub-tensor of a tensor $t^{\prime}$, denoted by $t\subseteq t^{\prime}$, if $t$ can be obtained from $t^{\prime}$ by removing triples from its support, i.e. for every $i,j,k$, either $t_{i,j,k}=t^{\prime}_{i,j,k}$, or $t_{i,j,k}=0$.

A special type of restriction is the so called zeroing out (also called combinatorial restriction): let $t$ be a tensor over $X,Y,Z$; $t^{\prime}$ is a zeroing out of $t$ if it is obtained by selecting $X^{\prime}\subseteq X,Y^{\prime}\subseteq Y,Z^{\prime}\subseteq Z$ and setting to zero all $x_{i}\in X\setminus X^{\prime},y_{j}\in Y\setminus Y^{\prime},z_{k}\in Z\setminus Z^{\prime}$; thus, $t^{\prime}$ is a tensor over $X^{\prime},Y^{\prime},Z^{\prime}$ and it equals $t$ on all triples over these sets.

Similarly to the relationship between rank and restriction, the border rank of $t$ is at most $r$ if and only if $t\trianglelefteq\langle r\rangle$.

1.3 Structural Properties of Tensors

A direct sum of two tensors $t$ and $t^{\prime}$ over disjoint variable sets $X,Y,Z$ and $X^{\prime},Y^{\prime},Z^{\prime}$, $t\oplus t^{\prime}$ is the tensor on variable sets $X\cup X^{\prime},Y\cup Y^{\prime},Z\cup Z^{\prime}$ which is exactly $t$ on triples in $X\times Y\times Z$, exactly $t^{\prime}$ on triples in $X^{\prime}\times Y^{\prime}\times Z^{\prime}$, and is on all other triples. In contrast, a regular sum $t+t^{\prime}$ could have $t$ and $t^{\prime}$ share variables.

2 The Matrix Multiplication Tensor and Methods for Analyzing ω𝜔\omega

The way in which the approaches differ is mainly in how the embedding into $t^{\otimes N}$ is obtained. All known approaches to embed a matrix multiplication tensor into a tensor power $t^{\otimes N}$ of some other tensor $t$ actually all zero out variables in $t^{\otimes N}$ and argue that after the zeroing out, the remaining tensor is a matrix multiplication tensor.

There are two main approaches for obtaining good bounds on $\omega$ via zeroing out $t^{\otimes N}$: the laser method and the group theoretic approach. We will describe them both shortly.

Zeroing out is a very restricted border-rank preserving operation on a tensor. The most general embedding of a matrix multiplication tensor into $t^{\otimes N}$ would be a potentially complicated degeneration of $t^{\otimes N}$. In fact, in this case, since every border rank $q$ tensor is a degenerationThis folklore fact follows from inverting the DFT over cyclic groups; see eg. [AW18, Section 3.1]. of the structure tensor for addition modulo $q$, $T_{q}=\sum_{i=0}^{q-1}\sum_{j=0}^{q-1}x_{i}y_{j}z_{i+j\bmod q}$, it would suffice to find a degeneration of $T_{q}^{\otimes n}$ into a large matrix multiplication tensor, for large $n$. Unfortunately, we currently do not have techniques to find good degenerations. We call this hypothetical method the Universal method.

Instead of considering arbitrary degenerations of $t^{\otimes n}$, we could instead consider monomial degenerations of $t^{\otimes n}$ into a large matrix multiplication tensor. This approach would subsume both the Laser Method and the Group Theoretic approach. Although again there are no known techniques to obtain better monomial degenerations than zeroing outs, monomial degenerations seem easier to argue about than arbitrary degenerations. We call the method of finding the optimal (with respect to bounding $\omega$) monomial degeneration of a tensor power into a matrix multiplication tensor, the Galactic method. (Reaching the end of our Galaxy is more feasible than seeing the entire Universe.) To complete the analogy, we can call the method using zeroing outs the Solar method (i.e. exploring the Solar System).

The Solar method subsumes the Group Theoretic Approach and the Laser Method, but is more general, and current techniques do not suffice to find the optimal zeroing-out of $t^{\otimes n}$ into matrix multiplication even for simple tensors. Our lower bounds will be not only for the Solar method, but also for the Galactic method which is even more out of reach for the current matrix multiplication techniques.

To be clear, the Solar method, Galactic method, and Universal method, give us successively more power when analyzing specific tensors. For example, it may be the case that for a specific tensor $T$, the Solar method applied to $T$ cannot get as low an upper bound on $\omega$ as the Universal method applied to $T$ can. This captures the known methods to get bounds on $\omega$ by using tensors like the Coppersmith-Winograd tensor or a group tensor, which we will define shortly. The three different methods will trivially give the same bound, $\omega$, when applied to matrix multiplication tensors themselves, but this is not particularly interesting: the entire point of these different methods is that the asymptotic rank of matrix multiplication tensors is not well-understood, and applying the methods to other tensors can help us get better bounds on it.

We will now describe the two approaches that follow the Solar method.

3 The Laser Method

Strassen [Str86] proposed a method for embedding a matrix multiplication tensor into a large tensor power of a starting tensor. He called it the Laser Method. In this method, we start with a tensor $t$ over variables $X$, $Y$, $Z$ of asymptotic rank $q$, where say $|X|=q$, so that $t$ has essentially optimal asymptotic rank. The variable sets are then partitioned into blocks: $X=X_{1}\cup\ldots\cup X_{a}$, $Y=Y_{1}\cup\ldots\cup Y_{b}$, $Z=Z_{1}\cup\ldots,Z_{c}$. Define by $t_{IJK}$ the sub-tensor of $t$ obtained by zeroing-out all variables $x\notin X^{I}$, $y\in Y^{J}$, $z\in Z^{K}$. We obtain a partitioning

Ideally, the constituent tensors $t_{IJK}$ should be matrix multiplication tensors, but this is not necessary.

In the large tensor power $t^{\otimes N}$, one then is allowed to zero out variables $\bar{x}_{i}$, $\bar{y}_{j}$ and $\bar{z}_{k}$ (removing all triples containing them). This zeroing out is not arbitrary, however: if some variable, say $\bar{x}_{i}$ is zeroed out, consider its index $i$ – it is a sequence of length $N$ of original indices $i,i,\ldots,i[N]$. Say that $x_{i[z]}\in X_{I(z)}$ (i.e. $I(z)$ is the block that $\bar{x}_{i}$ uses in its $z$th coordinate). Then every other $x$ variable, $\bar{x}_{i^{\prime}}$ for which $x_{i^{\prime}[z]}\in X_{I(z)}$ for all $z$, must be zeroed out as well. That is, variables with the same block sequence must either all be kept or all zeroed out.

One considers such possible zeroing outs and attempts to argue that one of them leaves exactly a direct sum of matrix multiplication tensors (possibly of different dimensions). Then one uses the asymptotic sum inequality of Schönhage [Sch81] to obtain a bound on $\omega$:

If $\bigoplus_{i=1}^{p}\langle k_{i},m_{i},n_{i}\rangle$ has border rank $\leq r$, and $r>p$, then $\omega\leq 3\tau$, where $\sum_{i=1}^{p}(k_{i}m_{i}n_{i})^{\tau}=r$.

Looking at Schönhage’s proof of the asymptotic sum inequality, however, we see that what it is actually doing is, taking a large tensor power of $\bigoplus_{i=1}^{p}\langle k_{i},m_{i},n_{i}\rangle$ and zeroing out variables to obtain independent copies of the same single matrix multiplication tensor, i.e. $F\odot\langle K,M,L\rangle$. Thus, we can think of the laser method as zeroing out $t^{\otimes N}$ in a block-preserving fashion, to obtain a copies of the same matrix multiplication tensor.

We now turn to the most successful implementation of the Laser Method: the Coppersmith-Winograd approach.

The Coppersmith-Winograd (CW) family of tensors is as follows: Let $q\geq 1$ be an integer.

Coppersmith and Winograd [CW90] followed the laser method. The tensors $CW_{q}$ have a natural partitioning $CW_{q}=T_{002}+T_{020}+T_{200}+T_{011}+T_{101}+T_{110}$, where $T_{002}=x_{0}y_{0}z_{q+1},T_{200}=x_{q+1}y_{0}z_{0},T_{020}=x_{0}y_{q+1}z_{0},T_{101}=\sum_{i=1}^{q}x_{i}y_{0}z_{i},T_{011}=\sum_{i=1}^{q}x_{0}y_{i}z_{i},T_{110}=\sum_{i=1}^{q}x_{i}y_{i}z_{0}$.

The partitioning is actually a block partitioning: The $T_{IJK}$ are obtained by blocking the $X$, $Y$ and $Z$ variables into three blocks: the indices $\{0,\ldots,q+1\}$ are blocked into block containing $\{0\}$, block $1$ containing $\{1,\ldots,q\}$ and block $2$ containing $\{q+1\}$, and then, block $I$ of $X$ (resp. $Y$ and $Z$) contains all $x_{i}$ (resp. $y_{i}$ and $z_{i}$) with $i$ in block $I$ of the indices. Then $T_{IJK}$ is the block tensor formed by the triples with $x$ variables in block $I$, $y$ variables in block $J$ and $z$ variables in block $K$.

The sub-tensors $T_{IJK}$ have two useful properties: (1) they are all matrix multiplication tensors, (2) for each $T_{IJK}$ above, $I+J+K=2$.

The Coppersmith-Winograd implementation of the laser method uses these properties together with sets excluding $3$-term arithmetic progressions (in conjunction with property (2) above) to decide which blocks of variables to zero out in $CW_{q}^{\otimes n}$. Since the zeroing out proceeds by zeroing out variables that have the same block sequences, and due to property (1) in the end one obtains a sum of matrix multiplication tensors, and due to the use of sets excluding $3$-term arithmetic progressions one can guarantee that in fact this is a direct sum of many large matrix multiplication tensors. Then one can use the asymptotic sum inequality to obtain a bound on $\omega$. To optimize the bound on $\omega$, one selects the best $q$, which ends up being $q=6$. Coppersmith and Winograd then achieve a slightly better bound on $\omega$ by analyzing the square $CW_{q}^{\otimes 2}$ in a similar way.

The later improvements on the Coppersmith-Winograd bounds by Stothers [DS13], Vassilevska W. [Wil12] and Le Gall [LG14] instead used the laser method with the CW tools starting from $CW_{q}^{\otimes 4},CW_{q}^{\otimes 8}$ and $\{CW_{q}^{\otimes 16}$ and $CW_{q}^{\otimes 32}\}$, respectively. Each new analysis used different, but related, blockings and partitionings, and each ultimately optimized the resulting bound on $\omega$ by picking $q=5$, and hence using $CW_{5}$ as the base tensor.

The Coppersmith-Winograd analysis works for any blocking of the variables of a tensor $t$ into blocks with integer names so that there exists an integer $b$ such that for every triple $(I,J,K)$ where $I$ is an $x$-block, $J$ is a $y$-block and $K$ is a $z$-block, $I+J+K=b$. For such a blocking, each constituent tensor $T_{IJK}$ should ideally be a matrix multiplication tensor itself. In recent applications of the method, the tensors $T_{IJK}$ need not be matrix multiplications, but then one needs to perform a Coppersmith-Winograd analysis on them to obtain a bound known as their Value which roughly says how good they are at supporting matrix multiplication.

The Coppersmith-Winograd approach doesn’t exploit very much about the block tensors $T_{IJK}$. In particular, one can replace each $T_{IJK}$ with another tensor $T^{\prime}_{IJK}$ over the same sets of variables $X_{I},Y_{J},Z_{K}$, as long as $T^{\prime}_{IJK}$ has the same “value”, and the modified tensor $T^{\prime}$ has the same border rank as $T$; the bound on $\omega$ the approach would give would be exactly the same! When $T_{IJK}$ is a matrix multiplication tensor $\langle a,b,c\rangle$, for instance, one can replace it with another matrix multiplication tensor $\langle a^{\prime},b^{\prime},c^{\prime}\rangle$ as long as the new tensor uses the same variables and $a^{\prime}b^{\prime}c^{\prime}=abc$, and as long as the produced full tensor has the same border rank. For instance, if we take $T_{110}=\sum_{i=1}^{q}\sum_{j=1}^{q}x_{i}y_{j}z_{0}$ and replace it with $\sum_{i=1}^{q}\sum_{j=1}^{q}x_{i}y_{q+1-i}z_{0}$, then we would get the rotated $CW_{q}$ tensor studied in [AW18]. This tensor still has rank $q+2$ and this gives the same upper bound on $\omega$ using the CW approach.

We can thus define a family of generalized CW tensors, $\underline{CW}_{q}$ as follows.

The family $\underline{CW}_{q}$ of tensors includes, for every permutation $\sigma\in S_{q}$, the tensor

We remark that the family above contains all tensors obtained from $CW_{q}$ by replacing $\sum_{i=1}^{q}(x_{i}y_{i}z_{0}+x_{i}y_{0}z_{i}+x_{0}y_{i}z_{i})$ with $\sum_{i=1}^{q}(x_{\tau(i)}y_{\sigma(i)}z_{0}+x_{\alpha(i)}y_{0}z_{\beta(i)}+x_{0}y_{\gamma(i)}z_{\delta(i)})$ for any choice of $\alpha,\beta,\gamma,\delta,\sigma,\tau\in S_{q}$.

The constituent tensor $T_{110}$ of $CW^{\sigma}_{q}$ is $\sum_{i=1}^{q}x_{i}y_{\sigma(i)}z_{0}$, which is still a $\langle 1,q,1\rangle$ tensor. Thus, for any such tensor from the family $\underline{CW}_{q}$, if its border rank is $q+2$, the Coppersmith-Winograd approach would give exactly the same bound on $\omega$, as with $CW_{q}$.

4 Group-theoretic approach

Cohn and Umans [CU03] pioneered a new group-theoretic approach for matrix multiplication. The idea is as follows. Take a group $G$ and consider its group tensor defined below. (Throughout this paper, we write groups in multiplicative notation.)

For any finite group $G$, the group tensor of $G$, denoted $T_{G}$, is a tensor over $X_{G},Y_{G},Z_{G}$ where $X_{G}:=\{x_{g}\mid g\in G\}$, $Y_{G}:=\{y_{g}\mid g\in G\}$, and $Z_{G}:=\{z_{g}\mid g\in G\}$, given by

Now suppose that we can find any degeneration (e.g. a zeroing out) of $T_{G}$ into $\bigoplus_{i=1}^{s}\langle k_{i},m_{i},n_{i}\rangle$. Then, by the asymptotic sum inequality we would get that

Cohn and Umans defined two properties of subsets of $G$ which yield a zeroing out of $T_{G}$ into matrix multiplication tensors: (1) the triple product property, so that any $G$ that satisfies it admits a zeroing out into a matrix multiplication tensor, and (2) the simultaneous triple product property, so that any $G$ that satisfies it admits a zeroing out into a direct sum of matrix multiplication tensors.

These properties provide the zeroing out, and the group representation provides the rank bound. The approach is extremely clean to define. The goal is then to find a group with known character degrees, satisfying one of the two triple product properties well, so that the matrix multiplication tensors one can get are large. Typically one works with a family of groups, parameterized by $n$ (as in $Z_{n}$ or $S_{n}$), and then one can pick the $n$ that optimizes the bound on $\omega$, or even take $n$ to $\infty$, e.g. when the groups correspond to tensor powers of some tensor.

We refer the reader to [Lan17, Section 3.5] for more exposition on the Group-theoretic approach and its interpretation as finding a zeroing out of group tensors.

5 Independent Tensors

In this paper, we will be especially interested in zeroing outs and monomial degenerations from tensors $T$ to independent tensors $\langle r\rangle$. We give a few relevant definitions here.

For a tensor $T$ over $X,Y,Z$, its independence number, $I(T)$, is the maximum size of an independent tensor which can result from a zeroing out of $T$. We similarly can define the asymptotic independence number of $T$ by

6 Tri-colored Sum-free Sets

A number of recent works (eg. [BCC+17a, BCC+17b, AW18]) have explored connections between lower bounds on matrix multiplication algorithms, and a notion from extremal combinatorics called a ‘tri-colored sum-free set’. In this paper, we will expand upon and generalize this connection as one of our tools for proving lower bounds on $\omega_{g}(T)$ for various tensors $T$.

For a group $G$, a tri-colored sum-free set in $G$ is a set $S\subseteq G^{3}$ of triples of elements of $G$ such that:

for all $(a,b,c)\in S$, we have $ab=c$, and

for all $(a_{1},b_{1},c_{1}),(a_{2},b_{2},c_{2}),(a_{3},b_{3},c_{3})\in S$ which are not all the same triple, we have $a_{1}b_{2}\neq c_{3}$.

In the literature, tri-colored sum-free sets are sometimes also called multiplicative matchings.

Let $G$ be any nontrivial finite group. There is a constant $\delta<1$ such that for any positive integer $n$, any tri-colored sum-free set in $G^{n}$ has size at most $(\delta|G|)^{n}$.

There are a number of families of groups $G$ where even stronger upper bounds than this are known; we refer the reader to the introduction of [BCC+17b] for an exposition of these bounds. In Section 6, we will show how Theorem 3.2 (and also the aforementioned stronger bounds) can be used to give lower bounds on the $\omega$ bound one can achieve using the Galactic method on a wide range of tensors $T$.

7 Comparison with Slice Rank Bounds

The work on limitations of the group-theoretic approach typically proceeds by giving upper bounds on the so-called ‘slice rank’ of the tensor $T_{G}$ of a group $G$. It is known [Tao16, TS16] that for any tensor $T$, if $T$ has a degeneration to an independent tensor $D$, then $|D|\leq\text{slice-rank}(T)$. Hence, for some tensor $T$, if one can show an upper bound on $\text{slice-rank}(T^{\otimes n})$ for all $n$, this yields an upper bound on $\omega_{u}(T)$, the value of $\omega$ which can be achieved using the Universal method applied to $T$.

For instance, the limitation result of Sawin [Saw17], Theorem 3.2 above, is proved by showing that for every fixed group $G$, there is a $\delta<1$ such that $\text{slice-rank}(T_{G}^{\otimes n})<\delta^{n}|G|^{n}$, which implies using the connection described above that $\omega_{u}(T_{G})>2$. In particular, this generalizes our Theorem 6.1 in which we show that Sawin’s result implies that $\omega_{g}(T_{G})>2$. Again, we note that since $\delta$ depends on $G$, this does not rule out achieving $\omega=2$ by using the Universal method applied to a sequence of groups whose lower bounds on $\omega_{u}$ approach $2$.

It is worth asking whether similar slice-rank upper bounds can be used to show a lower bound on $\omega_{u}(CW_{q})$ as well. Indeed, $CW_{q}$ is easily seen to have slice-rank at most $3$. However, slice-rank is not submultiplicative in general, and in fact it is known that $CW_{q}^{\otimes n}$ can have slice-rank much more than $3^{n}$. For instance, the fact that $\omega_{s}(CW_{5})\leq 2.373$ implies that $\text{slice-rank}(CW_{5}^{\otimes n})\geq 7^{2n/2.373-o(n)}\geq 5.15^{n-o(n)}$. It is not clear how to upper bound the slice-rank of $CW_{q}^{\otimes n}$ in general.

We refer to [BCC+17a, BCC+17b] for formal definitions related to slice-rank and matrix multiplication, as we won’t need slice-rank in this paper.

Matrix Multiplication and Independent Tensors

For a tensor $T$, let $\omega_{g}(T)\geq 2$ denote the best bound on $\omega$ that one can achieve using the Galactic Method with $T$. Hence, for all tensors $T$, we have $\omega\leq\omega_{g}(T)$.

Let $T$ be any tensor. For each positive integers $n,a,b,c$, let $F_{T,n,a,b,c}$ be the largest number of disjoint (sharing no variables) copies of $\langle a,b,c\rangle$ which can be found as a monomial degeneration of $T^{\otimes n}$. Then,

We use the following monomial degeneration of matrix multiplication tensors which slightly generalizes Strassen’s (from [Str86, Theorem 4]). We prove it here for completeness.

For any positive integers $a,b,c$, there is a monomial degeneration of $\langle a,b,c\rangle$ into an independent tensor of size $\frac{3}{4}\cdot\frac{abc}{\max\{a,b,c\}}$.

Assume first that $a=2m+1$, $b=2n+1$, and $c=2p+1$ are all odd, and assume without loss of generality that $c\geq a,b$. Recall that

For any term $x_{ij}y_{jk}z_{ki}\in\langle a,b,c\rangle$, we thus have $\alpha(x_{ij})+\beta(y_{jk})+\gamma(z_{ki})=(i+j+k)^{2}\geq 0$. We have equality, and thus the term is included in the result $D$ of the monomial degeneration, if and only if $i+j+k=0$. We can see that if $i+j+k=0$, then any two of $i,j,k$ determines the third, meaning any one of the variables $x_{ij},y_{jk},z_{ki}$ determines the other two, and so $D$ is indeed an independent tensor. Finally, there is a triple of $(i,j,k)$, $|i|\leq n,|j|\leq m,|k|\leq p$ with $i+j+k=0$ for each pair $(i,j)$, $|i|\leq n,|j|\leq m$ with $|i+j|\leq p$. Since $p\geq n,m$, we can see there are at least $\frac{3}{4}ab$ such pairs, as desired. The cases where $a,b,c$ are not all odd are similar. ∎

Finally we need a Lemma relating monomial degenerations to independent tensors and zeroing-outs to independent tensors, which is a special case of a result of [AW18]:

Suppose $A$ is a tensor which has a monomial degeneration into $f$ independent triples. Then, for positive integers $n$, $A^{\otimes n}$ has a zeroing out into $\Omega(f^{n}/n^{2})=f^{n-o(n)}$ independent triples.

Combining our results so far shows that matrix multiplication tensors have large asymptotic independence numbers:

Finally, we can prove the main idea behind our lower bound framework:

Let $T$ be over $X,Y,Z$. By Lemma 4.1, for every $\delta>0$, there are positive integers $n,a,b,c$ such that $T^{\otimes n}$ has a monomial degeneration to $F\odot\langle a,b,c\rangle$, where

Thus, by Lemma 4.4 and Lemma 4.2, we have that

Similarly, $a$ and $b$ have the same lower bound. Hence,

Now let $f=\lim_{n\rightarrow\infty}F^{1/n}$. Since $F\geq 1$, we get that $f\geq 1$. We obtain:

where the last inequality holds since $f\geq 1$ and $3-6(1-\delta)/\omega_{g}(T)\geq 0$. The result follows since the inequality above holds for all $\delta>0$. ∎

Partitioning Tools for proving lower bounds

We begin with some useful terminology and notation about partitioning tensors. Let $D$ be a sub-tensor of a tensor $T$, that is, it is obtained by removing triples from the support of $T$. If $T$ is over variable sets $X=\{x_{1},\ldots,x_{a}\},Y=\{y_{1},\ldots,y_{b}\},Z=\{z_{1},\ldots,z_{c}\}$, then $T^{\otimes n}$, and hence $D^{\otimes n}$, is over variable sets $\bar{X},\bar{Y},\bar{Z}$, where the variables in $\bar{X}$ are indexed by $n$-length sequences over $[a]$, the variables in $\bar{Y}$ are indexed by $n$-length sequences over $[b]$, the variables in $\bar{Z}$ are indexed by $n$-length sequences over $[c]$.

Let $T$ be a partitioned tensor $T=\sum_{i}P_{i}$, and let $D$ be a sub-tensor of $T^{\otimes n}$. Consider some $j\in\{1,\ldots,n\}$. We say that $D$ has an entry of $P_{i}$ in the $j$th coordinate if there is a triple $(\alpha,\beta,\gamma)$ in the support of $D$ for which $(\alpha_{j},\beta_{j},\gamma_{j})$ is in the support of $P_{i}$.

Since the $P_{i}$ partition the triples in the support of $T$, this is well-defined.

We begin with our first partitioning tool, which we interpret after the Theorem statement.

For any positive integer $n$, let $g_{n}$ be the largest integer such that $T^{\otimes n}$ has a zeroing out into an independent tensor $D_{n}$ of size $|D_{n}|=g_{n}$.

Set $T^{\prime}=T^{\otimes n}$ and $D^{\prime}=D_{n}$, and then for $j$ from $1$ to $n$ do the following process:

Currently $T^{\prime}=Q_{1}\otimes Q_{2}\otimes\cdots\otimes Q_{j-1}\otimes T^{n-j+1}$, and $|D^{\prime}|\geq q_{1}q_{2}\cdots q_{j-1}\cdot|D_{n}|$, and moreover, $D^{\prime}$ is a zeroing out of $T^{\prime}$. Since $T=A+B$ is a partitioning of $T$, it must be the case that either at least a $p$ fraction of the independent triples in $D^{\prime}$ have an entry of $A$ in their $j$th coordinate, or else at least a $1-p$ fraction of the independent triples in $D^{\prime}$ have an entry of $B$ in their $j$th coordinate. In the former case, set $Q_{j}=A$ and $q_{j}=p$, and in the latter case, set $Q_{j}=B$ and $q_{j}=1-p$. Recall that there is a zeroing out $z$ such that $z(T^{\prime})=D^{\prime}$. Now, replace the $j$th tensor in the product defining $T^{\prime}$ by $Q_{j}$, i.e. set $T^{\prime}=Q_{1}\otimes Q_{2}\otimes\cdots\otimes Q_{j}\otimes T^{n-j}$. By our choice of $Q_{j}$, we know that if we apply the same zeroing out $z$ to the new $T^{\prime}$, we get at least a $q_{j}$ fraction of the number of independent triples we had before, i.e. $|z(T^{\prime})|\geq q_{j}|D^{\prime}|$. Let $D^{\prime}$ be this new independent tensor $z(T^{\prime})$.

Once we have done this for all $j$, we are left with a tensor $\bigotimes_{j=1}^{n}Q_{j}$ which has a zeroing out into $|D|\cdot\prod_{j=1}^{n}q_{j}$ independent triples. Suppose that we picked $Q_{j}=A$ in $k$ of the steps, and hence picked $Q_{j}=B$ in the remaining $n-k$ of the steps. Hence, we have a zeroing out of $A^{\otimes k}\otimes B^{\otimes n-k}$ into $t:=g_{n}\cdot p^{k}\cdot(1-p)^{n-k}$ independent triples.

We will now give two different upper bounds on $t$. First, we will count $x$-variables. Since $A$ has only one $x$-variable, and $B$ has at most $q-1$ different $x$-variables, our tensor $A^{\otimes k}\otimes B^{\otimes n-k}$ must have at most $(q-1)^{n-k}$ different $x$-variables. Hence, $t\leq(q-1)^{n-k}$.

Combining the two upper bounds, we see that

We can see (by setting the two terms equal and solving for $k$) that the right-hand side of (1) is maximized when $k=pn$. We therefore get a bound independent of $k$ which must hold no matter what $k$ ends up being:

and since this holds for all positive integers $n$, it implies our desired bound. ∎

We next move on to our second tool. We show that if a tensor $T$ has a large asymptotic independence number, then there must be a way to define a probability distribution on the terms of $T$ such that each variable is assigned approximately the same probability mass.

$\sum_{x_{i}y_{j}z_{k}\in T}p(x_{i}y_{j}z_{k})=1$, and

For each fixed $i$, fixed $j$, or fixed $k$, $\sum_{x_{i}y_{j}z_{k}\in T}p(x_{i}y_{j}z_{k})\geq\frac{1}{q}-\sqrt{(\delta+\kappa)\ln(q)}.$

Before proving Theorem 5.2, we first prove a key Lemma:

For any integers $n\geq 1$ and $q\geq 2$, any real $\delta\geq 0$, and any tensor $T$ over $X,Y,Z$ with $|X|=q$ and $x_{1}\in X$, suppose $T^{\otimes n}$ has a zeroing out into an independent tensor $D$ of size $|D|=q^{(1-\delta)n}$. Let $S_{X}\subseteq X^{n}$ be the set of all $x$-variables used in terms in $D$, and let $\varepsilon=\sqrt{\delta\ln(q)}$. Then, at least $q^{(1-\delta)n}-q^{(1-2\delta)n}$ of the elements $x\in S_{X}$ have $x_{1}$ appear in between $(1/q-\varepsilon)n$ and $(1/q+\varepsilon)n$ of the entries of $x$.

Notice that the number of different $n$-tuples of variables of $X$ which contain $x_{1}$ exactly $i$ times is $\binom{n}{i}\cdot(q-1)^{n-i}$. Hence, the number of elements $x\in X^{n}$ which do not have $x_{1}$ appear in between $\frac{1-\varepsilon}{q}n$ and $\frac{1+\varepsilon}{q}n$ of the entries of $x$ is

Each term in $T^{\otimes n}$, and hence in $D$, corresponds to an $n$-tuple of terms from $T$. We thus define a probability distribution $p:X\otimes Y\otimes Z\to$ as follows: draw a uniformly random $\alpha\in\{1,\ldots,n\}$, then draw a uniformly random one of the $|D|$ independent triples from $D$ and return its entry in the $\alpha$th coordinate. Since this random process always returns a term from $T$, we have $\sum_{x_{i}y_{j}z_{k}\in T}p(x_{i}y_{j}z_{k})=1$.

Now, pick any fixed $i$ and consider the sum $p(x_{i}):=\sum_{x_{i}y_{j}z_{k}\in T}p(x_{i}y_{j}z_{k})$. Let $S_{X}\subseteq X^{n}$ be the set of all $X$-variables used in terms of $D$, so $|S_{X}|=|D|=q^{n(1-\delta-\delta^{\prime})}$. Then, $p(x_{i})$ can be alternatively characterized as the probability, upon drawing a random $\alpha\in\{1,2,\ldots,n\}$ and random $X_{s}\in S_{X}$, that the $\alpha$th coordinate of $X_{s}$ is $x_{i}$. By Lemma 5.1, setting $\varepsilon=\sqrt{(\delta+\delta^{\prime})\ln(q)}$, we know that for all but $q^{n(1-2\delta-2\delta^{\prime})}$ of the $X_{s}\in S_{X}$, the variable $x_{i}$ appears in between $(1/q-\varepsilon)n$ and $(1/q+\varepsilon)n$ of the entries of $X_{s}$. Hence,

By a symmetric argument, this same lower bound holds for all of the variables in $X,Y,$ and $Z$. Notice that as $n\to\infty$, the lower bound approaches $(1/q-\varepsilon)$, and $(1/q-\varepsilon)>1/q-\sqrt{(\delta+\kappa)\ln(q)}$. We can thus pick a sufficiently large $n$ so that the resulting probability distribution has all the desired properties. ∎

For one simple but interesting Corollary, we will show that in any tensor $T$ which has two ‘corner terms’ (see the Corollary statement for the precise meaning; we will see later that many important tensors have these corner terms), then no matter what the remainder of $T$ looks like, $T$ still does not have too large of an asymptotic independence number.

However, we know that $p(x_{q}),p(y_{q})\geq 1/q-\sqrt{(\delta+\kappa)\ln(q)}$, and so $p(z_{1})\geq 2/q-2\sqrt{(\delta+\kappa)\ln(q)}$. Similarly, applying the lower bound on $p(z_{i})$ for all $i>1$, we see that $p(z_{1})\leq 1-(q-1)(1/q-\sqrt{(\delta+\kappa)\ln(q)})$. Combining the two bounds shows that

Since this holds for all $\kappa>0$, it implies a lower bound on $\delta$ in terms of $q$ as desired. ∎

Let $T$ be a tensor over $X,Y,Z$. We say that $X^{\prime}\subseteq X$, $Y^{\prime}\subseteq Y$, $Z^{\prime}\subseteq Z$ are minimal for $T$ if $X^{\prime}$ is the minimal (by inclusion) subset of $X$ such that for each $x_{i}\in X\setminus X^{\prime}$, for all $j,k$, $T_{i,j,k}=0$, and similarly, $Y^{\prime}$ is the minimal subset of $Y$ such that for each $y_{j}\in Y\setminus Y^{\prime}$, for all $i,k$, $T_{i,j,k}=0$ and $Z^{\prime}$ is the minimal subset of $Z$ such that for each $z_{k}\in Z\setminus Z^{\prime}$, for all $i,j$, $T_{i,j,k}=0$.

If $T$ is a tensor, then the measure of $T$, denoted $\mu(T)$, is given by $\mu(T):=|X^{\prime}|\cdot|Y^{\prime}|\cdot|Z^{\prime}|$, where $X^{\prime},Y^{\prime},Z^{\prime}$ are minimal for $T$.

Suppose $X,Y,Z$ are minimal for $T$. Hence,

For our main tool, we can generalize this to partitioned tensors:

Let $s:=\sum_{i=1}^{k}(\mu(P_{i}))^{1/3}$, and for each $i\in\{1,2,\ldots,k\}$, let $p_{i}:=(\mu(P_{i}))^{1/3}/s$, so that $p_{i}\in$ and $\sum_{i=1}^{k}p_{i}=1$. For any positive integer $n$, let $D_{n}$ be the biggest independent tensor which can result from a zeroing out of $T^{\otimes n}$, and let $z$ be the zeroing out from $T^{\otimes n}$ to $D_{n}$.