Limits on the Universal Method for Matrix Multiplication

Introduction

One of the biggest open questions in computer science asks how quickly one can multiply two matrices. Progress on this problems is measured by giving bounds on $\omega$, the exponent of matrix multiplication, defined as the smallest real number such that two $n\times n$ matrices over a field can be multiplied using $n^{\omega+o(1)}$ field operations. Since Strassen’s breakthrough algorithm [Str69] showing that $\omega\leq\log_{2}(7)\approx 2.81$, there has been a long line of work, resulting in the current best bound of $\omega\leq 2.3729$ [Wil12, LG14], and it is popularly conjectured that $\omega=2$.

The key to Strassen’s algorithm is an algebraic identity showing how $2\times 2\times 2$ matrix multiplication can be computed surprisingly efficiently (in particular, Strassen showed that the $2\times 2\times 2$ matrix multiplication tensor has rank at most $7$; see Section 3 for precise definitions). Arguing about the ranks of larger matrix multiplication tensors has proven to be quite difficult – in fact, even the rank of the $3\times 3\times 3$ matrix multiplication tensor isn’t currently known. Progress on bounding $\omega$ since Strassen’s algorithm has thus taken the following approach: Pick a tensor (trilinear form) $T$, typically not a matrix multiplication tensor, such that

Powers $T^{\otimes n}$ of $T$ can be efficiently computed (i.e. $T$ has low asymptotic rank), and

$T$ is useful for performing matrix multiplication, since large matrix multiplication tensors can be ‘embedded’ within powers of $T$.

Combined, these give an upper bound on the rank of matrix multiplication itself, and hence $\omega$.

The most general type of embedding which is known to preserve the ranks of tensors as required for the above approach is a degeneration. In [AW18b], the author and Vassilevska Williams called this method of taking a tensor $T$ and finding the best possible degeneration of powers $T^{\otimes n}$ into matrix multiplication tensors the Universal Method applied to $T$, and the best bound on $\omega$ which can be proved in this way is written $\omega_{u}(T)$. They also defined two weaker methods: the Galactic Method applied to $T$, in which the ‘embedding’ must be a more restrictive monomial degeneration, resulting in the bound $\omega_{g}(T)$ on $\omega$, and the Solar Method applied to $T$, in which the ‘embedding’ must be an even more restrictive zeroing out, resulting in the bound $\omega_{s}(T)$ on $\omega$. Since monomial degenerations and zeroing outs are successively more restrictive types of degenerations, we have that for all tensors $T$,

These methods are very general; there are no known methods for computing $\omega_{u}(T)$, $\omega_{g}(T)$, or $\omega_{s}(T)$ for a given tensor $T$, and these quantities are even unknown for very well-studied tensors $T$. The two main approaches to designing matrix multiplication algorithms are the Laser Method of Strassen [Str87] and the Group-Theoretic Method of Cohn and Umans [CU03]. Both of these approaches show how to give upper bounds on $\omega_{s}(T)$ for particular structured tensors $T$ (and hence upper bound $\omega$ itself). In other words, they both give ways to find zeroing outs of tensors into matrix multiplication tensors, but not necessarily the best zeroing outs. In fact, it is known that the Laser Method does not always give the best zeroing out for a particular tensor $T$, since the improvements from [CW90] to later works [DS13, Wil12, LG14] can be seen as giving slight improvements to the Laser Method to find better and better zeroing outs These works apply the Laser Method to higher powers of the tensor $T=CW_{q}$, a technique which is still captured by the Solar Method.. The Group-Theoretic Method, like the Solar Method, is very general, and it is not clear how to optimally apply it to a particular group or family of groups.

How much can we improve our bound on $\omega$ using a more clever analysis of the Coppersmith-Winograd tensor?

The author and Vassilevska Williams [AW18b] addressed this question by showing that there is a constant $c>2$ so that for all $q$, $\omega_{g}(CW_{q})>c$. In other words, the Galactic Method (monomial degenerations) cannot be used with $CW_{q}$ to prove $\omega=2$. However, this leaves open a number of important questions: How close to $2$ can we get using monomial degenerations; could it be that $\omega_{g}(CW_{q})\leq 2.1$? Perhaps more importantly, what if we are allowed to use arbitrary degenerations; could it be that $\omega_{u}(CW_{q})\leq 2.1$, or even $\omega_{u}(CW_{q})=2$?

The second main question of this paper concerns the Laser Method. The Laser Method upper bounds $\omega_{s}(T)$ for any tensor $T$ with certain structure (which we describe in detail in Section 6), and has led to every improvement on $\omega$ since its introduction by Strassen [Str87].

When the Laser Method applies to a tensor $T$, how close does it come to optimally analyzing $T$?

As discussed, we know the Laser Method does not always give a tight bound on $\omega_{s}(T)$. For instance, Coppersmith-Winograd [CW90] applied the Laser Method to $CW_{q}$ to prove $\omega_{s}(CW_{q})\leq 2.376$, and then later work [DS13, Wil12, LG14] analyzed higher and higher powers of $CW_{q}$ to show $\omega_{s}(CW_{q})\leq 2.373$. Ambainis, Filmus and Le Gall [AFLG15] showed that analyzing higher and higher powers of $CW_{q}$ itself with the Laser Method cannot yield an upper bound better than $\omega_{s}(CW_{q})\leq 2.3725$. What about for other tensors? Could there be a tensor such that applying the Laser Method to $T$ yields $\omega_{s}(T)\leq c$ for some $c>2$, but applying the Laser Method to high powers $T^{\otimes n}$ of $T$ yields $\omega_{s}(T)=2$? Could applying an entirely different method to such a $T$, using arbitrary degenerations and not just zeroing outs, show that $\omega_{u}(T)=2$?

We give strong resolutions to both Question 1.1 and Question 1.2.

To resolve Question 1.1, we prove a new lower bound for the Coppersmith-Winograd tensor:

$\omega_{u}(CW_{q})\geq 2.16805$ for all $q$.

In other words, no analysis of $CW_{q}$, using any techniques within the Universal Method, can prove a bound on $\omega$ better than $2.16805$. This generalizes the main result of [AW18b] from the Galactic method to the Universal method, and gives a more concrete lower bound, increasing the bound from ‘a constant greater than $2$’ to $2.16805$. We also give stronger lower bounds for particular tensors in the family. For instance, for the specific tensor $CW_{5}$ which yields the current best bound on $\omega$, we show $\omega_{u}(CW_{5})\geq 2.21912\ldots$.

We also show how our slice rank lower bounds can be used to study other properties of tensors. Coppersmith and Winograd [CW90] introduced the notion of the value $V_{\tau}(T)$ of a tensor $T$, which is useful when applying the Laser Method to a larger tensor $T^{\prime}$ which contains $T$ as a subtensor. We show how our slice rank lower bounding tools yield a tight upper bound on the value of $t_{112}$, the notorious subtensor of $CW_{q}^{\otimes 2}$ which arises when applying the Laser Method to powers of $CW_{q}$. Although the value $V_{\tau}(t_{112})$ appears in every analysis of $CW_{q}$ since [CW90], including [DS13, Wil12, LG14, LG12, GU18], the best lower bound on it has not improved since [CW90], and our new upper bound here helps explain why. See Sections 3.5 and 5.4 for more details.

We briefly note that our lower bound of $2.16805>2+\frac{1}{6}$ in Theorem 1.3 may be significant when compared to the recent algorithm of Cohen, Lee and Song [CLS18] which solves $n$-variable linear programs in time about $O(n^{\omega}+n^{2+1/6})$.

The Laser Method is “Complete”

The tensors we prove this for are what we call laser-ready tensors – tensors to which the Laser Method (as used by [CW90] on $CW_{q}$) applies; see Definition 6.1 for the precise definition. Tensors need certain structure to be laser-ready, but tensors $T$ with this structure are essentially the only ones for which successful techniques for upper bounding $\omega_{u}(T)$ are known. In fact, every record-holding tensor in the history of matrix multiplication algorithm design has been laser-ready.

If $T$ is a laser-ready tensor, and the Laser Method applied to $T$ yields the bound $\omega_{u}(T)\leq c$ for some $c>2$, then $\omega_{u}(T)>2$.

To reiterate: If $T$ is any tensor to which the Laser Method applies (as in Definition 6.1), and the Laser Method does not yield $\omega=2$ when applied to $T$, then in fact $\omega_{u}(T)>2$, and even the substantially more general Universal method applied to $T$ cannot yield $\omega=2$. Hence, the Laser Method, which was originally used as an algorithmic tool, can also be seen as a lower bounding tool. Conversely, Theorem 1.4 shows that the Laser Method is “complete”, in the sense that it cannot yield a bound on $\omega$ worse than $2$ when applied to a tensor which is able to prove $\omega=2$.

Theorem 1.4 explains and generalizes a number of phenomena:

The fact that Coppersmith-Winograd [CW90] applied the Laser method to the tensor $CW_{q}$ and achieved an upper bound greater than $2$ on $\omega$ implies that $\omega_{u}(CW_{q})>2$, and no arbitrary degeneration of powers of $CW_{q}$ can yield $\omega=2$.

As mentioned above, it is known that applying the Laser method to higher and higher powers of a tensor $T$ can successively improve the resulting upper bound on $\omega$. Theorem 1.4 shows that if the Laser method applied to the first power of any tensor $T$ did not yield $\omega=2$, then this sequence of Laser method applications (which is a special case of the Universal method) must converge to a value greater than $2$ as well. This generalizes the result of Ambainis, Filmus and Le Gall [AFLG15], who proved this about applying the Laser Method to higher and higher powers of the specific tensor $T=CW_{q}$.

Since, as discussed above, almost all of the most-studied tensors are laser-ready, this might help explain why we have been unable to separate the two notions.

2 Other Related Work

Cohn and Umans [CU13] introduced the notion of the support rank of tensors, and showed that upper bounds on the support rank of matrix multiplication tensors can be used to design faster Boolean matrix multiplication algorithms. Recently, Karppa and Kaski [KK19] used ‘probabilistic tensors’ as another way to design Boolean matrix multiplication algorithms.

In fact, our tools for proving asymptotic slice rank upper bounds can be used to prove lower bounds on these approaches as well. For instance, our results imply that finding a ‘weighted’ matrix multiplication tensor as a degeneration of a power of $CW_{q}$ (in order to prove a support rank upper bound) cannot result in a better exponent for Boolean matrix multiplication than $2.16805$.

Concurrent Work

3 Outline

In Section 2 we give an overview of the proofs of our main results. In Section 3 we introduce all the concepts and notation related to tensors which will be used throughout the paper. In particular, in Subsection 3.6 we introduce the relevant notions and basic properties related to slice rank. In Section 4 we present the proofs of our new lower bounding tools for asymptotic slice rank. In Section 5 we apply these tools to a number of tensors of interest including $CW_{q}$. Finally, in Section 6, we define and discuss the “completeness” of the Laser method.

Proof Overview

We give a brief overview of the techniques we use to prove our main results, Theorems 1.3 and 1.4. All the technical terms we refer to here will be precisely defined in Section 3.

Matrix multiplication tensors have high asymptotic slice rank.

Section 4: Tools for Upper Bounding Asymptotic Slice Rank

Section 5: Universal Method Lower Bounds

Section 6: “Completeness” of the Laser Method

Preliminaries

We begin by introducing the relevant notions and notation related to tensors and matrix multiplication. We will use the same notation introduced in [AW18b, Section 3], and readers familiar with that paper may skip to Subsection 3.5.

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

If $T_{1}$ is a tensor over $X_{1},Y_{1},Z_{1}$, and $T_{2}$ is a tensor over $X_{2},Y_{2},Z_{2}$, then the tensor product $T_{1}\otimes T_{2}$ is a tensor over $X_{1}\times X_{2},Y_{1}\times Y_{2},Z_{1}\times Z_{2}$ such that, for any $(x_{1},x_{2})\in X_{1}\times X_{2}$, $(y_{1},y_{2})\in Y_{1}\times Y_{2}$, and $(z_{1},z_{2})\in Z_{1}\times Z_{2}$, the coefficient of $(x_{1},x_{2})(y_{1},y_{2})(z_{1},z_{2})$ in $T_{1}\otimes T_{2}$ is the product of the coefficient of $x_{1}y_{1}z_{1}$ in $T_{1}$, and the coefficient of $x_{2}y_{2}z_{2}$ in $T_{2}$. For any tensor $T$ and positive integer $n$, the tensor power $T^{\otimes n}$ is the tensor over $X^{n},Y^{n},Z^{n}$ resulting from taking the tensor product of $n$ copies of $T$.

If $T_{1}$ is a tensor over $X_{1},Y_{1},Z_{1}$, and $T_{2}$ is a tensor over $X_{2},Y_{2},Z_{2}$, then the direct sum $T_{1}\oplus T_{2}$ is a tensor over $X_{1}\sqcup X_{2}$, $Y_{1}\sqcup Y_{2}$, $Z_{1}\sqcup Z_{2}$ which results from forcing the variable sets to be disjoint (as in a normal disjoint union) and then summing the two tensors. For a nonnegative integer $m$ and tensor $T$ we write $m\odot T$ for the disjoint sum of $m$ copies of $T$.

2 Tensor Rank

3 Matrix Multiplication Tensors

For positive integers $a,b,c$, the matrix multiplication tensor $\langle a,b,c\rangle$ is a tensor over $\{x_{ij}\}_{i\in[a],j\in[b]}$, $\{y_{jk}\}_{j\in[b],k\in[c]}$, $\{z_{ki}\}_{k\in[c],i\in[a]}$ given by

It is not hard to verify that for positive integers $a_{1},a_{2},b_{1},b_{2},c_{1},c_{2}$, we have $\langle a_{1},b_{1},c_{1}\rangle\otimes\langle a_{2},b_{2},c_{2}\rangle\simeq\langle a_{1}a_{2},b_{1}b_{2},c_{1}c_{2}\rangle$. The exponent of matrix multiplication, denoted $\omega$, is defined as

Because of the tensor product property above, we can alternatively define $\omega$ in a number of ways:

For instance, Strassen [Str69] showed that $R(\langle 2,2,2\rangle)\leq 7$, which implies that $\omega\leq\log_{2}(7)$.

4 Degenerations and the Universal Method

If such a transformation is possible, we say $T_{2}$ is a degeneration of $T_{1}$. There are also two more restrictive types of degenerations:

$T_{2}$ is a monomial degeneration of $T_{1}$ if such a transformation is possible where the polynomials in the ranges of $\alpha,\beta,\gamma$ have at most one monomial, and furthermore, for each $x\in X_{1}$ there is at most one $x^{\prime}\in X_{2}$ such that $\alpha(x,x^{\prime})\neq 0$, and similarly for $\beta$ and $\gamma$. Some definitions of monomial degenerations do not have this second condition, or equivalently, consider a monomial degeneration to be a ‘restriction’ composed with what we defined here. The distinction is not important for this paper, but we give this definition since it captures Strassen’s monomial degeneration from matrix multiplication tensors to independent tensors [Str86] (see also Proposition 3.5 below), and it is the notion that the prior work [AW18b] proved lower bounds against.

$T_{2}$ is a zeroing out of $T_{1}$ if, in addition to the restrictions of a monomial degeneration, the ranges of $\alpha,\beta,\gamma$ must be $\{0,1\}$.

Degenerations are useful in the context of matrix multiplication algorithms because degenerations cannot increase the rank of a tensor. In other words, if $T_{2}$ is a degeneration of $T_{1}$, then $R(T_{2})\leq R(T_{1})$ [Bin80]. It is often hard to bound the rank of matrix multiplication tensors directly, so all known approaches proceed by bounding the rank of a different tensor $T$ and then showing that powers of $T$ degenerate into matrix multiplication tensors.

In [AW18b], two weaker versions of the Universal Method are also defined: the Galactic Method, in which the degeneration must be a monomial degeneration, resulting in a bound $\omega_{g}(T)$, and the Solar Method, in which the degeneration must be a zeroing out, resulting in a bound $\omega_{s}(T)$. To be clear, all three of these methods are very general, and we don’t know the values of $\omega_{s}(T)$, $\omega_{g}(T)$, or $\omega_{u}(T)$ for almost any nontrivial tensors $T$. In fact, all the known approaches to bounding $\omega$ proceed by giving upper bounds on $\omega_{s}(T)$ for some carefully chosen tensors $T$; the most successful has been the Coppersmith-Winograd family of tensors $T=CW_{q}$, which has yielded all the best known bounds on $\omega$ since the 80’s [CW82, DS13, Wil12, LG14]. Indeed, the two most successful approaches, the Laser Method [Str87] and the Group-Theoretic Approach [CU03] ultimately use zeroing outs of tensors. We refer the reader to [AW18b, Sections 3.3 and 3.4] for more details on these approaches and how they relate to the notions used here.

5 Tensor Value

Coppersmith and Winograd [CW90] defined the value of a tensor in their analysis of the $CW_{q}$ tensor. For a tensor $T$, and any $\tau\in[2/3,1]$, the $\tau$-value of $T$, denoted $V_{\tau}(T)$, is defined as follows: Consider all positive integers $n$, and all ways $\sigma$ to degenerate $T^{\otimes n}$ into a direct sum $\bigoplus_{i=1}^{q(\sigma)}\langle a_{i}^{\sigma},b_{i}^{\sigma},c_{i}^{\sigma}\rangle$ of matrix multiplication tensors. Then, $V_{\tau}(T)$ is given by

6 Asymptotic Slice Rank

The main new notions we will need in this paper relate to the slice rank of tensors. We say a tensor $T$ over $X,Y,Z$ has x-rank $1$ if it is of the form

for some choices of the $\alpha$ and $\beta$ coefficients over the base field. More generally, the x-rank of $T$, denoted $\mathop{\operatorname{S_{x}}}(T)$, is the minimum number of tensors of x-rank 1 whose sum is $T$. We can similarly define the y-rank, $\mathop{\operatorname{S_{y}}}$, and the z-rank, $\mathop{\operatorname{S_{z}}}$. Then, the slice rank of $T$, denoted $\mathop{\operatorname{S}}(T)$, is the minimum $k$ such that there are tensors $T_{X}$, $T_{Y}$ and $T_{Z}$ with $T=T_{X}+T_{Y}+T_{Z}$ and $\mathop{\operatorname{S_{x}}}(T_{X})+\mathop{\operatorname{S_{y}}}(T_{Y})+\mathop{\operatorname{S_{z}}}(T_{Z})=k$.

We note a few simple properties of slice rank which will be helpful in our proofs:

$\mathop{\operatorname{S}}(A)\leq\mathop{\operatorname{S_{x}}}(A)\leq\mathop{\operatorname{R}}(A)$,

$\mathop{\operatorname{S_{x}}}(A\otimes B)\leq\mathop{\operatorname{S_{x}}}(A)\cdot\mathop{\operatorname{S_{x}}}(B)$,

$\mathop{\operatorname{S}}(A+B)\leq\mathop{\operatorname{S}}(A)+\mathop{\operatorname{S}}(B)$, and $\mathop{\operatorname{S_{x}}}(A+B)\leq\mathop{\operatorname{S_{x}}}(A)+\mathop{\operatorname{S_{x}}}(B)$,

$\mathop{\operatorname{S}}(A\otimes B)\leq\mathop{\operatorname{S}}(A)\cdot\max\{\mathop{\operatorname{S_{x}}}(B),\mathop{\operatorname{S_{y}}}(B),\mathop{\operatorname{S_{z}}}(B)\}$, and

If $A$ is a tensor over $X,Y,Z$, then $\mathop{\operatorname{S_{x}}}(T)\leq|X|$ and hence $\mathop{\operatorname{S}}(T)\leq\min\{|X|,|Y|,|Z|\}$.

(1) and (2) are straightforward. (3) follows since the sum of the slice rank (resp. x-rank) expressions for $A$ and for $B$ gives a slice rank (resp. x-rank) expression for $A+B$. To prove (4), let $m=\max\{\mathop{\operatorname{S_{x}}}(B),\mathop{\operatorname{S_{y}}}(B),\mathop{\operatorname{S_{z}}}(B)\}$, and note that if $A=A_{X}+A_{Y}+A_{Z}$ such that $\mathop{\operatorname{S_{x}}}(A_{X})+\mathop{\operatorname{S_{y}}}(A_{Y})+\mathop{\operatorname{S_{z}}}(A_{Z})=\mathop{\operatorname{S}}(A)$, then

Finally, (5) follows since, for instance, any tensor with one only x-variable has x-rank 1. ∎

Asymptotic slice rank is interesting in the context of matrix multiplication algorithms because of the following facts.

For a positive integer $q$, the independent tensor of size $q$, denoted $\langle q\rangle$, is the tensor $\sum_{i=1}^{q}x_{i}y_{i}z_{i}$ with $q$ terms that do not share any variables.

For any positive integers $a,b,c$, the matrix multiplication tensor $\langle a,b,c\rangle$ has a (monomial) degeneration to an independent tensor of size at least $0.75\cdot abc/\max\{a,b,c\}$.

To summarize: we know that degenerations cannot increase asymptotic slice rank, and that matrix multiplication tensors have a high asymptotic slice rank. Hence, if $T$ is a tensor such that $\omega_{u}(T)$ is ‘small’, meaning a power of $T$ has a degeneration to a disjoint sum of many large matrix multiplication tensors, then $T$ itself must have ‘large’ asymptotic slice rank. This can be formalized identically to [AW18b, Theorem 4.1 and Corollary 4.3] to show:

7 Partition Notation

In a number of our results, we will be partitioning the terms of tensors into blocks defined by partitions of the three variable sets. Here we introduce some notation for some properties of such partitions; these definitions all depend on the particular partition of the variables being used, which will be clear from context.

Suppose $T$ is a tensor minimal over $X,Y,Z$, and let $X=X_{1}\cup\cdots\cup X_{k_{X}}$, $Y=Y_{1}\cup\cdots\cup Y_{k_{Y}}$, $Z=Z_{1}\cup\cdots\cup Z_{k_{Z}}$ be partitions of the three variable sets. For $(i,j,k)\in[k_{X}]\times[k_{Y}]\times[k_{Z}]$, let $T_{ijk}$ be $T$ restricted to $X_{i},Y_{j},Z_{k}$ (i.e. $T$ with $X\setminus X_{i}$, $Y\setminus Y_{j}$, and $Z\setminus Z_{k}$ zeroed out), and let $L=\{T_{ijk}\mid(i,j,k)\in[k_{X}]\times[k_{Y}]\times[k_{Z}],T_{ijk}\neq 0\}$. $T_{ijk}$ is called a block of $T$. For $i\in[k_{X}]$ let $L_{X_{i}}=\{T_{ij^{\prime}k^{\prime}}\in L\mid(j^{\prime},k^{\prime})\in[k_{Y}]\times[k_{Z}]\}$, and define similarly $L_{Y_{j}}$ and $L_{Z_{k}}$.

and $p_{Y}$ and $p_{Z}$ similarly. This expression, which arises naturally in the Laser Method, will play an important role in our upper bounds and lower bounds.

8 Tensor Rotations and Variable-Symmetric Tensors

If $T$ is a tensor over $X,Y,Z$, then the rotation of $T$, denoted $rot(T)$, is the tensor over $Y,Z,X$ such that for any $(x_{i},y_{j},z_{k})\in X\times Y\times Z$, the coefficient of $x_{i}y_{j}z_{k}$ in $T$ is equal to the coefficient of $y_{j}z_{k}x_{i}$ in $rot(T)$. Tensor $T$ is variable-symmetric if $T\simeq rot(T)$.

If $T$ is a variable-symmetric tensor minimal over $X,Y,Z$, then partitions $X=X_{1}\cup\cdots\cup X_{k_{X}}$, $Y=Y_{1}\cup\cdots\cup Y_{k_{Y}}$, $Z=Z_{1}\cup\cdots\cup Z_{k_{Z}}$ of the variable sets are called $T$-symmetric if (using the notation of the previous subsection) $k_{X}=k_{Y}=k_{Z}$, $|X_{i}|=|Y_{i}|=|Z_{i}|$ for all $i\in[k_{X}]$, and the block $T_{jki}\simeq rot(T_{ijk})$ for all $(i,j,k)\in[k_{X}]^{3}$. For the $L$ resulting from such a $T$-symmetric partition, a probability distribution $p\in P(L)$ is called $T$-symmetric if it satisfies $p(T_{ijk})=p(T_{jki})$ for all $(i,j,k)\in[k_{X}]^{3}$, and we write $P^{sym}(L)\subseteq P(L)$ for the set of such $T$-symmetric distributions. Notice in particular that any $p\in P^{sym}(L)$ satisfies $p_{X}=p_{Y}=p_{Z}$.

Combinatorial Tools for Asymptotic Slice Rank Upper Bounds

If $X,Y,Z$ are minimal for $T$, then the measure of $T$, denoted $\mu(T)$, is given by $\mu(T):=|X|\cdot|Y|\cdot|Z|$. We state two simple facts about $\mu$:

if $A$ is minimal over $X,Y,Z$, then $\mathop{\operatorname{S}}(A)\leq\min\{|X|,|Y|,|Z|\}\leq\mu(A)^{1/3}$.

2 Generalization of [AW18b, Theorem 5.2]

For any tensor $T$ and partition of its variable sets,

For any positive integer $n$, we can write

This is upper bounded by $p_{X}^{n+o(n)}$, where $p_{X}$ is the quantity defined in Section 3.7. It follows that $\mathop{\operatorname{S_{x}}}\left(\sum_{(P_{1},\ldots,P_{n})\in L_{n,p}}P_{1}\otimes\cdots\otimes P_{n}\right)\leq p_{X}^{n+o(n)}$. We can similarly argue about $\mathop{\operatorname{S_{y}}}$ and $\mathop{\operatorname{S_{z}}}$. Hence,

Hence, $\mathop{\operatorname{S}}(T^{\otimes n})\leq\limsup_{p}\min\{p_{X},p_{Y},p_{Z}\}^{n+o(n)}$, and the desired result follows. ∎

We make a remark about applying Theorem 4.4 to variable-symmetric tensors. This remark has implicitly been used in past work on applying the Laser method, such as [CW90], but we prove it here for completeness. Recall the notation in Section 3.8 about such tensors.

Suppose $T$ is a variable-symmetric tensor over $X,Y,Z$, and $X=X_{1}\cup\cdots\cup X_{k_{X}}$, $Y=Y_{1}\cup\cdots\cup Y_{k_{Y}}$, $Z=Z_{1}\cup\cdots\cup Z_{k_{Z}}$ are $T$-symmetric partitions. Then,

Consider any $p\in P(L)$, and define the distribution $p^{\prime}\in P^{sym}(L)$ by $p^{\prime}(T_{ijk}):=(p(T_{ijk})+p(T_{jki})+p(T_{kij}))/3$ for each $T_{ijk}\in L$. In order to show that $\min\{p_{X},p_{Y},p_{Z}\}\leq p^{\prime}_{X}$, we will show that $(p_{X}p_{Y}p_{Z})^{1/3}\leq p^{\prime}_{X}$:

where the second-to-last step follows from the fact that for any real numbers $a,b,c\in$, setting $d=(a+b+c)/3$, we have $a^{a}b^{b}c^{c}\geq d^{3d}$. ∎

3 Generalization of [AW18b, Theorem 5.1]

The final remaining tool from [AW18b], their Theorem 5.1, turns out to be unnecessary for proving our tight lower bounds in the next section. Nonetheless, we sketch here how to extend it to give asymptotic slice rank upper bounds as well.

For a tensor $T$, let $m(T):=\max\{\mathop{\operatorname{S_{x}}}(T),\mathop{\operatorname{S_{y}}}(T),\mathop{\operatorname{S_{z}}}(T)\}$. Recall from Lemma 3.1 that for any two tensors $A,B$ we have $\mathop{\operatorname{S}}(A\otimes B)\leq\mathop{\operatorname{S}}(A)\cdot m(B)$.

Suppose $T,A,B$ are tensors such that $A+B=T$. Then,

We begin by, for any integers $n\geq k\geq 0$, giving bounds on $\mathop{\operatorname{S}}(A^{\otimes k}\otimes B^{\otimes(n-k)})$. First, since $\mathop{\operatorname{S_{x}}}$ is submultiplicative, we have

Second, from the definition of $m$, we have

It follows that for any positive integer $n$ we have

Computing the Slice Ranks for Tensors of Interest

In this section, we give slice rank upper bounds for a number of tensors of interest. It will follow from Section 6 that all of the bounds we prove in this Section are tight.

We begin with the generalized CW tensors defined in [AW18b], which for a positive integer $q$ and a permutation $\sigma:[q]\to[q]$ are given by

That said, we will now use Theorem 4.4 to prove that $c\geq 2.16805$. (In fact, essentially the same argument as we present now shows that [AW18b, Theorem 5.2] was already sufficient to show the weaker claim that $\omega_{g}(CW_{q,\sigma})\geq 2.16805$).

We begin by partitioning the variable sets of $CW_{q,\sigma}$, using the notation of Theorem 4.4. Let $X_{0}=\{x_{0}\}$, $X_{1}=\{x_{1},\ldots,x_{q}\}$, and $X_{2}=\{x_{q+1}\}$, so that $X_{0}\cup X_{1}\cup X_{2}$ is a partition of the $x$-variables of $CW_{q,\sigma}$. The sets of partitions were 1-indexed before, but we 0-index here for notational consistency with past work. Similarly, let $Y_{0}=\{y_{0}\}$, $Y_{1}=\{y_{1},\ldots,y_{q}\}$, $Y_{2}=\{y_{q+1}\}$, $Z_{0}=\{z_{0}\}$, $Z_{1}=\{z_{1},\ldots,z_{q}\}$, and $Z_{2}=\{z_{q+1}\}$. We can see this is a $CW_{q,\sigma}$-symmetric partition with $L=\{T_{002},T_{020},T_{200},T_{011},T_{101},T_{110}\}$.

Consider any probability distribution $p\in P^{sym}(L)$. By symmetry, we know that $p(T_{002})=p(T_{020})=p(T_{200})=v$ and $p(T_{011})=p(T_{101})=p(T_{110})=1/3-v$ for some value $v\in[0,1/3]$. Applying Theorem 4.4, and in particular Proposition 4.7, yields:

It is not hard to see that the resulting lower bound on $\omega_{u}(CW_{q,\sigma})$ is increasing with $q$ and is always at least $2.16805\ldots$ (see Appendix A below for a proof), and hence that for any $q$ and any $\sigma$ we have $\omega_{u}(CW_{q,\sigma})\geq 2.16805$ as desired.

2 Generalized Simple Coppersmith-Winograd Tensors

Similar to $CW_{q,\sigma}$, we can define for a positive integer $q$ and a permutation $\sigma:[q]\to[q]$ the simple Coppersmith-Winograd tensor $cw_{q,\sigma}$ given by:

The first few values are as follows; note that we cannot get a bound better than $2$ when $q=2$ because of Coppersmith and Winograd’s remark.

3 Cyclic Group Tensors

We next look at two tensors which were studied in [CU03], [AW18a], and [AW18b, Section 7.3]. For each positive integer $q$, define the tensor $T_{q}$ (the structural tensor of the cyclic group $C_{q}$) as:

Define also the lower triangular version of $T_{q}$, called $T_{q}^{lower}$, as:

4 The Value of the Subtensor t112t_{112} of C​Wq⊗2CW_{q}^{\otimes 2}

A key tensor which arises in applying the Laser method to increasing powers of $CW_{q}$, including [CW90, Wil12, LG14, LG12, GU18], is the tensor $t_{112}$ which (for a given positive integer $q$) is given by

Coppersmith-Winograd [CW90] and future work studied the value of this tensor. In [CW90] it is shown that for every $\tau\in[2/3,1]$,

This bound has been used in all the subsequent work using $CW_{q}$, without improvement. Here we show it is tight and cannot be improved in the case $\tau=2/3$:

$V_{2/3}(t_{112})=2^{2/3}q^{2/3}(q^{2}+2)^{1/3}.$

Consider the variable-symmetric tensor $t_{s}:=t_{112}\otimes rot(t_{112})\otimes rot(rot(t_{112}))$. As in [CW90], by definition of $V_{2/3}$, for every $\delta>0$ there is a positive integer $n$ such that $t_{s}^{\otimes n}$ has a degeneration to $\bigoplus_{i}\langle a_{i},a_{i},a_{i}\rangle$ for values such that $\sum_{i}a_{i}^{2}\geq(V_{2/3}(T_{112}))^{3n(1-\delta)}$. In particular, by Corollary 3.6 this yields the bound

The only upper bound we are able to prove on $V_{\tau}$ for $\tau>2/3$ is the straightforward $V_{\tau}(t_{112})\leq V_{2/3}(t_{112})^{3\tau/2}=2^{\tau}q^{\tau}(q^{2}+2)^{\tau/2}$, which is slightly worse than the best known lower bound $V_{\tau}(t_{112})\geq 2^{2/3}q^{\tau}(q^{3\tau}+2)^{1/3}$. It is an interesting open problem to prove tight upper bounds on $V_{\tau}(T)$ for any nontrivial tensor $T$ and value $\tau>2/3$. $T=t_{112}$ may be a good candidate since the Laser method seems unable to improve $V_{\tau}(t_{112})$ for any $\tau$, even when applied to any small tensor power $t_{112}^{\otimes n}$.

Slice Rank Lower Bounds via the Laser Method

Consider any tensor $T$ which is minimal over $X,Y,Z$, and let $X=X_{1}\cup\cdots\cup X_{k_{X}}$, $Y=Y_{1}\cup\cdots\cup Y_{k_{Y}}$, $Z=Z_{1}\cup\cdots\cup Z_{k_{Z}}$ be partitions of the three variable sets. Define $T_{ijk}$, $L$, and $p_{X}$ for a probability distribution $p$ on $L$, as in the top of Subsection 3.7. Recall in particular that $T_{ijk}$ is $T$ restricted to the variable sets $X_{i}$, $Y_{j}$, and $Z_{k}$.

We say that $T$, along with partitions of $X,Y,Z$, is a laser-ready tensor partition if the following three conditions are satisfied:

For every $(i,j,k)\in[k_{X}]\times[k_{Y}]\times[k_{Z}]$, either $T_{ijk}=0$, or else $T_{ijk}$ has a degeneration to a tensor $\langle a,b,c\rangle$ with $ab=|X_{i}|$, $bc=|Y_{j}|$, and $ca=|Z_{k}|$ (i.e. a matrix multiplication tensor which is as big as possible given $|X_{i}|$, $|Y_{j}|$, and $|Z_{k}|$).

$T$ is variable-symmetric, and the partitions are $T$-symmetric.

These conditions are exactly those for which the original Laser Method used by Coppersmith and Winograd [CW90] applies to $T$. We note that condition (3) is a simplifying assumption rather than a real condition on $T$: for any tensor $T$ and partitions satisfying conditions (1) and (2), the tensor $T^{\prime}:=T\otimes rot(T)\otimes rot(rot(T))$ along with the corresponding product partitions, satisfies all three conditions, gives at least as good a bound on $\omega$ using the Laser Method as $T$ and the original partitions, and more generally has $\omega_{u}(T^{\prime})\leq\omega_{u}(T)$.

Suppose $T$, along with the partitions of $X,Y,Z$, is a laser-ready tensor partition. Then, for any distribution $p\in P^{sym}(L)$, and any positive integer $n$, the tensor $T^{\otimes n}$ has a degeneration into

Typically, as described in [Wil12, Section 3], there is an additional loss in the size of the degeneration if there are multiple different distributions $p,p^{\prime}$ with the same marginals (meaning $p(X_{i})=p^{\prime}(X_{i})$, $p(Y_{j})=p^{\prime}(Y_{j})$, and $p(Z_{k})=p^{\prime}(Z_{k})$ for all $i,j,k$) but different values of $V(p):=\prod_{T_{ijk}\in L}V_{\tau}(T_{ijk})^{p(T_{ijk})}$ for any $\tau\in[2/3,1]$. However, because of condition (1) in the definition of a laser-ready tensor partition, the quantity $V(p)$ is equal to

and in particular satisfies $V(p)=V(p^{\prime})$ for any two distributions $p,p^{\prime}$ with the same marginals. Thus, we do not incur this loss, and we get the desired degeneration. ∎

Our key new result about such tensor partitions is as follows:

Suppose tensor $T$, along with the partitions of $X,Y,Z$, is a laser-ready tensor partition. Then,

For the lower bound, we know from Theorem 6.2 that for all $p\in P^{sym}(L)$, and all positive integers $n$, the tensor $T^{\otimes n}$ has a degeneration into

By Proposition 3.5, this means $T^{\otimes n}$ has a degeneration to an independent tensor of size

$CW_{q,\sigma}$, $cw_{q,\sigma}$, and $T_{q}^{lower}$, partitioned as they were in the previous section, are laser-ready tensor partitions. The tight bound for $T_{q}$ follows from the degeneration to $T_{q}^{lower}$ described in the previous section. ∎

If $T$ is a tensor with a laser-ready tensor partition, and applying the Laser method to $T$ with this partition yields an upper bound on $\omega$ of $\omega_{u}(T)\leq c$ for some $c>2$, then $\omega_{u}(T)>2$.

When the Laser method shows, as in Theorem 6.2, that $T^{\otimes n}$ has a degeneration into

the resulting upper bound on $\omega_{u}(T)$ is that

Acknowledgements

I would like to thank Matthias Christandl, Joshua Grochow, Ryan Williams, Virginia Vassilevska Williams, and Jeroen Zuiddam for helpful discussions and suggestions.

References

Appendix A Proof that ωu​(C​Wq,σ)≥2.16805\omega_{u}(CW_{q,\sigma})\geq 2.16805 for all qq

The value of this optimization problem is computed for $1\leq q\leq 8$ in a table in Section 5.1, where we see that $\omega_{u}(CW_{q,\sigma})\geq 2.16805$ for all $q\leq 8$.

Let $v_{q}$ denote the argmin for the optimization problem. In particular, for $q=8$, the argmin is $v_{8}=0.017732422\ldots$. From the $q^{2/3-2v}$ term in the optimization problem, we see that $v_{q+1}\leq v_{q}$ for all $q$, and in particular, $v_{q}\leq v_{8}$ for all $q>8$. It follows that $f(v_{q})\leq f(v_{8})=2.07389\ldots$ for all $q>8$. Thus, for all $q>8$ we have:

This expression equals $2.18562\ldots$ at $q=9$, and is easily seen to be increasing with $q$ for $q>9$, which implies as desired that $\omega_{u}(CW_{q,\sigma})\geq 2.16805$ for all $q\geq 9$ and hence all $q$.