A note on the gap between rank and border rank
Jeroen Zuiddam

arXiv:1504.05597v2 [] 23 Mar 2017

Centrum Wiskunde & Informatica, Science Park 123, Amsterdam

Abstract
We study the tensor rank of the tensor corresponding to the algebra of n-variate
complex polynomials modulo the dth power of each variable. As a result we
find a sequence of tensors with a large gap between rank and border rank, and
thus a counterexample to a conjecture of Rhodes. At the same time we obtain a
new lower bound on the tensor rank of tensor powers of the generalised W-state
tensor. In addition, we exactly determine the tensor rank of the tensor cube of
the three-party W-state tensor, thus answering a question of Chen et al.
Keywords: tensor rank, border rank, algebraic complexity theory, quantum
information theory, W-state.
2010 MSC: 68Q17, 15A69, 16Z05

1. Introduction
Let V1 , . . . , Vk be finite-dimensional complex vector spaces and consider the
vector space V := V1 ⊗· · ·⊗Vk of k-tensors. A tensor of the form v1 ⊗v2 ⊗· · ·⊗vk
in V is called simple. The tensor rank of a tensor t ∈ V is the smallest number r
such that t can be written as a sum of r simple tensors. The border rank R(t)
of t is the smallest number r such that t is the limit of a sequence of tensors
in V of rank at most r, in the Euclidean topology. Clearly, R(t) ≤ R(t) and
already in the small space C2 ⊗ C2 ⊗ C2 there exist tensors with R(t) < R(t).
Tensor rank plays a fundamental role in various problems in modern applied
mathematics. One famous example is the problem of deciding the complexity of
matrix multiplication [1]. We refer to [2] for more examples of applications of
tensor rank. While the tensor rank of a 2-tensor (matrix rank) can be efficiently
computed, computing the tensor rank of a k-tensor is NP-hard when k ≥ 3
[3, 4, 5]. The border rank notion is important for at least the following two
reasons. Unlike tensor rank, border rank is defined by polynomial equations.
One approach for computing a lower bound for the tensor rank of a tensor is
thus to find the relevant border rank equation and then verify that the tensor
does not satisfy the equation. This strategy was for example used in [6]. On the
other hand, border rank upper bounds can in some situations be turned into

Email address: j.zuiddam@cwi.nl (Jeroen Zuiddam)

1

nontrivial rank upper bounds, especially when one is interested in the asymptotic
behaviour of tensor rank when taking large tensor powers of a fixed tensor. This
idea is crucial in, for example, the laser method of Strassen [7] and all later
improvements of this method, see for example [8].
This paper is motivated by the following basic question about tensor rank
and border rank.
Problem 1. What is the maximal ratio R(t)/ R(t) for a k-tensor t in (Cn )⊗k ?
Our main result is the following lower bound. Let e0 , e1 be the standard
basis of C2 . Define Wk to be the tensor e1 ⊗ e0 ⊗ · · · ⊗ e0 + e0 ⊗ e1 ⊗ · · · ⊗ e0 +
· · · + e0 ⊗ · · · ⊗ e0 ⊗ e1 living in (C2 )⊗k . This tensor is known as the generalised
W-state tensor in quantum information theory.
Theorem 2. Let k ≥ 3. There exists an explicit sequence of k-tensors tn in
n
(C2 )⊗k such that
R(tn )
≥ k − o(1),
R(tn )
n

when n goes to infinity. Namely, let tn = Wk⊗n ∈ (C2 )⊗k, the n-fold tensor
Kronecker product of Wk . Then R(tn ) = 2n and R(tn ) ≥ k · 2n − o(2n ), when n
goes to infinity.
We obtain Theorem 2 by applying a tensor rank lower bound of Bläser to
the tensor corresponding to the algebra Ad,n := C[x1 , . . . , xn ]/(xd1 , . . . , xdn ) of
n-variate complex polynomials modulo the dth power of each variable. This
in turn leads to the aforementioned lower bound on the tensor rank of tensor
powers of the generalised W-state tensor Wk . Our bound improves the lower
bound R(Wk⊗n ) ≥ (k − 1) · 2n − k + 2 of Chen et al. [9].
We note that it is a major open problem to find explicit tensors t ∈ (Cn )⊗3
with R(t) ≥ (3 + ε)n for any ε > 0 [10]. There are explicit tensors t ∈ (Cn )⊗3
known with R(t) ≥ (3 − o(1))n when n goes to infinity, see [11, Theorem 2].
Related work. De Silva and Lim show that for a 3-tensor t the difference between
tensor rank and border rank R(t) − R(t) can be arbitrarily large [12]. However,
their result implies a lower bound of only 3/2 on the maximal ratio R(t)/ R(t)
for t a 3-tensor.
Allman et al. give explicit tensors Kn in Cn ⊗ Cn ⊗ Cn of border rank n
and rank 2n − 1 [13]; a rank to border rank ratio that converges to 2. They
provide references to other tensors with similar rank and border rank behaviour.
We note that the tensor Kn is essentially the tensor of the algebra C[x]/(xn ).
It was conjectured by Rhodes that the rank of a tensor in Cn ⊗ Cn ⊗ Cn of
border rank n is at most 2n − 1 [14, Conjecture 0]. Theorem 2 shows that this
conjecture is false.
Independently of the author and with different techniques, Landsberg and
Michałek have recently constructed a sequence of 3-tensors with a ratio of rank
to border rank converging to 5/2, thus also disproving the above conjecture [15].

2

As is also mentioned in [15], we note that for any k ≥ 3, the tensor Wk ∈
(C2 )⊗k has border rank 2 and rank k, thus giving a rank to border rank ratio
of k/2, see the proof of Theorem 2.
As pointed out by an anonymous reviewer, a lower bound on the maximal ratio between rank and border rank for 3-tensors (k = 3) similar to
the one in Theorem 2 in this paper, can also be obtained as follows. Let
Id (x1 , . . . , xn ) ⊆ C[x1 , . . . , xn ] be the ideal generated by all monomials of degree d. Bläser [11] proves that the tensor corresponding to the algebra Pn,d defined
as C[x1 , . . . , xn ]/Id+1 (x1 , . . . , xn ) has tensor rank R(Pn,d ) ≥ (3−o(1)) dim(Pn,d ).
Moreover, the ideal Id+1 (x1 , . . . , xn ) is a so-called monomial ideal and is therefore
“smoothable”. It turns out (see [16]) that associative unital algebras defined
by smoothable ideals (like Pn,d ) have “minimal border rank” which in this
case means that R(Pn,d ) = dim Pn,d . Combining these observations yields, for
any d > 1, an explicit sequence of 3-tensors tn ∈ (Cdim(Pn,d ) )⊗3 such that
R(tn )/ R(tn ) ≥ 3 − o(1) when n goes to infinity. Note that the algebra Pn,d is
slightly different from the algebra Ad,n that we study here.
Very little is known about general upper bounds on the rank to border rank
ratio. We are only aware of the following bound that can be deduced from a
result of Lehmkuhl and Lickteig [17] and Proposition 15.26 in [1]. For any tensor
t ∈ Cn ⊗ Cn ⊗ Cn we have R(t)/ R(t) ≤ 2 · 9(n−1) R(t) + 1.
Outline. This paper is organised as follows. First we introduce the algebra Ad,n
and for the corresponding tensor study its border rank and tensor rank. Then
we observe that this tensor specialises to powers of the W-state tensor, yielding
the gap between rank and border rank given above. Finally, we compute the
tensor rank of the tensor cube of the three-party W-state tensor.
2. The algebra Ad,n
Many examples of interesting 3-tensors come from algebras. A complex
algebra is a complex vector space V together with a multiplication defined by a
bilinear map φ : V × V → V . An algebra is called associative if φ(φ(u, v), w) =
φ(u, φ(v, w)) for all u, v, w ∈ V . An algebra is called unital if there is an element
e ∈ V such that φ(e, v) = φ(v, e) = v for all v ∈ V . Let e1 , e2 , . . . be a basis
of V and e∗1 , e∗2 , . . . the dual basis. We can naturally view the algebra (V, φ) as a
tensor in V ⊗ V ⊗ V by
X
φ 7→
e∗k (φ(ei , ej )) ei ⊗ ej ⊗ ek ,
i,j,k

called the structure tensor. In this way we can speak about the tensor rank and
border rank of an algebra. There are many results on the tensor rank and border
rank of algebras, in particular of the algebra of n × n matrices, for which we
refer to [1] and [18]. For results on the tensor rank and border rank of general
tensors we refer to [2]. In this section we will study the complex associative
unital algebra
Ad,n := (C[x]/(xd ))⊗n = C[x1 , . . . , xn ]/(xd1 , . . . , xdn ),
3

of n-variate complex polynomials modulo the dth power of each variable.
2.1. Border rank
A tensor t in V1 ⊗ · · · ⊗ Vk is called 1-concise if there does not exist a
proper subspace U1 ⊆ V1 such that t ∈ U1 ⊗ V2 ⊗ · · · ⊗ Vk . Similarly, we define
i-conciseness for i ∈ {2, . . . , k}. A tensor is called concise if it is i-concise for
all i. We can think of a concise tensor as a tensor that “uses” all dimensions
of the local spaces Vi . Tensors of unital algebras are concise. For a concise
tensor t in V1 ⊗ · · · ⊗ Vk the border rank is at least maxi dim Vi [1, Lemma 15.23].
The following proposition is a direct consequence of the well-known fact that
R(C[x]/(xd )) = d, see [1, Example 15.20].
Proposition 3. R(Ad,n ) = dn .
Proof. The algebra Ad,n is unital. Therefore, the corresponding tensor Ad,n ∈
n
n
n
Cd ⊗ Cd ⊗ Cd is concise. This implies that R(Ad,n ) ≥ dn . On the other
hand, border rank is submultiplicative under tensor products, so R(Ad,n ) =
R((C[x]/(xd ))⊗n ) ≤ R(C[x]/(xd ))n = dn .
2.2. Rank lower bound
Let (V, φ) be a complex finite-dimensional associative unital algebra. A
subspace I ⊆ V is called a left-ideal if φ(V, I) = I. A left-ideal I is called
nilpotent if I n = {0} for some positive integer n. The nilradical of V is the sum
of all nilpotent left-ideals in A.
Theorem 4 ([18, Theorem 7.4]). Let A be a finite-dimensional complex associative unital algebra and let N be the nilradical of A. For any integer m ≥ 1,
R(A) ≥ dim(A) − dim(N 2m−1 ) + 2 dim(N m ).
We will apply Theorem 4 to the algebra Ad,n . Let us first look at a small
example.
Example 5. Consider the algebra A := A2,2 = C[x1 , x2 ]/(x21 , x22 ) of dimension 4.
The elements in A are of the form α + βx1 + γx2 + δx1 x2 with α, β, γ, δ ∈ C.
The nilradical N ⊆ A is the subspace spanned by {x1 , x2 , x1 x2 }, and hence has
dimension 3. The square of the nilradical N 2 is spanned by x1 x2 and hence has
dimension 1. Taking m = 1, Theorem 4 gives R(A) ≥ 4 − 3 + 2 · 3 = 7.
We use extended binomial coefficients
to get a handle on the dimension of

powers of the radical of Ad,n . Let nb d be the number of ways to put b balls
into n containers with at most d balls per container. This equals the number of
monomials of degree b in C[x1 , . . . , xn ]/(xd+1
, . . . , xd+1
n ).
1
Lemma 6. For any 0 ≤ q < 1/2,
bqndc 

X
b=0


n
b d

(d + 1)n

→ 0

4

as

n → ∞.

Proof. Fix n, d. The limit
 
1
n
ln
,
n→∞ n
ρn d

hd (ρ) := lim

0 ≤ ρ ≤ d,

exists, the function hd is strictly concave, unimodal and reaches its maximum
ln(m + 1) at the point ρ = d/2 [19]. Let 0 ≤ q < 1/2 and let ρ := qd. For all
ρ < d/2, hd (ρ) < ln(d + 1), so there is an ε > 0 such that hd (ρ) + ε < ln(d + 1).
For n big enough,
 

n
≤ exp (hd (ρ) + ε)n
ρn d
and thus
Pbqndc
b=0

(d +

n
b d
1)n




≤ (qnd + 1) exp (hd (ρ) + ε − ln(d + 1))n ,

which goes to zero as n goes to infinity.
We note that the case d = 1 can also easily be obtained from the well-known
inequality
bqnc  
X n
≤ 2H(q)n ,
b
b=0

where H(q) = −q log2 q − (1 − q) log2 (1 − q) is the binary entropy of q, see for
example [20, Lemma 16.19].
Proposition 7. Let n ≥ 1, d ≥ 2 be integers. Then
" 2m−2  
#
m−1
X n
X n
n
R(Ad,n ) ≥ 2 d + max
− 2
≥ 3dn − o(dn ).
m≥1
b d−1
b d−1
b=0

b=0

Proof. The nilradical N of Ad,n is the ideal generated by x1 , . . . , xn , that is, N
is the subspace of Ad,n of elements with zero constant term. The mth power N m
is the subspace spanned
by monomials
of degree at least m, hence the dimension

Pm−1
of N m equals dn − b=0 nb d−1 . Theorem 4 then gives, for any m ≥ 1,


2m−2
m−1
X n 
X n 
n
n
R(Ad,n ) ≥ d − d −
+2 d −
b d−1
b d−1
b=0
b=0




2m−2
m−1
X n
X n
−2
.
= 2dn +
b d−1
b d−1
n

b=0

b=0

If 2m − 1 ≤ n(d − 1), then
2m−2
X 
b=0

n
b



n(d−1)
n

=d −
d−1

n(d−1)−(2m−1)  
X n
X
n
n
= d −
,
b d−1
b d−1

b=2m−1

b=0

5

so
R(Ad,n ) ≥ 3 · dn −

n(d−1)−(2m−1) 

X
b=0

n
b


−2
d−1

m−1
X

n
b

b=0


.
d−1

One checks that for any n large enough there exists an m ≥ 1 such that
2m − 1 ≤ n(d − 1), n(d − 1) − (2m − 1) < 12 n(d − 1) and m − 1 < 12 n(d − 1).
Therefore, with Lemma 6, we obtain the inequality R(Ad,n ) ≥ 3 · dn − o(dn ).
For computations, the following lemma is useful.
Lemma 8. For integers b ≥ 1, n ≥ 1, d ≥ 2,
 
 

min(n,bb/dc)
X
n
n b+n−1−i·d
=
(−1)i
.
b d−1
i
n−1
i=0
Proof. Let X := {ways to put b balls into n containers} and for j ∈ [n] let
Aj := {ways to put b balls in n containers such that container j has at least
d balls} ⊂ X. By the inclusion-exclusion principle [21, Proposition 1.13], the
number of elements of X which lie in none of the subsets Aj is


X
\
X
|I|
|I| b + n − 1 − |I| · d
(−1)
Aj =
(−1)
.
n−1
j∈I

I⊆{1,...,n}

I⊆{1,...,n}


n
Now use that there are |I|
subsets of size |I| in {1, . . . , n}. The statement
about the special case d = 2 follows immediately from the definition.
In the table below we list some values of the lower bound of Proposition 7.
d

2

3

4

5

6

n
1
2
3
4
5
6

3
7
15
33
68
141

5
18
57
182
576
1773

7
33
142
601
2507
10356

9
53
285
1509
7824
40329

11
78
501
3166
19782
121971

Table 1: Lower bounds for R(Ad,n ) from Proposition 7. The bold numbers are known to be
sharp, see Theorem 15.

2.3. Rank upper bound
It is well-known that upper bounds on border rank imply upper bounds on
rank. Proposition 3 implies the following upper bound on R(Ad,n ). We will not
use the upper bound later, but it provides some context for the lower bound of
Proposition 7.

6

Proposition 9. R(Ad,n ) ≤ (nd + 1)dn .
Proof. The statement follows from the proof of Theorem 5 in [22], using that the
error degree in the degeneration of the dth unit tensor to Ad,n is d [1, Example
15.20].
3. Generalised W-state tensor
In quantum information theory, the generalised W-state tensor Wk is the
tensor in (C2 )⊗k defined by
Wk := e1 ⊗ e0 ⊗ · · · ⊗ e0 + e0 ⊗ e1 ⊗ · · · ⊗ e0 + · · · + e0 ⊗ · · · ⊗ e0 ⊗ e1 .
It is not hard to check that, in a particular basis, the tensor of the algebra
A2,1 = C[x]/(x2 ) equals W3 . Therefore, R(A2,n ) = R(W3⊗n ) and R(A2,n ) =
R(W3⊗n ). By the following proposition, lower bounds for R(W3⊗n ) give lower
bounds for R(Wk⊗n ).
Proposition 10 ([9]). R(Wk⊗n ) ≥ R(W3⊗n ) + (k − 3)(2n − 1).
Theorem 11.
R(Wk⊗n )

n

≥ (k − 1)2 + max
m≥1

2m−2
X 
b=0


m−1
X n
n
− (k − 3) ≥ k · 2n − o(2n ).
−2
b
b
b=0

Proof. Combine Proposition 10 with Proposition 7 for A2,n .
Chen et al. give the lower bound R(Wk⊗n ) ≥ (k − 1)2n − k + 2, which they
obtain by combining the lower bound R(A2,n ) ≥ 2n+1 − 1 with Proposition 10 [9].
Theorem 11 improves the lower bound of Chen et al. The best upper bound so
far is R(Wk⊗n ) ≤ (n(k − 1) + 1)2n [22].
Below we list some values of the lower bound of Theorem 11. The first
two columns are, in fact, sharp [9]. In Section 5 we will prove the equality
R(W3⊗3 ) = 16. Therefore, the lower bound of Theorem 11 is not sharp in
general.
n

1

2

3

4

5

6

7

8

9

10

3
4
5
6
7
8
9
10

7
10
13
16
19
22
25
28

15
22
29
36
43
50
57
64

33
48
63
78
93
108
123
138

68
99
130
161
192
223
254
285

141
204
267
330
393
456
519
582

297
424
551
678
805
932
1059
1186

601
856
1111
1366
1621
1876
2131
2386

1230
1741
2252
2763
3274
3785
4296
4807

2544
3567
4590
5613
6636
7659
8682
9705

k
3
4
5
6
7
8
9
10

Table 2: Lower bounds for R(Wk⊗n ) from Theorem 11. The bold numbers are known to be
sharp [9].

7

4. Gap between rank and border rank
Our main result Theorem 2 follows easily from Theorem 11.
Proof of Theorem 2. By Proposition 3, R(Wk⊗n ) = 2n . By Theorem 11,
therefore,
R(Wk⊗n )
o(2n )
,
≥
k
−
2n
R(Wk⊗n )
when n goes to infinity.
5. Tensor cube of the W-state tensor
It is known that the tensor rank of W := W3 equals 3 and the tensor rank of
the tensor square W ⊗2 equals 7, see [23, Lemma 3]. For the tensor cube W ⊗3
the tensor rank was known to be either 15 or 16 [9, Theorem 4]. We will prove
the following.
Theorem 12. The tensor rank of W ⊗3 equals 16.
In the following, algebra means complex finite-dimensional associative algebra.
Let (V, φ) be an algebra. A subspace I ⊂ V is called a two-sided ideal if
φ(I, V ) = φ(V, I) = I. A two-sided ideal I is called maximal if for all two-sided
ideals J with I ⊆ J ⊆ V we have J = I or J = V . Similarly for left-ideals.
Theorem 13 (Alder-Strassen bound [1, Theorem 17.14]). Let A be an algebra
with t maximal two-sided ideals. Then R(A) ≥ 2 dim A − t.
Definition 14. Let A be an algebra with t maximal two-sided ideals. We say
A has minimal rank if R(A) = 2 dim A − t.
There is a structural description of the algebras of minimal rank [24]. We will
only need the following special case. A simply generated algebra is an algebra of
the form C[x]/(f ) for some nonconstant polynomial f ∈ C[x]. A generalised null
algebra is an algebra A such that there exist nilpotent elements w1 , . . . , ws ∈ A
with wi wj = 0 if i 6= j and A = C[w1 , . . . , ws ]. A local algebra is an algebra
with a unique maximal left-ideal. The radical rad A of A is the intersection of
all maximal left-ideals of A. The radical is a two-sided nilpotent ideal (see for
example [25]).
Theorem 15 ([1, Theorem 17.38]). A commutative local algebra is of minimal
rank if and only if it is a simply generated algebra or a generalised null algebra.
Lemma 16 (Nakayama’s lemma). Let A be an algebra such that A/ rad A ∼
= C.
Then A can be generated as an algebra by p := dim rad A/(rad A)2 elements
in rad A, that is, there are w1 , . . . , wp ∈ rad A such that A = C{w1 , . . . , wp }.
This p is minimal.
We repeat a proof found in [26].

8

Proof. Let N := rad A. Let w1 , . . . , wp ∈ N such that w1 + N 2 , . . . , wp + N 2 is
a C-basis for N/N 2 . One can show by induction that for any r ≥ 1,
{wi1 · · · wir + N r+1 | 1 ≤ i1 , . . . , ir ≤ p}
generates N r /N r+1 as a vector space over C. Using that A/N ∼
= C (so A = C⊕N )
and that N is nilpotent, we get
A = C{w1 , . . . , wp }.
Suppose p is not minimal. Then there is a q < p and a surjective morphism
of algebras
φ : C{X1 , . . . , Xq }  A.
Without loss of generality, we may assume that φ(Xi ) is in N , since otherwise
we can use the decomposition A = C ⊕ N to map φ(Xi ) to N . The set
{φ(Xi ) + N 2 | 1 ≤ i ≤ q}
is too small to generate N/N 2 , and φ maps monomials of degree ≥ 2 in
C{X1 , . . . , Xq } to N 2 . Therefore, φ is not surjective.
Proof of Theorem 12. The W-state tensor is the structure tensor of the algebra W := C[x]/(x2 ). Consider the algebra
A := W ⊗3 = C[x, y, z]/(x2 , y 2 , z 2 ).
It is not hard to see that A is a local algebra with maximal ideal (x, y, z). Let N
be the radical rad A = (x, y, z). By the Alder-Strassen bound (Theorem 13) we
have
R(A) ≥ 2 dim A − 1 = 15.
We will show that A is not of minimal rank. The following type of argument
has been used before by Büchi to compute ranks of certain local algebras of
dimension at most 5 [26]. Suppose A has minimal rank. By Nakayama’s lemma
(Lemma 16), the algebra A can be generated by dim rad A/(rad A)2 = 3 elements
and no fewer. Therefore, by Theorem 15 our algebra A is a generalised null
algebra. Hence there are elements x1 , x2 , x3 ∈ N with x1 x2 = 0, x2 x3 = 0,
and x1 x3 = 0 such that (x1 + N 2 , x2 + N 2 , x3 + N 2 ) is a basis of N/N 2 . On the
other hand, (x + N 2 , y + N 2 , z + N 2 ) is a basis of N/N 2 . Therefore, there are
elements Aij ∈ C and pi ∈ N 2 with
x1 = A11 x + A12 y + A13 z + p1 ,
x2 = A21 x + A22 y + A23 z + p2 ,
x3 = A31 x + A32 y + A33 z + p3 ,
and det A 6= 0. We may assume that A11 is nonzero. We have relations
0 = x1 x2 = (A11 A22 + A12 A21 )xy + (A11 A23 + A13 A21 )xz
+ (A12 A23 + A13 A22 )yz + terms in N 3 ,
0 = x1 x3 = (A11 A32 + A12 A31 )xy + (A11 A33 + A13 A31 )xz
+ (A12 A33 + A13 A32 )yz + terms in N 3 .
9

Let
f1 := A11 A22 + A12 A21 ,
g1 := A11 A32 + A12 A31 ,

f2 := A11 A23 + A13 A21 ,
g2 := A11 A33 + A13 A31 ,

f3 := A12 A23 + A13 A22 ,
g3 := A12 A33 + A13 A32 .

Then we can rewrite the relations as 0 = f1 = f2 = f3 = g1 = g2 = g3 .
With the following Sage code we can compute the syzygy module of the ideal
I := (det(A), f1 , f2 , f3 , g1 , g2 , g3 ) C[Aij ].
R = PolynomialRing(QQ, 3, var_array="a")
A = matrix(R, 3, 3, lambda i,j: "a%d%d" % (i,j))
var("a","b","c")
y = A * vector([a,b,c])
I = R.ideal(det(A),
"a00*a11+a01*a10","a00*a12+a02*a10","a01*a12+a02*a11",
"a00*a21+a01*a20","a00*a22+a02*a20","a01*a22+a02*a21")
L = I.syzygy_module()
print L.str()
One of the syzygies is
− A11 det(A) = (A13 A31 − A11 A33 )f1 + (−3A12 A31 − A11 A32 )f2 + 0 · f3
+ 2A11 A23 g1 + 2A12 A21 g2 + 0 · g3 ,
implying det(A) = 0, which is a contradiction.
Acknowledgements. The author is grateful to Matthias Christandl, Markus Bläser
and Florian Speelman for helpful discussions. Part of this work was done while
the author was visiting the Simons Institute for the Theory of Computing, UC
Berkeley and the Workshop on Algebraic Complexity Theory 2015, Saarbrücken.
This work is supported by the Netherlands Organisation for Scientific Research
(NWO), through the research programme 617.023.116, and by the European
Commission, through the SIQS project.
References
[1] P. Bürgisser, M. Clausen, M. A. Shokrollahi, Algebraic complexity theory,
Vol. 315 of Grundlehren der Mathematischen Wissenschaften, SpringerVerlag, Berlin, 1997. doi:10.1007/978-3-662-03338-8.
[2] J. M. Landsberg, Tensors: geometry and applications, Vol. 128 of Graduate
Studies in Mathematics, American Mathematical Society, Providence, RI,
2012.
[3] J. Håstad, Tensor rank is NP-complete, J. Algorithms 11 (4) (1990) 644–654.
doi:10.1016/0196-6774(90)90014-6.

10

[4] C. J. Hillar, L.-H. Lim, Most tensor problems are NP-hard, J. ACM 60 (6)
(2013) Art. 45, 39. doi:10.1145/2512329.
[5] Y. Shitov, How hard is the tensor rank? (2016). arXiv:1611.01559.
[6] J. D. Hauenstein, C. Ikenmeyer, J. M. Landsberg, Equations for lower
bounds on border rank, Exp. Math. 22 (4) (2013) 372–383. doi:10.1080/
10586458.2013.825892.
[7] V. Strassen, Relative bilinear complexity and matrix multiplication, J. Reine
Angew. Math. 375/376 (1987) 406–443. doi:10.1515/crll.1987.375-376.
406.
[8] F. Le Gall, Powers of tensors and fast matrix multiplication, in: ISSAC
2014—Proceedings of the 39th International Symposium on Symbolic and
Algebraic Computation, ACM, New York, 2014, pp. 296–303. doi:10.1145/
2608628.2608664.
[9] L. Chen, E. Chitambar, R. Duan, Z. Ji, A. Winter, Tensor rank and
stochastic entanglement catalysis for multipartite pure states, Phys. Rev.
Lett. 105 (20) (2010) 200501. doi:10.1103/PhysRevLett.105.200501.
[10] M. Bläser, Explicit tensors, in: Perspectives in computational complexity,
Vol. 26 of Progr. Comput. Sci. Appl. Logic, Birkhäuser/Springer, Cham,
2014, pp. 117–130. doi:10.1007/978-3-319-05446-9_6.
[11] M. Bläser, Improvements of the Alder-Strassen bound: algebras with nonzero
radical, in: Automata, languages and programming, Vol. 2076 of Lecture
Notes in Comput. Sci., Springer, Berlin, 2001, pp. 79–91. doi:10.1007/
3-540-48224-5_7.
[12] V. de Silva, L.-H. Lim, Tensor rank and the ill-posedness of the best lowrank approximation problem, SIAM J. Matrix Anal. Appl. 30 (3) (2008)
1084–1127. doi:10.1137/06066518X.
[13] E. S. Allman, P. D. Jarvis, J. A. Rhodes, J. G. Sumner, Tensor rank,
invariants, inequalities, and applications, SIAM J. Matrix Anal. Appl. 34 (3)
(2013) 1014–1045. doi:10.1137/120899066.
[14] E. Ballico, A. Bernardi, Stratification of the fourth secant variety of Veronese
varieties via the symmetric rank, Adv. Pure Appl. Math. 4 (2) (2013) 215–
250. doi:10.1515/apam-2013-0015.
[15] J. M. Landsberg, M. Michałek, Abelian tensors (2016). doi:10.1016/j.
matpur.2016.11.004.
[16] M. Bläser, V. Lysikov, On degeneration of tensors and algebras, in: 41st International Symposium on Mathematical Foundations of Computer Science
(MFCS 2016), Vol. 58, 2016, pp. 19:1–19:11. doi:10.4230/LIPIcs.MFCS.
2016.19.
11

[17] T. Lehmkuhl, T. Lickteig, On the order of approximation in approximative
triadic decompositions of tensors, Theoret. Comput. Sci. 66 (1) (1989) 1–14.
doi:10.1016/0304-3975(89)90141-2.
[18] M. Bläser, Lower bounds for the bilinear complexity of associative algebras,
Comput. Complexity 9 (2) (2000) 73–112. doi:10.1007/PL00001605.
[19] N.-E. Fahssi, Polynomial triangles revisited (2012). arXiv:1202.0228.
[20] J. Flum, M. Grohe, Parameterized complexity theory, Texts in Theoretical
Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2006.
[21] S. Jukna, Extremal combinatorics: with applications in computer science,
Springer Science & Business Media, 2011.
[22] P. Vrana, M. Christandl, Asymptotic entanglement transformation between
W and GHZ states, J. Math. Phys. 56 (2) (2015) 022204, 12. doi:10.1063/
1.4908106.
[23] N. Yu, E. Chitambar, C. Guo, R. Duan, Tensor rank of the tripartite state
W tensor n, Phys. Rev. A 81 (1) (2010) 014301. doi:10.1103/PhysRevA.
81.014301.
[24] M. Bläser, A complete characterization of the algebras of minimal bilinear
complexity, SIAM J. Comput. 34 (2) (2004/05) 277–298. doi:10.1137/
S0097539703438277.
[25] R. S. Pierce, Associative algebras, Vol. 88 of Graduate Texts in Mathematics,
Springer-Verlag, New York-Berlin, 1982, studies in the History of Modern
Science, 9.
[26] W. Büchi, Über eine klasse von algebren minimalen ranges, Ph.D. thesis,
Universität Zürich (1984).

12

