==== TABLE OF CONTENTS ====
Exponential-PSD-rank-of-positively-shifted-matching-matrices//fourier-smoothing.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//introduction.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//local-averaging.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//main.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//matching-cells.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//matching-smoothing.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//matching.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//parity.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//splitting.tex
Exponential-PSD-rank-of-positively-shifted-matching-matrices//refs.bib
===========================
==== BEGIN Exponential-PSD-rank-of-positively-shifted-matching-matrices//fourier-smoothing.tex ====
\section{Fourier concentration of squares under product averages}
\label{sec:fourier}
We next show how averaging a positive semidefinite matrix-valued
function can produce a representation by squares whose Fourier
coefficients concentrate around a separate center for each square.
The assumption is a scalar variance bound for each coordinate average.
This bound extends to matrix-valued functions with the same constant.
We will use it to control a fourth-order Gram potential and then
convert that bound into an estimate on the Fourier coefficients.
Fix an integer $a\ge1$, put $L=2^a$, and identify each of
$Y_1,\ldots,Y_t$ with the additive group $(\mathbb F_2)^a$.
We use a second copy $\Lambda=(\mathbb F_2)^a$ to index its characters.
For $p=(p_1,\ldots,p_t)\in\Lambda^t$ and
$y=(y_1,\ldots,y_t)\in\prod_iY_i$, define
\[
\chi_p(y)=(-1)^{\sum_{i=1}^t p_i\cdot y_i},
\]
where the inner products and the exponent are computed modulo two.
These real characters form an orthonormal basis for uniform probability
on $\prod_iY_i$. For a real matrix-valued function $H$, write
\[
\widehat H_p=\E_y[\chi_p(y)H(y)],
\qquad H(y)=\sum_{p\in\Lambda^t}\widehat H_p\chi_p(y).
\]
The block degree of $\chi_p$ is $|\{i:p_i\ne0\}|$.
A function has block degree at most $D$ if its Fourier coefficients
vanish at every character of block degree greater than $D$; this
convention includes the zero function.
We also write
$\operatorname{dist}(p,q)=|\{i:p_i\ne q_i\}|$.
Multiplication by $\chi_q$ translates frequency $p$ to $p+q$, whose
block degree is $\operatorname{dist}(p,q)$. In particular, a real
function supported within distance $D$ of $q$ becomes a function of
block degree at most $D$ after this multiplication, with its square
unchanged. This translation of Fourier support while preserving
squares also appears in the construction of sparse sums of squares
on finite abelian groups by Fawzi, Saunderson, and
Parrilo~\cite{fsp-sparse}.
\begin{theorem}[Fourier smoothing of matrix squares]
\label{thm:fourier-smoothing}
Let $t,r\ge1$ be integers. For each $1\le i\le t$, let $X_i$ and
$\mathcal M_i$ be nonempty finite sets with uniform probability, and
let $Y_i$ be a specified copy of $(\mathbb F_2)^a$, where $a\ge1$ and
$L=2^a$. For $m\in\mathcal M_i$ and $y\in Y_i$, let
$\pi_{i,y}^m$ be a probability distribution on $X_i$.
Suppose that, for some $\theta\ge0$, these distributions satisfy
\begin{equation}\label{eq:channel-marginal}
\E_{m\in\mathcal M_i}\pi_{i,y}^m(x)=\frac1{|X_i|}
\qquad(x\in X_i, y\in Y_i)
\end{equation}
and, for every real function $g:X_i\to\R$ and every $y\in Y_i$,
\begin{equation}\label{eq:channel-variance}
\E_{m\in\mathcal M_i}
\left(\sum_{x\in X_i}\pi_{i,y}^m(x)g(x)-\E_{x\in X_i}g(x)\right)^2
\le\theta\E_{x\in X_i}g(x)^2.
\end{equation}
Let $F:\prod_iX_i\to\mathbb S_+^r$ satisfy $\tr F(x)\le B$ for all
$x$, where $B>0$ and $\mathbb S_+^r$ is the cone of real symmetric
positive semidefinite $r$-by-$r$ matrices. Fix $\lambda>1$ such that
\begin{equation}\label{eq:smoothing-parameter}
L\lambda^2C_L\theta\le1,
\end{equation}
where $C_L=2^{L-1}$ is the constant of Lemma~\ref{lem:splitting}.
For $m=(m_1,\ldots,m_t)\in\prod_i\mathcal M_i$, define
\begin{equation}\label{eq:product-average}
\overline F_m(y)
=\sum_{x\in\prod_iX_i}
\left(\prod_{i=1}^t\pi_{i,y_i}^{m_i}(x_i)\right)F(x).
\end{equation}
There is a finite integer $R$ and a family of functions
$H_q^m:\prod_iY_i\to\R^{R\times r}$, indexed by
$m\in\prod_i\mathcal M_i$ and $q\in\Lambda^t$, such that
\begin{equation}\label{eq:smoothing-squares}
\overline F_m(y)=\sum_{q\in\Lambda^t}H_q^m(y)^{\mathsf T}H_q^m(y).
\end{equation}
For each $m,q$, form the horizontal concatenation and its Gram matrix
\begin{equation}\label{eq:smoothing-gram}
U_q^m=
\left[\lambda^{\operatorname{dist}(q,p)/2}
\widehat H_{q,p}^m\right]_{p\in\Lambda^t},
\qquad C_q^m=U_q^m(U_q^m)^{\mathsf T},
\end{equation}
where $\widehat H_{q,p}^m$ is the Fourier coefficient of $H_q^m$ at $p$.
The family can be chosen so that, for independent uniform $m_i$,
\begin{equation}\label{eq:smoothing-potential}
\E_m\sum_{q\in\Lambda^t}\normF{C_q^m}^2\le2^tB^2.
\end{equation}
Consequently, at least one $m$ satisfies
\begin{equation}\label{eq:smoothing-coefficients}
\sum_{q,p\in\Lambda^t}
\lambda^{\operatorname{dist}(q,p)}\normF{\widehat H_{q,p}^m}^2
\le L^t\sqrt r\,B\,2^{t/2}.
\end{equation}
\end{theorem}
The weights in \eqref{eq:smoothing-coefficients} penalize frequencies
far from the center $q$ of their branch. To explain the potential,
fix $m,q$, suppress these indices, and put
$w_p=\lambda^{\operatorname{dist}(q,p)}$. Then
\[
\tr C=\sum_p w_p\normF{\widehat H_p}^2,
\qquad
\normF{C}^2=\sum_{p,p'}w_pw_{p'}
\normF{\widehat H_p^{\mathsf T}\widehat H_{p'}}^2.
\]
Thus the trace measures the weighted Fourier mass we want to bound,
whereas the squared Frobenius norm measures squared overlaps of
coefficient matrices. The latter quantity matches the squared norm
in the variance assumption.
We prove the theorem by processing the coordinates in order. A direct
sum of squares realizes each new average, and
Lemma~\ref{lem:splitting} separates its new frequencies into branches.
We bound the increase of the Gram potential at each step, then use
the ranks of the final Gram matrices to bound their traces.
\begin{proof}
For a matrix-valued function $Z$ on $X_i$, use the notation
\[
T_{i,y}Z(m)=\sum_{x\in X_i}\pi_{i,y}^m(x)Z(x).
\]
Applying \eqref{eq:channel-variance} to each entry and summing gives
\begin{equation}\label{eq:matrix-channel-variance}
\E_m\normF{T_{i,y}Z(m)-\E_xZ(x)}^2
\le\theta\E_x\normF{Z(x)}^2.
\end{equation}
This inequality holds in every finite matrix dimension, with the same
$\theta$.
\paragraph{Partial averages and the potential.}
Use the abbreviations $m_{\le i}=(m_1,\ldots,m_i)$ and
$x_{>i}=(x_{i+1},\ldots,x_t)$, and likewise for $y$.
At stage $i$ we construct functions
\[
H_q^{(i)}(y_{\le i};x_{>i}),\qquad q\in\Lambda^i,
\]
depending also on $m_{\le i}$, such that
\begin{equation}\label{eq:partial-squares}
\sum_{q\in\Lambda^i}(H_q^{(i)})^{\mathsf T}H_q^{(i)}
=\sum_{x_{\le i}}
\left(\prod_{j=1}^i\pi_{j,y_j}^{m_j}(x_j)\right)F(x).
\end{equation}
All matrices at stage $i$ have a common row dimension $R_i$ and $r$
columns. Their Fourier coefficients refer only to the processed
variables $y_{\le i}$. Define
\begin{equation}\label{eq:partial-gram}
U_q^{(i)}=
\left[\lambda^{\operatorname{dist}(q,p)/2}
\widehat H_{q,p}^{(i)}\right]_{p\in\Lambda^i},
\qquad C_q^{(i)}=U_q^{(i)}(U_q^{(i)})^{\mathsf T}.
\end{equation}
Thus $U_q^{(i)}$ has $rL^i$ columns and is a function of $x_{>i}$.
The potential is
\[
\Phi_i=\E_{m_{\le i},x_{>i}}
\sum_{q\in\Lambda^i}\normF{C_q^{(i)}}^2,
\]
where all listed variables are independent and uniform.
At stage zero take $R_0=r$ and $H_{\varnothing}^{(0)}=F^{1/2}$.
Then $C_{\varnothing}^{(0)}=F$, so
$\Phi_0\le\E_x(\tr F(x))^2\le B^2$.
We will prove $\Phi_{i+1}\le2\Phi_i$ while preserving
\eqref{eq:partial-squares}.
\paragraph{Realizing one more average.}
Fix $m_{\le i}$, a branch $q\in\Lambda^i$, and $x_{>i+1}$.
For the new coordinate abbreviate $X_{i+1},Y_{i+1},m_{i+1}$ by
$X,Y,m$, and write its input as $x$ and its character variable as
$y$. The old concatenation is now a matrix function
$U(x)=U_q^{(i)}(x;x_{>i+1})$.
Put
\[
Z(x)=U(x)^{\mathsf T}U(x).
\]
It has size $rL^i$ by $rL^i$, and
\begin{equation}\label{eq:two-gram-norms}
\normF{Z(x)}^2=\normF{C_q^{(i)}(x)}^2.
\end{equation}
The fixed data determine the entire function $x\mapsto U(x)$ before
the new averaging parameter $m$ is chosen.
For a fixed $m$, form a matrix-valued function $H'$ with
$R_{i+1}=L|X|R_i$ rows. We give different values of $y$ disjoint row
blocks by indexing those blocks with $(y',x)\in Y\times X$.
This extra label will eliminate products between different $y$-values
from the Fourier overlap calculation below.
The block at $(y',x)$ is
\begin{equation}\label{eq:tagged-stack}
H'(y_{\le i},y)_{(y',x)}
=\mathbf1_{\{y'=y\}}\sqrt{\pi_y^m(x)}\,
H_q^{(i)}(y_{\le i};x,x_{>i+1}).
\end{equation}
Consequently,
\[
H'^{\mathsf T}H'
=\sum_{x\in X}\pi_y^m(x)
H_q^{(i)}(y_{\le i};x,x_{>i+1})^{\mathsf T}
H_q^{(i)}(y_{\le i};x,x_{>i+1}).
\]
This stack performs the new average. We next split its space of row
coordinates in a way that controls its Fourier coefficients.
For $z\in\Lambda$, concatenate the Fourier coefficients of $H'$ at
$(p,z)$, using only the old weights:
\[
V_z=\left[\lambda^{\operatorname{dist}(q,p)/2}
\widehat H'_{p,z}\right]_{p\in\Lambda^i},
\qquad A_z=V_zV_z^{\mathsf T}.
\]
The $(y',x)$ row block of $V_z$ is
$L^{-1}\chi_z(y')\sqrt{\pi_{y'}^m(x)}U(x)$.
Multiplying the stacked matrices therefore gives the identity
\begin{equation}\label{eq:new-frequency-overlap}
V_z^{\mathsf T}V_{z'}
=\frac1{L^2}\sum_{y\in Y}
\chi_z(y)\chi_{z'}(y)T_{i+1,y}Z(m).
\end{equation}
In particular,
$\tr(A_zA_{z'})=\normF{V_z^{\mathsf T}V_{z'}}^2$.
\paragraph{The overlap estimate.}
For $z=z'$, Jensen's inequality and
\eqref{eq:channel-marginal} applied to
\eqref{eq:new-frequency-overlap} give
\[
\E_m\tr(A_z^2)
\le\frac1{L^2}\E_x\normF{Z(x)}^2.
\]
For $z\ne z'$, let $\mu=\E_xZ(x)$.
Character orthogonality permits subtracting $\mu$ from every summand
in \eqref{eq:new-frequency-overlap}. Jensen's inequality and
\eqref{eq:matrix-channel-variance} now give
\[
\begin{split}
\E_m\tr(A_zA_{z'})
&\le\frac1{L^2}\E_y\E_m
\normF{T_{i+1,y}Z(m)-\mu}^2\\
&\le\frac\theta{L^2}\E_x\normF{Z(x)}^2.
\end{split}
\]
Together with \eqref{eq:two-gram-norms}, these estimates say that
\begin{equation}\label{eq:overlap-summary}
\E_m\tr(A_zA_{z'})
\le \frac1{L^2}\E_x\normF{C_q^{(i)}(x)}^2
\begin{cases}
1,&z=z',\\
\theta,&z\ne z'.
\end{cases}
\end{equation}
The new frequency Gram matrices thus have small total overlap in
expectation. We can now use Lemma~\ref{lem:splitting} to assign them
to separate branches, charging the misplaced compressions to this
overlap.
\paragraph{Splitting the stack and updating the weights.}
For each $m$, apply Lemma~\ref{lem:splitting} to $(A_z)_{z\in\Lambda}$,
obtaining projections $(P_s)_{s\in\Lambda}$. Define
\[
H_{(q,s)}^{(i+1)}=P_sH'.
\]
Since $\sum_sP_s=I$ and $P_s^2=P_s=P_s^{\mathsf T}$, we have
$\sum_s(H_{(q,s)}^{(i+1)})^{\mathsf T}H_{(q,s)}^{(i+1)}
=H'^{\mathsf T}H'$.
Summing over $q$ proves \eqref{eq:partial-squares} at the new stage.
These projections may depend on $m_{\le i+1}$ and $x_{>i+1}$, but
they do not depend on any processed variable $y_{\le i+1}$.
Hence they commute with taking the Fourier coefficients in these
variables. We retain all $R_{i+1}$ rows of every projected matrix,
even when the ranks of the projections vary with the
remaining inputs. This gives a common coordinate system for every
branch at every value of those inputs. Since all sets are finite,
the choices of projections for all histories and remaining inputs can
be made simultaneously, using no future averaging parameters.
The new distance satisfies
$\operatorname{dist}((q,s),(p,z))
=\operatorname{dist}(q,p)+\mathbf1_{\{s\ne z\}}$.
The Gram matrix with the new weights is therefore
\[
C_{(q,s)}^{(i+1)}
=\sum_{z\in\Lambda}\lambda^{\mathbf1_{\{s\ne z\}}}P_sA_zP_s.
\]
Cauchy--Schwarz for this sum of $L$ matrices, followed by
Lemma~\ref{lem:splitting}, gives
\begin{equation}\label{eq:one-step-potential}
\begin{split}
\sum_s\normF{C_{(q,s)}^{(i+1)}}^2
&\le L\left(
\sum_z\normF{A_z}^2
+\lambda^2C_L\sum_{z\ne z'}\tr(A_zA_{z'})
\right).
\end{split}
\end{equation}
For the terms with $s=z$ we used
$\normF{P_zA_zP_z}\le\normF{A_z}$.
There are $L$ diagonal terms and $L(L-1)$ ordered off-diagonal terms
in \eqref{eq:overlap-summary}. Taking expectation in
\eqref{eq:one-step-potential} yields
\[
\E_m\sum_s\normF{C_{(q,s)}^{(i+1)}}^2
\le\bigl(1+(L-1)\lambda^2C_L\theta\bigr)
\E_x\normF{C_q^{(i)}(x)}^2
\le2\E_x\normF{C_q^{(i)}(x)}^2.
\]
This estimate was proved for every fixing of $m_{\le i}$ and
$x_{>i+1}$. Under the product probability law, the new $m$ is
independent of these variables. Although earlier projections can
make $Z(x)$ an arbitrary function of the current input $x$, it is
independent of this new $m$, as required when applying
\eqref{eq:matrix-channel-variance}. Thus we may sum over $q$ and
average over the fixed data to obtain $\Phi_{i+1}\le2\Phi_i$.
At $i=t$, this proves \eqref{eq:smoothing-squares} and
\eqref{eq:smoothing-potential}, with $R=R_t$.
\paragraph{From the Gram potential to Fourier mass.}
Choose $m$ with
$\sum_q\normF{C_q^m}^2\le2^tB^2$.
Each $U_q^m$ has $rL^t$ columns, so
$\rank(C_q^m)\le rL^t$, regardless of its row dimension.
For a positive semidefinite matrix $C$,
$\tr C\le\sqrt{\rank C}\,\normF{C}$.
Applying this inequality and then Cauchy--Schwarz over the $L^t$
branches gives
\[
\begin{split}
\sum_{q,p}\lambda^{\operatorname{dist}(q,p)}
\normF{\widehat H_{q,p}^m}^2
&=\sum_q\tr C_q^m\\
&\le\sqrt{rL^t}\sum_q\normF{C_q^m}\\
&\le\sqrt{rL^t}\sqrt{L^t}
\left(\sum_q\normF{C_q^m}^2\right)^{1/2}\\
&\le L^t\sqrt r\,B\,2^{t/2}.
\end{split}
\]
This is \eqref{eq:smoothing-coefficients}.
\end{proof}
==== END Exponential-PSD-rank-of-positively-shifted-matching-matrices//fourier-smoothing.tex ====
==== BEGIN Exponential-PSD-rank-of-positively-shifted-matching-matrices//introduction.tex ====
\section{Introduction}
\label{sec:introduction}
Semidefinite lifts describe a convex set as the image of an affine
section of a positive semidefinite cone. They can be substantially
smaller than linear descriptions, so lower bounds for linear extended
formulations do not automatically exclude small semidefinite lifts.
We prove an exponential lower bound for perfect matching by studying
an exact factorization problem that also allows a fixed positive
shift of every odd-cut slack.
For even $n\ge4$, let $E_n$ be the edges of the complete graph $K_n$
on $[n]=\{1,\ldots,n\}$, let $\mathcal M_n$ be its perfect matchings,
and let $\mathcal O_n$ be the odd-cardinality subsets of $[n]$.
For $U\subseteq[n]$, write $\delta(U)$ for the edges with exactly
one endpoint in $U$. For $0\le\rho\le1$, define the matrix
\begin{equation}\label{eq:main-matrix}
A_n(\rho)_{U,M}=|M\cap\delta(U)|-1+\rho,
\qquad U\in\mathcal O_n,\quad M\in\mathcal M_n.
\end{equation}
Every perfect matching crosses an odd set an odd positive number
of times, so this matrix is nonnegative. Its rows consist solely
of odd cuts.
The \emph{real positive semidefinite rank} of a finite nonnegative
matrix $A$, denoted $\rankpsd A$, is the least integer $r\ge1$ for
which there are real symmetric positive semidefinite matrices
$F_U,G_M\in\R^{r\times r}$ satisfying
\[
A_{U,M}=\tr(F_UG_M)
\qquad\text{for every row and column}.
\]
Such matrices are called PSD factors. The entries must be reproduced
exactly, and no symmetry, equivariance, sparsity, or precision
restriction is imposed on the factors.
\begin{theorem}\label{thm:main}
There is a constant $c>0$ such that, for every fixed $0<\rho<1$,
there is $n_0=n_0(\rho)$ for which
\[
\rankpsd A_n(\rho)\ge2^{cn}
\]
for every even $n\ge n_0$.
\end{theorem}
The endpoint $\rho=1$ has a factorization of size $\binom n2$:
use diagonal matrices indexed by edges, with diagonal entries
$\mathbf1_{\{e\in\delta(U)\}}$ for a row and
$\mathbf1_{\{e\in M\}}$ for a column. Thus the endpoint $\rho=1$
cannot be included in the exponential lower bound.
The exponential rate in Theorem~\ref{thm:main} is independent of
$\rho$, although the threshold is allowed to deteriorate as
$\rho$ tends to one.
\subsection{Exact semidefinite lifts}
Let
\[
P_n=\operatorname{conv}\{\mathbf1_M:M\in\mathcal M_n\}
\subseteq\R^{E_n}
\]
be the perfect matching polytope. A \emph{semidefinite lift of
size $r$} represents $P_n$ as an affine image of
$L\cap\mathbb S_+^r$, where $L$ is an affine subspace of the real
symmetric matrices and $\mathbb S_+^r$ is their PSD cone. Also let
$T_n(\rho)$ denote the matrix obtained by adjoining to $A_n(\rho)$
the edge rows
\[
T_n(\rho)_{e,M}=\mathbf1_{\{e\in M\}},\qquad e\in E_n.
\]
Adding rows cannot decrease PSD rank, so
Theorem~\ref{thm:main} applies to $T_n(\rho)$ as well.
\begin{corollary}[Unshifted rank and exact lifts]
\label{cor:exact-lift}
There are constants $c_0>0$ and $n_1$ such that, for every even
$n\ge n_1$, both $A_n(0)$ and $T_n(0)$ have real PSD rank at least
$2^{c_0n}$, and every exact semidefinite lift of $P_n$ has size at
least $2^{c_0n}$.
\end{corollary}
\begin{proof}
Appending scalar blocks $\rho$ to the row factors and $1$ to the
column factors of $A_n(0)$ gives a factorization of $A_n(\rho)$.
Consequently
\[
\rankpsd A_n(\rho)\le\rankpsd A_n(0)+1.
\]
Fix $\rho=1/2$ and apply Theorem~\ref{thm:main}. For all sufficiently
large even $n$,
\[
\rankpsd T_n(0)\ge\rankpsd A_n(0)\ge2^{cn}-1\ge2^{cn/2}.
\]
Edmonds's description of $P_n$ uses nonnegativity and odd-cut
inequalities, within the affine space of degree equations
$\sum_{e\ni v}x_e=1$ \cite{edmonds}. Thus $T_n(0)$ is a slack
matrix of this description. Every row inequality is tight at some
perfect matching. Any redundant row is therefore a nonnegative
combination of facet slack rows, so including it does not change
PSD rank. The cone-factorization theorem identifies this rank with
the minimum size of a semidefinite lift
\cite[Theorem~2.4 and Corollary~2.6]{gpt}.
For completeness, an arbitrary lift can be restricted to the
smallest face of the PSD cone containing its feasible section.
This face is a PSD cone of size at most $r$, and the section meets
its relative interior, supplying the properness needed for
factorization. An affine image can be made linear on the affine
slice without increasing size: the slice cannot contain zero,
since its intersection with the cone would then have a bounded
affine image only if that image were a point. A linear functional
equal to one on the slice therefore absorbs the translation.
Taking $c_0=c/2$ proves the corollary.
\end{proof}
\subsection{History and the role of the shift}
Edmonds's inequality description \cite{edmonds} is the starting
point for formulation complexity of matching. Yannakakis
developed the nonnegative-factorization framework and proved an
exponential lower bound for symmetric linear formulations
\cite{yannakakis}. Rothvo\ss\ proved the unrestricted exponential
linear extension-complexity bound \cite{rothvoss}. The
cone-factorization framework of Gouveia, Parrilo, and Thomas
\cite{gpt} gives the corresponding connection between PSD rank
and semidefinite lifts.
For the particular shifted matrix, Braun and Pokutta proved
exponential nonnegative rank for the entries
$(|M\cap\delta(U)|-1+\rho)/2$, for each fixed $0<\rho<1$
\cite[Section~2.2.3 and Theorem~3.1]{braun-pokutta}.
Positive scalar multiplication does not change rank, so their
matrix is the same factorization problem with nonnegative scalar
factors in place of arbitrary PSD factors. Braun and collaborators
proved exponential lower bounds for coordinate-symmetric
semidefinite formulations of matching
\cite[Definition~2.2 and Theorem~3.10]{matching-symmetric}.
Here no group action on the factor coordinates is assumed.
Permutation symmetry will be used only to analyze averaging
operators.
Lee, Raghavendra, and Steurer developed a general approach to
unrestricted SDP lower bounds through sums of squares and
low-degree separating functionals \cite{lrs}. Our proof follows
that approach, with a transfer argument tailored to matching.
It treats the exact positive shift in Equation~\eqref{eq:main-matrix}.
Exactness matters: Kaniewski, Lee, and de Wolf construct matrices
of subexponential PSD rank that approximate the unshifted matching
slack with entrywise error at most $2^{-\sqrt{n/2}}$
\cite[Section~7.3 and Theorem~19]{kaniewski-lee-dewolf}.
\subsection{Proof strategy and reusable ingredients}
The obstruction is an inconsistent parity system on an expanding
graph $H$ with $t$ vertices. Each vertex carries $d$ incidence
bits of prescribed parity, and the sum of the prescribed parities
is odd. Some edge must therefore have unequal bits at its two
ends. Subtracting $1-\rho$ from the number of disagreements gives
a positive function $f$. Products of signs of the free incidence
bits give Fourier characters, each involving certain vertex blocks.
Section~\ref{sec:parity} constructs a linear functional that is
nonnegative on squares of functions whose Fourier characters each
involve at most a small fixed fraction of the blocks, yet takes
value $-(1-\rho)$ on $f$. The signed
moment construction is related to Grigoriev's low-degree
functionals for Tseitin contradictions \cite{grigoriev}.
To realize this system in matching, replace every vertex of $H$
by a cell of $k$ vertices. The cell size $k$ is a sufficiently
large constant, fixed before $n$ tends to infinity. Each auxiliary
incidence uses one terminal; the remaining vertices are paired
inside the cell. A local cut restriction fixes the terminal bits
and gives equal bits to every internal pair. The only crossing
edges are then the auxiliary disagreements. Section~\ref{sec:matching}
performs this construction and completes the proof.
The main analytic task is to show that a small PSD factorization
would make $f$ close enough to a low-degree sum of squares.
Let $\overline F(y)$ be the row factor averaged over cuts with
incidence assignment $y$. Pairing this average with the factor of
the corresponding matching gives $f(y)$. Taking square roots of
the row factors gives matrix functions with no initial degree bound;
averaging their squares cannot be replaced by squaring their
averages. We instead construct an exact representation
\[
\overline F(y)=\sum_q H_q(y)^{\mathsf T}H_q(y)
\]
by real rectangular matrix functions. The index $q$ labels both
a summand, called a branch, and a Fourier character $\chi_q$.
The goal is to concentrate the coefficients of $H_q$ on characters
that differ from $\chi_q$ in only a few vertex blocks.
Section~\ref{sec:local} proves the local averaging estimate used
at each step. Its scalar variance bound tends to zero as $k$
grows and extends to matrices without a dimension factor.
The proof combines a trace estimate with a lower bound on the
dimensions of invariant eigenspaces, a spectral mechanism also
used in quasirandom-group arguments \cite{gowers}.
Section~\ref{sec:splitting} proves a dimension-free orthogonal
splitting inequality for a finite family of PSD matrices.
These ingredients yield the abstract product averaging theorem
in Section~\ref{sec:fourier}. It bounds the Fourier mass of each
branch with weights growing exponentially in the number of blocks
where a character differs from its center $q$. The controlled quantity is
the squared Frobenius norm of a weighted Gram matrix, hence a
fourth-order expression in the Fourier coefficients. Its use
allows repeated averaging even though representing an average by
a direct sum introduces additional rows into the matrices $H_q$.
After truncation near the center $q$, multiplication by $\chi_q$
moves each retained character to low block degree while
preserving squares, as in finite-group Fourier sums of squares
\cite{fsp-sparse}. This is the step that lets the separating
functional contradict the factorization.
The local averaging lemma, the orthogonal splitting inequality,
and the product theorem are stated separately from the global
matching factorization problem.
Appendix~\ref{sec:matching-smoothing} gives a further independent
smoothing theorem for averages over matchings with any prescribed
edge-count table across a fixed number of cells. Its estimate is
uniform even for rare tables and unbalanced cell sizes, and its
three-cell specialization includes a single polynomial in the
three intercell counts.
\paragraph{Notation.}
Finite sets carry uniform probability unless another law is specified;
averages are denoted by $\E$. For real matrices we use the Frobenius
norm $\normF B=(\tr(B^{\mathsf T}B))^{1/2}$ and operator norm
$\normop B$. The relation $A\preceq B$ means that $B-A$ is PSD.
All logarithms are natural unless their base is displayed.
==== END Exponential-PSD-rank-of-positively-shifted-matching-matrices//introduction.tex ====
==== BEGIN Exponential-PSD-rank-of-positively-shifted-matching-matrices//local-averaging.tex ====
\section{Averaging within a cell}
\label{sec:local}
We next construct restrictions of a cut to one cell. The restrictions
prescribe its values at a fixed number of terminals and make its values
equal across every internal matching edge. Averaging a function over
these restrictions has a uniform marginal and, as the cell grows, small
variance over the choice of terminals and matching. The variance bound
will hold for matrix-valued functions with a constant independent of their
dimensions.
Fix an even integer $d\ge 2$, and let $k$ be a sufficiently large even
integer. A cell has vertex set $[k]$. For $b\in\{0,1\}$, let $w$ be the
unique integer in $\{k/2,k/2+1\}$ congruent to $b$ modulo two, and set
\[
X=\binom{[k]}{w},
\qquad
Y_b=\left\{y\in\{0,1\}^d:
\sum_{\ell=1}^d y_\ell\equiv b\pmod 2\right\},
\qquad L=|Y_b|=2^{d-1}.
\]
We identify a subset $a\in X$ with its indicator function when referring
to its bits.
Local column data $m$ consist of an ordered list of distinct terminals
$(v_1,\ldots,v_d)$ and a perfect matching of the remaining $k-d$ vertices.
Let $\mathcal M$ be the finite set of these data, with its uniform law.
For $y\in Y_b$, define $\pi_y^m$ to be the uniform probability measure on
the subsets $a\in X$ satisfying
\begin{equation}
\mathbf 1_a(v_\ell)=y_\ell\quad(1\le\ell\le d),
\qquad
\mathbf 1_a(u)=\mathbf 1_a(v)
\quad\text{for every internal pair }\{u,v\}\text{ of }m.
\label{local:restrictions}
\end{equation}
To see that this measure is defined, write
\begin{equation}
s=|y|,\qquad h=\frac{k-d}{2},\qquad
g=\frac{w-s}{2}.
\label{local:parameters}
\end{equation}
The parity condition makes $g$ integral. A subset satisfying
\eqref{local:restrictions} consists of the prescribed terminals and a
choice of $g$ whole pairs among the $h$ internal pairs. If
$\delta=w-k/2\in\{0,1\}$, then
\begin{equation}
g=\frac h2+\frac d4+\frac\delta2-\frac s2,
\qquad
\left|g-\frac h2\right|\le\frac d4+\frac12.
\label{local:central}
\end{equation}
Thus $0\le g\le h$ for all sufficiently large $k$, uniformly in $b$ and
$y$. The support of $\pi_y^m$ has cardinality $\binom hg$.
For a real function $B$ on $X$, define
\[
(T_yB)(m)=\sum_{a\in X}\pi_y^m(a)B(a).
\]
The same definition applies entrywise to a real matrix-valued function.
Expectations over $a$ and $m$ below use the uniform laws on $X$ and
$\mathcal M$, respectively.
\begin{lemma}[Local averaging]
\label{lem:local-averaging}
For each fixed even $d\ge2$, there are $k_0(d)$ and numbers
$\theta_d(k)\ge0$, defined for even $k\ge k_0(d)$, with
$\theta_d(k)\to0$ as $k\to\infty$, such that the following holds for the
construction above, for both $b\in\{0,1\}$ and every $y\in Y_b$.
First,
\begin{equation}
\E_m\pi_y^m(a)=\frac1{|X|}\qquad(a\in X).
\label{local:marginal}
\end{equation}
Second, every real function $B:X\to\R$ satisfies
\begin{equation}
\E_m\left|(T_yB)(m)-\E_aB(a)\right|^2
\le\theta_d(k)\,
\E_a\left|B(a)-\E_aB(a)\right|^2.
\label{local:scalar-variance}
\end{equation}
For every pair of positive integers $p,q$, the same constant gives, for
every $B:X\to\R^{p\times q}$,
\begin{equation}
\E_m\normF{(T_yB)(m)-\E_aB(a)}^2
\le\theta_d(k)\,
\E_a\normF{B(a)-\E_aB(a)}^2
\le\theta_d(k)\,\E_a\normF{B(a)}^2.
\label{local:matrix-variance}
\end{equation}
One may take $\theta_d(k)=O_d(k^{-1/4}\sqrt{\log(k+2)})$.
\end{lemma}
\begin{proof}
The uniform law of $m$ and the restrictions
\eqref{local:restrictions} are equivariant under permutations of the
$k$ vertices. Since the symmetric group is transitive on $X$, the
marginal law of $a$, obtained by first sampling $m$ and then
$a\sim\pi_y^m$, is uniform. This proves \eqref{local:marginal}.
Fix $b$ and $y$, and write $T=T_y$. Equip the function spaces on $X$
and $\mathcal M$ with the inner products for uniform probability, and
put $K=T^*T$. This is a positive semidefinite self-adjoint operator.
The marginal identity gives $K1=1$. We will show that
$\tr(K^2)=o(k)$, while every nonconstant eigenspace has dimension at
least $k/2$. Together these estimates force the largest eigenvalue
on the orthogonal complement of the constants to tend to zero.
\emph{The two-sample kernel.}
Sample $m$ uniformly, and then sample $a,a'$ independently from
$\pi_y^m$ conditional on $m$. Let $J(a,a')$ be their joint
probability, and let $N=|X|$. The density of this joint law relative
to two independent uniform elements of $X$ is
$D(a,a')=N^2J(a,a')$. Indeed, for scalar functions $B_1,B_2$,
\[
\langle B_1,KB_2\rangle
=\sum_{a,a'\in X}J(a,a')B_1(a)B_2(a').
\]
Consequently the ordinary matrix entries of $K$ are $D(a,a')/N$, and
symmetry gives
\begin{equation}
\tr(K^2)=\frac1{N^2}\sum_{a,a'\in X}D(a,a')^2.
\label{local:density-trace}
\end{equation}
The joint law is permutation-invariant, so $D(a,a')$ depends only on
$|a\cap a'|$. Conditional on $m$, the two subsets choose independent
$g$-subsets of the $h$ internal pairs. If the second choice replaces
exactly $j$ pairs of the first, their intersection has size
$s+2(g-j)=w-2j$. The probability of this event is
\[
P_j=\frac{\binom gj\binom{h-g}j}{\binom hg},
\qquad 0\le j\le g_*:=\min(g,h-g).
\]
For two independent uniform elements of $X$, the probability of the
same intersection size is
\[
Q_j=\frac{\binom w{2j}\binom{k-w}{2j}}{\binom kw}.
\]
Both laws are uniform within each intersection class. The density
there is therefore $P_j/Q_j$, and it vanishes on the remaining
classes. The identities
$w=2g+s$ and $k-w=2(h-g)+(d-s)$ ensure that every displayed $Q_j$
is positive. Equation~\eqref{local:density-trace} becomes
\begin{equation}
\tr(K^2)
=\sum_{j=0}^{g_*}\frac{P_j^2}{Q_j}
=\frac{\binom kw}{\binom hg^2}
\sum_{j=0}^{g_*}
\frac{\binom gj^2\binom{h-g}j^2}
{\binom w{2j}\binom{k-w}{2j}}.
\label{local:trace-formula}
\end{equation}
\emph{A trace estimate.}
Since $k=2h+d$, $w=k/2+O(1)$, and
$g=h/2+O_d(1)$, the central binomial estimates give
\begin{equation}
\frac{\binom kw}{\binom hg^2}=O_d(\sqrt h),
\label{local:central-ratio}
\end{equation}
uniformly in $b$ and $y$. Moreover,
$\binom w{2j}\ge\binom{2g}{2j}$ and
$\binom{k-w}{2j}\ge\binom{2(h-g)}{2j}$.
For integers $0\le j\le u$, the identity
\[
\frac{\binom uj^2}{\binom{2u}{2j}}
=\frac{\binom{2j}j\binom{2(u-j)}{u-j}}{\binom{2u}u}
\]
and the bounds $\binom{2v}v\asymp4^v/\sqrt{v+1}$ imply
\begin{equation}
\frac{\binom uj^2}{\binom{2u}{2j}}
\le C\sqrt{\frac{u+1}{(j+1)(u-j+1)}}
\label{local:binomial-ratio}
\end{equation}
with an absolute constant $C$, including at the endpoints $j=0,u$.
Applying this bound with $u=g$ and $u=h-g$ shows that the sum in
\eqref{local:trace-formula} is at most
\[
C^2\sum_{j=0}^{g_*}
\frac{h+1}{(j+1)(g_*-j+1)}
=\frac{2C^2(h+1)}{g_*+2}\sum_{j=1}^{g_*+1}\frac1j.
\]
By \eqref{local:central}, $g_*=h/2+O_d(1)$, so this is
$O_d(\log(h+2))$. Thus
\begin{equation}
\tr(K^2)=O_d(\sqrt h\log(h+2)).
\label{local:trace-bound}
\end{equation}
\emph{From trace to contraction.}
We now use permutation symmetry to ensure that every nonconstant
eigenvalue contributes many times to the trace. This is the
multiplicity principle used, in a different setting, in
\cite[Lemma~3.2]{gowers}; here an elementary argument suffices.
We claim that, for even $k\ge6$, every nonzero permutation-invariant
subspace $V\subseteq\R^X$ orthogonal to the constants has dimension
at least $k/2$. Choose $k/2$ disjoint transpositions of the vertices.
Their actions on $V$ are commuting orthogonal involutions, so they
admit simultaneous diagonalization with sign patterns in
$\{1,-1\}^{k/2}$. If a nonzero simultaneous eigenspace has a pattern
with $j$ negative signs, where $00\), there are an integer
\(d\ge1\) and \(N_0\) such that, for every even \(N\ge N_0\), every
positive integer cell-size vector summing to \(N\), and every admissible table,
\begin{equation}\label{smooth:eq-smoothing}
\normop{T_t(I-\Pi_d)}\le N^{-K}.
\end{equation}
Moreover, for each fixed partition \(Z\) and function \(f\), the values
\((T_t\Pi_df)(Z)\), as \(t\) varies over all admissible tables, are
given by a single polynomial of total degree at most \(d\) in the
intercell counts \((t_{uv})_{u2d\). In fact,
every matching then contains an edge entirely outside the fixed
vertices; transposing its endpoints belongs to \(G\), fixes that
matching, and reverses the sign of the function. The function must
vanish at every matching. Thus a diagram occurring in
\(\mathcal P_d^\perp\) has both first row and first column shorter than
\(N-d\).
Let \(\lambda\) be any remaining diagram. The product of its first
row and first column lengths is at least \(N\). Transpose if
necessary so that its first row has length \(b\ge\sqrt N\);
transposition preserves the number of standard tableaux. Retain
that row and a Young subdiagram of exactly \(d\) boxes below it.
Such a subdiagram exists because \(N-b\ge d\).
For large \(N\), we have \(b\ge2d\). Put \(1,\ldots,d\) into the
first \(d\) positions of the top row. Choose any \(d\) of the
remaining \(b\) labels \(d+1,\ldots,b+d\) for the lower boxes, fill
those boxes in a fixed standard order, and put the unused labels
increasingly into the rest of the top row. Each lower box is in
one of the first \(d\) columns, so the resulting tableau is
standard. The \(\binom bd\) choices give distinct tableaux of this
subdiagram. Each extends to \(\lambda\) by adding the remaining
boxes along a fixed corner-addition chain with successively larger
labels. The dimension \(f^\lambda\) therefore satisfies
\[
f^\lambda\ge\binom bd
\ge\frac{b^d}{2^dd!}
\ge c_dN^{d/2},
\]
as required.
\end{proof}
\subsection{From moments to smoothing, and from products to polynomials}
\begin{proof}[Proof of Theorem~\ref{thm:matching-smoothing}]
Complexification does not change operator norms. The operator
\(\mathcal A=T_t^*T_t\) commutes with vertex permutations, since
\(T_t\) intertwines their actions on matchings and partitions.
The projection \(Q=I-\Pi_d\) also commutes with permutations,
because \(\mathcal P_d\) is invariant. The compression
\(B=Q\mathcal A Q\), acting on \(\mathcal P_d^\perp\), is therefore
positive semidefinite and equivariant. Moreover,
\[
\tr(B^2)\le\tr(\mathcal A^2),\qquad
\normop{B}=\normop{T_tQ}^2.
\]
The first inequality is contraction of the Hilbert--Schmidt norm
under orthogonal compression and does not require \(Q\) and
\(\mathcal A\) to commute.
If \(B\ne0\), its largest-eigenvalue eigenspace is invariant and
contains an irreducible constituent. Lemma~\ref{smooth:lem-dimension}
and the fourth-moment bound give
\[
c_dN^{d/2}\normop{T_tQ}^4
\le e^{2a_\ell}(N+1)^{b_\ell}.
\]
The same inequality holds if \(B=0\). Choose \(d\) so that
\(d/2>b_\ell+4K\). For all sufficiently large \(N\), this proves
\eqref{smooth:eq-smoothing}, uniformly in the sizes and the table.
To prove the polynomial assertion, fix a partition and a generating
product of edge indicators. Repeated indicators may be removed,
and a product containing two distinct incident edges vanishes.
Otherwise the specified edges form a partial matching. Let
\(m_{uv}\) be its type counts and let
\[
a_u=2m_{uu}+\sum_{v\ne u}m_{uv}
\]
be the number of its endpoints in cell \(u\). The probability
that a matching with table \(t\) contains these specified edges is
\begin{equation}\label{smooth:eq-containment}
\frac{2^{\sum_um_{uu}}\prod_{u\le v}(t_{uv})_{m_{uv}}}
{\prod_u(s_u)_{a_u}},
\qquad
(z)_j=z(z-1)\cdots(z-j+1),\quad (z)_0=1.
\end{equation}
Indeed, apply a uniform cell-preserving vertex permutation to any
one matching with table \(t\). This is uniform over all such
matchings by transitivity. The denominator counts injections of
the specified endpoint lists, while the numerator chooses distinct
edges of each type and the two orientations of each internal edge.
The denominator is positive because \(a_u\le s_u\).
If \(t_{uv}0$, there are an integer $d\ge1$ and $N_0$ with the following property. Let $N\ge N_0$ be even, and let $a,b,c$ be positive integers summing to $N$. For a uniform ordered partition into cells of these sizes, prescribe $x,y,z$ edges between the first and second, first and third, and second and third cells, respectively. Assume that $x,y,z$ are nonnegative integers and that
\[
a-x-y,\qquad b-x-z,\qquad c-y-z
\]
are nonnegative even integers. Let $T_{x,y,z}$ average functions on perfect matchings subject to these counts, and let $\Pi_d$ project onto the edge-product span of degree at most $d$, using uniform measures as above. Then
\[
\normop{T_{x,y,z}(I-\Pi_d)}\le N^{-K}
\]
uniformly in all the sizes and admissible triples. For every fixed partition and matching function $f$, the values $T_{x,y,z}\Pi_df$ are given by one polynomial of total degree at most $d$ in $(x,y,z)$ across all admissible triples.
\end{corollary}
\begin{proof}
Apply Theorem~\ref{thm:matching-smoothing} with $\ell=3$, intercell counts $t_{12}=x$, $t_{13}=y$, $t_{23}=z$, and internal counts $(a-x-y)/2$, $(b-x-z)/2$, $(c-y-z)/2$.
\end{proof}
==== END Exponential-PSD-rank-of-positively-shifted-matching-matrices//matching-smoothing.tex ====
==== BEGIN Exponential-PSD-rank-of-positively-shifted-matching-matrices//matching.tex ====
\section{From matching factors to low-degree squares}
\label{sec:matching}
We now combine the three ingredients: the local restrictions of
Lemma~\ref{lem:local-averaging}, the product averaging result in
Theorem~\ref{thm:fourier-smoothing}, and the separating functional from
Proposition~\ref{prop:parity-functional}. The vertices of the parity
graph will become cells of matching vertices. Averaging the row factor
within each cell realizes the parity disagreement function exactly.
The Fourier estimate will then approximate that function by squares
on which the separating functional is nonnegative.
\begin{lemma}[Normalization of PSD factors]
\label{lem:normalization}
Let $S$ be a finite nonzero nonnegative matrix with entries at most $B$.
If $S$ admits a real PSD factorization of size $r_0$, it admits one
of size $r\le r_0$ whose row factors $F_a$ and column factors $G_m$
satisfy
\[
\tr F_a\le B,\qquad \tr G_m\le r.
\]
\end{lemma}
\begin{proof}
Compress to the span of the images of all column factors. This
preserves their pairings with the row factors and reduces the size
to some $r\ge1$. The average column factor is positive definite on
this span. Hence the compact convex hull of the column factors
contains a positive definite matrix $J$ maximizing the determinant.
The one-sided derivative of $\log\det$ in the direction $G_m-J$
is nonpositive, giving
\[
\tr(J^{-1}G_m)\le r.
\]
Replace the column factors by $J^{-1/2}G_mJ^{-1/2}$ and the row
factors by $J^{1/2}F_aJ^{1/2}$. These congruences preserve PSD and
trace pairings. The new column traces have the required bound.
The new row trace is $\tr(F_aJ)$, a convex combination of entries
of the original row, and is at most $B$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Use the constants $d=100$, $\beta=1/100$, and $\tau=1/1000$ of
Section~\ref{sec:parity}, and put $L=2^{d-1}$. Let $C_L$ be the
constant in Lemma~\ref{lem:splitting}. First choose $\lambda>1$
so that
\begin{equation}\label{eq:matching-lambda}
\lambda^\tau\ge64L^4.
\end{equation}
Next fix an even integer $k$ large enough for the local construction
and for
\begin{equation}\label{eq:matching-local-smallness}
L\lambda^2C_L\theta_d(k)\le1.
\end{equation}
Lemma~\ref{lem:local-averaging} permits this choice. These constants
are fixed independently of $n$ and $\rho$.
Fix $0<\rho<1$ and set $\epsilon=1-\rho$. For a large even $n$,
let $t$ be the largest even integer satisfying $kt\le n$. Then
\begin{equation}\label{eq:matching-size}
kt\le nD}
\normF{\widehat H_{q,p}G^{1/2}}^2\notag\\
&\le L^t r\lambda^{-\tau t}
\bigl(L^t\sqrt r\,n2^{t/2}\bigr)\notag\\
&\le n\left(\frac{4L^2}{\lambda^\tau}\right)^t
\le n(4L)^{-2t}.
\label{eq:matching-tail}
\end{align}
The first inequality is Cauchy--Schwarz over at most $L^t$
characters in each branch. The second uses
$\normop G\le\tr G\le r$, Equation~\eqref{eq:matching-fourier-bound},
and the fact that an integer distance greater than $D$ is greater
than $\tau t$. The last line uses $r\le2^t$ and
Equation~\eqref{eq:matching-lambda}.
The full stack in Equation~\eqref{eq:matching-full-squares} has norm
at most $\sqrt n$. Expanding the difference of the squared norms
of that stack and its truncation, and then using
Equation~\eqref{eq:matching-tail}, gives
\begin{equation}\label{eq:matching-uniform-error}
\norm{f-f_*}_\infty
\le 2n(4L)^{-t}+n(4L)^{-2t}.
\end{equation}
\paragraph{The separating functional.}
In branch $q$, multiplication by the real character $\chi_q$
does not change any square. It translates a retained frequency
$p$ to $p+q$, whose block degree is $\dist(p,q)\le D$.
This character translation is the elementary support-shifting
principle used in Fourier sums of squares
\cite{fsp-sparse}.
Consequently $f_*$ is a sum of squares of real functions of block
degree at most $D$, including after multiplication by the constant
matrix $G^{1/2}$.
Proposition~\ref{prop:parity-functional} therefore supplies a
functional $\mathcal D$ with
\[
\mathcal D(f_*)\ge0,\qquad \mathcal D(f)=-\epsilon.
\]
On the other hand, its norm bound and
Equation~\eqref{eq:matching-uniform-error} give
\[
|\mathcal D(f-f_*)|
\le 2n4^{-t}+n(16L)^{-t}\longrightarrow0
\]
by Equation~\eqref{eq:matching-size}, since $k$ is fixed.
For sufficiently large $n$, this is smaller than $\epsilon$,
a contradiction.
We have excluded every factorization of size at most $2^t$.
For all sufficiently large $n$, Equation~\eqref{eq:matching-size}
also gives $t\ge n/(2k)$. Thus
\[
\rankpsd A_n(\rho)>2^t\ge2^{n/(2k)}.
\]
Taking $c=1/(2k)$ proves the theorem. Only the final comparison
with $\epsilon=1-\rho$ makes the threshold depend on $\rho$.
\end{proof}
==== END Exponential-PSD-rank-of-positively-shifted-matching-matrices//matching.tex ====
==== BEGIN Exponential-PSD-rank-of-positively-shifted-matching-matrices//parity.tex ====
\section{An expanding parity system}
\label{sec:parity}
We now construct a function that is nonnegative on a product of Boolean
blocks, but is separated from sums of squares of low block degree by a
linear functional. The blocks record incidence bits of a graph. At each
vertex these bits have a prescribed parity, and the total prescribed parity
is odd. Consequently some edge must have different bits at its two ends.
The separating functional nevertheless assigns value zero to the number of
such disagreements. The construction is a block-coordinate version of the
low-degree functionals for Tseitin contradictions; compare
Grigoriev~\cite{grigoriev}. We give the construction and its positivity
proof in full.
Fix the constants
\begin{equation}
d=100,\qquad \beta=\frac1{100},\qquad
\tau=\frac{\beta}{10}=\frac1{1000}.
\label{eq:parity-constants}
\end{equation}
All edges of the multigraphs below are distinguished, even when they have
the same endpoints. Cuts and degrees count these edges with their
multiplicities. For a multigraph \(H\) and a set \(W\) of its vertices,
\(\delta_H(W)\) consists of the edges with exactly one endpoint in \(W\).
Expansion will select a unique small side whenever a cut has few edges;
this will specify the signs in our functional.
\begin{lemma}[Expanding multigraphs]
\label{lem:expander}
For every sufficiently large even integer \(t\), there is a bipartite
\(d\)-regular multigraph \(H\) on \([t]\) such that
\begin{equation}
|\delta_H(W)|\geq \beta d\min\{|W|,t-|W|\}
\qquad (W\subseteq[t]).
\label{eq:parity-expansion}
\end{equation}
In particular, \(H\) is connected.
\end{lemma}
\begin{proof}
Write \(t=2l\), split the vertices into two sets of size \(l\), and take
the union of \(d\) independent uniform perfect matchings between the two
sides. Equivalently, choose \(d\) independent uniform permutations of
\([l]\).
It suffices to check vertex sets of size \(w\leq l\). Fix such a
nonempty set \(W\), containing \(a\) vertices on the first side and
\(b\) on the second, so that \(a+b=w\). Always
\(|\delta_H(W)|\geq d|a-b|\). Thus a failure of
\eqref{eq:parity-expansion} is possible only when
\(|a-b|<.1w\), in which case
\[
.45w\leq a,b\leq .55w.
\]
If the cut has fewer than \(\beta dw\) edges, fewer than \(.05da\)
of the \(da\) images of the first-side vertices can lie outside the
second-side subset: indeed their number is at most
\(\beta dw\leq (.01/.45)da<.05da\).
There are at most \(\exp(.21da)\) choices for these exceptional images,
where an image is specified by its domain vertex and permutation label.
Here we used
\[
\sum_{j\leq .05N}\binom Nj
\leq \exp\bigl(N[-.05\log(.05)-.95\log(.95)]\bigr)
\leq \exp(.21N).
\]
For any prescribed set of nonexceptional images, sampling without
replacement within each permutation bounds the probability that they
all lie in the second-side subset by \((b/l)\) to their number.
Independence between permutations therefore gives
\[
\Pr\bigl[|\delta_H(W)|<\beta dw\bigr]
\leq \exp(.21da)(.55w/l)^{.95da}.
\]
The exponent \(.21+.95\log(.55w/l)\) is negative. Using
\(da\geq45w\) and \(\binom{2l}{w}\leq(2el/w)^w\), a union bound
over all sets of size \(w\) is consequently at most
\[
\exp\!\left(
w\left[\log(2e)+45\bigl(.21+.95\log(.55)\bigr)
+41.75\log(w/l)\right]\right)
\leq e^{-8w}.
\]
The last inequality uses \(w/l\leq1\) and
\(\log(2e)+45(.21+.95\log(.55))<-8\); all logarithms here are
natural. Since \(\sum_{w\geq1}e^{-8w}<1\), some choice of the
permutations satisfies \eqref{eq:parity-expansion}.
A nontrivial connected component would have an empty cut, so the
expansion inequality also gives connectivity.
\end{proof}
Fix a graph \(H\) as in Lemma~\ref{lem:expander}, and order the \(d\)
incidences at each vertex. Choose bits \(b_1,\ldots,b_t\) with odd sum;
one may take \(b_1=1\) and \(b_i=0\) for \(i>1\). At vertex \(i\),
let
\begin{equation}
Y_i=\left\{y_i\in\{0,1\}^d:
\sum_{j=1}^d y_{i,j}=b_i\pmod2\right\},
\qquad Y=\prod_{i=1}^tY_i.
\label{eq:parity-domain}
\end{equation}
The first \(d-1\) bits of \(y_i\) are free and determine the last one.
Thus each \(Y_i\) is an affine Boolean cube of size
\(L=2^{d-1}\), equipped with uniform probability.
We use the block characters of Section~\ref{sec:fourier} in these free
coordinates. Explicitly, set \(\Lambda=\{0,1\}^{d-1}\), with
coordinatewise addition modulo two and zero element \(0\). For
\(p=(p_1,\ldots,p_t)\in\Lambda^t\), define
\[
\chi_p(y)=(-1)^{\sum_{i=1}^t\sum_{j=1}^{d-1}p_{i,j}y_{i,j}},
\qquad |p|_{\mathrm{blk}}=|\{i:p_i\ne0\}|.
\]
These characters form an orthonormal basis for real functions on \(Y\).
A function has \emph{block degree at most \(D\)} if its Fourier
coefficients vanish for \(|p|_{\mathrm{blk}}>D\).
For an edge \(e=uv\), denote its two incidence bits by \(y_{u,e}\) and
\(y_{v,e}\). Given \(\epsilon>0\), define
\begin{equation}
f_\epsilon(y)=
\sum_{e=uv\in E(H)}\mathbf1_{\{y_{u,e}\ne y_{v,e}\}}-\epsilon.
\label{eq:parity-function}
\end{equation}
The sum of the disagreement indicators is odd. Indeed, modulo two it
equals the sum of all incidence bits, and
\(\sum_i b_i\equiv1\pmod2\).
In particular, \(f_\epsilon\geq1-\epsilon>0\) when \(0<\epsilon<1\).
\begin{proposition}[A functional separating low-degree squares]
\label{prop:parity-functional}
For every sufficiently large even \(t\), let \(H\), \(Y\), and
\(f_\epsilon\) be as above, and put \(D=\lfloor\tau t\rfloor\).
There is a real linear functional \(\mathcal D\) on the space of all
real functions on \(Y\) such that
\begin{align}
\mathcal D(1)&=1,
\label{eq:parity-functional-one}\\
\mathcal D(g^2)&\geq0
&&\text{if \(g\) has block degree at most \(D\)},
\label{eq:parity-functional-positivity}\\
\mathcal D(f_\epsilon)&=-\epsilon
&&(\epsilon>0),
\label{eq:parity-functional-value}\\
|\mathcal D(h)|&\leq L^t\norm{h}_\infty
&&\text{for every real function \(h\) on \(Y\)}.
\label{eq:parity-functional-norm}
\end{align}
\end{proposition}
\begin{proof}
We specify \(\mathcal D\) on characters. First map any set of
incidences to the edges having an odd number of incidences in that set.
A character index \(p\) selects the incidences \((i,j)\) for which
\(j