A Universal Sequence of Tensors for the Asymptotic Rank Conjecture

The first line of research, announced by Strassen [71] in his 1986 FOCS paper and developed in a sequence of papers [66, 67, 68] and PhD theses [15, 74, 54] (cf. [72]), builds a duality theory for asymptotic rank of tensors based on the theory of preordered commutative semirings, with the direct sum and tensor (Kronecker) product of tensors as the pertinent semiring operations, and the preorder defined by a rank-capturing tensor restriction relation. Wigderson and Zuiddam [76] give a recent comprehensive exposition of Strassen’s theory and the preorder-theoretic topological dual spaces – the asymptotic spectrum of a space of tensors – which enable a tight characterization of the asymptotic rank of a tensor via the preorder-monotone homomorphisms in the dual. Yet, progress in terms of understanding the structure and identifying explicit points in the asymptotic spectrum of tensors has been slow. Beyond Strassen’s original construction of support functionals, which are restricted to the subspace of oblique tensors, only recently Christandl, Vrana, and Zuiddam [18] constructed a family of explicit universal spectral points – called quantum functionals – using theory of quantum entropy and covariants; however, also this dual family is far from yielding broadly tight lower bounds on asymptotic rank.

Viewed from the standpoint of Strassen’s duality theory, rather than working in a dual space, in this paper we seek and obtain as our main result an explicit and universal primal characterization of tensor exponents and thus asymptotic rank in ${𝔽}^d\otimes {𝔽}^d\otimes {𝔽}^d$ – before proceeding to our results, let us review a second pertinent line of prior research and motivation.

The second line of research seeks to study spaces of tensors to identify the worst-case behaviour in the space using tools from algebraic geometry, in particular building on the seminal concept of border rank of a tensor due to Bini, Capovani, Romani, and Lotti [6] (see also Schönhage [62]) and its geometric characterization via secant varieties of Segre and Veronese varieties (e.g. [13, 14, 50, 42, 45, 78]). For a space $ℱ$ of tensors, let $\sigma (ℱ)={sup}_{T\in ℱ}\sigma (T)$; as a special case, for $d=1,2,\mathrm{\dots }$ let $\sigma (d)=\sigma ({𝔽}^d\otimes {𝔽}^d\otimes {𝔽}^d)$. It is immediate that $1\le \sigma (d)\le 2$ and that $\sigma (1)=1$. Over the complex numbers, it is a nontrivial consequence of the geometry of tensors that $\sigma (2)=1$. Already the value $\sigma (3)$ is open and would be of substantial interest to determine. For example, it is known that $\sigma (3)=1$ implies $\omega =2$ by the application of the Coppersmith–Winograd method [26] to a specific $3\times 3\times 3$ tensor. It appears very difficult to prove lower bounds on $\sigma (d)$ apart from the trivial $\sigma (d)\ge 1$. Indeed, any tensor $T\in {({𝔽}^d)}^{\otimes 3}$ with $\sigma (T)>1$ would yield an explicit sequence of tensors, namely its Kronecker powers, such that for any constant $C>0$ for $k\gg 0$ we have rank and border rank of $T^{⊠k}$ greater than $C{d}^k$. Currently, we do not know explicit examples of such sequences for $C=3$ with the current world record lower bound on rank in [1]. One of the main obstacles is lack of methods to prove that a given tensor has high rank or border rank. In case of rank, the state of the art is the substitution method, based on linear algebra. In case of border rank, one looks for polynomial witnesses that vanish on tensors of given bounded border rank. However in this case, most known equations, not found via explicit computations, also vanish on so-called cactus varieties, which fill the ambient space quickly and thus known methods cannot provide super-linear lower bounds on tensor rank [4, 5, 12, 32, 38]. The state of the art for border rank is based on mixture of different methods, barely breaking the bound for $C=2$ [48]. As the rank of the generic tensor grows quadratically with $d$ the problem is often referred to as an instance of the hay in a haystack problem (phrase due to H. Karloff): find an explicit object that behaves generically. There is hope in the new introduced method of border apolarity [13], still there is currently no clear path of getting past $C=3$.

The difficulty of lower bounds and progressively improving upper bounds for specific exponents, the exponent $\omega$ in particular, has prompted bold conjectures on worst-case exponents for broad families of tensors. Most notably, writing ${𝒯}_d$ for the space of all tight tensors in ${𝔽}^d\otimes {𝔽}^d\otimes {𝔽}^d$, Strassen’s asymptotic rank conjecture (cf. [69, Conjecture 5.3]) states that the worst-case exponent for this space is the least possible:

Strassen’s asymptotic rank conjecture, if true, immediately implies the algorithmically serendipitous corollary $\omega =2$ in particular; cf. also [7, 59] for further consequences to algorithms. A yet stronger conjecture (cf. Bürgisser, Clausen, and Shokrollahi [16, Problem 15.5]; also e.g. Conner, Gesmundo, Landsberg, Ventura, and Wang [23, Conjecture 1.4] as well as Wigderson and Zuiddam [76, Section 13, p. 122]) states that the least possible exponent is shared by all concise tensors in ${𝔽}^d\otimes {𝔽}^d\otimes {𝔽}^d$:

A key result supporting Conjecture 1 and Conjecture 2, implicit in Strassen [67, Proposition 3.6] and highlighted by Christandl, Vrana, and Zuiddam [17, Proposition 2.12] as well as Conner, Gesmundo, Landsberg, and Ventura [22, Remark 2.1], is that tensor rank is known to be nontrivially submultiplicative under Kronecker products; stated in terms of worst-case tensor exponents, Strassen proved that for all $d\ge 1$ it holds that $\sigma (d)\le \frac{2\omega }{3}$.

Viewed in terms of exponents of tensors and universality, we can rephrase Strassen’s result as stating that the exponent of the matrix multiplication tensor ${\mathrm{MM}}_2$ controls from above the exponent of all other tensors, namely we have $\sigma (d)\le \frac{4}{3}\sigma ({\mathrm{MM}}_2)=\frac{2\omega }{3}$. This rephrasing suggests that one should seek explicit constructions of tensors $U\in {𝔽}^d\otimes {𝔽}^d\otimes {𝔽}^d$ that are worst-case universal for the class with $\sigma (d)=\sigma (U)$. In rough analogy with computational complexity theory, such explicit tensors capture the “hardest” tensors in a class of tensors and, for example, would provide an explicit object of study towards resolving Conjectures 1 and 2.

For a field $𝔽$ and positive integers $d$ and $q$, our key object of study is the Kronecker power map

that takes a tensor $S\in {𝔽}^d\otimes {𝔽}^d\otimes {𝔽}^d$ to its $q$^th tensor (Kronecker) power ${\mathrm{K}}_{d,q}(S)=S^{⊠q}$.

It will be convenient to study the Kronecker power map ${\mathrm{K}}_{d,q}$ by working with tensors in coordinates, so let us set up conventions accordingly. Let us write $[d]=\{1,2,\mathrm{\dots },d\}$ and identify the spaces ${𝔽}^{d\times d\times d}={𝔽}^d\otimes {𝔽}^d\otimes {𝔽}^d$. For a tensor $S\in {𝔽}^{d\times d\times d}$ in the domain of ${\mathrm{K}}_{d,q}$, we write $S_{i,j,k}\in 𝔽$ for the entry of $S$ at position $i,j,k\in [d]$. For a tensor $T\in {𝔽}^{d^q\times d^q\times d^q}$ in the codomain of ${\mathrm{K}}_{d,q}$, it is convenient to index the entries $T_{I,J,K}\in 𝔽$ of $T$ with $q$-tuples $I=(i_1,i_2,\mathrm{\dots },i_q)\in {[d]}^q$, $J=(j_1,j_2,\mathrm{\dots },j_q)\in {[d]}^q$, $K=(k_1,k_2,\mathrm{\dots },k_q)\in {[d]}^q$. Indeed, with this convention, the image ${\mathrm{K}}_{d,q}(S)=S^{⊠q}$ of a tensor $S\in {𝔽}^{d\times d\times d}$ can be defined entrywise for all $I,J,K\in {[d]}^q$ by

Next we embed the image ${\mathrm{K}}_{d,q}({𝔽}^{d\times d\times d})$ in the least-dimensional subspace of ${𝔽}^{d^q\times d^q\times d^q}$ possible, so-called linear span, and provide an explicit basis for this subspace in the assumed coordinates. Towards this end, working with integer compositions that capture the distinct right-hand sides of (3) for a generic $S$ with support in a nonempty set $\mathrm{\Delta }\subseteq [d]\times [d]\times [d]$ will be convenient. In precise terms, a function $g:\mathrm{\Delta }\to {\mathbb{N}}_{\ge 0}$ with ${\sum }_{\delta \in \mathrm{\Delta }}g(\delta )=q$ is a composition of the positive integer $q$ with domain $\mathrm{\Delta }$. Let us write ${𝒞}_q^{\mathrm{\Delta }}$ for the set of all compositions of $q$ with domain $\mathrm{\Delta }$. The distinct right-hand sides of (3) for a generic $S$ are now enumerated by the compositions $g\in {𝒞}_q^{\mathrm{\Delta }}$; explicitly, associate with $g$ the product

Writing ${𝔽}^{\mathrm{\Delta }}$ for the subspace of all tensors in ${𝔽}^{d\times d\times d}$ with support in $\mathrm{\Delta }$, we next provide a basis $(T^{(g)}\in {𝔽}^{d^q\times d^q\times d^q}:g\in {𝒞}_q^{\mathrm{\Delta }})$ that enables us to express the Kronecker power $S^{⊠q}$ of an arbitrary tensor $S\in {𝔽}^{\mathrm{\Delta }}$ as the linear combination

We need short preliminaries to define the tensors $T^{(g)}$ in the assumed coordinates. For $I,J,K\in {[d]}^q$, define the triple-counting composition ${\mathrm{\Phi }}_{I,J,K}\in {𝒞}_q^{[d]\times [d]\times [d]}$ for all $u,v,w\in [d]$ by

We use Iverson’s bracket notation; for a logical proposition $P$, we write $[[P]]$ to indicate a $0$ if $P$ is false and a $1$ if $P$ is true.

We provide various equivalent characterisations of these tensors $T^{(g)}$ in Lemma 9 (on page 9). The characterisation via integer compositions in Definition 7 in particular enables an immediate verification via (7), (4), and (3) that (5) holds. In particular, the linear span of the image ${\mathrm{K}}_{d,q}({𝔽}^{\mathrm{\Delta }})$ is contained in the linear span of the composition basis. What is less immediate is that the reverse containment holds under mild assumptions on the field $𝔽$ by identifying the Kronecker power map with the Veronese map on homogeneous $\mathrm{\Delta }$-variate polynomials of degree $q$. In coordinates, by relying on homogeneous polynomial interpolation we show in Corollary 13 and Proposition 15 that for every $g\in {𝒞}_q^{\mathrm{\Delta }}$ there exist tensors $S_f\in {𝔽}^{\mathrm{\Delta }}$ and scalars ${\lambda }_{f,g}\in 𝔽$ indexed by $f\in {𝒞}_q^{\mathrm{\Delta }}$ such that

Now (5) and (8) imply the composition basis spans exactly the linear span of ${\mathrm{K}}_{d,q}({𝔽}^{\mathrm{\Delta }})$.

By subadditivity of tensor rank, from the linear combination (5) we have immediately for an arbitrary tensor $S\in {𝔽}^{\mathrm{\Delta }}$ that

Conversely, for an arbitrary $g\in {𝒞}_q^{\mathrm{\Delta }}$, we have from (8) that

Recalling from combinatorics of integer compositions that $|{𝒞}_q^{\mathrm{\Delta }}|=\left(\genfrac{}{}{0pt}{}{|\mathrm{\Delta }|-1+q}{|\mathrm{\Delta }|-1}\right)\le {(|\mathrm{\Delta }|-1+q)}^{|\mathrm{\Delta }|-1}$, we observe that dimension of the linear span of ${\mathrm{K}}_{d,q}({𝔽}^{\mathrm{\Delta }})$ grows only polynomially in $q$ when $\mathrm{\Delta }$ is fixed. Theorem 3 and Theorem 4 follow essentially immediately by taking ${𝒰}_{\mathrm{\Delta }}=(U_{\mathrm{\Delta },q}:q=1,2,\mathrm{\dots })$ with $U_{\mathrm{\Delta },q}={⨁}_{g\in {𝒞}_q^{\mathrm{\Delta }}}{T}^{(g)}$ as the universal sequence.

The tensors $T^{(g)}$ admit several descriptions, e.g. a group-theoretic description can be given using orbit-indicators of the group ${\mathrm{SS}}_q$, see Lemma 9, and an alternative description can be given via type decompositions [76, Section 9.3] (see also [28]). There are several important applications of group theory in the study or tensor rank and asymptotic rank. We note that when $G$ is an Abelian group then the structure tensor $S_G$ of the group algebra is an orbit-indicator of the group $G^2$ identified with $\{(g_1,g_2,g_3)\in G^3:g_1+g_2=g_3\}$; in this case, the tensor $S_G$ has also minimal rank, equal to $|G|$, via the Discrete Fourier Transform. When $G$ is not Abelian, the representation theory of $G$ allows for nontrivial bounds on the rank of $S_G$; similar observations have been leveraged in the study of fast matrix multiplication; e.g. Cohn and Umans [20], Cohn, Kleinberg, Szegedy, and Umans [19], Cohn and Umans [21], Blasiak, Cohn, Grochow, Pratt, and Umans [10]. We expect this structure to enable further work towards an eventual proof or disproof of the (extended) asymptotic rank conjecture.

In addition to enabling worst-case characterisation of tensor exponents for families of tensors, the tensors $T^{(g)}$ enable the following “win-win” dichotomy (cf. Corollary 21 for a precise statement) that motivates their further study:
   Either the extended asymptotic rank conjecture (Conjecture 2) holds, implying $\omega =2$ and a disproof of the Set Cover Conjecture; or the tensors $T^{(g)}$ form an explicit sequence of tensors with superlinear border rank growth, providing substantial progress for the “hay in the haystack” problem for rank and border rank.

We stress that we here view explicitness as the property of not only a single tensor but rather a sequence of tensors; cf. e.g. [48, Section 3]. Both the tensors $T^{(g)}$ and the tensors in our universal sequences have zero-one entries in coordinates, and these entries may be computed fast. Indeed, from (7) it is immediate that we have linear-time algorithms that output $T_{I,J,K}^{(g)}$ given $I,J,K,g$ as input. Similarly, listing (or ranking/unranking) integer compositions $g\in {𝒞}_q^{\mathrm{\Delta }}$ for given $\mathrm{\Delta },q$ admit fast algorithms.

Our techniques reduce the question about asymptotic ranks to questions about ranks of specific tensors, where $T^{(g)}$ is only one possible choice. Another one is to apply representation theory of the symmetric group ${\mathrm{SS}}_p$. It turns out that ranks of very special tensors, precisely invariants in the tensor product of three Specht modules ${(S^{\alpha }\otimes S^{\beta }\otimes S^{\gamma })}^{{\mathrm{SS}}_p}$, where $\alpha ,\beta ,\gamma$ are partitions of $p$ with at most $d$ parts, govern the exponent $\sigma (d)$. Precise results are given in Section 4.

We note that the condition ${\mathrm{\Phi }}_{I,J,K}=g$ from Definition 7 determines the triple $(I,J,K)$ up to simultaneous action by an element of ${\mathrm{SS}}_q$. This proves equivalence of point $(1)$ with the original definition.

The coordinates of $K_{d,p}(S)$ in the canonical basis are monomials of degree $q$ in the coordinates of $S$. A monomial $S^g$ appears exactly on the entries indexed by such $(I,J,K)$’s that ${\mathrm{\Phi }}_{I,J,K}=g$. This proves equivalence of point $(2)$ with Definition 7.

In Proposition 15, we show that the linear span of the image of $K_{d,q}$ coincides with the linear span of $T^{(g)}$’s for $g\in {𝒞}_q^{{[d]}^3}$ and $|𝔽|>q$. As $T^{(g)}$’s have disjoint supports, we obtain point (3). $◀$

From now on we will assume that the cardinality of the field is greater than $q$.

Let $T^{(g)\ast }$ be the basis of $L_{d,q}^{\ast }$ dual to $T^{(g)}$. The image of the linear function $\sum {\lambda }_g{T}^{(g)\ast }$ is $\sum {\lambda }_g{S}^g$. Surjectivity is obvious.

By induction on the number $n$ of variables, one proves that no polynomial of degree $q$ may vanish identically on ${𝔽}^n$, when $|𝔽|>q$. Hence, no linear form $l$ is mapped to the zero function and the linear map $l\mapsto l\circ K_{d,p}$ is injective. This finishes the proof. $◀$

Clearly $L_{d,q}$ contains the image of $K_{d,q}$. If the containment was strict, there would exist a nonzero linear function $l\in L_{d,q}$ vanishing on the image. Then $l\circ K_{d,q}=0$. This is not possible by Lemma 14. $◀$

Fix $T\in {({𝔽}^d)}^{\otimes 3}$. By Lemma 9 the tensor $K_{d,q}(T)$ is a linear combination of $T^{(g)}$’s for $g\in {𝒞}_q^{{[d]}^3}$. As $|{𝒞}_q^{{[d]}^3}|=\left(\genfrac{}{}{0pt}{}{d^3-1+q}{d^3-1}\right)$ we obtain:

The statement under the assumption of asymptotic rank $r$ for $T^{(g)}$’s is proved in the same way, noting that asymptotic rank is subadditive and submultiplicative (e.g. [76]). $◀$

First fix $d_i$. By Lemma 17 we see that any $T\in ({({𝔽}^{d_i})}^{\otimes 3})$ has asymptotic rank at most:

Note that for fixed $d_i$ we have

This confirms Conjecture 2 for any $T\in {({𝔽}^{d_i})}^{\otimes 3}$. We conclude that it must hold for each $d$ from the next Lemma 19. $◀$

As the sequence $\sigma (d)$ is bounded it is enough to prove:

Fix $ϵ>0$ and $d_0\in {\mathbb{Z}}_{\ge 1}$. For contradiction assume there are infinitely many $d_i$ such that $\sigma (d_i)\le \sigma (d_0)-ϵ$. Hence, we also obtain infinitely many $k_i$ such that .

We note that we have $\sigma (d_0^{k_i})\ge \sigma (d_0)$ as taking Kronecker power of a tensor does not change the exponent. Hence, for any $\delta >0$ there exists $T_{\delta }\in {({𝔽}^{d_0^{k_i}})}^{\otimes 3}$ of asymptotic rank at least $d_0^{k_i(\sigma (d_0)-\delta )}$. As we may embed $T_{\delta }$ in larger space, we see that its asymptotic rank is at most $d_i^{\sigma (d_i)}\le d_0^{(k_i+1)(\sigma (d_0)-ϵ)}$. We obtain:

As this holds for any $\delta >0$ we obtain:

which is a contradiction for $k_i$ sufficiently large. $◀$ The following more precise result shows that the exponent governing the asymptotic rank is completely determined via asymptotic ranks of the tensors $T^{(g)}$.

The implication “$\Leftarrow$” is immediate. For the implication “$\Rightarrow$”, assume that a tensor $T$ has asymptotic rank greater than $d^{\tau +ϵ}$ for fixed $ϵ>0$. By applying Lemma 17 for $q\gg 0$ such that we obtain a contradiction. $◀$

We note that there are countably many tensors $T^{(g)}$ and they form a sequence of explicit tensors. This sequence gives rise to the following dichotomy.

It is clear that for special $g$ the rank of $T^{(g)}$ can be small. For example if $g$ is supported at one element, then $T^{(g)}$ has support of cardinality one and thus is of rank one.

We prove the equality by proving both inequalities.

First, suppose that for some constant $\sigma$. Fix an $ϵ>0$ so that for $q$ sufficiently large . Then, for $q$ sufficiently large and all $g\in {𝒞}_q^{{[d]}^3}$ we have . As ${lim}_{q\to \mathrm{\infty }}{|{𝒞}_q^{{[d]}^3}|}^{1/q}=1$ we see that for $q$ sufficiently large and all $g\in {𝒞}_q^{{[d]}^3}$ we have $\sigma (T^{(g)})\le \sigma$. Applying Lemma 17 and taking limit, as $q\to \mathrm{\infty }$ we see that $\sigma (T)\le \sigma$ for all $T\in {({𝔽}^d)}^{\otimes 3}$.

Suppose now that for all $T\in {({𝔽}^d)}^{\otimes 3}$ we have . Fix $ϵ>0$, such that for all $T\in {({𝔽}^d)}^{\otimes 3}$. By Proposition 15 for any $g\in {𝒞}_q^{{[d]}^3}$ the tensor $T^{(g)}$ is a sum of at most $|{𝒞}_q^{{[d]}^3}|$-many tensors of type $K_{d,q}(T)$. Hence, for $q$ sufficiently large we have:

It follows that:

As ${lim}_{q\to \mathrm{\infty }}|{𝒞}_q^{{[d]}^3}|/d^{ϵq}=0$ we see that $\mathrm{R}(U_{d,q})\le {(|{𝒞}_q^{{[d]}^3}|d^q)}^{\sigma }$ for $q\gg 0$. Thus $\sigma ({𝒰}_d)\le \sigma$, which finishes the proof. $◀$

Next, we construct one universal sequence realizing the worst possible exponent, irrespective of $d$ via a diagonal argument on the sequences ${𝒰}_d$. Accordingly, recalling Definition 22, define the diagonal sequence $𝒟=(D_d:d=1,2,\mathrm{\dots })$ of tensors for all positive integers $d$ by setting $D_d=U_{d,d^4}$. It is immediate that the sequence is explicit. Theorem 6 is restated below for convenience.

By Lemma 19 it is enough to prove that for every $ϵ>0$, for all $d$ sufficiently large we have $\sigma (U_{d,d^4})>\sigma (d)-ϵ$. For any (concise) $T\in {({𝔽}^d)}^{\otimes 3}$ we have:

After taking root of order $d^4$ we only need to prove that ${lim}_{d\to \mathrm{\infty }}{|{𝒞}_{d^4}^{{[d]}^3}|}^{1/d^4}=1$. We have:

which finishes the proof. $◀$

Let us write in coordinates $T=({\lambda }_{p,q,r})$ and

For $i=1,2,3$, define $l_i:{𝔽}^{d^4}\to {𝔽}^{d^3}$ as follows: