Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP

Rossman, Benjamin; Zhu, Davidson

doi:10.4230/LIPIcs.ITCS.2026.113

Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC¹ $\neq$ VNP

Benjamin Rossman

Duke University, Durham, NC, USA Davidson Zhu

Duke University, Durham, NC, USA

Abstract

The sum-of-squares (SoS) complexity of a $d$ -multiquadratic polynomial $f$ (quadratic in each of $d$ blocks of $n$ variables) is the minimum $s$ such that $f=\sum_{i=1}^{s}g_{i}^{2}$ with each $g_{i}$ $d$ -multilinear. In the case $d=2$ , Hrubeš, Wigderson and Yehudayoff [13] showed that an $n^{1+\Omega(1)}$ lower bound on the SoS complexity of explicit biquadratic polynomials implies an exponential lower bound for non-commutative arithmetic circuits. In this paper, we establish an analogous connection between general multiquadratic sum-of-squares and commutative arithmetic formulas. Specifically, we show that an $n^{d-o(\log d)}$ lower bound on the SoS complexity of explicit $d$ -multiquadratic polynomials, for any $d=d(n)$ with $\omega(1)\leq d(n)\leq O(\frac{\log n}{\log\log n})$ , would separate the algebraic complexity classes $\mathsf{VNC^{1}}$ and $\mathsf{VNP}$ .

Keywords and phrases:

sum-of-squares, arithmetic formulas

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algebraic complexity theory

Editor:

Shubhangi Saraf

Series and Publisher:

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

1 Introduction

Computational complexity theory aims to categorize computational problems by the amount of time and resources they need. The algebraic complexity classes proposed by Leslie Valiant [31], on the other hand, were created for understanding the tractability of polynomials, as opposed to Boolean functions. Arithmetic circuits, branching programs and formulas are defined as analogs of their Boolean counterparts.

Algebraic complexity classes $\mathsf{VF}\ (=\mathsf{VNC^{1}})\subseteq\mathsf{VBP}\subseteq\mathsf{VP}\ (=% \mathsf{VNC^{2}})\subseteq\mathsf{VNP}$ consist of sequences of $\mathrm{poly}(n)$ -degree $n$ -variate polynomials that are computable by $\mathrm{poly}(n)$ -size arithmetic formulas, branching programs, circuits and projections of circuits, respectively. As with the analogous Boolean classes ( $\mathsf{NC^{1}}\subseteq\mathsf{NL}\subseteq\mathsf{P}\subseteq\mathsf{NP}$ ), these four algebraic classes are believed to be distinct. However, it remains a major open problem even to separate $\mathsf{VNC^{1}}$ from $\mathsf{VNP}$ , despite significant progress on lower bounds for formulas, branching programs and circuits in various restricted settings: low-depth [2, 17, 18], multilinear [9, 20, 23], set-multilinear [3, 16, 25], and non-commutative [6, 19, 30] (to mention just a few representative works).

1.1 Biquadratic sum-of-squares and non-commutative circuits

Let $f\in\mathbb{F}[X_{1},\dots,X_{n},Y_{1},\dots,Y_{n}]$ be a biquadratic polynomial over a field $\mathbb{F}$ with monomials of the form $X_{i_{1}}X_{i_{2}}Y_{j_{1}}Y_{j_{2}}$ . The (biquadratic) sum-of-squares complexity of $f$ , denoted $\mathrm{SoS}(f)$ , is the minimum number $s$ of bilinear polynomials $g_{1},\dots,g_{s}$ such that $f=g_{1}^{2}+\dots+g_{s}^{2}$ . When $\mathbb{F}$ is algebraically closed, we have $\mathrm{SoS}(f)\leq n^{2}$ for all $f$ , while a dimension-counting argument shows that $\mathrm{SoS}(f)=\Omega(n^{2})$ for almost all $f$ .

Sum-of-squares complexity has been intensively studied for the separable biquadratic polynomial

\displaystyle q_{n}\vcentcolon=(X_{1}^{2}+\dots+X_{n}^{2})\cdot(Y_{1}^{2}+% \dots+Y_{n}^{2}).

Over $\mathbb{R}$ and $\mathbb{C}$ , trivial bound are given by

\displaystyle n\leq\mathrm{SoS}_{\mathbb{C}}(q_{n})\leq\mathrm{SoS}_{\mathbb{R% }}(q_{n})\leq n^{2}.

A classical theorem of Hurwitz from 1898 shows that $\mathrm{SoS}_{\mathbb{R}}(q_{n})=n$ iff $n\in\{1,2,4,8\}$ [15]. An upper bound $\mathrm{SoS}_{\mathbb{R}}(q_{n})=O(\frac{n^{2}}{\log n})$ is given by the classical Radon-Hurwitz construction (see [22, 28]). Asymptotically, this remains the strongest known upper bound over $\mathbb{R}$ . It was also the strongest known bound over $\mathbb{C}$ , until a recent breakthrough of Hrubeš [14]:

Theorem 1.1 ([14]).

There exists a sum-of-squares decomposition of $q_{n}$ over $\mathbb{C}$ with just $O(n^{1.62})$ terms, that is, $\mathrm{SoS}_{\mathbb{C}}(q_{n})=O(n^{1.62})$ .

As for lower bounds, Adams and Atiyah [1] showed $\mathrm{SoS}_{\mathbb{C}}(q_{n})\geq 2^{\lceil\log_{2}n\rceil}$ ; in particular, $\mathrm{SoS}_{\mathbb{C}}(q_{n})\geq 2n-2$ infinitely often. Slightly better bounds have been obtained for specific values of $n$ (and for general fields of characteristic $\neq 2$ ) using techniques from algebraic K-theory [7]. However, no lower bound better than $\mathrm{SoS}_{\mathbb{C}}(q_{n})=\Omega(n)$ is currently known.

A striking result of Hrubeš, Wigderson and Yehudayoff [13] explains the difficulty of improving this lower bound. They show that proving a sufficiently super-linear lower bound on $\mathrm{SoS}_{\mathbb{C}}(q_{n})$ would have a dramatic consequence in non-commutative algebraic circuit complexity:

Theorem 1.2 ([13]).

Let $f=(f_{n})$ be any explicit sequence¹¹1The sequence $f=(f_{n})$ is explicit if the coefficient in $f_{n}$ of each monomial $X_{i_{1}}X_{i_{2}}Y_{j_{1}}Y_{j_{2}}$ is computable in $\mathrm{polylog}(n)$ time given $n$ and indices $i_{1},i_{2},j_{1},j_{2}\in[n]$ . of biquadratic polynomials over $\mathbb{C}$ . If $\mathrm{SoS}_{\mathbb{C}}(f)=\Omega(n^{1+\varepsilon})$ for any $\varepsilon>0$ , then the permanent $\mathrm{PERM}_{n}$ requires exponential size non-commutative circuits; in particular, this implies a separation of complexity classes $\mathsf{VP}_{\mathsf{nc}}$ and $\mathsf{VNP}_{\mathsf{nc}}$ (the non-commutative algebraic analogues of $\mathsf{P}$ and $\mathsf{NP}$ ). Moreover, a lower bound $\mathrm{SoS}_{\mathbb{C}}(f)=\Omega(n\log^{5}n)$ suffices for the separation $\mathsf{VP}_{\mathsf{nc}}\neq\mathsf{VNP}_{\mathsf{nc}}$ .

Notice that Hrubeš’s upper bound $\mathrm{SoS}_{\mathbb{C}}(q_{n})=O(n^{1.62})$ does not rule out the possibility of separating $\mathsf{VP}_{\mathsf{nc}}$ and $\mathsf{VNP}_{\mathsf{nc}}$ via an $\Omega(n^{1+\varepsilon})$ lower bound. (We remark that Theorems 1.1 and 1.2 hold more generally over any algebraically closed field, but are not known to extend to $\mathbb{R}$ ; see the discussion in §1.4.)

1.2 Multiquadratic sum-of-squares and commutative set-multilinear formulas

The main theorem of this paper shows that strong enough lower bounds for multiquadratic sum-of-squares imply super-polynomial lower bounds for commutative arithmetic formulas.

Let $f$ be a $d$ -multiquadratic polynomial over an algebraically closed field, that is, a linear combination of monomials $X^{(1)}_{i_{1}}X^{(1)}_{j_{1}}\cdots X^{(d)}_{i_{d}}X^{(d)}_{j_{d}}$ where $i_{1},j_{1},\dots,i_{d},j_{d}\in[n]$ . As in the biquadratic setting ( $d=2$ ), the (multiquadratic) sum-of-squares complexity of $f$ , denoted $\mathrm{SoS}(f)$ , is defined as the minimum number $s$ of $d$ -multilinear polynomials $g_{1},\dots,g_{s}$ such that $f=g_{1}^{2}+\dots+g_{s}^{2}$ . Similar to the biquadratic setting, we have $\mathrm{SoS}(f)\leq O(n^{d})$ for all $f$ , and $\mathrm{SoS}(f)=\Omega((n/2)^{d})$ for almost all $f$ (Prop. 3.17).

Our main result – stated informally below and formally in the next subsection – shows that a nearly optimal lower bound on the SoS complexity of explicit $d$ -multiquadratic polynomials would separate the algebraic complexity classes $\mathsf{VNC^{1}}$ and $\mathsf{VNP}$ .

Theorem 1.3 (informal).

Let $f=(f_{n})$ be any explicit sequence of $d$ -multiquadratic polynomials over an algebraically closed or finite field of characteristic $\neq 2$ . If $\mathrm{SoS}(f)=n^{d-o(\log d)}$ , then this yields an $n^{\Omega(\log d)}$ lower bound on the set-multilinear formula size of associated $d+1$ -multilinear polynomials $\widetilde{f}=(\widetilde{f}_{n})$ . If in addition $d=d(n)$ satisfies $\omega(1)\leq d(n)\leq O(\frac{\log n}{\log\log n})$ , we get a separation $\mathsf{VNC^{1}}\neq\mathsf{VNP}$ (via a lemma of Raz [24]).

While Theorem 1.3 is analogous to the result of Hrubeš, Wigderson and Yehudayoff [13], it is closer in nature to a well-known theorem of Raz [24] linking tensor rank to set-multilinear formula lower bounds (see the discussion in §1.4).

1.3 Partial transpose rank of $n^{d}\times n^{d}$ matrices

Definition 1.4.

Let $\mathcal{X}=\{X_{i_{1}}^{(1)}\}_{i_{1}=1}^{n}\cup\{X_{i_{2}}^{(2)}\}_{i_{2}=1}% ^{n}\cup\cdots\cup\{X_{i_{d}}^{(d)}\}_{i_{d}=1}^{n}$ be $d$ disjoint blocks of $n$ variables. A polynomial $P(\mathcal{X})$ is $d$ -multiquadratic if each monomial of $P(\mathcal{X})$ has total degree exactly $2$ in each block.

Every $n^{d}\times n^{d}$ matrix $M$ gives rise to a $d$ -multiquadratic polynomial defined by

\displaystyle Q_{M}\vcentcolon=\sum_{\vec{i},\vec{j}\in[n]^{d}}M_{\vec{i},\vec% {j}}\cdot X^{(1)}_{i_{1}}X^{(1)}_{j_{1}}\cdots X^{(d)}_{i_{d}}X^{(d)}_{j_{d}}.

Conversely, for fields of characteristic $\neq 2$ , we get a bijective correspondence between $d$ -multiquadratic polynomials (with $d$ blocks of $n$ variables) and $n^{d}\times n^{d}$ matrices satisfying $M=M^{\top_{1}}=\dots=M^{\top_{d}}$ , where ${\top_{k}}$ is the $k$ -th partial transpose operation which swaps row-index $i_{k}$ and column-index $j_{k}$ . We refer to such matrices as fully symmetric.

The actual main theorem of this paper concerns a generalization of SoS complexity called partial transpose rank – or PT-rank for short – which is a complexity measure on general $n^{d}\times n^{d}$ matrices (not just fully symmetric ones). We say that an $n^{d}\times n^{d}$ matrix $P$ is PT-basic if $P^{\top_{\kappa}}$ has rank $1$ for any $\kappa\subseteq[d]$ , where ${}^{\top_{\kappa}}$ is the composition of (commuting) operations ${\top_{k}}$ for $k\in\kappa$ . We then define the PT-rank of any $n^{d}\times n^{d}$ matrix $M$ as the minimum number $r$ of PT-basic matrices $P_{1},\dots,P_{r}$ such that $M=P_{1}+\dots+P_{r}$ . This complexity measure is closely related to SoS complexity: for fully symmetric matrices $M$ (satisfying $M=M^{\top_{k}}$ for all $k\in[d]$ ), we show that $\mathrm{PT\textup{-}rank}(M)$ and $\mathrm{SoS}(Q_{M})$ are equivalent to an $O(2^{d})$ factor over any algebraically closed or finite field of characteristic $\neq 2$ (Prop. 3.15).

Our main theorem relates the PT-rank of an arbitrary $n^{d}\times n^{d}$ matrix $M$ with the set-multilinear formula size of an associated multilinear polynomial of degree $d+1$ in $dn+(d-1)n^{2}+dn$ variables:

\displaystyle\widetilde{Q}_{M}\vcentcolon=\sum_{\vec{i},\vec{j}\in[n]^{d}}M_{% \vec{i},\vec{j}}\cdot\widetilde{X}^{(0)}_{i_{1}}\widetilde{X}^{(1)}_{j_{1},i_{% 2}}\cdots\widetilde{X}^{(d-1)}_{j_{d-1},i_{d}}\widetilde{X}^{(d)}_{j_{d}}.

Theorem 1.5 (Main theorem).

For every $n^{d}\times n^{d}$ matrix $M$ (over any field), the set-multilinear formula size of $\widetilde{Q}_{M}$ is at least $\mathrm{PT\textup{-}rank}(M)/n^{d-\log d+1}$ .

Via a standard set-multilinearization lemma of Raz [24], we get the following corollary:

Corollary 1.6.

Suppose that $\mathrm{PT\textup{-}rank}(M)=n^{d-o(\log d)}$ where $M$ is any explicit sequence of $n^{d}\times n^{d}$ matrices with $\omega(1)\leq d(n)\leq O(\frac{\log n}{\log\log n})$ . Then $\widetilde{Q}_{M}$ has arithmetic formula size at least $n^{(1-o(1))\log d}$ and, hence, $\mathsf{VNC^{1}}\neq\mathsf{VNP}$ .

(Theorem 1.3 on SoS complexity follows directly from Theorem 1.5 and Corollary 1.6. For a $d$ -multiquadratic polynomial $f=Q_{M}$ , the multilinear polynomial $\widetilde{f}$ of Theorem 1.3 is given by $\widetilde{Q}_{M}$ .)

Since almost all $M$ have PT-rank $\geq(\frac{1}{2}-o(1))n^{d}$ (Prop. 3.16), finding an explicit $M$ with $\mathrm{PT\textup{-}rank}(M)=n^{d-o(\log d)}$ is a classic problem of “finding hay in a haystack”. By finding a very explicit $M$ (with $\widetilde{Q}_{M}$ in $\mathsf{VP}$ rather than $\mathsf{VNP}$ ), Corollary 1.6 could conceivably be used to show $\mathsf{VNC^{1}}\neq\mathsf{VP}$ . On the flipside, an additional result of this paper (Theorem 6.6) rules out lower bounds, over fields of characteristic $\neq 2$ , whenever $\widetilde{Q}_{M}$ belongs to the class $\mathsf{VBP_{ord}}$ of set-multilinear polynomials computable by a polynomial-size ordered branching program. This negative result leverages the recent upper bound $\mathrm{SoS}_{\mathbb{C}}(q_{n})=O(n^{1.62})$ of Hrubeš [14] (Theorem 1.1). We also show that $\mathrm{PT\textup{-}rank}(M)$ is at most $n^{O(d^{0.7})}$ when $M$ is a Kronecker product of $d$ $n\times n$ matrices over any fields of characteristic $\neq 2$ (Theorem 6.3); this observation rules out certain explicit $n^{d}\times n^{d}$ matrices as candidates for having PT-rank $n^{d-o(\log d)}$ .

So far as we know, over $\mathrm{GF}(2)$ , it is possible that the $n^{d}\times n^{d}$ identity matrix $I_{n^{d}}$ has PT-rank $n^{d-o(\log d)}$ or even exactly $n^{d}$ . If so, by Theorem 1.5 this implies an $n^{(1-o(1))\log d}$ lower bound on the formula size of iterated matrix multiplication $\mathrm{IMM}_{n,d+1}$ ( $=\widetilde{Q}_{I_{n^{d}}}$ ), which would separate classes $\mathsf{VNC^{1}}$ and $\mathsf{VBP}$ over $\mathrm{GF}(2)$ .

1.4 Related work

Following the influential paper of Hrubeš, Wigderson and Yehudayoff [13], subsequent work by various authors [3, 5, 8] has found additional reductions between various sum-of-squares complexity measures and algebraic circuit lower bounds. Most recently, Dutta, Saxena and Thierauf [8] showed that an $d^{0.5+\Omega(1)}$ lower bound on the support-sum of any explicit degree- $d$ univariate polynomial would separate $\mathsf{VP}$ and $\mathsf{VNP}$ . However, none of the prior work has explored the $d$ -multiquadratic setting, nor implications specific to arithmetic formulas.

More closely related to our main theorem is the well-known theorem of Raz [24] that an $n^{d-o(d)}$ lower bound on the tensor rank of any explicit $d$ -multilinear polynomial $g$ (i.e. order- $d$ tensor $[n]^{d}\to\mathbb{F}$ ) implies an $n^{\Omega(\log d)}$ lower bound on the set-multilinear formula size of the same polynomial $g$ . The further implication $\mathsf{VNC^{1}}\neq\mathsf{VNP}$ when $\omega(1)\leq d(n)\leq O(\frac{\log n}{\log\log n})$ follows from an additional lemma in [24], which we also invoke above.

We remark that a lower bound $\mathrm{SoS}(f)=n^{d-o(\log n)}$ for an explicit $d$ -multiquadratic polynomial $f$ (i.e. fully symmetric $n^{d}\times n^{d}$ matrix) is conceivable without having to break the longstanding $O(n^{\lfloor d/2\rfloor})$ tensor rank barrier. Indeed, Theorem 1.3 appears to evade the known barriers for rank-based lower bound methods identified by Efremenko et al [10] and Garg et al [11].

1.5 Outline of the paper

The rest of the paper is organized as follows: §2 presents key definitions pertaining to tensors, matrices, and arithmetic formulas. §3 formally introduces partial transpose rank and explores its properties. §4 proves a weaker (but easier and illustrative) version of our main theorem – with respect to non-commutative set-multilinear formulas. §5 proves the main theorem – with respect to commutative set-multilinear formulas. §6 discusses upper bounds for PT-rank and candidate explicit hard matrices.

2 Preliminaries

Throughout this paper, $n, d$ are arbitrary positive integers, where we regard $n$ as a growing parameter and $d=d(n)$ as a function of $n$ .

We write $[n]$ for the set $\{1,\dots,n\}$ and $\log n$ for the base-2 logarithm of $n$ . We write $\langle\cdot,\cdot\rangle:[n]^{2}\to[n^{2}]$ for the pairing bijection defined by $\langle i,j\rangle\vcentcolon=(i-1)n+j$ .

2.1 The underlying field

Throughout this paper, $\mathbb{F}$ is an arbitrary field. We will explicitly state whenever an assumption on $\mathbb{F}$ is required. In particular, our main theorem (Theorem 1.5) and other results concerning PT-rank work for completely general fields (including characteristic $2$ ).

The only results that depend on $\mathbb{F}$ concern the relationship between PT-rank and SoS complexity (Lemma 3.15) and the consequence of our main theorem stated in the terms of SoS complexity (Theorem 1.3). Even here, our results apply to a large class of fields of characteristic $\neq 2$ , including all algebraically closed fields and finite fields.

2.2 Matrices and tensors

In the Introduction, our main theorem was stated first in terms of SoS complexity of $d$ -multiquadratic polynomials, then more generally in terms of PT-rank of $n^{d}\times n^{d}$ matrices. These rank measures were linked to the algebraic complexity of a third kind of object: $d+1$ -multilinear polynomials. It is convenient to regard these objects as different flattenings of a tensor $[n]^{2d}\to\mathbb{F}$ to tensors of format $[n^{2}]^{d}$ or $[n^{d}]^{2}$ or $[n]\times[n^{2}]^{d-1}\times[n]$ , respectively.

Definition 2.1 (Tensors).

An order $d$ tensor is a function $A:[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ where $n_{1},\dots,n_{d}$ are nonnegative integers.²²2All definitions and claims in this paper can be rephrased in a basis-free manner, that is, regarding $A$ as a multilinear function $\mathbb{F}^{n_{1}}\times\dots\times\mathbb{F}_{n_{d}}\to\mathbb{F}$ without reference to any specific bases for vector spaces $\mathbb{F}^{n_{i}}$ . We shall mainly (but not exclusively) consider tensors $[n]^{d}\to\mathbb{F}$ where $n_{1}=\dots=n_{d}=n$ . More generally, we consider tensors $A:[n]^{D}\to\mathbb{F}$ with coordinates indexed by a nonempty finite set $D$ .³³3Specifically, in §5 we consider tensors where $D$ is the directed edge set of an arbitrary subgraph of $\mathrm{Path}_{d}$ .

For tensors $A:[n]^{d}\to\mathbb{F}$ and $B:[n]^{e}\to\mathbb{F}$ , their tensor product is denoted by $A\otimes B:[n]^{d+e}\to\mathbb{F}$ . For tensors $A:[n]^{D}\to\mathbb{F}$ and $B:[n]^{E}\to\mathbb{F}$ with $D$ and $E$ disjoint, their tensor product is denoted by $A\otimes B:[n]^{D\cup E}\to\mathbb{F}$ .

The tensor rank of a tensor $A:[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ , denoted $\textrm{tensor-rank}(A)$ , is the minimum number $r$ such that $A$ admits a decomposition $A=\sum_{j=1}^{r}(A_{1,j}\otimes\dots\otimes A_{d,j})$ for some collection of order 1 tensors $A_{i,j}:[n_{i}]\to\mathbb{F}$ .⁴⁴4We define tensor rank solely for the sake of comparing our main result (Theorem 1.5) with Raz’s theorem shows that an $n^{d-o(d)}$ lower bound on tensor rank implies $\mathsf{VNC^{1}}\neq\mathsf{VP}$ [24], as discussed in §1.4. Elsewhere in this paper, we only every consider the matrix rank of flattened tensors.

Definition 2.2 (Matrices).

A matrix is an order $2$ tensor $M:[m_{1}]\times[m_{2}]\to\mathbb{F}$ , also written as $M\in\mathbb{F}^{m_{1}\times m_{2}}$ . The rank of $M$ is denoted by $\mathrm{rank}(M)$ ; note that this is a special case tensor rank. The transpose of $M$ is denoted by $M^{\mathsf{T}}\in\mathbb{F}^{m_{2}\times m_{1}}$ . (We use a bolder font $\mathsf{T}$ to distinguish the full transpose from partial transpose operations $\top_{\kappa}$ on $n^{d}\times n^{d}$ matrices introduced in Def. 3.1.)

For matrices $M:[m_{1}]\times[m_{2}]\to\mathbb{F}$ and $N:[n_{1}]\times[n_{2}]\to\mathbb{F}$ , their Kronecker product is denoted by $M\mathrel{\mathchoice{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$% \displaystyle\boxtimes$}}}}{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$% \textstyle\boxtimes$}}}}{\raisebox{-0.83334pt}{\hbox{\raisebox{0.0pt}{$% \scriptstyle\boxtimes$}}}}{\raisebox{-0.83336pt}{\hbox{\raisebox{0.0pt}{$% \scriptscriptstyle\boxtimes$}}}}}N:[m_{1}n_{1}]\times[m_{2}n_{2}]\to\mathbb{F}$ (not to be confused with the tensor product $M\otimes N:[m_{1}]\times[m_{2}]\times[n_{1}]\times[n_{2}]\to\mathbb{F}$ .)

The $n\times n$ identity matrix is denoted by $I_{n}$ . We write $I_{n}^{\otimes d}$ for the order $2d$ tensor $I_{n}\otimes\dots\otimes I_{n}$ ( $d$ times) (not to be confused with the $n^{d}\times n^{d}$ matrix $I_{n^{d}}=I_{n}\mathrel{\mathchoice{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0% pt}{$\displaystyle\boxtimes$}}}}{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{% $\textstyle\boxtimes$}}}}{\raisebox{-0.83334pt}{\hbox{\raisebox{0.0pt}{$% \scriptstyle\boxtimes$}}}}{\raisebox{-0.83336pt}{\hbox{\raisebox{0.0pt}{$% \scriptscriptstyle\boxtimes$}}}}}\dots\mathrel{\mathchoice{\raisebox{-0.83333% pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\boxtimes$}}}}{\raisebox{-0.83333pt}{% \hbox{\raisebox{0.0pt}{$\textstyle\boxtimes$}}}}{\raisebox{-0.83334pt}{\hbox{% \raisebox{0.0pt}{$\scriptstyle\boxtimes$}}}}{\raisebox{-0.83336pt}{\hbox{% \raisebox{0.0pt}{$\scriptscriptstyle\boxtimes$}}}}}I_{n}$ , which is a tensor of order $2$ ).

When $M$ is an $n^{d}\times n^{d}$ matrix, we index its rows and columns by $d$ -tuples in $[n]^{d}$ . That is, we express the entries of $M$ as $M_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{d})}$ .

Definition 2.3 (Matrix flattening of a tensor).

For a tensor $A:[n]^{D}\to\mathbb{F}$ and partition $I\sqcup J=D$ , we denote $\mathrm{Mat}_{I,J}(A)$ for the flattened matrix

\displaystyle\mathrm{Mat}_{I,J}(A):[n^{|I|}]\times[n^{|J|}]\to\mathbb{F}.

2.3 Set-multilinear formula size

There is a one-to-one correspondence between order $d$ tensors $A:[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ and set-multilinear polynomials $P_{A}\in\mathbb{F}_{\mathsf{sm}}[\mathcal{X}]$ in variables $\mathcal{X}=\{X^{(i)}_{a}:i\in[d],\,a\in[n_{i}]\}$ . Namely, $A$ describes the coefficients of $P_{A}$ :

\displaystyle P_{A}(\mathcal{X})=\sum_{(a_{1},\dots,a_{d})\in[n_{1}]\times% \dots\times[n_{d}]}A_{a_{1},\dots,a_{d}}\ X^{(1)}_{a_{1}}\cdots X^{(d)}_{a_{d}}.

For any nonempty finite set $D$ , we have a similar correspondence between tensors $A:[n]^{D}\to\mathbb{F}$ and set-multilinear polynomial $P_{A}\in\mathbb{F}_{\mathsf{sm}}[\mathcal{X}]$ in variables $\mathcal{X}=\{X^{(i)}_{a}:i\in D,\,a\in[n]\}$ .

Definition 2.4 (Set-multilinear formula size).

The set-multilinear formula size of a tensor $A:[n]^{D}\to\mathbb{F}$ , denoted $\mathcal{L}_{\mathsf{sm}}(A)$ , is the minimum number of leaves in a syntactically set-multilinear arithmetic formula that computes the associated polynomial $P_{A}$ . This may also be defined directly by induction:

$\blacksquare$

If $|D|=1$ , then $\mathcal{L}_{\mathsf{sm}}(A)$ is $1$ if $A$ is non-zero anywhere and $0$ otherwise.
$\blacksquare$

If $|D|\geq 2$ , then $\mathcal{L}_{\mathsf{sm}}(A)$ is the minimum value of $\sum_{i}\ (\mathcal{L}_{\mathsf{sm}}(B_{i})+\mathcal{L}_{\mathsf{sm}}(C_{i}))$ over indexed families $\{(E_{i},F_{i},B_{i},C_{i})\}_{i}$ (where $i$ runs over an arbitrary, unnamed index set) such that $E_{i},F_{i}$ are disjoint nonempty sets satisfying $E_{i}\cup F_{i}=D$ and $B_{i}:[n]^{E_{i}}\to\mathbb{F}$ and $C_{i}:[n]^{F_{i}}\to\mathbb{F}$ are tensors satisfying $A=\sum_{i}B_{i}\otimes C_{i}$ .

For further background on algebraic complexity measures, see [4, 26, 29].

2.4 $n^{d}\times n^{d}$ matrices and their shifted tensors

Recall that our main theorem, Theorem 1.5, relates $\mathrm{PT\textup{-}rank}(M)$ to the set-multilinear formula size of a related polynomial. This polynomial is denoted $\widetilde{Q}_{M}$ in the statement of Theorem 1.5. However, it is convenient to speak of the associated tensor, which we shall refer to as the “shifted tensor” of $M$ .

Definition 2.5 (The shifted tensor of an $n^{d}\times n^{d}$ matrix $M$ ).

For any $n^{d}\times n^{d}$ matrix $M$ , we defined the reshaped tensor $\mathrm{ShiftedTensor}(M):[n^{2}]^{d+1}\to\mathbb{F}$ as follows. Recall that $\langle\cdot,\cdot\rangle$ is a bijection $[n]^{2}\to[n^{2}]$ . For all $p,i_{1},j_{1},\dots,i_{d},j_{d},q\in[n]$ , we have
$\displaystyle\mathrm{ShiftedTensor}(M)(\langle p,i_{1}\rangle,\langle j_{1},i_% {2}\rangle,\dots,\langle j_{d-1},i_{d}\rangle,\langle j_{d},q\rangle)$ $\displaystyle\vcentcolon=\mathds{1}\{p=q=1\}\cdot M_{(i_{1},\dots,i_{d}),(j_{1% },\dots,j_{d})}.$

Note that the set-multilinear polynomial $P_{\mathrm{ShiftedTensor}(M)}$ is precisely $\widetilde{Q}_{M}$ of Theorem 1.5.

Definition 2.6 (Iterated Matrix Multiplication).

An important example of a “shifted tensor” is the Iterated Matrix Multiplication tensor $\mathrm{IMM}_{n,d}:[n^{2}]^{d}\to\mathbb{F}$ defined by

\displaystyle\mathrm{IMM}_{n,d}(\langle a_{1},b_{1}\rangle,\dots,\langle a_{d}% ,b_{d}\rangle)\vcentcolon=\mathds{1}[\,(b_{1},\dots,b_{d-1})=(a_{2},\dots,a_{d% })\,].

The familiar corresponding set-multilinear polynomial describes the sum of entries in the product of $d$ symbolic $n\times n$ matrices:

\displaystyle P_{\mathrm{IMM}_{n,d}}(\mathcal{X})=\sum_{a_{0},\dots,a_{d}\in[n% ]}X^{(1)}_{\langle a_{0},a_{1}\rangle}X^{(2)}_{\langle a_{1},a_{2}\rangle}% \cdots X^{(d)}_{\langle a_{d-1},a_{d}\rangle}.

Note that $\mathrm{IMM}_{n,d}=\mathrm{ShiftedTensor}(I_{n^{d-1}})$ , that is, $\mathrm{IMM}_{n,d}$ is the shifted tensor of the $n^{d-1}\times n^{d-1}$ identity matrix.

3 Partial transpose rank

The partial transpose is a key concept in quantum information theory, particularly in studying entanglement and separability of quantum states [12, 21]. In this section, we introduce the partial transpose rank of an $n^{d}\times n^{d}$ matrix. To the best of our knowledge, this notion has not been explicitly studied before. As we show, PT rank generalizes SoS complexity (for fully symmetric matrices over algebraically closed or finite fields of characteristic $\neq 2$ ).

We begin by defining the partial transpose operations on $n^{d}\times n^{d}$ matrices.

Definition 3.1 (Partial transpose).

Let $M$ be an $n^{d}\times n^{d}$ matrix.

$\blacksquare$

For $k\in[d]$ , the $k$ -th partial transpose of $M$ , denoted $M^{\top_{k}}$ , is the $n^{d}\times n^{d}$ matrix defined by

$\displaystyle M^{\top_{k}}_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{d})}% \vcentcolon=M^{\vphantom{\top_{k}}}_{(i_{1},\dots,i_{k-1},j_{k},i_{k+1},\dots,% i_{d}),(j_{1},\dots,j_{k-1},i_{k},j_{k+1},\dots,j_{d})}.$
$\blacksquare$

For $\kappa\subseteq[d]$ , the $\kappa$ -partial transpose of $M$ is the matrix $M^{\top_{\kappa}}\vcentcolon=M^{\top_{k_{1}}\dots\top_{k_{c}}}$ where $k_{1},\dots,k_{c}$ are the distinct elements of $\kappa$ (in any order).

Note that $M^{\top_{\emptyset}}=M$ and $M^{\top_{[d]}}=M^{\mathsf{T}}$ (the usual transpose of $M$ ). Also note that

\displaystyle M^{\top_{\kappa_{1}}\top_{\kappa_{2}}}=M^{\top_{\kappa_{2}}\top_% {\kappa_{1}}}=M^{\top_{\kappa_{1}\vartriangle\kappa_{2}}}

where $\kappa_{1}\vartriangle\kappa_{2}=(\kappa_{1}\setminus\kappa_{2})\cup(\kappa_{2% }\setminus\kappa_{1})$ is the symmetric difference of $\kappa_{1}$ and $\kappa_{2}$ . In particular, the transpose of $M^{\top_{\kappa}}$ is $M^{\top_{\overline{\kappa}}}$ where $\overline{\kappa}\vcentcolon=[d]\setminus\kappa$ is the complement of $\kappa$ . If $M$ is symmetric (i.e. $M^{\top}=M$ ), it follows that $M^{\top_{\kappa}}=M^{\top_{\overline{\kappa}}}$ .

Definition 3.2 (Fully symmetric matrices).

We say that an $n^{d}\times n^{d}$ matrix $M$ is fully symmetric if $M^{\top_{k}}=M$ for all $k\in[d]$ (equivalently: if $M^{\top_{\kappa}}=M$ for all $\kappa\subseteq[d]$ ).

Example 3.3.

Let $d=2$ and $n=3$ . Suppose $M$ is a partitioned $3^{2}\times 3^{2}$ matrix with $3\times 3$ blocks $M_{11},\dots,M_{33}$ . Then

	$\displaystyle M^{\top_{\emptyset}}=M$	$\displaystyle=\small\begin{bmatrix}M_{11}&M_{12}&M_{13}\\ M_{21}&M_{22}&M_{23}\\ M_{31}&M_{32}&M_{33}\end{bmatrix},$	$\displaystyle M^{\top_{\{1\}}}=M^{\top_{1}}$	$\displaystyle=\small\begin{bmatrix}M_{11}^{\top}&M_{12}^{\top}&M_{13}^{\top}\\ M_{21}^{\top}&M_{22}^{\top}&M_{23}^{\top}\\ M_{31}^{\top}&M_{32}^{\top}&M_{33}^{\top}\end{bmatrix},$
	$\displaystyle M^{\top_{\{2\}}}=M^{\top_{2}}$	$\displaystyle=\small\begin{bmatrix}M_{11}&M_{21}&M_{31}\\ M_{12}&M_{22}&M_{32}\\ M_{13}&M_{23}&M_{33}\end{bmatrix},$	$\displaystyle M^{\top_{\{1,2\}}}=M^{\top}$	$\displaystyle=\small\begin{bmatrix}M_{11}^{\top}&M_{21}^{\top}&M_{31}^{\top}\\ M_{12}^{\top}&M_{22}^{\top}&M_{32}^{\top}\\ M_{13}^{\top}&M_{23}^{\top}&M_{33}^{\top}\end{bmatrix}.$

When $d=2$ (as in this example), the operation $\top_{1}$ is also known as the block transpose, since it transposes the individual blocks within a partitioned $n^{2}\times n^{2}$ matrix.

Definition 3.4 (Partial transpose rank).

Let $M$ be an $n^{d}\times n^{d}$ matrix.

$\blacksquare$

$M$ is PT-basic if there exists $\kappa\subseteq[d]$ such that $\mathrm{rank}(M^{\top_{\kappa}})=1$ .
$\blacksquare$

The PT-rank of $M$ is the minimum number of PT-basic matrices that sum to $M$ .

The next lemma gives an alternative characterization of $\mathrm{PT\textup{-}rank}$ .

Lemma 3.5.

The PT-rank of an $n^{d}\times n^{d}$ matrix $M$ equals the minimum value of $\sum_{\kappa\subseteq[d-1]}\mathrm{rank}(N_{\kappa}^{\top_{\kappa}})$ over all decompositions $M=\sum_{\kappa\subseteq[d-1]}N_{\kappa}$ .

Proof.

Let $r$ be the PT-rank of $M$ and let $B_{1},\dots,B_{r}$ be PT-basic matrices that sum to $M$ . For each $B_{i}$ , there exists $\kappa_{i}\subseteq[d]$ with $\mathrm{rank}(B_{i}^{\smash{\top_{\kappa_{i}}}})=1$ . Without loss of generality, we may choose $\kappa_{i}\subseteq[d-1]$ , since $\mathrm{rank}(B_{i}^{\smash{\top_{\kappa_{i}}}})=\mathrm{rank}((B_{i}^{\smash{% \top_{\kappa_{i}}}})^{\mathsf{T}})=\mathrm{rank}(B_{i}^{\smash{\top_{\overline% {\kappa_{i}}}}})$ . Now define $N_{\kappa}\vcentcolon=\sum_{i\in[r]\,:\,\kappa_{i}=\kappa}B_{i}$ . $\hfill\blacktriangleleft$

The next two examples illustrate PT-rank in the case $d=2$ .

Example 3.6.

Let $d=2$ and $n=2$ . The $2^{2}\times 2^{2}$ identity matrix has PT-rank $2$ , since it is not PT-basic, but is a sum of PT-basic matrices:

\displaystyle\left[\begin{array}[]{rr|rr}1&0&0&0\\ 0&1&0&0\\ \hline\cr 0&0&1&0\\ 0&0&0&1\\ \end{array}\right]

\displaystyle=\left[\begin{array}[]{rr|rr}1&0&0&\!\!\!-1\\ 0&0&0&0\\ \hline\cr 0&0&0&0\\ \!\!\!-1&0&0&1\\ \end{array}\right]+\left[\begin{array}[]{rr|rr}0&0&0&0\\ 0&1&1&0\\ \hline\cr 0&1&1&0\\ 0&0&0&0\\ \end{array}\right]^{\top_{1}}

3.1 Properties of PT-rank

Unlike the full transpose ( $\kappa=[d]$ ), the partial transpose operation can increase matrix rank when $\emptyset\subsetneqq\kappa\subsetneqq[d]$ . (See full version of the paper for proofs of lemmas in this section.)

Lemma 3.7.

For every $n^{d}\times n^{d}$ matrix $M$ and $\kappa\subseteq[d]$ , we have

\displaystyle\mathrm{rank}(M^{\top_{\kappa}})\leq n^{2\min\{|\kappa|,d-|\kappa% |\}}\,\mathrm{rank}(M).

Moreover, this inequality is best possible in general.

The partial transpose also behaves differently than the full transpose with respect to products of matrices. For two $n^{d}\times n^{d}$ matrices $P$ and $M$ , we have $(PM)^{\top}=M^{\top}P^{\top}$ ; additionally, $\mathrm{rank}((PM)^{\top})=\mathrm{rank}(M^{\top})$ whenever $P$ is invertible. With respect to the partial transpose, we get analogous equations only in the case that $P$ (or $M$ ) is a Kronecker product of $d$ $n\times n$ matrices.

Lemma 3.8.

Let $P$ and $M$ be $n^{d}\times n^{d}$ matrices such that $P=B_{1}\mathrel{\mathchoice{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$% \displaystyle\boxtimes$}}}}{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$% \textstyle\boxtimes$}}}}{\raisebox{-0.83334pt}{\hbox{\raisebox{0.0pt}{$% \scriptstyle\boxtimes$}}}}{\raisebox{-0.83336pt}{\hbox{\raisebox{0.0pt}{$% \scriptscriptstyle\boxtimes$}}}}}\dots\mathrel{\mathchoice{\raisebox{-0.83333% pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\boxtimes$}}}}{\raisebox{-0.83333pt}{% \hbox{\raisebox{0.0pt}{$\textstyle\boxtimes$}}}}{\raisebox{-0.83334pt}{\hbox{% \raisebox{0.0pt}{$\scriptstyle\boxtimes$}}}}{\raisebox{-0.83336pt}{\hbox{% \raisebox{0.0pt}{$\scriptscriptstyle\boxtimes$}}}}}B_{d}$ for $n\times n$ matrices $B_{1},\dots,B_{d}$ . Then for all $\kappa\subseteq[d]$ ,

\displaystyle(PM)^{\top_{\kappa}}=LM^{\top_{\kappa}}R\quad\text{where }L=% \mathop{\mathchoice{\raisebox{-3.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle% \boxtimes$}}}}{\raisebox{-3.0pt}{\hbox{\raisebox{0.0pt}{$\textstyle\boxtimes$}% }}}{\raisebox{-3.0pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\boxtimes$}}}}{% \raisebox{-3.0pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\boxtimes$}}}}}_{k% =1}^{d}\begin{cases}I_{n}&\text{if }k\in\kappa\\ B_{k}&\text{otherwise}\end{cases}\text{ and }R=\mathop{\mathchoice{\raisebox{-% 3.0pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\boxtimes$}}}}{\raisebox{-3.0pt}{% \hbox{\raisebox{0.0pt}{$\textstyle\boxtimes$}}}}{\raisebox{-3.0pt}{\hbox{% \raisebox{0.0pt}{$\scriptstyle\boxtimes$}}}}{\raisebox{-3.0pt}{\hbox{\raisebox% {0.0pt}{$\scriptscriptstyle\boxtimes$}}}}}_{k=1}^{d}\begin{cases}B_{k}^{% \mathsf{T}}&\text{if }k\in\kappa\\ I_{n}&\text{otherwise.}\end{cases}

Moreover, if $B_{1},\dots,B_{d}$ are nonsingular then $\mathrm{rank}((PM)^{\top_{\kappa}})=\mathrm{rank}(M^{\top_{\kappa}})$ .

Corollary 3.9.

$\mathrm{PT\textup{-}rank}$ is invariant under the action of $\mathrm{GL}(n)^{d}$ on $n^{d}\times n^{d}$ matrices.

Corollary 3.9 shows that $\mathrm{PT\textup{-}rank}$ generalizes to a complexity measure on multilinear functions $V_{1}\times\dots\times V_{d}\to V_{1}\times\dots\times V_{d}$ (equivalently: on tensors in $\bigotimes_{c=1}^{d}(V_{c}\otimes V_{c}^{\ast})$ ) for any $n$ -dimensional $\mathbb{F}$ -vector spaces $V_{1},\dots,V_{d}$ , independent of a choice of bases.

Note that the PT-rank of a matrix depends on its assumed dimension. For example, the PT-rank of an $n^{4}\times n^{4}$ matrix is different from its PT-rank treated as a $\widehat{n}^{2}\times\widehat{n}^{2}$ matrix where $\widehat{n}=n^{2}$ , as a different set of partial transposes are allowed. When there is ambiguity, we write $\mathrm{PT\textup{-}rank}_{[n]^{4}}(M)$ or $\mathrm{PT\textup{-}rank}_{[n^{2}]^{2}}(M)$ to distinguish these two cases.

Lemma 3.10.

$\mathrm{PT\textup{-}rank}_{[n]^{pq}}(M)\leq\mathrm{PT\textup{-}rank}_{[n^{p}]^% {q}}(M)$ whenever $d=pq$ with $p,q\geq 1$ .

Proof.

Write $M$ for the $n^{pq}\times n^{pq}$ matrix and $N$ for the equivalent $\widehat{n}^{q}\times\widehat{n}^{q}$ matrix with $\widehat{n}=n^{p}$ . For $\lambda\subseteq[q]$ , note that

\displaystyle\mathrm{rank}(N^{\top_{\lambda}})=\mathrm{rank}(M^{\top_{\kappa}}% )\quad\text{where }\kappa=\{k+(l-1)p:k\in[p],\ l\in[\lambda]\}.

The claimed inequality follows from this fact and the characterization of PT-rank given by Lemma 3.5. $\hfill\blacktriangleleft$

3.2 PT-rank and SoS complexity

We now explain the close relationship between PT-rank of $n^{d}\times n^{d}$ matrices and SoS complexity of $d$ -multiquadratic forms.

Definition 3.11 (Multiquadratic polynomial $Q_{M}$ ).

For an $n_{1}\cdots n_{d}\times n_{1}\cdots n_{d}$ matrix $M$ , let $Q_{M}$ denote the $d$ -multiquadratic polynomial

\displaystyle Q_{M}\vcentcolon=\sum_{\vec{i},\vec{j}\in[n_{1}]\times\dots% \times[n_{d}]}M_{\vec{i},\vec{j}}\cdot X^{(1)}_{i_{1}}X^{(1)}_{j_{1}}\cdots X^% {(d)}_{i_{d}}X^{(d)}_{j_{d}}.

For example, the identity matrix $I_{n^{3}}$ has corresponding $3$ -multiquadratic polynomial

\displaystyle q_{I_{n^{3}}}=\Big(\sum_{i\in[n]}X_{i}^{2}\Big)\Big(\sum_{i\in[n% ]}Y_{i}^{2}\Big)\Big(\sum_{i\in[n]}Z_{i}^{2}\Big)

where we write $X_{i},Y_{i},Z_{i}$ for $X^{(1)}_{i},X^{(2)}_{i},X^{(3)}_{i}$ . (The biquadratic polynomial $q_{n}$ in the Introduction is given by $q_{I_{n^{2}}}$ in this notation.)

Lemma 3.12.

Let $\mathbb{F}$ be algebraically closed field of characteristic $\neq 2$ . Then over $\mathbb{F}$ , we have $\mathrm{SoS}(Q_{M})\leq\mathrm{PT\textup{-}rank}(M)$ .

Proof.

Suppose $\mathrm{SoS}(Q_{M})=m<\infty$ . Then, there exist an $m\times n^{d}$ matrix $L$ such that

\displaystyle Q_{M}

\displaystyle=\sum_{\ell=1}^{m}\Big(\sum_{\vec{i}\in[n]^{d}}L_{\ell,\vec{i}}% \cdot X^{(1)}_{i_{1}}\cdots X^{(d)}_{i_{d}}\Big)^{2}=\sum_{\vec{i},\vec{j}\in[% n]^{d}}(L^{\mathsf{T}}L)_{\vec{i},\vec{j}}\cdot X^{(1)}_{i_{1}}X^{(1)}_{j_{1}}% \cdots X^{(d)}_{i_{d}}X^{(d)}_{j_{d}}.

Over an algebraically closed field, we have the familiar fact

\displaystyle\{\textup{symmetric matrices of rank}\leq m\}=\{L^{\mathsf{T}}L:L% \in\mathbb{F}^{m\times n^{d}}\}.

Therefore,
$\displaystyle\mathrm{SoS}(Q_{M})=\min\bigg\{\mathrm{rank}(D):\textup{symmetric% }D\textup{ s.t.\ }Q_{M}=\sum_{\vec{i},\vec{j}\in[n]^{d}}D_{\vec{i},\vec{j}}% \cdot X^{(1)}_{i_{1}}X^{(1)}_{j_{1}}\cdots X^{(d)}_{i_{d}}X^{(d)}_{j_{d}}\bigg\}.$

Since variables commute, the righthand equation is equivalent to $M=\frac{1}{2^{d}}\sum_{\kappa\subseteq[d]}D^{\top_{\kappa}}$ . That is,

\displaystyle\mathrm{SoS}(Q_{M})\leq\min\bigg\{\mathrm{rank}(D):M=\frac{1}{2^{% d}}\sum_{\kappa\subseteq[d-1]}D^{\top_{\kappa}}\bigg\}.

Given any decomposition $M=\sum_{\kappa\subseteq[d]}P_{\kappa}^{\top_{\kappa}}$ with $\mathrm{PT\textup{-}rank}(M)=\sum_{\kappa}\mathrm{rank}(P_{\kappa})$ , let $D=\frac{1}{2^{d}}\sum_{\kappa}P_{\kappa}$ . Then

\displaystyle\frac{1}{2^{d}}\sum_{\kappa}D^{\top_{\kappa}}=\frac{1}{2^{d}}\sum% _{\kappa}\sum_{\lambda}P_{\lambda}^{\top_{\kappa}}=\frac{1}{2^{d}}\sum_{\kappa% }(\sum_{\lambda}P_{\lambda}^{\top_{\lambda}})^{\top_{\kappa}}=\frac{1}{2^{d}}% \sum_{\kappa}M^{\top_{\kappa}}=M.

Therefore, $\mathrm{SoS}(Q_{M})\leq\mathrm{rank}(D)\leq\sum_{\kappa}\mathrm{rank}(P_{% \kappa})=\mathrm{PT\textup{-}rank}(M)$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 3.13.

Over finite fields $\mathbb{F}$ , the bound $\mathrm{SoS}(Q_{M})-1\leq\mathrm{PT\textup{-}rank}(M)$ can be proved using same ideas as above. The only difference is that following the result from [27], every symmetric matrix of rank $m$ can be expressed as $L^{\mathsf{T}}L$ for $L\in\mathbb{F}^{(m+1)\times n^{d}}$ , thus comes the additional $1$ .

As we show next, the bounds above are tight up to $O(2^{d})$ factor for fully symmetric matrices.

Lemma 3.14.

If $M$ is a fully symmetric matrix over a field of characteristic $\neq 2$ , then $\mathrm{PT\textup{-}rank}(M)\leq 2^{d-1}\,\mathrm{SoS}(Q_{M})$ .

Proof.

Suppose $\mathrm{SoS}(Q_{M})=m<\infty$ . Then there exists an $m\times n^{d}$ matrix $L$ such that

\displaystyle Q_{M}

\displaystyle=\sum_{\ell=1}^{m}\Big(\sum_{\vec{i}\in[n]^{d}}L_{\ell,\vec{i}}% \cdot X^{(1)}_{i_{1}}\cdots X^{(d)}_{i_{d}}\Big)^{2}=\sum_{\vec{i},\vec{j}\in[% n]^{d}}(L^{\mathsf{T}}L)_{\vec{i},\vec{j}}\cdot X^{(1)}_{i_{1}}X^{(1)}_{j_{1}}% \cdots X^{(d)}_{i_{d}}X^{(d)}_{j_{d}}.

Since these are commutative polynomials (in particular, $X^{(k)}_{i_{k}}X^{(k)}_{j_{k}}=X^{(k)}_{j_{k}}X^{(1)}_{i_{k}}$ ), it follows that

\displaystyle\sum_{\kappa\subseteq[d]}M^{\top_{\kappa}}=\sum_{\kappa\subseteq[% d]}(L^{\mathsf{T}}L)^{\top_{\kappa}}.

Since $M$ is fully symmetric and $L^{\mathsf{T}}L$ is symmetric, it follows that $2^{d-1}\,M=\sum_{\kappa\subseteq[d-1]}(L^{\mathsf{T}}L)^{\top_{\kappa}}$ . Therefore, we have $M=\sum_{\kappa\subseteq[d-1]}N_{\kappa}$ for matrices $N_{\kappa}\vcentcolon=\frac{1}{2^{d-1}}(L^{\mathsf{T}}L)^{\top_{\kappa}}$ . Since $\mathrm{rank}((N_{\kappa})^{\top_{\kappa}})=\mathrm{rank}(L^{\mathsf{T}}L)=s$ for each $\kappa\subseteq[d-1]$ , we have $\mathrm{PT\textup{-}rank}(M)\leq 2^{d-1}s=2^{d-1}\,\mathrm{SoS}(Q_{M})$ . $\hfill\blacktriangleleft$

Lemmas 3.14 and 3.12 together imply:

Proposition 3.15.

Let $M$ be an $n^{d}\times n^{d}$ matrix over algebraically closed or finite field of characteristic $\neq 2$ . Then $\mathrm{SoS}(Q_{M})-1\leq\mathrm{PT\textup{-}rank}(M)\leq 2^{d-1}\,\mathrm{SoS% }(Q_{M})$ .

3.3 PT-rank of almost all matrices

Although not required for any other results in this paper, we conclude this section by observing that (asymptotically) almost all $n^{d}\times n^{d}$ matrices have PT-rank $\Omega(n^{d})$ , and (asymptotically) almost all fully symmetric $n^{d}\times n^{d}$ matrices have PT-rank $\Omega((n/2)^{d})$ . These results are established standard dimension-counting arguments. (See full paper for proofs.)

Proposition 3.16.

Asymptotically almost all $n^{d}\times n^{d}$ matrices have PT-rank at least $(\frac{1}{2}-\varepsilon)n^{d}$ for every constant $\varepsilon>0$ .

Since the set of fully symmetric $n^{d}\times n^{d}$ matrices has dimension $\geq n^{2d}/2^{d}$ , a similar counting argument shows:

Proposition 3.17.

Asymptotically almost all fully symmetric $n^{d}\times n^{d}$ matrices have PT-rank at least $(\frac{1}{2^{d+1}}-\varepsilon)n^{d}$ for any constant $\varepsilon>0$ .

4 Non-commutative set-multilinear formula lower bounds from PT-rank

Recall the main theorem of this paper:

Theorem 1.5 (restated).

For every $n^{d}\times n^{d}$ matrix $M$ , we have

\displaystyle\mathcal{L}_{\mathsf{sm}}(\mathrm{ShiftedTensor}(M))

\displaystyle\geq\frac{\mathrm{PT\textup{-}rank}(M)}{n^{d-\log d+1}}.

As a helpful warm-up to the proof in §5, in this section we shall prove a strictly weaker – but slightly simpler – version of Theorem 1.5 that lower bounds the non-commutative set-multilinear formula size of $\mathrm{ShiftedTensor}(M)$ . We start with the definition:

Definition 4.1.

The non-commutative set-multilinear formula size of a tensor $A:[n]^{d}\to\mathbb{F}$ , denoted $\mathcal{L}_{\mathsf{nc,sm}}(A)$ , is defined inductively as follows:

$\blacksquare$

If $d=1$ , then $\mathcal{L}_{\mathsf{nc,sm}}(A)$ equals $1$ if $A$ is non-zero at any point and $0$ otherwise.
$\blacksquare$

If $d\geq 2$ , then $\mathcal{L}_{\mathsf{nc,sm}}(A)$ is the minimum value of $\sum_{i}\ (\mathcal{L}_{\mathsf{nc,sm}}(B_{i})+\mathcal{L}_{\mathsf{nc,sm}}(C_% {i}))$ over indexed families $\{(e_{i},f_{i},B_{i},C_{i})\}_{i}$ where $e_{i},f_{i}$ are positive integers satisfying $e_{i}+f_{i}=d$ and $B_{i}:[n]^{e_{i}}\to\mathbb{F}$ and $C_{i}:[n]^{f_{i}}\to\mathbb{F}$ are tensors such that $A=\sum_{i}B_{i}\otimes C_{i}$ .

In the remainder of this section, we prove the following:

Theorem 4.2 (Non-commutative version of Theorem 1.5).

For every $n^{d}\times n^{d}$ matrix $M$ , we have

\displaystyle\mathcal{L}_{\mathsf{nc,sm}}(\mathrm{ShiftedTensor}(M))

\displaystyle\geq\frac{\mathrm{PT\textup{-}rank}(M)}{n^{d-\log d+1}}.

4.1 The complexity measure $\rho$ on order $2d$ tensors

We introduce a complexity measure on tensors $A:[n]^{2d}\to\mathbb{F}$ , denoted $\rho(A)$ , which is closely related to PT-rank (normalized by factor $n^{-d}$ ), but with an added “max” quantifier that affects the $\top_{1}$ and $\top_{k}$ partial transposes. (A precise relationship between $\rho$ and $\mathrm{PT\textup{-}rank}$ is noted at the end of this section.)

Definition 4.3.

For any $a,b\in\{0,1\}$ and $\alpha\in\{0,1\}^{d-1}$ , we define a partition $I_{a,\alpha,b}\sqcup J_{a,\alpha,b}=[2d]$ by

	$\displaystyle I_{a,\alpha,b}$	$\displaystyle\vcentcolon=[2d]\,\cap\,\{$	$\displaystyle a,\,2+\alpha_{1},\,4+\alpha_{2},\,\dots,\,2d-2+\alpha_{d},\,2d+b$	$\displaystyle\},$
	$\displaystyle J_{a,\alpha,b}$	$\displaystyle\vcentcolon=[2d]\,\cap\,\{1-\mbox{}$	$\displaystyle a,\,3-\alpha_{1},\,5-\alpha_{2},\,\dots,\,2d-1-\alpha_{d},\,2d+1-b$	$\displaystyle\}.$

For a tensor $A:[n]^{2d}\to\mathbb{F}$ , we define its relative rank with respect to $(a,\alpha,b)\in\{0,1\}^{d+1}$ as follows:

\displaystyle\mathrm{relrk}_{a,\alpha,b}(A)

\displaystyle\vcentcolon=n^{-d}\ \mathrm{rank}(\mathrm{Mat}_{I_{a,\alpha,b},J_% {a,\alpha,b}}(A)).

Lemma 4.4.

$\mathrm{relrk}_{a,\alpha,b}(A)\leq n^{-\mathds{1}[a\neq b]}$ .

Proof.

Follows from the observation that

	$\displaystyle\|I_{a,\alpha,b}\|$	$\displaystyle=d-1+\mathds{1}[a=1]+\mathds{1}[b=0],$
	$\displaystyle\|J_{a,\alpha,b}\|$	$\displaystyle=d-1+\mathds{1}[a=0]+\mathds{1}[b=1],$

and therefore $\min\{|I_{a,\alpha,b}|,\ |J_{a,\alpha,b}|\}=d-\mathds{1}[a\neq b]$ . $\hfill\blacktriangleleft$

The next lemmas show that $\mathrm{relrk}$ is sub-additive and multiplicative.

Lemma 4.5.

$\mathrm{relrk}_{a,\alpha,b}(\sum_{i}A_{i})\leq\sum_{i}\ \mathrm{relrk}_{a,% \alpha,b}(A_{i})$ .

Proof.

Follows from sub-additivity of rank. $\hfill\blacktriangleleft$

Lemma 4.6.

For all $A:[n]^{2d}\to\mathbb{F}$ and $B:[n]^{2e}\to\mathbb{F}$ and $a,b,c\in\{0,1\}$ and $\alpha\in\{0,1\}^{d-1}$ and $\beta\in\{0,1\}^{e-1}$ , with respect to the tensor product $A\otimes B:[n]^{2(d+e)}\to\mathbb{F}$ , we have

	$\displaystyle I_{a,\alpha,b,\beta,c}$	$\displaystyle=I_{a,\alpha,b}\sqcup I_{b,\beta,c},$
	$\displaystyle J_{a,\alpha,b,\beta,c}$	$\displaystyle=J_{a,\alpha,b}\sqcup J_{b,\beta,c},$
	$\displaystyle\mathrm{Mat}_{I_{a,\alpha,b,\beta,c},J_{a,\alpha,b,\beta,c}}(A% \otimes B)$	$\displaystyle=\mathrm{Mat}_{I_{a,\alpha,b},J_{a,\alpha,b}}(A)\mathrel{% \mathchoice{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$\displaystyle% \boxtimes$}}}}{\raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$\textstyle% \boxtimes$}}}}{\raisebox{-0.83334pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle% \boxtimes$}}}}{\raisebox{-0.83336pt}{\hbox{\raisebox{0.0pt}{$% \scriptscriptstyle\boxtimes$}}}}}\mathrm{Mat}_{I_{b,\beta,c},J_{b,\beta,c}}(B),$
	$\displaystyle\mathrm{relrk}_{a,\alpha,b,\beta,c}(A\otimes B)$	$\displaystyle=\mathrm{relrk}_{a,\alpha,b}(A)\ \mathrm{relrk}_{b,\beta,c}(B).$

(Note: We only require the inequality $\mathrm{relrk}_{a,\alpha,b,\beta,c}(A\otimes B)\leq\mathrm{relrk}_{a,\alpha,b}% (A)\ \mathrm{relrk}_{b,\beta,c}(B)$ , that is, the sub-multiplicativity of $\mathrm{relrk}$ .)

Proof.

Follows from definitions and multiplicativity of matrix rank under Kronecker product. $\hfill\blacktriangleleft$

Definition 4.7.

For a tensor $A:[n]^{2d}\to\mathbb{F}$ , notation $\{X_{\alpha}\}\vdash A$ denotes that $X_{\alpha}$ are tensors $[n]^{2d}\to\mathbb{F}$ , indexed by $\alpha\in\{0,1\}^{d-1}$ , such that $A=\sum_{\alpha}X_{\alpha}$ .

We define a complexity measure $\rho(A)$ by

\displaystyle\rho(A)

\displaystyle\vcentcolon=\max_{a,b\in\{0,1\}}\ \min_{\{X_{\alpha}\}\vdash A}\ % \sum_{\alpha\in\{0,1\}^{d-1}}\ \mathrm{relrk}_{a,\alpha,b}(X_{\alpha}).

Lemma 4.8.

$\rho$ is sub-additive, that is, $\rho(\sum_{i}A_{i})\leq\sum_{i}\rho(A_{i})$ where $\{A_{i}\}_{i}$ is any indexed family of tensors $A_{i}:[n]^{2d}\to\mathbb{F}$ .

Proof.

We have

	$\displaystyle\rho(\sum_{i}A_{i})$	$\displaystyle=\max_{a,b}\ \>\hskip 1.0pt\min_{\{X_{\alpha}\}\vdash\sum_{i}A_{i% }}\ \>\hskip 1.0pt\sum_{\alpha}\ \mathrm{relrk}_{a,\alpha,b}(X_{\alpha})$
		$\displaystyle\leq\max_{a,b}\ \min_{\begin{subarray}{c}\{X_{i,\alpha}\}\vdash A% _{i}\\ X_{\alpha}\,\vcentcolon=\,\sum_{i}X_{i,\alpha}\end{subarray}}\ \sum_{\alpha}\ % \mathrm{relrk}_{a,\alpha,b}(X_{\alpha})$
		$\displaystyle=\max_{a,b}\ \min_{\{X_{i,\alpha}\}\vdash A_{i}}\ \sum_{\alpha}\ % \mathrm{relrk}_{a,\alpha,b}(\sum_{i}X_{i,\alpha})$
		$\displaystyle\leq\max_{a,b}\ \min_{\{X_{i,\alpha}\}\vdash A_{i}}\ \sum_{i}\ % \sum_{\alpha}\ \mathrm{relrk}_{a,\alpha,b}(X_{i,\alpha})$
		$\displaystyle=\max_{a,b}\ \sum_{i}\ \min_{\{X_{i,\alpha}\}\vdash A_{i}}\ \sum_% {\alpha}\ \mathrm{relrk}_{a,\alpha,b}(X_{i,\alpha})$
		$\displaystyle\leq\sum_{i}\ \max_{a,b}\ \min_{\{X_{i,\alpha}\}\vdash A_{i}}\ % \sum_{\alpha}\ \mathrm{relrk}_{a,\alpha,b}(X_{i,\alpha})$
		$\displaystyle=\sum_{i}\ \rho(A_{i}).\$

$\hfill\blacktriangleleft$

Unlike relative rank, $\rho$ is not obviously multiplicative or sub-multiplicative under tensor product. However, the following key lemma shows that $\rho$ always shrinks under tensor products. In contrast, the relative rank of a tensor product $A\otimes B$ is only guaranteed to shrink when (the matrix flattening of) $A$ or $B$ has unbalanced dimensions.

Lemma 4.9.

For all $A:[n]^{2d}\to\mathbb{F}$ and $B:[n]^{2e}\to\mathbb{F}$ , we have

\displaystyle\rho(A\otimes B)\leq n^{-1}\ \min\{\rho(A),\ \rho(B)\}.

Proof.

Let $a, b, c$ range over $\{0,1\}$ , and let $\alpha,\beta$ range over $\{0,1\}^{d-1},\{0,1\}^{e-1}$ respectively. We have

	$\displaystyle\rho(A\otimes B)$	$\displaystyle=\max_{a,c}\ \qquad\min_{\begin{subarray}{c}\{Z_{\alpha,b,\beta}% \}\vdash A\otimes B\end{subarray}}\ \qquad\sum_{\alpha,b,\beta}\ \mathrm{relrk% }_{a,\alpha,b,\beta,c}(Z_{\alpha,b,\beta})$
		$\displaystyle\leq\max_{a,c}\ \min_{\begin{subarray}{c}\{X_{\alpha}\}\vdash A,% \ \{Y_{\beta}\}\vdash B\\ Z_{\alpha,b,\beta}\,\vcentcolon=\,\mathds{1}[b=1-c]\cdot X_{\alpha}\otimes Y_{% \beta}\end{subarray}}\ \sum_{\alpha,b,\beta}\ \mathrm{relrk}_{a,\alpha,b,\beta% ,c}(Z_{\alpha,b,\beta})$
		$\displaystyle=\max_{a,c}\ \min_{\{X_{\alpha}\}\vdash A,\ \{Y_{\beta}\}\vdash B% }\ \sum_{\alpha,\beta}\ \mathrm{relrk}_{a,\alpha,1-c,\beta,c}(X_{\alpha}% \otimes Y_{\beta})$
		$\displaystyle=\max_{a,c}\ \min_{\{X_{\alpha}\}\vdash A,\ \{Y_{\beta}\}\vdash B% }\ \sum_{\alpha,\beta}\ \mathrm{relrk}_{a,\alpha,1-c}(X_{\alpha})\ \mathrm{% relrk}_{1-c,\beta,c}(Y_{\beta})\quad\text{(Lemma \ref{la:relrk-mult})}$
		$\displaystyle\leq\max_{a,c}\ \min_{\{X_{\alpha}\}\vdash A,\ \{Y_{\beta}\}% \vdash B}\ \sum_{\alpha,\beta}\ \mathrm{relrk}_{a,\alpha,1-c}(X_{\alpha})\ n^{% -1}\quad\text{(Lemma \ref{la:deficit})}$
		$\displaystyle=n^{-1}\ \max_{a,c}\ \min_{\{X_{\alpha}\}\vdash A}\ \sum_{\alpha}% \ \mathrm{relrk}_{a,\alpha,1-c}(X_{\alpha})$
		$\displaystyle=n^{-1}\ \max_{a,b}\ \min_{\{X_{\alpha}\}\vdash A}\ \sum_{\alpha}% \ \mathrm{relrk}_{a,\alpha,b}(X_{\alpha})$
		$\displaystyle=n^{-1}\ \rho(A).\$

The proof of $\rho(A\otimes B)\leq\ n^{-1}\rho(B)$ follows similarly. $\hfill\blacktriangleleft$

4.2 Non-commutative formula lower bounds from $\rho$

Definition 4.10 (The order $d$ flattening $A^{\flat}:[n^{2}]^{d}\to\mathbb{F}$ of an order $2d$ tensor $A:[n]^{2d}\to\mathbb{F}$ ).

For an order $2d$ tensor $A:[n]^{2d}\to\mathbb{F}$ , we define its order $d$ flattening $A^{\flat}:[n^{2}]^{d}\to\mathbb{F}$ by the identity

\displaystyle A(a_{1},b_{1},\dots,a_{d},b_{d})=A^{\flat}(\langle a_{1},b_{1}% \rangle,\dots,\langle a_{d},b_{d}\rangle)

for all $a_{1},b_{1},\dots,a_{d},b_{d}\in[n]$ .

Note that this flattening operation commutes with the tensor product: for any $A:[n]^{2d}\to\mathbb{F}$ and $B:[n]^{2e}\to\mathbb{F}$ , we have $(A\otimes B)^{\flat}=A^{\flat}\otimes B^{\flat}$ (as tensors $[n]^{2(d+e)}\to\mathbb{F}$ ).

Theorem 4.11.

For every $A:[n]^{2d}\to\mathbb{F}$ , we have $\mathcal{L}_{\mathsf{nc,sm}}(A^{\flat})\geq n^{\log d}\ \rho(A)$ . That is, any non-commutative set-multilinear formula computing the flattened tensor $A^{\flat}:[n^{2}]^{d}\to\mathbb{F}$ has size at least $n^{\log d}\ \rho(A)$ .

Proof.

We argue by induction on $d$ . The base case $d=1$ is trivial. Assume $d\geq 2$ and fix $\{(e_{i},f_{i},B_{i},C_{i})\}_{i}$ with $e_{i},f_{i}\geq 1$ and $e_{i}+f_{i}=d$ and $B_{i}:[n]^{e_{i}}\to\mathbb{F}$ and $C_{i}:[n]^{f_{i}}\to\mathbb{F}$ such that $A=\sum_{i}\ B_{i}\otimes C_{i}$ and $\mathcal{L}_{\mathsf{nc,sm}}(A^{\flat})=\sum_{i}\ (\mathcal{L}_{\mathsf{nc,sm}% }(B_{i}^{\flat})+\mathcal{L}_{\mathsf{nc,sm}}(C_{i}^{\flat})).$

We have

	$\displaystyle\mathcal{L}_{\mathsf{nc,sm}}(A^{\flat})$	$\displaystyle\geq\sum_{i}\,\Big(n^{\log e_{i}}\ \rho(B_{i})+n^{\log f_{i}}\ % \rho(C_{i})\Big)\quad\text{(induction hypothesis)}$
		$\displaystyle\geq\sum_{i\,:\,e_{i}\,\geq\,d/2}n^{\log e_{i}}\ \rho(B_{i})+\sum% _{i\,:\,f_{i}\,>\,d/2}n^{\log f_{i}}\ \rho(C_{i})$
		$\displaystyle\geq\sum_{i\,:\,e_{i}\,\geq\,d/2}n^{\log e_{i}+1}\ \rho(B_{i}% \otimes C_{i})+\sum_{i\,:\,f_{i}\,>\,d/2}n^{\log f_{i}+1}\ \rho(B_{i}\otimes C% _{i})\quad\text{(Lemma \ref{la:rho-tensor})}$
		$\displaystyle\geq n^{\log d}\ \sum_{i}\,\rho(B_{i}\otimes C_{i})$
		$\displaystyle\geq n^{\log d}\ \rho(\sum_{i}B_{i}\otimes C_{i})\quad\text{(% Lemma \ref{la:rho-subadd})}$
		$\displaystyle=n^{\log d}\ \rho(A).\$

$\hfill\blacktriangleleft$

We are finally ready to prove Theorem 4.2.

Proof of Theorem 4.2.

Let $M$ be an $n^{d}\times n^{d}$ matrix. Recall the order $d+1$ tensor $\mathrm{ShiftedTensor}(M):[n^{2}]^{d+1}\to\mathbb{F}$ , which equals $\mathrm{PaddedTensor}(M)^{\flat}$ for the order $2d+2$ tensor $\mathrm{PaddedTensor}(M):[n]^{2d+2}\to\mathbb{F}$ defined by
$\displaystyle\mathrm{PaddedTensor}(M)(p,i_{1},j_{1},i_{2},\dots,j_{d-1},i_{d},% j_{d},q)$ $\displaystyle=\mathds{1}\{p=q=1\}\cdot M_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{% d})},$ $\displaystyle\mathrm{ShiftedTensor}(M)(\langle p,i_{1}\rangle,\langle j_{1},i_% {2}\rangle,\dots,\langle j_{d-1},i_{d}\rangle,\langle j_{d},q\rangle)$ $\displaystyle=\mathds{1}\{p=q=1\}\cdot M_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{% d})}.$

It follows immediately from definitions of $\mathrm{PT\textup{-}rank}$ and $\rho$ that $\mathrm{PT\textup{-}rank}(M)=n^{d+1}\,\rho(\mathrm{PaddedTensor}(M))$ . Theorem 4.11 now implies the desired bound

\displaystyle\mathcal{L}_{\mathsf{nc,sm}}(\mathrm{ShiftedTensor}(M))\geq n^{% \log d}\ \rho(\mathrm{PaddedTensor}(M))

\displaystyle=\frac{\mathrm{PT\textup{-}rank}(M)}{n^{d-\log d+1}}.\

$\hfill\blacktriangleleft$

5 Commutative set-multilinear formula lower bounds from PT-rank

This section generalizes the argument in the last section to prove our main theorem (Theorem 1.5).

5.1 Extending $\rho$ to tensors over subgraphs of $\mathrm{Path}_{d}$

Instead of considering tensors $[n]^{2d}\to\mathbb{F}$ , we consider tensors $[n]^{D(G)}\to\mathbb{F}$ with coordinates indexed by the (symmetric) directed edge set of a subgraph $G$ of an undirected path graph.

Let $\mathrm{Path}_{\mathbb{Z}}$ be the undirected path graph with vertex set $\{v_{i}:i\in\mathbb{Z}\}$ and edge set $\{\{v_{i-1},v_{i}\}:i\in\mathbb{Z}\}$ .

Let $G=(V(G),E(G))$ , $E(G)\subseteq\binom{V(G)}{2}$ , range over nonempty finite subgraphs of $\mathrm{Path}_{\mathbb{Z}}$ with no isolated vertices (i.e., $V(G)=\bigcup_{e\in E(G)}e$ ). We next introduce some useful notation:

$\blacksquare$

We consider the partition $V_{1}(G)\sqcup V_{2}(G)=V(G)$ defined by

$\displaystyle V_{1}(G)$ $\displaystyle\vcentcolon=\{v\in V(G):v\text{ has degree $1$ in }G\},$

$\displaystyle V_{2}(G)$ $\displaystyle\vcentcolon=\{v\in V(G):v\text{ has degree $2$ in }G\}.$
$\blacksquare$

Let $D(G)\subseteq V(G)\times V(G)$ be the (symmetric) set of directed edges of $G$ , that is,

$\displaystyle D(G)$ $\displaystyle\vcentcolon=\{vw:\{v,w\}\in E(G)\}.$

We consider the partition $D_{1}(G)\sqcup D_{2}(G)=D(G)$ defined by

$\displaystyle D_{1}(G)$ $\displaystyle\vcentcolon=\{vw\in D(G):v\in V_{1}(G)\},$

$\displaystyle D_{2}(G)$ $\displaystyle\vcentcolon=\{vw\in D(G):v\in V_{2}(G)\}.$

Note that $|D_{1}(G)|=|V_{1}(G)|$ and $|D_{2}(G)|=2|V_{2}(G)|$ .

$\blacksquare$

For any set $S\subseteq V(\mathrm{Path}_{\mathbb{Z}})$ , let $\mathcal{P}(S)$ denote the set of pairs $\gamma=(I_{\gamma},J_{\gamma})$ of disjoint sets $I_{\gamma},J_{\gamma}\subseteq D(\mathrm{Path}_{\mathbb{Z}})$ such that

$\displaystyle S=\{v:vu\in I_{\gamma}\}=\{v:vw\in J_{\gamma}\}.$

(That is, for each $v_{i}\in S$ with neighbors $v_{i-1},v_{v_{i+1}}$ in $\mathrm{Path}_{\mathbb{Z}}$ , exactly one of the sets $I_{\gamma}$ and $J_{\gamma}$ contains $v_{i}v_{i-1}$ and the other contains $v_{i}v_{v_{i+1}}$ .) Note that $|I_{\gamma}|=|J_{\gamma}|=|S|$ and $|\mathcal{P}(S)|=2^{|S|}$ .
$\blacksquare$

For disjoint sets $S_{1},S_{2}\subseteq V(\mathrm{Path}_{\mathbb{Z}})$ and $\gamma_{1}\in\mathcal{P}(S_{1})$ and $\gamma_{2}\in\mathcal{P}(\gamma_{2})$ , let

$\displaystyle\gamma_{1}\sqcup\gamma_{2}\vcentcolon=(I_{\gamma_{1}}\sqcup I_{% \gamma_{2}},J_{\gamma_{1}}\sqcup J_{\gamma_{2}})\in\mathcal{P}(S_{1}\sqcup S_{% 2}).$

We now consider tensors $A:[n]^{D(G)}\to\mathbb{F}$ and define analogues of $\mathrm{relrk}$ and $\rho$ .

$\blacktriangleright$ Remark 5.1.

When $G$ is a path of length $d$ with vertices $v_{0},\dots,v_{d}$ , we identify the sequence of directed edges $v_{0}v_{1},v_{1}v_{0},v_{1}v_{2},v_{2}v_{1},\dots,v_{d-1}v_{d},v_{d}v_{d-1}$ with integers $1,\dots,2d$ . We thus identify $D(G)$ with the set $[2d]$ and tensors $[n]^{D(G)}\to\mathbb{F}$ with tensors $[n]^{2d}\to\mathbb{F}$ . Under this identification, the following definitions of $\mathrm{relrk}$ and $\rho$ directly generalize those in §4.

Definition 5.2.

For a graph $G\subseteq\mathrm{Path}_{\mathbb{Z}}$ and tensor $A:[n]^{D(G)}\to\mathbb{F}$ and $\alpha\in\mathcal{P}(V_{2}(G))$ and $\gamma\in\mathcal{P}(V_{1}(G))$ , we define

\displaystyle\mathrm{relrk}_{\alpha,\gamma}(A)

\displaystyle\vcentcolon=n^{-|E(G)|}\ \mathrm{rank}(\mathrm{Mat}_{I_{\alpha}% \sqcup(I_{\gamma}\cap D_{1}(G)),\,J_{\alpha}\sqcup(J_{\gamma}\cap D_{1}(G))}(A% )).

Definition 5.3.

For a graph $G\subseteq\mathrm{Path}_{\mathbb{Z}}$ and tensor $A:[n]^{D(G)}\to\mathbb{F}$ , notation $\{X_{\alpha}\}\vdash A$ denotes that $X_{\alpha}$ are tensors $[n]^{D(G)}\to\mathbb{F}$ , indexed by $\alpha\in\mathcal{P}(V_{2}(G))$ , such that $A=\sum_{\alpha}X_{\alpha}$ .

We define the complexity measure $\rho(A)$ by

\displaystyle\rho(A)

\displaystyle\vcentcolon=\max_{\gamma\in\mathcal{P}(V_{1}(G))}\ \min_{\{X_{% \alpha}\}\vdash A}\ \sum_{\alpha\in\mathcal{P}(V_{2}(G))}\ \mathrm{relrk}_{% \alpha,\gamma}(X_{\alpha}).

Lemma 5.4.

$\rho(\sum_{i}A_{i})\leq\sum_{i}\rho(A_{i})$ .

Note that $|I_{\alpha}|=|J_{\alpha}|=|V_{2}(G)|$ and $|D_{1}(G)\cap I_{\gamma}|+|D_{1}(G)\cap J_{\gamma}|=|V_{1}(G)|$ . As a consequence, we get the following generalization of Lemma 4.4.

Lemma 5.5.

$\mathrm{relrk}_{\alpha,\gamma}(A)\leq n^{-|\,|I_{\gamma}\,\cap\,D_{1}(G)|\,-\,% |J_{\gamma}\,\cap\,D_{1}(G)|\,|}$ .

Part (a) of the next lemma shows that the bound of Lemma 5.5 may be as small as $n^{-|V_{1}(G)|}$ . Part (b) makes a related observation that will be useful later.

Lemma 5.6.

(a)

For every graph $G\subseteq\mathrm{Path}_{\mathbb{Z}}$ , there exist unique elements $\gamma^{+},\gamma^{-}\in\mathcal{P}(V_{1}(G))$ such that

$\displaystyle I_{\gamma^{+}}=J_{\gamma^{-}}=D_{1}(G),\qquad J_{\gamma^{+}}\cap D% _{1}(G)=I_{\gamma^{-}}\cap D_{1}(G)=\emptyset.$
(b)

For all edge-disjoint graphs $G,H\subseteq\mathrm{Path}_{\mathbb{Z}}$ , there exist unique elements $\delta^{+},\delta^{-}\in\mathcal{P}(V_{1}(G)\cap V_{1}(H))$ such that

$\displaystyle I_{\delta^{+}}=J_{\delta^{-}}=D_{1}(G)\cap D_{1}(H),\qquad J_{% \delta^{+}}\cap D_{1}(H)=I_{\delta^{-}}\cap D_{1}(H)=\emptyset.$

Proof.

(a)

Consider any $v\in V_{1}(G)$ with neighbors $u, w$ in $\mathrm{Path}_{\mathbb{Z}}$ . Without loss of generality, $\{v,u\}\notin E(G)$ and $\{v,w\}\in E(G)$ . We include $v w$ in $I_{\gamma^{+}}$ ( $=J_{\gamma^{-}}$ ) and $v u$ in $I_{\gamma^{-}}$ ( $=J_{\gamma^{+}}$ ).
(b)

Consider any $v\in V_{1}(G)\cap V_{1}(H)$ with neighbors $u, w$ in $\mathrm{Path}_{\mathbb{Z}}$ . Without loss of generality, $\{v,u\}\in E(G)\setminus E(H)$ and $\{v,w\}\in E(H)\setminus E(G)$ . We include $v w$ in $I_{\delta^{+}}$ ( $=J_{\delta^{-}}$ ) and $v u$ in $I_{\delta^{-}}$ ( $=J_{\delta^{+}}$ ).

$\hfill\blacktriangleleft$

Lemma 5.7.

Suppose that $G, H$ are edge-disjoint finite subgraphs of $\mathrm{Path}_{\mathbb{Z}}$ , let $A:[n]^{D(G)}\to\mathbb{F}$ and $B:[n]^{D(H)}\to\mathbb{F}$ , and consider the tensor product $A\otimes B:[n]^{D(G\cup H)}\to\mathbb{F}$ . For all

	$\displaystyle\alpha\in\mathcal{P}(V_{2}(G)),\quad\beta\in\mathcal{P}(V_{2}(H))% ,\quad\delta\in\mathcal{P}(V_{1}(G)\cap V_{1}(H)),$
	$\displaystyle\xi\in\mathcal{P}(V_{1}(G)\setminus V_{1}(H)),\quad\zeta\in% \mathcal{P}(V_{1}(H)\setminus V_{1}(G)),$

we have

\displaystyle\mathrm{relrk}_{\alpha\cup\beta\cup\delta,\,\xi\cup\zeta}(A% \otimes B)

\displaystyle=\mathrm{relrk}_{\alpha,\,\xi\cup\delta}(A)\ \mathrm{relrk}_{% \beta,\,\zeta\cup\delta}(B).

Lemma 5.8.

For all edge-disjoint $G,H\subseteq\mathrm{Path}_{\mathbb{Z}}$ and tensors $A:[n]^{D(G)}\to\mathbb{F}$ and $B:[n]^{D(H)}\to\mathbb{F}$ , we have

\displaystyle\rho(A\otimes B)\leq n^{-|V_{1}(G)\,\cap\,V_{1}(H)|}\ \min\{\rho(% A),\ \rho(B)\}.

(See full paper for the proof, which is similar to Lemma 5.7.)

5.2 Set-multilinear formula lower bounds from $\rho$

The next definition generalizes the flattening operation $\flat$ introduced in Def. 4.10.

Definition 5.9.

For any $G\subseteq\mathrm{Path}_{\mathbb{Z}}$ and $A:[n]^{D(G)}\to\mathbb{F}$ , let $A^{\flat}:[n^{2}]^{E(G)}\to\mathbb{F}$ denote the flattened tensor defined in the natural way: for $x\in[n]^{D(G)}$ , we have $A^{\flat}(y)=A(x)$ where $y\in[n^{2}]^{E(G)}$ is the element defined by $y_{\{v_{i-1},v_{i}\}}=\langle x_{v_{i-1}},x_{v_{i}}\rangle$ for each $i\in\mathbb{Z}$ such that $\{v_{i-1},v_{i}\}\in E(G)$ .

The analog of Theorem 4.11 for (commutative) set-multilinear formulas has a similar proof based on the inductive definition of $\mathcal{L}_{\mathsf{sm}}$ However, instead of $\log d$ in the exponent of $n$ , the relevant parameter becomes $\log\ell(G)$ where $\ell(G)$ is the length of the longest path in $G$ . We record this notation below:

Definition 5.10.

For $G\subseteq\mathrm{Path}_{\mathbb{Z}}$ , let $\ell(G)$ denote the length of the longest path in $G$ (i.e., the maximal number of edges in a connected component of $G$ ).

Theorem 5.11.

For every $G\subseteq\mathrm{Path}_{\mathbb{Z}}$ and $A:[n]^{D(G)}\to\mathbb{F}$ , we have

\displaystyle\mathcal{L}_{\mathsf{sm}}(A^{\flat})\geq n^{\log\ell(G)}\ \rho(A).

That is, any set-multilinear arithmetic formula computing the flattened tensor $A^{\flat}:[n^{2}]^{E(G)}\to\mathbb{F}$ has size at least $n^{1+\log\ell(G)}\ \rho(A)$ .

Proof.

We argue by induction on $|E(G)|$ . The base case $|E(G)|=1$ is trivial, since $|E(G)|-|V(G)|+1+\log|E(G)|=0$ and $\rho(A)\leq 1$ .

Now assume $|E(G)|\geq 2$ and fix $\{(H_{i},K_{i},B_{i},C_{i})\}_{i}$ with $H_{i},K_{i}\subsetneqq G$ such that $H_{i}\cup K_{i}=G$ and $B_{i}:[n]^{D(H_{i})}\to\mathbb{F}$ and $C_{i}:[n]^{D(K_{i})}\to\mathbb{F}$ such that $A=\bigcup_{i}B_{i}\otimes C_{i}$ and $\mathcal{L}_{\mathsf{sm}}(A^{\flat})=\sum_{i}\ (\mathcal{L}_{\mathsf{sm}}(B_{i% }^{\flat})+\mathcal{L}_{\mathsf{sm}}(C_{i}^{\flat}))$ .

Note that for all $i$ ,

\displaystyle\ell(G)\leq\max\{\ell(H_{i}),\,\ell(K_{i})\}\cdot(|V_{1}(H_{i})% \cap V_{1}(K_{i})|+1).

Therefore,

\displaystyle\log\ell(G)\leq\max\{\log\ell(H_{i}),\,\log\ell(K_{i})\}+|V_{1}(H% _{i})\cap V_{1}(K_{i})|.

We now have

	$\displaystyle\mathcal{L}_{\mathsf{sm}}(A^{\flat})$	$\displaystyle\geq\sum_{i}\,\Big(n^{\log\ell(H_{i})}\ \rho(B_{i})+n^{\log\ell(K% _{i})}\ \rho(C_{i})\Big)\quad\text{(induction hypothesis)}$
		$\displaystyle\geq\sum_{i}\,n^{\max\{\log\ell(H_{i}),\,\log\ell(K_{i})\}\,+\,\|V% _{1}(H_{i})\,\cap\,V_{1}(K_{i})\|}\ \rho(B_{i}\otimes C_{i})\quad\text{(Lemma % \ref{la:rho-tensor2})}$
		$\displaystyle\geq n^{\log\ell(G)}\ \sum_{i}\ \rho(B_{i}\otimes C_{i})$
		$\displaystyle\geq n^{\log\ell(G)}\ \rho(\,\sum_{i}\,B_{i}\otimes C_{i})\quad% \text{(Lemma \ref{la:rho-subadd2})}$
		$\displaystyle=n^{\log\ell(G)}\ \rho(A).\$

$\hfill\blacktriangleleft$

In the special case where $G$ is path of length $d$ , Theorem 5.11 has the following corollary, which directly strengthens Theorem 4.11 by replacing $\mathcal{L}_{\mathsf{nc,sm}}$ with $\mathcal{L}_{\mathsf{sm}}$ .

Corollary 5.12.

For every $A:[n]^{2d}\to\mathbb{F}$ , we have $\mathcal{L}_{\mathsf{sm}}(A^{\flat})\geq n^{\log d}\ \rho(A)$ .

Finally, Theorem 1.5 follows directly from Theorem 4.11 via the same observation that

\displaystyle\mathrm{PT\textup{-}rank}(M)=n^{d+1}\,\rho(\mathrm{PaddedTensor}(% M))

for every $n^{d}\times n^{d}$ matrix $M$ and that $\mathrm{ShiftedTensor}(M)=\mathrm{PaddedTensor}(M)^{\flat}$ .

6 Upper bounds and candidate hard matrices for PT-rank

In this section, we first present some known PT-rank upper bounds for certain families of matrices. These bounds are based on Hrubes’ recent subquadratic upper bound for the sum-of-squares problem [14]. Then, we give some explicit candidate hard matrices that might realize our desired lower bound.

6.1 Kronecker products of $n\times n$ matrices have low PT-rank

Recall Hrubeš’ upper bound $\mathrm{SoS}(q_{n})=O(n^{1.62})$ (Theorem 1.1). By Proposition 3.15, this is equivalent to $\mathrm{PT\textup{-}rank}(I_{n^{2}})=O(n^{1.62})$ . This immediately gives the following upper bound on $\mathrm{PT\textup{-}rank}(I_{n^{d}})$ for all $d$ .

Proposition 6.1.

$\mathrm{PT\textup{-}rank}(I_{n^{d}})=n^{0.81d+O(1)}$ .

Proof.

We prove the bound $\mathrm{PT\textup{-}rank}(I_{n^{d}})=O(n^{0.81d})$ in the case where $d$ is even. (The bound $n^{0.81d+O(1)}$ for odd $d$ follows by monotonicity.) This bound is given by the following calculation:

\displaystyle\mathrm{PT\textup{-}rank}_{[n]^{d}}(I_{n^{d}})

\displaystyle\leq\mathrm{PT\textup{-}rank}_{[n^{d/2}]^{2}}(I_{(n^{d/2})^{2}})=% O((n^{d/2})^{1.62})=O(n^{0.81d}).

The first inequality holds since $\mathrm{PT\textup{-}rank}_{[n]^{d}}$ can use $\top_{\kappa}$ for all $\kappa\subseteq[d-1]$ , whereas $\mathrm{PT\textup{-}rank}_{[n^{d/2}]^{2}}$ can only use $\top_{\kappa}$ for $\kappa\in\{\emptyset,[d/2]\}$ . $\hfill\blacktriangleleft$

Notice that the PT-rank bound of Proposition 6.1 involves only two partial transposes, namely $\top_{\emptyset}$ and $\top_{[d/2]}$ . Using all $2^{d}$ partial transposes, we can show a much stronger upper bound:

Proposition 6.2.

$\mathrm{PT\textup{-}rank}(I_{n^{d}})=n^{O(d^{0.7})}$ .

Proof.

The construction by Hrubeš shows that

\displaystyle\prod_{i=1}^{d}\bigg(\sum_{j=1}^{n}X_{i,j}^{2}\bigg)=\prod_{i^{% \prime}=1}^{d/2}\bigg(\sum_{j^{\prime}=1}^{O(n^{1.62})}f_{i^{\prime},j^{\prime% }}^{2}\bigg),

where $f_{i^{\prime},j^{\prime}}$ is a bilinear form in $\{X_{i,(2j^{\prime}-1)}\}_{i=1}^{d}$ and $\{X_{i,(2j^{\prime})}\}_{i=1}^{d}$ . We may repeat the step by considering $f_{i^{\prime}j^{\prime}}$ as new variables. Inductively, this gives

\displaystyle\prod_{i=1}^{d}\bigg(\sum_{j=1}^{n}X_{i,j}^{2}\bigg)=\sum_{j^{% \prime}=1}^{s}g_{j^{\prime}}^{2},

where $g_{j^{\prime}}$ is multilinear in the $d$ sets of variables and

\displaystyle s=O(n^{(1.62)^{\log_{2}d}})\leq n^{O(d^{0.7})}.

The corollary follows from Proposition 3.15. $\hfill\blacktriangleleft$

The upper bound above extends to Kronecker products of $n\times n$ matrices, via $GL(n,\mathbb{F})^{d}$ -invariance of PT-rank (Lemma 3.8). Thus, we have proved:

Theorem 6.3.

If $M$ is a Kronecker product of $d$ $n\times n$ matrices, then $\mathrm{PT\textup{-}rank}(M)$ is at most $n^{O(d^{0.7})}$ .

6.2 Matrices in $\mathsf{VBP_{ord}}$ have low PT-rank

The Kronecker products of $n\times n$ matrices have low PT-rank. Using this fact, we may derive an upper bound for all matrices whose shifted tensors are in the complexity class $\mathsf{VBP_{ord}}$ .

Definition 6.4 (Ordered algebraic branching programs).

Let $f$ be a set-multilinear polynomial over $\mathbb{F}$ of degree $d$ in variable sets $X^{(1)},X^{(2)},\dots,X^{(d)}$ . We say that $f$ has an ordered algebraic branching program of width $w$ and size $s$ if

\displaystyle f=v_{1}^{\mathsf{T}}M_{1}M_{2}\cdots M_{d}v_{2},

where $v_{1}\in\mathbb{F}^{w_{0}}$ and $v_{2}\in\mathbb{F}^{w_{d}}$ are vectors whose entries are in $\mathbb{F}$ , $M_{i}\in\mathbb{F}^{w_{i-1}\times w_{i}}$ are matrices whose entries are linear combinations of variables in $X_{i}$ for $i\in[d]$ , and the following holds:

\displaystyle w_{i}\leq w\text{ for }0\leq i\leq[d]\text{ and }\sum_{i=0}^{d}w% _{i}\leq s.

Definition 6.5 ( $\mathsf{VBP_{ord}}$ ).

A sequence of set-multilinear polynomials with $n$ variables is in $\mathsf{VBP_{ord}}$ if and only if it can be computed by a sequence of ordered algebraic branching programs with size $s=n^{O(1)}$ .

An ordered algebraic branching program for a tensor $A$ is an ordered algebraic branching program for its associated set-multilinear polynomial $P_{A}$ (as defined in Section 2.3). The class $\mathsf{VBP_{ord}}$ is defined for tensors similarly.

Our main result (Theorem 1.5) shows that sufficiently strong lower bounds on $\mathrm{PT\textup{-}rank}(M)$ for explicit matrices $M$ would imply a separation of classes $\mathsf{VNC^{1}}$ and $\mathsf{VNP}$ . For a more stringent notion of “explicit”, this reduction could even potentially separate $\mathsf{VNC^{1}}$ from $\mathsf{VP}$ (i.e., arithmetic formulas from circuits). In this section, however, we describe a limitation of PT-rank by showing that it cannot separate $\mathsf{VNC^{1}}$ from $\mathsf{VBP_{ord}}$ (i.e., arithmetic formulas from ordered branching programs).

Theorem 6.6.

For any sequence of $n^{d}\times n^{d}$ matrices $M$ such that $\mathrm{ShiftedTensor}(M)\in\mathsf{VBP_{ord}}$ , we have $\mathrm{PT\textup{-}rank}(M)\leq n^{0.81d+O(1)}$ .

(See full paper for the proof.)

6.3 Candidate hard matrices

We now propose a natural family of $n^{d}\times n^{d}$ matrices over $\mathbb{F}=\mathbb{C}$ which are plausible candidates for having nearly maximal PT-rank.

Definition 6.7.

Let $d$ be an even integer. Let $n$ be a prime power such that $n>2d$ . Let $T$ be an $d\times d$ matrix over the prime field $\mathbb{F}_{n}$ . Let $\omega=e^{2\pi i/n}$ be a primitive $n$ th root of unity. Then, define the $n^{d}\times n^{d}$ matrix $W_{T}$ over $\mathbb{C}$ by

\displaystyle(W_{T})_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{d})}=\omega^{(i_{1},% \dots,i_{d})T(j_{1},\dots,j_{d})^{\top}}.

With the definition above, we first consider three choices $T_{1},T_{2},T_{3}$ that don’t work, that is, where $W_{T}$ has small PT-rank.

Identity matrix

For $T_{1}=I_{d}$ , we have

\displaystyle(W_{T_{1}})_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{d})}=\omega^{(i_% {1},\dots,i_{d})(j_{1},\dots,j_{d})^{\top}}.

We may define $n\times n$ matrices $W_{T_{1},l}$ for $l\in[d]$ by $(W_{T_{1},l})_{i_{l},j_{l}}=\omega^{i_{l}j_{l}}$ . Then, we have $W_{T_{1}}=W_{T_{1},1}\mathrel{\mathchoice{\raisebox{-0.83333pt}{\hbox{% \raisebox{0.0pt}{$\displaystyle\boxtimes$}}}}{\raisebox{-0.83333pt}{\hbox{% \raisebox{0.0pt}{$\textstyle\boxtimes$}}}}{\raisebox{-0.83334pt}{\hbox{% \raisebox{0.0pt}{$\scriptstyle\boxtimes$}}}}{\raisebox{-0.83336pt}{\hbox{% \raisebox{0.0pt}{$\scriptscriptstyle\boxtimes$}}}}}\cdots\mathrel{\mathchoice{% \raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\boxtimes$}}}}{% \raisebox{-0.83333pt}{\hbox{\raisebox{0.0pt}{$\textstyle\boxtimes$}}}}{% \raisebox{-0.83334pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\boxtimes$}}}}{% \raisebox{-0.83336pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\boxtimes$}}}}% }W_{T_{1},d}$ . By Theorem 6.3, this implies $\mathrm{PT\textup{-}rank}(W_{T_{1}})=n^{O(d^{0.7})}.$

Cyclic matrix

Consider the cyclic permutation matrix $T_{2}$ defined by

\displaystyle(T_{2})_{a,b}=1[a+1\equiv b\mod{d}].

For this choice of $T_{2}$ , we have

\displaystyle(W_{T_{2}})_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{d})}=\omega^{(i_% {1},\dots,i_{d-1},i_{d})(j_{2},\dots,j_{d},j_{1})^{\top}}.

Let $\kappa=\{1,3,5,\dots,d-1\}$ . Then, by definition of partial transpose, we have

\displaystyle(W_{T_{2}}^{\top_{\kappa}})_{(j_{1},i_{2},\dots,j_{d-1},i_{d}),(i% _{1},j_{2},\dots,i_{d-1},j_{d})}=(W_{T_{2}})_{(i_{1},\dots,i_{d}),(j_{1},\dots% ,j_{d})}=\omega^{(i_{1},\dots,i_{d-1},i_{d})(j_{2},\dots,j_{d},j_{1})^{\top}}.

Define $n^{d}$ vectors $u$ and $v$ by

\displaystyle u_{(j_{1},i_{2},\dots,j_{d-1})}=\omega^{(i_{2},i_{4},\dots,i_{d}% )(j_{1},j_{3},\dots,j_{d-1})^{\top}},v_{(i_{1},j_{2},\dots,i_{d-1})}=\omega^{(% i_{1},i_{3},\dots,i_{d-1})(j_{2},j_{4},\dots,j_{d})^{\top}}.

We then have $W_{T_{2}}^{\top_{\kappa}}=uv^{\top}$ , which means it has rank $1$ . Therefore, $\mathrm{PT\textup{-}rank}(W_{T_{2}})=1$ .

Upper triangular matrix

Consider the upper triangular matrix $T_{3}$ defined by

\displaystyle(T_{3})_{a,b}=1[a\leq b].

For this choice of $T_{3}$ , we have $(W_{T_{3}})_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{d})}=\omega^{\sum_{k\leq l}i_% {k}j_{l}}.$

Let $A$ be the unique $[n]^{2d}$ tensor such that $A^{\flat}=\mathrm{ShiftedTensor}(W_{T_{3}})$ . Then,

\displaystyle A(p,i_{1},j_{1},i_{2},\dots,j_{d},q)=(W_{T_{3}})_{(i_{1},\dots,i% _{d}),(j_{1},\dots,j_{d})}.

Then, it can be observed that $\mathrm{rank}(\mathrm{Mat}_{\{1,\dots,d+1\},\{d+2,\dots,2d+2\}})\leq n^{2}$ . (In fact, $A^{\flat}\in\mathsf{VBP_{ord}}$ .) Therefore, $\mathrm{PT\textup{-}rank}(W_{T_{3}})\leq n^{0.81d+O(1)}$ by Theorem 6.6.

The three matrices $T_{1},T_{2},T_{2}$ considered above give rise to $W_{T}$ with small PT-rank. We now give some evidence that a Cauchy matrix (in which every submatrix has full rank) might be a good choice of $T$ . (See full paper for proofs of the propositions in this section.)

Definition 6.8.

For $\lambda\subseteq[d]$ , let $W_{T}^{[\lambda]}$ be the $n^{2|\lambda|}\times n^{2(d-|\lambda|)}$ matrix defined by

\displaystyle(W_{T}^{[\lambda]})_{(i_{\lambda},j_{\lambda}),(i_{\lambda^{c}},j% _{\lambda^{c}})}\;=\;(W_{T})_{(i_{1},\dots,i_{d}),(j_{1},\dots,j_{d})}.

Proposition 6.9.

Let $T$ be a Cauchy matrix. For every $\lambda\subseteq[d]$ , the matrix $W_{T}^{[\lambda]}\in\mathbb{C}^{\,n^{2|\lambda|}\times n^{2(d-|\lambda|)}}$ has full rank:

\displaystyle\mathrm{rank}(W_{T}^{[\lambda]})\;=\;n^{\,2\min\{|\lambda|,\,d-|% \lambda|\}}.

The two propositions above disable the only two upper bound techniques we know: taking a single partial transpose, and finding some flattening of $K_{T}$ with small rank in order to apply Hrubeš’ construction.

References

[1] John F Adams and Michael F Atiyah. K-theory and the hopf invariant. The Quarterly Journal of Mathematics, 17(1):31–38, 1966.
[2] Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.12.
[3] V Arvind and S Raja. Some lower bound results for set-multilinear arithmetic computations. Chicago Journal OF Theoretical Computer Science, 6:1–262, 2016.
[4] Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi. Algebraic complexity theory, volume 315. Springer Science & Business Media, 2013.
[5] Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference (CCC 2018), volume 102 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.CCC.2018.12.
[6] Prerona Chatterjee. Separating abps and some structured formulas in the non-commutative setting. In 36th Computational Complexity Conference, 2021.
[7] Daniel Dugger and Daniel C Isaksen. The hopf condition for bilinear forms over arbitrary fields. Annals of mathematics, pages 943–964, 2007.
[8] Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. Weighted sum-of-squares lower bounds for univariate polynomials imply $\mathrm{VP}\neq\mathrm{VNP}$ . computational complexity, 33(1):1–54, 2024.
[9] Zeev Dvir, G Malod, S Perifel, and A Yehudayoff. Separating multilinear branching programs and formulas. In 44th Annual ACM Symposium on Theory of Computing, STOC’12, 2012.
[10] Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ITCS.2018.1.
[11] Ankit Garg, Visu Makam, Rafael Oliveira, and Avi Wigderson. More barriers for rank methods, via a “numeric to symbolic” transfer. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 824–844. IEEE Computer Society, 2019.
[12] Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. On the necessary and sufficient conditions for separability of mixed quantum states. Phys. Lett. A, 223(1), 1996.
[13] Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff. Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society, 24(3):871–898, 2011.
[14] Pavel Hrubeš. A subquadratic upper bound on sum-of-squares composition formulas. In 39th Computational Complexity Conference (CCC 2024), volume 300 of LIPIcs, pages 12:1–12:11, 2024. doi:10.4230/LIPIcs.CCC.2024.12.
[15] Adolf Hurwitz. Über die komposition der quadratischen formen. Mathematische Annalen, 88(1):1–25, 1922.
[16] Deepanshu Kush and Shubhangi Saraf. Near-Optimal Set-Multilinear Formula Lower Bounds. In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:33. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CCC.2023.15.
[17] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In Shachar Lovett, editor, 37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CCC.2022.32.
[18] Nutan Limaye, Srikanth Srinivasan, and Sebastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 804–814. IEEE Computer Society, 2022.
[19] Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410–418, 1991.
[20] Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational complexity, 6:217–234, 1996. doi:10.1007/BF01294256.
[21] Asher Peres. Separability criterion for density matrices. Physical Review Letters, 77(8):1413, 1996.
[22] AR Rajwade. Squares, volume 171. Cambridge University Press, 1993.
[23] Ran Raz. Multilinear- $\mathrm{NC_{1}}$ $\neq$ multilinear- $\mathrm{NC_{2}}$ . In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 344–351. IEEE, 2004.
[24] Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. Journal of the ACM (JACM), 60(6):1–15, 2013. doi:10.1145/2535928.
[25] Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17:515–535, 2008. doi:10.1007/S00037-008-0254-0.
[26] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 95, 2015.
[27] Gadiel Seroussi and Abraham Lempel. Factorization of symmetric matrices and trace-orthogonal bases in finite fields. SIAM Journal on Computing, 9(4):758–767, 1980. doi:10.1137/0209059.
[28] Daniel B Shapiro. Compositions of quadratic forms, volume 33. Walter de Gruyter, 2011.
[29] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3–4):207–388, 2010. doi:10.1561/0400000039.
[30] Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan. Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 416–425, 2022. doi:10.1145/3519935.3520044.
[31] Leslie G Valiant. Completeness classes in algebra. In Proceedings of the 17th ACM Symposium on Theory of Computing, pages 249–261, 1979. doi:10.1145/800135.804419.

[bib.bib1] [1] John F Adams and Michael F Atiyah. K-theory and the hopf invariant. The Quarterly Journal of Mathematics, 17(1):31–38, 1966.

[bib.bib2] [2] Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.12.

[bib.bib3] [3] V Arvind and S Raja. Some lower bound results for set-multilinear arithmetic computations. Chicago Journal OF Theoretical Computer Science, 6:1–262, 2016.

[bib.bib4] [4] Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi. Algebraic complexity theory, volume 315. Springer Science & Business Media, 2013.

[bib.bib5] [5] Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference (CCC 2018), volume 102 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.CCC.2018.12.

[bib.bib6] [6] Prerona Chatterjee. Separating abps and some structured formulas in the non-commutative setting. In 36th Computational Complexity Conference, 2021.

[bib.bib7] [7] Daniel Dugger and Daniel C Isaksen. The hopf condition for bilinear forms over arbitrary fields. Annals of mathematics, pages 943–964, 2007.

[bib.bib8] [8] Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. Weighted sum-of-squares lower bounds for univariate polynomials imply $\mathrm{VP}\neq\mathrm{VNP}$ . computational complexity, 33(1):1–54, 2024.

[bib.bib9] [9] Zeev Dvir, G Malod, S Perifel, and A Yehudayoff. Separating multilinear branching programs and formulas. In 44th Annual ACM Symposium on Theory of Computing, STOC’12, 2012.

[bib.bib10] [10] Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ITCS.2018.1.

[bib.bib11] [11] Ankit Garg, Visu Makam, Rafael Oliveira, and Avi Wigderson. More barriers for rank methods, via a “numeric to symbolic” transfer. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 824–844. IEEE Computer Society, 2019.

[bib.bib12] [12] Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. On the necessary and sufficient conditions for separability of mixed quantum states. Phys. Lett. A, 223(1), 1996.

[bib.bib13] [13] Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff. Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society, 24(3):871–898, 2011.

[bib.bib14] [14] Pavel Hrubeš. A subquadratic upper bound on sum-of-squares composition formulas. In 39th Computational Complexity Conference (CCC 2024), volume 300 of LIPIcs, pages 12:1–12:11, 2024. doi:10.4230/LIPIcs.CCC.2024.12.

[bib.bib15] [15] Adolf Hurwitz. Über die komposition der quadratischen formen. Mathematische Annalen, 88(1):1–25, 1922.

[bib.bib16] [16] Deepanshu Kush and Shubhangi Saraf. Near-Optimal Set-Multilinear Formula Lower Bounds. In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:33. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CCC.2023.15.

[bib.bib17] [17] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In Shachar Lovett, editor, 37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CCC.2022.32.

[bib.bib18] [18] Nutan Limaye, Srikanth Srinivasan, and Sebastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 804–814. IEEE Computer Society, 2022.

[bib.bib19] [19] Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410–418, 1991.

[bib.bib20] [20] Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational complexity, 6:217–234, 1996. doi:10.1007/BF01294256.

[bib.bib21] [21] Asher Peres. Separability criterion for density matrices. Physical Review Letters, 77(8):1413, 1996.

[bib.bib22] [22] AR Rajwade. Squares, volume 171. Cambridge University Press, 1993.

[bib.bib23] [23] Ran Raz. Multilinear- $\mathrm{NC_{1}}$ $\neq$ multilinear- $\mathrm{NC_{2}}$ . In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 344–351. IEEE, 2004.

[bib.bib24] [24] Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. Journal of the ACM (JACM), 60(6):1–15, 2013. doi:10.1145/2535928.

[bib.bib25] [25] Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17:515–535, 2008. doi:10.1007/S00037-008-0254-0.

[bib.bib26] [26] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 95, 2015.

[bib.bib27] [27] Gadiel Seroussi and Abraham Lempel. Factorization of symmetric matrices and trace-orthogonal bases in finite fields. SIAM Journal on Computing, 9(4):758–767, 1980. doi:10.1137/0209059.

[bib.bib28] [28] Daniel B Shapiro. Compositions of quadratic forms, volume 33. Walter de Gruyter, 2011.

[bib.bib29] [29] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3–4):207–388, 2010. doi:10.1561/0400000039.

[bib.bib30] [30] Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan. Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 416–425, 2022. doi:10.1145/3519935.3520044.

[bib.bib31] [31] Leslie G Valiant. Completeness classes in algebra. In Proceedings of the 17th ACM Symposium on Theory of Computing, pages 249–261, 1979. doi:10.1145/800135.804419.

	$\displaystyle V_{1}(G)$	$\displaystyle\vcentcolon=\{v\in V(G):v\text{ has degree $1$ in }G\},$
	$\displaystyle V_{2}(G)$	$\displaystyle\vcentcolon=\{v\in V(G):v\text{ has degree $2$ in }G\}.$

	$\displaystyle D_{1}(G)$	$\displaystyle\vcentcolon=\{vw\in D(G):v\in V_{1}(G)\},$
	$\displaystyle D_{2}(G)$	$\displaystyle\vcentcolon=\{vw\in D(G):v\in V_{2}(G)\}.$

Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC1 ≠ VNP

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Biquadratic sum-of-squares and non-commutative circuits

Theorem 1.1 ([14]).

Theorem 1.2 ([13]).

1.2 Multiquadratic sum-of-squares and commutative set-multilinear formulas

Theorem 1.3 (informal).

1.3 Partial transpose rank of 𝒏𝒅×𝒏𝒅 matrices

Definition 1.4.

Theorem 1.5 (Main theorem).

Corollary 1.6.

1.4 Related work

1.5 Outline of the paper

2 Preliminaries

2.1 The underlying field

2.2 Matrices and tensors

Definition 2.1 (Tensors).

Definition 2.2 (Matrices).

Definition 2.3 (Matrix flattening of a tensor).

2.3 Set-multilinear formula size

Definition 2.4 (Set-multilinear formula size).

2.4 𝒏𝒅×𝒏𝒅 matrices and their shifted tensors

Definition 2.5 (The shifted tensor of an nd×nd matrix M).

Definition 2.6 (Iterated Matrix Multiplication).

3 Partial transpose rank

Definition 3.1 (Partial transpose).

Definition 3.2 (Fully symmetric matrices).

Example 3.3.

Definition 3.4 (Partial transpose rank).

Lemma 3.5.

Proof.

Example 3.6.

3.1 Properties of PT-rank

Lemma 3.7.

Lemma 3.8.

Corollary 3.9.

Lemma 3.10.

Proof.

3.2 PT-rank and SoS complexity

Definition 3.11 (Multiquadratic polynomial QM).

Lemma 3.12.

Proof.

▶ Remark 3.13.

Lemma 3.14.

Proof.

Proposition 3.15.

3.3 PT-rank of almost all matrices

Proposition 3.16.

Proposition 3.17.

4 Non-commutative set-multilinear formula lower bounds from PT-rank

Theorem 1.5 (restated).

Definition 4.1.

Theorem 4.2 (Non-commutative version of Theorem 1.5).

4.1 The complexity measure 𝝆 on order 𝟐⁢𝒅 tensors

Definition 4.3.

Lemma 4.4.

Proof.

Lemma 4.5.

Proof.

Lemma 4.6.

Proof.

Definition 4.7.

Lemma 4.8.

Proof.

Lemma 4.9.

Proof.

4.2 Non-commutative formula lower bounds from 𝝆

Definition 4.10 (The order d flattening A♭:[n2]d→𝔽 of an order 2⁢d tensor A:[n]2⁢d→𝔽).

Theorem 4.11.

Proof.

Proof of Theorem 4.2.

Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC¹ $\neq$ VNP

1.3 Partial transpose rank of $n^{d}\times n^{d}$ matrices

2.4 $n^{d}\times n^{d}$ matrices and their shifted tensors

Definition 2.5 (The shifted tensor of an $n^{d}\times n^{d}$ matrix $M$ ).

Definition 3.11 (Multiquadratic polynomial $Q_{M}$ ).

$\blacktriangleright$ Remark 3.13.

4.1 The complexity measure $\rho$ on order $2d$ tensors

4.2 Non-commutative formula lower bounds from $\rho$

Definition 4.10 (The order $d$ flattening $A^{\flat}:[n^{2}]^{d}\to\mathbb{F}$ of an order $2d$ tensor $A:[n]^{2d}\to\mathbb{F}$ ).

5.1 Extending $\rho$ to tensors over subgraphs of $\mathrm{Path}_{d}$

$\blacktriangleright$ Remark 5.1.

5.2 Set-multilinear formula lower bounds from $\rho$

6.1 Kronecker products of $n\times n$ matrices have low PT-rank

6.2 Matrices in $\mathsf{VBP_{ord}}$ have low PT-rank

Definition 6.5 ( $\mathsf{VBP_{ord}}$ ).