Structure vs Randomness for Bilinear Maps

Structure vs randomness for bilinear maps, Discrete Analysis 2022:12, 21 pp.

A tensor can be thought of as a higher-dimensional analogue of a matrix (where a matrix is 2-dimensional). Tensors arise very naturally in the context of multilinear forms, since if $V_1,\dots,V_d$ are vector spaces over a field $\mathbb F$ with given bases, then a $d$-linear map $\mu$ from $V_1\times\dots\times V_d$ to $\mathbb F$ is given by a formula of the kind

$\mu:(x_1,\dots,x_d)=\sum_{i_1,\dots,i_d}a_{i_1,\dots,i_d}x_{1,i_1}\dots x_{d,i_d}$,

where $x_{i,j}$ is the $j$th coordinate of $x_i$.

For matrices and bilinear forms, the notion of rank plays such a fundamental role that an obvious question is how to generalize it to tensors and multilinear forms. However, it turns out that there are several natural generalizations, and different notions of tensor rank are useful in different situations. It is therefore of great interest to try to understand how these notions relate to each other.

One way to describe the rank of a bilinear form $\beta:V\times W\to\mathbb F$ is that it is the smallest $r$ such that we can write $\beta(v,w)$ as $\sum_{i=1}^ra_i(v)b_i(w)$ for some linear forms $a:V\to\mathbb F$ and $b:W\to\mathbb F$. Equivalently, we say that a bilinear form has rank 1 if it breaks up as a product of linear forms, and then the rank of a bilinear form is the smallest number of rank-1 forms needed to contain it in their linear span. If we try to generalize this to trilinear forms, we find that there are two ways that we might wish to define a rank-1 form. The more obvious, which leads to the notion of tensor rank is to define it as a form $(u,v,w)\mapsto a(u)b(v)c(w)$, where $a$, $b$ and $c$ are linear forms. Another, which leads to the notion of slice rank, which played a central role in the developments surrounding the famous solution of the cap-set problem, is to define a rank-1 form as any trilinear form that is a product of a linear form in one variable and a bilinear form in the other two variables – and is thus a product of two simpler forms. Clearly as $d$ increases, the possible ways of splitting up a $d$-linear form as a product of simpler multilinear forms increases as well, leading to several further notions of rank, of which we single out just one: a $d$-linear form is said to have partition rank 1 if it can be written as a product of two multilinear forms in disjoint non-empty subsets of the variables. For instance, if $\beta$ is a bilinear form and $\tau$ a trilinear form, then the form $(v_1,v_2,v_3,v_4,v_5)\mapsto\beta(x_1,x_4)\tau(x_2,x_3,x_5)$ is a 5-linear form of partition rank 1.

Another definition of rank for trilinear forms comes from the following observation in the bilinear case: if $\beta:V\times W\to\mathbb F_p$ is a bilinear form and $\omega_p=\exp(2\pi i/p)$, then the average

$\mathbb E_{v\in V}\mathbb E_{w\in W}\omega_p^{\beta(v,w)}$

is equal to $p^{-\mathrm{rk}(\beta)}$. To see this, note that the expectation over $w$ is zero if $\beta(v,w)$ is not identically zero, and 1 otherwise.

The quantity on the left-hand side generalizes very easily, leading Gowers and Wolf to define the analytic rank of a $d$-linear form $\mu:V_1\times\dots\times V_d\mathbb F_p$ to be

$-\log_p(\mathbb E_{v_1,\dots,v_d}\omega_p^{\mu(v_1,\dots,v_d)})$,

and to prove that it has some good properties. (In particular, they proved that it is subadditive up to a constant factor. Later, in an article published in this journal, Lovett removed the constant factor: that is, analytic rank is now known to be exactly subadditive.)

The concept of analytic rank is closely related to the notion of the bias of a polynomial, which appeared in earlier work of Green, Tao, Kaufmann, Lovett, and others, which is a measure of how far from uniformly distributed the values taken by the polynomial are. As a result of that work, it became a central problem to determine how the partition rank and the analytic rank of a multilinear form are related. A straightforward argument (see Theorem 1.7 part (i) in the paper of Lovett mentioned above, which was also obtained independently by Kazhdan and Ziegler) shows that the analytic rank is at most the partition rank. A considerably less straightforward argument of Bhowmick and Lovett showed that in fact the two ranks are equivalent, in the sense that the partition rank is bounded as a function of the analytic rank. However, the bound they obtained was of Ackermann type. A breakthrough obtained independently by Janzer and Milićević improved this to a polynomial dependence. (Janzer’s paper is also published in this journal.)

The authors of this paper have obtained a further breakthrough, showing that analytic and partition rank are equal up to a constant factor, provided the characteristic of the underlying field is sufficiently large. This paper itself is not about that result, but about a precursor to it that deals with the trilinear case and does not require the assumption about the field (other than that it should not be $\mathbb F_2$). In the case of trilinear forms, partition rank is the same as slice rank: the authors show that the slice rank of a trilinear form is at most 8.13 times its analytic rank, and draw several interesting consequences.

Just as a matrix corresponds to a linear map, a 3-tensor corresponds to a bilinear map – hence the word “bilinear” in the title rather than “trilinear”. (If $\tau:U\times V\times W\to\mathbb F$ is a trilinear form, we can define a bilinear map $\beta:U\times V\to W^*$ by $\beta(u,v)(w)=\tau(u,v,w)$.) This is a convenient perspective because the authors have used a further notion of rank (introduced by Kopparty, Zuiddam and the second author) that plays a crucial intermediate role in their proof. They define the geometric rank of a bilinear map $\beta:U\times V\to W$ to be the codimension of the algebraic variety $\{(u,v)\in U\times V:\beta(u,v)=0\}$. (The dimension of a variety can be defined as the length of the longest strictly increasing chain of non-zero irreducible varieties contained in it.) The complete result they prove in this paper is that the slice rank is at most three times the geometric rank, which is at most 8.13 times the analytic rank. Thus, the main result of the paper, as well as being an important result in its own right, is a convincing definition of the importance of the notion of geometric rank.