Geometric rank of tensors and subrank of matrix multiplication

- Department of Mathematics and Department of Computer Science, University of Toronto
- More about Swastik Kopparty

- Department of Mathematics, City University of New York
- More about Guy Moshkovitz

- Korteveg-de Vries Institute for Mathematics, University of Amsterdam
- More about Jeroen Zuiddam

*Discrete Analysis*, April. https://doi.org/10.19086/da.73322.

### Editorial introduction

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 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 F is the finite field Fp is to observe (following a straightforward calculation) that if M is a matrix of rank r, then s(M)=Ex,yexp(2πiM(x,y)/p)=p−r. If we wanted, we could therefore define the rank of M to be logp(1/s(M)). This has an obvious generalization to higher-order tensors. For instance, if d=3 then we define s(T) to be Ex,y,zexp(2πiT(x,y,z)/p) and we can consider the quantity logp(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)∈[n1]×[n2]×[n3], where [n] denotes the set {1,2,…,n}. Then for each k∈[n3] let Mk be the matrix Mk(i,j)=T(i,j,k). That is, the matrices Mk are the “slices” of T perpendicular to the third axis. Now define an algebraic variety in Fn1×Fn2 to be the set of all (x,y) such that xTMky=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 n1=n2=n3=n, and let T(i,j,k)=1 if i=j=k≤m and 0 otherwise. Then the variety V is the set of all (x,y)∈Fn×Fn such that xryr=0 for r=1,2,…,m, which can be shown to have codimension m (roughly speaking since if the coordinates x1,…,xm are non-zero, then the set of y such that (x,y)∈V is the set of y such that y1=⋯=ym=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 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 Fp, 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)∈V will be pn−m, so the number of points in V will be well approximated by p2n−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)=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 n3) 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.