# Is the asymptotic rank of a tensor bounded by (naive) border rank?

Write $$R(T)$$ for the rank of an order-$$3$$ tensor $$T \in \mathbb C^{m \times n \times p}$$ over the complex numbers. If $$T' \in \mathbb {C}^{m' \times n' \times p'}$$ is another such tensor then let $$T \otimes T' \in \mathbb{C}^{mm' \times nn' \times pp'}$$ denote their tensor product (aka Kronecker product). It is straightforward to verify that $$R(T \otimes T') \le R(T) R(T')$$, and from this it follows that the sequence $$R(T^k)^{1/k}$$ converges to its infimum. The asymptotic rank of $$T$$ is $$\tilde R(T) = \lim_{k \to \infty} R(T^k)^{1/k} = \inf_{k \ge 1} R(T^k)^{1/k}.$$

For example, if $$T = m_2$$ is the structure tensor for $$2 \times 2$$ matrix multiplication then $$\tilde R(T) = 2^\omega$$ where $$\omega$$ is the exponent of matrix multiplication. It would therefore be putting it mildly to say that $$\tilde R(T)$$ is not easy to calculate.

My question is actually about the border rank of tensors. The literature agrees universally that this is denoted $$\underline R(T)$$, but seems to vary wildly on what it's actual definition is. Here are some possibilities:

1. According to some sources, including Wikipedia, border rank is the minimal $$r$$ such that $$T$$ is a limit of tensors of rank at most $$r$$. Let's call this $$\underline R^\text{naive}$$. Wikipedia has a basic example of a tensor with $$R(T) = 3$$ but $$\underline R^\text{naive}(T) = 2$$.

2. That cannot possibly be the "right" definition for an arbitrary field since there is no natural topology in general. I have seen at least one source therefore define border rank to be the least $$r$$ such that $$T$$ is in the Zariski closure of the set of tensors of rank at most $$r$$. Call this $$\underline{R}^\text{Zariski}$$.

3. Most of the literature that actually carefully defines and proves things (such as the book Algebraic Complexity Theory, Chapter 15) defines border rank in terms of algebraic expressions over $$\mathbb C[\epsilon]$$ of the type $$\epsilon^d T + O(\epsilon^{d+1}) = (\text{rank-r tensor})$$ for some integer $$d$$. Let's call this definition $$\underline R^\text{original}(T)$$.

Note that $$\underline R^\text{Zariski} \le \underline R^\text{naive} \le \underline R^\text{original}$$.

Question 1: Are these things really different? What are good examples?

Anyway, the crucial inequality relating border rank (at least in its original definition) to asymptotic rank is $$\tilde R(T) \le \underline R^\text{original}(T)$$. However, it seems to be implicit in some of the more recent literature that this holds for $$R^\text{naive}$$ (see for example the intro to https://arxiv.org/abs/1112.6007). Is this true?

Question 2: Is it true that $$\tilde R \le \underline R^\text{naive}$$?

Of course, we could ask the same question for $$\underline R^\text{Zariski}$$, which would be even better.

• ... $R$ is a limit of tensors of rank at most $r$ - you mean, $T$ is a limit? Feb 22 at 20:48
• @FedorPetrov Yes, thanks Feb 23 at 9:03

It is true that over $$\mathbb{C}$$ (and over every algebraically closed field) we have $$\underline{R}^{\mathrm{Zariski}}(T) = \underline{R}^{\mathrm{original}}(T)$$.
The idea is that the set $$X_r$$ of tensors of rank at most $$r$$ is constructible and therefore contains a subset $$Y_r$$ open in the Zariski closure $$\overline{X}_r$$. If $$x \in \overline{X}_r \setminus X_r$$, then, taking an intersection of $$\overline{X}_r$$ with a general affine subspace of appropriate dimension containing $$x$$, we can get an algebraic curve $$C \subset \overline{X}_r$$ such that $$x \in C$$ and $$C \cap Y_r$$ is open in $$C$$. Then we take a normalization of this curve to get rid of possible singularity at $$x$$, which gives a local parametrization of $$C$$ at $$x$$ equivalent to the required expression with $$\varepsilon$$.