Subrank and optimal reduction of scalar multiplications to generic tensors (Q6591570)

The subrank of a bilinear map represents the maximum number of independent scalar multiplications that can be reduced to the bilinear map, based on the natural concept of algebraic complexity reduction. Here, the notion of a reduction between bilinear maps is a reduction in the sense of computational complexity. This concept generalizes the idea of matrix rank and extends naturally to multilinear maps (\(k\)-tensors) as bilinear maps (and more generally, multilinear maps) naturally correspond to tensors. Let \(K^{n_1,n_2,n_3}\) be the space of 3-tensors (three-dimensional arrays) \(T=(T_{i,j,k})_{i,j,k}\) where \(1\le i \le n_1\), \(1\le j \le n_2\) and \(1\le k \le n_3\). For tensors \(S\in K^{n_1,n_2,n_3}\) and \(T\in K^{m_1,m_2,m_3}\), the notation \(S \le T\) means that there exist \(n_1\times m_1\), \(n_2\times m_2\) and \(n_3\times m_3\) matrices \(A\), \(B\) and \(C\), respectively, such that \(S\) is obtained from \(T\) by applying \(A\), \(B\) and \(C\) to the slices of \(T\). Let \(I_r \in K^{r,r,r}\) be the tensor for which the diagonal entries \((i,i,i)\) of \(I_r\) are one and the other entries are zero. In the language of tensors, the subrank \(Q(T)\) is again the largest number \(r\) such that \(I_r \le T\). This definition of subrank also naturally extends to higher order tensors \( K^{n_1,\ldots,n_k}\).\N\NLet \(Q(n)=Q(n,n,n)\) represent the generic subrank of tensors in \(K^{n,n,n}\). More precisely, \(Q(n)\) refers to the subrank that applies to ``essentially all'' tensors, or to ``randomly chosen'' tensors with probability one. In this paper, the subrank of generic tensors with an arbitrary order (\(k\ge 3\)) is determined. It is proved that \(Q(n)\) grows as \(\sqrt{n}\). Specifically, both upper and lower bounds for \(Q(n)\) are established. The results presented in this paper significantly improve upon the previous best bounds on \(Q(n)\) established by \textit{V. Strassen} [J. Reine Angew. Math. 413, 127--180 (1991; Zbl 0746.65049)] and \textit{P. Bürgisser} [Degenerationsordnung und Trägerfunktional bilinearer Abbildungen. Konstanz: Universität Konstanz, Fak. f. Mathematik (1990; Zbl 0726.15023)]. Denoting the subrank of a generic tensor in \(K^{n,\ldots,n}\) of order \(k\) by \(Q(n,\ldots,n)\), both upper and lower bounds for \(Q(n,\ldots,n)\) are found. It is shown that \(Q(n,\ldots,n)\) grows as \(n^{1/(k-1)}\). Additionally, an optimal decomposition theorem is proven for tensor subspaces, decomposing the tensor space into highly structured subspaces. As an application of the upper bound on the generic subrank, it is demonstrated that subrank is not additive under the direct sum. The paper concludes by outlining several open problems that arise from or are closely related to the results on the generic subrank.