Geometric rank of tensors and subrank of matrix multiplication

Abstract

Geometric rank of tensors and subrank of matrix multiplication, Discrete Analysis 2023:1, 25 pp. The rank of a matrix is a parameter of obvious importance, so it is natural to wonder what the right definition is for the rank of a higher-dimensional matrix -- that is, of a tensor (which can be thought of as a $d$-dimensional array of elements of a field $\mathbb F$). This question turns out not to have a straightforward answer: there are many different natural definitions for the rank of a tensor that specialize to matrix rank when the tensor has dimension 2. However, it also turns out that several of these definitions are useful and have important applications. One approach to defining a notion of rank is first to decide what the rank-1 tensors should be and then to define the rank of a tensor $T$ to be the smallest number of rank-1 tensors needed to generate $T$ as a linear combination. If $d=3$ and we define a rank-1 tensor to be one of the form $T(x,y,z)=a(x)b(y)c(z)$, then we obtain the notion of _tensor rank_. If instead we define a rank-1 tensor to be one of the form $a(x)b(y,z)$, $a(y)b(x,z)$ or $a(z)b(x,y)$, then we obtain the notion of _slice rank_, which was introduced by Tao and played a key role in his reformulation of the famous solution to the cap-set problem. A different approach, which works when $\mathbb F$ is the finite field $\mathbb F_p$ is to observe (following a straightforward calculation) that if $M$ is a matrix of rank $r$, then $s(M)=\mathbb E_{x,y}\exp(2\pi iM(x,y)/p)=p^{-r}$. If we wanted, we could therefore define the rank of $M$ to be $\log_p(1/s(M))$. This has an obvious generalization to higher-order tensors. For instance, if $d=3$ then we define $s(T)$ to be $\mathbb E_{x,y,z}\exp(2\pi iT(x,y,z)/p)$ and we can consider the quantity $\log_p(1/s(T))$ as a kind of rank of $T$. This notion was introduced by Gowers and Wolf, who called it the _analytic rank_ of the tensor. However, in contrast with tensor rank and slice rank, the definition of the analytic rank depends on the field being finite, and it is not obvious what an analogous notion should be for fields of characteristic zero. This question was explicitly asked by Lovett, and is answered in this paper, where the authors introduce yet another notion of rank, which they call _geometric rank_. For a 3-tensor $T$, the geometric rank is defined as follows. Let $T$ have coefficients $T(i,j,k)$ for $(i,j,k)\in [n_1]\times [n_2]\times [n_3]$, where $[n]$ denotes the set $\{1,2,\dots,n\}$. Then for each $k\in[n_3]$ let $M_k$ be the matrix $M_k(i,j)=T(i,j,k)$. That is, the matrices $M_k$ are the "slices" of $T$ perpendicular to the third axis. Now define an algebraic variety in $\mathbb F^{n_1}\times\mathbb F^{n_2}$ to be the set of all $(x,y)$ such that $x^TM_ky=0$ for every $k$. The geometric rank of $T$ is defined to be the codimension of this variety, which can be shown to be independent of which of the three directions we use to define the slices. To illustrate this with a very simple example, suppose that $n_1=n_2=n_3=n$, and let $T(i,j,k)=1$ if $i=j=k\leq m$ and 0 otherwise. Then the variety $V$ is the set of all $(x,y)\in\mathbb F^n\times\mathbb F^n$ such that $x_ry_r=0$ for $r=1,2,\dots,m$, which can be shown to have codimension $m$ (roughly speaking since if the coordinates $x_1,\dots,x_m$ are non-zero, then the set of $y$ such that $(x,y)\in V$ is the set of $y$ such that $y_1=\dots=y_m=0$, which has codimension $m$). While the relationship between geometric rank and analytic rank is not completely straightforward, it is at least plausible, given basic results about the sizes of varieties in finite fields, that if we approximate a field $\mathbb F$ by larger and larger finite fields and count the number of points in the corresponding variety $V$, then it should grow like a power and that that power should be the codimension of $V$. Indeed, the example just given illustrates this: if the coefficients belong to $\mathbb F_p$, say, then for large $p$ almost every $x$ will have all its first $m$ coordinates not equal to zero, so for almost every $x$ the number of $y$ with $(x,y)\in V$ will be $p^{n-m}$, so the number of points in $V$ will be well approximated by $p^{2n-m}$. While the definition of geometric rank can be seen to be natural, what matters more is whether it is useful. In this paper the authors demonstrate its utility by first showing that it gives upper and lower bounds for various other notions of rank, which sometimes leads to easier ways of bounding other ranks of given tensors. Then they apply these results to analyse the important _matrix multiplication tensor_, which is the tensor that corresponds to the trilinear map $T(A,B,C)=\text{tr}(ABC)$ where $A$, $B$ and $C$ are three matrices for which the right-hand side makes sense. (More precisely, for each choice of sizes for the matrices we obtain a separate matrix multiplication tensor.) The famous and important problem of determining the number of scalar multiplications needed in order to calculate the product of two matrices turns out to be equivalent to determining the tensor rank of the matrix multiplication tensor. In 1987, Strassen (the first person to obtain a power saving on the trivial upper bound of $n^3$) obtained a lower bound for a notion of rank called the border subrank, and the results of this paper prove that this bound of Strassen is sharp. Since this paper first appeared as a preprint, the notion of geometric rank has played an important role in a central problem of additive combinatorics, which is to relate analytic rank to partition rank (where the rank-1 tensors of degree $d$ are those of the form $UV$, where $U$ and $V$ depend on disjoint sets of variables). After a long series of developments, Alex Cohen and the second author made essential use of geometric rank to prove that for sufficiently large finite fields the partition rank is bounded above by a linear function of the analytic rank.