How to count the number of tensors over a finite field of tensor rank $r$?

Question

For simplicity, work over $\mathbb F_2$ and only consider order-$3$ equilateral tensors. For $r\in\mathbb Z_{>0}$, how many tensors $\mathfrak{T}\in\mathsf{Ten}_{n}^{\otimes 3}(\mathbb F_2)$ are there of tensor rank $r$? ($\mathfrak{T}$ is Gothic $T$.) Here $\mathsf{Ten}_n^{\otimes 3}(\mathbb F_2)$ denotes the set of all $n\times n\times n$ tensors over $\mathbb F_2$. In general, the tensor rank of a tensor $\mathfrak{T}\in\mathsf{Ten}_{\ell,m,n}(\mathbb F)$ is defined as $$\mathrm{trk}(\mathfrak{T})=\min\left\{r\in\mathbb Z_{>0}\colon\mathfrak{T}=\sum_{i=1}^r\vec{u}\otimes\vec{v}\otimes \vec{w} \text{ for }\vec u\in\mathbb F^\ell,\vec v\in\mathbb F^m,\vec w\in\mathbb F^n\right\}.$$

The same question is easy for matrices over $\mathbb F_2$ (and indeed over finite field of any characteristic). Note that picking an $r$-dimensional subspace of $\mathbb F_2^n$ can be thought as picking a rank $r$ matrix of size $n\times k$ for some $n\ge k\ge r$ (for the current purpose, take $k=n$), modulo picking a $k\times r$ matrix of rank $r$. $$\# r\text{-dim subspaces}=\frac{\#n\times k\text{ matrices of rank }r}{\#k\times r\text{ matrices of rank }r}.$$

The number of $r$-dimensional subspaces is given by the famous Gaussian binomial coefficient $\begin{bmatrix}n\\r\end{bmatrix}_2$. The number of full column-rank $k\times r$ matrix ($k>r$) can be obtained by sequentially picking its columns so that the $i$-th column is linearly independent of the first $i-1$ columns. This gives $\prod_{i=0}^{r-1}(2^k-2^i)$. Hence the number of rank-$r$ $n\times k$ matrices is $$\begin{bmatrix}n\\r\end{bmatrix}_2\cdot \prod_{i=0}^{r-1}(2^k-2^i)=\prod_{i=0}^{r-1}\frac{(2^n-2^i)(2^k-2^i)}{2^r-2^i}.$$

I do not see how to apply such an idea to tensors. For one thing, we can think of a tensor as generating a vector space of matrices. Some people call it a slice space of the tensor (cf. page 2 of this paper). However, there does not seem to be a higher order notion of Gaussian coefficient for a subspace of $\mathsf{Mat}_{n\times n}(\mathbb F_2)$. For another thing, tensors have different directions. By that I mean, an order-$3$ tensor has three directions. We cannot pick sequentially two-dimensional slices, i.e., three $n\times n$ matrices, and claim that the tensor rank is bounded desiredly.

My question is: how can one count the number of $\ell\times m\times n$ tensors over $\mathbb F_q$ of rank $r$?

Answer 1

This seems difficult. Deciding if a tensor has rank $\leq r$ (over a fixed finite field) is $\mathsf{NP}$-complete (Hastad, 1990). I haven't checked recently, but surely it's also the case that counting the number of ways to write a given tensor as a sum of $r$ rank-one tensors is $\mathsf{\# P}$-complete. Such counts are the size of the fibers of the natural map from r-tuples of rank-1 tensors onto the space of tensors of rank $\leq r$, which would be at least one analogue of trying to count them the way you did for rank $r$ matrices.

Note that, unlike matrices, the space of tensors of rank $r$ has many orbits of the natural group action (of $GL_n \times GL_n \times GL_n$), whereas for matrices the set of matrices of a given rank is a single orbit. Counting the number of these orbits also seems hard. (In particular, deciding whether two tensors are in the same orbit is at least as hard as Graph Isomorphism, Code Equivalence, and several even harder isomorphism problems, so we might expect that counting isomorphism types of tensors of rank $r$ - for $r$ sufficiently large* - should be at least as hard as counting isomorphism types of graphs. The complexity of the latter problem is not known, but again, seems hard, see, e.g., this question.)

* For $r=1$ and 2 it should not be too hard to count. Maybe even for the next few values. But even relatively small $r$ - maybe 5 or 6 is enough? maybe 10? - I expect this to already be difficult.

Answer 2

As far as I know the problem of finding what is the maximal rank of any $n\times n \times n$ tensor is open. Since this is a subproblem of your question it is unlikely that there exists a formula for # of tensors of a given tensor rank.