What is the largest tensor rank of $n \times n \times n$ tensor?

Question

The tensor rank of a three dimensional array $M[i,j,k], i,j,k\in [1,\ldots,n]$ is the minimal number of vectors $x_i,y_i,z_i$, such that $M=\sum_{i=1}^d x_i\otimes y_i\otimes z_i$. From dimension argument it easily follows that there exists a tensor of tensor rank at least $\frac{1}{3}n^2$. One can also easily show that every tensor is of tensor rank at most $n^2$.

So I know that the maximal tensor rank is between $\frac{1}{3}n^2$ and $n^2$. Does any one know what is the maximal tensor rank?

p.s. As far as I understand maximal border rank is $\frac{1}{3}n^2$.

Answer 1

The lower bound can be improved slightly to $n^3/(3n-2)$ by noting that in $x\otimes y\otimes z$ one can assume $|y|=|z|=1$. See also Chapter 20, "Typical Tensorial Rank", in the book Algebraic Complexity Theory, by Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi.

An upper bound of $n^2−n−1$ is shown in http://arxiv.org/abs/0909.4262v4 so that is probably the best known upper bound.

Answer 2

For tensors in $\mathbb{R}^3 \otimes \mathbb{R}^3 \otimes \mathbb{R}^3$ or in $\mathbb{C}^3 \otimes \mathbb{C}^3 \otimes \mathbb{C}^3$, the maximum rank is $5$. See Bremner, Hu, On Kruskal's theorem that every $3 \times 3 \times 3$ array has rank at most $5$, 2013 (MR3089693). (Their proof in the complex case also works for any algebraically closed field of characteristic not equal to $2$. Interestingly, over the field with two elements there are $3 \times 3 \times 3$ tensors of rank $6$.)

For tensors in $\mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$ or in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$, for $n \geq 4$, the maximum rank is at most $\binom{n+1}{2}$. See Atkinson, Lloyd Bounds on the ranks of some 3-tensors, 1980 (MR0570374). (They state the result only over $\mathbb{C}$, but say that "however, many of our techniques remain valid for arbitrary fields of characteristic zero". I have not tried to figure out if their proof works over $\mathbb{R}$.) Alternatively, see Theorem 1 and Theorem 3 of Sumi, Miyazaki, Sakata, About the maximal rank of $3$-tensors over the real and the complex number field, 2010 (MR2652318). (Theorem 4 of this paper also gives the upper bound $5$ in the $n=3$ case.)

I think it is still open what the actual maximal rank is for $n \geq 4$, but this narrows down the range to be between $n^3/(3n-2)$ and $\binom{n+1}{2}$.