arXiv:1708.05622v2 [cs.DS] 6 Nov 2017

Improved Rectangular Matrix Multiplication
using Powers of the Coppersmith-Winograd Tensor
François Le Gall
Graduate School of Informatics
Kyoto University
legall@i.kyoto-u.ac.jp

Florent Urrutia
IRIF
Université Paris Diderot
urrutia@irif.fr

Abstract
In the past few years, successive improvements of the asymptotic complexity of square matrix
multiplication have been obtained by developing novel methods to analyze the powers of the
Coppersmith-Winograd tensor, a basic construction introduced thirty years ago. In this paper we
show how to generalize this approach to make progress on the complexity of rectangular matrix
multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric
way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor,
we succeed in improving the complexity of rectangular matrix multiplication.
Let α denote the maximum value such that the product of an n × nα matrix by an nα × n
matrix can be computed with O(n2+ǫ ) arithmetic operations for any ǫ > 0. By analyzing the
fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower
bound α > 0.31389, which improves the previous lower bound α > 0.30298 obtained by Le Gall
(FOCS’12) from the analysis of the second power of the Coppersmith-Winograd tensor. More
generally, we give faster algorithms computing the product of an n × nk matrix by an nk × n
matrix for any value k 6= 1. (In the case k = 1, we recover the bounds recently obtained for
square matrix multiplication).
These improvements immediately lead to improvements in the complexity of a multitude of
fundamental problems for which the bottleneck is rectangular matrix multiplication, such as
computing the all-pair shortest paths in directed graphs with bounded weights.

1
1.1

Introduction
Background

Matrix multiplication is one of the most important problems in mathematics and computer science.
In 1969, Strassen discovered the first algorithm with subcubic complexity computing the product
of two square matrices [25]. In modern notation, Strassen’s result can be stated as an upper bound
ω < 2.81 on the exponent of square matrix multiplication ω, defined as the minimum value such
that two n × n matrices can be multiplied using O(nω+ǫ ) arithmetic operations for any constant
ǫ < 0. Strassen’s breakthrough initiated intense work on the complexity of matrix multiplication,
which in a span of a few decades lead to several improvements, culminating in the celebrated
O(n2.376 )-time algorithm for square matrix multiplication by Coppersmith and Winograd [10], i.e.,
the upper bound ω < 2.376 on the exponent of square matrix multiplication. This algorithm
is obtained from a basic construction, which is nowadays often called the Coppersmith-Winograd
tensor. Coppersmith and Winograd showed that analyzing this tensor gives the upper bound
ω < 2.388, and next showed that analyzing the second power of this tensor gives the improved
upper bound ω < 2.376.
A natural question, already mentioned in Coppersmith and Winograd’s paper [10], was whether
higher powers of the Coppersmith-Winograd tensor can lead to further improvement to the complexity of matrix multiplication. Most efforts to investigate this direction quickly stopped after
discovering that the third power does not seem to lead to any further improvement. More than
twenty year later, however, Stothers [24] (see also [11]) and Vassilevska Williams [28] showed that
the fourth power does give an improvement: the fourth power leads to the upper bound ω ≤ 2.373.
The technically challenging analysis of the fourth power was made possible by the introduction of
powerful general recursive techniques to analyze powers of tensors. Extending these techniques,
Vassilevska Williams [28] and then Le Gall [18] succeeded in analyzing higher powers up to the
32nd power, which gave additional small improvements and lead to the current best known upper
bound on the exponent of square matrix multiplication ω < 2.3728639. Table 1 summarises all
these results. Ambainis et al. [3] finally showed that further improving this upper bound will be
hard: they showed that analyzing higher powers of the Coppersmith-Winograd tensor (e.g., powers
64, 128,...) using the same methodology cannot give any further significant improvement on ω (in
particular it cannot lead to a proof of the popular conjecture ω = 2).
Besides square matrix multiplication, rectangular matrix multiplication plays a central role in
many algorithms as well. In addition to natural applications to computational problems in linear
algebra, typical examples of application include the construction of fast algorithms for the allpairs shortest paths problem [2, 21, 31, 34, 35], dynamic computation of the transitive closure
m
1
2
4
8
16
32

Upper bound
ω < 2.3871900
ω < 2.3754770
ω < 2.372927
ω < 2.372873
ω < 2.3728640
ω < 2.3728639

Reference
Coppersmith and Winograd [10]
Coppersmith and Winograd [10]
Vassilevska Williams [28]
Vassilevska Williams [28]
Le Gall [18]
Le Gall [18]

Table 1: Upper bounds on ω obtained by analyzing the m-th power of the Coppersmith and
Winograd tensor.

1

k
0.30298
0.31
0.32
0.33
0.34
0.35
0.40
0.45
0.50

upper bound
on ω(k)
2
2.000063
2.000371
2.000939
2.001771
2.002870
2.012175
2.027102
2.046681

k
0.5302
0.55
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00

upper bound
on ω(k)
2.060396
2.070063
2.096571
2.125676
2.156959
2.190087
2.224790
2.260830
2.298048
2.336306
2.375477

k
1.10
1.20
1.30
1.40
1.50
1.75
2.00
2.50
3.00
4.00
5.00

upper bound
on ω(k)
2.456151
2.539392
2.624703
2.711707
2.800116
3.025906
3.256689
3.727808
4.207372
5.180715
6.166736

Table 2: Upper bounds from [17] on the exponent of the multiplication of an n × nk matrix by an
nk × n matrix, obtained by analyzing the second power of the Coppersmith-Winograd tensor.
[12, 22], detection of subgraphs [29, 32], speed-up of sparse square matrix multiplication [4, 15,
33] and algorithms for bounded-difference min-plus square matrix multiplication [6]. Rectangular
matrix multiplication has also been used in computational complexity [1, 20, 30] and computational
geometry [14, 15].
The typical problem
when studying
rectangular matrix multiplication is computing
 kconsidered


k
the product of an n × n matrix by an n × n matrix, for some parameter k ≥ 0.1 In analogy to
the square case, the exponent of rectangular matrix multiplication, denoted ω(k), is defined as the
minimum value such that this product can be computed using O(nω(k)+ǫ ) arithmetic operations for
any constant ǫ > 0. Also note that for k = 1 (i.e., for square matrices), we have ω(1) = ω.
Coppersmith [8]
= 2. This surprising result means that the
 showed
 in 1982 that
 ω(0.172)

product of an n × n0.172 matrix by an n0.172 × n matrix can be computed in time almost linear
in the size of the output (which contains n2 entries). This discovery lead to the introduction of the
following quantity α:
α = sup{k | ω(k) = 2}.
Since proving that α = 1 is equivalent to proving that ω = 2, the quantity α is sometimes called the
dual exponent of matrix multiplication. Coppersmith’s result [8] then corresponds to the bound
α ≥ 0.172. Coppersmith [9] later showed that α > 0.29462 by analyzing the Coppersmith-Winograd
tensor in the context of rectangular matrix multiplication. Fifteen years later, Le Gall [17] showed
that the second power of the Coppersmith-Winograd tensor can also be analyzed in the context
of rectangular matrix multiplication, which lead to the improved lower bound α > 0.30298. This
analysis was actually much more general and gave bounds on ω(k) that improved prior bounds
[13, 16] for any k 6= 1. (For k = 1, i.e., square matrix multiplication, this approach recovered the
upper bound ω < 2.376 from [10]). The results from [17] are presented in Table 2.
1

Note that a basic result in algebraic complexity theory states
of the following
 that the algebraic
 complexities

three problems are the same: computing the product of an n × nk matrix by an nk × n matrix, computing the
 
 
product of an nk × n matrix by an n × n matrix, and computing the product of an n × n matrix by an n × nk
matrix. In this paper for concreteness we discuss only the first type of products, but all our bounds naturally hold
for the two other types as well.

2

k
k
0.31389
0.32
0.33
0.34
0.35
0.40
0.45
0.50

upper bound
on ω(k)
2
2.000064
2.000448
2.001118
2.001957
2.010314
2.024801
2.044183

0.5286
0.55
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00

upper bound
on ω(k)
2.057085
2.067488
2.093981
2.123097
2.154399
2.187543
2.222256
2.258317
2.295544
2.333789
2.372927

k
1.10
1.20
1.30
1.40
1.50
1.75
2.00
2.50
3.00
4.00
5.00

upper bound
on ω(k)
2.453481
2.536550
2.621644
2.708400
2.796537
3.021591
3.251640
3.721503
4.199712
5.171210
6.157233

Table 3: Our upper bounds on the exponent of the multiplication of an n × nk matrix by an nk × n
matrix, obtained by analyzing the fourth power of the Coppersmith-Winograd tensor.

1.2

Our results

In view of the recent progress in square matrix multiplication algorithms obtained by analyzing
higher powers of the Coppersmith-Winograd tensor, it is natural to ask whether the same approach
can be applied to obtain further improvements on the complexity of rectangular matrix multiplication as well. We investigate this question in this paper, and present a framework to extend the
analysis of higher powers to the case of rectangular matrix multiplication. We concretely focus on
the analysis of the fourth power of the Coppersmith-Winograd tensor and show that this analysis
leads to non-negligible improvements. The new upper bounds we obtain on the exponent of rectangular matrix multiplication ω(k) are given in Table 3 and the values for k ≤ 1 are plotted in
Figure 1.2 We obtain in particular the new lower bound
α ≥ 0.31389
on the dual exponent of matrix multiplication, as stated in the following theorem.




Theorem 1.1. The product of an n× n0.31389 matrix by an n0.31389 ×n matrix can by computed
with O(n2+ǫ ) arithmetic operations for any constant ǫ > 0.
This new bound improves the previous best known lower bound α > 0.30298 by Le Gall [17].
For other values of k as well, our new upper bounds on ω(k) are systematically better than those
of [17], as can be seen by comparing Table 2 and Table 3. For instance we obtain ω(3) ≤ 4.199712,
which improves the previous upper bound ω(3) ≤ 4.207372. Note that for k = 1 (i.e., for square
matrix multiplication), we obtain the same upper bound ω ≤ 2.372927 on the exponent of square
matrix multiplication as the bound obtained by analyzing the fourth power [11, 18, 24, 28]. Indeed,
for k = 1 our analysis becomes essentially the same as the analysis for the square case in those
prior works.
A surprising, or at least unexpected, aspect of the result of Theorem 1.1 is that the improvement
from the second power to the fourth power (from α > 0.30298 to α > 0.31389) exceeds the
improvement known from the first power to the second power (from α > 0.29462 to α > 0.30298).
This is completely different from the improvements achieved on ω when analyzing successive powers
2

Note that the curve of Figure 1 has the same shape as the curve for the second power given in [17].

3

ω(k)

2.372927

2
0

0.31389

1
k

Figure 1: Our upper bounds on the exponent of the multiplication of an n × nk matrix by an nk × n
matrix.
of the Coppersmith-Winograd tensor, which are decreasing, as summarized in Table 1. Actually,
all the numerical results we have obtained confirm that for any fixed value of k the improvements
on ω(k) decrease similarly to the square case when analyzing successive powers. For instance for
k = 0.8 and k = 2 the first power gives ω(0.8) < 2.2356 and ω(2) < 3.2699; by examining Tables 2
and 3 we observe that the improvement is larger from the first power to the second power. The
situation happens to be different, however, for lower bounds on α. Since the curves representing
the upper bounds on ω(k) have horizontal asymptotes at the lower bound on α (see Figure 1 of the
present paper and Figure 1 in [17]), even small improvements on ω(k) can lead to fairly significant
improvements on α, as our results show.
The most pressing question is now to investigate what will happen for even higher powers of
the Coppersmith-Winograd tensor (e.g., power 8 or 16). We believe that this question is important
since, besides its theoretical interest, further significant improvements for α may be obtained in
this way. A concrete approach would be to adapt to the rectangular case the numerically efficient
methods based on convex optimization developed, in the setting of square matrix multiplication,
to study high powers of the Coppersmith-Winograd tensor [18]. In the other direction, it may be
possible to show some limitations on the improvements achievable when studying higher powers,
by generalizing the recent approach developed for the square case [3].
Applications of our results. Our new bounds can be used to improve essentially all the known
algorithms based on rectangular matrix multiplication algorithms (e.g., the algorithms in [2, 14,
15, 21, 31, 29, 32, 34, 35]). Following [17], we discuss below one concrete example.
Zwick [35] has shown how to use rectangular matrix multiplication to compute the all-pairs
shortest paths in weighted direct graphs where the weights are bounded integers. The time complexity obtained by Zwick for graphs with constant weights is O(n2+µ+ǫ ), for any constant ǫ > 0,
where µ is the solution of the equation ω(µ) = 1 + 2µ. The results from [17] (see Table 2) show
that ω(0.5302) < 2.0604, which gives the upper bound µ < 0.5302. The results of the present paper
(see Table 3) show that ω(0.5286) < 2.0572, which gives the upper bound µ < 0.5286.

4

1.3

Overview of our approach

Before presenting an overview of the techniques used in this paper, we give an informal description
of algebraic complexity theory (a more detailed presentation of these notions is given in Section 2).
Trilinear forms and the asymptotic sum inequality. The matrix multiplication of an m × n
matrix by an n × p matrix can be represented by the following trilinear form, denoted as hm, n, pi:
hm, n, pi =

p
m X
n X
X

xrs yst zrt ,

r=1 s=1 t=1

where xrs , yst and zrt are formal variables. This form can be interpreted as follows: the (r, t)-th
entry of the product of an m × n matrix M by an n × p matrix M ′ can be obtained by setting
xij = Mij for all (i, j) ∈ [m] × [n] and yij = Mij′ for all (i, j) ∈ [n] × [p], setting zrt = 1 and setting
all the other z-variables to zero. One can then think of the z-variables as formal variables used to
record the entries of the matrix product.
More generally, a trilinear form t is represented as
XXX
t=
tuvw xu yv zw .
u∈A v∈B w∈C

where A, B and C are three sets, xu , yv and zw are formal variables and the tuvw ’s are coefficients
in a field F. The rank of the trilinear form t, denoted R(t), represents the number of multiplications
needed for the computation. The border rank of t, denoted R(t), is a generalization of the concept
of rank, which
P is also related to the complexity of computing the tensor.
A sum i ti of trilinear forms is a direct sum if the ti ’s do not share variables. Informally,
Schönhage’s asymptotic sum inequality [23] for rectangular matrix multiplication states that, if
the form t can be converted into a direct sum of c trilinear forms, each form being isomorphic to
hm, m, mk i, then
c · mω(k) ≤ R(t).
This implies that to obtain good upper bounds on the exponent of rectangular matrix multiplication,
it is enough to find a tensor t of low border rank that can be converted into many independent
(i.e., not sharing any variables) products of large enough rectangular matrices.
Overview of the analysis of the second power. We now give a brief overview of the analysis
of the second power of the Coppersmith-Winograd tensor given in [17] to derive the upper bounds
on ω(k) of Table 2. The Coppersmith-Winograd tensor is a trilinear form Fq introduced in [10].
Here q is a parameter (concretely, q is an integer between 2 and 10). Its second power Fq ⊗ Fq can
actually be written as a sum of fifteen terms Tuvw :
X
Fq ⊗ Fq =
Tuvw .
0≤u,v,w≤4
u+v+w=4

In order to apply Schönhage’s asymptotic sum inequality, this sum must first be converted into
a direct sum. This is done using a powerful general technique known as the laser method, first
introduced by Strassen [26] and then successively generalized and refined [10, 11, 13, 16, 17, 18, 24,
28]. The first step is to take the N -th tensor product of the basic construction, where N is a large
integer, and then zero variables so that the remaining terms do not share variables. Since we want
5

each remaining term to be isomorphic to a rectangular matrix product in order to obtain an upper
bound on ω(k) via Schönhage’s asymptotic sum inequality, the choice of zeroed variables has to be
done carefully. The laser method allows us, for any choice of the fifteen parameters auvw ∈ [0, 1]
satisfying specific constraints, to convert the N -th tensor product of the basic construction into a
direct sum of many terms (the number of these terms depending on the values of the auvw ’s), each
isomorphic to
O
⊗auvw N
Tuvw
.
(1)
0≤u,v,w≤4
u+v+w=4

The next step is to analyze each term (1) and show that it corresponds to a direct sum of
matrix products of the form hm, m, mk i (the number of terms in the direct sum and the value of m
will depend on the values of the auvw ’s and q). Some of the Tuvw ’s (more precisely, all the Tuvw ’s
except T112 , T121 and T211 ) can be analyzed in a straightforward way, since they correspond to
matrix products. The main technical contribution of the approach from [17] was to show that each
of the remaining three terms can be converted into a large number of objects called “C -tensors” in
Strassen’s terminology [27]. This conversion is done again via the laser method, which introduces
additional parameters. Finally, Ref. [17] explained how to convert these C -tensors into a direct
sum of matrix multiplication tensors. Combining the analysis of these fifteen terms shows that (1)
corresponds to a direct sum of matrix products of the form hm, m, mk i, as wanted. Schönhage’s
asymptotic sum inequality then gives the upper bound on ω(k) presented in Table 2 by numerically
optimizing the choice of the parameters (the choice of q, the auvw ’s and the additional parameters
arising in the second extraction).
Overview of our analysis of the fourth power. The fourth power of the CoppersmithWinograd tensor can be written as a sum of 45 terms Tuvw :
X
Fq⊗4 =
Tuvw .
0≤u,v,w≤8
u+v+w=8

For conciseness, this tensor will be denoted F through the paper. Similarly to the analysis of the
second power, the laser method allows us, for any choice of parameters auvw ∈ [0, 1] satisfying
specific constraints, to convert the N -th tensor product of the basic construction into a direct sum
of many terms, each isomorphic to
O
⊗auvw N
Tuvw
.
(2)
0≤u,v,w≤8
u+v+w=8

We call this process the first extraction, which is explained in detail in Section 3. Note that while
this extraction is more complicated than for the second power since the number of variables is larger
and deriving the constraints that the parameters should satisfy is more complex, conceptually the
analysis is fairly standard.
The main technical contribution of this work is a methodology to analyze each term (2). A
natural strategy would be to mimic the analysis done in [17] for the second power and analyze each
component Tuvw individually. While this leads to some improvement over the second power when
k is close to 1 (in particular, this leads to the same upper bound ω < 2.372927 as in prior works
analyzing the fourth power in the context of square matrix multiplication [24, 28]), this strategy
does not give any improvement for smaller values of k (in particular, no improved lower bound on
the dual exponent of matrix multiplication α). Our strategy, instead, is to analyze all the terms
Tuvw together via the laser method. As in the term-by-term analysis done for the second power
6

in [17], this introduces a set of new parameters for each term and a set of constraints that these
parameters should satisfy. A difference is that now some of the constraints are global: they can
involve the parameters of all the 45 terms. We call this process the second extraction, which is
explained in detail in Section 4. Note that this methodology appears to be more powerful than
the term-by-term conversion to C -tensors done in [17]: First, as already mentioned, the latter
approach does not seem to lead to any improvement on α for the fourth power. Second, our new
methodology, when applied to the analysis of the second power in replacement of the conversion
into C -tensors done in [17], already leads to upper bounds on ω(k) slightly better than those found
in [17] for some values of k (more precisely, we observed such improvements for values in the range
k ∈ [0.37, 0.46]).
The second extraction outlined in the previous paragraph actually does not completely analyze (2): it simply decomposes each term Tuvw into a direct sum of products of the fifteen terms
arising in the analysis of the second power. To complete the analysis, we recursively apply the
same strategy as for the second extraction and analyse the contribution of all these fifteen terms
together, again using the laser method (which introduce two additional parameters). We call this
process the third extraction, which is explained in detail in Section 5.
Finally, combining our three extractions, we conclude that the tensor F ⊗N can be converted into
a direct sum of c trilinear forms, each form being isomorphic to hm, m, mk i, for some values c and m
depending on all the parameters introduced. Applying Schönhage’s asymptotic sum inequality then
gives an inequality involving ω(k) and all these parameters (the formal statement is Theorem 6.1
in Section 6). Optimizing numerically the choice of parameters, under the constraints derived on
those parameters, gives the upper bounds of Table 3 and the lower bound on α of Theorem 1.1.

2

Preliminaries

We present various known results and tools related to matrix multiplication. Two good references
for an extensive treatment of this topic are [7] and [5].

2.1

General notations and definitions

In this paper we will use, for any positive integer n, the notation [[1, n]] to represent the set
{1,
P . . . , n}. Given a finite set X we denote P(X) the set of all function a : X →]0, 1[ ∩ Q such that
x∈X a(x) = 1. Note that the functions in P(X) are simply probability distributions on X where
the probabilities are rational and strictly between 0 and 1.
We define the notion of type. A type can be seen as a frequency vector.
Definition 2.1. Given N ∈ N, a finite set U , two mappings u : [[1, N ]] −→ U and t ∈ P(U ), we
say that u is of type t if |u−1 (x)| = t(x)N holds for all x ∈ U .

2.2

Tensors, matrix multiplication and the asymptotic sum inequality

Let F be a field, let u,v,w be three positive integers, and let U = Fu , V = Fv and W = Fw . A
tensor t of format (u, v, w) is an element of U ⊗ V ⊗ W = Fu×v×w , where ⊗ denotes the tensor
product. Fix a base (xi ) of U , a base (yj ) of V and a base (zk ) of W . We write xi yj zk as a short
cut for xi ⊗ P
yj ⊗ zk . The family (xi yj zk ) is a base of U ⊗ V ⊗ W , and thus t can be written in this
base as t =
tijk xi yj zk , where the tijk are coefficients in F. For a tensor written under this form,
ijk

7

we call the (xi ) the x variables, and similarly we call the (yj ) and the (zk ) the y variables and the
z variables.
Let t ∈ U ⊗ V ⊗ W and t′ ∈ U ′ ⊗ V ′ ⊗ W ′ be two tensors. The direct sum t ⊕ t′ , is a tensor in
(U ⊕U ′ )⊗(V ⊕V ′ )⊗(W ⊕W ′ ). The tensor product t⊗t′ is a tensor in (U ⊗U ′ )⊗(V ⊗V ′ )⊗(W ⊗W ′ ).
For any positive c, we will denote the tensor t ⊕ · · · ⊕ t (with c occurrences of t) by c · t and the
tensor t ⊗ · · · ⊗ t (with c occurrences of t) by t⊗c .
The tensor representing the multiplication of an m × n matrix by an n × p matrix over the
field F, denoted hm, n, pi, is the tensor of format (mn, np, mp) defined as
X
hm, n, pi =
tijk xi yj zk
ijk

where i spans [[1, m]] × [[1, n]], j spans [[1, n]] × [[1, p]], k spans [[1, m]] × [[1, p]] and

1 if i = (r, s), j = (s, t) and k = (r, t) for some integers (r, s, t) ∈ [[1, m]] × [[1, n]] × [[1, p]]
tijk =
0 otherwise.
We also consider the tensor of format (n, n, n) which represents n independent scalar products.
n
P
It is denoted by hni and is defined as hni =
xl yl zl .
l=1

The following definitions allow us to relate the properties of different tensors. Let λ denote an
indeterminate, and F[λ] the space of polynomials in λ with coefficients in F.
′

′

′

Definition 2.2. Let t ∈ Fu×v×w and t′ ∈ F[λ]u ×v ×w be two tensors. We say that t′ is a restriction
′
′
′
of t, and denote t′ ≤ t, if there are linear maps α : Fu −→ F[λ]u , β : Fv −→ F[λ]v , γ : Fw −→ F[λ]w
′
′
′
such that (α⊗β⊗γ)(t) = t′ where (α⊗β⊗γ) is the linear map Fu ⊗Fv ⊗Fw −→ F[λ]u ⊗F[λ]v ⊗F[λ]w
obtained by taking the tensor product of α, β, γ.
The intuition behind this notion is that the restriction of a tensor is easier to compute than
the original tensor, in the sense that an algorithm computing a tensor t can be converted into an
algorithm computing a tensor t′ ≤ t with the same complexity.
Definition 2.3. Let t ∈ F[λ]u×v×w and t′ ∈ Fu×v×w be two tensors. We say that t′ is an approximation of t, if there exists a tensor t′′ ∈ F[λ]u×v×w and some s ∈ N such that t = λs t′ + λs+1 t′′ .
We may also write : t = λs t′ + O(λs+1 ).
This is analogous to the notion of approximate computation.
′

′

′

Definition 2.4. Let t ∈ Fu×v×w and t′ ∈ Fu ×v ×w be two tensors. We say that t′ is a degeneration
of t, and denote t′ ✂ t, if t′ is an approximation of a restriction of t.
Note that by definition, t′ ≤ t =⇒ t′ ✂ t. The notion of degeneration can be seen as an
approximate conversion. It has the following property.
Proposition 2.1 (Proposition 15.25 in [7]). Let t1 , t′1 , t2 and t′2 be four tensors. Suppose that t′1 ✂t1
and t′2 ✂ t2 . Then t′1 ⊕ t′2 ✂ t1 ⊕ t2 and t′1 ⊗ t′2 ✂ t1 ⊗ t2 .
Definition 2.5. Let t be a tensor. The border rank of t is R(t) = min{r ∈ N | t ✂ hri}.

8

The notion of border rank enables us to formally define the exponent of rectangular matrix
multiplication, as follows. For any k ≥ 0,
ω(k) = inf{β | R(hn, ⌊nk ⌋, ni) = O(nβ )}.
The exponent of square matrix multiplication is ω = ω(1).
Similarly to almost all recent works on matrix multiplications, our main tool for proving lower
bounds on ω(k) will be Schönhage’s asymptotic sum inequality [23] (see [13, 16, 17, 19] for the
version of the inequality given below).
Theorem 2.1 (Schönhage’s asymptotic sum inequality). Let k, m and c be three positive integers.
Let t be a tensor such that c · hm, m, mk i ✂ t. Then
c · mω(k) ≤ R(t).

2.3

The fourth power of Coppersmith-Winograd tensor

For any positive integer q, the Coppersmith-Winograd tensor [10] is the tensor of format
(q + 2, q + 2, q + 2) defined as
Fq =

q
X
(x0 yi zi + xi y0 zi + xi yi z0 ) + x0 y0 zq+1 + x0 yq+1 z0 + xq+1 y0 z0 .
i=1

Coppersmith and Winograd showed that R(Fq ) ≤ q + 2.
They also considered the square of this tensor. For any t ∈ N, define the set
St = {(i, j, k) ∈ N3 | i + j + k = t}.

Define the tensors xii′ yjj ′ zkk′ = xi yj zk ⊗ xi′ yj ′ zk′ . By regrouping terms, we can write
X
Tijk
(Fq )⊗2 =
(i,j,k)∈S4

where
T004 = x0,0 y0,0 zq+1,q+1
q
q
X
X
x0,0 yi,0 zi,q+1 +
x0,0 y0,k zq+1,k
T013 =
i=1

k=1

T022 = x0,0 yq+1,0 z0,q+1 + x0,0 y0,q+1 zq+1,0 +
T112 =

q
X
i=1

xi,0 yi,0 z0,q+1 +

q
X

q
X

x0,0 yi,k zi,k
i,k=1
q
X

xi,0 y0,k zi,k +

x0,k y0,k zq+1,0 +

i,k=1

k=1

q
X

x0,k yi,0 zi,k

i,k=1

and the other eleven terms are obtained by permuting the indexes of the x variables, the y variables
and z variables in the above expressions (e.g., T040 = x0,0 yq+1,q+1 z0,0 and T400 = xq+1,q+1 y0,0 z0,0 ).
Note that R(Fq⊗2 ) ≤ (q + 2)2 from the submultiplicativity of the border rank.
Let us now consider the fourth power of the Coppersmith-Winograd tensor Fq (already studied,
in the context of square matrix multiplication, in Refs. [11, 24, 18, 28]). For any (i, j, k) ∈ S8 define
the set
Sijk = {((u, v, w), (u′ , v ′ , w′ )) ∈ S4 × S4 | u + u′ = i, v + v ′ = j, w + w′ = k}
9

and the tensor

X

Tijk =

((u,v,w),(u′ ,v′ ,w ′ ))∈Sijk

Tuvw ⊗ Tu′ v′ w′ .

By regrouping terms, the fourth power of Fq , which hereafter we simply denote F (the value of q
will be implicit until the very end of the paper), can be written as
F = (Fq )⊗4
= (Fq )⊗2 ⊗ (Fq )⊗2

 
X
Tuvw  ⊗ 
=
(u,v,w)∈S4

=

X

((u,v,w),(u′ ,v′ ,w ′ ))∈S42

=

X

(i,j,k)∈S8

=

X

X

(u′ ,v′ ,w ′ )∈S

Tuvw ⊗ Tu′ v′ w′

X

((u,v,w),(u′ ,v′ ,w ′ ))∈Sijk



4

Tu′ v′ w′ 

Tuvw ⊗ Tu′ v′ w′

Tijk .

(i,j,k)∈S8

Note that R(F ) ≤ (q + 2)4 , again from the submultiplicativity of the border rank.
When later working with the terms Tijk , we will sometimes consider the equivalent decomposition
X
Vijk [uvw]
Tijk =
(u,v,w)∈S ijk

where
S ijk = {(u, v, w) ∈ S4 , ∃ (u′ , v ′ , w′ ) ∈ S4 , u + u′ = i, v + v ′ = j, w + w′ = k}
and
∀ (u, v, w) ∈ S ijk , Vijk [uvw] = Tuvw ⊗ Ti−u,j−v,k−w .
For any integer N ∈ N and triple (I, J, K) with I = (I(1), . . . , I(N )), J = (J(1), . . . , J(N )),
K = (K(1), . . . , K(N )) such that (I(1), J(1), K(1)), . . . , (I(N ), J(N ), K(N )) ∈ S8 , define
TIJK = TI(1)J(1)K(1) ⊗ · · · ⊗ TI(N )J(N )K(N ) .
Notice that we define TIJK only for triple (I, J, K) from the set
{(I, J, K), ∀ l ∈ [[1, N ]], (I(l), J(l), K(l)) ∈ S8 } ∼
= S8N .
We can then write:

X

F ⊗N =

TIJK .

(I,J,K)∈S8N
N

Finally, for any triple (a, b, c) ∈ S8 and any triple (I, J, K) = (I(l), J(l), K(l))l∈[[1,N ]] ∈ S abc , we
define
N
O
Vabc [IJK] =
Vabc [I(l)J(l)K(l)].
l=1

10

2.4

Extraction from a tensor

In this subsection we explain our main tool to realize an extraction from a sum of tensors. An
extraction consists in assigning some variables to zero in a tensor (thus eliminating all their contributions to the sum). If a tensor T ′ is extracted from T , then T ′ ≤ T trivially holds. Our primary
goal is to guarantee that the resulting tensor T ′ is a direct sum of isomorphic tensors, so that the
asymptotic sum inequality can be used.
All recent progresses on square or rectangular matrix multiplication have been obtained by
performing extractions based on the so-called laser method [10, 11, 13, 16, 17, 18, 24, 26, 28].
Le Gall [17] introduced the following convenient framework to interpret such reductions in the
rectangular case. In this framework, a sum of tensors corresponds to a graph whose vertices are
the tensors in the sum. There is an edge between two vertices in the graph if and only if the two
corresponding terms in the sum of tensors share a variable. Let G denote this graph, and U denote
its set of vertices. Zeroing a term in the sum corresponds to removing one vertex from the graph.
As mentioned above, however, terms can be zeroed only by zeroing the variables it contains. This
means that such a zeroing operation may actually remove more than one vertex from the graph.
Extracting a direct sum from the original tensor is then equivalent to removing vertices from the
graph by such zeroing operations and reaching an edgeless graph. When using this methodology,
we will like to additionally guarantee that the vertices remaining in the final graph are from a
specified subset U ∗ ⊆ U . Concretely, the set U ∗ will be the set of vertices of terms matching a
certain type, which will ensure that all the tensors remaining after the extraction are of this type.
In our extractions we will use the following theorem from [17], which is tailored for this goal and
was already used for the analysis of the second power of the Coppersmith-Winograd tensor.
Theorem 2.2 (Theorem 4.2 in [17]). Let τ be a fixed positive integer. Let N be a large integer and
define the set

Λ = (I, J, K) ∈ [τ ]N × [τ ]N × [τ ]N | Iℓ + Jℓ + Kℓ = τ for all ℓ ∈ {1, . . . , N } .

Define the three coordinate functions f1 , f2 , f3 : [τ ]N × [τ ]N × [τ ]N → [τ ]N as follows.
f1 ((I, J, K)) = I
f2 ((I, J, K)) = J
f3 ((I, J, K)) = K

Let U be a subset of Λ such that there exist integers N1 , N2 and N3 for which the following property
holds: for any I ∈ [τ ]N ,
|{u ∈ U | f1 (u) = I}| ∈ {0, N1 }

|{u ∈ U | f2 (u) = I}| ∈ {0, N2 }

|{u ∈ U | f3 (u) = I}| ∈ {0, N3 }.
Let T1 = |f1 (U )|, T2 = |f2 (U )| and T3 = |f3 (U )|. Let G be the (simple and undirected) graph with
vertex set U in which two distinct vertices u and v are connected if and only if there exists one
index i ∈ {1, 2, 3} such that fi (u) = fi (v).
Assume there exists a set U ∗ ⊆ U such that
• |fi (U ∗ )| = Ti for each i ∈ {1, 2, 3};

11

• there exist integers N1∗ , N2∗ and N3∗ such that
|{u ∈ U | fi (u) = I}| = Ni ⇔ |{u ∈ U ∗ | fi (u) = I}| = Ni∗
for each I ∈ [τ ]N and each i ∈ {1, 2, 3}.
Define a removal operation as removing all the vertices u (if any) such that fi (u) = I, for a fixed
sequence I ∈ [τ ]N and a fixed position i ∈ {1, 2, 3} Then, for any constant ǫ > 0, the graph G can
be converted, with only removal operations, into an edgeless graph with


T1 N1∗
Ω
(N1 + N2 + N3 )1+ǫ
vertices, all of them being in U ∗ .

3

First extraction

In this section we describe our first extraction.
Let us consider any function a ∈ P(S8 ). For any (i, j, k) ∈ S8 we will often write a(ijk) instead
of a(i, j, k). Given a, we define the following three mappings:
X
a(ijk),
A : [[0, 8]] −→ ]0, 1[ i 7−→ A(i) =
j,k∈N|(i,j,k)∈S8

B : [[0, 8]] −→ ]0, 1[

j 7−→ B(j) =

C : [[0, 8]] −→ ]0, 1[

k 7−→ C(k) =

X

a(ijk),

i,k∈N|(i,j,k)∈S8

X

a(ijk).

i,j∈N|(i,j,k)∈S8

A,B,C are the projections of a on each of the three coordinates. We thus have
X
X
X
A(i) =
B(j) =
C(k) = 1.
i∈[[0,8]]

j∈[[0,8]]

k∈[[0,8]]

We are going to realize a first extraction from the tensor F ⊗N , where N is such that
∀ (i, j, k) ∈ S8 , a(ijk)N ∈ N (such an N always exists since the values of a are rational). The
goal is to zero variables so that, from the sum
X
F ⊗N =
TIJK ,
(I,J,K)∈S8N

we are left only with tensors TIJK where (I, J, K) is of type a, i.e, tensors isomorphic to
O
a(ijk)N
.
Tijk
(i,j,k)∈S8

We now explain how to achieve this goal.

12

The extraction. First notice that for any (I, J, K), (I ′ , J ′ , K ′ ) ∈ S8N such that I 6= I ′ , the x
variables in TIJK and in TI ′ J ′ K ′ are disjoint. We set to zero all the x variables except the ones
which appear in a TIJK where I is of type A, that is to say we set to zero all variables which appear
in a TIJK with I not of type A. We are thus left with only the tensors TIJK with I of type A.
We apply the same process for the y and z variables so that only remain the tensors TIJK with
I of type A, J of type B and K of type C. Let [a] denote the set of mappings a : S8 −→ ]0, 1[
which have the same projections as a and satisfy ∀ (i, j, k) ∈ S8 , a(ijk)N ∈ N. The tensors which
remain are exactly the tensors TIJK with (I, J, K) of type a ∈ [a].
The number of sequences I ∈ [[0, 8]]N of type A is


N
TX =
(A(i)N )i∈[[0,8]]
as choosing a sequence I of type A is equivalent to choose the location of the A(i) elements i for
i ∈ [[0, 8]]. Using the Stirling formula, we get, with the A(i) fixed and N −→ ∞,


N 
 1

TX = Θ  4
N



 8
Q

i=0





A(i)A(i)
1



.


Similarly, we define the number of sequences J ∈ [[0, 8]]N of type B as TY and the number of
sequences K ∈ [[0, 8]]N of type C as TZ .
For any fixed sequence I of type A, the number of remaining forms TIJK of type a is

8 
Y
A(i)N
∗
NX =
,
(a(ijk)N )j,k∈N|(i,j,k)∈S8
i=0

while the total number of remaining forms TIJK is

8 
XY
A(i)N
.
NX =
(a(ijk)N )j,k∈N|(i,j,k)∈S8
a∈[a] i=0

Define, the function g which associates to any mapping x : S8 −→ ]0, 1[ (i, j, k) 7−→ x(ijk) the
!−1
9
Q
P
l = 45,
x(ijk)x(ijk)
. Using Stirling’s formula, and the fact that |S8 | =
value g(x) =
l=1

(i,j,k)∈S8

we get that

NX∗



8
Q

A(i)A(i)
 g(a)

i=0
= Θ

N 18



N 



8
Q

A(i)A(i)
 X g(a)



i=0
 , NX = Θ 
N 18


a∈[a]

N 



.


Similarly, for any sequence J of type B, the number of remaining forms TIJK of type a and the
total number of remaining forms TIJK are

"
#N 
"
#N 
8
8
Q
Q

 g(a)
B(j)B(j) 
g(a)
B(j)B(j) 




X
j=0
j=0




∗
NY = Θ 
 , NY = Θ 
,




N 18
N 18
a∈[a]



13

and for any sequence K of type C, the number of remaining forms TIJK of type a and the total
number of remaining forms TIJK are



N 
N 
8
8
Q
Q
C(k)
C(k)
C(k)
C(k)


 X g(a)
 g(a)




k=0
k=0
∗
NZ = Θ 
 , NZ = Θ 
.
N 18
N 18




a∈[a]

Using the framework presented in Subsection 2.4, we get by Theorem 2.2 that for any ǫ > 0 we
can further extract from the remaining TIJK a direct sum of


TX NX∗
Ω
(NX + NY + NZ )1+ǫ
tensors TIJK , all of which are of type a. We want the number of tensors is this direct sum to be
high. For this to happen, we now formulate some conditions on a.

Conditions on a.

We first want to find a ∈ P(S8 ) such that g(a) = max g(a). Let us see g as
a∈[a]

a function from the set ]0, 1[45 to the set of positive real numbers. We want to find the maximum
f the
of g on the domain [a] ⊂]0, 1[45 . For this, we will find the maximum of g on the domain [a],
f ⊇ [a], and
set of mappings S8 −→ ]0, 1[ which have the same projections as a. Note that [a]
f
f is a convex subset of ]0, 1[45 . Consider the function ln g : [a]
f −→ R. For any a ∈ [a],
that [a]
P
−a(ijk) ln a(ijk). Since ln g is a concave function on a convex domain, any
ln g(a) =
(i,j,k)∈S8

critical point of ln g is a global maximum of ln g, and thus of g. We express the conditions satisfied
by the critical points below.
We first observe that ln g can actually be written as a (concave) function of only 21 variables,
namely a(215), a(224), a(233), a(242), a(251), a(260), a(314), a(323), a(332), a(341), a(350),
a(413), a(422), a(431), a(440), a(512), a(521), a(530), a(611), a(620), a(710). This is because ln g
f and the elements of [a]
f have, by definition, the same projections as a, and thus
is defined on [a],
f the a(ijk) satisfy the following system of linear equations:
for any a ∈ [a]
∀ i ∈ [[0, 8]], A(i) =
∀ j ∈ [[0, 8]], B(j) =
∀ k ∈ [[0, 8]], C(k) =

X

a(ijk),

j,k∈N|(i,j,k)∈S8

X

a(ijk),

i,k∈N|(i,j,k)∈S8

X

a(ijk).

i,j∈N|(i,j,k)∈S8

Resolving of the (homogeneous) linear system3 reduces the number of variables to 21, as claimed.
From now we will assume that a satisfies the symmetry condition
∀ (i, j, k) ∈ S8 , a(ijk) = a(ikj).
3

A Maple file deriving the symbolic solution of this system is available at [36].

14

(C1)

∂ ln g
= 0 leads, after simplification
∂a(ijk)
and by condition (C1), to a system of 10 non linear equations:

Computing each one of the 21 partial differential equations

0 = − ln(a(017)) + ln(a(026)) + ln(a(107)) − ln(a(125)) − ln(a(206)) + ln(a(215)),
0 = − ln(a(017)) + ln(a(026)) + ln(a(107)) − ln(a(116)) − ln(a(602)) + ln(a(611)),
0 = − ln(a(017)) + ln(a(035)) + ln(a(107)) − ln(a(134)) − ln(a(305)) + ln(a(314)),
0 = − ln(a(017)) + ln(a(044)) + ln(a(107)) − ln(a(134)) − ln(a(404)) + ln(a(413)),
0 = − ln(a(017)) + ln(a(035)) + ln(a(107)) − ln(a(125)) − ln(a(503)) + ln(a(512)),

0 = − ln(a(017)) + ln(a(035)) + ln(a(107)) + ln(a(116)) − ln(a(125)) − ln(a(134))−
ln(a(206)) + ln(a(224)),

(C2)

0 = − ln(a(017)) + ln(a(044)) + ln(a(107)) + ln(a(116)) − ln(a(134)) − ln(a(134))−
ln(a(206)) + ln(a(233)),

0 = − ln(a(017)) − ln(a(026)) + ln(a(035)) + ln(a(044)) + ln(a(107)) + ln(a(116))−
ln(a(134)) − ln(a(134)) − ln(a(305)) + ln(a(323)),

0 = − ln(a(017)) − ln(a(026)) + ln(a(044)) + ln(a(035)) + ln(a(107)) + ln(a(116))−
ln(a(134)) − ln(a(134)) − ln(a(305)) + ln(a(323)),

0 = − ln(a(017)) − ln(a(026)) + ln(a(044)) + ln(a(035)) + ln(a(107)) + ln(a(116))−
ln(a(134)) − ln(a(125)) − ln(a(404)) + ln(a(422)).

Note that, as the value of any a ∈ [a] is fixed from the values of only 21 variables, and as
∀ (i, j, k) ∈ S8 , a(ijk)N ∈ [[1, N ]], we have |[a]| ≤ N 21 . For any a satisfying these 10 equations, we
have g(a) = max g(a) and thus, NX = O(N 21 NX∗ ), NY = O(N 21 NY∗ ), NZ = O(N 21 NZ∗ ).
a∈[a]

Final statement. Let us also impose the condition
8
Y
i=0

A(i)A(i) ≥

8
Y

B(j)B(j) .

(C3)

j=0

By the symmetry condition (C1), this implies that

8
Q

i=0

A(i)A(i) ≥

8
Q

k=0

NY∗ = NZ∗ = O(NX∗ ), and thus we obtain (NX + NY + NZ ) = O(N 21 NX∗ ) and


TX NX∗
TX
.
=Ω
(NX + NY + NZ )1+ǫ
(N 21(1+ǫ) (NX∗ )ǫ
As by definition NX∗ ≤ |S8 |N = 45N , this is equal to



1

r1 = Ω  25+21ǫ N ǫ
N
45

We obtain the following final result.

15





 8
Q

i=0

N 





A(i)A(i)
1



.


C(k)C(k) .

We get

Theorem 3.1. Let q be any positive integer. Let a be any function from P(S8 ) satisfying the
constraints (C1), (C2) and (C3). Then for any ǫ > 0, the trilinear form F ⊗N admits a restriction
N
⊗a(ijk)N
which is a direct sum of r1 trilinear forms, each of which is isomorphic to
.
Tijk
(i,j,k)∈S8

4

Second extraction

As we will see later in details in Section 6, the tensors Tijk for (i, j, k) ∈ S8 with one or more of
their indices i, j, k equal to 0 are actually matrix products tensors. No further work is required for
them. In contrast, the tensors Tijk for (i, j, k) ∈ S 8 where S 8 = {(i, j, k) ∈ S8 | i > 0, j > 0, k > 0}
do not correspond to matrix products.
We are now going to realize an extraction on all the tensors Tijk , (i, j, k) ∈ S 8 . We first study
the properties of the Tijk , (i, j, k) ∈ S 8 . In Subsection 4.1, we consider the particular case of the
tensors T233 , T323 and T332 . In Subsection 4.2, we consider the remaining tensors, i.e., the tensors
Tijk for (i, j, k) ∈ S8′ = S 8 \ {(2, 3, 3), (3, 2, 3), (3, 3, 2)}, which are actually easier to analyze. Then,
in Subsection 4.3, we explain the limitations of independent extractions and introduce our method
to realize a joint extraction.

4.1

The tensors T233 , T323 , T332

The extractions from the tensors T233 , T323 , T332 can be realized similarly to the extraction from
the tensor F that we realized in Section 3. As the situation is similar for the three tensors, we only
detail the extraction from the tensor T233 .
We start from the decomposition
X
V233 [uvw].
T233 =
(u,v,w)∈S 233

By definition of the (Tijk )(i,j,k)∈S4 , for any (i, j, k), (i′ , j ′ , k′ ) ∈ S 233 such that i 6= i′ , the x variables in
Tijk and in Ti′ j ′ k′ are disjoints, and thus the x variables in V233 [ijk] and in V233 [i′ j ′ k′ ] are disjoint.
a(233)N
We can thus realize an extraction from T233
just as in Section 3. We consider a mapping
a233 ∈ P(S 233 ), with projections A233 , B233 , C233 . As the (a233 (ijk)a(233)) are rational numbers,
and as N will later go to infinity, we can assume that ∀ (i, j, k) ∈ S 233 , a233 (ijk)a(233)N ∈ N. We
impose the symmetry condition ∀ (i, j, k) ∈ S 233 , a233 (ijk) = a233 (ikj), and thus B233 = C233 . We
also impose the symmetry condition
∀ (i, j, k) ∈ S 233 , a233 (ijk) = a233 (2 − i, 3 − j, 3 − k),
as V233 [ijk] = V233 [2 − i, 3 − j, 3 − k]. By realizing an extraction successively on the x variables, the
a(233)N
y variables and the z variables, we are left with the tensors V233 [IJK] where (I, J, K) ∈ S 233
is of type a233 ∈ [a233 ]. Here [a233 ] denotes the set of mappings a233 : S 233 −→ ]0, 1[ which have
the same projections as a233 and satisfy ∀ (i, j, k) ∈ S 233 , a233 (ijk)a(233)N ∈ N.
The number of sequences I ∈ [[0, 2]]a(233)N of type A233 is
 
T233,X =



a(233)N
(A233 (i)a(233)N )i∈[[0,2]]




1
= Θ
N

16



 2
Q

i=0

a(233)N 



1

.




A
(i)
(i) 233

A233

Define the function g233 which associates to any mapping x : S 233 −→ ]0, 1[ (i, j, k) 7−→ x(ijk)
the value
−1

Y
x(ijk)x(ijk)  .
g233 (x) = 
(i,j,k)∈S 233

For any fixed sequence I of type A233 , the number of remaining forms V233 [IJK] with (I, J, K) of
type a233 is

∗
N233,X

=

2 
Y
i=0

A233 (i)a(233)N
(a233 (ijk)a(233)N )j,k∈N|(i,j,k)∈S 233





2
Q

(i)A233 (i)

A233
 g233 (a233 )

i=0
= Θ

(a(233)N )7/2

a(233)N 

while the total number of remaining forms V233 [IJK] is
N233,X =

X

2 
Y

a233 ∈[a233 ] i=0





= Θ


X

A233 (i)N
(a233 (ijk)a(233)N )j,k∈N|(i,j,k)∈S 233



g233 (a233 )

2
Q

A233

(i)A233 (i)

i=0

(a(233)N )7/2

a233 ∈[a233 ]



,




a(233)N 



.


Similarly, for any fixed sequence J of type B233 , the number of remaining forms V233 [IJK] with
(I, J, K) of type a233 is
"
#a(233)N 
3
Q

 g233 (a233 )
B233 (j)B233 (j)


j=0


∗
N233,Y
= Θ
,
3


(a(233)N )


the total number of remaining forms V233 [IJK] is

"
N233,Y

3
Q


g233 (a233 )
B233 (j)B233 (j)
 X
j=0

= Θ

(a(233)N )3
a233 ∈[a233 ]

#a(233)N 




,



and for any fixed sequence K of type C233 , the number of remaining forms V233 [IJK] with
(I, J, K) of type a233 is N233,Z = N233,Y and the total number of remaining forms V233 [IJK]
∗
∗
is N233,Z
= N233,Y
.
By studying the function g233 in a similar way as we studied the function g in Section 3, we get
that g(a233 ) = max g(a233 ) for a233 satisfying the constraint
a233 ∈[a233 ]

2 ln(a233 (211)) + ln(a233 (130)) − ln(a233 (202)) − ln(a233 (220)) − ln(a233 (112)) = 0.
17

Calculations show that a233 ∈ [a233 ] can be written as a function of a233 (130) and
a233 (103) only, and as a233 (130), a 233 (103) ∈ [[1, a(233)N ]], we have that |[a233 ]| ≤ (a(233)N )2
∗
∗
and thus we obtain N233,X = O((a(233)N )2 N233,X
), N233,Y = O((a(233)N )2 N233,Y
) and
2
∗
N233,Z = O((a(233)N ) N233,Z ).
The tensors T323 and T332 are analysed similarly. Imposing the constraints
2 ln(a323 (121)) + ln(a323 (310)) − ln(a323 (022)) − ln(a323 (220)) − ln(a323 (112)) = 0

2 ln(a332 (112)) + ln(a332 (031)) − ln(a332 (202)) − ln(a332 (022)) − ln(a332 (211)) = 0
∗
∗
implies that N323,X = O(N 2 N323,X
) and N332,X = O(N 2 N332,X
).

To summarize, when analyzing T233 , T323 and T332 we need to impose the following three
constraints (in addition to other constraints discussed later):
2 ln(a233 (211)) + ln(a233 (130)) − ln(a233 (202)) − ln(a233 (220)) − ln(a233 (112)) = 0

2 ln(a323 (121)) + ln(a323 (310)) − ln(a323 (022)) − ln(a323 (220)) − ln(a323 (112)) = 0

(D2)

2 ln(a332 (112)) + ln(a332 (031)) − ln(a332 (202)) − ln(a332 (022)) − ln(a332 (211)) = 0.

4.2

The tensors of S8′

We adopt the same notations as in the previous subsection. We consider as before mappings aijk ∈ P(S ijk ) for (i, j, k) ∈ S8′ , with projections Aijk , Bijk and Cijk , and assume as
before ∀ (u, v, w) ∈ S ijk , aijk (uvw)a(ijk)N ∈ N. For (i, j, k) ∈ S8′ , the number of sequences
I ∈ [[0, i]]a(ijk)N of type Aijk is




a(ijk)N

Tijk,X =



a(ijk)N
(Aijk (u)a(ijk)N )u∈[[0,i]]




 1
= Θ
 2i
N



 i
Q

u=0

1

Aijk (u)Aijk





(u)



.



The extractions on the elements of S8′ are simpler in the sense that we have
∀ (i, j, k) ∈ S8′ , [aijk ] = {aijk }, i.e., fixing the projections Aijk , Bijk and Cijk fixes all the values
of the mapping aijk . We thus have
∗
∗
∗
Nijk,X = Nijk,X
, Nijk,Y = Nijk,Y
, Nijk,Z = Nijk,Z
,

with

Nijk,X =

Nijk,Y =

i 
Y

x=0

j 
Y

y=0

Aijk (x)a(ijk)N
(aijk (xyz)a(ijk)N )y,z∈N|(x,y,z)∈S ijk

Aijk (y)a(ijk)N
(aijk (xyz)a(ijk)N )x,z∈N|(x,y,z)∈S ijk





18



i
Q

a(ijk)N 

Aijk (x)Aijk (x)
 gijk (aijk )

x=0
= Θ

|S ijk | − (i + 1)
2
(a(ijk)N )
"

j
Q



,


#a(ijk)N 

 gijk (aijk )
Bijk (y)Bijk (y)

y=0

= Θ

|S ijk | − (j + 1)

2
(a(ijk)N )




,



Nijk,Z =

4.3

k 
Y

z=0



Aijk (z)a(ijk)N
(aijk (xyz)a(ijk)N )x,y∈N|(x,y,z)∈S ijk





= Θ



a(ijk)N 

gijk (aijk )
Cijk (z)Cijk (z)

z=0
.

|S ijk | − (k + 1)

2
(a(ijk)N )
k
Q

The joint extraction

If we were to realize the extraction on each of the Tijk , (i, j, k) ∈ S 8 independently, we would have
to impose either the constraints
∀ (i, j, k) ∈ S 8 ,

i
Y

Aijk (x)

Aijk (x)

x=0

≥

j
Y

Bijk (y)

Bijk (y)

i
Y

and

Aijk (x)

Aijk (x)

x=0

y=0

≥

k
Y

Cijk (z)Cijk (z)

z=0

or, as in [17], introduce the notion of C -tensor to perform the analysis. It does not seem, however,
that any of these two approaches is helpful for analyzing the fourth power of the CoppersmithWinograd tensor in the rectangular setting (in particular, the above constraints are too strong and
do not lead to any improved lower bound on α). Instead, we are going to realize a global extraction
directly on the tensor
O
⊗a(ijk)N
.
(3)
Tijk
(i,j,k)∈S 8

Note that this tensor can be decomposed as follows:

O

⊗a(ijk)N

Tijk

O

=

(i,j,k)∈S 8

(i,j,k)∈S 8

O

=

(i,j,k)∈S 8
a(ijk)N

where for (I, J, K) ∈ S ijk
O






X

a(ijk)N

(I,J,K)∈S ijk




Vijk [IJK]

Vijk [I(l)J(l)K(l)].

l∈[[1,a(ijk)N ]]

⊗a(ijk)N

Tijk

=

(i,j,k)∈S 8

(I,J,K)∈

X
Q

a(ijk)N

S ijk

(i,j,k)∈S8

where we see (I, J, K) ∈

Vijk [uvw]

(u,v,w)∈S ijk



N

, Vijk [IJK] =

⊗a(ijk)N

X

Q

(i,j,k)∈S 8
a(ijk)N
.
S ijk

a(ijk)N

S ijk




O

(i,j,k)∈S 8



Vijk [Iijk Jijk Kijk ]

as a family (Iijk , Jijk , Kijk )(i,j,k) indexed by (i, j, k) ∈ S 8

with (Iijk , Jijk , Kijk ) ∈
Let (i, j, k) ∈ S 8 . By definition of the (Tuvw )(u,v,w)∈S4 , for any (u, v, w), (u′ , v ′ , w′ ) ∈ S ijk such
that u 6= u′ , the x variables in Tuvw and in Tu′ v′ w′ are disjoint, and thus the x variables in Vijk [uvw]
a(ijk)N

′ , J′ , K′ ) ∈ S
and in Vijk [u′ v ′ w′ ] are disjoint. This implies that for any (Iijk , Jijk , Kijk ), (Iijk
ijk
ijk
ijk
′
′
′
′ , the x variables in V [I J
with Iijk 6= Iijk
ijk ijk ijk Kijk ] and in Vijk [Iijk Jijk Kijk ] are disjoint.
The x variables of the tensor (3) are indexed by a sequence of indices. This sequence can be
divided in a partition of subsequences, each subsequence being associated to a Vijk [Iijk , Jijk , Kijk ]

19

Q
a(ijk)N
with I 6= I ′ , the x
for a (i, j, k) ∈ S 8 . Hence, for any (I, J, K), (I ′ , J ′ , K ′ ) ∈ (i,j,k)∈S 8 S ijk
N
N
′
′
′
′
′
′
variables in V [IJK] =
(i,j,k)∈S 8 Vijk [Iijk Jijk Kijk ] and V [I J K ] =
(i,j,k)∈S 8 Vijk [Iijk Jijk Kijk ]
are disjoint.
We rewrite the tensor (3) as
X
O
⊗a(ijk)N
=
Tijk
V [IJK].
(i,j,k)∈S 8

(I,J,K)∈

Q

a(ijk)N

S ijk

(i,j,k)∈S8

e = (Aijk )
e
Define e
a = (aijk )(i,j,k)∈S 8 and the three projections A
(i,j,k)∈S 8 , B = (Bijk )(i,j,k)∈S 8 ,

e = (Cijk )
C
(i,j,k)∈S 8 . We extend the definition of type (Definition 2.1) to a product of types: we say,
Q
a(ijk)N
e if for every (i, j, k) ∈ S 8 , Iijk is of type
, that I is of multi-type A
for (I, J, K) ∈ (i,j,k)∈S 8 S ijk
Aijk , and that (I, J, K) is of multi-type e
a if for every (i, j, k) ∈ S 8 (Iijk , Jijk , Kijk ) is of type aijk .
We set to 0 all the x variables except those that appear in a V [IJK] where I is of multi-type
e We apply the same procedure for the y variables with the multi-type B
e and for the z variables
A.
e We are thus left with only the tensors V [IJK] with I of multi-type A,
e J
with the multi-type C.
e
e
of multi-type B, K of multi-type C.
By definition of a multi-type, the number of I of multi-type Ã is
Y
Tf
Tijk,X .
X =
(i,j,k)∈S 8

For any fixed I of multi-type Ã, the number of remaining tensors V [IJK] with (I, J, K) of multitype ã is
Y
∗
e∗ =
Nijk,X
.
N
X
(i,j,k)∈S 8

For any fixed I of multi-type Ã, the number of remaining tensors V [IJK] is
Y
eX =
Nijk,X .
N
(i,j,k)∈S 8

For any fixed J of multi-type B̃, the number of remaining tensors V [IJK] is
Y
eY =
N
Nijk,Y .
(i,j,k)∈S 8

For any fixed K of multi-type C̃, the number of remaining tensors V [IJK] is
Y
eZ =
Nijk,Z .
N
(i,j,k)∈S 8

We now show that we are under the conditions of Theorem 2.2. We set




Y
a(ijk)N
Λ′ = (I, J, K) ∈
S4
.


(i,j,k)∈S 8

a(ijk)N

a(ijk)N

Note that as ∀ (i, j, k) ∈ S 8 , S ijk P⊆ S4
, for any remaining tensor V [IJK], we
a(ijk).
By defining an arbitrary ordering
have that (I, J, K) ∈ Λ′ . Let γ =
(i,j,k)∈S 8
θ : (i, j, k, l) 7−→ [[1, γN ]] for (i, j, k) ∈ S 8 and l ∈ [[1, a(ijk)N ]], we have Λ′ ∼
= Λ where
20

n
o
Λ = (I, J, K) ∈ [[0, 4]]γN ×[[0, 4]]γN ×[[0, 4]]γN | ∀ d ∈ [[1, γN ]], I[θ −1 (d)]+J[θ −1 (d)]+K[θ −1 (d)] = 4

with the notation I[(i, j, k, l)] = Iijk (l), J[(i, j, k, l)] = Jijk (l), K[(i, j, k, l)] = Kijk (l).
g
g
f
We set U to be set of (I, J, K) of the remaining V [IJK]. We set N1 = N
X , N2 = NY , N3 = NZ .
∗
We set U to be the set of (I, J, K) of the remaining V [IJK] with (I, J, K) of multi-type e
a. We
∗
∗
∗
∗
∗
∗
g
g
f
f
f
f
set N1 = NX , N2 = NY , N3 = NZ . We set T1 = TX , T2 = TY , T3 = TZ , and all the conditions of
N
⊗a(ijk)N
, a direct sum of
Tijk
Theorem 2.2 are satisfied. Fix ǫ > 0. We obtain, from
(i,j,k)∈S 8

!

∗
g
Tf
X NX
g
g f 1+ǫ
(N
X + NY + NZ )

Ω

trilinear forms, each of which being a V [IJK] with (I, J, K) of multi-type e
a, i.e., isomorphic to


O
O

Vuvw (ijk)⊗auvw (ijk)a(uvw)N  .
(u,v,w)∈S 8

(i,j,k)∈S uvw

We now impose the constraint
Y

(i,j,k)∈S 8

i
Y

Aijk (x)Aijk (x)

x=0

!a(ijk)

This implies that
Y

(i,j,k)∈S 8

≥

Y

(i,j,k)∈S 8



Nijk,Y = O 




Y

(i,j,k)∈S 8

g
g
i.e., N
Y = O(NX ).
We impose the symmetry condition

j
Y

y=0

a(ijk)

Bijk (y)Bijk (y) 

.

(D3)



Nijk,X 

∀ (i, j, k) ∈ S 8 , ∀ (u, v, w) ∈ S ijk , aijk (uvw) = aijk (i − u, j − v, k − w) = aikj (u, w, v).

(D1)

g
f
f
g
The symmetry conditions (C1) and (D1) give N
Y = NZ and NZ = O(NX ). The number of terms
in the direct sum that we obtain is
!
∗
g
Tf
X NX
.
Ω
1+ǫ
g
N
X

∗
. Let us rewrite
We have seen in Subsection 4.2 that ∀ (i, j, k) ∈ S8′ , Nijk,X = Nijk,X



g
N
X =

Y

(i,j,k)∈S8′

and



∗
g

N
X =

Y

(i,j,k)∈S8′



Nijk,X  

Y

(i,j,k)∈{(2,3,3),(3,2,3),(3,3,2)}



Y

∗

Nijk,X

(i,j,k)∈{(2,3,3),(3,2,3),(3,3,2)}

21



Nijk,X 


∗
.
Nijk,X

∗
We have seen in Section 4.1 that by imposing the constraints (D2) we have N233,X = O(N 2 N233,X
),
2
∗
2
∗
N323,X = O(N N323,X ) and N332,X = O(N N332,X ). Therefore we have

Y

(i,j,k)∈{(2,3,3),(3,2,3),(3,3,2)}



Nijk,X = O N 6

Y

(i,j,k)∈{(2,3,3),(3,2,3),(3,3,2)}



∗
,
Nijk,X

6g
∗
g
and thus N
X = O(N NX ) and the number of terms in the direct sum that we obtain is
!
Tf
X
.
Ω
∗ǫ
g
N 6(1+ǫ) N
X

For any (i, j, k) ∈ S 8 , by definition we have
∗
Nijk,X

a(ijk)N

≤ |S ijk |

a(ijk)N

≤ |S4 |

=

5
X
l=1

l

!a(ijk)N

= 15a(ijk)N

N
∗
g
and thus N
X ≤ 15 , and the number of terms in the direct sum is
!
Tf
X
.
Ω
15N ǫ N 6(1+ǫ)

Replacing Tf
X by its expression, this is equal to




r2 = Ω 



1
6ǫ+6+

15N ǫ N

P
(i,j,k)∈S 8



i
2




 Y 


 i

(i,j,k)∈S 8  Q A
ijk
u=0

a(ijk) N 
 

 
1

 .

 

 
A
(u)
(u) ijk

We summarize the result of this section in the following theorem.

Theorem 4.1. Let q be any positive integer. Let a be any function from P(S8 ) satisfying the
symmetry constraint (C1). For all (i, j, k) ∈ S 8 , let aijk be functions from P(S ijk ) satisfying the
N
⊗a(ijk)N
Tijk
admits
constraints (D1), (D2) and (D3). Then for any ǫ > 0, the trilinear form
(i,j,k)∈S 8

a restriction which is a direct sum of r2 tensors, all isomorphic to


O
O

Vuvw (ijk)⊗auvw (ijk)a(uvw)N  .
(u,v,w)∈S 8

5

(i,j,k)∈S uvw

Third extraction

From the second extraction of Section 4 appeared tensors of the form Vuvw (ijk), which are
formed from tensors Tijk , (i, j, k) ∈ S4 . We will see in Section 6 that all the tensors Tijk with
(i, j, k) ∈ S4 \ S 4 , where S 4 = {(2, 1, 1), (1, 1, 2), (2, 1, 2)}, correspond to matrix products. The last
extraction, that we now realize, deals with the tensors T211 , T121 and T112 .
22

5.1

Properties of the tensors T211 , T121 and T112

We first focus on the tensor T211 and analyze it as done in Ref. [17]. This tensor can be written as
T211 = t011 + t101 + t110 + t200 , where
t011 =
t101 =
t110 =
t200 =

q
X

x0,q+1 yi,0 zi,0 ,

i=1
q
X

i,k=1
q
X

xi,k y0,k zi,0 ,
xi,k yi,0 z0,k ,

i,k=1
q
X

xq+1,0 y0,k z0,k .

k=1

For (I, J, K) = (Il , Jl , Kl )l∈[[1,n]] ∈ S2n , define tIJK =
We now describe an extraction from
⊗2m
=
T211

N

tI l J l K l .

l∈[[1,l]]

X

tIJK ,

(I,J,K)∈S22m

where m is an integer. Note that for (i, j, k), (i′ , j ′ , k′ ) ∈ S2 , if i 6= i′ the x variables in tijk and ti′ j ′ k′
are distinct, if j 6= j ′ the y variables in tijk and ti′ j ′ k′ are distinct, and if k 6= k′ the z variables in
tijk and ti′ j ′ k′ are distinct. Thus, for (I, J, K), (I ′ , J ′ , K ′ ) ∈ S22m , if I 6= I ′ the x variables in tIJK
and tI ′ J ′ K ′ are distinct, if J 6= J ′ the y variables in tIJK and tI ′ J ′ K ′ are distinct, and if K 6= K ′
the z variables in tIJK and tI ′ J ′ K ′ are distinct. Fix b ∈ ]0, 1[ ∩ Q and assume (m will later go to
infinity) that bm ∈ N. Define a211 (011) = a211 (200) = (1 − b)/2, a211 (101) = a211 (110) = b/2, with
projections A211 , B211 , C211 . Note that by definition of a211 , B211 = C211 . We set to 0 all the x
variables but the ones which appear in a tIJK with I of type A211 , and all the y (resp. z) except
the ones which appear in a tIJK with J (resp. K) of type B211 .
It was shown in Subsection 6.1 of [17] that this leads to a sum of forms tIJK isomorphic to
⊗(1−b)m

t011

⊗(1−b)m

⊗bm
⊗ t⊗bm
101 ⊗ t110 ⊗ t200

∼
= hq 2bm , q 2bm , q 2(1−b)m i

and that, adopting the same notations as in the previous extractions of Sections 3 and 4, we have



2m !
2m
1
2
T211,X =
=Θ
·
(1 − b)m, (1 − b)m, 2mb
m (2b)b (1 − b)1−b




2mb
1 h i2m
∗
N211,X = N211,X
=
= Θ √ · 2b
m
mb
 


2m
1
2m
T211,Y = T211,Z =
= Θ √ · [2]
m
m

2m !



1
m
m
1
∗
∗
.
·
N211,Y = N211,Z = N211,Y = N211,Z =
=Θ
m bb (1 − b)1−b
m(1 − b) m(1 − b)
The forms T112 and T121 can be analyzed in the same way as T211 by permuting the roles of the
x variables, the y variables and the z variables.
23

5.2

Joint extraction of the tensors T211 , T121 and T112

From the extraction of Sections 3 and 4, we obtain tensors isomorphic to
⊗α112 N
⊗α121 N
⊗α211 N
T112
⊗ T121
⊗ T211

where for (i, j, k) ∈ {(2, 1, 1), (1, 1, 2), (2, 1, 2)},
X
αijk =
(u,v,w)∈S 8

,∃(i′ ,j ′ ,k ′ )∈S

4

a(uvw)auvw (ijk) +

,((i,j,k),(i′ ,j ′ ,k ′ ))∈S

X

uvw

a(uvw)auvw (i′ j ′ k′ ).

(u,v,w)∈S 8 ,∃(i′ ,j ′ ,k ′ )∈S4 ,((i′ ,j ′ ,k ′ ),(i,j,k))∈Suvw

Note that the symmetry conditions (C1) and (D1) imply that α112 = α121 .
Using the parameters from Subsection 5.1, we realize a joint extraction on the tensor
⊗α112 N
⊗α112 N
⊗α211 N
T112
⊗ T121
⊗ T211
, just as in Subsection 4.3. We actually use a constant b ∈ ]0, 1[
for defining the types used for T112 and T121 and another constant b̃ for the type used for T211 . We
impose the constraint
 α211
α
2b̃
2b 112
α211
≥
(E3)
α
(bb (1 − b)1−b ) 112
b̃b̃ (1 − b̃)1−b̃
which ensures that N211,Y N112,Y N121,Y = N211,Z N112,Z N121,Z = O (N211,X N112,X N121,X ). We then
get a direct sum of


T211,X T112,X T121,X
Ω
(N211,X N112,X N121,X )ǫ
trilinear forms, all isomorphic to

(α112 +α211 b̃)N (α112 +α211 b̃)N (2α112 b+α211 (1−b̃))N
Td
,q
,q
i.
211 = hq

Replacing the T by their values, and using the bounds N211,X ≤ 4α211 N , N112,X = N121,X ≤ 4α112 N ,
we get that the number of terms in the direct sum is


 

r3 = Ω 

1

4(α211 +2α112 )N ǫ N 2

22α112 +α211

N



α211   .
(2b̃)b̃ (1 − b̃)1−b̃

We summarize the result of this last extraction in the following theorem.

Theorem 5.1. For any positive α211 , α112 , for any b, b̃ ∈ ]0, 1[ ∩ Q satisfying (E3) and for any
ǫ > 0, the trilinear form
⊗α112 N
⊗α112 N
⊗α211 N
T112
⊗ T121
⊗ T211
admits a restriction which is a direct sum of r3 trilinear forms, all isomorphic to Td
211 .

24

6

The full extraction

Let us first extend the definition of the values αijk , which were introduced only for (i, j, k) ∈ S 4 in
Section 5.2, to all triples in S4 : for any (i, j, k) ∈ S4 define
X
a(uvw)auvw (ijk)N +
αijk =
(u,v,w)∈S 8 ,∃(i′ ,j ′ ,k ′ )∈S4 ,((i,j,k),(i′ ,j ′ ,k ′ ))∈Suvw

X

a(uvw)auvw (i′ j ′ k′ )N.

(u,v,w)∈S 8 ,∃(i′ ,j ′ ,k ′ )∈S4 ,((i′ ,j ′ ,k ′ ),(i,j,k))∈Suvw

From the three consecutive extractions described in Sections 3–5, we get a direct sum of r1 r2 r3
trilinear forms, each of them being isomorphic to

 

O
O
α N
a(ijk)N 

Tijk
Tijkijk  ⊗ Td
⊗
(∗)
211 .
(i,j,k)∈S8 \S 8

(i,j,k)∈S4 \S 4

For any (i, j, k) ∈ S4 \ S 4 , the trilinear form Tijk represent a matrix product (cf. [10]):
T004 ∼
= T040
T013
T103

∼
= T400
∼
= T031
∼
= T301

∼
= h1, 1, 1i
∼
= h1, 1, 2qi
∼
= h2q, 1, 1i

T130 ∼
= T310 ∼
= h1, 2q, 1i
T022 ∼
= h1, 1, q 2 + 2i

T202 ∼
= hq 2 + 2, 1, 1i
∼ h1, q 2 + 2, 1i.
T220 =

It can be seen from the definitions of the trilinear form Tijk , (i, j, k) ∈ S8 \ S 8 that they also
represent a matrix product. We have:
T008 ∼
= T080 ∼
= T800
T017 ∼
= T071
T107 ∼
= T170

T701 ∼
= T710
T026 ∼
= T062

∼
= h1, 1, 1i
∼
= h1, 1, 4qi
∼
= h4q, 1, 1i

∼
= h1, 4q, 1i
∼
= h1, 1, 6q 2 + 4i
∼
= h6q 2 + 4, 1, 1i

T206 ∼
= T260
T602 ∼
= T620 ∼
= h1, 6q 2 + 4, 1i
∼ T053 =
∼ h1, 1, 4q 3 + 12qi
T035 =

T305 ∼
= T350
T503 ∼
= T530

T044

∼
= h4q 3 + 12q, 1, 1i
∼
= h1, 4q 3 + 12q, 1i
∼
= h1, 1, q 4 + 12q 2 + 6i

T404 ∼
= hq 4 + 12q 2 + 6, 1, 1i
T440 ∼
= h1, q 4 + 12q 2 + 6, 1i.
25

As we have seen in Section 5, Td
211 is also a matrix product. Hence, the r1 r2 r3 isomorphic trilinear
forms that we have extracted all represent the same matrix product. By the symmetry constraints
(C1) and (D1), we get that this matrix product is of the form hQN , QN , RN i. The expressions of Q
and R are obtained by replacing in (∗) the Tijk and Td
211 by the matrix products they correspond to.
We refrain from giving here the complete expressions for R and Q since the formulas are extremely
long (they can be found in the files of the programs used for the numerical analysis [36]). We have
shown:
r1 r2 r3 · hQN , QN , RN i ≤ F ⊗N .

As we alreadysaw in Subsection 2.2, R (F ) ≤ (q + 2)4 and thus by submultiplicativity of the border
rank R F ⊗N ≤ (q + 2)4N . By Schönhage’s asymptotic sum inequality (Theorem 2.1), we have:
log R

r1 r2 r3 QN ω( log Q ) ≤ (q + 2)4N ,

and taking the N -th root, we get:
1

(r1 r2 r3 ) N Q

log R
ω( log
)
Q

≤ (q + 2)4 .

Let

1

1

M = lim lim (r1 r2 r3 ) N =
ǫ→0 N →∞

8
Q

A(i)A(i)

(i,j,k)∈S 8

i=0

We have

Y



MQ



 i
Q

u=0

log R
ω( log
)
Q

1
Aijk (u)Aijk

a(ijk)





(u)

22α112 +α211
α211 .

(2b̃)b̃ (1 − b̃)1−b̃

≤ (q + 2)4 .

We summarize the result of the whole process in the following theorem.
Theorem 6.1. Let q be any positive integer. Let a be any function from P(S8 ) satisfying the
constraints (C1), (C2) and (C3). For all (u, v, w) ∈ S 8 , let auvw be functions from P(S uvw )
satisfying the constraints (D1), (D2) and (D3). Finally, let b and b̃ be any two values from ]0, 1[ ∩ Q
satisfying the constraint (E3). Then the following inequality holds:
MQ

log R
ω( log
)
Q

≤ (q + 2)4 .

Theorem 6.1 enables us to obtain our new upper bounds on ω(k): for any k, if we find values q,
log R
a, auvw for each (u, v, w) ∈ S 8 , b and b̃ satisfying the constraints in Theorem 6.1 such that log
Q =k
and MQν ≥ (q + 2)4 for some ν , then we get, since MQω(k) ≤ (q + 2)4 , that ω(k) ≤ ν. The
bounds given in Table 3 and Theorem 1.1 are obtained by finding the optimal values for q, a, auvw
for each (u, v, w) ∈ S 8 , b and b̃ by numerical analysis using Maple. The source code of the Maple
programs used for the numerical analysis, which include the complete formulas for the terms R and
Q, is available at [36].

Acknowledgements.
This work is partially supported by ERC QCC, ANR grant RDAM, JSPS Grant-in-Aid for Young
Scientists (A) No. 16H05853 and JSPS Grant-in-Aids for Scientific Research (A) No. 15H01677 and
16H01705.
26

References
[1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. In Proceedings of the 56th Symposium on Foundations
of Computer Science, pages 98–117, 2015.
[2] Noga Alon and Raphael Yuster. Fast algorithms for maximum subset matching and all-pairs
shortest paths in graphs with a (not so) small vertex cover. In Proceedings of the 15th Annual
European Symposium on Algorithms, pages 175–186, 2007.
[3] Andris Ambainis, Yuval Filmus, and François Le Gall. Fast matrix multiplication: Limitations
of the Coppersmith-Winograd method. In Proceedings of the 47th Symposium on Theory of
Computing, pages 585–593, 2015.
[4] Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In Proceedings of the 12th International Conference on Database Theory, pages 121–126,
2009.
[5] Markus Bläser. Fast matrix multiplication. Theory of Computing, Graduate Surveys, 5:1–60,
2013.
[6] Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams. Truly
sub-cubic algorithms for language edit distance and RNA-folding via fast bounded-difference
min-plus product. In Proceedings of the 57th Symposium on Foundations of Computer Science,
pages 375–384, 2016.
[7] Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic complexity
theory. Springer, 1997.
[8] Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM Journal on Computing,
11(3):467–471, 1982.
[9] Don Coppersmith.
13(1):42–49, 1997.

Rectangular matrix multiplication revisited.

Journal of Complexity,

[10] Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions.
Journal of Symbolic Computation, 9(3):251–280, 1990.
[11] Alexander Munro Davie and Andrew James Stothers. Improved bound for complexity of matrix
multiplication. Proceedings of the Royal Society of Edinburgh, 143A:351–370, 2013.
[12] Camil Demetrescu and Giuseppe F. Italiano. Fully dynamic transitive closure: Breaking
through the o(n2 ) barrier. In Proceedings of the 41st Symposium on Foundations of Computer
Science, pages 381–389, 2000.
[13] Xiaohan Huang and Victor Y. Pan. Fast rectangular matrix multiplication and applications.
Journal of Complexity, 14(2):257–299, 1998.
[14] Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin. Counting colors in boxes. In
Proceedings of the 18th Symposium on Discrete Algorithms, pages 785–794, 2007.
[15] Haim Kaplan, Micha Sharir, and Elad Verbin. Colored intersection searching via sparse rectangular matrix multiplication. In Proceedings of the 22nd Symposium on Computational Geometry, pages 52–60, 2006.
27

[16] ShanXue Ke, BenSheng Zeng, WenBao Han, and Victor Y. Pan. Fast rectangular matrix
multiplication and some applications. Science in China Series A: Mathematics, 51(3):389–
406, 2008.
[17] François Le Gall. Faster algorithms for rectangular matrix multiplication. In Proceedings of
the 53rd Symposium on Foundations of Computer Science, pages 514–523, 2012.
[18] François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th
International Symposium on Symbolic and Algebraic Computation, pages 296–303, 2014.
[19] Grazia Lotti and Francesco Romani. On the asymptotic complexity of rectangular matrix
multiplication. Theoretical Computer Science, 23:171–185, 1983.
[20] Mihai Patrascu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings
of the 21st Symposium on Discrete Algorithms, pages 1065–1075, 2010.
[21] Liam Roditty and Asaf Shapira. All-pairs shortest paths with a sublinear additive error. ACM
Transactions on Algorithms, 7(4):45, 2011.
[22] Piotr Sankowski and Marcin Mucha. Fast dynamic transitive closure with lookahead. Algorithmica, 56(2):180–197, 2010.
[23] Arnold Schönhage. Partial and total matrix multiplication. SIAM Journal on Computing,
10(3):434–455, 1981.
[24] Andrew Stothers. On the Complexity of Matrix Multiplication. PhD thesis, University of
Edinburgh, 2010.
[25] Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354–356,
1969.
[26] Volker Strassen. The asymptotic spectrum of tensors and the exponent of matrix multiplication. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science,
pages 49–54, 1986.
[27] Volker Strassen. Relative bilinear complexity and matrix multiplication. Journal für die reine
und angewandte Mathematik, 375-376:406–443, 1987.
[28] Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In
Proceedings of the 44th Symposium on Theory of Computing, pages 887–898, 2012.
[29] Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu.
Finding four-node subgraphs in triangle time. In Proceedings of the 26th Symposium on Discrete Algorithms, pages 1671–1680, 2015.
[30] Ryan Williams. Non-uniform ACC circuit lower bounds. In Proceedings of the 26th Conference
on Computational Complexity, pages 115–125, 2011.
[31] Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted
APSP. In Proceedings of 20th Symposium on Discrete Algorithms, pages 950–957, 2009.
[32] Raphael Yuster and Uri Zwick. Detecting short directed cycles using rectangular matrix
multiplication and dynamic programming. In Proceedings of the 15th Symposium on Discrete
Algorithms, pages 254–260, 2004.
28

[33] Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Transactions on
Algorithms, 1(1):2–13, 2005.
[34] Uri Zwick. All pairs lightest shortest paths. In Proceedings of the 31st Symposium on Theory
of Computing, pages 61–69, 1999.
[35] Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication.
Journal of the ACM, 49(3):289–317, 2002.
[36] http://www.francoislegall.com/RMM.zip.

29

