Discreteness of asymptotic tensor ranks

Discreteness of asymptotic tensor ranks, Discrete Analysis 2025:15, 51 pp.

This paper concerns tensors of order 3, that is, a generalization of matrices to three dimensions, where one considers three-dimensional arrays of elements of a field $\mathbb F$ rather than two-dimensional arrays. It is natural to try to generalize important matrix parameters, in particular rank, to 3-tensors, but there turn out to be many different natural definitions of the rank of a higher-order tensor that all specialize to the familiar notion of rank when the order is 2.

One way to define the rank of an $m\times n$ matrix $A$ over $\mathbb F$ is to define it as the smallest $r$ such that $A$ can be written as $\sum_{i=1}^ru_i\otimes v_i$, where $u_i\in \mathbb F^m$ and $v_i\in\mathbb F^n$, and $u\otimes v$ is notation for the matrix with $xy$th entry equal to $u_xv_y$. To put it another way, non-zero matrices of the form $u\otimes v$ are defined to have rank 1 and the rank of a matrix is the size of the smallest decomposition into rank-1 matrices.

To generalize this approach to tensors, one simply needs to say what a rank-1 tensor should be. An obvious candidate for order-$d$ tensors is tensors of the form $u_1\otimes\dots\otimes u_d$ (which is defined in the obvious way). If we adopt this as our definition of a rank-1 tensor, then the resulting notion of rank is called tensor rank. However, there are other approaches. One that has been prominent recently because of its connection to the solution of the cap-set problem is slice rank, where the rank-1 tensors are defined to be those of the form $u_i\otimes T_i$, where $u_i$ depends only on the $i$th entry and $T_i$ does not depend on the $i$th entry. For instance, when $i=2$ and $d=3$, the $(x,y,z)$ entry of such a tensor would be of the form $u(y)v(x,z)$.

Another notion of tensor rank, called subrank, takes as its starting point the fact that a matrix has rank $k$ if by means of elementary row and column operations it can be turned into a matrix that has $k$ 1s on the diagonal and is zero everywhere else. Given a tensor of order $d$, we can define a “slice operation” to be like a row or column operation except that now we apply the operations to $(d-1)$-dimensional slices. The subrank is the largest $r$ such that we can obtain the $r\times\dots\times r$ “identity tensor” $\sum_{i=1}^re_i\otimes e_i\otimes\dots\otimes e_i$ by performing elementary slice operations or deleting slices.

The Kronecker product $S\boxtimes T$ of two tensors $S$ and $T$ is the tensor one obtains by replacing each entry $s_{i_1\dots i_d}$ of $S$ by $s_{i_1\dots i_d}T$. Thus, if $S$ is an $m_1\times\dots\times m_d$ tensor and $T$ is an $n_1\times\dots\times n_d$ tensor, then $S\boxtimes T$ is an $m_1n_1\times\dots\times m_dn_d$ tensor. We also define the $n$th Kronecker power $T^{\boxtimes n}$ of $T$ to be the Kronecker product of $n$ copies of $T$. And then, given a tensor parameter $F$, such as one of the notions of rank defined above, one can define an “asymptotic” version $\underline F$ of $F$ by
$$\underline F(T)=\lim_{n\to\infty} F(T^{\boxtimes n})^{1/n}$$
(or by the lim inf for parameters $F$ for which the limit does not necessarily exist).

If $d=2$ and $A$ and $B$ are matrices, it is easy to check that the rank of $A\boxtimes B$ is the product of the ranks of $A$ and $B$. Therefore, the rank of $A^{\boxtimes n}$ is the $n$th power of the rank of $A$, so there is no difference between rank and asymptotic rank. However, when $d>2$ it is no longer true that rank is multiplicative (for any of the notions of rank discussed above), so asymptotic rank is a non-trivial new notion, and one that turns out to be important in several contexts.

One of these contexts that particularly stands out is matrix multiplication. The map that takes two $n\times n$ matrices $A$ and $B$ and outputs their product $AB$ is a bilinear map from $\mathbb F^{n\times n}\times\mathbb F^{n\times n}$ to $\mathbb F^{n\times n}$. Each component of this map is a bilinear form on $\mathbb F^{n\times n}$ so can be represented as an $n^2\times n^2$ matrix, and putting together the matrices for the $n^2$ components yields an $n^2\times n^2\times n^2$ tensor $M_n$. If we index each coordinate by an element of $[n]^2$, then the $((p,q),(r,s),(t,u))$ entry of $M_n$ is 1 if $q=r, p=t$ and $s=u$ and is 0 otherwise. It turns out that the tensor rank of $M_n$ gives an upper bound for the number of operations (suitably defined) needed to multiply together two $n\times n$ matrices.

A natural way to obtain such an upper bound is to obtain a non-trivial upper bound for the tensor rank of $M_k$ for some fixed $k$ and then tensor it up. For example, Strassen’s famous algorithm for matrix multiplication proceeds by finding a way of multiplying two $2\times 2$ matrices using seven operations (instead of the trivial eight) and using that to show that two $2^m\times 2^m$ matrices can be multiplied together using $7^m$ operations. Pursuing this thought leads to the conclusion that the matrix multiplication exponent $\omega$, the smallest number such that the number of operations needed to multiply two $n\times n$ matrices is $n^{\omega+o(1)}$, is equal to the logarithm of the asymptotic tensor rank of $M_2$. In particular, if one could show that this asymptotic tensor rank is strictly greater than 2, one would have solved a major open problem by showing that the matrix multiplication exponent is strictly greater than 2.

It turns out that not only is this problem open, but also the much more general problem that asks whether there is any $n\times n\times n$ tensor with asymptotic tensor rank greater than $n$. Given that even this is unknown, it makes good sense to try to improve our understanding of asymptotic tensor rank, which is one of the main aims of this paper.

If $A$ is a matrix, then since the asymptotic rank is equal to the rank, it must be an integer. But this is no longer true of tensors, and indeed there are examples where it is known not to be an integer. It therefore becomes interesting to investigate the set of values that the asymptotic rank of a tensor (of given dimension $d$ and given lengths in the $d$ different directions) can take for various notions of rank. Previous work has shown that the set of possible values has gaps: for example, the only possible non-integral value less than 2 is $2^{h(1/3)}$, where $h$ is the binary entropy function. It has also shown that the set of possible values is countable. This paper considerably strengthens the latter result by showing that it is in fact a discrete set. This is trivial for matrices, since it must be an integer, but much less so for tensors (except that for the asymptotic tensor rank of tensors over a finite field, it turns out to have a very short proof).

The paper also contains a wealth of intermediate results of independent interest, including results on the relations between subrank and the min-rank of matrix spaces, between min-rank and max-rank, as well as between small Kronecker powers and matrix multiplication. (The min-rank/max-rank of a 3-tensor $T$ in direction $i$ is the smallest/largest rank of a matrix belonging to the linear span of the slices of $T$ perpendicular to direction $i$.) A key lemma proved in the paper is that if a 3-tensor $T\in\mathbb F^{n_1\times n_2\times n_3}$ is concise – meaning that for each of the three directions its slices in that direction are linearly independent – then its asymptotic subrank is at least the cube root of $\min\{n_1,n_2,n_3\}$.