Slice Rank and Partition Rank of the Determinant

Lampert, Amichai; Moshkovitz, Guy

doi:10.4230/LIPIcs.ITCS.2026.90

Slice Rank and Partition Rank of the Determinant

Amichai Lampert

University of Michigan, Ann Arbor, MI, USA Guy Moshkovitz

City University of New York, NY, USA

Abstract

The Laplace expansion expresses the $n\times n$ determinant $\mathrm{det}_{n}$ as a sum of $n$ products. Do shorter expansions exist? In this paper we:

$\blacksquare$

Fully determine the slice rank decompositions of $\mathrm{det}_{n}$ (where each product must contain a linear factor): In this case, we show that $n$ summands are necessary, and moreover, the only such expansions with $n$ summands are equivalent (in a precise sense) to the Laplace expansion.
$\blacksquare$

Prove a logarithmic lower bound for the partition rank of $\mathrm{det}_{n}$ (where each product is of multilinear forms): In this case, we show that at least $\log_{2}(n)+1$ summands are needed and we explain why existing techniques fail to yield any nontrivial lower bound.
$\blacksquare$

Separate partition rank from slice rank for $\mathrm{det}_{n}$ : we find a quadratic expansion for $\mathrm{det}_{4}$ , over any field, with fewer summands than the Laplace expansion. This construction is related to a well-known example of Green-Tao and Lovett-Meshulam-Samorodnitsky disproving the naive version of the Gowers Inverse conjecture over small fields.

An important motivation for these questions comes from the challenge of separating structure and randomness for tensors. On the one hand, we show that the random construction fails to separate: for a random tensor of partition rank $r$ , the analytic rank is $r-o(1)$ with high probability. On the other hand, our results imply that the determinant yields the first asymptotic separation between partition rank and analytic rank of $d$ -tensors, with their ratio tending to infinity with $d$ .

Keywords and phrases:

Slice rank, partition rank, determinant

Funding:

Amichai Lampert: NSF Award DMS-2402041.

Guy Moshkovitz: NSF Award DMS-2302988 and a PSC-CUNY award.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algebraic complexity theory

Related Version:

Full Version: https://arxiv.org/abs/2509.06294

Acknowledgements:

AL is grateful to the City University of New York for its hospitality during the period when this project was initiated.

DOI:

10.4230/LIPIcs.ITCS.2026.90

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The determinant is one of the most well known polynomials in mathematics, and formulas for it are naturally important. The Laplace (row) expansion is the principal such formula, expressing the determinant of $n\times n$ matrices as a sum of products: for any $i$ , $\mathrm{det}(A)=\sum_{j=1}^{n}(-1)^{i+j}a_{i,j}\mathrm{det}(A_{i,j}),$ where $A_{i,j}$ is obtained from $A$ by removing row $i$ and column $j$ . The number of summands in the Laplace expansion for the $n\times n$ determinant is $n$ . Are there expansions of the determinant with fewer summands? In this paper we initiate the study of such expansions. This follows in the tradition of [6, 15], where other notions of rank for the determinant were studied.

We denote by $\mathrm{det}_{n}$ the determinant polynomial of $n\times n$ matrices. The slice rank [25, 23] of the determinant equals the minimal number of summands when we require each of the products to have a linear factor. Our first result completely characterizes these expansions.

Theorem 1 (see Theorem 9).

$\textnormal{srk}(\mathrm{det}_{n})=n$ for every $n\geq 2$ , and the only minimum slice rank expansions are all “equivalent” to the Laplace expansion.

Since the determinant is a multilinear form – meaning a homogeneous polynomial that is linear in each of its vector variables¹¹1In the case of the determinant, the rows of the matrix (or, alternatively, the columns). – it is natural to require that the terms of the expansion are multilinear as well. For a multilinear form $T$ , the partition rank [22] $\textnormal{prk}(T)$ is the least number of summands when we require each of the factors to be multilinear. Our results for partition rank of the determinant are as follows:

Theorem 2 (see Theorem 13).

For every $n\geq 2$ , $\textnormal{prk}(\mathrm{det}_{n})\geq\log_{2}(n)+1$ .

Theorem 3 (see Theorem 16).

It is not true that $\textnormal{prk}(\mathrm{det}_{n})=n$ , or that $\textnormal{prk}(\mathrm{det}_{n})=\textnormal{srk}(\mathrm{det}_{n})$ . Namely, $\textnormal{prk}(\mathrm{det}_{4})=3$ over any field.

We mention that the partition rank expansion of $\mathrm{det}_{4}$ in Theorem 3 is genuinely different from the Laplace expansion or the generalized Laplace expansion (see Lemma 18).

Note that we consider expressions of the determinant as, simply, a sum of products, each with at least two factors. For comparison, in (multilinear) arithmetic formulas or circuits, each factor in the expansion is also given an expansion, as well as each factor in those expansions and so on. In this context, what we are interested in is only the top fan-in, which is trivially at most $n$ .²²2An extreme case is where all factors in the expansions are required to be linear (this corresponds to the traditional notion of tensor rank), for which an exponential lower bound of $\binom{n}{\lfloor{n/2}\rfloor}$ is known for the number of summands [6].

Our proof strategy for Theorem 2 (and similar proof strategies used to bound partition rank in the past) cannot yield a lower bound on $\textnormal{prk}(\mathrm{det}_{n})$ better than logarithmic (see Remark 14). It remains open whether a different strategy could do better.

Problem 0.

Determine the asymptotics of $\textnormal{prk}(\mathrm{det}_{n})$ .

One can also ask about expansions of the determinant where the factors need not be multilinear. This corresponds to the strength (or rank) of $\mathrm{det}_{n}$ , where for any form $P$ , $\textnormal{str}(P)$ is the least number of reducible forms that sum to $P$ . For this notion, even obtaining any nontrivial bound is open.

Conjecture 1.

$\lim_{n\to\infty}\textnormal{str}(\mathrm{det}_{n})=\infty$ .

As far as we know, it could be true that $\textnormal{str}(\mathrm{det}_{n})=n$ for all $n\neq 4$ !

1.1 Structure versus randomness

Proving lower bounds for $\textnormal{prk}(\mathrm{det}_{n})$ also has an important application in the study of the structure-versus-randomness phenomenon for (multilinear) polynomials. Structure is usually captured by partition rank, and randomness by analytic rank. For a multilinear form $T$ over a finite field $\mathbb{F}$ , denote $\textnormal{bias}(T)=\Pr[T=0]-\Pr[T=y]$ for any nonzero $y\in\mathbb{F}$ .³³3The definition is independent of the choice of $y\neq 0$ .⁴⁴4Throughout, the probabilities are over a uniformly random choice in the relevant domain. The analytic rank [8] of $T$ is $\textnormal{ark}(T)=-\log_{|\mathbb{F}|}(\textnormal{bias}(T))$ .

Sub-additivity [13, 16] implies $\textnormal{ark}(T)\leq\textnormal{prk}(T)$ . A central conjecture in additive combinatorics (see e.g. [16, 1, 10, 19]) – the partition-versus-analytic rank conjecture – posits that the inverse approximately holds: $\textnormal{prk}(T)\leq O_{d}(\textnormal{ark}(T))$ (that is, uniformly in $n$ and $\mathbb{F}$ ). This conjecture is known to hold if the field is large enough [5, 20].⁵⁵5 $|\mathbb{F}|\geq(\textnormal{ark}(T)+1)^{\epsilon(d)}$ would do. It is also known to hold up to a logarithmic factor in $\textnormal{ark}(T)$ over any finite field [20]. The extent to which the bound must depend on $d$ , however, is unclear, and the best lower bound we are aware of is a $3/2$ factor [4] (see also [14, 3] for the slightly weaker lower bound of $4/3$ witnessed by the matrix multiplication tensor).

Formally, define the extremal ratio $A(d)=\max_{T}\textnormal{prk}(T)/\lceil\textnormal{ark}(T)\rceil$ , where the maximum is over all $d$ -linear forms $T$ .⁶⁶6One can define a version of $A(d)$ over large enough fields, which is necessarily finite by the aforementioned [5] (even if the partition-versus-analytic rank conjecture turned out to be false). The lower bound on $A(d)$ we prove in this paper indeed holds over any finite field.⁷⁷7The ceiling avoids the rather degenerate case where $\textnormal{prk}(T)=1$ but the denominator $\textnormal{ark}(T)$ , which need not be an integer, is close to $0$ (when $T$ is a product of many factors). Linear algebra tells us that $A(2)=1$ (that is, $\textnormal{prk}(T)=\textnormal{ark}(T)$ for any linear map/bilinear form $T$ ), and as mentioned above, it is known that $A(3)\geq\frac{3}{2}$ . (Note also that $A(d)$ is monotone increasing).

It seems that separating partition rank from analytic rank – that is, proving the existence of a multilinear form that has high partition rank but low analytic rank – is a nontrivial challenge. In particular, for almost all $d$ -linear forms $T\colon(\mathbb{F}^{n})^{d}\to\mathbb{F}$ , both $\textnormal{prk}(T)$ and $\textnormal{ark}(T)$ are essentially $n$ . However, what if we condition $T$ to have a given partition rank? We show that one cannot obtain a separation in this way either.

Theorem 4 (see Theorem 23).

A random $d$ -linear form of partition rank $r$ has, with high probability, analytic rank roughly $r$ .

In the context of separating structure from randomness, the importance of obtaining lower bounds for $\textnormal{prk}(\mathrm{det}_{n})$ stems from the observation (see Corollary 20 below) that $\lceil\textnormal{ark}(\mathrm{det}_{n})\rceil=2$ for any $n\geq 2$ . Therefore, any lower bound on $\textnormal{prk}(\mathrm{det}_{n})$ would yield a corresponding lower bound on $A(d)$ , namely $A(d)\geq\textnormal{prk}(\mathrm{det}_{d})/2$ . We therefore obtain from Theorem 2 the following separation.

Corollary 2 (See Corollary 21).

$A(d)\geq(\log_{2}(d)+1)/2$ , and in particular, $A(d)$ is unbounded.

It follows that a dependence on $d$ in the structure-versus-randomness question is inevitable. Tensors whose partition and analytic rank are far apart are provably rare, by Theorem 23. Explicitly, we now know of one such example, the determinant, by Theorem 13. It would be interesting to find additional explicit constructions of such tensors.

Let us remark that randomness can also be defined geometrically, over any field $\mathbb{F}$ , using geometric rank [14]. For a $d$ -linear form $T=T(x^{(1)},\ldots,x^{(d)})$ , denote $\nabla T(x^{(1)},\ldots,x^{(d-1)})=(\partial T/\partial x^{(d)}_{i})_{i}$ the gradient of $T$ with respect to the last (say) vector variable. Over finite fields, the gradient is intimately connected to the analytic rank; indeed, a simple Fourier-analytic argument (e.g. [16]) shows that $\textnormal{bias}(T)=\Pr[\nabla T=0]$ . This motivates the definition of geometric rank, which is the geometric analogue of analytic rank. Formally, $\textnormal{grk}(T)=\textnormal{codim}\{x|\nabla T(x)=0\}$ , the codimension of the algebraic variety (over the algebraic closure of $\mathbb{F}$ ) cut out by the gradient. It is known that $\textnormal{grk}(T)=\Theta_{d}(\textnormal{ark}(T))$ over any finite field [3, 21], and that $\textnormal{grk}(T)=\Theta_{d}(\textnormal{prk}(T))$ over any algebraically closed field [12, 24]. We can now define a geometric analogue to $A(d)$ , namely $G(d)=\max_{T}\textnormal{prk}(T)/\textnormal{grk}(T)$ , where the maximum is over all $d$ -linear forms. One can verify that all our results about separating structure and randomness translate, with some effort, to the geometric setting, in which analytic rank is replaced by geometric rank. In particular, $G(d)\geq\frac{\log_{2}(d)+1}{2}.$

It remains open to obtain a super-logarithmic separation between structure and randomness, either using an explicit construction or not, and either in the finite field setting or in the geometric setting.

Problem 2.

Prove or disprove: $A(d)=\omega(\log d)$ . Similarly for $G(d)$ .

2 Slice rank of the determinant

Henceforth all polynomials are assumed to have coefficients in some field $\mathbb{F}$ . We begin this section with the definition of slice rank:

Definition 3.

If $f$ is a form (i.e. homogeneous polynomial) of degree $d$ then its slice rank, written $\textnormal{srk}(f),$ is the minimal $r$ such that $f=\sum_{i=1}^{r}\alpha_{i}g_{i},$ where $\alpha_{i}$ are linear forms and $g_{i}$ are forms of degree $d-1.$ ⁸⁸8Slice rank is usually defined for multilinear forms and requires the decomposition to respect the multilinear structure. Our less restrictive definition means that our characterization of slice rank decompositions of the determinant holds in greater generality.

In this section we will characterize the slice rank decompositions of the determinant. We will prove that the slice rank of $\mathrm{det}_{n}$ is $n$ , and show that any slice rank decomposition of length $n$ is equivalent to the Laplace expansion, in a sense we will soon make precise.

2.1 Equivalence for slice rank decompositions

We now turn to describing some natural reductions for slice rank decompositions. See Karam [11] for a more detailed discussion. Let $f$ be a form of degree $d$ , and let $f=\sum_{i=1}^{r}\alpha_{i}g_{i}$ be some (initial) slice rank decomposition. We will denote this decomposition by $(\vec{\alpha},\vec{g}).$

Definition 4.

We define a preorder $\lesssim$ on the collection of slice rank decompositions of $f$ by taking the transitive closure of the following natural relations:

1.

Linear reduction: Let $\beta_{1},\ldots,\beta_{r}$ be linear forms with $\alpha_{1},\ldots,\alpha_{r}\in\operatorname{Span}(\beta_{1},\ldots,\beta_{r}).$ Writing $\alpha_{i}=\sum_{j=1}^{r}c_{i,j}\beta_{j},$ we get:

$f=\sum_{i=1}^{r}\alpha_{i}g_{i}=\sum_{i=1}^{r}\sum_{j=1}^{r}c_{i,j}\beta_{j}g_% {i}=\sum_{j=1}^{r}\beta_{j}\sum_{i=1}^{r}c_{i,j}g_{i}.$

Thus, $(\vec{\beta},\vec{h})$ is another slice rank decomposition, where $h_{j}=\sum_{i=1}^{r}c_{i,j}g_{i}.$ We declare $(\vec{\beta},\vec{h})\lesssim(\vec{\alpha},\vec{g}).$
2.

Syzygy reduction: If $h_{i}=g_{i}-\sum_{j\neq i}q_{i,j}\alpha_{j}$ for an alternating matrix $(q_{i,j})_{i,j}$ of forms of degree $d-2$ (i.e. $q_{i,i}=0$ and $q_{i,j}=-q_{j,i}$ ), then

$f=\sum_{i=1}^{r}\alpha_{i}g_{i}=\sum_{i=1}^{r}\alpha_{i}h_{i}+\sum_{1\leq i<j% \leq r}\alpha_{i}\alpha_{j}(q_{i,j}+q_{j,i})=\sum_{i=1}^{r}\alpha_{i}h_{i}.$

Therefore, $(\vec{\alpha},\vec{h})$ is another slice rank decomposition of $f$ . We declare $(\vec{\alpha},\vec{h})\lesssim(\vec{\alpha},\vec{g}).$ Note that in this case we also have $(\vec{\alpha},\vec{g})\lesssim(\vec{\alpha},\vec{h})$ .
3.

Symmetric reduction: If $A:\mathbb{F}^{n}\to\mathbb{F}^{n}$ is a linear map (not necessarily invertible) such that $f\circ A=f$ ,⁹⁹9For example, if $f=\mathrm{det}_{n}$ then matrix transposition is one example of such a linear map (that is, $f$ is an invariant under matrix transposition). then $(\vec{\alpha}\circ A,\vec{g}\circ A)$ is also a slice rank decomposition with $(\vec{\alpha}\circ A,\vec{g}\circ A)\lesssim(\vec{\alpha},\vec{g}).$

$\blacktriangleright$ Remark 5.

We briefly discuss the motivation for choosing these reduction rules. The bilinear map $(\vec{\alpha},\vec{g})\mapsto\sum_{i=1}^{r}\alpha_{i}g_{i}$ is symmetric under the action of the orthogonal group, which corresponds to linear reduction. It is also preserved under translation of $\vec{g}$ by an alternating matrix times $\vec{\alpha}$ , which corresponds to syzygy reduction.¹⁰¹⁰10We could also translate $\vec{\alpha}$ but that would increase the degree of its entries. These two symmetries preserve the bilinear form which parametrizes slice rank decompositions, but there may be additional symmetries coming from the form $f$ itself – these correspond to symmetric reduction.

Definition 6.

Two slice rank decompositions $(\vec{\alpha},\vec{g})$ and $(\vec{\beta},\vec{h})$ are equivalent if both $(\vec{\beta},\vec{h})\lesssim(\vec{\alpha},\vec{g})$ and $(\vec{\alpha},\vec{g})\lesssim(\vec{\beta},\vec{h})$ .

Our goal here is to show that, up to our equivalence defined above, slice rank decompositions are determined by their (linearly independent) linear factors.

Lemma 7.

Suppose that $(\vec{\alpha},\vec{g})$ and $(\vec{\beta},\vec{h})$ are two slice rank decompositions of $f .$ If $\beta_{1},\ldots,\beta_{r}$ are linearly independent and their linear span contains $\alpha_{1},\ldots,\alpha_{r},$ then $(\vec{\beta},\vec{h})\lesssim(\vec{\alpha},\vec{g}).$

Proof.

By assumption, $\alpha_{i}=\sum_{j}c_{i,j}\beta_{j}.$ Plugging this in yields

0=f-f=\sum_{j=1}^{r}\beta_{j}(h_{j}-\sum_{i=1}^{r}c_{i,j}g_{i}).

The proof is complete once we show that if $t_{1},\ldots,t_{r}$ are forms of degree $d-1$ satisfying $0=\sum_{j=1}^{r}\beta_{j}t_{j}$ then $t_{j}=\sum_{i\neq j}q_{i,j}\beta_{i}$ for forms $q_{i,j}$ of degree $d-2$ which satisfy $q_{i,j}=-q_{j,i}$ . This we prove by induction on $r,$ following an argument from [26].

In the base case $r=1$ the equality $\beta_{1}t_{1}=0$ implies $t_{1}=0$ as claimed. Suppose the claim holds for $r-1$ and that $0=\sum_{j=1}^{r}\beta_{j}t_{j}.$ Restricting to the hyperplane $W$ where $\beta_{r}$ vanishes, we have $0=\left(\sum_{j=1}^{r-1}\beta_{j}t_{j}\right)\restriction_{W}.$ The linear forms $\beta_{1},\ldots,\beta_{r-1}$ are linearly independent when restricted to $W,$ so the inductive hypothesis implies that for $j<r$ we have $t_{j}\restriction_{W}=\sum_{i\neq j,r}q_{i,j}\beta_{i}\restriction_{W}$ , where $q_{i,j}$ are forms on $W$ of degree $d-2$ satisfying $q_{i,j}=-q_{j,i}$ for all $i<j<r$ .

We lift $q_{i,j}$ to forms of degree $d-2$ on the whole space while preserving the skew-symmetry $q_{i,j}=-q_{j,i}$ for all $i<j<r.$ This gives us $t_{j}=\sum_{i\neq j,r}q_{i,j}\beta_{i}+s_{j}\beta_{r}$ for $j<r$ , where $s_{j}$ are forms of degree $d-2.$ Therefore,

0=\sum_{j=1}^{r}\beta_{j}t_{j}=\sum_{j=1}^{r-1}\beta_{j}\left(\sum_{i\neq j,r}% q_{i,j}\beta_{i}+s_{j}\beta_{r}\right)+\beta_{r}t_{r}=\beta_{r}\left(\sum_{j=1% }^{r-1}s_{j}\beta_{j}+t_{r}\right).

Dividing both sides by $\beta_{r}$ yields $t_{r}=-\sum_{i=1}^{r-1}s_{i}\beta_{i},$ proving the inductive claim with $q_{r,i}=s_{i}=-q_{i,r}$ for $i<r$ . $\hfill\blacktriangleleft$

Corollary 8.

If $(\vec{\alpha},\vec{g})$ and $(\vec{\beta},\vec{h})$ are two slice rank decompositions of $f$ , and $\alpha_{i}$ and $\beta_{i}$ are bases for the same linear space, then the two slice rank decompositions are equivalent.

2.2 Slice rank decompositions of the determinant

Our goal is to prove the following:

Theorem 9.

For every $n\geq 2$ , the slice rank of $\mathrm{det}_{n}$ equals $n .$ Moreover, any slice rank decomposition $\mathrm{det}_{n}=\sum_{i=1}^{n}\alpha_{i}g_{i}$ is equivalent (in the sense of Definition 6) to the Laplace expansion along the first row.

Towards the proof of Theorem 9, we will prove the following characterization of slice rank decompositions of the determinant. We introduce the notation $R_{1}=\operatorname{Span}(x_{1,1},\ldots,x_{1,n})$ for the linear space spanned by the coordinates of the first row of a matrix $(x_{i,j})$ .

Proposition 10.

Suppose $\mathrm{det}_{n}=\sum_{i=1}^{r}\alpha_{i}g_{i}$ is a slice rank decomposition. Then:

1.

The inequality $r\geq n$ holds and
2.

If $r=n$ there exists $A\in\textnormal{SL}_{n}(\mathbb{F})$ such that either $(\alpha_{i}(Ax))_{i\in[n]}$ or $(\alpha_{i}(Ax^{t}))_{i\in[n]}$ is a basis for $R_{1}.$

Our main tool is the following result of Meshulam [18] (we are interested specifically in the case $s=n-1$ ). We denote by $M_{n}(\mathbb{F})$ space of $n\times n$ matrices with coefficients in $\mathbb{F}.$

Lemma 11 (Meshulam).

Let $\mathcal{M}\subseteq M_{n}(\mathbb{F})$ be a subspace.

1.

If $\dim(\mathcal{M})>sn$ then it contains a matrix of rank greater than $s .$
2.

If $\dim(\mathcal{M})=sn$ and $\textnormal{rk}(x)\leq s$ for all $x\in\mathcal{M},$ then there exists a subspace $E\subset\mathbb{F}^{n}$ of dimension $s$ such that $\mathcal{M}=E\otimes\mathbb{F}^{n}$ or $\mathcal{M}^{t}=E\otimes\mathbb{F}^{n},$ where

$E\otimes\mathbb{F}^{n}:=\operatorname{Span}\{uv^{t}:u\in E,v\in\mathbb{F}^{n}\}.$

We are now ready to prove our characterization.

Proof of Proposition 10.

Let

\mathcal{M}=\{x\in M_{n}(\mathbb{F}):\alpha_{1}(x)=\ldots\alpha_{r}(x)=0\}.

By assumption, $\mathrm{det}_{n}$ vanishes identically on $\mathcal{M},$ so all the matrices in $\mathcal{M}$ have rank at most $n-1.$ By Lemma 11,

(n-1)n\geq\dim\mathcal{M}\geq n^{2}-r\implies r\geq n.

This proves the first assertion. Moreover, if $r=n$ then we are in the second case of Lemma 11 (with $s=n-1$ ), so $\mathcal{M}=\mathbb{F}^{n}\otimes E$ or $\mathcal{M}=E\otimes\mathbb{F}^{n}$ for some $(n-1)$ -dimensional subspace $E\subset\mathbb{F}^{n}$ . (Equivalently, either all matrices in $\mathcal{M}$ have row space $E$ , or they all have column space $E$ .) We may then choose $A\in\textnormal{SL}_{d}(\mathbb{F})$ such that either $A\mathcal{M}$ or $A\mathcal{M}^{t}$ is the space of matrices with zeros in the first row, which means that $(\alpha_{i}(A^{-1}x))_{i\in[n]}$ or $(\alpha_{i}(A^{-1}x^{t}))_{i\in[n]}$ is a basis for $R_{1},$ respectively. Indeed, let $A$ map $E$ to the subspace $E^{\prime}\subseteq\mathbb{F}^{n}$ spanned by the standard basis vectors $e_{2},\ldots,e_{n}$ , and note that $A\mathcal{M}=A(E\otimes\mathbb{F}^{n})=\operatorname{Span}\{Auv^{t}:u\in E,v% \in\mathbb{F}^{n}\}=E^{\prime}\otimes\mathbb{F}^{n}$ , as desired. $\hfill\blacktriangleleft$

Now we are ready to prove our main result in this section.

Proof of Theorem 9.

We have already proved that the slice rank of $\mathrm{det}_{n}$ equals $n .$ Let $\mathrm{det}_{n}=\sum_{i=1}^{n}\alpha_{i}g_{i}$ be a slice rank decomposition with $n$ summands. By Proposition 10, there exists $A\in\textnormal{SL}_{n}(\mathbb{F})$ such that either $\alpha_{i}(Ax)$ or $\alpha_{i}(Ax^{t})$ is a basis for $R_{1}.$ Note that the determinant is invariant under the invertible linear maps $x\mapsto x^{t}$ and $x\mapsto Ax$ (for any $A\in\textnormal{SL}_{n}(\mathbb{F})$ ), so this constitutes a symmetric reduction. Let $(\vec{\alpha^{\prime}},\vec{g})$ , with $\alpha^{\prime}_{i}=\alpha_{i}\circ A$ for every $i$ , be the corresponding decomposition of $\mathrm{det}_{n}$ , which is thus equivalent to our initial decomposition. Now, if $(\vec{\beta},\vec{h})$ denotes the Laplace expansion along the first row, then we have that both $\vec{\alpha^{\prime}}$ and $\vec{\beta}$ are bases for $R_{1}$ . Applying Corollary 8, we deduce that they are equivalent, which, by transitivity, completes the proof. $\hfill\blacktriangleleft$

3 Partition rank of the determinant

In this section we prove nontrivial lower and upper bounds on $\textnormal{prk}(\mathrm{det}_{n})$ , the partition rank of the determinant, when viewed as a multilinear function in the rows of a matrix. We explain why current techniques fail to obtain any nontrivial lower bound and also why our lower bound cannot be improved even with our new argument.

3.1 Partition rank lower bound

Our proof of the lower bound will proceed by repeatedly finding an assignment that zeros out at least one term in the expansion. It crucially uses the highly symmetric nature of the determinant. We will need the following simple lemma.

Lemma 12.

Let $\vec{Q}\colon(\mathbb{F}^{n})^{k}\to\mathbb{F}^{\ell}$ be a $k$ -linear map with $k+\ell\leq n$ . Then there exist linearly independent $v_{1},\ldots,v_{k}\in\mathbb{F}^{n}$ such that $\vec{Q}(v_{1},\ldots,v_{k})=0$ .

Proof.

Let $v_{1},\ldots,v_{k-1}\in\mathbb{F}^{n}$ be any $k-1$ linearly independent vectors. Consider the restriction $L(x)=\vec{Q}(v_{1},\ldots,v_{k-1},x)$ , which is a linear map $L\colon\mathbb{F}^{n}\to\mathbb{F}^{\ell}$ . We have $\dim\ker(L)\geq n-\ell\geq k$ , by assumption. Thus, there exists $v_{k}\in\ker(L)\setminus\operatorname{Span}\{v_{1},\ldots,v_{k-1}\}$ . The vectors $v_{1},\ldots,v_{k}$ are linearly independent and satisfy $\vec{Q}(v_{1},\ldots,v_{k})=L(v_{k})=0$ , as needed. $\hfill\blacktriangleleft$

We introduce one more piece of useful notation. If $T\colon(\mathbb{F}^{n})^{d}\to\mathbb{F}$ is a multilinear form, $k<d$ , and $v_{1},\ldots,v_{k}\in\mathbb{F}^{n}$ are fixed, then $T[v_{1},\ldots,v_{k}]:(\mathbb{F}^{n})^{d-k}\to\mathbb{F}$ is the multilinear form obtained by fixing the first $k$ vectors in $T .$ We can now proceed with our proof of the lower bound. In everything that follows, $\lg(x)$ stands for $\log_{2}(x)$ .

Theorem 13.

$\textnormal{prk}(\mathrm{det}_{n})\geq\lg(n)+1$ .

Proof.

This follows by induction on $n$ from the statement that there exists some $n/2\leq m<n$ with $\textnormal{prk}(\mathrm{det}_{n})>\textnormal{prk}(\mathrm{det}_{m}).$ Indeed,

\textnormal{prk}(\mathrm{det}_{n})>\textnormal{prk}(\mathrm{det}_{m})\geq% \lceil\lg(m)\rceil+1\geq\lceil\lg(n/2)\rceil+1\geq\lceil\lg(n)\rceil.

To prove this statement, consider a partition rank decomposition of $\mathrm{det}_{n}$ of minimal length $\mathrm{det}_{n}=\sum_{i=1}^{r}Q_{i}R_{i},$ where for each $i$ , $Q_{i}$ and $R_{i}$ are multilinear forms in disjoint sets of variable vectors. Let $I_{i}\subset[n]$ correspond to the subset of vector variables that $Q_{i}\in(\mathbb{F}^{n})^{|I_{i}|}\to\mathbb{F}$ depends on (so $|I_{i}|=\deg(Q_{i})$ , and $R_{i}$ depends on $I_{i}^{c}:=[n]\setminus I_{i}$ ). We choose our notation so that $|I_{i}|\leq n/2$ for all $i\in[r]$ , and $1\in I_{i}$ if $|I_{i}|=n/2$ (as a tiebreaker).

Let $I$ be a minimal set in $\{I_{i}\}_{i\in[r]}$ , and denote $k=|I|\leq n/2.$ Assume without loss of generality that $I=[k],$ applying a permutation to the rows if necessary. Suppose that $I_{1}=\cdots=I_{\ell}=[k],$ and $I_{i}\neq[k]$ for all $i>\ell.$ We may assume that $k+r\leq n$ since otherwise we are done by

\textnormal{prk}(\mathrm{det}_{n})=r>n-k\geq\textnormal{prk}(\mathrm{det}_{n-k% }).

Applying lemma 12 to the multilinear map $(Q_{1},\ldots,Q_{\ell})\colon(\mathbb{F}^{n})^{k}\to\mathbb{F}^{\ell},$ we deduce that there exist linearly independent $v_{1},\ldots,v_{k}$ with $Q_{i}(v_{1},\ldots,v_{k})=0$ for all $i\in[\ell].$ Let $A\in\textnormal{SL}_{n}(\mathbb{F})$ be a matrix with $Ae_{i}=v_{i}$ for $i=1,\ldots,k,$ where $e_{i}$ are the standard basis vectors. Note that

\mathrm{det}_{n}(x_{1},\ldots,x_{n})=\mathrm{det}_{n}(Ax_{1},\ldots,Ax_{n})=% \sum_{i=1}^{r}(Q_{i}\circ A)\cdot(R_{i}\circ A)

so that we may assume without loss of generality that $v_{i}=e_{i}$ for $i=1,\ldots,k.$

By the minimality of $I$ and our convention for choosing the $I_{i},$ we get that for any $i>\ell,$ both $I_{i}\nsubseteq[k]$ and also $[n]\setminus I_{i}\nsubseteq[k].$ Therefore,

\mathrm{det}_{n-k}=\mathrm{det}_{n}[e_{1},\ldots,e_{k}]=\sum_{i=\ell+1}^{r}(Q_% {i}R_{i})[e_{1},\ldots,e_{k}]

is a partition rank decomposition of length $r-\ell.$ Thus,

\textnormal{prk}(\mathrm{det}_{n-k})\leq r-\ell<r=\textnormal{prk}(\mathrm{det% }_{n}).

This completes the proof of the theorem, recalling that $n-k\geq n/2.$ $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 14.

Existing techniques for lower-bounding the partition rank or the slice rank of tensors [25, 22] proceed by showing that $\textnormal{prk}(T)\geq\textnormal{prk}(T[u])$ for a single well-chosen $u\in\mathbb{F}^{n}.$ For the determinant this inductively gives the trivial inequality $\textnormal{prk}(\mathrm{det}_{n})\geq\textnormal{prk}(\mathrm{det}_{2})=2.$ Another known approach is via the inequality $\textnormal{prk}(T)\geq\textnormal{grk}(T)$ [14]. In our case $\textnormal{grk}(\mathrm{det}_{n})=2$ for all $n\geq 2$ , so this again yields the trivial bound $\textnormal{prk}(\mathrm{det}_{n})\geq 2.$

On the other hand, our strategy involves (carefully) fixing many – potentially $n/2$ – of the $n$ vector variables at each step. We note that this novel proof strategy can never yield a super-logarithmic lower bound. This is because such an assignment might zero out only a single summand in the expansion, at the the expense of reducing $\mathrm{det}_{n}$ to $\mathrm{det}_{n/2}.$ Thus, repeating such an argument will always result in a partition rank lower bound of roughly $\lg(n)$ .

$\blacktriangleright$ Remark 15.

For small values of $n$ , the bound $\textnormal{prk}(\mathrm{det}_{n})\geq\lceil\lg(n)\rceil+1$ in Theorem 13 implies $\textnormal{prk}(\mathrm{det}_{2})=2$ , $\textnormal{prk}(\mathrm{det}_{3})=3$ , and $\textnormal{prk}(\mathrm{det}_{4})\geq 3$ .

Next, we show that our lower bound is tight for $\mathrm{det}_{4}$ .

3.2 Partition rank upper bound

Here we demonstrate that, unlike for slice rank, the partition rank of the determinant is not always full. We do so by presenting a (perhaps surprising) “quadratic” expansion of the determinant of $4\times 4$ matrices, quite unlike the Laplace expansion.

For an $n\times n$ matrix $A$ and subsets $I,J\subseteq[n]$ , we denote by $A_{I,J}$ the $|I|\times|J|$ submatrix of $A$ on the rows indexed by $I$ and the columns indexed by $J$ .¹¹¹¹11Put differently, $A_{I,J}$ removes from $A$ all rows in $[n]\setminus I$ and all columns in $[n]\setminus J$ .

Theorem 16.

For any $4\times 4$ matrix $A$ over any field,

\displaystyle\begin{split}\mathrm{det}(A)&=\bigg(\sum_{J}\mathrm{det}(A_{\{1,2% \},J})\bigg)\bigg(\sum_{J}\mathrm{det}(A_{\{3,4\},J})\bigg)\\ &-\bigg(\sum_{J}\mathrm{det}(A_{\{1,3\},J})\bigg)\bigg(\sum_{J}\mathrm{det}(A_% {\{2,4\},J})\bigg)\\ &+\bigg(\sum_{J}\mathrm{det}(A_{\{1,4\},J})\bigg)\bigg(\sum_{J}\mathrm{det}(A_% {\{2,3\},J})\bigg),\end{split}

(1)

where all summations are over $J\in\binom{[4]}{2}$ (all choices of $2$ out of the $4$ columns).

Corollary 17.

Over any field, $\textnormal{prk}(\mathrm{det}_{4})=3$ .

This result is partially inspired by the results of Green-Tao [9] and Lovett-Meshulam-Samorodnitsky [17], who showed that $S_{4}$ , the elementary symmetric polynomial of degree $4$ , is a counterexample to the naive version of the inverse conjecture for Gowers norms in small characteristic, namely over $\mathbb{F}_{2}$ . The connection to our question comes from the fact that over $\mathbb{F}_{2},$ the multilinear form corresponding to $S_{4}$ in four variables is precisely the $4\times 4$ determinant.

As a quick example for computing the determinant using (1), consider the simple case of diagonal matrices:

\mathrm{det}\begin{pmatrix}a&0&0&0\\ 0&b&0&0\\ 0&0&c&0\\ 0&0&0&d\end{pmatrix}=(ab)(cd)-(ac)(bd)+(ad)(bc).

For the interested reader, we show below in Section 3.2.1 that our expansion (1) is genuinely different from the Laplace expansion and the generalized Laplace expansions.

At the core of our upper bound is an identity relating four-dimensional and two-dimensional Levi-Civita symbols. The $d$ -dimensional Levi-Civita symbol, for $i_{1},\ldots,i_{d}\in[d]$ , is

\epsilon_{i_{1},\ldots,i_{d}}=\begin{cases}1&(i_{1},\ldots,i_{d})\text{ is a % permutation of even sign}\\ -1&(i_{1},\ldots,i_{d})\text{ is a permutation of odd sign}\\ 0&\text{otherwise}\end{cases}.

Here, $(i_{1},\ldots,i_{d})$ is the (not necessarily permutation) map $1\mapsto i_{1},\ldots,d\mapsto i_{d}$ . The Levi-Civita symbol naturally generalizes to arbitrary integers $i_{1},\ldots,i_{d}$ , which we will use in the $2$ -dimensional case; namely, for any $i, j$ ,

\epsilon_{i,j}=\begin{cases}1&i<j\\ -1&i>j\\ 0&i=j\end{cases}.

Proof of Theorem 16.

First, we write out each determinant appearing in (1):

\displaystyle\begin{split}\mathrm{det}(A)&=\Big(\sum_{i,j}\epsilon_{i,j}a_{1,i% }a_{2,j}\Big)\Big(\sum_{i,j}\epsilon_{i,j}a_{3,i}a_{4,j}\Big)\\ &-\Big(\sum_{i,j}\epsilon_{i,j}a_{1,i}a_{3,j}\Big)\Big(\sum_{i,j}\epsilon_{i,j% }a_{2,i}a_{4,j}\Big)\\ &+\Big(\sum_{i,j}\epsilon_{i,j}a_{1,i}a_{4,j}\Big)\Big(\sum_{i,j}\epsilon_{i,j% }a_{2,i}a_{3,j}\Big),\end{split}

where all summations are over $i,j\in[4]$ (in fact, can assume $i\neq j$ as $\epsilon_{i,i}=0$ ). Comparing the coefficients of $a_{1,i}a_{2,j}a_{3,k}a_{4,\ell}$ in both sides for each $(i,j,k,\ell)$ , our expansion turns out to be equivalent to the following “ $4$ -to- $2$ ” identity of Levi-Civita symbols: for all $i,j,k,w\in[4]$ ,

\epsilon_{i,j,k,\ell}=\epsilon_{i,j}\epsilon_{k,\ell}-\epsilon_{i,k}\epsilon_{% j,\ell}+\epsilon_{i,\ell}\epsilon_{j,k}.

(2)

A direct inspection reveals that if the identity holds for $(i,j,k,\ell)$ , then it also holds after transposing any two indices. For example,

\epsilon_{j,i,k,\ell}=-\epsilon_{i,j,k,\ell}=-(\epsilon_{i,j}\epsilon_{k,\ell}% -\epsilon_{i,k}\epsilon_{j,\ell}+\epsilon_{i,\ell}\epsilon_{j,k})=\epsilon_{j,% i}\epsilon_{k,\ell}-\epsilon_{j,k}\epsilon_{i,\ell}+\epsilon_{j,\ell}\epsilon_% {i,k}.

Since all permutations are obtained by a sequence of transpositions, we may apply any desired permutation to $i,j,k,\ell$ in the course of our proof.

If $i,j,k,\ell$ are not all distinct then by the above property we may assume $i=j$ . Then the left hand side of equation (2) is $\epsilon_{i,i,k,\ell}=0$ , since $(i,i,k,\ell)$ is not a permutation, and the right hand side is $-\epsilon_{i,k}\epsilon_{i,\ell}+\epsilon_{i,\ell}\epsilon_{i,k}=0$ also.

If $i,j,k,\ell$ are all distinct, then because transpositions generate the group of permutations, we may assume $(i,j,k,\ell)=(1,2,3,4).$ In this case, the left hand side of equation (2) equals $1$ , and the right hand side equals

\epsilon_{1,2}\epsilon_{3,4}-\epsilon_{1,3}\epsilon_{2,4}+\epsilon_{1,4}% \epsilon_{2,3}=1-1+1=1

as well. This completes the proof. $\hfill\blacktriangleleft$

Proof of Corollary 17.

We have the lower bound $\textnormal{prk}(\mathrm{det}_{4})\geq 3$ by Remark 15, and the upper bound $\textnormal{prk}(\mathrm{det}_{4})\leq 3$ from Theorem 16. $\hfill\blacktriangleleft$

3.2.1 Comparison to other expansions

For a $4\times 4$ matrix $A$ , the $2$ -row Laplace expansion, along rows $I=\{1,2\}$ (say), is

\mathrm{det}(A)=\sum_{J}(-1)^{j_{1}+j_{2}-1}\mathrm{det}(A_{I,J})\mathrm{det}(% A_{I^{c},J^{c}}),

(3)

where the summation is over all $J\in\binom{[4]}{2}$ (all choices of $2$ out of the $4$ columns).¹²¹²12The coefficients can be written more generality as $(-1)^{\sum_{\ell}i_{\ell}+j_{\ell}}$ . To formally separate our expansion (1) from the Laplace expansion or the generalized Laplace expansion (3), we extend both the preorder of Definition 4 and the notion of equivalence in Definition 6 to partition rank in the obvious way. Note that this preorder preserves degrees, and so our quadratic expansion (1) is certainly not equivalent to the slice rank decomposition given by the Laplace expansion along a single row.

Lemma 18.

The expansions (1) and (3) are not equivalent.

Proof.

Let $(\vec{g},\vec{h})$ denote Laplace expansion along any two rows $I$ , given by an equation of the form (3). This partition rank decomposition of $\mathrm{det}_{4}$ has $\binom{4}{2}=6$ summands. We claim that the same is true whenever $(\vec{q},\vec{r})\lesssim(\vec{g},\vec{h})$ is another partition rank decomposition. Establishing this claim will complete the proof.

First, note that the quadratics in $\vec{g}$ (i.e. the six $2\times 2$ minors $\mathrm{det}(A_{I,J})$ ) are linearly independent. Therefore, the decomposition $(\vec{g},\vec{h})$ cannot be shortened by a linear reduction or a syzygy reduction. It thus remains to consider symmetric reductions. We claim that any linear map $T:M_{4}(\mathbb{F})\to M_{4}(\mathbb{F})$ satisfying $\mathrm{det}_{4}\circ T=\mathrm{det}_{4}$ must be an isomorphism. This would imply that the entries of $\vec{g}\circ T$ remain linearly independent quadratics, as needed. To prove this claim, suppose for contradiction that there exists a matrix $0\neq A\in M_{4}(\mathbb{F})$ satisfying $T(A)=0.$ Let $C\in M_{4}(\mathbb{F})$ be any invertible matrix that shares a row with $A .$ Then

0\neq\mathrm{det}_{4}(C)=\mathrm{det}_{4}(T(C))=\mathrm{det}_{4}(T(C-A))=% \mathrm{det}_{4}(C-A)=0,

where the construction of $C$ was used in the first inequality and the last equality, and the linearity of $T$ was used in the second equality. This completes the proof. $\hfill\blacktriangleleft$

As an aside, our expansion (1) is quite unremarkable as an arithmetic formula, when compared to the Laplace expansion or to the two-row Laplace expansion (3). For example, its (leaf) size is $144$ ( $24$ variable occurrences in each of the $6$ factors), compared to $64$ for the Laplace expansion, and $48$ for the generalized Laplace expansion. It also does not improve on its competitors in terms of the number of products, for example. Moreover, when applied on random real matrices, it typically produces intermediate reals of much larger magnitude than the original entries (as each of its factors has as many as $12$ monomials). Nevertheless, if we measure these expansions by their partition rank, then (1) is strictly better, and indeed best possible.

4 Separating partition and analytic rank

In this section we prove an asymptotic separation between partition rank and analytic rank, using Theorem 2. On the other hand, we show that one cannot obtain a better separation – or really any separation at all – by considering random multilinear forms, even when they are conditioned to have high partition rank.

4.1 Asymptotic separation

We compute a tight estimate for the probability that $m$ independent, uniformly random vectors in $\mathbb{F}_{q}^{n}$ ( $\mathbb{F}_{q}$ is the finite field of size $q$ ) are linearly dependent.

Lemma 19.

For any $m\leq n$ ,

1\leq\Pr_{A\in\mathbb{F}_{q}^{m\times n}}[\textnormal{rk}(A)<m]/q^{-(n-m+1)}<1% +1/(q-1).

Proof.

The number of $m$ -tuples $(v_{1},\ldots,v_{m})$ of linearly independent vectors in $\mathbb{F}_{q}^{n}$ is, as is well known, $\prod_{i=0}^{m-1}(q^{n}-q^{i})$ , since each $v_{i}$ ( $i=1,\ldots,m$ ) can be any vector in $\mathbb{F}_{q}^{n}$ that lies outside the subspace spanned by $v_{1},\ldots,v_{i-1}$ . Thus,

\Pr_{A\in\mathbb{F}_{q}^{m\times n}}[\textnormal{rk}(A)=m]=q^{-mn}\prod_{i=0}^% {m-1}(q^{n}-q^{i})=\prod_{i=0}^{m-1}(1-1/q^{n-i}).

To upper bound this probability, we bound $1-1/q^{n-i}\leq 1$ for every $i<m-1$ ; to lower bound it, we use the generalized Bernoulli’s inequality $\prod_{i}(1-x_{i})\geq 1-\sum_{i}x_{i}$ for $0\leq x_{i}\leq 1$ . We get

1-\sum_{i=0}^{m-1}1/q^{n-i}\leq\Pr_{A\in\mathbb{F}_{q}^{m\times n}}[% \textnormal{rk}(A)=m]\leq 1-1/q^{n-m+1}.

Put $k=n-m+1$ . For the geometric series on the left hand side, we have

\sum_{i=0}^{m-1}1/q^{n-i}=\sum_{i=k}^{n}1/q^{j}<q^{-k}/(1-1/q).

Thus, as desired, $q^{-k}\leq\Pr_{A\in\mathbb{F}_{q}^{m\times n}}[\textnormal{rk}(A)<m]<(1+1/(q-1% ))q^{-k}$ . $\hfill\blacktriangleleft$

Corollary 20.

Over any finite field $\mathbb{F}$ , and for any $n\geq 2$ ,

\lceil{\textnormal{ark}(\mathrm{det}_{n})}\rceil=2.

Proof.

Put $\mathbb{F}=\mathbb{F}_{q}$ . For convenience, write $\mathrm{det}_{n}=\mathrm{det}(A)$ where $A=(a_{i,j})$ is a general $n\times n$ matrix, whose rows are the $n$ variable vectors of $\mathrm{det}_{n}$ . The gradient of $\mathrm{det}_{n}$ with respect to the last row of $A$ is, by the Laplace expansion,

\nabla\mathrm{det}_{n}=\big((-1)^{n+1}\mathrm{det}(A_{n,1}),\ldots,(-1)^{n+n}% \mathrm{det}(A_{n,n})\big),

where $A_{i,j}$ is obtained from $A$ by removing row $i$ and column $j$ . Let $A^{\prime}$ denote the $(n-1)\times n$ matrix obtained from $A$ by removing row $n$ . Then $\nabla\mathrm{det}_{n}(A^{\prime})=0$ if and only if every $(n-1)\times(n-1)$ minor of $A^{\prime}$ is zero, which is equivalent to $\textnormal{rk}(A^{\prime})<n-1$ . In other words,

\Pr[\nabla\mathrm{det}_{n}=0]=\Pr_{A^{\prime}\in\mathbb{F}_{q}^{(n-1)\times n}% }[\textnormal{rk}(A^{\prime})<n-1].

Lemma 19, in the special case $m=n-1$ , says $q^{-2}\leq\Pr[\nabla\mathrm{det}_{n}=0]<c_{q}q^{-2}$ with $c_{q}=q/(q-1)$ . Therefore, $2-\log_{q}c_{q}<\textnormal{ark}(\mathrm{det}_{n})\leq 2$ . Trivially $c_{q}\leq q$ , so $1<\textnormal{ark}(\mathrm{det}_{n})\leq 2$ , that is, $\lceil{\textnormal{ark}(\mathrm{det}_{n})}\rceil=2$ . $\hfill\blacktriangleleft$

Corollary 21.

For any $d\geq 2$ ,

A(d)\geq\frac{\log_{2}(d)+1}{2}\xrightarrow[d\to\infty]{}\infty.

Proof.

Combining Theorem 13 and Corollary 20, we get

A(d)=\max_{\text{$d$-linear }T}\frac{\textnormal{prk}(T)}{\lceil{\textnormal{% ark}(T)}\rceil}\geq\frac{\textnormal{prk}(\mathrm{det}_{d})}{\lceil{% \textnormal{ark}(\mathrm{det}_{d})}\rceil}\geq\frac{\log_{2}(d)+1}{2}.\

$\hfill\blacktriangleleft$

4.2 Random multilinear forms

Denote by $\mathcal{T}_{{n},{d}}(\mathbb{F})$ the set of $d$ -linear forms $T\colon(\mathbb{F}^{n})^{d}\to\mathbb{F}$ . Let $\mathcal{T}_{{n},{d}}^{(r)}(\mathbb{F})$ be the distribution obtained by summing $r$ reducible forms chosen independently and uniformly at random from $\mathcal{T}_{{n},{d}}(\mathbb{F})$ . Clearly, this distribution satisfies $\Pr[\textnormal{prk}(T)\leq r]=1$ , and so $\Pr[\textnormal{ark}(T)\leq r]=1$ . We will prove that, over any finite field $\mathbb{F}$ , the analytic rank of these multilinear forms is roughly $r$ with high probability. Intuitively, this means tensors $T$ with $\textnormal{prk}(T)/\textnormal{ark}(T)>2$ (say) are rare, in the sense that only a $o(1)$ -fraction of them satisfies this inequality, even when the numerator is fixed.

$\blacktriangleright$ Remark 22.

Other properties of random elements of $\mathcal{T}_{{n},{d}}^{(r)}(\mathbb{F})$ were previously studied in [2, 7].

We use the following asymptotic notation in $n$ : $A\sim B$ if¹³¹³13Not to be confused with the probabilistic notation of “distributed as”. $\lim_{n\to\infty}A/B=1$ (that is, $A=(1+o(1))B$ ), $A\gtrsim B$ if $\lim_{n\to\infty}A/B\geq 1$ (that is, $A\geq(1+o(1))B$ ), and $A\lesssim B$ analogously.

Theorem 23.

Let $\mathbb{F}$ be a finite field, $d\geq 2$ , and $\epsilon>0$ . If $r\leq(1-\epsilon)n/2$ then

\mathop{\mathbb{E}}_{T\sim\mathcal{T}_{{d},{n}}^{(r)}(\mathbb{F})}\,% \textnormal{bias}(T)\sim|\mathbb{F}|^{-r}.

Corollary 24.

In the conditions of Theorem 23, for any $c>0$ ,

\Pr_{T\sim\mathcal{T}_{{d},{n}}^{(r)}(\mathbb{F})}[\,r-c\leq\textnormal{ark}(T% )\leq r\,]\gtrsim 1-q^{-c}.

Proof.

Put $\mathbb{F}=\mathbb{F}_{q}$ . By Markov’s inequality on the random variable $\textnormal{bias}(T)\geq 0$ ,

\Pr[\textnormal{ark}(T)\leq r-c]=\Pr[\textnormal{bias}(T)\geq q^{-(r-c)}]\leq q% ^{r-c}\mathop{\mathbb{E}}\textnormal{bias}(T)\sim q^{-c}.\

$\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 25.

Our proof works for an arbitrary finite field $\mathbb{F}$ . As for an infinite field $\mathbb{F}$ , an essentially identical argument shows that a generic $T\in\mathcal{T}_{{d},{n}}^{(r)}(\mathbb{F})$ has geometric rank $r .$

We begin with some auxiliary lemmas. Henceforth, we say that $x\in(\mathbb{F}^{n})^{d}$ is nontrivial if $x^{(i)}\neq 0$ for every $i$ . We will also need the following observation about evaluating a random multilinear form.

Lemma 26.

Let $T\in\mathcal{T}_{{d},{n}}$ be chosen uniformly at random. For any $x\in(\mathbb{F}^{n})^{d}$ nontrivial, $T(x)$ is distributed uniformly in $\mathbb{F}$ .

Proof.

We have $T(x^{1},\ldots,x^{(d)})=\sum_{i_{1},\ldots,i_{d}}c_{i_{1},\ldots,i_{d}}x^{(1)}% _{i_{1}}\cdots x^{(d)}_{i_{d}}$ with $c_{i_{1},\ldots,i_{d}}\in\mathbb{F}$ chosen uniformly at random. Abbreviate $X_{i_{1},\ldots,i_{d}}=x^{(1)}_{i_{1}}\cdots x^{(d)}_{i_{d}}$ . Since $x$ is nontrivial, for every $1\leq i\leq d$ there is $1\leq j_{i}\leq n$ such that $x^{i}_{j_{i}}\neq 0$ . Put $J=(j_{1},\ldots,j_{d})$ . We deduce that $T(x)\in\mathbb{F}$ is distributed uniformly since $c_{J}X_{J}$ is: for every $y\in\mathbb{F}$ , we have $T(x)=y$ if and only if $c_{J}=(y-\sum_{I\neq J}c_{I}X_{I})/X_{J}$ . $\hfill\blacktriangleleft$

We will later use the following elementary observations to bound the effects of low probability (“bad”) events.

Lemma 27.

Let $A, B, E$ be finite sets. If $|A\setminus E|=|B\setminus E|$ then $\big||A|-|B|\big|\leq|E|$ .

Proof.

We have $|A|=|A\setminus E|+|A\cap E|=|B\setminus E|+|A\cap E|$ by assumption. This implies the bound $|A|\geq|B\setminus E|\geq|B|-|E|$ , and the bound $|A|\leq|B|+|E|$ . $\hfill\blacktriangleleft$

Lemma 28.

For events $A$ and $E$ , $\big|\Pr[A]-\Pr[A|E^{c}]\big|\leq\Pr[E]$ .

Proof.

We prove the identity $\Pr[A]-\Pr[A|E^{c}]=\Pr[A\cap E]-\Pr[E]\Pr[A|E^{c}]$ , from which the desired bounds follow since $0\leq\Pr[A\cap E]\leq\Pr[E]$ . By the law of total probability, $\Pr[A]-\Pr[A\cap E^{c}]=\Pr[A\cap E]$ , and $\Pr[A\cap E^{c}]=\Pr[A|E^{c}](1-\Pr[E])$ , so the desired identity follows. $\hfill\blacktriangleleft$

We are now ready to give the proof.

Proof of Theorem 23.

Put $V=\mathbb{F}^{n}$ . Henceforth, for $T\sim\mathcal{T}_{{d},{n}}^{(r)}(\mathbb{F})$ with a given partition-rank decomposition $T=\sum_{i=1}^{r}R_{i}S_{i}$ , we let $R_{i}$ , for concreteness, depend on $x^{(d)}$ (so $S_{i}$ does not). For $T\sim\mathcal{T}_{{d},{n}}$ and $x=(x^{(1)},\ldots,x^{(d-1)})\in V^{d-1}$ , we define the events

A=\{(x,T)|\nabla T(x)=0\},

B=\{(x,T)|S_{1}(x)=\cdots=S_{r}(x)=0\},

E=\{(x,T)|\nabla R_{1}(x),\ldots,\nabla R_{r}(x)\text{ are linearly dependent}\}.

We claim that $A\setminus E=B\setminus E$ . Indeed, observe that $\nabla T(x)=\sum_{i=1}^{r}S_{i}(x)\nabla R_{i}(x)$ . Thus, for $x$ fixed, $\nabla T(x)\in\mathbb{F}^{n}$ can be written as a linear combination of $\nabla R_{1}(x),\ldots,\nabla R_{r}(x)\in\mathbb{F}^{n}$ with respective coefficients $S_{1}(x),\ldots,S_{r}(x)\in\mathbb{F}$ . Therefore, if $(x,T)\notin E$ then we have the equivalence $(x,T)\in A$ if and only if $(x,T)\in B$ . That is, $A\setminus E=B\setminus E$ , as claimed. Therefore, we may apply Lemma 27 to deduce that

\big|\Pr[A]-\Pr[B]\big|\leq\Pr[E].

(4)

Note that $\Pr[A]=\mathop{\mathbb{E}}_{T}\Pr_{x}[A|T]=\mathop{\mathbb{E}}_{T}\textnormal{% bias}(T)$ . We will prove that

\Pr[B]\sim q^{-r},

(5)

and that

\Pr[E]\leq 3q^{-(n-r+1)}.

(6)

To see why these suffice, observe that (4) implies, assuming (6), that

\big|\mathop{\mathbb{E}}_{T}\textnormal{bias}(T)/q^{-r}-\Pr[B]/q^{-r}\big|\leq 3% q^{-(n-2r+1)}\leq 3q^{-(r+\epsilon n)},

where the last inequality uses the statement’s assumption $r\leq(1-\epsilon)n/2$ . Assuming (5), and taking the limit as $n\to\infty$ , we get $\mathop{\mathbb{E}}_{T}\textnormal{bias}(T)\sim q^{-r}$ , as desired.

It therefore remains to prove (5) and (6). We will use the event $F=\{(x,T)|x\text{ is trivial}\}$ . For (5), recall that the coefficients of $S_{1},\ldots,S_{r}$ are chosen independently and uniformly at random. By Lemma 26, for any nontrivial $x\in V^{d}$ we have that $S_{1}(x),\ldots,S_{r}(x)$ are $r$ independent, uniformly random scalars in $\mathbb{F}$ . Therefore, $\Pr[B|F^{c}]=q^{-r}$ . By Lemma 28, $\big|\Pr[B]-\Pr[B|F^{c}]\big|\leq\Pr[F]=q^{-(d-1)n}$ , which thus proves (5).

For (6), observe that, since the coefficients of $R_{1},\ldots,R_{r}$ are chosen independently and uniformly at random (from $\mathbb{F}$ ), so are the coefficients of $\nabla R_{1},\ldots,\nabla R_{r}$ . By Lemma 26, for any nontrivial $x\in V^{d}$ we have that $\nabla R_{1}(x),\ldots,\nabla R_{r}(x)$ are $r$ independent, uniformly random vectors in $\mathbb{F}^{n}$ . Therefore, by Lemma 19, $\Pr[E|F^{c}]\leq 2q^{-(n-r+1)}$ . By Lemma 28, $\big|\Pr[E]-\Pr[E|F^{c}]\big|\leq\Pr[F]=q^{-(d-1)n}$ , which thus proves (6). As explained above, this completes the proof. $\hfill\blacktriangleleft$

References

[1] Karim Adiprasito, David Kazhdan, and Tamar Ziegler. On the schmidt and analytic ranks for trilinear forms, 2021. arXiv:2102.03659.
[2] Edoardo Ballico, Arthur Bik, Alessandro Oneto, and Emanuele Ventura. Strength and slice rank of forms are generically equal. Israel Journal of Mathematics, 254:275–291, 2023.
[3] Qiyuan Chen and Ke Ye. Stability of ranks under field extensions, 2024. arXiv:2409.04034.
[4] Alex Cohen and Guy Moshkovitz. Structure vs. randomness for bilinear maps. Discrete Analysis, 12, 2022. Conference version in 53rd ACM STOC 2021, pp. 800–808.
[5] Alex Cohen and Guy Moshkovitz. Partition and analytic rank are equivalent over large fields. Duke Mathematical Journal, 172:2433–2470, 2023.
[6] Harm Derksen. On the nuclear norm and the singular value decomposition of tensors. Foundations of Computational Mathematics, 16:779–811, 2016. doi:10.1007/S10208-015-9264-X.
[7] Daniel Erman. Matrix factorizations of generic polynomials, 2021. arXiv:2112.08864.
[8] W. T. Gowers and Julia Wolf. Linear forms and higher-degree uniformity for functions on $\mathbb{F}_{p}^{n}$ . Geometric and Functional Analysis, 21:36–69, 2011.
[9] Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the gowers norms. Contributions to Discrete Mathematics, 4:1–36, 2009.
[10] Oliver Janzer. Polynomial bound for the partition rank vs the analytic rank of tensors. Discrete Analysis, 7, 2020.
[11] Thomas Karam. Small sunflowers and the structure of slice rank decompositions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287, pages 67:1–22, 2024. doi:10.4230/LIPIcs.ITCS.2024.67.
[12] David Kazhdan, Amichai Lampert, and Alexander Polishchuk. Schmidt rank and singularities. Ukrainian Mathematical Journal, 75:1420–1442, 2024.
[13] David Kazhdan and Tamar Ziegler. Approximate cohomology. Selecta Mathematica, 24:499–509, 2018.
[14] Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric rank of tensors and subrank of matrix multiplication. In 35th Computational Complexity Conference (CCC 2020), volume 35, pages 1–21, 2020. Also in Discrete Analysis 1 (2023). doi:10.4230/LIPIcs.CCC.2020.35.
[15] J. M. Landsberg and Zach Teitler. On the ranks and border ranks of symmetric tensors. Foundations of Computational Mathematics, 10:339–366, 2010. doi:10.1007/S10208-009-9055-3.
[16] Shachar Lovett. The analytic rank of tensors and its applications. Discrete Analysis, 7, 2019.
[17] Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky. Inverse conjecture for the gowers norm is false. Theory of Computing, 7:131–145, 2011. doi:10.4086/TOC.2011.V007A009.
[18] Roy Meshulam. On the maximal rank in a subspace of matrices. Quarterly Journal of Mathematics, 36:225–229, 1985.
[19] Luka Milićević. Polynomial bound for partition rank in terms of analytic rank. Geometric and Functional Analysis, 29:1503–1530, 2019.
[20] Guy Moshkovitz and Daniel Zhu. Quasi-linear relation between partition and analytic rank, 2022. Submitted. arXiv:2211.05780.
[21] Guy Moshkovitz and Daniel Zhu. Uniform stability of ranks, 2024. arXiv:2411.03412.
[22] Eric Naslund. The partition rank of a tensor and k-right corners in $\mathbb{F}_{q}^{n}$ . Journal of Combinatorial Theory, Series A, 174:105190, 2020.
[23] Will Sawin and Terence Tao. Notes on the “slice rank” of tensors, 2016. URL: https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors.
[24] Wolfgang M. Schmidt. The density of integer points on homogeneous varieties. Acta Mathematica, 154:243–296, 1985.
[25] Terence Tao. A symmetric formulation of the croot–lev–pach–ellenberg–gijswijt capset bound, 2016. URL: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.
[26] usr0192. Regular sequence and relations, 2020. URL: https://math.stackexchange.com/questions/3559651/regular-sequence-and-relations.

[bib.bib1] [1] Karim Adiprasito, David Kazhdan, and Tamar Ziegler. On the schmidt and analytic ranks for trilinear forms, 2021. arXiv:2102.03659.

[bib.bib2] [2] Edoardo Ballico, Arthur Bik, Alessandro Oneto, and Emanuele Ventura. Strength and slice rank of forms are generically equal. Israel Journal of Mathematics, 254:275–291, 2023.

[bib.bib3] [3] Qiyuan Chen and Ke Ye. Stability of ranks under field extensions, 2024. arXiv:2409.04034.

[bib.bib4] [4] Alex Cohen and Guy Moshkovitz. Structure vs. randomness for bilinear maps. Discrete Analysis, 12, 2022. Conference version in 53rd ACM STOC 2021, pp. 800–808.

[bib.bib5] [5] Alex Cohen and Guy Moshkovitz. Partition and analytic rank are equivalent over large fields. Duke Mathematical Journal, 172:2433–2470, 2023.

[bib.bib6] [6] Harm Derksen. On the nuclear norm and the singular value decomposition of tensors. Foundations of Computational Mathematics, 16:779–811, 2016. doi:10.1007/S10208-015-9264-X.

[bib.bib7] [7] Daniel Erman. Matrix factorizations of generic polynomials, 2021. arXiv:2112.08864.

[bib.bib8] [8] W. T. Gowers and Julia Wolf. Linear forms and higher-degree uniformity for functions on $\mathbb{F}_{p}^{n}$ . Geometric and Functional Analysis, 21:36–69, 2011.

[bib.bib9] [9] Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the gowers norms. Contributions to Discrete Mathematics, 4:1–36, 2009.

[bib.bib10] [10] Oliver Janzer. Polynomial bound for the partition rank vs the analytic rank of tensors. Discrete Analysis, 7, 2020.

[bib.bib11] [11] Thomas Karam. Small sunflowers and the structure of slice rank decompositions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287, pages 67:1–22, 2024. doi:10.4230/LIPIcs.ITCS.2024.67.

[bib.bib12] [12] David Kazhdan, Amichai Lampert, and Alexander Polishchuk. Schmidt rank and singularities. Ukrainian Mathematical Journal, 75:1420–1442, 2024.

[bib.bib13] [13] David Kazhdan and Tamar Ziegler. Approximate cohomology. Selecta Mathematica, 24:499–509, 2018.

[bib.bib14] [14] Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric rank of tensors and subrank of matrix multiplication. In 35th Computational Complexity Conference (CCC 2020), volume 35, pages 1–21, 2020. Also in Discrete Analysis 1 (2023). doi:10.4230/LIPIcs.CCC.2020.35.

[bib.bib15] [15] J. M. Landsberg and Zach Teitler. On the ranks and border ranks of symmetric tensors. Foundations of Computational Mathematics, 10:339–366, 2010. doi:10.1007/S10208-009-9055-3.

[bib.bib16] [16] Shachar Lovett. The analytic rank of tensors and its applications. Discrete Analysis, 7, 2019.

[bib.bib17] [17] Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky. Inverse conjecture for the gowers norm is false. Theory of Computing, 7:131–145, 2011. doi:10.4086/TOC.2011.V007A009.

[bib.bib18] [18] Roy Meshulam. On the maximal rank in a subspace of matrices. Quarterly Journal of Mathematics, 36:225–229, 1985.

[bib.bib19] [19] Luka Milićević. Polynomial bound for partition rank in terms of analytic rank. Geometric and Functional Analysis, 29:1503–1530, 2019.

[bib.bib20] [20] Guy Moshkovitz and Daniel Zhu. Quasi-linear relation between partition and analytic rank, 2022. Submitted. arXiv:2211.05780.

[bib.bib21] [21] Guy Moshkovitz and Daniel Zhu. Uniform stability of ranks, 2024. arXiv:2411.03412.

[bib.bib22] [22] Eric Naslund. The partition rank of a tensor and k-right corners in $\mathbb{F}_{q}^{n}$ . Journal of Combinatorial Theory, Series A, 174:105190, 2020.

[bib.bib23] [23] Will Sawin and Terence Tao. Notes on the “slice rank” of tensors, 2016. URL: https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors.

[bib.bib24] [24] Wolfgang M. Schmidt. The density of integer points on homogeneous varieties. Acta Mathematica, 154:243–296, 1985.

[bib.bib25] [25] Terence Tao. A symmetric formulation of the croot–lev–pach–ellenberg–gijswijt capset bound, 2016. URL: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.

[bib.bib26] [26] usr0192. Regular sequence and relations, 2020. URL: https://math.stackexchange.com/questions/3559651/regular-sequence-and-relations.

Slice Rank and Partition Rank of the Determinant

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Theorem 1 (see Theorem 9).

Theorem 2 (see Theorem 13).

Theorem 3 (see Theorem 16).

Problem 0.

Conjecture 1.

1.1 Structure versus randomness

Theorem 4 (see Theorem 23).

Corollary 2 (See Corollary 21).

Problem 2.

2 Slice rank of the determinant

Definition 3.

2.1 Equivalence for slice rank decompositions

Definition 4.

▶ Remark 5.

Definition 6.

Lemma 7.

Proof.

Corollary 8.

2.2 Slice rank decompositions of the determinant

Theorem 9.

Proposition 10.

Lemma 11 (Meshulam).

Proof of Proposition 10.

Proof of Theorem 9.

3 Partition rank of the determinant

3.1 Partition rank lower bound

Lemma 12.

Proof.

Theorem 13.

Proof.

▶ Remark 14.

▶ Remark 15.

3.2 Partition rank upper bound

Theorem 16.

Corollary 17.

Proof of Theorem 16.

Proof of Corollary 17.

3.2.1 Comparison to other expansions

Lemma 18.

Proof.

4 Separating partition and analytic rank

4.1 Asymptotic separation

Lemma 19.

Proof.

Corollary 20.

Proof.

Corollary 21.

Proof.

4.2 Random multilinear forms

▶ Remark 22.

Theorem 23.

Corollary 24.

Proof.

▶ Remark 25.

Lemma 26.

Proof.

Lemma 27.

Proof.

Lemma 28.

Proof.

Proof of Theorem 23.

References

$\blacktriangleright$ Remark 5.

$\blacktriangleright$ Remark 14.

$\blacktriangleright$ Remark 15.

$\blacktriangleright$ Remark 22.

$\blacktriangleright$ Remark 25.