# Generic Subrank

Harm Derksen, Visu Makam, and Jeroen Zuiddam

Subrank and Optimal Reduction
of Scalar Multiplications to Generic Tensors

Harm Derksen Visu Makam Jeroen Zuiddam<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Northeastern University Radix Trading Europe
B.V. University of Amsterdam

Abstract

Since the seminal works of Strassen and Valiant it has been a central theme in
algebraic complexity theory to understand the _relative_ complexity of
algebraic problems, that is, to understand which algebraic problems (be it
bilinear maps like matrix multiplication in Strassen’s work, or the
determinant and permanent polynomials in Valiant’s) can be reduced to each
other (under the appropriate notion of reduction).

In this paper we work in the setting of bilinear maps and with the usual
notion of reduction that allows applying linear maps to the inputs and output
of a bilinear map in order to compute another bilinear map. As our main result
we determine precisely how many independent scalar multiplications can be
reduced to a given bilinear map (this number is called the _subrank_ , and
extends the concept of matrix diagonalization to tensors), for essentially all
(i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map
$T:V\times V\to V$ where $\dim(V)=n$ that $\theta(\sqrt{n})$ independent
scalar multiplications can be reduced to $T$. Our result significantly
improves on the previous upper bound from the work of Strassen (1991) and
Bürgisser (1990) which was $n^{2/3+o(1)}$. Our result is very precise and
tight up to an additive constant. Our full result is much more general and
applies not only to bilinear maps and 3-tensors but also to $k$-tensors, for
which we find that the generic subrank is $\theta(n^{1/(k-1)})$. Moreover, as
an application we prove that the subrank is not additive under the direct sum.

The subrank plays a central role in several areas of complexity theory (matrix
multiplication algorithms, barrier results) and combinatorics (e.g., the cap
set problem and sunflower problem). As a consequence of our result we obtain
several large separations between the subrank and tensor methods that have
received much interest recently, notably the slice rank (Tao, 2016), analytic
rank (Gowers–Wolf, 2011; Lovett, 2018;
Bhrushundi–Harsha–Hatami–Kopparty–Kumar, 2020), geometric rank
(Kopparty–Moshkovitz–Zuiddam, 2020), and G-stable rank (Derksen, 2020).

Our proofs of the lower bounds rely on a new technical result about an optimal
decomposition of tensor space into structured subspaces, which we think may be
of independent interest.

###### Contents

  1. 1 Introduction
    1. 1.1 Subrank and generic subrank
    2. 1.2 Our Results
    3. 1.3 Technical Overview
    4. 1.4 Related Work
    5. 1.5 Paper Organization
  2. 2 Upper bounds on generic subrank
    1. 2.1 Tensors of order three
    2. 2.2 Higher-order tensors
  3. 3 Lower bounds on generic subrank
  4. 4 Constructions of tensor space decompositions
    1. 4.1 General construction methods
    2. 4.2 Recursive construction for every order
  5. 5 Application: Subrank is not additive
  6. 6 Open problems

##  1 Introduction

We solve a fundamental problem in algebraic complexity theory about a notion
of complexity on bilinear maps (tensors) called the _subrank_ , which was
introduced by Strassen in [Str87] in the study of fast matrix multiplication
algorithms, and which later found close connections to several hypergraph
independence and Ramsey-type problems in combinatorics and tensor methods in
these areas (e.g., analytic rank [Lov19, BHH+20] and related notions). Our
results improve significantly on previous bounds from the work of Bürgisser
[Bü90] and Strassen [Str91].

In high-level terms, the subrank of a bilinear map is the largest number of
independent scalar multiplications that can be reduced to (i.e. “embedded in”)
the bilinear map, under the natural algebraic complexity notion of reduction
(which we elaborate on in a moment). This definition extends the usual rank of
matrices and moreover naturally extends further to multilinear maps
($k$-tensors). In this paper, we:

  * •

determine the subrank for almost all bilinear maps (i.e. generic bilinear
maps),

  * •

prove precise bounds that are accurate up to a small additive constant,

  * •

extend the above results from bilinear maps ($3$-tensors) also to multilinear
maps ($k$-tensors),

  * •

prove as a technical result (used in the proofs of the above) an optimal
decomposition theorem for tensor subspace, decomposing tensor space into very
structured subspaces,

  * •

prove, as an application of our upper bound on generic subrank, that the
subrank is not additive under the direct sum.

Let us biefly state our asymptotic results here. (We will return to these in
more detail in Section 1.2.) We prove for any vector space111We will require
the base field of the vector space to have the mild property of being
algebraically closed (but it will be clear from our techniques that this
assumption can be weakened considerably). $V$ with $\dim(V)=n$ that almost all
bilinear maps $T:V\times V\to V$ have subrank equal to $\theta(\sqrt{n})$.
That is, $\theta(\sqrt{n})$ independent scalar multiplications can be reduced
to $T$. For $k$-tensors we find the subrank to be $\theta(n^{1/(k-1)})$ on
almost all $k$-tensors.

To prove our results we use methods from algebraic geometry as well as linear
algebraic arguments. Our upper bound proof relies on an efficient
parametrization of the set of tensors with subrank larger than a given number
(as a collection of orbits) and a good dimension estimate of this set. Our
lower bound proof relies on arguments involving differentials. At the core we
prove a technical result about a very structured decomposition of tensor space
which we think may be of independent interest. The main goal here (in the
simplest case) is to write tensor space as a sum of tensor subspaces as
efficiently as possible (meaning with smallest as possible sum of dimensions)
such that each subspace has the special form of a matrix subspace tensored
with $n$-space. Our technical result is that we can do this optimally for any
order of tensor space. We discuss the proof methods further in Section 1.3.

To get some intuition for the subrank it is instructive to ask how the subrank
relates to the better known complexity notion _tensor rank_. Subrank and rank
are indeed closely linked, and in a sense they are dual to each other. Indeed,
whereas the subrank of a bilinear map $T$ is the maximal number of independent
scalar multiplications that can be reduced to $T$, the rank of $T$ is (among
several equivalent definitions) the minimal number of independent scalar
multiplications that $T$ reduces to. In this way, the rank measures the
computational “cost” of $T$ in terms of scalar multiplications while the
subrank measures the “value” of $T$ in terms of independent scalar
multiplications.

###  1.1 Subrank and generic subrank

Let us now discuss more precisely several equivalent formulations and the
meaning of the definition of subrank, and the sense in which we determine the
subrank for almost all tensors (the generic subrank).

#### Subrank of bilinear and multilinear maps.

We first stay in the realm of bilinear maps, and will define subrank via the
notion of a reduction between bilinear maps, which is really a reduction in
the sense of computational complexity. Given two bilinear maps $S:V_{1}\times
V_{2}\to V_{3}$ and $T:W_{1}\times W_{2}\to W_{3}$ we say $S$ reduces to $T$
and write $S\leq T$ if there are linear maps $L_{1}:V_{1}\to W_{1}$,
$L_{2}:V_{2}\to W_{2}$ and $L_{3}:W_{3}\to V_{3}$ such that
$S(v_{1},v_{2})=L_{3}(T(L_{1}(v_{1}),L_{2}(v_{2}))$ for all $v_{1}\in
V_{1},v_{2}\in V_{2}$. (In the literature, this relation $\leq$ on tensors is
often called the _restriction preorder_ and when $S\leq T$ one says that “$S$
is a restriction of $T$ ” [Str87, BCS97].) In other words, if $S\leq T$, then
any algorithm for $T$ also gives an algorithm for $S$ (with only small
computational overhead, namely applying the linear maps $L_{i}$ to inputs and
output). Next, an important basic bilinear map that we use to define subrank
is (for any positive integer $r$) the bilinear map $I_{r}$ that computes $r$
independent scalar multiplications with scalars from some222We will put some
mild restrictions on the field in some parts of the paper. field $K$:

$I_{r}:K^{r}\times K^{r}\to
K^{r}:(v_{1},v_{2})\mapsto((v_{1})_{1}(v_{2})_{1},\ldots,(v_{1})_{r}(v_{2})_{r}).$

With these notions set up, the subrank ${\rm Q}(T)$ of a bilinear map
$T:V_{1}\times V_{2}\to V_{3}$ is defined as the largest number $r$ such that
$I_{r}$ reduces to $T$, that is, $I_{r}\leq T$. On the other hand, the tensor
rank of $T$ is the smallest number $r$ such that $T\leq I_{r}$. Thus, the
subrank ${\rm Q}(T)$ is indeed the largest number of independent scalar
multiplications that can be reduced to $T$, while the rank is the smallest
number of independent scalar multiplications that $T$ reduces to. The above
definition of subrank extends directly to multilinear maps
$V_{1}\times\cdots\times V_{k-1}\to V_{k}$ by naturally extending the
reduction and defining $I_{r}$ as the multilinear map that computes $r$
independent $(k-1)$-wise products.

#### Subrank of tensors.

Alternatively we may phrase the definition of the subrank in the language of
tensors, as bilinear maps (and multilinear maps) naturally correspond to
these. Let $K^{n_{1},n_{2},n_{3}}$ be the space of 3-tensors (3-dimensional
arrays) $T=(T_{i,j,k})_{i,j,k}$ with $i\in[n_{1}]$, $j\in[n_{2}]$,
$k\in[n_{3}]$. For tensors $S\in K^{n_{1},n_{2},n_{3}}$ and $T\in
K^{m_{1},m_{2},m_{3}}$ we write $S\leq T$ if there are matrices
$A\in\operatorname{Mat}_{n_{1},m_{1}}$,
$B\in\operatorname{Mat}_{n_{2},m_{2}}$, $C\in\operatorname{Mat}_{n_{3},m_{3}}$
such that $S$ is obtained from $T$ by applying $A,B,C$ to the slices of $T$,
in the sense that

$S_{i,j,k}=\sum_{a,b,c}A_{i,a}B_{j,b}C_{k,c}T_{a,b,c}$

for all $i\in[n_{1}],j\in[n_{2}],k\in[n_{3}]$. Let $I_{r}\in K^{r,r,r}$ be the
tensor for which the diagonal entries $(I_{r})_{i,i,i}$ are 1 and the other
entries are 0. In this language the subrank ${\rm Q}(T)$ is again the largest
number $r$ such that $I_{r}\leq T$. This definition of subrank also naturally
extends to higher-order tensors $K^{n_{1},\ldots,n_{k}}$.

#### Subrank on “almost all” tensors; generic subrank.

It follows from a short argument (which we give later; 2.1) that for vector
spaces $V_{1},V_{2},V_{3}$, there is a subset $U$ of all bilinear maps
$V_{1}\times V_{2}\to V_{3}$ that is nonempty and Zariski-open (the complement
is the zero-set of a finite collection of polynomials) and with constant
subrank. This set $U$ thus contains almost all bilinear maps $V_{1}\times
V_{2}\to V_{3}$. The subrank on $U$ is called the _generic subrank_. We denote
the generic subrank of bilinear maps $K^{n_{1}}\times K^{n_{2}}\to K^{n_{3}}$
(or equivalently of tensors in $K^{n_{1},n_{2},n_{3}}$) by ${\rm
Q}(n_{1},n_{2},n_{3})$ (and by ${\rm Q}(n_{1},\ldots,n_{k})$ generally for
higher-order tensors).

###  1.2 Our Results

As our main results we determine (1) the subrank of generic tensors of order
three, and, more generally, (2) the subrank of generic tensors of any order
$k\geq 3$. Moreover, as a core technical ingredient in our proof of (1) and
(2), we prove (3) an optimal decomposition of tensor space into highly
structured subspaces, which we think is of independent interest and which may
have further applications in algebraic complexity theory. We will now describe
each of these results in detail.

#### (1) The generic subrank of tensors of order three.

We will begin by discussing our results for tensors of order three (or
equivalently, for trilinear maps or bilinear maps on vector spaces of
appropriate dimensions). Recall that ${\rm Q}(n)={\rm Q}(n,n,n)$ denotes the
generic subrank of tensors in $K^{n,n,n}$. In other words, ${\rm Q}(n)$ is the
value that the subrank takes on “essentially all” tensors, or on “randomly
chosen” tensors with probability 1. We prove that ${\rm Q}(n)$ grows as
$\sqrt{n}$.

######  Theorem 1.1.

We have ${\rm Q}(n)=\theta(\sqrt{n})$.

We thus solve the problem of determining the generic subrank of tensors of
order three (and also, with more work, of order $k$ in general as we will
discuss below). In computational terms, Theorem 1.1 states that for
“essentially all” bilinear maps $T:K^{n}\times K^{n}\to K^{n}$ we can reduce
the problem of multiplying $\sqrt{n}$ independent pairs of numbers to $T$, and
that this is optimal (under the usual notion of reduction from algebraic
complexity theory in which linear maps are applied to the inputs and output of
$T$).

In particular, with Theorem 1.1 we significantly improve on the previous best
upper bound on ${\rm Q}(n)$ of Strassen and Bürgisser (obtained via the method
of “lower support functionals”) which was ${\rm Q}(n)\leq n^{2/3+o(1)}$.

As an application of Theorem 1.1 we prove that the subrank is not additive
under the direct sum. Namely, we prove that there are bilinear maps
$S,T:K^{n}\times K^{n}\to K^{n}$ such that ${\rm Q}(T)+{\rm
Q}(S)=\theta(\sqrt{n})$ while ${\rm Q}(T\oplus S)\geq n$. In other words, it
is sometimes possible to reduce many more independent scalar multiplications
to a direct sum of bilinear maps than to the bilinear maps separately.333This
result is the subrank analogue of the recent result of Shitov [Shi19] that
disproved Strassen’s additivity conjecture for tensor rank [Str73]. For this
he constructed a complicated example of 3-tensors $S,T$ (over any infinite
field) such that ${\rm R}(S\oplus T)<{\rm R}(S)+{\rm R}(T)$. We discuss
additivity results further in Section 1.4 .

As a direct consequence of Theorem 1.1, we separate the generic subrank ${\rm
Q}(n)$ from the generic asymptotic subrank
$\operatorname{\underaccent{\wtilde}{Q}}(n)$444The asymptotic subrank is
defined as $\operatorname{\underaccent{\wtilde}{Q}}(T)=\lim_{n\to\infty}{\rm
Q}(T^{\otimes n})^{1/n}$ and $\operatorname{\underaccent{\wtilde}{Q}}(n)$
denotes the value of $\operatorname{\underaccent{\wtilde}{Q}}(T)$ for a
generic tensor $T\in K^{n,n,n}$., for which Strassen proved that the generic
value satisfies $\operatorname{\underaccent{\wtilde}{Q}}(n)\geq n^{2/3}$
[Str88, Prop. 3.6]. Moreover, our result gives a large separation between the
subrank on the one hand, and the slice rank (and partition rank, for higher
order tensors), geometric rank, and G-stable rank on the other hand (whose
generic value is full).

Let us now discuss the bound of Theorem 1.1 in more detail, and in particular
get the precise constants right, after which we discuss the extension to
higher-order tensors. We (naturally) obtain Theorem 1.1 in two parts, namely
by first proving the following upper bound:

######  Theorem 1.2.

We have ${\rm Q}(n)\leq\lfloor\sqrt{3n-2}\rfloor$.

And then proving the following essentially matching lower bound:

######  Theorem 1.3.

We have ${\rm Q}(n)\geq 3(\lfloor\sqrt{n/3+1/4}-1/2\rfloor)$.

It is not difficult to see that our upper and lower bounds on the generic
subrank are very precise. Namely, the difference between the upper bound
$\lfloor\sqrt{3n-2}\rfloor$ and the lower bound
$3(\lfloor\sqrt{n/3+1/4}-1/2\rfloor)$ is at most a small additive
constant.555Indeed, a straightforward direct computation shows that
$\lfloor\sqrt{3n-2}\rfloor-3(\lfloor\sqrt{n/3+1/4}-1/2\rfloor)\leq 5$.

We conjecture that our upper bound in Theorem 1.2 is tight. Through a more
sophisticated analysis (which requires as a final component a computer
verification that a determinant is nonzero) we prove that for all $1\leq n\leq
100$ our upper bound is in fact tight, that is: for all $1\leq n\leq 100$ we
have ${\rm Q}(n)=\lfloor\sqrt{3n-2}\rfloor$.

#### (2) The generic subrank of $k$-tensors.

So far we have discussed only tensors of order three. With more elaborate
methods we are able to completely extend our above results from tensors of
order three to tensors of order $k$ for every $k\geq 3$. Denoting the subrank
of a generic tensor in $K^{n,\ldots,n}$ of order $k$ by ${\rm Q}(n,\ldots,n)$,
we find that ${\rm Q}(n,\ldots,n)$ grows as $n^{1/(k-1)}$.

######  Theorem 1.4.

We have ${\rm Q}(n,\ldots,n)=\theta(n^{1/(k-1)})$.

Again this result directly leads to a large separation between the subrank and
the asymptotic subrank (for which the generic value, extending a construction
of Strassen, satisfies $\operatorname{\underaccent{\wtilde}{Q}}(n)\geq
n^{2/k}$), and a separation between the subrank and the slice rank, partition
rank, geometric rank and G-stable rank (all of whose generic value is $n$).

Regarding the precise bounds, we prove Theorem 1.4 in two parts again. In the
first we extend the upper bound of Theorem 1.2 to order $k$, in a fully
general manner as an upper bound on the generic subrank ${\rm
Q}(n_{1},\ldots,n_{k})$ where the $n_{i}$ need not be equal, as follows.

######  Theorem 1.5.

We have ${\rm
Q}(n_{1},\ldots,n_{k})\leq\bigl{(}\sum_{i=1}^{k}n_{i}-(k-1)\bigr{)}^{\frac{1}{k-1}}.$

Then finally we extend Theorem 1.3 to order $k$ tensors, which leads to the
asymptotically matching lower bound (which for conciseness we will not write
down here more explicitly).

######  Theorem 1.6.

We have ${\rm Q}(n,\ldots,n)\geq\Omega(n^{1/(k-1)})$.

Our proof of this last theorem (and also Theorem 1.3) makes crucial use of the
technical results on tensor space that we discuss in the next section.

#### (3) Technical result: structured subspace decomposition of tensor space.

The proofs of our lower bounds (Theorem 1.3 and Theorem 1.6) rely on a
technical result about a very structured decomposition of tensor space which
we think may be of independent interest, so we will describe it here. The main
goal here (in the simplest case) is to write tensor space $K^{n,n,n}$ as a sum
of tensor subspaces as efficiently as possible (meaning with smallest as
possible sum of dimensions) such that each subspace has the form of an
$n\times n$ matrix subspace tensored with $K^{n}$ (so that it becomes a
subspace of $K^{n,n,n}$) with the tensoring being applied in any of the three
possible directions. Our result is that we can do this optimally for any order
of tensor space.

We will begin our discussion with the simplest version, which is for the
tensor space $K^{3,3,3}$, as it is the easiest to explain (and in fact also
not hard to prove) and forms the basis for the proof of the (harder to prove)
general version for the tensor space $K^{n,\ldots,n}=(K^{n})^{\otimes n}$ of
tensors of order $n$ and dimension $n$ in each direction (in our application
to the generic subrank we use a blow-up argument so that we can deal with
tensors of order $k$ and dimension $n$ in each direction).

Recall that $K^{n_{1},n_{2},n_{3}}$ denotes the space of $n_{1}\times
n_{2}\times n_{3}$ tensors with coefficients in the field $K$, which we
require to be large enough in this part. Let $\operatorname{Mat}_{n,m}$ denote
the space of $n\times m$ matrices with coefficients in $K$. We use a special
notation to denote a certain construction of a tensor subspaces given a matrix
subspace. Namely, for any given $n_{1}\times n_{2}$ matrix subspace
$\mathcal{W}\subseteq\operatorname{Mat}_{n_{1},n_{2}}$ we denote by
$\mathcal{W}[3]$ the tensor subspace $\mathcal{W}\otimes K^{n_{3}}\subseteq
K^{n_{1},n_{2},n_{3}}$. Analogously, for any matrix subspace
$\mathcal{W}\subseteq\operatorname{Mat}_{n_{2},n_{3}}$ we denote by
$\mathcal{W}[1]\subseteq K^{n_{1},n_{2},n_{3}}$ the tensor subspace obtained
by appropriately tensoring $\mathcal{W}$ with $K^{n_{1}}$, and for any matrix
subspace $\mathcal{W}\subseteq\operatorname{Mat}_{n_{1},n_{3}}$ we denote by
$\mathcal{W}[2]\subseteq K^{n_{1},n_{2},n_{3}}$ the tensor subspace obtained
by appropriately tensoring $W$ with $K^{n_{2}}$.

For the tensor space $K^{3,3,3}$ we have the following optimal decomposition
theorem.

######  Theorem 1.7.

There exist subspaces
$\mathcal{X}_{i}\subseteq\operatorname{Mat}_{3,3}=K^{3}\otimes K^{3}$, each of
dimension 3, such that

$K^{3,3,3}=\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3].$

Comparing dimensions, we have $\dim K^{3,3,3}=3\cdot 3\cdot
3=\dim\mathcal{X}_{1}[1]+\dim\mathcal{X}_{2}[2]+\dim\mathcal{X}_{3}[3]$ and so
the decomposition in Theorem 1.7 is optimal. In other words, it is a direct
sum decomposition of $K^{3,3,3}$.

The requirement in Theorem 1.7 that the $\mathcal{X}_{i}$ all have dimension 3
is crucial to make the theorem interesting, as without this requirement we
could “decompose” $K^{3,3,3}$ simply as $K^{3,3,3}=\mathcal{X}_{1}[1]$ with
$\mathcal{X}_{1}=\operatorname{Mat}_{3,3}$. Interestingly, the analogous
statement of Theorem 1.7 for any matrix space $K^{n,n}$ is false. That is, for
every positive integer $n$ there are no subspaces $\mathcal{X}_{i}\subseteq
K^{n}$, each of dimension $n/2$, such that
$K^{n,n}=\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]$. This is saying that if we
pick a row space $R$ and a column space $C$ of dimension $n/2$, then it is not
possible to write every $n\times n$ matrix $A$ as $A_{1}+A_{2}$ where the row
space of $A_{1}$ is in $R$ and the column space of $A_{2}$ is in $C$. On the
other hand, 3-tensors do not suffer from this malady: we can write any tensor
as a sum of thee tensors, whose “rowi”-space are asked to be in a generic
space of the right dimension. (Here we can think of $W[i]$ as tensors whose
“rowi”-space is $W$.) Therefore, Theorem 1.7 is demonstrating an interesting
phenomenon that occurs in tensor space but not in matrix space.

Theorem 1.7 (as opposed to the upcoming generalization to $(K^{n})^{\otimes
n}$) is not difficult to prove. Indeed, one may choose the matrix subspaces
$\mathcal{X}_{i}$ randomly and then for such an explicit choice verify
directly that they satisfy the claim (and this approach will work with high
probability). In fact, there are even valid choices of the $\mathcal{X}_{i}$
such that each $\mathcal{X}_{i}$ is spanned by a matrix with coefficients in
$\\{0,1\\}$.

Next we discuss the higher-dimensional version of Theorem 1.7 in which
$K^{3,3,3}$ is generalized to $n$-tensor space $(K^{n})^{\otimes n}$. We
naturally extend our previous notation so that for every tensor subspace
$\mathcal{W}\subseteq(K^{n})^{\otimes(n-1)}$ we define, for any
$i\in\\{1,\ldots,n\\}$, the tensor subspace
$\mathcal{W}[i]\subseteq(K^{n})^{\otimes n}$ by tensoring $\mathcal{W}$ with
$K^{n}$ in one of the $n$ possible ways.

By a recursive construction with $K^{3,3,3}$ as a base case, we find the
following optimal decomposition of $n$-tensor space $(K^{n})^{\otimes n}$ for
all $n\geq 3$.

######  Theorem 1.8.

For every integer $n\geq 3$ there exist subspaces
$\mathcal{X}_{i}\subseteq(K^{n})^{\otimes n-1}$ of dimension $n^{n-2}$ such
that

$(K^{n})^{\otimes
n}=\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\cdots+\mathcal{X}_{n}[n].$

Again, since $\dim K^{n,\ldots,n}=n^{n}=n\cdot n\cdot
n^{n-2}=\sum_{i=1}^{n}\dim\mathcal{X}_{i}[i]$, the decomposition in Theorem
1.8 is optimal in terms of dimension and hence a direct sum decomposition of
$(K^{n})^{\otimes n}$.

Theorem 1.8 is the theorem we use to prove the general generic subrank lower
bound Theorem 1.6. However, the methods we introduce in the process of proving
Theorem 1.8 allow us much more generally for other choices of positive
integers $n_{1},\ldots,n_{k}$ to construct optimal decompositions
$K^{n_{1},\ldots,n_{k}}=\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\cdots+\mathcal{X}_{k}[k]$
from known decompositions. This leads to a natural fundamental mathematical
question (with potentially other applications) of what choices of
$n_{1},\ldots,n_{k}$ and $\dim\mathcal{X}_{i}$ allow such decompositions.

###  1.3 Technical Overview

We give a brief technical overview of the methods and ideas that we use in our
proofs.

#### Upper bounds on generic subrank.

The high-level approach in our proof of the upper bound on the generic subrank
in Theorem 1.2 (and similarly for the general case of Theorem 1.5) is as
follows. For any nonnegative integer we consider the set $\mathcal{C}_{r}$ of
tensors in $K^{n,n,n}$ with subrank at least $r$. We argue that the generic
subrank is precisely the largest $r$ such that the dimension of
$\mathcal{C}_{r}$ equals the dimension $n^{3}$ of the full space $K^{n,n,n}$.
We then prove the core ingredient, namely the dimension upper bound
$\dim(\mathcal{C}_{r})\leq n^{3}-r(r^{2}-3n+2)$. This information leads to the
desired result, since if we let $t$ be the generic subrank ${\rm Q}(n)$, then
we must by the above have $n^{3}=\dim(\mathcal{C}_{t})\leq
n^{3}-t(t^{2}-3n+2)$, from which we directly deduce that $t\leq\sqrt{3n-2}$,
that is, we obtain the bound ${\rm Q}(n)\leq\sqrt{3n-2}$ of Theorem 1.2.

To prove the aforementioned dimension upper bound on $\mathcal{C}_{r}$ that is
the core ingredient in the above argument we employ the idea of providing a
(non-injective) parametrization of $\mathcal{C}_{r}$, compute the dimension of
the parameter space, and then subtracting the dimension “over-count” (the
fiber dimension under the parametrization). For this we first define a set
$X_{r}$ of tensors in $K^{n,n,n}$ of a special form, namely whose
$[r]\times[r]\times[r]$ subtensor is zero except for the diagonal which is
nonzero. Then the elements of $X_{r}$ clearly have subrank at least $r$ (and
are thus in $\mathcal{C}_{r}$). The important point is that, by applying all
possible basis transformations to the tensors in $X_{r}$ we obtain all of
$\mathcal{C}_{r}$. Thus $X_{r}$ together with the group of all basis
transformations provide the parametrization of $\mathcal{C}_{r}$. Technically,
we describe this by saying that the map
$\psi_{r}:\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times
X_{r}\to K^{n,n,n}$ that maps $(A,B,C,T)$ to $(A\otimes B\otimes C)T$ has
image precisely $\mathcal{C}_{r}$. Now the computation to upper bound
$\dim(\mathcal{C}_{r})$ consists of computing the dimension of the domain
$\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times
X_{r}$ and subtracting the dimension of a general fiber of $\psi_{r}$, which
we carry out to arrive at the dimension upper bound stated earlier.

#### Lower bounds on generic subrank.

The high-level approach in our proof of the lower bound on the generic subrank
in Theorem 1.3 (and the general Theorem 1.6) is as follows. We use notation
defined in the upper bound proof discussion and the results section (Section
1.2). Our proof reduces the problem of lower bounding the generic subrank
${\rm Q}(n_{1},n_{2},n_{3})$ to a problem of constructing tensor space
decompositions of a specific form (which we discuss further in the next
section). Namely we prove that, for $r\leq n_{1},n_{2},n_{3}$ (with a
technical condition), if $\mathcal{X}_{i}\subseteq\operatorname{Mat}_{r,r}$
are subspaces of dimension $n_{i}-r$ for $i=1,2,3$ such that

$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]=K^{r,r,r},$

then ${\rm Q}(n_{1},n_{2},n_{3})\geq r$. (And we prove the analogous statement
for higher-order tensors.) Finding such $\mathcal{X}_{i}$ we discuss in the
next section. The proof of the lower bound given the $\mathcal{X}_{i}$ goes as
follows.

Recall the map
$\psi_{r}:\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times
X_{r}\to K^{n,n,n}$ whose image we already claimed is the set
$\mathcal{C}_{r}$ of tensors of subrank at least $r$. To reach our goal we
want to find conditions that imply that the image of $\psi_{r}$ has full
dimension $n^{3}$ and thus is Zariski-dense in $K^{n,n,n}$. To do this we use
the notion of the differential $d\psi_{r}$ of $\psi_{r}$ and a general method
that says that the dimension of a map can be computed as the rank of the
differential at a “generic point”.

The differential $d\psi_{r}$ at the point $(g_{1},g_{2},g_{3},T)$ is the map

$(d\psi_{r})_{(g_{1},g_{2},g_{3},T)}:\operatorname{Mat}_{n,n}\times\operatorname{Mat}_{n,n}\times\operatorname{Mat}_{n,n}\times
Y_{r}\to K^{n,n,n}$

where $Y_{r}$ is the tangent space of $X_{r}$, given by

$(A,B,C,S)\mapsto((A\otimes g_{2}\otimes g_{3})+(g_{1}\otimes B\otimes
g_{3})+(g_{1}\otimes g_{2}\otimes C))T+(g_{1}\otimes g_{2}\otimes g_{3})S.$

Analyzing this map we compute its image which leads to the aforementioned
lower bound statement on the generic subrank. In fact we prove a stronger
lower bound, which in characteristic 0 characterizes the generic subrank
precisely, but with a harder to analyze condition, in Theorem 3.9. In
particular, if the characteristic of $K$ is $0$, then Theorem 3.9 says that
${\rm Q}(n_{1},n_{2},n_{3})$ is given by the smallest number $r$ such that
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}=K^{r,r,r}$ for
generic subspaces $\mathcal{X}_{i}\subseteq\operatorname{Mat}_{r,r}$ of
dimension $n_{i}-r$, where $W_{r}\subseteq K^{r,r,r}$ is the subspace of
tensors such that $T_{ijk}=0$ if $i,j,k$ are all different. (In other
characteristics this number $r$ gives a lower bound.)

#### Constructions of tensor space decompositions.

To prove Theorem 1.8 we introduce general methods to construct the optimal
tensor space decompositions as described in the theorem from existing ones. We
then give some small constructions and combine these in multiple recursions to
achieve the required object.

To set this up we take a very general approach in which we study direct sum
decompositions

$K^{n_{1},n_{2},\ldots,n_{k}}=\mathcal{X}_{1}[1]+\cdots+\mathcal{X}_{k}[k]$

where $\mathcal{X}_{i}\subseteq K^{n_{1}}\otimes\cdots\otimes
K^{n_{i-1}}\otimes K^{n_{i+1}}\otimes\cdots\otimes K^{n_{k}}$ is a tensor
subspace and $\mathcal{X}_{i}[i]$ denotes the subspace obtained by tensoring
$\mathcal{X}_{i}$ with $K^{n_{i}}$ as the $i$th tensor factor. Let $a_{i}$ be
the dimension of $\mathcal{X}_{i}$. We are interested in which values of
$n_{1},\ldots,n_{k}$ and $a_{1},\ldots,a_{k}$ allow for a decomposition of the
above form. Writing these numbers into a $2\times k$ matrix

$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{k}\\\
a_{1}&a_{2}&\cdots&a_{k}\end{bmatrix}$

we let $\mathcal{S}$ be the set of all such matrices for which a decomposition
exists satisfying the parameters given in the matrix. Then Theorem 1.8
corresponds to proving that the $2\times n$ matrix

$\begin{bmatrix}n&n&\cdots&n\\\ n^{n-2}&n^{n-2}&\cdots&n^{n-2}\end{bmatrix}$
(1)

is an element of $\mathcal{S}$.

Next we observe that there are some simple constructions and properties of
elements in $\mathcal{S}$, such as: if a matrix is in $\mathcal{S}$ then if we
permute its columns it is still in $\mathcal{S}$ and the matrix
$\begin{bmatrix}n\\\ 1\end{bmatrix}$ is in $\mathcal{S}$. With slightly more
work we can give direct constructions for

$\begin{bmatrix}2&2&2\\\ 0&3&1\end{bmatrix}$ (2)

being an element of $\mathcal{S}$, for instance.

In order to construct more elements of $\mathcal{S}$ we prove a “direct sum
construction” that given two elements in $\mathcal{S}$ combines them to get a
new one. Namely, this result gives that, if

$\begin{bmatrix}n_{1}&n_{2}&\dots&n_{k-1}&n_{k}^{\prime}\\\
a_{1}^{\prime}&a_{2}^{\prime}&\cdots&a_{k-1}^{\prime}&a_{k}\end{bmatrix}\in\mathcal{S}$

and

$\begin{bmatrix}n_{1}&n_{2}&\dots&n_{k-1}&n_{k}^{\prime\prime}\\\
a_{1}^{\prime\prime}&a_{2}^{\prime\prime}&\cdots&a_{k-1}^{\prime\prime}&a_{k}\end{bmatrix}\in\mathcal{S}$

then we have

$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{k}\\\
a_{1}&a_{2}&\cdots&a_{k}\end{bmatrix}\in\mathcal{S}$

where $n_{k}=n_{k}^{\prime}+n_{k}^{\prime\prime}$, and
$a_{i}=a_{i}^{\prime}+a_{i}^{\prime\prime}$ for $i=1,2,\dots,k-1$.

Finally, from some simple base cases including (2) we give a construction for

$\begin{bmatrix}3&3&3\\\ 3&3&3\end{bmatrix}$

being an element of $\mathcal{S}$ and via an elaborate argument with multiple
recursions arrive at the matrix in (1) being an element of $\mathcal{S}$,
which is the ingredient required in our proof of Theorem 1.6. It is natural to
ask what precisely are all elements of $\mathcal{S}$, which we leave as an
open problem.

###  1.4 Related Work

The previous best bound on the generic subrank ${\rm Q}(n)$ was the upper
bound $n^{2/3+o(1)}$ which follows from the work of Bürgisser [Bü90, Satz
2.8]888[Bü90, Satz 2.8] determines the generic value of a tensor parameter
called the “lower support functional” (unteren Trägerfunktional) which upper
bounds the subrank as proven in [Str91]. as part of the broader research
program on the theory of asymptotic spectra of tensors (motivated by the study
of matrix multiplication algorithms). The proof of this bound relies on the
method of “lower support functionals” introduced by Strassen in [Str91] (see
also the more recent surveys on this topic in [CVZ18, Zui18, WZ21]) and the
properties of these that he proves there. This method recovers certain
asymptotic information about tensors, which importantly is monotone under the
restriction preorder and normalized on diagonal tensors so that it provides an
upper bound on the subrank (in a manner that is very different from the
approach that we take to prove our optimal upper bound). Bürgisser’s analysis
of this method on generic tensors consists of proving that the support of a
generic tensor is large for any choice of basis and a combinatorial study of a
certain type of covering of these supports, which leads to the aforementioned
$n^{2/3+o(1)}$ upper bound.

Recent research has brought about a rich collection of tensor methods that are
in a similar “regime” as the subrank (for instance, they are all monotone
under restriction), each with their own properties and applications in
complexity theory and combinatorics. Notable are the slice rank [Tao16] and
closely related partition rank [Nas20], the analytic rank [GW11, Lov19,
BHH+20], the geometric rank [KMZ20, GL21] and G-stable rank [Der20]. Some
important applications of these methods include new bounds on cap sets [Tao16,
EG17], new bounds on the sunflower problem [NS17], determining the border
subrank of matrix multiplication [KMZ20], and proving matrix multiplication
barriers [BCC+17, Alm19, CVZ19]. Many strong connections have been shown among
these parameters. In particular, Derksen [Der20] showed that the G-stable rank
is equal to the slice rank up to a constant factor, and Cohen–Moshkovitz
[CM21a, CM21b] showed (over large fields) that the partition rank, analytic
rank and geometric rank are equal up to a constant factor, the culmination of
a long line of work on this topic [GT09, KL08, BL15, Jan18, Jan20, Mil19]. All
of the aforementioned tensor parameters are lower bounded by the
subrank.999The analytic rank requires a natural normalization for this to be
true, that is, one should normalize it by the analytic rank of a full-
dimensional diagonal tensor. Our results provide a large separation on almost
all tensors between the subrank and all other aforementioned parameters, as
the generic subrank satisfies ${\rm Q}(n)=\theta(\sqrt{n})$ whereas the
generic value of all other parameters is the maximal value $n$.

The study of “generic” or “typical” complexity in algebraic complexity theory
goes back to at least Strassen’s paper “Rank and optimal computation of
generic tensors” [Str83], in which he determines the tensor rank of almost all
tensors (i.e. generic tensors). His result is that the rank ${\rm
R}(n_{1},n_{2},n_{3})$ of almost all tensors in $K^{n_{1},n_{2},n_{3}}$ grows
as $n_{1}n_{2}n_{3}/(n_{1}+n_{2}+n_{3}-2)$ and a description is given of
“perfect shapes” $(n_{1},n_{2},n_{3})$ for which precisely equality ${\rm
R}(n_{1},n_{2},n_{3})=n_{1}n_{2}n_{3}/(n_{1}+n_{2}+n_{3}-2)$ holds. (It is
still a fundamental open problem to find explicit tensors in $K^{n,n,n}$ with
rank close to $n^{2}$ [Blä14] with important implications to formula lower
bounds [Raz13].) For the shape $(n,n,3)$ with $n$ odd this work provides an
equation that determines whether a tensor has typical rank or not. These
equations lead to several later generalizations [LO13, Koi20] and subsequently
precise barrier results for “rank methods” [EGdOW18, GMdOW19]. Our result
rather than generic rank determines the generic subrank. The rank of a tensor
being the smallest number of scalar multiplications that the tensor reduces
to, the subrank is a natural dual to the tensor rank. We note that combining
the results on generic subrank and generic rank, we see that reducing scalar
multiplications to a generic tensor and reducing the generic tensor back to
scalar multiplications necessarily induces a great loss, as ${\rm
Q}(n,n,n)=\theta(\sqrt{n})$ is much smaller than ${\rm
R}(n,n,n)=\theta(n^{2})$.

The study of additivity results is a central theme in complexity theory and
mathematics. In algebraic complexity, it has been long known (and crucial in
the design of matrix multiplication algorithms) that the border rank of
tensors (the approximative version of tensor rank) is not additive under the
direct sum [Sch81] (see also [Blä13, Lemma 7.1] and [BCS97, (15.12)]).
Strassen conjectured the tensor rank to be additive under the direct sum, but
this was disproved recently by Shitov [Shi19]. On the other hand, the analytic
rank [Lov19], geometric rank [KMZ20], G-stable rank [Der20] and slice rank
[Gow21] were shown to be additive recently. The subrank, as we show, is
however not additive. Our proof of this relies on writing a tensor as a sum of
two generic tensors, which is reminiscent of methods that Razborov [Raz92]
uses to prove a linear upper bound on submodular complexity measures of
boolean functions (see also [RZ21]).

###  1.5 Paper Organization

In Section 2 we prove the upper bound theorems Theorem 1.2 and Theorem 1.5. In
Section 3 we prove the characterization of generic subrank that allows us to
reduce the problem of determining its value to the tensor subspace
decomposition problem. In Section 4 we solve the tensor subspace decomposition
problem thus completing the lower bound proof. In Section 5 we use our upper
bounds to prove that the subrank is not additive under direct sum. In Section
6 we discuss several natural related open problems.

##  2 Upper bounds on generic subrank

In this section, we prove our upper bounds on the generic subrank of tensors.
We give a detailed proof in the case of $3$-tensors, and then generalize to
tensors of all orders.

###  2.1 Tensors of order three

The techniques we use are familiar in invariant theory and representation
theory. The main idea is to take advantage of the fact that subrank is
invariant under a large group of symmetries, namely change of basis on each
tensor leg. Further, this group of symmetries has excellent algebraic
properties which can often be leveraged to remarkable effect.

First and foremost, we have to argue that generic subrank is a valid notion,
which we do in the following proposition. The proof is a standard argument
which we will discuss because it naturally uses some ingredients that we will
use later on.

######  Proposition 2.1.

For every $n$ there is a non-empty Zariski-open subset $U\subseteq K^{n,n,n}$
and integer $r$ such that for all $T\in U$ we have ${\rm Q}(T)=r$.

For any $n$, the number $r$ given by 2.1 is unique since any two non-empty
Zariski-open subsets $U_{1},U_{2}\subseteq K^{n,n,n}$ must intersect
($K^{n,n,n}$ is irreducible). This number $r$ we call the generic subrank
${\rm Q}(n)$. Similarly we define the generic subrank ${\rm
Q}(n_{1},\ldots,n_{k})$ of $K^{n_{1},\ldots,n_{k}}$.

We discuss a couple of preparatory results before giving the proof of 2.1. We
define $X_{r}$ to be the set of tensors in $K^{n,n,n}$ whose
$[r]\times[r]\times[r]$ subtensor is zero except for the diagonal entries in
$[r]\times[r]\times[r]$ which are all nonzero,

$X_{r}=\left\\{T\in K^{n,n,n}\ |\ T_{ijk}=0\text{ for
}(i,j,k)\in[r]^{3}\setminus\\{(i,i,i)\ |\ i\in[r]\\}\text{ and }T_{i,i,i}\neq
0\text{ for }i\in[r]\right\\}.$

We let $\psi_{r}$ be the map that applies basis transformations to elements of
$X_{r}$,

$\displaystyle\psi_{r}:\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times
X_{r}$ $\displaystyle\longrightarrow K^{n,n,n}$ $\displaystyle(A,B,C,T)$
$\displaystyle\longmapsto(A\otimes B\otimes C)T.$

We define $\mathcal{C}_{r}$ to be the set of tensors in $K^{n,n,n}$ whose
subrank is at least $r$,

$\mathcal{C}_{r}=\\{T\in K^{n,n,n}\ |\ {\rm Q}(T)\geq r\\}.$

######  Lemma 2.2.

The image of $\psi_{r}$ is precisely $\mathcal{C}_{r}$.

###### Proof.

To prove ${\rm im}(\psi_{r})=\mathcal{C}_{r}$ we show both inclusions.

First we will prove ${\rm im}(\psi_{r})\subseteq\mathcal{C}_{r}$. As a first
step we will prove that $X_{r}\subseteq\mathcal{C}_{r}$. Let $T\in X_{r}$. Let
$T_{i,i,i}=\lambda_{i}\neq 0$. Let

$A=\begin{pmatrix}{\rm Id}_{r}&0\\\ 0&0\end{pmatrix}$

where ${\rm Id}_{r}$ denotes the identity matrix of size $r\times r$ and let

$B=\begin{pmatrix}D&0\\\ 0&0\end{pmatrix}$

where $D$ is a diagonal matrix of size $r\times r$ whose diagonal entries are
$\lambda_{1}^{-1},\lambda_{2}^{-1},\dots,\lambda_{r}^{-1}$. It is easy to
check that $(A\otimes A\otimes B)\cdot T=I_{r}$. Thus
$X_{r}\subseteq\mathcal{C}_{r}$. Since subrank is invariant under the action
of
$\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}$,
we see that $\mathcal{C}_{r}$ is
$\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}$
invariant, so we deduce that ${\rm
im}(\psi_{r})=(\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n})\cdot
X_{r}\subseteq\mathcal{C}_{r}.$

Now we will prove $\mathcal{C}_{r}\subseteq{\rm im}(\psi_{r})$. Let
$T\in\mathcal{C}_{r}$. Then, there exist $A,B,C\in\operatorname{Mat}_{r,n}$
such that $(A\otimes B\otimes C)\cdot T=I_{r}$. Let

$\widetilde{A}=\begin{pmatrix}A\\\ \ast\end{pmatrix}$

be a completion of $A$ to a full rank $n\times n$ matrix, and similarly define
$\widetilde{B}$ and $\widetilde{C}$. This is possible because $A,B,C$ must all
have rank $r$. Then
$(\widetilde{A}\otimes\widetilde{B}\otimes\widetilde{C})\cdot T\in X_{r}$,
which implies that $T\in{\rm im}(\psi_{r})$. Thus
$\mathcal{C}_{r}\subseteq{\rm im}(\psi_{r})$ ∎

We now give the proof of the existence of the generic subrank (2.1). The proof
is standard and may safely be skipped.

###### Proof of 2.1.

The map ${\rm Q}$ attains only finitely many values on $V=K^{n,n,n}$, namely
$\\{0,1,\ldots,n\\}$. Thus it has finitely many fibers $P_{i}={\rm
Q}^{-1}(i)\subseteq V$. Each $P_{i}$ is a constructible set, since
$P_{i}=\mathcal{C}_{i}\setminus\mathcal{C}_{i+1}$ and $\mathcal{C}_{i}$ is
constructible as a consequence of 2.2. Then $\bigcup_{i=0}^{n}P_{i}=V$ and so
$\bigcup_{i=0}^{n}\overline{P_{i}}=V$. However, $V$ is irreducible so there
must be an $i$ such that $\overline{P_{i}}=V$. Since $P_{i}$ is constructible
it contains a subset $U\subseteq P_{i}$ that is non-empty and Zariski-open in
$\overline{P_{i}}=V$ (this is a general fact, see e.g. [Bor91]). This $U$ and
$i$ satisfy the claim. ∎

Now that we have established that the generic subrank exists, we continue to
prove our upper bound on it. The following simple lemma is straightforward,
but crucial:

######  Lemma 2.3.

The generic subrank ${\rm Q}(n)=\max\\{r\ |\ \dim(\mathcal{C}_{r})=n^{3}\\}$.

###### Proof.

As above, let $P_{i}$ denote the subset of tensors with subrank $i$. Then, by
definition of ${\rm Q}(n)$ and the fact that
$\mathcal{C}_{r}=\bigsqcup_{i=r}^{n}P_{i}$, we deduce that
$\dim(\mathcal{C}_{r})=n^{3}$ if and only if $\mathcal{C}_{r}\supseteq P_{{\rm
Q}(n)}$ if and only if $r\leq{\rm Q}(n)$. ∎

######  Proposition 2.4.

The following is an upper bound for the dimension of $\mathcal{C}_{r}$:

$\dim(\mathcal{C}_{r})\leq
3n^{2}+(n^{3}-r^{3}+r)-3(n(n-r)+r)=n^{3}-r(r^{2}-3n+2).$

###### Proof.

Consider the map $\psi$ above. The theorem on dimension of fibres says that

$\dim(\mathcal{C}_{r})=\dim(\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times
X_{r})-\dim(\text{general fiber of }\psi_{r}).$

We see that
$\dim(\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times\operatorname{GL}_{n}\times
X_{r})=3n^{2}+(n^{3}-r^{3}+r)$ because each $\operatorname{GL}_{n}$
contributes $n^{2}$ to the dimension and $X_{r}$ is a Zariski-open subset of a
linear subspace of $K^{n,n,n}$ of dimension $(n^{3}-r^{3}+r)$. Thus, to
compute $\dim(\mathcal{C}_{r})$, we only need to compute the dimension of the
general fiber of $\psi_{r}$. Note that the dimension of any fiber is at most
the dimension of the general fiber, so it suffices to find a lower bound on
the dimension of all fibers.

Suppose $T\in\mathcal{C}_{r}$, then $T=(g_{1}\otimes g_{2}\otimes g_{3})\cdot
S$ for some $S\in X_{r}$ by 2.2. It is easy to see that
$\dim(\psi^{-1}(T))=\dim(\psi^{-1}(S))$ since $\psi^{-1}(T)$ and
$\psi^{-1}(S)$ are isomorphic as varieties – indeed this follows from the
observation that
$(A,B,C,U)\in\psi^{-1}(T)\Longleftrightarrow(g_{1}^{-1}A,g_{2}^{-1}B,g_{3}^{-1}C,U)\in\psi^{-1}(S)$.
Thus, it suffices to lower bound the dimension of $\psi^{-1}(S)$ for $S\in
X_{r}$.

Let $S\in X_{r}$. Let $L\subseteq\operatorname{GL}_{m}$ be the subset of
matrices of the form

$\begin{pmatrix}D&0\\\ \ast&\ast\end{pmatrix}$

where $D$ is a diagonal matrix of size $r\times r$. It is easy to see that
$\dim(L)=n(n-r)+r$. For $A,B,C\in L$, it is easy to see that $(A\otimes
B\otimes C)\cdot S\in X_{r}$. Thus, $(A^{-1},B^{-1},C^{-1},(A\otimes B\otimes
C)\cdot S)\in\psi^{-1}(S)$. In particular, this means that
$\dim(\psi^{-1}(S))\geq 3\dim(L)=3(n(n-r)+r)$. Thus, we conclude that
$\dim(\text{generic fiber})\geq 3(n(n-r)+r)$ and so

$\dim(\mathcal{C}_{r})\leq
3n^{2}+(n^{3}-r^{3}+r)-3(n(n-r)+r)=n^{3}-r(r^{2}-3n+2).\qed$

Now, we have everything necessary to prove the upper bound for the subrank of
$3$-tensors.

###### Proof of Theorem 1.2.

Suppose the subrank of a generic tensor in $K^{n,n,n}$ is $t={\rm Q}(n)$. Then
we know that $n^{3}=\dim(\mathcal{C}_{t})$ by Lemma 2.3 and
$\dim(\mathcal{C}_{t})\leq n^{3}-t(t^{2}-3n+2)$ by Proposition 2.4. Thus, we
must have $t^{2}-3n+2\leq 0$, so $t\leq\sqrt{3n-2}$. Hence, we have ${\rm
Q}(n)\leq\sqrt{3n-2}$ as desired. ∎

###  2.2 Higher-order tensors

In the general case, where we look at tensors in
$K^{n_{1},n_{2},\dots,n_{k}}$, we define analogously the objects $X_{r}$ and
$\mathcal{C}_{r}$, the map
$\psi:\prod_{i=1}^{k}\operatorname{GL}_{n_{i}}\times
X_{r}\rightarrow\mathcal{C}_{r}$, etc.

###### Proof of Theorem 1.5.

We obtain analogously that

$\dim(\mathcal{C}_{r})=\Bigl{(}\sum_{i=1}^{k}n_{i}^{2}\Bigr{)}+\Bigl{(}\prod_{i=1}^{k}n_{i}-r^{k}+r\Bigr{)}-\sum_{i=1}^{k}(n_{i}(n_{i}-r)+r)=\prod_{i=1}^{k}n_{i}-r\Bigl{(}r^{k-1}-\sum_{i=1}^{k}n_{i}+(k-1)\Bigr{)}.$

Suppose the subrank of a generic tensor in $K^{n_{1},n_{2},\dots,n_{k}}$ is
$t={\rm Q}(n_{1},\ldots,n_{k})$. Then, we have

$\prod_{i=1}^{k}n_{i}=\dim(\mathcal{C}_{t})\leq\prod_{i=1}^{k}n_{i}-t\Bigl{(}t^{k-1}-\sum_{i=1}^{k}n_{i}+(k-1)\Bigr{)},$

so we get that $t^{k-1}-\sum_{i=1}^{k}n_{i}+(k-1)\leq 0$, so that

${\rm
Q}(n)=t\leq\Bigl{(}\sum_{\smash{i=1}}^{k}n_{i}-(k-1)\Bigr{)}^{\frac{1}{k-1}}$

as desired. ∎

##  3 Lower bounds on generic subrank

In this section, we describe the technique we use to show lower bounds on
generic subrank. In order to make this technique effective, we will need some
explicit constructions of linear subspaces which we postpone to the next
section.

First, we introduce some notation. We identify
$\operatorname{Mat}_{n_{2},n_{3}}$ with $K^{n_{2}}\otimes K^{n_{3}}$ in the
standard way. For a linear subspace
$\mathcal{X}\subseteq\operatorname{Mat}_{n_{2},n_{3}}$, we define a linear
subspace

$\mathcal{X}[1]=K^{n_{1}}\otimes\mathcal{X}\subseteq K^{n_{1},n_{2},n_{3}}.$

The linear subspace $\mathcal{X}[1]$ consists precisely of the tensors whose
slices in the first direction (i.e., matrices
$(T_{1jk})_{j,k},(T_{2jk})_{j,k},\dots,(T_{njk})_{j,k}$) are in $\mathcal{X}$.
Similarly, we define $\mathcal{X}[2]$ (resp. $\mathcal{X}[3]$) as the set of
tensors whose slices in the second (resp. third) direction are in
$\mathcal{X}$.

The main idea behind proving our lower bounds is the following result:

######  Theorem 3.1.

Let $r\leq n_{1},n_{2},n_{3}$ such that $n_{i}-r\leq r^{2}$.101010Without this
assumption it does not mean anything to have a generic subspace of dimension
$n_{i}-r$. Moreover, if $n_{i}-r>r^{2}$, then it is easy to see that ${\rm
Q}(n_{1},n_{2},n_{3})\geq r$. Let
$\mathcal{X}_{i}\subseteq\operatorname{Mat}_{r,r}$ be a generic subspace of
dimension $n_{i}-r$ for $i=1,2,3$. Suppose
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]=K^{r,r,r}$, then

${\rm Q}(n_{1},n_{2},n_{3})\geq r.$

In fact, we can prove a stronger version of the above theorem, which we state
as Theorem 3.9. However, the downside of this stronger version is that it has
a hypothesis that is more difficult to work with.

To prove that $r$ is a lower bound for the generic subrank, we need to show
that the image of $\psi_{r}$ has dimension $n^{3}$, that is, the image is
Zariski-dense in $K^{n,n,n}$. The dimension of the image of a map can be
captured by the rank of the differential at a generic point – an idea that is
familiar to differential geometers and algebraic geometers alike. In arbitrary
characteristic, we know that the rank of the differential at a generic point
is a lower bound for the dimension of the image, which is sufficient for
proving lower bounds. In characteristic $0$, the image of the rank of the
differential at a generic point is equal to the dimension of the image.
Consequently, we are able to obtain an exact linear algebraic characterization
for generic subrank in Theorem 3.9.

Recall that we defined the map

$\psi_{r}:\operatorname{GL}_{n_{1}}\times\operatorname{GL}_{n_{2}}\times\operatorname{GL}_{n_{3}}\times
X_{r}\rightarrow K^{n_{1},n_{2},n_{3}},$

where

$X_{r}=\left\\{T\in K^{n_{1},n_{2},n_{3}}\ |\ T_{ijk}=0\text{ for
}(i,j,k)\in[r]^{3}\setminus\\{(i,i,i)\ |\ i\in[r]\\}\text{ and }T_{i,i,i}\neq
0\text{ for }i\in[r]\right\\}.$

Observe that

$Y_{r}=\left\\{T\in K^{n_{1},n_{2},n_{3}}\ |\ T_{ijk}=0\text{ for
}(i,j,k)\in[r]^{3}\setminus\\{(i,i,i)\ |\ i\in[r]\\}\right\\}$

is the tangent space of $X_{r}$. The differential at a point
$(g_{1},g_{2},g_{3},T)$ is

$(d\psi_{r})_{(g_{1},g_{2},g_{3},T)}:\operatorname{Mat}_{n_{1},n_{1}}\times\operatorname{Mat}_{n_{2},n_{2}}\times\operatorname{Mat}_{n_{3},n_{3}}\times
Y_{r}\longrightarrow K^{n_{1},n_{2},n_{3}}$

given by

$(A,B,C,S)\longmapsto((A\otimes g_{2}\otimes g_{3})+(g_{1}\otimes B\otimes
g_{3})+(g_{1}\otimes g_{2}\otimes C))T+(g_{1}\otimes g_{2}\otimes g_{3})S.$

######  Lemma 3.2.

If for generic
$(g_{1},g_{2},g_{3},T)\in\operatorname{GL}_{n_{1}}\times\operatorname{GL}_{n_{2}}\times\operatorname{GL}_{n_{3}}\times
X_{r}$ we have

${\rm im}((d\psi_{r})_{(g_{1},g_{2},g_{3},T)})=K^{n_{1},n_{2},n_{3}},$

then ${\rm Q}(n_{1},n_{2},n_{3})\geq r$. The converse holds if the
characteristic of $K$ is $0$.

###### Proof.

If the rank of the differential $d\psi_{r}$ at a generic point is full, then
the image of $\psi_{r}$ must be full dimensional, that is, Zariski-dense (and
constructible). Every tensor in the image of $\psi_{r}$ has subrank $\geq r$.
Hence, the generic subrank must be at least $r$.

Assume now that characteristic of $K$ is zero. If the rank of $d\psi_{r}$ at a
generic point is not full, then the image of $\psi_{r}$ is not full
dimensional, that is, the set of tensors having subrank $\geq r$ is not
Zariski-dense, so we get ${\rm Q}(n_{1},n_{2},n_{3})<r$, thereby proving the
converse. ∎

We use the following equivariance property of the differential.

######  Lemma 3.3.

We have for all $g_{i}\in\operatorname{GL}_{n_{i}}$ and $T\in X_{r}$ that

${\rm im}((d\psi_{r})_{(g_{1},g_{2},g_{3},T)})=(g_{1}\otimes g_{2}\otimes
g_{3})({\rm im}((d\psi_{r})_{(I,I,I,T)}).$

###### Proof.

We see directly that

$(d\psi_{r})_{(g_{1},g_{2},g_{3},T)}(A,B,C,S)=(g_{1}\otimes g_{2}\otimes
g_{3})(d\psi_{r})_{(I,I,I,T)}(g_{1}^{-1}A,g_{2}^{-1}B,g_{3}^{-1}C,S)$

which implies the claim. ∎

######  Corollary 3.4.

If for generic $T\in X_{r}$ we have ${\rm
im}((d\psi_{r})_{(I,I,I,T)})=K^{n_{1},n_{2},n_{3}}$, then we have that ${\rm
Q}(n_{1},n_{2},n_{3})\geq r$. The converse holds if the characteristic of $K$
is $0$.

So, let us now analyze more carefully the image of $(d\psi_{r})_{(I,I,I,T)}$
for a generic tensor $T$. Below, we write $d$ for $(d\psi_{r})_{(I,I,I,T)}$
for notational simplicity. Thus $d$ is given by

$d(A,B,C,S)=((A\otimes I\otimes I)+(I\otimes B\otimes I)+(I\otimes I\otimes
C))\cdot T+S.$

The map $d$ is a linear map, so we see that

${\rm im}\ d=\sum_{i=1}^{3}d(\operatorname{Mat}_{n_{i},n_{i}})+d(Y_{r})$

where we use the notation $d(Y_{r})=d(0,0,0,Y_{r})$,
$d(\operatorname{Mat}_{n_{1},n_{1}})=d(\operatorname{Mat}_{n_{1},n_{1}},0,0,0)$,
etc.

######  Lemma 3.5.

The image of $Y_{r}$ under the differential map $d$ is

$d(Y_{r})=Y_{r}$

###### Proof.

Observe that for any $S\in Y_{r}$, we have $d(0,0,0,S)=S$. ∎

Let $L_{i}=[T_{ijk}]_{j,k}$ for $1\leq i\leq n_{1}$. These just split the
tensor in the first direction as a stack of $n$ matrices. Let $\mathcal{L}$
denote the span of the $L_{i}$s.

######  Lemma 3.6.

The image of $\operatorname{Mat}_{n_{1},n_{1}}$ under the differential $d$ is

$d(\operatorname{Mat}_{n_{1},n_{1}})=\mathcal{L}[1].$ (3)

###### Proof.

For any $A\in\operatorname{Mat}_{n_{1},n_{1}}$, let
$T^{\prime}=d(A,0,0,0)=(A\otimes I\otimes I)\cdot T$. Consider the slices
$L_{i}=[T_{ijk}]_{j,k}$. Then, it is straighforward to compute that for $1\leq
i\leq n_{1}$, the slice

$[T^{\prime}_{ijk}]_{j,k}=\sum_{t=1}^{n_{1}}a_{it}L_{i}.\qed$

Similar to $L_{i}$, define the slices in the other directions as
$M_{j}=[T_{ijk}]_{i,k}$ and $N_{k}=[T_{ijk}]_{i,j}$. Let $\mathcal{M}$ and
$\mathcal{N}$ denote the spans of the $M_{j}$s and $N_{k}$s respectively.

######  Corollary 3.7.

The image of the differential $d$ is

${\rm im}\ d=\mathcal{L}[1]+\mathcal{M}[2]+\mathcal{N}[3]+Y_{r}.$

###### Proof.

This follows from Lemma 3.6 (and its counterparts in the other two directions)
and Lemma 3.5. ∎

Now, we refine the above corollary. Denote by $\widehat{L_{i}}$ the top-left
$r\times r$ submatrix of $L_{i}$. Then, let $\mathcal{\widehat{L}}={\rm
span}(\widehat{L_{1}},\widehat{L_{2}},\dots,\widehat{L_{n_{1}}})$. Similarly
define $\widehat{M_{j}},\widehat{N_{k}}$ and $\mathcal{\widehat{M}}$ and
$\mathcal{\widehat{N}}$.

######  Proposition 3.8.

The image of the differential $d$ is

${\rm im}\
d=\mathcal{\widehat{L}}[1]+\mathcal{\widehat{M}}[2]+\mathcal{\widehat{N}}[3]+Y_{r}.$

###### Proof.

This follows directly from Corollary 3.7 and the definition of the coordinate
subspace $Y_{r}$. ∎

Now, we can finally prove Theorem 3.1.

###### Proof of Theorem 3.1.

Let $T\in X_{r}$ be generic. Define $L_{i},M_{i},N_{i}$ as above. Let

$\mathcal{X}_{1}={\rm
span}(\widehat{L_{r+1}},\widehat{L_{r+2}},\dots,\widehat{L_{n_{1}}}).$

Then $\mathcal{X}_{1}$ is a generic subspace of $\operatorname{Mat}_{r,r}$ of
dimension $n_{1}-r$. We similarly define

$\displaystyle\mathcal{X}_{2}$ $\displaystyle={\rm
span}(\widehat{M_{r+1}},\widehat{M_{r+2}},\dots,\widehat{M_{n_{2}}})$
$\displaystyle\mathcal{X}_{3}$ $\displaystyle={\rm
span}(\widehat{N_{r+1}},\widehat{N_{r+2}},\dots,\widehat{N_{n_{3}}}).$

By hypothesis,
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]=K^{r,r,r}$. Hence,
by Proposition 3.8, we see that

${\rm
im}(d)=\mathcal{\widehat{L}}[1]+\mathcal{\widehat{M}}[2]+\mathcal{\widehat{N}}[3]+Y_{r}\supseteq\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+Y_{r}=K^{r,r,r}+Y_{r}=K^{n_{1},n_{2},n_{3}}.$

Thus, we get that ${\rm Q}(n_{1},n_{2},n_{3})\geq r$ by Corollary 3.4. ∎

We observe that the idea from the proof of Theorem 3.1 actually yields the
stronger version below. To state this we define the linear subspace

$W_{r}=\\{T\in K^{r,r,r}\ |\ T_{ijk}=0\text{ if $i,j,k$ are all
different}\\}\subseteq K^{r,r,r}.$

######  Theorem 3.9.

Let $r\leq n_{1},n_{2},n_{3}$ such that $n_{i}=r<r^{2}$ for $i=1,2,3$. Let
$\mathcal{X}_{i}\subseteq\operatorname{Mat}_{r,r}$ be a generic subspace of
dimension $n_{i}-r$ for $i=1,2,3$. Suppose

$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}=K^{r,r,r},$

then ${\rm Q}(n_{1},n_{2},n_{3})\geq r$. Further, if characteristic of $K$ is
$0$, then we have the converse.

In other words, if characteristic of $K$ is $0$, then Theorem 3.9 says that
${\rm Q}(n_{1},n_{2},n_{3})$ is given by the smallest number $r$ such that
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}=K^{r,r,r}$ for
generic subspaces $\mathcal{X}_{i}\subseteq\operatorname{Mat}_{r,r}$ of
dimension $n_{i}-r$.

###### Proof.

The proof is similar to that of Theorem 3.1. Take a generic $T\in X_{r}$.
Define $L_{i},M_{i},N_{i}$ as above. Set $\mathcal{X}_{1}={\rm
span}(\widehat{L_{r+1}},\widehat{L_{r+2}},\dots,\widehat{L_{n_{1}}})$. Then
$\mathcal{X}_{1}$ is a generic subspace of $\operatorname{Mat}_{r,r}$ of
dimension $n_{1}-r$. Let $P_{1}={\rm
span}(\widehat{L_{1}},\widehat{L_{2}},\dots,\widehat{L_{r}})$. Similarly
define $\mathcal{X}_{2}={\rm
span}(\widehat{M_{r+1}},\widehat{M_{r+2}},\dots,\widehat{M_{n_{2}}})$ and
$\mathcal{X}_{3}={\rm
span}(\widehat{N_{r+1}},\widehat{N_{r+2}},\dots,\widehat{N_{n_{3}}})$ and also
$P_{2}={\rm span}(\widehat{M_{1}},\dots,\widehat{M_{r}})$ and $P_{3}={\rm
span}(\widehat{N_{1}},\dots,\widehat{N_{r}})$.

It is a straightforward computation to see that since $T$ is generic in
$X_{r}$, we have $P_{1}[1]+P_{2}[2]+P_{3}[3]=W_{r}$. Hence, using Proposition
3.8, we see that

$\displaystyle{\rm im}(d)$
$\displaystyle=\mathcal{\widehat{L}}[1]+\mathcal{\widehat{M}}[2]+\mathcal{\widehat{N}}[3]+Y_{r}$
$\displaystyle=\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+P_{1}[1]+P_{2}[2]+P_{3}[3]+Y_{r}$
$\displaystyle=\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}+Y_{r}$

Now, we claim that

$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}=K^{r,r,r}\Leftrightarrow\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}+Y_{r}=K^{n_{1},n_{2},n_{3}}.$

The proof of the claim is rather straightforward, the only subtle point being
that $Y_{r}$ and $K^{r,r,r}$ have an intersection (i.e., the main diagonal of
$K^{r,r,r}$), but this intersection is included in $W_{r}$ anyway, so the
claim goes through.

Thus, we get that ${\rm im}(d)=K^{n_{1},n_{2},n_{3}}$ if and only if
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}=K^{r,r,r}$.
Now, the theorem follows from applying Corollary 3.4. ∎

In the next section we will prove that the requirement of Theorem 3.1 is
satisfied. This goes as follows. We will show (4.2) that:

######  Lemma 3.10.

Let $\mathcal{X}_{i}\subseteq\operatorname{Mat}_{3,3}$ be a generic subspace
of dimension 3 for $i=1,2,3$. Then
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]=K^{3,3,3}$.

Then from a blow-up argument we obtain:

######  Lemma 3.11.

Let $\mathcal{X}_{i}\subseteq\operatorname{Mat}_{3d,3d}$ be a generic subspace
of dimension $3d^{2}$ for $i=1,2,3$. Then
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]=K^{3d,3d,3d}$.

###### Proof.

It is enough to construct one such choice of $\mathcal{X}_{i}$. By 3.10 there
exist subspaces $\mathcal{Y}_{i}\subseteq\operatorname{Mat}_{3,3}$ of
dimension 3 such that
$\mathcal{Y}_{1}[1]+\mathcal{Y}_{2}[2]+\mathcal{Y}_{3}[3]=K^{3,3,3}$. Then
$\mathcal{X}_{i}=\mathcal{Y}_{i}\otimes\operatorname{Mat}_{d,d}$ satisfy the
claim. ∎

######  Theorem 3.12.

Let $d$ be a positive integer such that $n-3d\geq 3d^{2}$. Then ${\rm
Q}(n,n,n)\geq 3d$.

###### Proof.

Taking $r=3d$, this follows from Theorem 3.1 and 3.11. ∎

###### Proof of Theorem 1.3.

If we take $d=\lfloor\sqrt{n/3+1/4}-1/2\rfloor$, then we have
$d\leq\sqrt{n/3+1/4}-1/2$, so $(d+1/2)^{2}\leq n/3+1/4$. Thus,
$d^{2}+d+1/4\leq n/3+1/4$, so $d^{2}+d\leq n/3$ or equivalently $3d^{2}\leq
n-3d$. Thus, it follows from Theorem 3.12 that ${\rm Q}(n)\geq 3d.$ ∎

For the higher-order lower bound Theorem 1.6 we prove (4.3) the analogous
higher-order version of 3.10 which we can similarly blow up and apply Theorem
3.1 to.

##  4 Constructions of tensor space decompositions

We assume that the base field $K$ is infinite.

Let ${\mathcal{C}}$ be the set of all matrices
$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}$ for which $n_{1},n_{2},\dots,n_{d}$ are
positive integers, $a_{1},a_{2},\dots,a_{d}$ are nonnegative integers and
$\sum_{i=1}^{d}a_{i}n_{i}=\prod_{i=1}^{d}n_{i}$. Let ${\mathcal{S}}$ be the
subset of all $\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}\in{{\mathcal{C}}}$ with the following
property: If $V_{1},V_{2},\dots,V_{d}$ are vector spaces of dimensions
$n_{1},n_{2},\dots,n_{d}$ respectively, and $W_{i}$ is a general subspace of
$\widehat{V}_{i}:=V_{1}\otimes V_{2}\otimes\cdots\otimes V_{i-1}\otimes
V_{i+1}\otimes\cdots\otimes V_{d}$ of dimension $a_{i}$ for all $i$, then
$\sum_{i=1}^{d}\Phi_{i}(W_{i}\otimes V_{i})=V_{1}\otimes\cdots\otimes V_{d}$,
where $\Phi:\widehat{V}_{i}\otimes V_{i}\to V_{1}\otimes
V_{2}\otimes\cdots\otimes V_{d}$ is the isomorphism given by permuting the
factors.

###  4.1 General construction methods

We will use the following simple facts. It is obvious that if a matrix lies in
${\mathcal{S}}$ and we permute its columns, then it will still lie in
${\mathcal{S}}$. It is also clear that
$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}$ lies in ${\mathcal{S}}$ if and only if
$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}&1\\\
a_{1}&a_{2}&\cdots&a_{d}&0\end{bmatrix}$ lies in ${\mathcal{S}}$. The vector
$\begin{bmatrix}n\\\ 1\end{bmatrix}$ lies in ${\mathcal{S}}$ for all positive
integers $n$. Finally,

$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}&1&1\\\
a_{1}&a_{2}&\cdots&a_{d}&b_{1}&b_{2}\end{bmatrix}\in{\mathcal{S}}\textnormal{\quad
if and only if \quad}\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}&1\\\
a_{1}&a_{2}&\cdots&a_{d}&b_{1}+b_{2}\end{bmatrix}\in{\mathcal{S}}$ (4)

######  Lemma 4.1 (Direct sum construction).

Suppose that $n_{d}=n_{d}^{\prime}+n_{d}^{\prime\prime}$, and
$a_{i}=a_{i}^{\prime}+a_{i}^{\prime\prime}$ for $i=1,2,\dots,d-1$, and

$\begin{bmatrix}n_{1}&n_{2}&\dots&n_{d-1}&n_{d}^{\prime}\\\
a_{1}^{\prime}&a_{2}^{\prime}&\cdots&a_{d-1}^{\prime}&a_{d}\end{bmatrix},\begin{bmatrix}n_{1}&n_{2}&\dots&n_{d-1}&n_{d}^{\prime\prime}\\\
a_{1}^{\prime\prime}&a_{2}^{\prime\prime}&\cdots&a_{d-1}^{\prime\prime}&a_{d}\end{bmatrix}\in{\mathcal{S}}.$

Then we have $\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}\in{\mathcal{S}}$.

###### Proof.

Suppose $V_{1},V_{2},\dots,V_{d}$ are vector spaces of dimensions
$n_{1},n_{2},\dots,n_{d}$ respectively and choose a general subspace $W_{d}$
of $V_{d}$ of dimension $a_{d}$. We can write $V_{d}=V_{d}^{\prime}\oplus
V_{d}^{\prime\prime}$ where $V_{d}^{\prime}$ and $V_{d}^{\prime\prime}$ have
dimensions $n_{d}^{\prime}$ and $n_{d}^{\prime\prime}$ respectively. For
$i=1,2,\dots,d-1$ choose a general subspace $W_{i}^{\prime}\subseteq
V_{1}\otimes\cdots\otimes V_{i-1}\otimes V_{i+1}\otimes\cdots\otimes
V_{d-1}\otimes V_{d}^{\prime}$ of dimension $a_{i}^{\prime}$ such that
$V_{1}\otimes V_{2}\otimes\cdots\otimes V_{d-1}\otimes V_{d}^{\prime}$ is
equal to $\big{(}\sum_{i=1}^{d-1}\Phi_{i}(W_{i}^{\prime}\otimes
V_{i})\big{)}+W_{d}\otimes V_{d}^{\prime}$. Similarly, for $i=1,2,\dots,d-1$,
choose a general subspace $W_{i}^{\prime\prime}\subseteq
V_{1}\otimes\cdots\otimes V_{i-1}\otimes V_{i+1}\otimes\cdots\otimes
V_{d-1}\otimes V_{d}^{\prime\prime}$ of dimension $a_{i}^{\prime\prime}$ such
that $V_{1}\otimes V_{2}\otimes\cdots\otimes V_{d-1}\otimes
V_{d}^{\prime\prime}$ is equal to
$\big{(}\sum_{i=1}^{d-1}\Phi_{i}(W_{i}^{\prime\prime}\otimes{V_{i}})\big{)}+W_{d}\otimes
V_{d}^{\prime\prime}$. Set $W_{i}=W_{i}^{\prime}\oplus
W_{i}^{\prime\prime}\subseteq V_{1}\otimes\cdots\otimes V_{i-1}\otimes
V_{i+1}\otimes\cdots\otimes V_{d}$ for $i=1,2,\dots,d-1$. Then we have

$\sum_{i=1}^{d}\Phi_{i}(W_{i}\otimes
V_{i})=\Big{(}\sum_{i=1}^{d-1}\Phi_{i}((W_{i}^{\prime}\oplus
W_{i}^{\prime\prime})\otimes V_{i})\Big{)}+W_{d}\otimes(V_{d}^{\prime}\oplus
V_{d}^{\prime\prime})=\\\
\left(\Big{(}\sum_{i=1}^{d-1}\Phi_{i}(W_{i}^{\prime}\otimes
V_{i})\Big{)}+W_{d}\otimes
V_{d}^{\prime}\right)\oplus\left(\Big{(}\sum_{i=1}^{d-1}\Phi_{i}(W_{i}^{\prime\prime}\otimes
V_{i})\Big{)}+W_{d}\otimes V_{d}^{\prime\prime}\right)=\\\
(V_{1}\otimes\cdots\otimes V_{d-1}\otimes
V_{d}^{\prime})\oplus(V_{1}\otimes\cdots\otimes V_{d-1}\otimes
V_{d}^{\prime\prime})=V_{1}\otimes V_{2}\otimes\cdots\otimes V_{d}.$

This finishes the proof. ∎

###  4.2 Recursive construction for every order

The following lemma gives 3.10 which we used in the proof of the generic
subrank lower bound for order three. After that we will recursively obtain
what is needed for the higher-order case generic subrank lower bound.

######  Lemma 4.2 (Base case).

We have $\begin{bmatrix}3&3&3\\\ 3&3&3\end{bmatrix}\in{\mathcal{S}}$.

###### Proof.

We can verify explicitly that $\begin{bmatrix}2&2&2\\\
0&3&1\end{bmatrix}\in{\mathcal{S}}$, as follows. For a $3$-dimensional
subspace $W_{1}$ of $V_{2}\otimes V_{3}=K^{2\times 2}$, take the space of all
matrices of the form

$\begin{pmatrix}a&b\\\ b&c\end{pmatrix}$

and for the $1$-dimensional subspace $W_{3}$ of $V_{1}\otimes V_{2}=K^{2\times
2}$, take the span of the identity matrix. A tensor in the intersection of
$W_{1}\otimes V_{3}\cap V_{1}\otimes W_{3}\subseteq V_{1}\otimes V_{2}\otimes
V_{3}$ is of the form

$\left(\begin{array}[]{cc|cc}a_{1}&b_{1}&a_{2}&b_{2}\\\
b_{1}&c_{1}&b_{2}&c_{2}\end{array}\right)=\left(\begin{array}[]{cc|cc}p_{1}&0&0&p_{1}\\\
p_{2}&0&0&p_{2}\end{array}\right)$

for some $a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},p_{1},p_{2}$. Clearly,
$b_{1}=c_{1}=a_{2}=b_{2}=0$. So we get $p_{1}=b_{2}=0$ and $p_{2}=b_{1}=0$. So
$W_{1}\otimes V_{3}\cap V_{1}\otimes W_{3}=0$ and $W_{1}\otimes
V_{3}+V_{1}\otimes W_{3}$ has dimension $3\cdot 2+2\cdot 1=8$ and therefore
must be equal to $V_{1}\otimes V_{2}\otimes V_{3}=K^{2\times 2\times 2}$.
Using 4.1, we now deduce:

  * •

$\begin{bmatrix}2&2&2\\\ 0&3&1\end{bmatrix},\begin{bmatrix}1&2&2\\\
0&0&2\end{bmatrix}\in{\mathcal{S}}$, so $\begin{bmatrix}3&2&2\\\
0&3&3\end{bmatrix}=\begin{bmatrix}2+1&2&2\\\
0&3+0&1+2\end{bmatrix}\in{\mathcal{S}}$

  * •

$\begin{bmatrix}3&1&1\\\ 1&0&0\end{bmatrix},\begin{bmatrix}3&1&1\\\
0&3&0\end{bmatrix}\in{\mathcal{S}}$, so $\begin{bmatrix}3&1&2\\\
1&3&0\end{bmatrix}=\begin{bmatrix}3&1&1+1\\\
1+0&0+3&0\end{bmatrix}\in{\mathcal{S}}$

  * •

$\begin{bmatrix}3&2&2\\\ 0&3&3\end{bmatrix},\begin{bmatrix}3&1&2\\\
1&3&0\end{bmatrix}\in{\mathcal{S}}$, so $\begin{bmatrix}3&3&2\\\
1&3&3\end{bmatrix}=\begin{bmatrix}3&2+1&2\\\
0+1&3&3+0\end{bmatrix}\in{\mathcal{S}}$

  * •

$\begin{bmatrix}3&1&1\\\ 1&0&0\end{bmatrix},\begin{bmatrix}3&1&1\\\
0&0&3\end{bmatrix}\in{\mathcal{S}}$, so $\begin{bmatrix}3&3&1\\\
2&0&3\end{bmatrix}=\begin{bmatrix}3&1+1+1&1\\\
1+1+0&0&0+0+3\end{bmatrix}\in{\mathcal{S}}$

  * •

$\begin{bmatrix}3&3&1\\\ 2&0&3\end{bmatrix},\begin{bmatrix}3&3&2\\\
1&3&3\end{bmatrix}\in{\mathcal{S}}$, so $\begin{bmatrix}3&3&3\\\
3&3&3\end{bmatrix}=\begin{bmatrix}3&3&1+2\\\
2+1&0+3&3\end{bmatrix}\in{\mathcal{S}}$

The final line finishes the proof. ∎

To continue, we define the “concatenation” notation:

$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}\odot\begin{bmatrix}m_{1}&m_{2}&\cdots&m_{e}\\\
b_{1}&b_{2}&\cdots&b_{e}\end{bmatrix}=\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}&m_{1}&m_{2}&\cdots&m_{e}\\\
a_{1}&a_{2}&\cdots&a_{d}&b_{1}&b_{2}&\cdots&b_{e}\end{bmatrix}$

and the $k$-fold repeated version of this notation:

$\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}^{\odot
k}=\underbrace{\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}\odot\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}\odot\cdots\odot\begin{bmatrix}n_{1}&n_{2}&\cdots&n_{d}\\\
a_{1}&a_{2}&\cdots&a_{d}\end{bmatrix}}_{k}.$

We will now use 4.1 and 4.2 to prove:

######  Lemma 4.3.

For all $n\geq 3$, we have $\begin{bmatrix}n\\\ n^{n-2}\end{bmatrix}^{\odot
n}\in{\mathcal{S}}$.

###### Proof.

We already know the case $n=3$ (4.2), so assume that $n\geq 4$.

We will first show that $\begin{bmatrix}n\\\ n\end{bmatrix}^{\odot
3}\odot\begin{bmatrix}1\\\ n^{2}\end{bmatrix}^{\odot(n-3)}\in{\mathcal{S}}$.
We note that a straightforward direct construction gives

$\begin{bmatrix}n&n&1\\\ k&0&n^{2}-kn\end{bmatrix}\in{\mathcal{S}}$

for $k=1,2,3$. To proceed, we choose nonnegative integers
$a_{1},a_{2},\dots,a_{n},b_{1},b_{2},\dots,b_{n}\in\\{0,1,2,3\\}$ such that
$a_{1}+a_{2}+\cdots+a_{n}=n$, $b_{1}+b_{2}+\cdots+b_{n}=n$ and $a_{i}b_{i}=0$
for all $i$. Indeed this can be done as follows: If $n=2m$ is even, then we
can take $a_{1}=a_{2}=\cdots=a_{m}=b_{m+1}=b_{m+2}=\cdots=b_{n}=2$ and
$b_{1}=b_{2}=\cdots=b_{m}=a_{m+1}=a_{m+2}=\cdots=a_{n}=0$. If $n=2m+1$ is odd,
then we take $a_{1}=3$, $b_{m+1}=1$,
$a_{2}=a_{3}=\cdots=a_{m}=b_{m+2}=b_{m+3}=\cdots=b_{n}=2$ and
$b_{1}=b_{2}=\cdots=b_{m}=a_{m+1}=a_{m+2}=\cdots=a_{n}=0$. Because
$a_{i}b_{i}=0$ we get that

$\begin{bmatrix}n&n&1\\\
a_{i}&b_{i}&n^{2}-(a_{i}+b_{i})n\end{bmatrix}\in{\mathcal{S}}$

and then using (4) we get

$\begin{bmatrix}n&n&1&1\\\
a_{i}&b_{i}&n&n^{2}-(a_{i}+b_{i}+1)n\end{bmatrix}\in{\mathcal{S}}$ (5)

for $i=1,2,\dots,n$. Applying the direct sum construction 4.1 to the elements
of (5) we get

$\begin{bmatrix}n&n&n&1\\\
n&n&n&n^{3}-3n^{2}\end{bmatrix}=\begin{bmatrix}n&n&1+\cdots+1&1\\\
\sum_{i}a_{i}&\sum_{i}b_{i}&n&\sum_{i}n^{2}-(a_{i}+b_{i}+1)n\end{bmatrix}\in{\mathcal{S}}.$

Applying (4) repeatedly to this we obtain $\begin{bmatrix}n\\\
n\end{bmatrix}^{\odot 3}\odot\begin{bmatrix}1\\\
n^{2}\end{bmatrix}^{\odot(n-3)}\in{\mathcal{S}}$.

We will now show by induction on $d$ that

$\begin{bmatrix}n\\\ n^{d-2}\end{bmatrix}^{\odot d}\odot\begin{bmatrix}1\\\
n^{d-1}\end{bmatrix}^{\odot(n-d)}\in{\mathcal{S}}$ (6)

for $d=3,4,\dots,n$. We already know that the base case $d=3$ is true. Suppose
for the induction step that $\begin{bmatrix}n\\\ n^{d-2}\end{bmatrix}^{\odot
d}\odot\begin{bmatrix}1\\\ n^{d-1}\end{bmatrix}^{\odot(n-d)}\in{\mathcal{S}}.$
Then we have using (4) that

$\begin{bmatrix}n\\\ n^{d-1}\end{bmatrix}^{\odot(d+1)}\odot\begin{bmatrix}1\\\
n^{d}\end{bmatrix}^{\odot(n-d-1)}=\begin{bmatrix}n\\\
n^{d-2}+\cdots+n^{d-2}\end{bmatrix}^{\odot
d}\odot\begin{bmatrix}1+1+\cdots+1\\\
n^{d-1}\end{bmatrix}\odot\begin{bmatrix}1\\\
n^{d-1}+\cdots+n^{d-1}\end{bmatrix}^{\odot(n-d)-1}\in{\mathcal{S}}.$

This proves (6).

Finally, by setting $d=n$ in (6) we obtain the claim $\begin{bmatrix}n\\\
n^{n-2}\end{bmatrix}^{\odot n}\in{\mathcal{S}}$. ∎

##  5 Application: Subrank is not additive

We discuss in this section an application of our upper bound Theorem 1.2 on
the generic subrank, namely that the subrank is not additive under the direct
sum. That is, there are tensors $S,T$ such that ${\rm Q}(T)+{\rm Q}(S)<{\rm
Q}(T\oplus S)$. In fact, we obtain a large gap between ${\rm Q}(T)+{\rm Q}(S)$
and ${\rm Q}(T\oplus S)$. The proof relies on the idea of writing the diagonal
tensor $I_{n}$ as a sum of two generic tensors and on basic properties of the
subrank.111111This idea was used earlier in [Bü90] to show that the “lower
support functionals” [Str91] are not additive. Their results can be used to
find a weaker non-additivity for subrank (with a smaller gap, and only for
tensors of order three), namely that there are tensors $S,T\in K^{n,n,n}$ such
that ${\rm Q}(T),{\rm Q}(S)\leq n^{2/3+o(1)}$ and ${\rm Q}(T\oplus S)\geq n$.

######  Theorem 5.1.

There are tensors $S,T\in K^{n,n,n}$ such that we have ${\rm Q}(T),{\rm
Q}(S)\leq\sqrt{3n-2}$ and ${\rm Q}(T\oplus S)\geq n$.

###### Proof.

By Theorem 1.2 there is a non-empty Zariski-open subset $U\subseteq K^{n,n,n}$
such that for all $T\in U$ we have ${\rm Q}(T)\leq\sqrt{3n-2}$. Recall that
$I_{n}\in K^{n,n,n}$ is the tensor with ones in the diagonal entries and
zeroes elsewhere. The subset $I_{n}-U\subseteq K^{n,n,n}$ is also non-empty
and Zariski-open, and thus the intersection $U\cap(I_{n}-U)$ is non-empty.
This means that there is a $T\in U$ such that $I_{n}-T$ is in $U$. Fix this
$T$ and let $S=I_{n}-T$. Then ${\rm Q}(T),{\rm Q}(S)\leq\sqrt{3n-2}$. For
their direct sum, we observe the simple general fact that $T\oplus S\geq T+S$
where the left-hand side is the direct sum and the right-hand side is the
coordinate-wise sum. Since subrank is monotone under $\geq$ we find that ${\rm
Q}(T\oplus S)\geq{\rm Q}(T+S)={\rm Q}(I_{n})=n$. ∎

The proof of Theorem 5.1 extends directly so that similarly from Theorem 1.5
we get the following higher-order non-additivity result.

######  Theorem 5.2.

There are $k$-tensors $S,T\in K^{n,\ldots,n}$ such that ${\rm Q}(T),{\rm
Q}(S)\leq(kn-(k-1))^{\frac{1}{k-1}}$ while ${\rm Q}(T\oplus S)\geq n$.

##  6 Open problems

There are several natural open problems that arise from or are closely related
to our study and results on the generic subrank in this paper. We briefly list
some of these problems here.

  * •

While we determine the generic subrank very precisely up to a small additive
constant, it is natural to ask whether our upper bound on the generic subrank
${\rm Q}(n)$ is exactly tight. We know that this is the case for all small
cases ($n\leq 100$).

  * •

Closely related to the above, but for higher-order and unbalanced formats,
what is the exact value of the generic subrank ${\rm Q}(n_{1},\ldots,n_{k})$
in $K^{n_{1},\ldots,n_{k}}$ when the dimensions $n_{i}$ are not all equal? In
particular, is our upper bound tight?

  * •

To attack the previous two problems the natural approach would be to use the
stronger Theorem 3.9. Our current lower bound on the generic subrank uses
Theorem 3.1 which relies on our constructions of decompositions
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]=K^{r,r,r}$. Theorem
3.9 suggests to instead construct decompositions
$\mathcal{X}_{1}[1]+\mathcal{X}_{2}[2]+\mathcal{X}_{3}[3]+W_{r}=K^{r,r,r}$.
What are the “best” constructions that can be obtained of this form?

  * •

There is a natural approximative version of subrank called _border_
subrank121212The difference with subrank is that the restriction preorder is
replaced by the _degeneration_ preorder, which results in the border subrank
${\underline{\rm Q}}(T)$ of $T$ being the largest number $r$ such that $I_{r}$
is in the $\operatorname{GL}_{n}^{\times 3}$-orbit closure of $T$. which plays
a central role in algebraic complexity theory (in particular the study of
matrix multiplication algorithms). The border subrank is at least the subrank.
What value does the border subrank take on generic tensors?

  * •

What is the value of the generic asymptotic subrank
$\operatorname{\underaccent{\wtilde}{Q}}(n)$? The state of the art is that
$n^{2/3}\leq\operatorname{\underaccent{\wtilde}{Q}}(n)\leq n$, so in
particular it remains open whether generic tensors have “full” generic
asymptotic subrank or not. We note that we do know of explicit tensors for
which the asymptotic subrank is not full (the so-called W-tensor, for example)
and also of explicit tensors for which the asymptotic subrank is full in a
non-trivial way (matrix multiplication tensors, for example). The
aforementioned lower bound of $n^{2/3}$ is by Strassen’s elegant construction
(which makes use of the matrix multiplication tensors). Our results show that
one cannot obtain better lower bound on
$\operatorname{\underaccent{\wtilde}{Q}}(n)$ by improving the lower bound on
the generic subrank ${\rm Q}(n)$ since ${\rm Q}(n)=\theta(\sqrt{n})$.

  * •

With the notation we introduced in Section 4 on constructions of tensor space
decompositions, it is natural to ask what precisely are the elements of
$\mathcal{S}$. Many elements can be constructed from simple base cases and the
direct sum construction. However, we do not know whether a finite number of
generators in this sense suffices to generate all of $\mathcal{S}$.

  * •

We found tensors $S,T$ for which there is a large gap between ${\rm Q}(S\oplus
T)$ and ${\rm Q}(S)+{\rm Q}(T)$. Is this the largest possible gap? More
speculatively, we may ask: is there a general relation between direct sum
problems (i.e. additivity under direct sum) and parameter values at generic
instances?

#### Acknowledgements.

The authors thank Swastik Kopparty for helpful discussions, and JM Landsberg
and Jan Draisma for comments. HD was partially supported by NSF grants
IIS-1837985 and DMS-2001460. VM was partially supported by NSF grants
CCF-1900460 and the University of Melbourne. JZ was partially supported by a
Simons Junior Fellowship and NWO Veni grant VI.Veni.212.284.

## References

  * [Alm19] Josh Alman.  Limits on the universal method for matrix multiplication.  In 34th Computational Complexity Conference (CCC 2019), pages 12:1–12:24, 2019.  doi:10.4230/LIPIcs.CCC.2019.12.
  * [BCC+17] Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans.  On cap sets and the group-theoretic approach to matrix multiplication.  Discrete Anal., pages Paper No. 3, 27, 2017.  arXiv:1605.06702, doi:10.19086/da.1245.
  * [BCS97] Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi.  Algebraic complexity theory, volume 315 of Grundlehren Math. Wiss. Springer-Verlag, Berlin, 1997.  doi:10.1007/978-3-662-03338-8.
  * [BHH+20] Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar.  On multilinear forms: Bias, correlation, and tensor rank.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), pages 29:1–29:23, 2020.  arXiv:1804.09124, doi:10.4230/LIPIcs.APPROX/RANDOM.2020.29.
  * [BL15] Abhishek Bhowmick and Shachar Lovett.  Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory, 2015.  arXiv:1506.02047.
  * [Blä13] Markus Bläser.  Fast Matrix Multiplication.  Number 5 in Graduate Surveys. Theory of Computing Library, 2013.  doi:10.4086/toc.gs.2013.005.
  * [Blä14] Markus Bläser.  Explicit tensors.  In Perspectives in computational complexity, pages 117–130. Springer, 2014.
  * [Bor91] Armand Borel.  Linear algebraic groups, volume 126 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 1991.  doi:10.1007/978-1-4612-0941-6.
  * [Bü90] Peter Bürgisser.  Degenerationsordnung und Trägerfunktional bilinearer Abbildungen.  PhD thesis, Universität Konstanz, 1990.  http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-20311.
  * [CM21a] Alex Cohen and Guy Moshkovitz.  Structure vs. randomness for bilinear maps.  In 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), 2021.  doi:10.1145/3406325.3451007.
  * [CM21b] Alex Cohen and Guy Moshkovitz.  Partition rank and analytic rank are uniformly equivalent, 2021.  arXiv:2102.10509.
  * [CVZ18] Matthias Christandl, Péter Vrana, and Jeroen Zuiddam.  Universal points in the asymptotic spectrum of tensors (extended abstract).  In Proceedings of the 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2018), 2018.  arXiv:1709.07851, doi:10.1145/3188745.3188766.
  * [CVZ19] Matthias Christandl, Péter Vrana, and Jeroen Zuiddam.  Barriers for fast matrix multiplication from irreversibility.  In 34th Computational Complexity Conference (CCC 2019), pages 26:1–26:17, 2019.  doi:10.4230/LIPIcs.CCC.2019.26.
  * [Der20] Harm Derksen.  The G-stable rank for tensors, 2020.  arXiv:2002.08435.
  * [EG17] Jordan S. Ellenberg and Dion Gijswijt.  On large subsets of $\mathbf{F}^{n}_{q}$ with no three-term arithmetic progression.  Ann. of Math. (2), 185(1):339–343, 2017.  doi:10.4007/annals.2017.185.1.8.
  * [EGdOW18] Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, and Avi Wigderson.  Barriers for rank methods in arithmetic complexity.  In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pages 1:1–1:19, 2018.  arXiv:1710.09502, doi:10.4230/LIPIcs.ITCS.2018.1.
  * [GL21] Runshi Geng and J. M. Landsberg.  On the geometry of geometric rank, 2021.  arXiv:2012.04679.
  * [GMdOW19] Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, and Avi Wigderson.  More barriers for rank methods, via a “numeric to symbolic” transfer.  In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 824–844, 2019.  doi:10.1109/FOCS.2019.00054.
  * [Gow21] W. T. Gowers.  The slice rank of a direct sum, 2021.  arXiv:2105.08394.
  * [GT09] Ben Joseph Green and Terence Tao.  The distribution of polynomials over finite fields, with applications to the gowers norms.  Contributions Discret. Math., 4(2), 2009.  URL: http://cdm.ucalgary.ca/cdm/index.php/cdm/article/view/133.
  * [GW11] W. T. Gowers and J. Wolf.  Linear forms and higher-degree uniformity for functions on $\mathbf{F}^{n}_{p}$.  Geom. Funct. Anal., 21(1):36–69, 2011.  doi:10.1007/s00039-010-0106-3.
  * [Jan18] Oliver Janzer.  Low analytic rank implies low partition rank for tensors, 2018.  arXiv:1809.10931.
  * [Jan20] Oliver Janzer.  Polynomial bound for the partition rank vs the analytic rank of tensors.  Discrete Anal., 2020.  arXiv:1902.11207.
  * [KL08] Tali Kaufman and Shachar Lovett.  Worst case to average case reductions for polynomials.  In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 166–175, 2008.  doi:10.1109/FOCS.2008.17.
  * [KMZ20] Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam.  Geometric rank of tensors and subrank of matrix multiplication.  In 35th Computational Complexity Conference (CCC 2020), 2020.  doi:10.4230/LIPIcs.CCC.2020.35.
  * [Koi20] Pascal Koiran.  On tensor rank and commuting matrices, 2020.  arXiv:2006.02374.
  * [LO13] J. M. Landsberg and Giorgio Ottaviani.  Equations for secant varieties of Veronese and other varieties.  Ann. Mat. Pura Appl. (4), 192(4):569–606, 2013.  doi:10.1007/s10231-011-0238-6.
  * [Lov19] Shachar Lovett.  The analytic rank of tensors and its applications.  Discrete Anal., 2019.  arXiv:1806.09179, doi:10.19086/da.8654.
  * [Mil19] Luka Milićević.  Polynomial bound for partition rank in terms of analytic rank.  Geom. Funct. Anal., 29(5):1503–1530, 2019.  arXiv:1902.09830, doi:10.1007/s00039-019-00505-4.
  * [Nas20] Eric Naslund.  The partition rank of a tensor and $k$-right corners in $\mathbb{F}_{q}^{n}$.  Journal of Combinatorial Theory, Series A, 174:105190, 2020.  arXiv:1701.04475, doi:10.1016/j.jcta.2019.105190.
  * [NS17] Eric Naslund and Will Sawin.  Upper bounds for sunflower-free sets.  Forum Math. Sigma, 5:Paper No. e15, 10, 2017.  doi:10.1017/fms.2017.12.
  * [Raz92] Alexander A. Razborov.  On submodular complexity measures.  In Poceedings of the London Mathematical Society symposium on Boolean function complexity, pages 76–83, 1992.  URL: https://dl.acm.org/doi/10.5555/167687.167709.
  * [Raz13] Ran Raz.  Tensor-rank and lower bounds for arithmetic formulas.  Journal of the ACM (JACM), 60(6):1–15, 2013.
  * [RZ21] Robert Robere and Jeroen Zuiddam.  Amortized circuit complexity, formal complexity measures, and catalytic algorithms.  Electron. Colloquium Comput. Complex., page 35, 2021.  URL: https://eccc.weizmann.ac.il/report/2021/035.
  * [Sch81] Arnold Schönhage.  Partial and total matrix multiplication.  SIAM J. Comput., 10(3):434–455, 1981.  doi:10.1137/0210032.
  * [Shi19] Yaroslav Shitov.  Counterexamples to Strassen’s direct sum conjecture.  Acta Math., 222(2):363–379, 2019.  doi:10.4310/ACTA.2019.v222.n2.a3.
  * [Str73] Volker Strassen.  Vermeidung von Divisionen.  J. Reine Angew. Math., 264:184–202, 1973.
  * [Str83] Volker Strassen.  Rank and optimal computation of generic tensors.  Linear Algebra Appl., 52/53:645–685, 1983.  doi:10.1016/0024-3795(83)80041-X.
  * [Str87] Volker Strassen.  Relative bilinear complexity and matrix multiplication.  J. Reine Angew. Math., 375/376:406–443, 1987.  doi:10.1515/crll.1987.375-376.406.
  * [Str88] Volker Strassen.  The asymptotic spectrum of tensors.  J. Reine Angew. Math., 384:102–152, 1988.  doi:10.1515/crll.1988.384.102.
  * [Str91] Volker Strassen.  Degeneration and complexity of bilinear maps: some asymptotic spectra.  J. Reine Angew. Math., 413:127–180, 1991.  URL: http://dx.doi.org/10.1515/crll.1991.413.127, doi:10.1515/crll.1991.413.127.
  * [Tao16] Terence Tao.  A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound.  https://terrytao.wordpress.com, 2016.
  * [WZ21] Avi Wigderson and Jeroen Zuiddam.  Asymptotic spectra: Theory, applications and extensions, 2021.  URL: https://staff.fnwi.uva.nl/j.zuiddam/papers/convexity.pdf.
  * [Zui18] Jeroen Zuiddam.  Algebraic complexity, asymptotic spectra and entanglement polytopes.  PhD thesis, University of Amsterdam, 2018.  URL: https://staff.fnwi.uva.nl/j.zuiddam/diss/diss_v2.pdf.