A Refined Laser Method and Faster Matrix Multiplication

Introduction

Settling the algorithmic complexity of matrix multiplication is one of the most fascinating open problems in theoretical computer science. The main measure of progress on the problem is the exponent $\omega$, defined as the smallest real number for which $n\times n$ matrices over a field can be multiplied using $O(n^{\omega+\varepsilon})$ field operations, for every $\varepsilon>0$. The value of $\omega$ could depend on the field, although the algorithms we discuss in this paper work over any field. The straightforward algorithm shows that $\omega\leq 3$, and we can see that $\omega\geq 2$ since any algorithm must output $n^{2}$ entries. In 1969, Strassen [Str69] obtained the first nontrivial upper bound on $\omega$, showing that $\omega<2.81$. Since then, a long series of papers (e.g. [Pan78, BCRL79, Pan80, Sch81, Rom82, CW82, Str86, CW90, DS13, Vas12, LG14, CU03, CKSU05, CU13]) has developed a powerful toolbox of techniques, culminating in the best bound to date of $\omega<2.37287$.

In this paper, we add one more tool to the toolbox and lower the best bound on the matrix multiplication exponent to

The main contribution of this paper is a new refined version of the laser method which we then use to obtain the new bound on $\omega$. The laser method (as coined by Strassen [Str86]) is a powerful mathematical technique for analyzing tensors. In our context, it is used to lower bound the “value” of a tensor in designing matrix multiplication algorithms. The laser method also has applications beyond bounding $\omega$ itself, including to other problems in arithmetic complexity like computing the “asymptotic subrank” of tensors [Alm19], and to problems in extremal combinatorics like constructing tri-colored sum-free sets [KSS18]. We believe our improved laser method may have other diverse applications.

We will see that our new method achieves better results than the laser method of prior work when applied to almost any sufficiently large tensor, including most of the tensors which arise in prior bounds on $\omega$. In fact, unlike in other recent work, it is clear before running any code that our new method yields a new improved bound on $\omega$.

The last several improvements to the best bound on $\omega$ have been modest. Most recently, Le Gall [LG14] brought the upper bound on $\omega$ from $2.37288$ [Vas12] to $2.37287$, and we bring it down to $2.37286$. (More precisely, we prove $\omega<2.3728596$.) A recent line of work has shown that only modest improvements can be expected if one continues using similar techniques. All fast matrix multiplication algorithms since 1986 use the laser method applied to the Coppersmith-Winograd family of tensors [CW90]. The techniques can also be simulated within the group theoretic method of Cohn and Umans [CU03, CKSU05, CU13]. A sequence of several papers [AFLG15, ASU13, BCC+17a, BCC+17b, AV18a, AV18b, Alm19, CVZ19] has given strong limitations on the power of the laser method, the group theoretic method and their generalizations, showing in particular that for many natural families of tensors, even approaches substantially more general than the laser method would not be able to prove that $\omega=2$. It is further known that the laser method, even our refined version of it, when applied to powers of the particular Coppersmith-Winograd tensor $CW^{\otimes 32}_{5}$ that achieves the current best bounds on $\omega$, cannot achieve $\omega<2.3725$ [AFLG15].

That said, the known limitation results are very specific to the tensors they are applied to, and so it is not ruled out that our improved laser method could be applied to a different family of tensors to yield even further improved bounds on $\omega$. Even in the case of the smaller Coppersmith-Winograd tensor $CW_{1}$, the known limitations are weaker, and it is conceivable that one could achieve $\omega<2.239$ using it.

In this subsection, we give an overview of our improvement to the laser method. We assume familiarity with basic notions related to tensors and matrix multiplication; unfamiliar readers may want to read Section 2 first.

Fast matrix multiplication algorithms since the 1980s have been designed by making use of a cleverly-chosen intermediate tensor $T$. They have consisted of two main ingredients:

A proof that $T$ has a high value for computing matrix multiplication (i.e. a restriction of $T^{\otimes n}$ into a large direct sum of matrix multiplication tensors).

Since the work of Coppersmith and Winograd [CW90], the fastest matrix multiplication algorithms have used $T=CW_{q}$, the Coppersmith-Winograd tensor. Coppersmith and Winograd showed that the asymptotic rank of $CW_{q}$ is as low as possible given its dimensions. Hence, subsequent work has focused on improving the bound on the value of $CW_{q}$, and this is the approach we take as well.

The primary way that past work has bounded the values of tensors like $CW_{q}$ is using the laser method. The laser method was so-named by Strassen [Str87], and then further developed by Coppersmith and Winograd [CW90] into its current form. We now describe the laser method at a high level.

Consider a tensor $T$ over finite variables sets $X,Y,Z$, given by

be the subtensor of $T$ restricted to $X_{i},Y_{j},Z_{k}$, we have

Suppose for now that each $T_{ijk}$ is either or else a matrix multiplication tensor; this will simplify the presentation here but is not needed in the general setting. Hence, $T$ is a sum of matrix multiplication tensors. The typical way to obtain matrix multiplication algorithms from a sum of matrix multiplication tensors, however, requires the sum to be a direct sum, and $T$ is not a direct sum in general. One could zero-out many of the $X_{i}$, $Y_{j}$, and $Z_{k}$ parts until $T$ is a direct sum of the remaining $T_{ijk}$ subtensors, but this typically removes ‘too much’ from the tensor.

The laser method instead takes the following approach. First, we pick a probability distribution $\alpha$ on the nonzero subtensors of $T$, which assigns probability $\alpha_{ijk}$ to $T_{ijk}$. Next, we take a large Kronecker power $n$ of $T$:

Since each of these sets can be used by at most one of the final $B$ subtensors, this multinomial coefficient upper bounds $B$. The laser method shows that if $T$ and $\alpha$ satisfy some additional conditions, then roughly this bound on $B$ can actually be achieved!

One of these conditions, which is the focus of our new improvement, is on the marginals of $\alpha$. Let $D_{\alpha}$ be the set of probability distributions $\beta$ with the same marginals as $\alpha$ (i.e. with $\alpha_{X_{i}}=\beta_{X_{i}}$ for all $i\in[k_{X}]$, $\alpha_{Y_{j}}=\beta_{Y_{j}}$ for all $j\in[k_{Y}]$, and $\alpha_{Z_{k}}=\beta_{Z_{k}}$ for all $k\in[k_{Z}]$). The laser method only achieves the aforementioned value of $B$ if there are no other probability distributions $\beta$ in $D_{\alpha}$. This is intuitively because the laser method is only zeroing-out sets of variables, and so it cannot distinguish between two distributions which have the same marginals. This is not an issue when analyzing smaller powers of $CW_{q}$ as in [CW90, DS13], since there the tensors and partitions are small enough that the linear system defining $D_{\alpha}$ has full rank. However, it becomes an issue when analyzing larger powers of $CW_{q}$ as in [Vas12, LG14].

The prior work dealt with this issue in a greedy way: Suppose that after the zeroing outs described above, we are left with a direct sum of $B$ subtensors consistent with $\alpha$, plus $m\cdot B$ other subtensors which are consistent with other distributions in $D_{\alpha}$. We can repeatedly pick a subtensor $S$ consistent with $\alpha$, and zero-out roughly $m$ subtensors which aren’t consistent with $\alpha$ until $S$ no longer shares variables with any remaining subtensors. We can then keep $S$ as an independent subtensor, but we may have zeroed out roughly $m$ other subtensors consistent with $\alpha$ in the process. We repeat until only subtensors consistent with $\alpha$ remain. Hence, the old approach leaves us with a direct sum of

In this work, we present a new way to deal with this issue, which improves the number of subtensors consistent with $\alpha$ at the end of the laser method to

This directly improves the final value bound achieved by the laser method by a factor of $\Theta(\sqrt{m})$. Since most of the applications of the laser method in the previous best bounds on $\omega$ [Vas12, LG14] apply it in settings where $m\gg 1$ is large enough to reduce the final value, it is evident even before running any code or computing any specific values that our improvement on the laser method leads to an improved bound on $\omega$.

Similar to other steps of the laser method, our new construction is probabilistic. We show that if one picks a random subset of roughly $B/\sqrt{m}$ subtensors consistent with $\alpha$, and zeroes out all variables which aren’t used by any of them, then there is a nonzero probability that all other subtensors are zeroed out.

It is worth asking whether the factor of $\sqrt{m}$ can be further improved. We give evidence that an improvement is not possible by constructing tensors for which our new probabilistic argument is tight up to low-order factors. Our constructed tensors even share special properties with the tensors that the laser method is usually applied to (they are “free”). That said, we leave open the possibility of improving the $\sqrt{m}$ bound for the specific tensors to which the laser method ultimately applies our probabilistic argument.

We present our new probabilistic argument for dealing with distributions $\beta\in D_{\alpha}$ other than $\alpha$ in Section 3, and then we show how to incorporate it into the laser method in Section 4. We then get into the details of actually applying the laser method to $CW_{q}$ to achieve our new bound on $\omega$: In Section 5 we discuss the computational problem of applying the laser method to a given tensor, and some algorithms and heuristics for solving it, and in Section 6 we detail how to apply the laser method to $CW_{q}$ specifically. Our new bound of $\omega<2.3728596$ is achieved by applying our refined laser method to $CW_{5}^{\otimes 32}$, the same tensor used by [LG14].

Our primary new contribution is the improved factor of $\sqrt{m}$ in the laser method, but we do add some new heuristics to the optimization framework of [Vas12, LG14] for applying the laser method to $CW_{q}$ as well. Although many of the ideas in our proof are similar to past work, we nonetheless give all the details, and we have written the body of the paper assuming little prior knowledge from the reader. We recommend the reader go through the sections in order, as the notation needed to apply the laser method is built up throughout.

2 Other Related Work

We do not specifically address algorithms for rectangular matrix multiplication in this paper. Since the best known algorithms for rectangular matrix multiplication also make use of the laser method, our techniques can be used to design faster rectangular matrix multiplication algorithms as well. That said, the computational issues which arise when bounding the running time of rectangular matrix multiplication are even more severe than when bounding $\omega$, and in fact the best known algorithms only use the $4$th Kronecker power of $CW_{q}$ [GU18], where our improved laser method does not yet kick in.

Lower Bounds for Matrix Multiplication

Preliminaries

For nonnegative integers $a_{1},\ldots,a_{k}$ with $a_{1}+\cdots+a_{k}=n$, we write $\binom{n}{[a_{i}]_{i\in[k]}}:=\binom{n}{a_{1},a_{2},\ldots,a_{k}}$ for the multinomial coefficient. One standard bound on multinomial coefficients that we will frequently make use of is that, if $p_{1},\ldots,p_{k}\in$ sum to $p_{1}+\cdots+p_{k}=1$, then for sufficiently large positive integers $n$ such that $p_{i}\cdot n$ is an integer for all $i\in[k]$, we have that

2 Tensors and Sums

For tensor $T$ over $X=\{x_{1},\ldots,x_{|X|}\},Y=\{y_{1},\ldots,y_{|Y|}\},Z=\{z_{1},\ldots,z_{|Z|}\}$ and tensor $T^{\prime}$ over $X^{\prime}=\{x^{\prime}_{1},\ldots,x^{\prime}_{|X^{\prime}|}\},Y^{\prime}=\{y^{\prime}_{1},\ldots,y^{\prime}_{|Y^{\prime}|}\},Z^{\prime}=\{z^{\prime}_{1},\ldots,z^{\prime}_{|Z^{\prime}|}\}$, given by

we now describe a number of operations and relations. We will use these two tensors as running notation throughout this section.

If $X=X^{\prime}$, $Y=Y^{\prime}$, and $Z=Z^{\prime}$, then the sum $T+T^{\prime}$ is the tensor whose coefficient of $x_{i}y_{j}z_{k}$ is $a_{ijk}+b_{ijk}$. It can be equivalently viewed as summing $T$ and $T^{\prime}$ as polynomials.

The direct sum $T\oplus T^{\prime}$ is the sum $T+T^{\prime}$ over the disjoint unions $X\sqcup X^{\prime},Y\sqcup Y^{\prime},Z\sqcup Z^{\prime}$. In other words, it is the sum $T+T^{\prime}$ after we first relabel the sets of variables so that they are disjoint.

We say $T$ and $T^{\prime}$ are isomorphic, written $T\equiv T^{\prime}$, if $|X|=|X^{\prime}|$, $|Y|=|Y^{\prime}|$, $|Z|=|Z^{\prime}|$, and there are bijections $\pi_{X}:[|X|]\to[|X^{\prime}|]$, $\pi_{Y}:[|Y|]\to[|Y^{\prime}|]$, and $\pi_{Z}:[|Z|]\to[|Z^{\prime}|]$ such that $a_{ijk}=b_{\pi_{x}(i)\pi_{y}(j)\pi_{z}(k)}$ for all $i\in[|X|]$, $j\in[|Y|]$, and $k\in[|Z|]$.

The rotation of $T$, denoted $T^{r}$, is the tensor over $Y,Z,X$ such that the coefficient of $y_{j}z_{k}x_{i}$ in $T^{r}$ is $a_{ijk}$. We similarly write $T^{rr}$ for the corresponding tensor over $Z,X,Y$.

3 Kronecker Products

The Kronecker product $T\otimes T^{\prime}$ is a tensor over $X\times X^{\prime},Y\times Y^{\prime},Z\times Z^{\prime}$ given by

One can think of $T\otimes T^{\prime}$ as multiplying $T$ and $T^{\prime}$ as polynomials, but then ‘merging’ together pairs of $x$-variables, pairs of $y$-variables, and pairs of $z$-variables into single variables.

For a positive integer $n$, we write $T^{\otimes n}:=T\otimes T\otimes T\otimes\cdots\otimes T$ ($n$ times) for the Kronecker power of $T$, which is a tensor over $X^{n},Y^{n},Z^{n}$. For $I\in[|X|]^{n}$, we will write $x_{I}$ to denote the element $(x_{I_{1}},x_{I_{2}},\ldots,x_{I_{n}})\in X^{n}$, and similarly for $Y^{n},Z^{n}$, so that

4 Tensor Rank

$R(T+T^{\prime})\leq R(T)+R(T^{\prime})$, by adding the rank expressions for $T$ and $T^{\prime}$,

$R(T)=R(T^{r})$ by rotating the rank expression, and

$R(T\otimes T^{\prime})\leq R(T)\cdot R(T^{\prime})$, by the distributive property, since one can verify that the Kronecker product of two rank $1$ tensors is also a rank $1$ tensor.

5 Matrix Multiplication Tensors

For positive integers $a,b,c$, the $a\times b\times c$ matrix multiplication tensor, written $\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

One can verify that for any positive integers $a,b,c,d,e,f$ we have $\langle a,b,c\rangle\otimes\langle d,e,f\rangle\equiv\langle ad,be,cf\rangle$. This corresponds to the fact that block matrices can be multiplied by appropriately multiplying and adding together blocks.

For any positive integers $q,r$, if $R(\langle q,q,q\rangle)=r$, then one can use the corresponding rank expression to design an arithmetic circuit for $n\times n\times n$ matrix multiplication of size $O(n^{\log_{q}(r)})$. This follows from the recursive approach introduced by Strassen [Str69]; see e.g. [Blä13, Proposition 1.1, Theorem 5.2]. The exponent of matrix multiplication, $\omega$, is hence defined as

Thus, for every $\varepsilon>0$, there is an arithmetic circuit for $n\times n\times n$ matrix multiplication of size $O(n^{\omega+\varepsilon})$. For instance, Strassen showed that $R(\langle 2,2,2\rangle)\leq 7$, which implied $\omega\leq\log_{2}(7)<2.81$. Since $\langle q,q,q\rangle^{\otimes n}\equiv\langle q^{n},q^{n},q^{n}\rangle$, we can equivalently write that, for any fixed integer $q$,

6 Schönhage’s Asymptotic Sum Inequality

By definition, in order to upper bound $\omega$, it suffices to upper bound the (asymptotic) rank of some matrix multiplication tensor. Schönhage [Sch81] showed that it also suffices to upper bound the (asymptotic) rank of a direct sum of multiple matrix multiplication tensors.

Suppose there are positive integers $r>m$, and $a_{i},b_{i},c_{i}$ for $i\in[m]$, such that the tensor

7 Zeroing-Outs, Restrictions, and Value

In fact, we will only use a limited type of a restriction called a zeroing out. We say $T^{\prime}$ is a zeroing out of $T$ if $X^{\prime}\subseteq X$, $Y^{\prime}\subseteq Y$, $Z^{\prime}\subseteq Z$, and the coefficient of $x_{i}y_{j}z_{k}$ is the same in $T$ and $T^{\prime}$ for every $x_{i}\in X^{\prime}$, $y_{j}\in Y^{\prime}$, and $z_{k}\in Z^{\prime}$. In this case, we write $T^{\prime}=T|_{X^{\prime},Y^{\prime},Z^{\prime}}$. We say the variables in $X\setminus X^{\prime}$, $Y\setminus Y^{\prime}$, and $Z\setminus Z^{\prime}$ have been zeroed-out; one can think of substituting in for those variables in $T$ to get to $T^{\prime}$.

Coppersmith and Winograd [CW90] formalized this approach to bounding $\omega$ by defining the value of a tensor. For $\tau\in[2/3,1]$, the $\tau$-value of $T$, written $V_{\tau}(T)$, is given by the supremum over all positive integers $n$, and all tensors of the form $\bigoplus_{i=1}^{m}\langle a_{i},b_{i},c_{i}\rangle$ which are restrictions of $(T\otimes T^{r}\otimes T^{rr})^{\otimes n}$, of

When $\tau$ is clear from context, we will simply write $V(T)$ and call it the value of $T$. One can see that for tensors $T,T^{\prime}$, the value $V_{\tau}$ satisfies $V_{\tau}(T\otimes T^{\prime})\geq V_{\tau}(T)\cdot V_{\tau}(T^{\prime})$ and $V_{\tau}(T\oplus T^{\prime})\geq V_{\tau}(T)+V_{\tau}(T^{\prime})$. We can also see that $V_{\tau}(\langle a,b,c\rangle)=(abc)^{\tau}$. We work with the tensor $T\otimes T^{r}\otimes T^{rr}$ instead of just $T$ in the definition of $V_{\tau}(T)$ since this more symmetric form can sometimes substantially increase the value of relatively ‘asymmetric’ tensors.

8 Coppersmith-Winograd Tensors

For a nonnegative integer $q$, the Coppersmith-Winograd tensor $CW_{q}$ is a tensor over $\{x_{0},\ldots,x_{q+1}\}$, $\{y_{0},\ldots,y_{q+1}\}$, $\{z_{0},\ldots,z_{q+1}\}$ given by

9 Salem-Spencer Sets

We briefly mention a ‘tensor interpretation’ of Theorem 2.2. For odd prime $M$, define the tensor $C_{M}$ over $\{x_{0},\ldots,x_{M-1}\}$, $\{y_{0},\ldots,y_{M-1}\}$, $\{z_{0},\ldots,z_{M-1}\}$ by

Letting $A$ be the set from Theorem 2.2, if we zero-out all $x_{i}$, $y_{i}$, and $z_{i}$ for which $i\notin A$ in $C_{M}$, then the result is the tensor

which is a direct sum of $|A|\geq M\cdot e^{-O(\sqrt{\log M})}$ terms.

Diagonalizing Arbitrary Tensors with Zeroing Outs

We now present a main new technical tool which we will later use in proving value lower bounds for tensors. It can be thought of as a generalization of Theorem 2.2 to tensors beyond just $C_{M}$. The resulting bound we get is not as large (it yields $\Omega(\sqrt{M})$ instead of $M\cdot e^{-O(\sqrt{\log M})}$ for $C_{M}$), although we show later in Theorem 3.2 and Theorem 3.3 that such a loss is required for this more general statement. The proof uses the probabilistic method.

Suppose $T$ is a tensor over $X,Y,Z$, with partitions $X=X_{1}\cup X_{2}\cup\cdots\cup X_{n}$, $Y=Y_{1}\cup Y_{2}\cup\cdots\cup Y_{n}$, $Z=Z_{1}\cup Z_{2}\cup\cdots\cup Z_{n}$ for some positive integer $n$. For $i,j,k\in[n]$, write $T_{ijk}:=T|_{X_{i},Y_{j},Z_{k}}$. Let $S=\{(i,j,k)\in[n]^{3}\mid T_{ijk}\neq 0\}$, and suppose that:

for all other $(i,j,k)\in S$, the three values $i,j,k$ are distinct.

Write $m:=(|S|-n)/n$, and suppose that $m\geq 1$. Then, there is a subset $I\subseteq[n]$ of size $|I|\geq\frac{2n}{3\sqrt{3m}}$ such that $T$ has a zeroing out into $\sum_{i\in I}T_{iii}$.

It follows that there is a choice of randomness with $|I|\geq\frac{2n}{3\sqrt{3m}}$. Fix this choice, then let $T^{\prime}$ be $T$ after zeroing-out every $X_{j},Y_{j},$ and $Z_{j}$ such that $j\notin I$; we claim this is the desired zeroing out. Evidently $T_{iii}$ is not zeroed out for any $i\in I$. Meanwhile, for any other $(i,j,k)\in S$, it must be that $T_{ijk}$ was zeroed out, i.e. at least one of $i,j,k$ is not in $I$, since either at least one of $i,j,k$ is not in $R$, in which case it would not be included in $I$, or else $i$ would have been included in $A$ and hence excluded from $I$. ∎

Theorem 3.1 shows how to start with a tensor $T$ which is a direct sum $\bigoplus_{i=1}^{n}T_{iii}$ plus roughly $m\cdot n$ additional subtensors $T_{ijk}$, and zero-out some variables so that $\Omega(n/\sqrt{m})$ of the $T_{iii}$ tensors remain, but all other subtensors are zeroed out. We will use this fact in the proof of Theorem 4.1 below to show that the value of $T$ is at least $V_{\tau}(T)\geq\Omega\left(\frac{n}{\sqrt{m}}\cdot\min_{i\in[n]}V_{\tau}(T_{iii})\right)$. It is natural to ask whether this $\sqrt{m}$ dependence is optimal; we next construct some tensors for which it is.

For positive integers $n\geq m$ with $n$ sufficiently large, there is a subset $S\subseteq\{(i,j,k)\in[n]^{3}\mid i,j,k\text{ distinct}\}$ with $|S|=mn$ such that, for any subset $I\subseteq[n]$ of size $|I|=\frac{n\log n}{\sqrt{m}}$, there is an $(i,j,k)\in S$ with $i,j,k\in I$.

Let $C$ be the set of subsets $I\subseteq[n]$ of size $\frac{n\log n}{\sqrt{m}}$. Hence,

Initially let $S=\emptyset$. We will repeatedly add an element $(i,j,k)$ to $S$, and then remove any remaining $I\in C$ with $i,j,k\in I$, until $C$ becomes empty. It suffices to show we only need to add $\leq mn$ elements to $S$.

At each step, we simply greedily pick any $(i,j,k)\in[n]^{3}$ with $i,j,k$ distinct which maximizes $|\{I\in C\mid i,j,k\in I\}|$. Note that if we pick three random distinct $i,j,k\in[n]$, then for a given $I\in C$, the probability that $i,j,k\in I$ is

for large enough $n$. It follows that we can pick $i,j,k$ which multiply $|C|$ by a factor which is less than $1-\frac{1}{2}\left(\frac{\log n}{\sqrt{m}}\right)^{3}$. After repeating $nm$ times, the resulting size of $C$ will be less than

for large enough $n$. Since $|C|$ is an integer, it follows that $|C|=0$ as desired. ∎

Let $S\subseteq[n]^{3}$ be the set from Theorem 3.2, with $|S|=m\cdot n$, and define the tensor $T$ over $\{x_{1},\ldots,x_{n}\}$, $\{y_{1},\ldots,y_{n}\}$, $\{z_{1},\ldots,z_{n}\}$ by

Theorem 3.2 says that, for any $I\subseteq[n]$ such that $T$ has a zeroing out into $\sum_{i\in I}x_{i}y_{i}z_{i}$, we must have $|I|<\frac{n\log n}{\sqrt{m}}$. This is nearly the size of the set $I$ constructed by Theorem 3.1.

The tensors to which we will apply Theorem 3.1 will have additional structure beyond those stipulated by Theorem 3.1. It is worth investigating whether the $\sqrt{m}$ factor in Theorem 3.1 can be improved for those tensors in particular. One particular property is that they are free, meaning, for any $i,j,k,i^{\prime},j^{\prime},k^{\prime}\in[n]$, such that $x_{i}y_{j}z_{k}$ and $x_{i^{\prime}}y_{j^{\prime}}z_{k^{\prime}}$ both have nonzero coefficients in $T$, at most one of $i=i^{\prime}$,$j^{\prime}=j$,$k=k^{\prime}$ holds. We can see that the tensor constructed from Theorem 3.2 is unlikely to be free. Nonetheless, with some additional work, we can construct a free tensor for which the $\sqrt{m}$ factor is still optimal:

For positive integers $n$ and $m$, with $n$ sufficiently large and $\log^{2}n\leq m\leq\sqrt{n/6}$, there is a subset $S\subseteq\binom{[n]}{3}$ with $|S|\leq O(mn)$ such that

any distinct $\{i,j,k\},\{i^{\prime},j^{\prime},k^{\prime}\}\in S$, have $|\{i,j,k\}\cap\{i^{\prime},j^{\prime},k^{\prime}\}|\leq 1$, and

for any subset $I\subseteq[n]$ of size $|I|=\frac{n\log(n)}{\sqrt{m}}$, there is an $\{i,j,k\}\in S$ with $i,j,k\in I$.

Let $N=2n$, and let $T=\binom{[N]}{3}$. Construct $S\subseteq T$ randomly by including each element of $T$ independently with probability $p:=\frac{Nm}{3|T|}$.

We compute some probabilities related to $S$.

Second, consider any fixed set $I\subseteq[N]$ of size $|I|=\frac{n\log n}{\sqrt{m}}$. For any three fixed elements $i,j,k\in I$, the probability that $\{i,j,k\}$ is not in $S$ is $1-\frac{Nm}{3|T|}\leq 1-\frac{2m}{N^{2}}$. Thus, for large enough $n$, the probability that no triple of $I$ is in $S$ is at most

Meanwhile, the number of sets $I\subseteq[N]$ of size $|I|=\frac{n\log n}{\sqrt{m}}$ is only

Thus the probability that all of those sets $I$ are covered by a triple in $S$ is overwhelming.

Let $U=[N]$ be the original universe. Now, repeat the following procedure that shrinks $U$ somewhat. If there are two triples $\{i,j,k\},\{i,j,k^{\prime}\}\in S$ which share two elements, then remove $i$ from $U$ (decreasing the size of $U$ by one, e.g. effectively making $U$ into $[N-1]$ the first time an element is removed). This removes all subsets $I$ of size $n(\log n)/\sqrt{m}$ containing $i$ and also removes all triples of $S$ containing $i$. The remaining subsets $I$ of $U$ of size $n(\log n)/\sqrt{m}$ are still covered by the remaining triples of $S$ as long as they were before we shrank $U$.

After this greedy procedure there are no more pairs of triples in $S$ that share a pair of elements. Let us consider the size of $U$ after the greedy procedure.

Let us fix two triples $(i,j,k),(i,j,k^{\prime})\in T$. The probability that both of them end up in (the original) $S$ is $\frac{N^{2}m^{2}}{9|T|^{2}}\leq\frac{2m^{2}}{N^{4}}$. The number of pairs of triples that share a pair of elements is $\leq N^{4}$. Thus the expected number of such pairs that end up in $T$ is $\leq 2m^{2}$. By Markov’s inequality, the probability that there are $>6m^{2}$ such pairs in $T$ is $\leq 1/3$.

Thus, with probability at least $1-1/3-1/3=1/3$, the original $S$ had size $\leq mN=2mn$ and we removed $\leq 6m^{2}$ elements from the universe. Since $m\leq\sqrt{n/6}$, we have removed $\leq N/2$ elements, and so the remaining universe size is at lest $N/2=n$. If necessary, remove more elements from $U$ until $|U|=n$, effectively removing the triples of $S$ and subsets of $U$ of size $n(\log n)/\sqrt{m}$ that contain these elements.

We get that for the remaining $S$, $|S|\leq O(mn)$, and with high probability, all subsets of $U$ of size $(n/\sqrt{m})\log(n)$ are covered by $S$. ∎

The requirement in Theorem 3.3 that $m\leq\sqrt{n/6}$ may seem restrictive, but all the tensors to which we will apply Theorem 4.1 have this property. Of course, the tensors to which we will apply Theorem 3.1 have even more structure still than just being free. We leave open the question of whether Theorem 3.1 can be further improved for them.

Refined Laser Method

Let $T$ be a tensor over $X,Y,Z$, with partitions $X=X_{1}\cup X_{2}\cup\cdots\cup X_{k_{X}}$, $Y=Y_{1}\cup Y_{2}\cup\cdots\cup Y_{k_{Y}}$, $Z=Z_{1}\cup Z_{2}\cup\cdots\cup Z_{k_{Z}}$ for some positive integers $k_{X},k_{Y},k_{Z}$, and for $(i,j,k)\in[k_{X}]\times[k_{Y}]\times[k_{Z}]$ define $T_{ijk}:=T|_{X_{i},Y_{j},Z_{k}}$. Let $S:=\{(i,j,k)\in[k_{X}]\times[k_{Y}]\times[k_{Z}]\mid T_{ijk}\neq 0\}$, and suppose there is an integer $P$ such that every $(i,j,k)\in S$ satisfies $i+j+k=P$. We call $T$ along with these partitions a $P$-partitioned tensor. Some prior work called $T$ a partitioned tensor whose outer structure is the tensor

Let $D$ be the set of $\alpha:S\to$ such that $\sum_{(i,j,k)\in S}\alpha(i,j,k)=1$. For each $\alpha\in D$, we define a few quantities.

First, for $(i,j,k)\in S$, write $\alpha_{ijk}:=\alpha(i,j,k)$. For $i\in[k_{X}]$ write

and similarly define $\alpha_{Y_{j}}$ for $j\in[k_{Y}]$ and $\alpha_{Z_{k}}$ for $k\in[k_{Z}]$. Define the three productsWe use the convention $0^{0}:=1$.

Finally, define $D_{\alpha}\subseteq D$, the set of $\beta\in D$ which have the same marginals as $\alpha$, by

We will show how to get a lower bound on $V_{\tau}(T)$ in terms of a given $\alpha\in D$, as follows:

For any tensor $T$ which is a $P$-partitioned tensor, any $\alpha\in D$, and any $\tau\in[2/3,1]$, we have

By comparison, the bound used by prior work [Vas12, LG14] was

Our Theorem 4.1 improves this by a factor of $\sqrt{\frac{\max_{\beta\in D_{\alpha}}\beta_{N}}{\alpha_{N}}}$, which is a strict improvement whenever there is a $\beta\in D_{\alpha}$ with $\beta_{N}>\alpha_{N}$. As we will see, this is frequently the case in the analysis of powers of $CW_{q}$ and their subtensors.

Throughout this section, we omit $\tau$ when writing $V_{\tau}$ and $\alpha_{V_{\tau}}$, and we will always use the specific $\tau$ in the statement of Theorem 4.1.

In the remainder of this section, we prove Theorem 4.1. Our proof strategy is as follows. Pick a large positive integer $n$, and consider the tensor $\mathcal{T}:=T^{\otimes n}\otimes T^{r\otimes n}\otimes T^{rr\otimes n}$. We are going to show that $\mathcal{T}$ can be zeroed out into a direct sum of

different tensors, each of which has value

As $n\to\infty$, this implies the desired bound on $V_{\tau}(T)=V_{\tau}(\mathcal{T})^{1/3n}$.

Our construction is divided into four main steps. The first three are mostly the same as the laser method from past work [CW90, DS13, Vas12, LG14], except that our analysis in step 3, in which we make use of Salem-Spencer sets, is more involved than in past work as we choose different parameters and need to preserve different properties of our tensor than in previous uses of the laser method. The main novel idea comes in step 4, where we apply our Theorem 3.1 as a final zeroing-out step which has not appeared in past work.

Before we begin, we make one technical remark: we will assume throughout this proof that $\alpha_{ijk}\cdot n$ is an integer for all $(i,j,k)\in S$. This can be achieved by adding a real number of magnitude at most $1/n$ to each $\alpha_{ijk}$ so that they are all integer multiples of $1/n$, while maintaining that $\sum_{(i,j,k)\in S}\alpha(i,j,k)=1$. In Appendix A below, we show that this is possible, and that the resulting changes to $\alpha$ only change the value bound (1) by a negligible multiplicative factor between $2^{-o(n)}$ and $2^{o(n)}$. Hence, this ‘rounding’ will not change the final bound in our proof.

2 Step 1: Removing blocks which are inconsistent with α𝛼\alpha

We say $X_{I}$ for $I\in[k_{X}]^{n}$ is consistent with $\alpha$ if, for all $i\in[k_{X}]$, we have

We define consistency with $\alpha$ for $Y_{J}$ for $J\in[k_{Y}]^{n}$, and $Z_{K}$ for $K\in[k_{Z}]^{n}$, similarly.

In $\mathcal{T}$, zero-out all $\mathcal{X}$-blocks $X_{I}\times Y_{J}\times Z_{K}$ where at least one of $X_{I},Y_{J},$ or $Z_{K}$ is not consistent with $\alpha$. Similarly, zero-out all $\mathcal{Y}$-blocks $Y_{J}\times Z_{K}\times X_{I}$ and all $\mathcal{Z}$-blocks $Z_{K}\times X_{I}\times Y_{J}$ where at least one of $X_{I},Y_{J},$ or $Z_{K}$ is not consistent with $\alpha$. Let $\mathcal{T}^{\prime}$ denote $\mathcal{T}$ after these zeroing outs.

The number of $X_{I}$ which are consistent with $\alpha$ is

we have that the number $N_{B}$ of remaining (not zeroed out) $\mathcal{X}$-blocks, $\mathcal{Y}$-blocks, or $\mathcal{Z}$-blocks in $\mathcal{T}^{\prime}$ is

For an $\mathcal{X}$-block $B_{X}=X_{I}\times Y_{J^{\prime}}\times Z_{K^{\prime\prime}}$, $\mathcal{Y}$-block $B_{Y}=Y_{J}\times Z_{K^{\prime}}\times X_{I^{\prime\prime}}$, and $\mathcal{Z}$-block $B_{Z}=Z_{K}\times X_{I^{\prime}}\times Y_{J^{\prime\prime}}$, we write $\mathcal{T}^{\prime}_{B_{X}B_{Y}B_{Z}}:=\mathcal{T}^{\prime}|_{B_{X},B_{Y},B_{Z}}$. We call $\mathcal{T}^{\prime}_{B_{X}B_{Y}B_{Z}}$ a block triple, and say that it uses $B_{X},B_{Y}$, and $B_{Z}$. For a $\beta\in D$, we say that $(X_{I},Y_{J},Z_{K})$ is consistent with $\beta$ if, for all $(i,j,k)\in S$,

Similarly, for $\beta,\beta^{\prime},\beta^{\prime\prime}\in D$, we say that $\mathcal{T}^{\prime}_{B_{X}B_{Y}B_{Z}}$ is consistent with $(\beta,\beta^{\prime},\beta^{\prime\prime})$ if $(X_{I},Y_{J},Z_{K})$ is consistent with $\beta$, $(X_{I^{\prime}},Y_{J^{\prime}},Z_{K^{\prime}})$ is consistent with $\beta^{\prime}$, and $(X_{I^{\prime\prime}},Y_{J^{\prime\prime}},Z_{K^{\prime\prime}})$ is consistent with $\beta^{\prime\prime}$.

we can count that the number of nonzero block triples $\mathcal{T}^{\prime}_{B_{X}B_{Y}B_{Z}}$ in $\mathcal{T}^{\prime}$ consistent with a given $(\beta,\beta^{\prime},\beta^{\prime\prime})$ for $\beta,\beta^{\prime},\beta^{\prime\prime}\in D_{\alpha,n}$ is

In particular, the number $N_{\alpha}$ of nonzero block triples in $\mathcal{T}^{\prime}$ consistent with $(\alpha,\alpha,\alpha)$ is

Moreover, we can count that the total number $N_{T}$ of nonzero block triples in $\mathcal{T}^{\prime}$ is at most

We will now describe a randomized process for zeroing-out more $\mathcal{X}$-blocks, $\mathcal{Y}$-blocks, and $\mathcal{Z}$-blocks. The ultimate goal is to zero-out a negligible $1-\exp(-o(n))$ fraction of blocks, so that for every remaining $\mathcal{X}$-block, $\mathcal{Y}$-block, and $\mathcal{Z}$-block, there is exactly one block triple which uses that block and is consistent with $(\alpha,\alpha,\alpha)$. Note that currently, by symmetry, every $\mathcal{X}$-block, $\mathcal{Y}$-block, and $\mathcal{Z}$-block in $\mathcal{T}^{\prime}$ has the same number $R$ of block triples which use that block and are consistent with $(\alpha,\alpha,\alpha)$. We can compute $R$ by dividing the total number of block triples consistent with $(\alpha,\alpha,\alpha)$ by the total number of blocks, to see that

Consider any $\mathcal{X}$-block $B_{X}=X_{I}\times Y_{J^{\prime}}\times Z_{K^{\prime\prime}}$, $\mathcal{Y}$-block $B_{Y}=Y_{J}\times Z_{K^{\prime}}\times X_{I^{\prime\prime}}$, and $\mathcal{Z}$-block $B_{Z}=Z_{K}\times X_{I^{\prime}}\times Y_{J^{\prime\prime}}$, such that $\mathcal{T}^{\prime}_{B_{X}B_{Y}B_{Z}}$ is a nonzero block triple in $\mathcal{T}^{\prime}$. Notice that

$h_{X}$ is pairwise-independent, i.e. for any two distinct $(I,J,K),(I^{\prime},J^{\prime},K^{\prime})\in[k_{X}]^{n}\times[k_{Y}]^{n}\times[k_{Z}]^{n}$, the values $h_{X}(I,J,K)$ and $h_{X}(I^{\prime},J^{\prime},K^{\prime})$ are independent (and similarly for $h_{Y}$ or $h_{Z}$).

For an $\mathcal{X}$-block $B_{X}=X_{I}\times Y_{J^{\prime}}\times Z_{K^{\prime\prime}}$, write $h_{X}(B_{X}):=h_{X}(I,J^{\prime},K^{\prime\prime})$, and similarly define $h_{Y}(B_{Y})$ for a $\mathcal{Y}$-block $B_{Y}$ and $h_{Z}(B_{Z})$ for a $\mathcal{Z}$-block $B_{Z}$.

Before continuing, we will bound the expected values of the following three random variables:

$C_{1}$, the number of nonzero block triples in $\mathcal{T}^{\prime\prime}$ consistent with $(\alpha,\alpha,\alpha)$,

$C_{2}$, the number of pairs of nonzero block triples in $\mathcal{T}^{\prime\prime}$ which are both consistent with $(\alpha,\alpha,\alpha)$ and which share a block (i.e. both use the same $\mathcal{X}$-block, $\mathcal{Y}$-block, or $\mathcal{Z}$-block), and

$C_{3}$, the number of nonzero block triples in $\mathcal{T}^{\prime\prime}$.

We next consider $C_{2}$, the number of pairs of nonzero block triples in $\mathcal{T}^{\prime\prime}$ which are both consistent with $(\alpha,\alpha,\alpha)$ and which both use the same $\mathcal{X}$-block, $\mathcal{Y}$-block, or $\mathcal{Z}$-block. The number of such pairs in $\mathcal{T}^{\prime}$ is $3N_{B}\cdot\binom{R}{2}$, since there are $N_{B}$ each of $\mathcal{X}$-blocks, $\mathcal{Y}$-blocks, and $\mathcal{Z}$-blocks in $\mathcal{T}^{\prime}$, and each has $R$ different block triples consistent with $(\alpha,\alpha,\alpha)$ which use it. Consider a fixed one of those pairs of $\mathcal{T}^{\prime}_{X_{B},Y_{B},Z_{B}}$ and $\mathcal{T}^{\prime}_{X_{B},Y_{B}^{\prime},Z_{B}^{\prime}}$, where we are assuming without loss of generality that they share an $\mathcal{X}$-block $X_{B}$. They will both not be zeroed out in $\mathcal{T}^{\prime\prime}$ if and only if $h_{X}(X_{B})\in A$, $h_{Y}(Y_{B})=h_{X}(X_{B})$, and $h_{Y}(Y_{B}^{\prime})=h_{X}(X_{B})$, which happens with probability $(|A|/M)\cdot(1/M)\cdot(1/M)=|A|/M^{3}$, as those three events are independent from the properties of $h_{X}$ and $h_{Y}$. Recall that $R=N_{\alpha}/N_{B}$ by definition of $R$, and $M\geq 100\cdot R$ by definition of $M$. Hence, using linearity of expectation, we can bound