Slice rank and analytic rank for trilinear forms

Slice rank and analytic rank for trilinear forms, Discrete Analysis 2025:25, 6 pp.

For a number of years, notions of rank for tensors have been studied in areas such as additive combinatorics and theoretical computer science, owing to the discovery of several applications, many of them quite unexpected.

Each of these notions is in one way or another a generalization of the usual notion of the rank of a matrix. Indeed, if $A$ is an $m\times n$ matrix over a field $\mathbb F$, then its rank is the smallest $k$ such that we can write $A$ as $\sum_{i=1}^ku_i\otimes v_i$, where this means that $A(x,y)=\sum_{i=1}^ku_i(x)v_i(y)$. Equivalently, we define a rank-1 matrix to be a matrix of the form $u\otimes v$, and the rank of a matrix $A$ is the smallest $k$ such that $A$ is a sum of $k$ rank-1 matrices.

A tensor of order $d$, or $d$-tensor, is like a $d$-dimensional matrix. One can generalize the notion of rank to tensors in various different ways by deciding in different ways what one wishes to consider as a rank-1 tensor. When $d=3$, the most obvious candidate is tensors of the form $u\otimes v\otimes w$ (that is, tensors given by a formula of the form $A(x,y,z)=u(x)v(y)w(z)$). This is called the tensor rank of the tensor.

Another notion rose to prominence when Terence Tao gave a beautiful reformulation in terms of tensors of the proof by Jordan Ellenberg and Dion Gijswijt of an exponentially small upper bound for the cap-set problem. Central to the proof was the notion of the slice rank of a tensor, and in particular of a 3-tensor. Here the rank-1 tensors are those of the form $uv$ where $u$ is a function of one of the variables and $v$ is a function of the other variables. Thus, if $A$ is a 3-tensor of slice rank 1, then $A(x,y,z)$ will be given by a formula of the form $u(x)v(y,z)$, $u(y)v(x,z)$ or $u(z)v(x,y)$. There is also a more general notion known as partition rank where the rank-1 tensors are functions of the form $uv$, where $u$ depends on some of the variables and $v$ depends on the remaining variables (and neither is constant). The partition rank coincides with the slice rank when $d=3$ and all three notions coincide when $d=2$.

A slightly less obvious notion is that of analytic rank, first given the name in a paper of Gowers and Wolf, though the notion is implicit in earlier papers. Let $A$ be a matrix over the finite field $\mathbb F_q$. Then
$$\mathbb E_{x,y}e(\langle x,Ay\rangle/q)=q^{-r},$$ where $r$ is the rank of $A$, since for each $y$ the expectation is 1 if $y\in\mathrm{ker}A$ and 0 otherwise, and the probability that $y\in\mathrm{ker}A$ is $q^{-r}$. Thus, the rank of $A$ is equal to $-\log_q \mathbb E_{x,y}e(\langle x,Ay\rangle/q)$. Thinking of the map $(x,y)\mapsto\langle x,Ay\rangle$ as a bilinear form $\alpha$, we can generalize this definition easily to $d$-linear forms by defining the analytic rank of a $d$-linear form $\alpha$ defined on $\mathbb F_q^{n_1}\times\dots\times\mathbb F_q^{n_d}$ as
$$-\log_q\mathbb E_{x_1,\dots,x_d}e(\alpha(x_1,\dots,x_d)/q).$$

Analytic rank turns out to have many properties that one would like it to have. For example, Lovett has shown that it is subadditive. (Gowers and Wolf had previously shown that it was subadditive up to a factor 2.) The relationship between analytic rank and partition rank also turns out to be important in additive combinatorics. It is not hard to show that the analytic rank is bounded above by the partition rank. A result of Green and Tao (which preceded the paper of Gowers and Wolf) showed that the partition rank can be bounded as a function of the analytic rank, and a series of subsequent improvements has eventually led to a proof by Moshkovitz and Zhu that the dependence is at most quasilinear – that is, linear up to logarithmic factors.

When $d=3$, it is known that the dependence is linear: this was shown independently by Adiprasito, Kazhdan and Ziegler, and by Cohen and Moshkovitz. That is, the slice rank is bounded above by a constant times the analytic rank. Both proofs make use of a non-trivial result of Derksen from algebraic geometry. The purpose of this paper is to give an elementary and self-contained proof.

The proof yields a slightly stronger statement as a bonus. Given a trilinear form $g:U\times V\times W\to\mathbb F_q$ one can create a linear form from $U$ to $\mathbb F_q$ by restricting $g$ to a pair of coordinates $(v,w)$. It turns out that all the linear forms in the slice-rank decomposition yielded by the proof are of this special kind.