$U^{\prime}=(U_{\tau})_{2},V^{\prime}=(V_{\tau})_{2}$ be the type $2$ vertices
in $U_{\tau},V_{\tau}$ respectively. Let $x_{i}$ for $i\in U^{\prime}\cup
V^{\prime}$ be random variables independently sampled from ${\mathcal{D}}$.
Define $x_{U^{\prime}}$ (resp. $x_{V^{\prime}}$) to be the subset of variables
$x_{i}$ for $i\in U^{\prime}$ (resp. $i\in V^{\prime}$).

For $\rho\in{\mathcal{P}}_{U}$, define
$W_{\rho,\rho}=\mathop{\mathbb{E}}_{y_{U_{2}}\sim{\mathcal{D}}^{U_{2}}}[v_{\rho,y_{U_{2}}}v_{\rho,y_{U_{2}}}^{T}]$
so that $H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}W_{\rho,\rho}$. Observe that
$W_{\rho,\rho}=\mathop{\mathbb{E}}[v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}]=\mathop{\mathbb{E}}[v_{\rho,x_{V^{\prime}}}v_{\rho,x_{V^{\prime}}}^{T}]$
because $x_{U^{\prime}}$ and $x_{V^{\prime}}$ are also sets of variables
sampled from ${\mathcal{D}}$ and, $U^{\prime}$, $V^{\prime}$ have the same
size as $U_{2}$ because $U_{\tau}=V_{\tau}=U$.

For $\rho,\rho^{\prime}\in{\mathcal{P}}_{U}$, define
$Y_{\rho,\rho^{\prime}}=\mathop{\mathbb{E}}\left[v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\right]$.
Then, $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}$. We have

$\displaystyle\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$
$\displaystyle=\frac{S(\tau)}{|Aut(U)|^{2}}\begin{bmatrix}R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}$

Since $\frac{S(\tau)}{|Aut(U)|^{2}}\geq 0$, it suffices to prove that
$\begin{bmatrix}R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}\succeq
0$. Consider

$\displaystyle\begin{bmatrix}R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}=$
$\displaystyle R(\tau)\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}&0\\\ 0&\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\end{bmatrix}$
$\displaystyle+\begin{bmatrix}R(\tau)\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in
P_{\tau}}W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$

We have $\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}=\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}\mathop{\mathbb{E}}[v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}]\succeq
0$. Similarly, $\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\succeq 0$. Also, $R(\tau)\geq 0$ and so, the first term
in the above expression,
$R(\tau)\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}&0\\\ 0&\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\end{bmatrix}$ is positive semidefinite. For the second
term,

$\displaystyle\begin{bmatrix}R(\tau)\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in
P_{\tau}}W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$
$\displaystyle\qquad=\sum_{\rho\in
P_{\tau}}\begin{bmatrix}R(\tau)\mathop{\mathbb{E}}[v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}]&\mathop{\mathbb{E}}\left[v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\right]\\\
\mathop{\mathbb{E}}\left[v_{\rho,x_{U^{\prime}}}^{T}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}\right]&R(\tau)\mathop{\mathbb{E}}[v_{\pi(\rho),x_{V^{\prime}}}v_{\pi(\rho),x_{V^{\prime}}}^{T}]\end{bmatrix}$
$\displaystyle\qquad=\sum_{\rho\in
P_{\tau}}\mathop{\mathbb{E}}\begin{bmatrix}R(\tau)v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}&v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\\\
v_{\rho,x_{U^{\prime}}}^{T}\left(\prod_{i\in U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}&R(\tau)v_{\pi(\rho),x_{V^{\prime}}}v_{\pi(\rho),x_{V^{\prime}}}^{T}\end{bmatrix}$

We will prove that the term inside the expectation is positive semidefinite
for each $\rho\in P_{\tau}$ and each sampling of the $x_{i}$ from
${\mathcal{D}}$, which will complete the proof. Fix $\rho\in P_{\tau}$ and any
sampling of the $x_{i}$ from ${\mathcal{D}}$. Let
$w_{1}=v_{\rho,X_{U^{\prime}}},w_{2}=v_{\pi(\rho),x_{V^{\prime}}}$. Let
$E=\prod_{i\in U^{\prime}\cup V^{\prime}}x_{i}^{deg^{\tau}(i)}$. We would like
to prove that $\begin{bmatrix}R(\tau)w_{1}w_{1}^{T}&Ew_{1}w_{2}^{T}\\\
Ew_{1}^{T}w_{2}&R(\tau)w_{2}w_{2}^{T}\end{bmatrix}\succeq 0$. For all $y$
sampled from ${\mathcal{D}}$, $|y|\leq C_{disc}\sqrt{D_{E}}$ and so,
$|E|\leq(C_{disc}\sqrt{D_{E}})^{\sum_{j\in U^{\prime}\cup
V^{\prime}}deg^{\tau}(j)}=R(\tau)$.

If $E\geq 0$, then

$\displaystyle\begin{bmatrix}R(\tau)w_{1}w_{1}^{T}&Ew_{1}w_{2}^{T}\\\
Ew_{1}^{T}w_{2}&R(\tau)w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)-E)\begin{bmatrix}w_{1}w_{1}^{T}&0\\\
0&w_{2}w_{2}^{T}\end{bmatrix}+E\begin{bmatrix}w_{1}w_{1}^{T}&w_{1}w_{2}^{T}\\\
w_{1}^{T}w_{2}&w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)-E)\left(\begin{bmatrix}w_{1}\\\
0\end{bmatrix}\begin{bmatrix}w_{1}&0\end{bmatrix}+\begin{bmatrix}0\\\
w_{2}\end{bmatrix}\begin{bmatrix}0&w_{2}\end{bmatrix}\right)+E\begin{bmatrix}w_{1}\\\
w_{2}\end{bmatrix}\begin{bmatrix}w_{1}&w_{2}\end{bmatrix}$
$\displaystyle\succeq 0$

since $R(\tau)-E\geq 0$ And if $E<0$,

$\displaystyle\begin{bmatrix}R(\tau)w_{1}w_{1}^{T}&Ew_{1}w_{2}^{T}\\\
Ew_{1}^{T}w_{2}&R(\tau)w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)+E)\begin{bmatrix}w_{1}w_{1}^{T}&0\\\
0&w_{2}w_{2}^{T}\end{bmatrix}-E\begin{bmatrix}w_{1}w_{1}^{T}&-w_{1}w_{2}^{T}\\\
-w_{1}^{T}w_{2}&w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)+E)\left(\begin{bmatrix}w_{1}\\\
0\end{bmatrix}\begin{bmatrix}w_{1}&0\end{bmatrix}+\begin{bmatrix}0\\\
w_{2}\end{bmatrix}\begin{bmatrix}0&w_{2}\end{bmatrix}\right)-E\begin{bmatrix}w_{1}\\\
-w_{2}\end{bmatrix}\begin{bmatrix}w_{1}&-w_{2}\end{bmatrix}$
$\displaystyle\succeq 0$

since $R(\tau)+E\geq 0$.

####  6.2.3 Proof of Lemma 6.17

The next proposition captures the fact that when we compose shapes
$\sigma,\gamma,\gamma^{T},\sigma^{\prime T}$, in order for
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime T}}$ to be
nonzero, the parities of the degrees of the merged vertices should add up
correspondingly.

######  Definition 6.31.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for
$\gamma\in\Gamma_{U,V}$ and parity vectors
$\rho,\rho^{\prime}\in{\mathcal{P}}_{U}$, define the
$\gamma\circ\gamma^{T}$-coefficient matrix
$H_{Id_{V},\rho,\rho^{\prime}}^{-\gamma,\gamma}$ as
$H_{Id_{V},\rho,\rho^{\prime}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})$
if
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U,\rho^{\prime}}$
and $0$ otherwise.

######  Proposition 6.32.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for all
$\gamma\in\Gamma_{U,V}$, there exists a set of parity vectors
$P_{\gamma}\subseteq{\mathcal{P}}_{U}$ such that

$H_{Id_{V}}^{-\gamma,\gamma}=\sum_{\rho\in
P_{\gamma}}H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$

###### Proof.

Take any $\rho\in{\mathcal{P}}_{U}$. For
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U}$, since
$H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=\frac{\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}}}{|Aut(V)|}$, $H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})$ is
nonzero precisely when
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime T}}$ is nonzero.
For this quantity to be nonzero, using Definition 6.9, we get that it is
necessary, but not sufficient, that the parity vector of $\sigma^{\prime}$
must also be $\rho$. And also observe that there exists a set $P_{\gamma}$ of
parity vectors $\rho$ for which $H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$ is
nonzero and their sum is precisely $H_{Id_{V}}^{-\gamma,\gamma}$.

######  Definition 6.33.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for all
$\gamma\in\Gamma_{U,V}$ and parity vector $\rho\in{\mathcal{P}}_{U}$, define
the matrix $H^{\prime}_{\gamma,\rho,\rho}$ as
$H^{\prime}_{\gamma,\rho,\rho}(\sigma,\sigma^{\prime})=H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})$
if $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U,\rho}$ and $0$ otherwise.

######  Proposition 6.34.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for
$\gamma\in\Gamma_{U,V}$, $H_{\gamma}^{\prime}=\sum_{\rho\in
P_{\gamma}}H_{\gamma,\rho,\rho}^{\prime}$.

We will now define vectors which are truncations of $v_{\rho,x_{U_{2}}}$.

######  Definition 6.35.

Let $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, and let
$\gamma\in\Gamma_{U,V}$. Let $x_{i}$ for $i\in U_{2}$ be variables. Denote
them collectively as $x_{U_{2}}$. For $\rho\in{\mathcal{P}}_{U}$, define
$v_{\rho,x_{U_{2}}}^{-\gamma}$ to be the vector indexed by left shapes
$\sigma\in{\mathcal{L}}$ such that the $\sigma$th entry is
$v_{\rho,x_{U_{2}}}(\sigma)$ if $|V(\sigma\circ\gamma)|\leq D_{V}$ and $0$
otherwise.

We restate Definition 6.16 for convenience.

See 6.16

######  Proposition 6.36.

For any $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, and for any
$\gamma\in\Gamma_{U,V}$, suppose we take $\rho\in P_{\gamma}$. When we compose
$\gamma$ with $\gamma^{T}$ to get $\gamma\circ\gamma^{T}$, let
$U^{\prime}=(U_{\gamma\circ\gamma^{T}})_{2},V^{\prime}=(V_{\gamma\circ\gamma^{T}})_{2}$
be the type $2$ vertices in
$U_{\gamma\circ\gamma^{T}},V_{\gamma\circ\gamma^{T}}$ respectively. And let
$W^{\prime}$ be the set of type $2$ vertices in $\gamma\circ\gamma^{T}$ that
were identified in the composition when we set $V_{\gamma}=U_{\gamma}^{T}$.
Let $x_{i}$ for $i\in U^{\prime}\cup W^{\prime}\cup V^{\prime}$ be random
variables independently sampled from ${\mathcal{D}}$. Define $x_{U^{\prime}}$
(resp. $x_{V^{\prime}},x_{W^{\prime}}$) to be the subset of variables $x_{i}$
for $i\in U^{\prime}$ (resp. $i\in V^{\prime},i\in W^{\prime}$). Then,

$H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}=\frac{1}{|Aut(V)|}S(\gamma)^{2}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

###### Proof.

Fix $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U,\rho}$ such that
$|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$. Note that
for $t\in\\{1,2\\}$,
$|\sigma|_{t}-\frac{|V_{\sigma}|_{t}}{2}+|\sigma^{\prime}|_{t}-\frac{|V_{\sigma^{\prime}}|_{t}}{2}+2(|\gamma|_{t}-\frac{|U_{\gamma}|_{t}+|V_{\gamma}|_{t}}{2})=|\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}|_{t}$. We can easily verify the equality using Definition 6.9 and
Definition 6.25.

######  Proposition 6.37.

For any $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, and for any
$\gamma\in\Gamma_{U,V}$, suppose we take $\rho\in{\mathcal{P}}_{U}$. Then,

$H^{\prime}_{\gamma,\rho,\rho}=\frac{1}{|Aut(U)|}\mathop{\mathbb{E}}_{y_{U_{2}}\sim{\mathcal{D}}^{U_{2}}}\left[(v_{\rho,y_{U_{2}}}^{-\gamma})(v_{\rho,y_{U_{2}}}^{-\gamma})^{T}\right]$

We can now prove Lemma 6.17.

See 6.17

###### Proof.

Let $U^{\prime},V^{\prime},W^{\prime}$ be as in 6.36. We have

$\displaystyle\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle=\sum_{\rho\in
P_{\gamma}}\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$
$\displaystyle=\sum_{\rho\in
P_{\gamma}}\frac{1}{|Aut(U)|}\cdot\frac{1}{R(\gamma)^{2}}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

We will now prove that, for all $\rho\in P_{\gamma}$,

$\displaystyle\frac{1}{|Aut(U)|}\cdot\frac{1}{R(\gamma)^{2}}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]\preceq
H^{\prime}_{\gamma,\rho,\rho}$

This reduces to proving that

$\displaystyle\frac{2}{R(\gamma)^{2}}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$
$\displaystyle\preceq
2\mathop{\mathbb{E}}_{y_{U_{2}}\sim{\mathcal{D}}^{U_{2}}}\left[(v_{\rho,y_{U_{2}}}^{-\gamma})(v_{\rho,y_{U_{2}}}^{-\gamma})^{T}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

where the last equality followed from linearity of expectation and the fact
that $U^{\prime}\equiv V^{\prime}\equiv U_{2}$.

Since $H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$ is symmetric, we have

$\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]=\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{V^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}\right]$

So, it suffices to prove

$\displaystyle\frac{1}{R(\gamma)^{2}}$
$\displaystyle\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}\right]$
$\displaystyle\preceq\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

We will prove that for every sampling of the $x_{i}$ from ${\mathcal{D}}$, we
have

$\displaystyle\frac{1}{R(\gamma)^{2}}$
$\displaystyle\left((v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}\right)$
$\displaystyle\preceq(v_{\rho,x_{U^{\prime}}}^{-\gamma})(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}$

Then, taking expectations will give the result. Indeed, fix a sampling of the
$x_{i}$ from ${\mathcal{D}}$. Let $E=\prod_{i\in U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}$ and let
$w_{1}=v_{\rho,x_{U^{\prime}}}^{-\gamma},w_{2}=v_{\rho,x_{V^{\prime}}}^{-\gamma}$.
Then, the inequality we need to show is

$\frac{E}{R(\gamma)^{2}}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})\preceq
w_{1}w_{1}^{T}+w_{2}w_{2}^{T}$

Now, since $|x_{i}|\leq C_{disc}\sqrt{D_{E}}$ for all $i$, we have
$|E|\leq\prod_{i\in U^{\prime}\cup W^{\prime}\cup
V^{\prime}}(C_{disc}\sqrt{D_{E}})^{deg^{\gamma\circ\gamma^{T}}(i)}=R(\gamma)^{2}$.

If $E\geq 0$, using
$\frac{E}{R(\gamma)^{2}}(w_{1}-w_{2})(w_{1}-w_{2})^{T}\succeq 0$ gives

$\displaystyle\frac{E}{R(\gamma)^{2}}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})$
$\displaystyle\preceq\frac{E}{R(\gamma)^{2}}(w_{1}w_{1}^{T}+w_{2}w_{2}^{T})$
$\displaystyle\preceq w_{1}w_{1}^{T}+w_{2}w_{2}^{T}$

since $0\leq E\leq R(\gamma)^{2}$.

And if $E<0$, using
$\frac{-E}{R(\gamma)^{2}}(w_{1}+w_{2})(w_{1}+w_{2})^{T}\succeq 0$ gives

$\displaystyle\frac{E}{R(\gamma)^{2}}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})$
$\displaystyle\preceq\frac{-E}{R(\gamma)^{2}}(w_{1}w_{1}^{T}+w_{2}w_{2}^{T})$
$\displaystyle\preceq w_{1}w_{1}^{T}+w_{2}w_{2}^{T}$

since $0\leq-E\leq R(\gamma)^{2}$.

Finally, we use the fact that for all $\rho\in{\mathcal{P}}_{U}$, we have
$H^{\prime}_{\gamma,\rho,\rho}\succeq 0$ which can be proved the same way as
the proof of Lemma 6.11. Therefore,

$\displaystyle\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle\preceq\sum_{\rho\in P_{\gamma}}H^{\prime}_{\gamma,\rho,\rho}$
$\displaystyle\preceq\sum_{\rho\in{\mathcal{P}}_{U}}H^{\prime}_{\gamma,\rho,\rho}$
$\displaystyle=H^{\prime}_{\gamma}$

##  7 Technical Definitions and Theorem Statement

###  7.1 Section Introduction

In this section, we make our definitions and results more precise. We also
generalize our definitions and results to handle problems where one or more of
the following is true:

  1. 1.

The input entries correspond to hyperedges rather than edges.

  2. 2.

We have different types of indices.

  3. 3.

$\Omega$ is a more complicated distribution than $\\{-1,+1\\}$.

  4. 4.

We have to consider matrix indices which are not multilinear.

Throughout this section and the remainder of this manuscript, we give the
reader a choice for the level of generality of this machinery. In particular,
we will first recall our definition for the simpler case when our input is
$\\{-1,+1\\}^{\binom{n}{2}}$ and we only consider multilinear indices. We will
then discuss how this simpler definition generalizes. We denote these
generalizations with an asterix $*$.

####  7.1.1 Additional Parameters for the General Case*

In the general case we will need a few additional parameters which we define
here.

######  Definition 7.1.

  1. 1.

We define $k$ to be the arity of the hyperedges corresponding to the input.

  2. 2.

We define $t_{max}$ to be the number of different types of indices. We define
$n_{i}$ to be the number of possibilities for indicies of type $i$ and we
define $n=\max{\\{n_{i}:i\in[t_{max]}\\}}$.

###  7.2 Indices, Input Entries, Vertices, and Edges

Note: For this section, we use $X$ to denote the input, we use $x$ to denote
entries of the input and we use $y$ to denote solution variables.

######  Definition 7.2 (Vertices: Simplified Case).

When the input and solution variables are indexed by one type of index which
takes values in $[n]$ then we represent the index $i$ by a vertex labeled $i$.

If we want to leave an index unspecified, we instead represent it by a vertex
labeled with a variable (we will generally use $u$, $v$, or $w$ for these
variables).

######  Definition 7.3 (Vertices: General Case*).

When the input and solution variables are indexed by several types of indices
where indices of type $t$ take values in $[n_{t}]$, we represent an index of
type $t$ with value $i$ as a vertex labeled by the tuple $(t,i)$. We say that
such a vertex has type $t$.

If we want to leave an index of type $t$ unspecified, we instead represent it
by a vertex labeled with a tuple $(t,?)$ where $?$ is a variable (which will
generally be $u$, $v$, or $w$).

######  Definition 7.4 (Edges: Simplified Case).

When the input is $X\in\\{-1,+1\\}^{\binom{n}{2}}$, we represent the entries
of the input by the undirected edges $\\{(i,j):i<j\in[n]\\}$. Given an edge
$e=(i,j)$, we take $x_{e}=x_{ij}$ to be the input entry corresponding to $e$.

######  Definition 7.5 (Edges: General Case*).

In general, we represent the entries of the input by hyperedges whose form
depends on nature of the input. We still take $x_{e}$ to be the input entry
corresponding to $e$.

######  Example 7.6.

If the input is an $n_{1}\times n_{2}$ matrix $X$ then we will have two types
of indices, one for the row and one for the column. Thus, we will have the
vertices $\\{(1,i):i\in[n_{1}]\\}\cup\\{(2,j):j\in[n_{2}]\\}$. In this case,
we have an edge $((1,i),(2,j))$ for each entry $x_{ij}$ of the input.

######  Example 7.7.

If the input is an $n\times n$ matrix $X$ which is not symmetric then we only
need the indices $[n]$. In this case, we have a directed edge $(i,j)$ for each
entry $x_{ij}$ where $i\neq j$. If the entries $x_{ii}$ are also part of the
input than we also have loops $(i,i)$ for these entries.

######  Example 7.8.

If our input is a symmetric $n\times n\times n$ tensor $X$ (i.e.
$x_{ijk}=x_{ikj}=x_{jik}=x_{jki}=x_{kij}=x_{kji}$) and $x_{ijk}=0$ whenever
$i,j,k$ are not distinct then we only need the indices $[n]$. In this case, we
have an undirected hyperedge $e=(i,j,k)$ for each entry $x_{e}=x_{ijk}$ of the
input where $i,j,k$ are distinct.

######  Example 7.9.

If the input is an $n_{1}\times n_{2}\times n_{3}$ tensor $X$ then we will
have three types of indices. Thus, we will have the vertices
$\\{(1,i):i\in[n_{1}]\\}\cup\\{(2,j):j\in[n_{2}]\\}\cup\\{(3,k):k\in[n_{3}]\\}$.
In this case, we have a hyperedge $e=((1,i),(2,j),(3,k))$ for each entry
$x_{e}=x_{ijk}$ of the input.

###  7.3 Matrix Indices and Monomials

In this subsection, we discuss how our matrices are indexed and how we
associate matrix indices with monomials. We also describe the automorphism
groups of matrix indices.

######  Definition 7.10 (Matrix Indices: Simplified Case).

If there is only one type of index and we have the constraints $y^{2}_{i}=1$
or $y^{2}_{i}=y_{i}$ on the solution variables then we define a matrix index
$A$ to be a tuple of indices $(a_{1},\ldots,a_{|A|})$. We make the following
definitions about matrix indices:

  1. 1.

We associate the monomial $\prod_{j=1}^{|A|}{y_{a_{j}}}$ to $A$.

  2. 2.

We define $V(A)$ to be the set of vertices $\\{a_{i}:i\in[|A|]\\}$. For
brevity, we will often write $A$ instead of $V(A)$ when it is clear from
context that we are referring to $A$ as a set of vertices rather than a matrix
index.

  3. 3.

We take the automorphism group of $A$ to be $Aut(A)=S_{|A|}$ (the permutations
of the elements of $A$)

######  Example 7.11.

The matrix index $A=(4,6,1)$ represents the monomial
${y_{4}}{y_{6}}{y_{1}}={y_{1}}{y_{4}}{y_{6}}$ and $Aut(A)=S_{3}$

######  Remark 7.12.

We take $A$ to be an ordered tuple rather than a set for technical reasons.

In general, we need a more intricate definition for matrix indices. We start
by defining matrix index pieces

######  Definition 7.13 (Matrix Index Piece Definition*).

We define a matrix index piece
$A_{i}=((a_{i1},\ldots,a_{i|A_{i}|}),t_{i},p_{i})$ to be a tuple of indices
$(a_{i1},\ldots,a_{i|A_{i}|})$ together with a type $t_{i}$ and a power
$p_{i}$. We make the following definitions about matrix index pieces:

  1. 1.

We associate the monomial
$p_{A_{i}}=\prod_{j=1}^{|A_{i}|}{y^{p_{i}}_{{t_{i}}j}}$ with $A_{i}$.

  2. 2.

We define $V(A_{i})$ to be the set of vertices
$\\{(t_{i},a_{ij}):j\in[|A_{i}|]\\}$.

  3. 3.

We take the automorphism group of $A_{i}$ to be $Aut(A_{i})=S_{|A_{i}|}$

  4. 4.

We say that $A_{i}$ and $A_{j}$ are disjoint if $V(A_{i})\cap
V(A_{j})=\emptyset$ (i.e. $t_{i}\neq t_{j}$ or
$\\{a_{i1},\ldots,a_{i|A_{i}|}\\}\cap\\{a_{j1},\ldots,a_{j|A_{j}|}\\}=\emptyset$)

######  Definition 7.14 (General Matrix Index Definition*).

We define a matrix index $A=\\{A_{i}\\}$ to be a set of disjoint matrix index
pieces. We make the following definitions about matrix indices:

  1. 1.

We associate the monomial $p_{A}=\prod_{A_{i}\in A}{p(A_{i})}$ with $A$.

  2. 2.

We define $V(A)$ to be the set of vertices $\cup_{A_{i}\in A}{V(A_{i})}$. For
brevity, we will often write $A$ instead of $V(A)$ when it is clear from
context that we are referring to $A$ as a set of vertices rather than a matrix
index.

  3. 3.

We take the automorphism group of $A$ to be $Aut(A)=\prod_{A_{i}\in
A}{Aut(A_{i})}$

######  Example 7.15 (*).

If $A_{1}=((2),1,1)$, $A_{2}=((3,1),1,2)$, and $A_{3}=((1,2,3),2,1)$ then
$A=\\{A_{1},A_{2},A_{3}\\}$ represesents the monomial
$p={y_{12}}{y^{2}_{13}}{y^{2}_{11}}{y_{21}}{y_{22}}{y_{23}}$ and we have
$Aut(A)=S_{1}\times S_{2}\times S_{3}$

###  7.4 Fourier Characters and Ribbons

A key idea is to analyze Fourier characters of the input.

######  Definition 7.16 (Simplified Fourier Characters).

If the input distribution is $\Omega=\\{-1,1\\}$ then given a multi-set of
edges $E$, we define $\chi_{E}(X)=\prod_{e\in E}{x_{e}}$.

######  Example 7.17.

If the input is a graph $G\in\\{-1,1\\}^{\binom{n}{2}}$ and $E$ is a set of
potential edges of $G$ (with no multiple edges) then
$\chi_{E}(G)=(-1)^{|E\setminus E(G)|}$.

In general, the Fourier characters are somewhat more complicated.

######  Definition 7.18 (Orthonormal Basis for ${\Omega}$*).

We define the polynomials $\\{h_{i}:i\in\mathbb{Z}\cap[0,|supp(\Omega)|-1]\\}$
to be the unique polynomials (which can be found through the Gram-Schmidt
process) such that

  1. 1.

$\forall i,E_{\Omega}[h^{2}_{i}(x)]=1$

  2. 2.

$\forall i\neq j,E_{\Omega}[h_{i}(x)h_{j}(x)]=0$

  3. 3.

For all $i$, the leading coefficient of $h_{i}(x)$ is positive.

######  Example 7.19.

If $\Omega$ is the normal distribution then the polynomials $\\{h_{i}\\}$ are
the Hermite polynomials with the appropriate normalization so that for all
$i$, $E_{\Omega}[h^{2}_{i}(x)]=1$. In particular, $h_{0}(x)=1$, $h_{1}(x)=x$,
$h_{2}(x)=\frac{x^{2}-1}{\sqrt{2!}}$, $h_{3}(x)=\frac{x^{3}-3x}{\sqrt{3!}}$,
etc.

######  Definition 7.20 (General Fourier Characters*).

Given a multi-set of hyperedges $E$, each of which has a label
$l(e)\in[|support(\Omega)|-1]$ (or $\mathbb{N}$ if $\Omega$ has infinite
support), we define $\chi_{E}=\prod_{e\in E}{h_{l(e)}{(X_{e})}}$.

We say that such a multi-set of hyperedges $E$ is proper if it contains no
duplicate hyperedges, i.e. it is a set (though the labels on the hyperedges
can be arbitrary non-negative integers). Otherwise, we say that $E$ is
improper.

######  Remark 7.21.

The Fourier characters are $\\{\chi_{E}:E\text{ is proper}\\}$. For improper
$E$, $\chi_{E}$ can be decomposed as a linear combination of $\chi_{E_{j}}$
where each $E_{j}$ is proper. We allow improper $E$ because it is sometimes
more convenient to have improper $E$ in the middle of the analysis and then do
this decomposition at the end.

######  Definition 7.22 (Ribbons).

A ribbon $R$ is a tuple $(H_{R},A_{R},B_{R})$ where $H_{R}$ is a multi-graph
(*or multi-hypergraph with labeled edges in the general case) whose vertices
are indices of the input and $A_{R}$ and $B_{R}$ are matrix indices such that
$V(A_{R})\subseteq V(H_{R})$ and $V(B_{R})\subseteq V(H_{R})$. We make the
following definitions about ribbons:

  1. 1.

We define $V(R)=V(H_{R})$ and $E(R)=E(H_{R})$

  2. 2.

We define $\chi_{R}=\chi_{E(R)}$.

  3. 3.

We define $M_{R}$ to be the matrix such that
$(M_{R})_{{A_{R}}{B_{R}}}=\chi_{R}$ and $M_{AB}=0$ whenever $A\neq A_{R}$ or
$B\neq B_{R}$.

We say that $R$ is a proper ribbon if $H_{R}$ contains no isolated vertices
outside of $A_{R}\cup B_{R}$ and $E(R)$ is proper. If there is an isolated
vertex in $(V(R)\setminus A_{R})\setminus B_{R}$ or $E(R)$ is improper then we
say that $R$ is an improper ribbon.

Proper ribbons are useful because they give an orthonormal basis for the space
of matrix valued functions.

######  Definition 7.23 (Inner products of matrix functions).

For a pair of real matrices $M_{1},M_{2}$ of the same dimension, we write
$\langle{M_{1},M_{2}}\rangle=tr({M_{1}}{M_{2}}^{T})$ (i.e.
$\langle{M_{1},M_{2}}\rangle$ is the entrywise dot product of $M_{1}$ and
$M_{2}$). For a pair of matrix-valued functions $M_{1},M_{2}$ (of the same
dimensions), we define

$\langle{M_{1},M_{2}}\rangle=E_{X}\left[\langle{M_{1}(X),M_{2}(X)}\rangle\right]$

######  Proposition 7.24.

If $R$ and $R^{\prime}$ are two proper ribbons then
$\langle{M_{R},M_{R^{\prime}}}\rangle=1$ if $R=R^{\prime}$ and is $0$
otherwise.

###  7.5 Shapes

In this subsection, we describe a basis for $S$-invariant matrix valued
functions where each matrix in this basis can be described by a relatively
small _shape_ $\alpha$. The fundamental idea behind shapes is that we keep the
structure of the objects we are working with but leave the elements of the
object unspecified.

####  7.5.1 Simplified Index Shapes

######  Definition 7.25 (Simplified Index shapes).

With our simplifying assumptions, an index shape $U$ is a tuple of unspecified
indices $(u_{1},\cdots,u_{|U|})$. We make the following definitions about
index shapes:

  1. 1.

We define $V(U)$ to be the set of vertices $\\{u_{i}:i\in[|U|]\\}$. For
brevity, we will often write $U$ instead of $V(U)$ when it is clear from
context that we are referring to $U$ as a set of vertices rather than an index
shape.

  2. 2.

We define the weight of $U$ to be $w(U)=|U|$.

  3. 3.

We take the automorphism group of $U$ to be $Aut(U)=S_{|U|}$ (the permutations
of the elements of $U$)

######  Definition 7.26.

We say that a matrix index $A=(a_{1},\ldots,a_{|A|})$ has index shape
$U=(u_{1},\ldots,u_{|U|})$ if $|U|=|A|$. Note that in this case, if we take
the map $\varphi:\\{u_{j}:j\in[|U|]\\}\rightarrow[n]$ where
$\varphi(u_{j})=a_{j}$ then
$\varphi(U)=(\varphi(u_{1}),\ldots,\varphi(u_{|U|}))=(a_{1},\ldots,a_{|A|})=A$

######  Definition 7.27.

We say that index shapes $U=(u_{1},\ldots,u_{|U|})$ and
$V=(v_{1},\ldots,v_{|V|})$ are equivalent (which we write as $U\equiv V$) if
$|U|=|V|$. If $U\equiv V$ then we can set $U=V$ by setting $v_{j}=u_{j}$ for
all $j\in[|U|]$.

######  Example 7.28.

The matrix index $A=\\{4,6,1\\}$ has shape $U=\\{u_{1},u_{2},u_{3}\\}$ which
has weight $3$.

####  7.5.2 General Index Shapes*

In general, we define general index shapes in the same way that we defined
general matrix indices (just with unspecified indices)

######  Definition 7.29 (Index Shape Piece Definition).

We define a index shape piece
$U_{i}=((u_{i1},\ldots,u_{i|U_{i}|}),t_{i},p_{i})$ to be a tuple of indices
$(u_{i1},\ldots,u_{i|A_{i}|})$ together with a type $t_{i}$ and a power
$p_{i}$. We make the following definitions about index shape pieces:

  1. 1.

We define $V(U_{i})$ to be the set of vertices
$\\{(t_{i},u_{ij}):j\in[|U_{i}|]\\}$.

  2. 2.

We define $w(U_{i})=|U_{i}|log_{n}(n_{t_{i}})$

  3. 3.

We take the automorphism group of $U_{i}$ to be $Aut(U_{i})=S_{|U_{i}|}$

######  Definition 7.30 (General Index Shape Definition).

We define an index shape $U=\\{U_{i}\\}$ to be a set of index shape pieces
such that for all $i^{\prime}\neq i$, either $t_{i^{\prime}}\neq t_{i}$ or
$p_{i^{\prime}}\neq p_{i}$. We make the following definitions about index
shapes:

  1. 1.

We define $V(U)$ to be the set of vertices $\cup_{U_{i}\in U}{V(U_{i})}$. For
brevity, we will often write $U$ instead of $V(U)$ when it is clear from
context that we are referring to $U$ as a set of vertices rather than an index
shape.

  2. 2.

We define $w(U)$ to be $w(U)=\sum_{U_{i}\in U}{w(U_{i})}$

  3. 3.

We take the automorphism group of $U$ to be $Aut(U)=\prod_{U_{i}\in
U}{Aut(U_{i})}$

######  Remark 7.31.

For technical reasons, we want to ensure that if two index shapes $U$ and
$U^{\prime}$ have the same weight then $U$ and $U^{\prime}$ have the same
number of each type of vertex. To ensure this, we add an infinitesimal
perturbation to each $n_{i}$ if necessary.

######  Definition 7.32.

We say that a matrix index $A$ has index shape $U$ if there is an assignment
of values to the unspecified indices of $U$ which results in $A$. More
precisely, we say that $A$ has index shape $U$ if there is a map
$\varphi:\\{u_{ij}\\}\rightarrow\mathbb{N}$ such that if we define
$\varphi(U_{i})$ to be
$\varphi(U_{i})=((\varphi(u_{i1}),\ldots,\varphi(u_{i|U_{i}|})),t_{i},p_{i})$
then $\varphi(U)=\\{\varphi(U_{i})\\}=\\{A_{i}\\}=A$.

######  Definition 7.33.

If $U$ and $V$ are two index shapes, we say that $U$ is equivalent to $V$
(which we write as $U\equiv V$) if $U$ and $V$ have the same number of index
shape pieces and we can order the index shape pieces of $U$ and $V$ so that
writing $U=\\{U_{i}\\}$ and $V=\\{V_{i}\\}$ where
$U_{i}=((u_{i1},\ldots,u_{i|U_{i}|}),t_{i},p_{i})$ and
$V_{i}=((v_{i1},\ldots,v_{i|V_{i}|}),t^{\prime}_{i},p^{\prime}_{i})$, we have
that for all $i$, $|V_{i}|=|U_{i}|$, $t^{\prime}_{i}=t_{i}$, and
$p^{\prime}_{i}=p_{i}$. If $U\equiv V$ then we can set $U=V$ by setting
$u_{ij}=v_{ij}$ for all $i$ and all $j\in[|U_{i}|]$.

####  7.5.3 Ribbon Shapes

With these definitions, we are now ready to define shapes and the matrices
associated to them.

######  Definition 7.34 (Shapes).

A ribbon shape $\alpha$ (which we call a shape for brevity) is a tuple
$\alpha=(H_{\alpha},U_{\alpha},V_{\alpha})$ where $H_{\alpha}$ is a multi-
graph (*or multi-hypergraph with labeled edges in the general case) whose
vertices are unspecified distinct indices of the input (*whose type is
specified in the general case) and $U_{\alpha}$ and $V_{\alpha}$ are index
shapes such that $V(U_{\alpha})\subseteq V(H_{\alpha})$ and
$V(V_{\alpha})\subseteq V(H_{\alpha})$. We make the following definitions
about shapes:

  1. 1.

We define $V(\alpha)=V(H_{\alpha})$ (note that $V(\alpha)$ and $V_{\alpha}$
are not the same thing) and we define $E(\alpha)=E(H_{\alpha})$.

  2. 2.

We say that a shape $\alpha$ is proper if it contains no isolated vertices
outside of $V(U_{\alpha})\cup V(V_{\alpha})$, $E(\alpha)$ has no multiple
edges/hyperedges and edges in $E(\alpha)$ do not have label $0$. If there is
an isolated vertex in $V(\alpha)\setminus V(U_{\alpha})\setminus
V(V_{\alpha})$ or $E(\alpha)$ has a multiple edge/hyperedge then we say that
$\alpha$ is an improper shape.

Note: For brevity, we will often write $U_{\alpha}$ and $V_{\alpha}$ instead
of $V(U_{\alpha})$ and $V(V_{\alpha})$ when it is clear from context that we
are referring to $U_{\alpha}$ and $V_{\alpha}$ as sets of vertices rather than
index shapes.

######  Definition 7.35 (Trivial shapes).

We say that a shape $\alpha$ is trivial if
$V(\alpha)=V(U_{\alpha})=V(V_{\alpha})$ and $E(\alpha)=\emptyset$. Otherwise,
we say that $\alpha$ is non-trivial.

######  Remark 7.36.

Note that all trivial shapes can do is permute the order of the vertices in
$V(U_{\alpha})=V(V_{\alpha})$.

######  Definition 7.37.

Informally, we say that a ribbon $R$ has shape $\alpha$ if replacing the
indices in $R$ with unspecified labels results in $\alpha$. Formally, we say
that $R$ has shape $\alpha$ if there is an injective mapping
$\varphi:V(\alpha)\rightarrow[n]$ (*or $[t_{max}]\times[n]$ in the general
case) such that $\varphi(\alpha)=R$, i.e. $\varphi(H_{\alpha})=H_{R}$,
$\varphi(U_{\alpha})=A_{R}$, and $\varphi(V_{\alpha})=B_{R}$

######  Definition 7.38.

We say that two shapes $\alpha$ and $\beta$ are equivalent (which we write as
$\alpha\equiv\beta$) if they are the same up to renaming their indices. More
precisely, we say that $\alpha\equiv\beta$ if there is a bijective map
$\pi:V(H_{\alpha})\rightarrow V(H_{\beta})$ such that
$\pi(H_{\alpha})=H_{\beta}$, $\pi(U_{\alpha})=U_{\beta}$, and
$\pi(V_{\alpha})=V_{\beta}$.

######  Definition 7.39.

Given a shape $\alpha$ and matrix indices $A,B$ of shapes $U_{\alpha}$ and
$V_{\alpha}$ respectively, we define $\mathcal{R}(\alpha,A,B)$ to be the set
of ribbons $R$ such that $R$ _has shape $\alpha$_, $A_{R}=A$, and $B_{R}=B$.

######  Definition 7.40.

For a shape $\alpha$, we define the matrix-valued function $M_{\alpha}$ to
have entries $M_{\alpha}(A,B)$ given by

$(M_{\alpha})_{A,B}(X)=\sum_{R\in\mathcal{R}(\alpha,A,B)}\chi_{R}(X)$

For examples of $M_{\alpha}$, see [AMP20].

######  Proposition 7.41.

The $M_{\alpha}$’s for proper shapes $\alpha$ are an orthogonal basis for the
$S$-invariant functions.111 Because of orthogonality of the underlying Fourier
characters, it is not hard to check that when $\alpha\neq\alpha^{\prime}$ and
$M_{\alpha},M_{\alpha^{\prime}}$ have the same dimensions,
$\langle{M_{\alpha},M_{\alpha^{\prime}}}\rangle=0$.

######  Remark 7.42.

Conceptually, one may think of forming an orthonormal basis for this space
with the functions $M_{\alpha}/\sqrt{\langle{M_{\alpha},M_{\alpha}}\rangle}$,
but for technical reasons it is easiest to work with these functions without
normalizing them to $1$. By orthogonality and the fact that every Boolean
function is a polynomial, any $S$-invariant matrix-valued function $\Lambda$
is expressible as

$\Lambda=\sum_{\alpha}\frac{\langle{\Lambda,M_{\alpha}}\rangle}{\langle{M_{\alpha},M_{\alpha}}\rangle}\cdot
M_{\alpha}$

###  7.6 Composing Ribbons and Shapes

######  Definition 7.43 (Composing Ribbons).

We say that ribbons $R_{1}$ and $R_{2}$ are composable if
$B_{R_{1}}=A_{R_{2}}$. Note that this definition is not symmetric so we may
have that $R_{1}$ and $R_{2}$ are composable but $R_{2}$ and $R_{1}$ are not
composable.

We say that $R_{1}$ and $R_{2}$ are properly composable if we also have that
$V(R_{1})\cap V(R_{2})=V(B_{R_{1}})=V(A_{R_{2}})$ (there are no unexpected
intersections between $R_{1}$ and $R_{2}$).

If $R_{1}$ and $R_{2}$ are composable ribbons then we define the composition
of $R_{1}$ and $R_{2}$ to be the ribbon $R_{1}\circ R_{2}$ such that

  1. 1.

$A_{R_{1}\circ R_{2}}=A_{R_{1}}$ and $B_{R_{1}\circ R_{2}}=B_{R_{2}}$

  2. 2.

$V(R_{1}\circ R_{2})=V(R_{1})\cup V(R_{2})$

  3. 3.

$E(R_{1}\circ R_{2})=E(R_{1})\cup E(R_{2})$ (and thus $\chi_{R_{1}\circ
R_{2}}=\chi_{R_{1}}\chi_{R_{2}}$)

We say that ribbons $R_{1},\ldots,R_{k}$ are composable/properly composable if
for all $j\in[k-1]$, $R_{1}\circ\ldots\circ R_{j}$ and $R_{j+1}$ are
composable/properly composable. If $R_{1},\ldots,R_{k}$ are composable then we
define $R_{1}\circ\ldots\circ R_{k}$ to be $R_{1}\circ\ldots\circ
R_{k}=(R_{1}\circ\ldots\circ R_{k-1})\circ R_{k}$

######  Proposition 7.44.

Ribbon composition is associative, i.e. if $R_{1},R_{2},R_{3}$ are
composable/properly composable ribbons then $R_{2},R_{3}$ are
composable/properly composable, $R_{1},(R_{2}\circ R_{3})$ are
composable/properly composable, and $R_{1}\circ(R_{2}\circ R_{3})=(R_{1}\circ
R_{2})\circ R_{3}$

######  Proposition 7.45.

If $R_{1}$ and $R_{2}$ are composable ribbons then $M_{R_{1}\cup
R_{2}}=M_{R_{1}}M_{R_{2}}$.

We have similar definitions for composing shapes.

######  Definition 7.46 (Composing Shapes).

We say that shapes $\alpha$ and $\beta$ are composable if $U_{\beta}\equiv
V_{\alpha}$. Note that this definition is not symmetric so we may have that
$\alpha$ and $\beta$ are composable but $\beta$ and $\alpha$ are not
composable.

If $\alpha$ and $\beta$ are composable shapes then we define the composition
of $\alpha$ and $\beta$ to be the shape $\alpha\circ\beta$ such that

  1. 1.

$U_{\alpha\circ\beta}=U_{\alpha}$ and $V_{\alpha\circ\beta}=V_{\beta}$

  2. 2.

After setting $U_{\beta}=V_{\alpha}$, we take
$V(\alpha\circ\beta)=V(\alpha)\cup V(\beta)$

  3. 3.

$E(\alpha\circ\beta)=E(\alpha)\cup E(\beta)$

We say that shapes $\alpha_{1},\ldots,\alpha_{k}$ are composable if for all
$j\in[k-1]$, $\alpha_{1}\circ\ldots\circ\alpha_{j}$ and $\alpha_{j+1}$ are
composable. If $\alpha_{1},\ldots,\alpha_{k}$ are composable then we define
the shape $\alpha_{1}\circ\ldots\circ\alpha_{k}$ to be
$\alpha_{1}\circ\ldots\circ\alpha_{k}=(\alpha_{1}\circ\ldots\circ\alpha_{k-1})\circ\alpha_{k}$

######  Proposition 7.47.

Shape composition is associative, i.e. if $\alpha_{1},\alpha_{2},\alpha_{3}$
are composable shapes then $\alpha_{2},\alpha_{3}$ are composable,
$\alpha_{1},(\alpha_{2}\circ\alpha_{3})$ are composable, and
$\alpha_{1}\circ(\alpha_{2}\circ\alpha_{3})=(\alpha_{1}\circ\alpha_{2})\circ\alpha_{3}$

###  7.7 Decomposition of Shapes into Left, Middle, and Right parts

In this subsection, we describe how shapes can be decomposed into left,
middle, and right parts based on the leftmost and rightmost _minimum vertex
separators_ , which is a crucial idea for our analysis.

######  Definition 7.48 (Paths).

A _path_ in a shape $\alpha$ is a sequence of vertices $v_{1},\ldots,v_{t}$
such that $v_{i},v_{i+1}$ are in some edge/hyperedge together. A pair of paths
is vertex-disjoint if the corresponding sequences of vertices are disjoint.

######  Definition 7.49 (Vertex separators).

Let $\alpha$ be a shape and let $U$ and $V$ be sets of vertices in $\alpha$.
We say that a set of vertices $S\subseteq V(\alpha)$ is a _vertex separator_
of $U$ and $V$ if every path in $\alpha$ from $U$ to $V$ contains at least one
vertex in $S$. Note that any vertex separator $S$ of $U$ and $V$ must contain
all of the vertices in $U\cap V$.

As a special case, we say that $S$ is a vertex separator of $\alpha$ if $S$ is
a vertex separator of $U_{\alpha}$ and $V_{\alpha}$

We define the weight of a set of vertices $S\subseteq V(\alpha)$ in the same
way that weight is defined for index shapes.

######  Definition 7.50 (Simplified Weight).

When there is only one type of index, the weight of a set of vertices
$S\subseteq V(\alpha)$ is simply $|S|$.

######  Definition 7.51 (General Weight*).

In general, given a set of vertices $S\subseteq V(\alpha)$, writing
$S=\cup_{t}{S_{t}}$ where $S_{t}$ is the set of vertices of type $t$ in $S$,
we define the weight of $S$ to be $w(S)=\sum_{t}{|S_{t}|log_{n}(n_{t})}$

######  Remark 7.52 (*).

Again, if necessary, we add an infinitesimal perturbation to
$n_{1},n_{2},\ldots,n_{t_{max}}$ so that if two separators $S$ and
$S^{\prime}$ have the same weight then $S$ and $S^{\prime}$ have the same
number of each type of vertex.

######  Definition 7.53 (Leftmost and rightmost minimum vertex separators).

The _leftmost_ minimum vertex separator is the vertex separator $S$ of minimum
weight such that for every other minimum-weight vertex separator $S^{\prime}$,
$S$ is a separator of $U_{\alpha}$ and $S^{\prime}$. The _rightmost_ minimum
vertex separator is the vertex separator $T$ of minimum weight such that for
every other minimum-weight vertex separator $T^{\prime}$, $T$ is a separator
of $T^{\prime}$ and $V_{\alpha}$

The work [BHK+16] showed that under our simplifying assumptions, leftmost and
rightmost minimum vertex separators are well defined. For a general proof that
leftmost and rightmost minimum vertex separators are well defined, see
Appendix A.

We now have the following crucial idea. Every shape $\alpha$ can be decomposed
into the composition of three composable shapes
$\sigma,\tau,{\sigma^{\prime}}^{T}$ based on the leftmost and rightmost
minimum vertex separators $S,T$ of $\alpha$ together with orderings of $S$ and
$T$.

######  Definition 7.54 (Simplified Separators With Orderings).

Under our simplifying assumptions, given a set of vertices $S\subseteq
V(\alpha)$ and an ordering $O_{S}=s_{1},\ldots,s_{|S|}$ of the vertices of
$S$, we define the index shape $(S,O_{S})$ to be
$(S,O_{S})=(s_{1},\ldots,s_{|S|})$.

######  Definition 7.55 (General Separators With Orderings*).

In the general case, we need to give an ordering for each type of vertex. Let
$S\subseteq V(\alpha)$ be a subset of the vertices of $\alpha$ and write
$S=\cup_{t}{S_{t}}$ where $S_{t}$ is the set of vertices in $S$ of type $t$.
Given $O_{S}=\\{O_{t}\\}$ where $O_{t}=s_{t1},\ldots,s_{t|S_{t}|}$ is an
ordering of the vertices of $S_{t}$, we define the index shape piece
$(S_{t},O_{t})$ to be $(S_{t},O_{t})=((s_{t1},\ldots,s_{t|S_{t}|}),t,1)$ and
we define the index shape $(S,O_{S})$ to be $(S,O_{S})=\\{(S_{t},O_{t})\\}$.

######  Proposition 7.56.

The number of possible orderings $O$ for $S$ is equal to $|Aut((S,O_{S}))|$

######  Definition 7.57 (Shape transposes).

Given a shape $\alpha$, we define $\alpha^{T}$ to be the shape $\alpha$ with
$U_{\alpha}$ and $V_{\alpha}$ swapped i.e. $U_{\sigma^{T}}=V_{\sigma}$ and
$V_{\sigma^{T}}=U_{\sigma}$.

######  Definition 7.58 (Left, middle, and right parts).

Let $\alpha$ be a shape. Let $S$ and $T$ be the leftmost and rightmost minimal
vertex separators of $\alpha$ together with orderings $O_{S},O_{T}$ of $S$ and
$T$.

  * -

We define the _left part_ $\sigma_{\alpha}$ of $\alpha$ to be the shape such
that

    1. 1.

$H_{\sigma_{\alpha}}$ is the induced subgraph of $H_{\alpha}$ on all of the
vertices of $\alpha$ reachable from $U_{\alpha}$ without passing through $S$
(note that $H_{\sigma_{\alpha}}$ includes the vertices of $S$) except that we
remove any edges/hyperedges which are contained entirely within $S$.

    2. 2.

$U_{\sigma_{\alpha}}=U_{\alpha}$ and $V_{\sigma_{\alpha}}=(S,O_{S})$

  * -

We define the _right part_ ${\sigma^{\prime}}^{T}_{\alpha}$ of $\alpha$ to be
the shape such that

    1. 1.

$H_{{\sigma^{\prime}}^{T}_{\alpha}}$ is the induced subgraph of $H_{\alpha}$
on all of the vertices of $\alpha$ reachable from $V_{\alpha}$ without passing
through $T$ (note that $H_{{\sigma^{\prime}}^{T}_{\alpha}}$ includes the
vertices of $T$) except that we remove any edges/hyperedges which are
contained entirely within $T$.

    2. 2.

$V_{{\sigma^{\prime}}^{T}_{\alpha}}=V_{\alpha}$ and
$U_{{\sigma^{\prime}}^{T}_{\alpha}}=(T,O_{T})$

  * -

We define the _middle part_ $\tau_{\alpha}$ of $\alpha$ to be the shape such
that

    1. 1.

$H_{\tau_{\alpha}}$ is the induced subgraph of $H_{\alpha}$ on all of the
vertices of $\alpha$ which are not reachable from $U_{\alpha}$ and
$V_{\alpha}$ without touching $S$ and $T$ (note that $H_{\tau_{\alpha}}$
includes the vertices of $S$ and $T$). $H_{\tau_{\alpha}}$ also includes the
hyperedges entirely within $S$ and the hyperedges entirely within $T$.

    2. 2.

$U_{\tau_{\alpha}}=(S,O_{S})$ and $V_{\tau_{\alpha}}=(T,O_{T})$

.

######  Proposition 7.59.

If $\sigma,\tau,{\sigma^{\prime}}^{T}$ are the left, middle, and rights parts
for $\alpha$ for given orderings $O_{S},O_{T}$ of $S$ and $T$ then
$\alpha=\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$.

######  Remark 7.60.

One may ask which ordering(s) we should take of $S$ and $T$. The answer is
that we will take all of the possible orderings of $S$ and $T$ simultaneously,
giving equal weight to each.

Based on this decomposition and the following claim, we make the following
definitions for what it means for a shape to be a left, middle, or right part.

######  Claim 7.61 (Proved in Section 6.1 in [BHK+16]).

222The proof in [BHK+16] only explicitly treats the case when the shapes
$\alpha$ are graphs, but the proof easily generalizes to the case when the
$\alpha$ are hypergraphs.

  * -

Every shape $\sigma$ which is the left part of some other shape $\alpha$ has
that $V_{\sigma}$ is its left-most and right-most minimum-weight separator.

  * -

Every shape ${\sigma}^{T}$ which is the right part of some other shape
$\alpha$ has that $U_{{\sigma}^{T}}$ is its left-most and right-most minimum-
weight separator.

  * -

Every shape $\tau$ which is the middle part of some other shape $\alpha$ has
$U_{\tau}$ as its left-most minimum size separator and $V_{\tau}$ as its
right-most minimum-weight separator.

######  Definition 7.62.

  1. 1.

We say that a shape $\sigma$ is a left shape if $\sigma$ is a proper shape,
$V_{\sigma}$ is the left-most and right-most minimum-weight separator of
$\sigma$, every vertex in $V(\sigma)\setminus V_{\sigma}$ is reachable from
$U_{\sigma}$ without touching $V_{\sigma}$, and $\sigma$ has no hyperedges
entirely within $V_{\sigma}$.

  2. 2.

We say that a shape $\tau$ is a proper middle shape if $\tau$ is a proper
shape, $U_{\tau}$ is the left-most minimum-weight separator of $\tau$, and
$V_{\tau}$ is the right most minimum-weight separator of $\tau$. In the
analysis, we will also need to consider improper middle shapes $\tau$ which
may not be proper shapes and which may have smaller separators between
$U_{\tau}$ and $V_{\tau}$.

  3. 3.

We say that a shape ${\sigma}^{T}$ is a right shape if ${\sigma}^{T}$ is a
proper shape, $U_{{\sigma}^{T}}$ is the left-most and right-most minimum-
weight separator of ${\sigma}^{T}$, every vertex in $V({\sigma}^{T})\setminus
U_{{\sigma}^{T}}$ is reachable from $V_{{\sigma}^{T}}$ without touching
$U_{{\sigma}^{T}}$, and ${\sigma}^{T}$ has no hyperedges entirely within
$U_{{\sigma}^{T}}$.

######  Proposition 7.63.

For all shapes $\sigma$, $\sigma$ is a left shape if and only if $\sigma^{T}$
is a right shape.

######  Remark 7.64.

As the reader has likely guessed, throughout this section we use $\sigma$ to
denote left parts and $\tau$ to denote middle parts. Instead of having a
separate letter for right parts, we express right parts as the transpose of a
left part.

###  7.8 Coefficient matrices

We will have that $\Lambda=\sum_{\alpha}{\lambda_{\alpha}M_{\alpha}}$. To
analyze $\Lambda$, it is extremely useful to express these coefficients in
terms of matrices. To do this, we will need a few more definitions. We start
by defining the sets of index shapes that can appear when analyzing $\Lambda$.

######  Definition 7.65.

Given a moment matrix $\Lambda$, we define the following sets of index shapes.

  1. 1.

We define $\mathcal{I}(\Lambda)=\\{U:\exists\text{ matrix index }A:A\text{ is
a row index of }\Lambda,A\text{ has shape }U\\}$ to be the set of index shapes
which describe row and column indices of $\Lambda$.

  2. 2.

We define $w_{max}$ to be $w_{max}=\max{\\{w(U):U\in\mathcal{I}(\Lambda)\\}}$.

  3. 3.

With our simplifying assumptions, we define $\mathcal{I}_{mid}$ to be
$\mathcal{I}_{mid}=\\{U:|U|\leq w_{max}\\}$

  4. 3*.

In general, we define $\mathcal{I}_{mid}$ to be
$\mathcal{I}_{mid}=\\{U:w(U)\leq w_{max},\forall U_{i}\in U,p_{i}=1\\}$

We also need to define the sets of shapes which can appear when analyzing
$\Lambda$.

######  Definition 7.66 (Truncation Parameters).

Given a moment matrix $\Lambda=\sum_{\alpha}{\lambda_{\alpha}M_{\alpha}}$, we
define $D_{V},D_{E}$ to be the smallest natural numbers such that for all
shapes $\alpha$ such that $\lambda_{\alpha}\neq 0$, decomposing $\alpha$ as
$\alpha=\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$,

  1. 1.

$|V(\sigma)|\leq D_{V}$, $|V(\tau)|\leq D_{V}$, and $|V(\sigma^{\prime})|\leq
D_{V}$.

  2. 2.*

For all edges $e\in E(\sigma)\cup E(\tau)\cup E(\sigma^{\prime})$, $l_{e}\leq
D_{E}$.

######  Remark 7.67.

Under our simplifying assumptions, all edges have label $1$ so we will take
$D_{E}=1$ and ignore conditions involving $D_{E}$.

######  Definition 7.68.

Given a moment matrix $\Lambda$, we define the following sets of shapes:

  1. 1.

$\mathcal{L}=\\{\sigma:\sigma\text{ is a left
shape},U_{\sigma}\in\mathcal{I}(\Lambda),V_{\sigma}\in\mathcal{I}_{mid},|V(\sigma)|\leq
D_{V},\forall e\in E(\sigma),l_{e}\leq D_{E}\\}$

  2. 2.

Given $V\in\mathcal{I}_{mid}$, we define
$\mathcal{L}_{V}=\\{\sigma\in\mathcal{L}:V_{\sigma}\equiv V\\}$

  3. 3.

Given $U\in\mathcal{I}_{mid}$, we define $\mathcal{M}_{U}=\\{\tau:\tau\text{
is a non-trivial proper middle shape},U_{\tau}\equiv V_{\tau}\equiv
U,|V(\tau)|\leq D_{V},\forall e\in E(\tau),l_{e}\leq D_{E}\\}$

######  Definition 7.69.

Given a moment matrix $\Lambda$, we define a $\Lambda$-coefficient matrix
(which we call a coefficient matrix for brevity) to be a matrix whose rows and
columns are indexed by left shapes $\sigma,\sigma^{\prime}\in\mathcal{L}$.

We say that a coefficient matrix $H$ is SOS-symmetric if
$H(\sigma,\sigma^{\prime})$ is invariant under permuting the vertices of
$U_{\sigma}$ and permuting the vertices of $U_{\sigma^{\prime}}$ (*more
precisely, for the general case we permute the vertices within each index
shape piece of $U_{\sigma}$ and permute the vertices within each index shape
piece of $U_{\sigma^{\prime}}$).

######  Definition 7.70.

Given a shape $\tau$, we say that a coefficient matrix $H$ is a
$\tau$-coefficient matrix if $H(\sigma,\sigma^{\prime})=0$ whenever
$V_{\sigma}\not\equiv U_{\tau}$ or $V_{\tau}\not\equiv
U_{{\sigma^{\prime}}^{T}}$.

######  Definition 7.71.

Given an index shape $U$, we define $Id_{U}$ to be the shape with
$U_{Id_{U}}=V_{Id_{U}}=U$, no other vertices, and no edges.

Given a shape $\tau$ and a $\tau$-coefficient matrix $H$, we create two
different matrix-valued functions, $M^{fact}_{\tau}(H)$ and
$M^{orth}_{\tau}(H)$. As we will see, we can express $\Lambda$ in terms of
$M^{orth}$ but to show PSDness we will need to shift to $M^{fact}$. We analyze
the difference betweem $M^{fact}$ and $M^{orth}$ in subsections 8.2, 8.3, and
8.4.

######  Definition 7.72.

Given a shape $\tau$ and a $\tau$-coefficient matrix $H$, define

$M^{fact}_{\tau}(H)=\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})M_{\sigma}M_{\tau}M_{\sigma^{\prime}}^{T}}$

######  Proposition 7.73.

For all $A$ and $B$ with shapes in $\mathcal{I}(\Lambda)$,

$\displaystyle\left(M^{fact}_{\tau}(H)\right)(A,B)=$
$\displaystyle\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})\sum_{A^{\prime},B^{\prime}}{\sum_{R_{1}\in\mathcal{R}(\sigma,A,A^{\prime}),R_{2}\in\mathcal{R}(\tau,A^{\prime},B^{\prime}),\atop
R_{3}\in\mathcal{R}({\sigma^{\prime}}^{T},B^{\prime},B)}M_{R_{1}}(A,A^{\prime})M_{R_{2}}(A^{\prime},B^{\prime})M_{R_{3}}(B^{\prime},B)}}$

If $R_{1},R_{2},R_{3}$ are properly composable then $R=R_{1}\circ R_{2}\circ
R_{3}$ has the expected shape $\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$.
Otherwise, $R_{1}\circ R_{2}\circ R_{3}$ will have a different shape. We
define $M^{orth}_{\tau}(H)$ to be the same sum as $M^{fact}_{\tau}(H)$ except
that it is restricted to properly composable ribbons $R_{1},R_{2},R_{3}$.

######  Definition 7.74.

We define $M^{orth}_{\tau}(H)$ so that for all $A$ and $B$ with shapes in
$\mathcal{I}(\Lambda)$,

$\displaystyle\left(M^{orth}_{\tau}(H)\right)(A,B)$
$\displaystyle=\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})\sum_{A^{\prime},B^{\prime}}{\sum_{R_{1}\in\mathcal{R}(\sigma,A,A^{\prime}),R_{2}\in\mathcal{R}(\tau,A^{\prime},B^{\prime}),\atop{R_{3}\in\mathcal{R}({\sigma^{\prime}}^{T},B^{\prime},B),R_{1},R_{2},R_{3}\text{
are properly
composable}}}M_{R_{1}}(A,A^{\prime})M_{R_{2}}(A^{\prime},B^{\prime})M_{R_{3}}(B^{\prime},B)}}$
$\displaystyle=\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})\sum_{A^{\prime},B^{\prime}}{\sum_{R_{1}\in\mathcal{R}(\sigma,A,A^{\prime}),R_{2}\in\mathcal{R}(\tau,A^{\prime},B^{\prime}),\atop{R_{3}\in\mathcal{R}({\sigma^{\prime}}^{T},B^{\prime},B),R_{1},R_{2},R_{3}\text{
are properly composable}}}M_{R_{1}\circ R_{2}\circ R_{3}}(A,B)}}$

It would be nice if we had that
$M^{orth}_{\tau}(H)=\sum_{\sigma\in\mathcal{R}_{U_{\tau}},\sigma^{\prime}\in\mathcal{R}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}}$.
However, this is not quite correct because there is an additional term related
to automorphism groups.

######  Definition 7.75.

Given a shape $\alpha$, define $Aut(\alpha)$ to be the set of mappings from
$\alpha$ to itself which keep $U_{\alpha}$ and $V_{\alpha}$ fixed.

######  Definition 7.76.

Given composable shapes $\sigma,\tau,{\sigma^{\prime}}^{T}$, we define

$Decomp(\sigma,\tau,\sigma^{\prime})=Aut(\sigma\circ\tau\circ{\sigma^{\prime}})/(Aut(\sigma)\times
Aut(\tau)\times Aut({\sigma^{\prime}}^{T}))$

######  Remark 7.77.

Each element $\pi\in Decomp(\sigma,\tau,\sigma^{\prime})$ decomposes
$\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$ into $\sigma$, $\tau$, and
${\sigma^{\prime}}^{T}$ by specifying copies $\pi(\sigma)$, $\pi(\tau)$,
$\pi({\sigma^{\prime}}^{T})$ of $\sigma$, $\tau$, and ${\sigma^{\prime}}^{T}$
such that
$\pi(\sigma)\circ\pi(\tau)\circ\pi({\sigma^{\prime}}^{T})=\pi(\sigma\circ\tau\circ{\sigma^{\prime}}^{T})=\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$.
Thus, $|Decomp(\sigma,\tau,\sigma^{\prime})|$ is the number of ways to
decompose $\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$ into $\sigma$, $\tau$,
and ${\sigma^{\prime}}^{T}$.

######  Lemma 7.78.

$M^{orth}_{\tau}(H)=\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})|Decomp(\sigma,\tau,{\sigma^{\prime}}^{T})|M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}}$

###### Proof sketch.

Observe that there is a bijection between ribbons $R$ with shape
$\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$ together with an element $\pi\in
Decomp(\sigma,\tau,\sigma^{\prime})$ and triples of ribbons
$(R_{1},R_{2},R_{3})$ such that

  1. 1.

$R_{1},R_{2},R_{3}$ have shapes $\sigma$, $\tau$, and ${\sigma^{\prime}}^{T}$,
respectively.

  2. 2.

$V(R_{1})\cap V(R_{2})=A_{R_{2}}=B_{R_{1}}$, $V(R_{2})\cap
V(R_{3})=A_{R_{3}}=B_{R_{2}}$, and $V(R_{1})\cap V(R_{3})=A_{R_{2}}\cap
B_{R_{2}}$

To see this, note that given such ribbons $R_{1},R_{2},R_{3}$, the ribbon
$R=R_{1}\circ R_{2}\circ R_{3}$ has shape
$\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$ and the ribbons
$R_{1},R_{2},R_{3}$ specify a decomposition of
$\sigma\circ\tau\circ{\sigma^{\prime}}^{T}$ into $\sigma$, $\tau$, and
${\sigma^{\prime}}^{T}$.

Conversely, given $R$ and an element $\pi\in
Decomp(\sigma,\tau,\sigma^{\prime})$, $\pi$ specifies how to decompose $R$
into ribbons $R_{1},R_{2},R_{3}$ of shapes $\sigma$, $\tau$, and
${\sigma^{\prime}}^{T}$.

For a more rigorous proof, see Appendix B.

######  Remark 7.79.

As this lemma shows, we have to be very careful about symmetry groups in our
analysis. For accuracy, it is safest to check that the coefficients for each
individual ribbon match.

Given a matrix-valued function $\Lambda$, we can associate coefficient
matrices to $\Lambda$ as follows:

######  Definition 7.80.

Given a matrix-valued function $\Lambda=\sum_{\alpha:\alpha\text{ is
proper}}{\lambda_{\alpha}M_{\alpha}}$,

  1. 1.

For each index shape $U\in\mathcal{I}_{mid}$ and every
$\sigma,\sigma^{\prime}\in\mathcal{L}_{U}$, we take
$H_{Id_{U}}(\sigma,\sigma^{\prime})=\frac{1}{|Aut(U)|}\lambda_{\sigma\circ{\sigma^{\prime}}^{T}}$

  2. 2.

For each $U\in\mathcal{I}_{mid}$, $\tau\in\mathcal{M}_{U}$ and
$\sigma,\sigma^{\prime}\in\mathcal{L}_{U}$, we take
$H_{\tau}(\sigma,\sigma^{\prime})=\frac{1}{|Aut(U_{\tau})|\cdot|Aut(V_{\tau})|}\lambda_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}$

######  Lemma 7.81.

$\Lambda=\sum_{U\in\mathcal{I}_{mid}}{M^{orth}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{orth}_{\tau}(H_{\tau})}}$

###### Proof.

We check that the coefficients for each individual ribbon $R$ match. There are
two cases to consider.

If $R$ has shape $\alpha$ where $\alpha$ has a unique minimum vertex separator
$S$, then there is a bijection between orderings $O_{S}$ for $S$ and pairs of
ribbons $R_{1},R_{2}$ such that $R_{1}\circ R_{2}=R$ and the shapes
$\sigma,{\sigma^{\prime}}^{T}$ of $R_{1},R_{2}$ are left and right shapes
respectively.

To see this, observe that when we concatenate $R_{1}$ and $R_{2}$, this
assigns the matrix index $B_{R_{1}}=A_{R_{2}}$ to $S$, which is equivalent to
specifying an ordering $O_{S}$ for $S$. Conversely, given an ordering $O_{S}$
for $S$, we take $R_{1}$ to be the part of $R$ between $A_{R}$ and $(S,O_{S})$
and we take $R_{2}$ to be the part of $R$ between $(S,O_{S})$ and $B_{R}$.

From this bijection, it follows that the coefficient of $M_{R}$ is
$\lambda_{\alpha}$ on both sides of the equation.

Similarly, if $R$ has shape $\alpha$ where $\alpha$ does not have a unique
minimal vertex separator, then there is a bijection between orderings
$O_{S},O_{T}$ for the leftmost and rightmost minimum vertex separators $S,T$
of $R$ and triples of ribbons $R_{1},R_{2},R_{3}$ such that $R_{1}\circ
R_{2}\circ R_{3}=R$ and the shapes $\sigma,\tau,{\sigma^{\prime}}^{T}$ of
$R_{1},R_{2},R_{3}$ are left, proper middle, and right shapes respectively.

To see this, observe that when we concatenate $R_{1}$, $R_{2}$, and $R_{3}$,
this assigns the matrix index $B_{R_{1}}=A_{R_{2}}$ to $S$ and assigns the
matrix index $B_{R_{2}}=A_{R_{3}}$ to $T$, which is equivalent to specifying
orderings $O_{S},O_{T}$ for $S,T$. Conversely, given orderings $O_{S},O_{T}$
for $S,T$, we take $R_{1}$ to be the part of $R$ between $A_{R}$ and
$(S,O_{S})$, we take $R_{2}$ to be the part of $R$ between $(S,O_{S})$ and
$(T,O_{T})$, and we take $R_{2}$ to be the part of $R$ between $(T,O_{T})$ and
$B_{R}$.

From this bijection, it again follows that the coefficient of $M_{R}$ is
$\lambda_{\alpha}$ on both sides of the equation.

###  7.9 The $-\gamma,-\gamma$ operation and qualitative theorem statement

In the intersection term anaylsis (see subsections 8.2, 8.3, and 8.4), we will
need to further decompose left shapes $\sigma$ as
$\sigma=\sigma_{2}\circ\gamma$ where $\sigma_{2}$ and $\gamma$ are themselves
left shapes. Accordingly, we make the following definitions

######  Definition 7.82.

Given a moment matrix $\Lambda$, we define the following sets of left shapes:

  1. 1.

$\Gamma=\\{\gamma:\gamma\text{ is a non-trivial left
shape},U_{\gamma},V_{\gamma}\in\mathcal{I}_{mid},|V(\gamma)|\leq D_{V},\forall
e\in E(\gamma),l_{e}\leq D_{E}\\}$

  2. 2.

Given $U,V\in\mathcal{I}_{mid}$ such that $w(U)>w(V)$, define
$\Gamma_{U,V}=\\{\gamma\in\Gamma:U_{\gamma}\equiv U,V_{\gamma}\equiv V\\}$.

  3. 3.

Given $U\in\mathcal{I}_{mid}$, define
$\Gamma_{U,*}=\\{\gamma\in\Gamma:U_{\gamma}\equiv U\\}$

  4. 4.

Given $V\in\mathcal{I}_{mid}$, define
$\Gamma_{*,V}=\\{\gamma\in\Gamma:V_{\gamma}\equiv V\\}$

######  Remark 7.83.

Under our simplifying assumptions, $\Gamma$ is the same as $\mathcal{L}$
except that $\Gamma$ excludes the trivial shapes. In general, while
$\mathcal{L}$ requires that $U_{\sigma}\in\mathcal{I}(\Lambda)$, $\Gamma$
requires that $U_{\gamma}\in\mathcal{I}_{mid}$. Note that
$\mathcal{I}(\Lambda)$ and $\mathcal{I}_{mid}$ may be incomparable because

  1. 1.

There may be index shapes $U\in\mathcal{I}_{mid}$ such that no matrix index of
$\Lambda$ has shape $U$.

  2. 2.

All index shape pieces $U_{i}$ for index shapes $U\in\mathcal{I}_{mid}$ must
have $p_{i}=1$ while this is not the case for $\mathcal{I}(\Lambda)$.

We now state our theorem qualitatively after giving one more definition.

######  Definition 7.84.

Given a shape $\tau$, left shapes $\gamma\in{\Gamma}_{*,U_{\tau}}$ and
$\gamma^{\prime}\in{\Gamma}_{*,V_{\tau}}$, and a $\tau$-coefficient matrix
$H$, define $H^{-\gamma,\gamma^{\prime}}$ to be the
$(\gamma\circ\tau\circ{\gamma^{\prime}}^{T})$-coefficient matrix with entries

  1. 1.

$H^{-\gamma,\gamma^{\prime}}(\sigma,\sigma^{\prime})=H(\sigma\circ\gamma,\sigma^{\prime}\circ\gamma^{\prime})$
if $|V(\sigma\circ\gamma)|\leq D_{V}$ and
$|V(\sigma^{\prime}\circ\gamma^{\prime})|\leq D_{V}$.

  2. 2.

$H^{-\gamma,\gamma^{\prime}}(\sigma,\sigma^{\prime})=0$ if
$|V(\sigma\circ\gamma)|>D_{V}$ or
$|V(\sigma^{\prime}\circ\gamma^{\prime})|>D_{V}$.

######  Remark 7.85.

For the theorem, we will only need the case when $\gamma^{\prime}=\gamma$

Our qualitative theorem statement is as follows:

######  Theorem 7.86.

Let
$\Lambda=\sum_{U\in\mathcal{I}_{mid}}{M^{orth}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{orth}_{\tau}(H_{\tau})}}$
be an SOS-symmetric matrix valued function.

There exist functions $f(\tau)$ and $f(\gamma)$ depending on $n$ and other
parameters such that if the following conditions hold:

  1. 1.

For all $U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$

  2. 2.

For all $U\in\mathcal{I}_{mid}$ and all $\tau\in\mathcal{M}_{U}$,

$\left[{\begin{array}[]{cc}H_{Id_{U}}&f(\tau)H_{\tau}\\\
f(\tau)H^{T}_{\tau}&H_{Id_{U}}\end{array}}\right]\succeq 0$

  3. 3.

For all $U,V\in\mathcal{I}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$, $H^{-\gamma,\gamma}_{Id_{V}}\preceq
f(\gamma)H_{Id_{U}}$

then with high probability $\Lambda\succeq 0$

######  Remark 7.87.

Roughly speaking, conditions 1 and 2 give us an approximate PSD decomposition
for the moment matrix $M$. Condition 3 comes from the intersection term
analysis, which is the most technically intensive part of the proof.

###  7.10 Quantitative theorem statement

To state our theorem quantitatively, we will need a few more things. First,
the conditions of the theorem will involve functions $B_{norm}(\alpha)$,
$B(\gamma)$, $N(\gamma)$, and $c(\alpha)$. Roughly speaking, these functions
will be used as follows in the analysis:

  1. 1.

$B_{norm}(\alpha)$ will bound the norms of the matrices $M_{\alpha}$

  2. 2.

$B(\gamma)$ and $N(\gamma)$ will help us bound the intersection terms (see
Section 8.4).

  3. 3.

$c(\alpha)$ will help us sum over the possible $\gamma$ and $\tau$.

Second, for technical reasons it turns out that comparing
$H^{-\gamma,\gamma}_{Id_{V_{\gamma}}}$ to $H_{Id_{U_{\gamma}}}$ doesn’t quite
work. Instead, we compare $H^{-\gamma,\gamma}_{Id_{V_{\gamma}}}$ to a matrix
$H^{\prime}_{\gamma}$ of our choice where $H^{\prime}_{\gamma}$ is very close
to $H_{Id_{U_{\gamma}}}$ ($H^{\prime}_{\gamma}$ will be the same as
$H_{Id_{U_{\gamma}}}$ up to truncation error).

######  Definition 7.88.

Given a function $B_{norm}(\alpha)$, we define the distance
$d_{\tau}(H_{\tau},H^{\prime}_{\tau})$ between two $\tau$-coefficient matrices
$H_{\tau}$ and $H^{\prime}_{\tau}$ to be

$d_{\tau}(H_{\tau},H^{\prime}_{\tau})=\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{|H^{\prime}_{\tau}(\sigma,\sigma^{\prime})-H_{\tau}(\sigma,\sigma^{\prime})|B_{norm}(\sigma)B_{norm}(\tau)B_{norm}(\sigma^{\prime})}$

Third, we need an SOS-symmetric analogue of the identity matrix.

######  Definition 7.89.

We define $Id_{Sym}$ to be the matrix such that

  1. 1.

The rows and columns of $Id_{Sym}$ are indexed by the matrix indices $A,B$
whose index shape is in $\mathcal{I}(\Lambda)$.

  2. 2.

$Id_{Sym}(A,B)=1$ if $p_{A}=p_{B}$ and $Id_{Sym}(A,B)=0$ if $p_{A}\neq p_{B}$.

######  Proposition 7.90.

If $M$ has SOS-symmetry and the rows and columns of $Id_{Sym}$ are indexed by
matrix indices $A,B$ whose index shape is in $\mathcal{I}(\Lambda)$ then
$M\preceq\left\lVert M\right\rVert Id_{Sym}$

######  Corollary 7.91.

For all $\tau$ and all SOS-symmetric $\tau$-coefficient matrices $H_{\tau}$
and $H^{\prime}_{\tau}$,

$M^{fact}_{\tau}(H^{\prime}_{\tau})+M^{fact}_{{\tau}^{T}}(H^{\prime}_{{\tau}^{T}})-M^{fact}_{\tau}(H_{\tau})-M^{fact}_{{\tau}^{T}}(H_{{\tau}^{T}})\preceq
2d_{\tau}(H_{\tau},H^{\prime}_{\tau})Id_{Sym}$

Note that if $\tau$, $H_{\tau}$ and $H^{\prime}_{\tau}$ are all symmetric then

$M^{fact}_{\tau}(H^{\prime}_{\tau})-M^{fact}_{\tau}(H_{\tau})\preceq
d_{\tau}(H_{\tau},H^{\prime}_{\tau})Id_{Sym}$

Finally, we need a few more definitions about shapes $\alpha$.

######  Definition 7.92 ($\mathcal{M}^{\prime}$).

We define $\mathcal{M}^{\prime}$ to be the set of all shapes $\alpha$ such
that

  1. 1.

$|V(\alpha)|\leq 3D_{V}$

  2. 2.*

$\forall e\in E(\alpha),l_{e}\leq D_{E}$

  3. 3.*

All edges $e\in E(\alpha)$ have multiplicity at most $3D_{V}$.

######  Definition 7.93 ($S_{\alpha}$).

Given a shape $\alpha$, define $S_{\alpha}$ to be the leftmost minimum vertex
separator of $\alpha$

######  Definition 7.94 ($I_{\alpha}$).

Given a shape $\alpha$, define $I_{\alpha}$ to be the set of vertices in
$V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})$ which are isolated.

We can now state our main theorem.

######  Theorem 7.95.

Given the moment matrix
$\Lambda=\sum_{U\in\mathcal{I}_{mid}}{M^{orth}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{orth}_{\tau}(H_{\tau})}}$,
for all $\varepsilon>0$, if we take

  1. 1.

$q=3\left\lceil{{D_{V}}ln(n)+\frac{ln(\frac{1}{\varepsilon})}{3}+{D_{V}}ln(5)+3{D^{2}_{V}}ln(2)}\right\rceil$

  2. 2.

$B_{vertex}=6{D_{V}}\sqrt[4]{2eq}$

  3. 3.

$B_{norm}(\alpha)={B_{vertex}^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}$

  4. 4.

$B(\gamma)=B_{vertex}^{|V(\gamma)\setminus U_{\gamma}|+|V(\gamma)\setminus
V_{\gamma}|}n^{\frac{w(V(\gamma)\setminus U_{\gamma})}{2}}$

  5. 5.

$N(\gamma)=(3D_{V})^{2|V(\gamma)\setminus V_{\gamma}|+|V(\gamma)\setminus
U_{\gamma}|}$

  6. 6.

$c(\alpha)=100(3D_{V})^{|U_{\alpha}\setminus V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+2|E(\alpha)|}2^{|V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})|}$

and we have SOS-symmetric coefficient matrices
$\\{H^{\prime}_{\gamma}:\gamma\in\Gamma\\}$ such that the following conditions
hold:

  1. 1.

For all $U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$

  2. 2.

For all $U\in\mathcal{I}_{mid}$ and $\tau\in\mathcal{M}_{U}$,

$\left[{\begin{array}[]{cc}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{array}}\right]\succeq
0$

  3. 3.

For all $U,V\in\mathcal{I}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}{N(\gamma)}^{2}{B(\gamma)^{2}}H^{-\gamma,\gamma}_{Id_{V}}\preceq
H^{\prime}_{\gamma}$

then with probability at least $1-\varepsilon$,

$\Lambda\succeq\frac{1}{2}\left(\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\right)-3\left(\sum_{U\in\mathcal{I}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

If it is also true that whenever $\left\lVert M_{\alpha}\right\rVert\leq
B_{norm}(\alpha)$ for all $\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

then with probability at least $1-\varepsilon$, $\Lambda\succeq 0$.

####  7.10.1 General Main Theorem

Before stating the general main theorem, we need to modify a few definitions
for $\alpha$ and give a few definitions for $\Omega$

######  Definition 7.96 ($S_{\alpha,min}$ and $S_{\alpha,max}$).

Given a shape $\alpha\in\mathcal{M}^{\prime}$, define $S_{\alpha,min}$ to be
the leftmost minimum vertex separator of $\alpha$ if all edges with
multiplicity at least $2$ are deleted and define $S_{\alpha,max}$ to be the
leftmost minimum vertex separator of $\alpha$ if all edges with multiplicity
at least $2$ are present.

######  Definition 7.97 (General $I_{\alpha}$).

Given a shape $\alpha$, define $I_{\alpha}$ to be the set of vertices in
$V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})$ such that all edges incident
with that vertex have multplicity at least $2$.

######  Definition 7.98 ($B_{\Omega}$).

We take $B_{\Omega}(j)$ to be a non-decreasing function such that for all
$j\in\mathbb{N}$, $E_{\Omega}[x^{j}]\leq B_{\Omega}(j)^{j}$

######  Definition 7.99 ($h^{+}_{j}$).

For all $j$, we define $h^{+}_{j}$ to be the polynomial $h_{j}$ where we make
all of the coefficients have positive sign.

######  Lemma 7.100.

If $\Omega=N(0,1)$ then we can take $B_{\Omega}(j)=\sqrt{j}$ and we have that

$h^{+}_{j}(x)\leq\frac{1}{\sqrt{j!}}(x^{2}+j)^{\frac{j}{2}}\leq\left(\frac{e}{j}(x^{2}+j)\right)^{\frac{j}{2}}$

For a proof, see [AMP20, Lemma 8.15].

######  Theorem 7.101.

Given the moment matrix
$\Lambda=\sum_{U\in\mathcal{I}_{mid}}{M^{orth}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{orth}_{\tau}(H_{\tau})}}$,
for all $\varepsilon>0$, if we take

  1. 1.

$q=\left\lceil{3{D_{V}}ln(n)+ln(\frac{1}{\varepsilon})+{(3D_{V})^{k}}ln(D_{E}+1)+3{D_{V}}ln(5)}\right\rceil$

  2. 2.

$B_{vertex}=6q{D_{V}}$

  3. 3.

$B_{edge}(e)=2h^{+}_{l_{e}}(B_{\Omega}(6{D_{V}}D_{E}))\max_{j\in[0,3{D_{V}}D_{E}]}{\left\\{\left(h^{+}_{j}(B_{\Omega}(2qj))\right)^{\frac{l_{e}}{\max{\\{j,l_{e}\\}}}}\right\\}}$

As a special case, if $\Omega=N(0,1)$ then we can take
$B_{edge}(e)=\left(400{D^{2}_{V}}{D^{2}_{E}}q\right)^{l_{e}}$

  4. 4.

$B_{norm}(\alpha)=2e{B_{vertex}^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus V_{\alpha}|}}\left(\prod_{e\in
E(\alpha)}{B_{edge}(e)}\right)n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha,min})}{2}}$

  5. 5.

$B(\gamma)=B_{vertex}^{|V(\gamma)\setminus U_{\gamma}|+|V(\gamma)\setminus
V_{\gamma}|}\left(\prod_{e\in
E(\gamma)}{B_{edge}(e)}\right)n^{\frac{w(V(\gamma)\setminus U_{\gamma})}{2}}$

  6. 6.

$N(\gamma)=(3D_{V})^{2|V(\gamma)\setminus V_{\gamma}|+|V(\gamma)\setminus
U_{\gamma}|}$

  7. 7.

$c(\alpha)=100(3{t_{max}}D_{V})^{|U_{\alpha}\setminus
V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+k|E(\alpha)|}(2t_{max})^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}$

and we have SOS-symmetric coefficient matrices
$\\{H^{\prime}_{\gamma}:\gamma\in\Gamma\\}$ such that the following conditions
hold:

  1. 1.

For all $U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$

  2. 2.

For all $U\in\mathcal{I}_{mid}$ and $\tau\in\mathcal{M}_{U}$,

$\left[{\begin{array}[]{cc}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{array}}\right]\succeq
0$

  3. 3.

For all $U,V\in\mathcal{I}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}{N(\gamma)}^{2}{B(\gamma)^{2}}H^{-\gamma,\gamma}_{Id_{V}}\preceq
H^{\prime}_{\gamma}$

then with probability at least $1-\varepsilon$,

$\Lambda\succeq\frac{1}{2}\left(\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\right)-3\left(\sum_{U\in\mathcal{I}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

If it is also true that whenever $\left\lVert M_{\alpha}\right\rVert\leq
B_{norm}(\alpha)$ for all $\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in{\mathcal{I}}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

then with probability at least $1-\varepsilon$, $\Lambda\succeq 0$.

###  7.11 Choosing $H^{\prime}_{\gamma}$ and Truncation Error

A canonical choice for $H^{\prime}_{\gamma}$ is to take

  1. 1.

$H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})=H_{Id_{U}}(\sigma,\sigma^{\prime})$
whenever $|V(\sigma\circ\gamma)|\leq D_{V}$ and
$|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$.

  2. 2.

$H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})=0$ whenever
$|V(\sigma\circ\gamma)|>D_{V}$ or $|V(\sigma^{\prime}\circ\gamma)|>D_{V}$.

With this choice, the truncation error is

$d_{Id_{U_{\gamma}}}(H_{Id_{U_{\gamma}}},H^{\prime}_{\gamma})=\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{U_{\gamma}}:V(\sigma)\leq
D_{V},V(\sigma^{\prime})\leq D_{V},\atop|V(\sigma\circ\gamma)|>D_{V}\text{ or
}|V(\sigma^{\prime}\circ\gamma)|>D_{V}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U_{\gamma}}}(\sigma,\sigma^{\prime})}$

##  8 Proof of the Main Theorem

In this section, we prove the main theorem under the assumption that the
functions $B_{norm}(\alpha)$, $B(\gamma)$, $N(\gamma)$, and $c(\alpha)$ have
certain properties. More precisely, we prove the following theorem.

######  Theorem 8.1.

For all $\varepsilon>0$ and all $\varepsilon^{\prime}\in(0,\frac{1}{20}]$, for
any moment matrix

$\Lambda=\sum_{U\in\mathcal{I}_{mid}}{M^{orth}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{orth}_{\tau}(H_{\tau})}},$

if $B_{norm}(\alpha)$, $B(\gamma)$, $N(\gamma)$, and $c(\alpha)$ are functions
such that

  1. 1.

With probability at least $(1-\varepsilon)$, for all shapes
$\alpha\in\mathcal{M}^{\prime},||M_{\alpha}||\leq B_{norm}(\alpha)$.

  2. 2.

For all $\tau\in\mathcal{M}^{\prime}$, $\gamma\in\Gamma_{*,U_{\tau}}$,
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}$, and all intersection patterns
$P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$B_{norm}(\tau_{P})\leq B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

Note: Intersection patterns and $\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$
will be defined later, see Definitions 8.8 and 8.9.

  3. 3.

For all composable $\gamma_{1},\gamma_{2}$,
$B(\gamma_{1})B(\gamma_{2})=B(\gamma_{1}\circ\gamma_{2})$.

  4. 4.

$\forall
U\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{U,*}}{\frac{1}{|Aut(U)|c(\gamma)}}<\varepsilon^{\prime}$

  5. 5.

$\forall
V\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{*,V}}{\frac{1}{|Aut(U_{\gamma})|c(\gamma)}}<\varepsilon^{\prime}$

  6. 6.

$\forall
U\in\mathcal{I}_{mid},\sum_{\tau\in\mathcal{M}_{U}}{\frac{1}{|Aut(U)|c(\tau)}}<\varepsilon^{\prime}$

  7. 7.

For all $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$, and
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}$
$\displaystyle\leq\frac{N(\gamma)N(\gamma^{\prime})}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-trivial}}}}$

Note: $\Gamma_{\gamma,\gamma^{\prime},j}$ will be defined later, see
Definition 8.18.

and we have SOS-symmetric coefficient matrices
$\\{H^{\prime}_{\gamma}:\gamma\in\Gamma\\}$ such that the following conditions
hold:

  1. 1.

For all $U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$

  2. 2.

For all $U\in\mathcal{I}_{mid}$ and $\tau\in\mathcal{M}_{U}$,

$\left[{\begin{array}[]{cc}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{array}}\right]\succeq
0$

  3. 3.

For all $U,V\in\mathcal{I}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}{N(\gamma)}^{2}{B(\gamma)^{2}}H^{-\gamma,\gamma}_{Id_{V}}\preceq
H^{\prime}_{\gamma}$

then with probability at least $1-\varepsilon$,

$\Lambda\succeq\frac{1}{2}\left(\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\right)-3\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

If it is also true that whenever $||M_{\alpha}||\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

then with probability at least $1-\varepsilon$, $\Lambda\succeq 0$.

Throughout this section, we assume that we have functions $B_{norm}(\alpha)$,
$B(\gamma)$, $N(\gamma)$, and $c(\alpha)$. If
$\forall\alpha\in\mathcal{M}^{\prime},||M_{\alpha}||\leq B_{norm}(\alpha)$
then we say that the norm bounds hold. For the other properties of these
functions, we will either restate these properties in our intermediate results
to highlight where these properties are needed or just state that the
conditions on these functions are satisfied for brevity.

###  8.1 Warm-up: Analysis with no intersection terms

In this subsection, we show how the analysis works if we ignore the difference
between $M^{fact}$ and $M^{orth}$

######  Theorem 8.2.

For all $\varepsilon^{\prime}\in(0,\frac{1}{2}]$, if the norm bounds hold and
the following conditions hold

  1. 1.

For all $U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$

  2. 2.

For all $U\in\mathcal{I}_{mid}$ and all $\tau\in\mathcal{M}_{U}$

$\left[{\begin{array}[]{cc}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{array}}\right]\succeq
0$

  3. 3.

$\forall
U\in\mathcal{I}_{mid},\sum_{\tau\in\mathcal{M}_{U}}{\frac{1}{|Aut(U)|c(\tau)}}\leq\varepsilon^{\prime}$.

then

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{fact}_{\tau}(H_{\tau})}\succeq(1-2\varepsilon^{\prime})\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}}\succeq
0$

###### Proof.

We first show how a single term $M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}$
plus its transpose $M_{\sigma^{\prime}}M_{{\tau}^{T}}M_{{\sigma}^{T}}$ can be
bounded.

######  Lemma 8.3.

If the norm bounds hold then for all $\tau\in\mathcal{M}^{\prime}$ and shapes
$\sigma,\sigma^{\prime}$ such that $\sigma,\tau,{\sigma^{\prime}}^{T}$ are
composable, for all $a,b$ such that $a>0$, $b>0$, and $ab=B_{norm}(\tau)^{2}$,

$M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}+M_{\sigma^{\prime}}M_{{\tau}^{T}}M_{{\sigma}^{T}}\preceq
aM_{\sigma}M_{\sigma^{T}}+bM_{\sigma^{\prime}}M_{{\sigma^{\prime}}^{T}}$

###### Proof.

Observe that

$\displaystyle 0\preceq$
$\displaystyle\left(\sqrt{a}M_{\sigma}-\frac{\sqrt{b}}{B_{norm}(\tau)}M_{{\sigma^{\prime}}}M_{\tau^{T}}\right)\left(\sqrt{a}M_{\sigma}-\frac{\sqrt{b}}{B_{norm}(\tau)}M_{{\sigma^{\prime}}}M_{\tau^{T}}\right)^{T}=$
$\displaystyle\left(\sqrt{a}M_{\sigma}-\frac{\sqrt{b}}{B_{norm}(\tau)}M_{{\sigma^{\prime}}}M_{\tau}\right)\left(\sqrt{a}M_{{\sigma}^{T}}-\frac{\sqrt{b}}{B_{norm}(\tau)}M_{{\tau}}M_{{\sigma^{\prime}}^{T}}\right)=$
$\displaystyle
aM_{\sigma}M_{\sigma^{T}}-M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}-M_{\sigma^{\prime}}M_{{\tau}^{T}}M_{{\sigma}^{T}}+\frac{b}{B_{norm}(\tau)^{2}}M_{\sigma^{\prime}}M_{\tau^{T}}M_{\tau}M_{{\sigma^{\prime}}^{T}}\preceq$
$\displaystyle
aM_{\sigma}M_{\sigma^{T}}-M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}-M_{\sigma^{\prime}}M_{{\tau}^{T}}M_{{\sigma}^{T}}+\frac{b}{B_{norm}(\tau)^{2}}M_{\sigma^{\prime}}(B_{norm}(\tau)^{2}{Id})M_{{\sigma^{\prime}}^{T}}$

Thus,
$M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}+M_{\sigma^{\prime}}M_{{\tau}^{T}}M_{{\sigma}^{T}}\preceq
aM_{\sigma}M_{\sigma^{T}}+bM_{\sigma^{\prime}}M_{{\sigma^{\prime}}^{T}}$, as
needed.

Unfortunately, if we try to bound everything term by term, there may be too
many terms to bound. Instead, we generalize this argument for vectors and
coefficient matrices.

######  Definition 8.4.

Let $\tau$ be a shape. We say that a vector $v$ is a left $\tau$-vector if the
coordinates of $v$ are indexed by left shapes
$\sigma\in\mathcal{L}_{U_{\tau}}$. We say that a vector $w$ is a right
$\tau$-vector if the coordinates of $w$ are indexed by left shapes
$\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}$.

######  Lemma 8.5.

For all $\tau\in\mathcal{M}^{\prime}$, if the norm bounds hold, $v$ is a left
$\tau$-vector, and $w$ is a right $\tau$-vector then

$M^{fact}_{\tau}(vw^{T})+M^{fact}_{{\tau}^{T}}(wv^{T})\preceq
B_{norm}(\tau)\left(M^{fact}_{Id_{U_{\tau}}}(vv^{T})+M^{fact}_{Id_{V_{\tau}}}(ww^{T})\right)$

and

$-M^{fact}_{\tau}(vw^{T})-M^{fact}_{{\tau}^{T}}(wv^{T})\preceq
B_{norm}(\tau)\left(M^{fact}_{Id_{U_{\tau}}}(vv^{T})+M^{fact}_{Id_{V_{\tau}}}(ww^{T})\right)$

###### Proof.

Observe that

$\displaystyle 0\preceq$
$\displaystyle\left(\sum_{\sigma}{v_{\sigma}M_{\sigma}\mp\frac{w_{\sigma}M_{\sigma}M_{{\tau}^{T}}}{B_{norm}(\tau)}}\right)\left(\sum_{\sigma^{\prime}}{v_{\sigma^{\prime}}M_{\sigma^{\prime}}\mp\frac{w_{\sigma^{\prime}}M_{\sigma^{\prime}}M_{{\tau}^{T}}}{B_{norm}(\tau)}}\right)^{T}=$
$\displaystyle\left(\sum_{\sigma}{v_{\sigma}M_{\sigma}\mp\frac{w_{\sigma}M_{\sigma}M_{{\tau}^{T}}}{B_{norm}(\tau)}}\right)\left(\sum_{\sigma^{\prime}}{v_{\sigma^{\prime}}M_{{\sigma^{\prime}}^{T}}\mp\frac{w_{{\sigma^{\prime}}}M_{\tau}M_{{\sigma^{\prime}}^{T}}}{B_{norm}(\tau)}}\right)=$
$\displaystyle\sum_{\sigma,\sigma^{\prime}}{\left(v_{\sigma}v_{\sigma^{\prime}}\right)M_{\sigma}M_{{\sigma^{\prime}}^{T}}}\mp\sum_{\sigma,\sigma^{\prime}}{\frac{\left(v_{\sigma}w_{\sigma^{\prime}}\right)}{B_{norm}(\tau)}M_{\sigma}M_{\tau}M_{\sigma^{\prime}}}$
$\displaystyle\mp\sum_{\sigma,\sigma^{\prime}}{\frac{\left(w_{\sigma}v_{\sigma^{\prime}}\right)}{B_{norm}(\tau)}M_{\sigma}M_{{\tau}^{T}}M_{\sigma^{\prime}}}+\frac{1}{B_{norm}(\tau)^{2}}\sum_{\sigma,\sigma^{\prime}}{\left(v_{\sigma}v_{\sigma^{\prime}}\right)M_{\sigma}M_{\tau}M_{{\tau}^{T}}M_{{\sigma^{\prime}}^{T}}}$

Further observe that

  1. 1.

$\sum_{\sigma,\sigma^{\prime}}{\left(v_{\sigma}v_{\sigma^{\prime}}\right)M_{\sigma}M_{{\sigma^{\prime}}^{T}}}=M^{fact}_{Id_{U_{\tau}}}(vv^{T})$

  2. 2.

$\sum_{\sigma,\sigma^{\prime}}{\left(v_{\sigma}w_{\sigma^{\prime}}\right)M_{\sigma}M_{\tau}M_{{\sigma^{\prime}}^{T}}}=M^{fact}_{\tau}(vw^{T})$

  3. 3.

$\sum_{\sigma,\sigma^{\prime}}{\left(w_{\sigma}v_{\sigma^{\prime}}\right)M_{\sigma}M_{{\tau}^{T}}M_{{\sigma^{\prime}}^{T}}}=M^{fact}_{{\tau}^{T}}(wv^{T})$

  4. 4.

$\displaystyle\sum_{\sigma,\sigma^{\prime}}{\left(w_{\sigma}w_{\sigma^{\prime}}\right)M_{\sigma}M_{\tau}M_{{\tau}^{T}}M_{{\sigma^{\prime}}^{T}}}$
$\displaystyle=\left(\sum_{\sigma}{w_{\sigma}M_{\sigma}}\right)M_{\tau}M_{{\tau}^{T}}\left(\sum_{\sigma}{w_{\sigma}M_{\sigma}}\right)^{T}$
$\displaystyle\preceq\left(\sum_{\sigma}{w_{\sigma}M_{\sigma}}\right)B_{norm}(\tau)^{2}{Id}\left(\sum_{\sigma}{w_{\sigma}M_{\sigma}}\right)^{T}$
$\displaystyle=B_{norm}(\tau)^{2}\sum_{\sigma,\sigma^{\prime}}{\left(w_{\sigma}w_{\sigma^{\prime}}\right)M_{\sigma}M_{{\sigma^{\prime}}^{T}}}$
$\displaystyle={B_{norm}(\tau)^{2}}M^{fact}_{Id_{V_{\tau}}}(ww^{T})$

Putting everything together,

$\frac{M^{fact}_{\tau}(vw^{T})+M^{fact}_{{\tau}^{T}}(wv^{T})}{B_{norm}(\tau)}\preceq
M^{fact}_{Id_{U_{\tau}}}(vv^{T})+M^{fact}_{Id_{V_{\tau}}}(ww^{T})$

and

$-\frac{M^{fact}_{\tau}(vw^{T})+M^{fact}_{{\tau}^{T}}(wv^{T})}{B_{norm}(\tau)}\preceq
M^{fact}_{Id_{U_{\tau}}}(vv^{T})+M^{fact}_{Id_{V_{\tau}}}(ww^{T})$

as needed.

######  Corollary 8.6.

For all $\tau\in\mathcal{M}^{\prime}$, if the norm bounds hold and $H_{U}$ and
$H_{V}$ are matrices such that

$\left[{\begin{array}[]{cc}H_{U}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&H_{V}\end{array}}\right]\succeq 0$

then $M^{fact}_{\tau}(H_{\tau})+M^{fact}_{{\tau}^{T}}(H_{\tau^{T}})\preceq
M^{fact}_{Id_{U_{\tau}}}(H_{U})+M^{fact}_{Id_{V_{\tau}}}(H_{V})$

###### Proof.

If $\left[{\begin{array}[]{cc}H_{U}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&H_{V}\end{array}}\right]\succeq 0$ then we can
write

$\left[{\begin{array}[]{cc}H_{U}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&H_{V}\end{array}}\right]=\sum_{i}{(v_{i},w_{i})(v_{i},w_{i})^{T}}$

Since the $M^{fact}$ operations are linear, the result now follows by summing
the equation

$M^{fact}_{\tau}({v_{i}}w_{i}^{T})+M^{fact}_{{\tau}^{T}}({w_{i}}v_{i}^{T})\preceq
B_{norm}(\tau)\left(M^{fact}_{Id_{U_{\tau}}}({v_{i}}v_{i}^{T})+M^{fact}_{Id_{V_{\tau}}}({w_{i}}w_{i}^{T})\right)$

over all $i$.

Theorem 8.2 now follows directly. For all $U\in\mathcal{I}_{mid}$ and all
$\tau\in\mathcal{M}_{U}$, using Corollary 8.6 with
$H_{U}=H_{V}=\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}$,

$M^{fact}_{\tau}(H_{\tau})+M^{fact}_{{\tau}^{T}}(H_{\tau^{T}})\preceq\frac{1}{|Aut(U)|c(\tau)}M^{fact}_{Id_{U}}(H_{Id_{U}})+\frac{1}{|Aut(U)|c(\tau)}M^{fact}_{Id_{U}}(H_{Id_{U}})$

Summing this equation over all $U\in\mathcal{I}_{mid}$ and all
$\tau\in\mathcal{M}_{U}$, we obtain that

$\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{fact}_{\tau}(H_{\tau})}}\preceq
2\varepsilon^{\prime}\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}$

as needed.

###  8.2 Intersection Term Analysis Strategy

As we saw in the previous subsection, the analysis works out nicely if we work
with $M^{fact}$. Unfortunately, our matrices are expressed in terms of
$M^{orth}$. In this subsection, we describe our strategy for analyzing the
difference between $M^{fact}$ and $M^{orth}$.

Recall the following expressions for $\left(M^{fact}_{\tau}(H)\right)(A,B)$
and $\left(M^{orth}_{\tau}(H)\right)(A,B)$ where $A$ has shape $U_{\tau}$ and
$B$ has shape $V_{\tau}$:

$\left(M^{fact}_{\tau}(H)\right)(A,B)=\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})\sum_{A^{\prime},B^{\prime}}{\sum_{R_{1}\in\mathcal{R}(\sigma,A,A^{\prime}),R_{2}\in\mathcal{R}(\tau,A^{\prime},B^{\prime}),\atop
R_{3}\in\mathcal{R}({\sigma^{\prime}}^{T},B^{\prime},B)}M_{R_{1}}(A,A^{\prime})M_{R_{2}}(A^{\prime},B^{\prime})M_{R_{3}}(B^{\prime},B)}}$
$\displaystyle\left(M^{orth}_{\tau}(H)\right)(A,B)$
$\displaystyle=\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})\sum_{A^{\prime},B^{\prime}}{\sum_{R_{1}\in\mathcal{R}(\sigma,A,A^{\prime}),R_{2}\in\mathcal{R}(\tau,A^{\prime},B^{\prime}),\atop{R_{3}\in\mathcal{R}({\sigma^{\prime}}^{T},B^{\prime},B),R_{1},R_{2},R_{3}\text{
are properly
composable}}}M_{R_{1}}(A,A^{\prime})M_{R_{2}}(A^{\prime},B^{\prime})M_{R_{3}}(B^{\prime},B)}}$

This implies that
$\left(M^{fact}_{\tau}(H)\right)(A,B)-\left(M^{orth}_{\tau}(H)\right)(A,B)$ is
equal to

$\sum_{\sigma\in\mathcal{L}_{U_{\tau}},\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}}{H(\sigma,\sigma^{\prime})\sum_{A^{\prime},B^{\prime}}{\sum_{R_{1}\in\mathcal{R}(\sigma,A,A^{\prime}),R_{2}\in\mathcal{R}(\tau,A^{\prime},B^{\prime}),\text{
and }R_{3}\in\mathcal{R}({\sigma^{\prime}}^{T},B^{\prime},B)\atop
R_{1},R_{2},R_{3}\text{ are not properly
composable}}M_{R_{1}}(A,A^{\prime})M_{R_{2}}(A^{\prime},B^{\prime})M_{R_{3}}(B^{\prime},B)}}$

Thus, to understand the difference between $M^{fact}$ and $M^{orth}$, we need
to analyze the terms $\chi_{R_{1}}\chi_{R_{2}}\chi_{R_{3}}=\chi_{R_{1}\circ
R_{2}\circ R_{3}}$ for ribbons $R_{1},R_{2},R_{3}$ which are composable but
not properly composable. These terms, which we call intersection terms, are
not negligible and must be analyzed carefully. In particular, we decompose
each resulting ribbon $R=R_{1}\circ R_{2}\circ R_{3}$ into new left, middle,
and right parts. We do this as follows:

  1. 1.

Let $V_{*}$ be the set of vertices which appear more than once in
$V(R_{1}\circ R_{2}\circ R_{3})$. In other words, $V_{*}$ is the set of
vertices involved in the intersections between $R_{1}$, $R_{2}$, and $R_{3}$
(not counting the facts that $B_{R_{1}}=A_{R_{2}}$ and $B_{R_{2}}=A_{R_{3}}$
because we expect these intersections).

  2. 2.

Let $A^{\prime}$ be the leftmost minimum vertex separator of $A_{R_{1}}$ and
$B_{R_{1}}\cup V_{*}$ in $R_{1}$. We turn $A^{\prime}$ into a matrix index by
specifying an ordering $O_{A^{\prime}}$ for the vertices in $A^{\prime}$.

  3. 3.

Let $B^{\prime}$ be the leftmost minimum vertex separator of $A_{R_{3}}\cup
V_{*}$ and $B_{R_{3}}$ in $R_{2}$. We turn $B^{\prime}$ into a matrix index by
specifying an ordering $O_{B^{\prime}}$ for the vertices in $B^{\prime}$.

  4. 4.

Decompose $R_{1}$ as $R_{1}={R^{\prime}}_{1}\cup R_{4}$ where
${R^{\prime}}_{1}$ is the part of $R_{1}$ between $A_{R_{1}}$ and $A^{\prime}$
and $R_{4}$ is the part of $R_{1}$ between $B^{\prime}$ and
$B_{R_{1}}=A_{R_{2}}$. Similarly, decompose $R_{3}$ as
$R_{3}=R_{5}\cup{R^{\prime}}_{3}$ where $R_{5}$ is the part of $R_{3}$ between
$B_{R_{1}}=A_{R_{2}}$ and $B^{\prime}$ and ${R^{\prime}}_{3}$ is the part of
$R_{3}$ between $B^{\prime}$ and $B_{R_{3}}$.

  5. 5.

Take $R^{\prime}_{2}=R_{4}\circ R_{2}\circ R_{5}$ and note that
$R^{\prime}_{1}\circ R^{\prime}_{2}\circ R^{\prime}_{3}=R_{1}\circ R_{2}\circ
R_{3}$. We view $R^{\prime}_{1},R^{\prime}_{2},R^{\prime}_{3}$ as the left,
middle, and right parts of $R=R_{1}\circ R_{2}\circ R_{3}$

While we will verify our analysis by checking the coefficients of the ribbons,
we want to express everything in terms of shapes. We use the following
conventions for the names of the shapes:

  1. 1.

As usual, we let $\sigma$, $\tau$, and ${\sigma^{\prime}}^{T}$ be the shapes
of $R_{1}$, $R_{2}$, and $R_{3}$.

  2. 2.

We let $\gamma$ and ${\gamma^{\prime}}^{T}$ be the shapes of $R_{4}$ and
$R_{5}$.

  3. 3.

We let $\sigma_{2}$, $\tau_{P}$, and ${\sigma^{\prime}_{2}}^{T}$ be the shapes
of $R^{\prime}_{1}$, $R^{\prime}_{2}$, and $R^{\prime}_{3}$. Here $P$ is the
intersection pattern induced by $R_{4}$, $R_{2}$, and $R_{5}$ which we define
in the next subsection.

######  Remark 8.7.

A key feature of our analysis is that it will work the same way regardless of
the shapes $\sigma_{2},{\sigma^{\prime}_{2}}^{T}$ of $R^{\prime}_{1}$ and
$R^{\prime}_{3}$. In other words, if we replace $\sigma_{2}$ by $\sigma_{2a}$
and $\sigma^{\prime}_{2}$ by $\sigma^{\prime}_{2a}$ for a given intersection
term, this just replaces $\sigma=\sigma_{2}\cup\gamma$ with
$\sigma_{a}=\sigma_{2a}\cup\gamma$ and
$\sigma^{\prime}=\sigma^{\prime}_{2}\cup\gamma^{\prime}$ with
$\sigma^{\prime}_{a}=\sigma^{\prime}_{2a}\cup\gamma^{\prime}$. This allows us
to focus on the shapes $\gamma$, $\tau$, and ${\gamma^{\prime}}^{T}$ and is
the reason why the $-\gamma,\gamma$ operation appears in our results.

###  8.3 Intersection Term Analysis

In this section, we implement our strategy for analyzing intersection terms.
For simplicity, we only give rough definitions and proof sketches here. For a
more rigorous treatment, see Apendix B.

We begin by defining intersection patterns which describe how the ribbons
$R_{1}$, $R_{2}$, and $R_{3}$ intersect.

######  Definition 8.8 (Rough Definition of Intersection Patterns).

Given $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$,
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$, and ribbons
$R_{1}$, $R_{2}$, and $R_{3}$ of shapes $\gamma$, $\tau$, and
${\gamma^{\prime}}^{T}$ which are composable but not properly composable, we
define the intersection pattern $P$ induced by $R_{1}$, $R_{2}$, and $R_{3}$
and the resulting shape $\tau_{P}$ as follows:

  1. 1.

We take $V(P)=V(\gamma\circ\tau\circ{\gamma^{\prime}}^{T})$.

  2. 2.

We take $E(P)$ to be the set of edges $(u,v)$ such that $u,v$ are distinct
vertices in $V(\sigma\circ\tau\circ{\sigma^{\prime}}^{T})$ but $u$ and $v$
correspond to the same vertex in $R_{1}\circ R_{2}\circ R_{3}$

  3. 3.

We define $\tau_{P}$ to be the shape of the ribbon $R=R_{1}\circ R_{2}\circ
R_{3}$

######  Definition 8.9.

Given $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$, and
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$, we define
$\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}$ to be the set of all
possible intersection patterns $P$ which can be induced by ribbons $R_{1}$,
$R_{2}$, and $R_{3}$ of shapes $\gamma$, $\tau$, and ${\gamma^{\prime}}^{T}$.

######  Remark 8.10.

Note that if $\gamma=Id_{U_{\tau}}$ and $\gamma^{\prime}=Id_{V_{\tau}}$ then
$\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}=\emptyset$ as every
intersection pattern must have an unexpected intersection so either $\gamma$
or $\gamma^{\prime}$ must be non-trivial.

It would be nice if the intersection pattern $P$ together with the ribbon $R$
allowed us to recover the original ribbons $R_{1}$, $R_{2}$, and $R_{3}$.
Unfortunately, it is possible for different triples of ribbons to result in
the same intersection pattern $P$ and ribbon $R$. That said, the number of
such triples cannot be too large, and this is sufficient for our purposes.

######  Definition 8.11.

Given an intersection pattern
$P\in\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}$, let $R$ be a ribbon of
shape $\tau_{P}$. We define $N(P)$ to be the number of different triples of
ribbons $R_{1},R_{2},R_{3}$ such that $R_{1}\circ R_{2}\circ R_{3}=R$ and
$R_{1},R_{2},R_{3}$ induce the intersection pattern $P$.

######  Lemma 8.12.

For all intersection patterns
$P\in\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}$,
$N(P)\leq|V(\tau_{P})|^{|V(\gamma)\setminus
U_{\gamma}|+|V(\gamma^{\prime})\setminus U_{\gamma^{\prime}}|}$

###### Proof sketch.

This can be proved by making the following observations:

  1. 1.

$A_{R_{1}}=A_{R}$ and $B_{R_{3}}=B_{R}$.

  2. 2.

All of the remining vertices in $V(R_{1})$ and $V(R_{3})$ must be equal to
some vertex in $V(R)$.

  3. 3.

Once $R_{1}$ and $R_{3}$ are determined, there is at most one ribbon $R_{2}$
such that $R_{1},R_{2},R_{3}$ are composable, $R=R_{1}\circ R_{2}\circ R_{3}$,
and $R_{1},R_{2},R_{3}$ induce the intersection pattern $P$.

With these definitions, we can now analyze the intersection terms.

######  Definition 8.13.

Given a left shape $\sigma$, define $e_{\sigma}$ to be the vector which has a
$1$ in coordinate $\sigma$ and has a $0$ in all other coordinates.

######  Lemma 8.14.

For all $\tau\in\mathcal{M}^{\prime}$, $\sigma\in\mathcal{L}_{U_{\tau}}$, and
$\sigma^{\prime}\in\mathcal{L}_{V_{\tau}}$,

$\displaystyle
M^{fact}_{\tau}(e_{\sigma}e^{T}_{\sigma^{\prime}})-M^{orth}_{\tau}(e_{\sigma}e^{T}_{\sigma^{\prime}})=\sum_{\sigma_{2}\in\mathcal{L},\gamma\in\Gamma:\sigma_{2}\circ\gamma=\sigma}{\frac{1}{|Aut(U_{\gamma})|}\sum_{P\in\mathcal{P}_{\gamma,\tau,Id_{V_{\tau}}}}N(P)M^{orth}_{\tau_{P}}(e_{\sigma_{2}}e^{T}_{\sigma^{\prime}})}$
$\displaystyle+\sum_{\sigma^{\prime}_{2}\in\mathcal{L},\gamma^{\prime}\in\Gamma:\sigma^{\prime}_{2}\circ\gamma^{\prime}=\sigma^{\prime}}{\frac{1}{|Aut(U_{\gamma^{\prime}})|}\sum_{P\in\mathcal{P}_{Id_{U_{\tau}},\tau,{\gamma^{\prime}}^{T}}}N(P)M^{orth}_{\tau_{P}}(e_{\sigma}e^{T}_{\sigma^{\prime}_{2}})}$
$\displaystyle+\sum_{\sigma_{2}\in\mathcal{L},\gamma\in\Gamma:\sigma_{2}\circ\gamma=\sigma}{\sum_{\sigma^{\prime}_{2}\in\mathcal{L},\gamma^{\prime}\in\Gamma:\sigma^{\prime}_{2}\circ\gamma^{\prime}=\sigma^{\prime}}{\frac{1}{|Aut(U_{\gamma})|\cdot|Aut(U_{\gamma^{\prime}})|}\sum_{P\in\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}}N(P)M^{orth}_{\tau_{P}}(e_{\sigma_{2}}e^{T}_{\sigma^{\prime}_{2}})}}$

###### Proof sketch.

This lemma follows from the following bijection. Consider the third term

$\sum_{\sigma_{2}\in\mathcal{L},\gamma\in\Gamma:\sigma_{2}\circ\gamma=\sigma}{\sum_{\sigma^{\prime}_{2}\in\mathcal{L},\gamma^{\prime}\in\Gamma:\sigma^{\prime}_{2}\circ\gamma^{\prime}=\sigma^{\prime}}{\frac{1}{|Aut(U_{\gamma})|\cdot|Aut(U_{\gamma^{\prime}})|}\sum_{P\in\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}}N(P)M^{orth}_{\tau_{P}}(e_{\sigma_{2}}e^{T}_{\sigma^{\prime}_{2}})}}$

On one side, we have the following data:

  1. 1.

Ribbons $R_{1}$, $R_{2}$, and $R_{3}$ of shapes
$\gamma,\tau,{\gamma^{\prime}}^{T}$ such that $R_{1},R_{2},R_{3}$ are
composable but $R_{1}$ and $R_{2}\circ R_{3}$ are not properly composable
(i.e. $R_{1}$ has an unexpected intersection with $R_{2}$ and/or $R_{3}$) and
$R_{1}\circ R_{2}$ and $R_{3}$ are not properly composable (i.e. $R_{3}$ has
an unexpected intersection with $R_{1}$ and/or $R_{2}$).

  2. 2.

An ordering $O_{A^{\prime}}$ on the leftmost minimum vertex separator
$A^{\prime}$ of $A_{R_{1}}$ and $V_{*}\cup B_{R_{1}}$ (recall that $V_{*}$ is
the set of vertices which appear more than once in $V(R_{1}\circ R_{2}\circ
R_{3})$).

  3. 3.

An ordering $O_{B^{\prime}}$ on the rightmost minimum vertex separator
$B^{\prime}$ of $V_{*}\cup A_{R_{3}}$ and $B_{R_{3}}$.

On the other side, we have the following data

  1. 1.

An intersection pattern $P\in\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}$
where $\gamma$ and ${\gamma^{\prime}}^{T}$ are non-trivial.

  2. 2.

Ribbons $R^{\prime}_{1}$, $R^{\prime}_{2}$, $R^{\prime}_{3}$ of shapes
$\sigma_{2}$, $\tau_{P}$, ${\sigma^{\prime}_{2}}^{T}$ which are properly
composable

  3. 3.

A number in $[N(P)]$ describing which possible triple of ribbons resulted in
the intersection pattern $P$ and the ribbon $R^{\prime}_{2}$.

To see this bijection, note that given the data on the first side, we can
recover the ribbons $R^{\prime}_{1}$, $R^{\prime}_{2}$, and $R^{\prime}_{3}$
as follows:

  1. 1.

We decompose $R_{1}$ as $R_{1}=R^{\prime}_{1}\circ R_{4}$ where
$B_{R^{\prime}_{1}}=A_{R_{4}}=A^{\prime}$ with the ordering $O_{A^{\prime}}$.

  2. 2.

We decompose $R_{3}$ as $R_{3}=R_{5}\circ R^{\prime}_{3}$ where where
$B_{R_{5}}=A_{R^{\prime}_{3}}=B^{\prime}$ with the ordering $O_{B^{\prime}}$.

  3. 3.

We take $R^{\prime}_{2}=R_{4}\circ R_{2}\circ R_{5}$.

The intersection pattern $P$ and the number in $[N(P)]$ can be obtained from
$R_{1}$, $R_{2}$, and $R_{3}$.

Conversely, with the data on the other side, we can recover the data on the
first side as follows:

  1. 1.

$R^{\prime}_{2}$ gives an ordering $O_{A^{\prime}}$ for
$A^{\prime}=A_{R^{\prime}_{2}}$ and an ordering $O_{B^{\prime}}$ for
$B^{\prime}=B_{R^{\prime}_{2}}$.

  2. 2.

The ribbon $R^{\prime}_{2}$, intersection pattern $P$, and number in $[N(P)]$
allow us to recover $R_{4}$, $R_{2}$, and $R_{5}$.

  3. 3.

We take $R_{1}=R^{\prime}_{1}\circ R_{4}$ and $R_{3}=R_{5}\circ
R^{\prime}_{3}$.

Thus, both sides have the same coefficient for each ribbon.

The analysis for the the first term is the same except that when
$\gamma^{\prime}$ is trivial, we always take $\gamma^{\prime}=Id_{V_{\tau}}$.
Thus, we always have that $B^{\prime}=B_{R^{\prime}_{2}}=B_{R_{2}}$ (with the
same ordering) and $R^{\prime}_{3}=R_{3}=Id_{B^{\prime}}$. Because of this,
there is no need to specify $R_{3}$, $R^{\prime}_{3}$, $R_{5}$, or an ordering
on $B^{\prime}$.

Similarly, the analysis for the the second term is the same except that when
$\gamma$ is trivial, we always take $\gamma=Id_{U_{\tau}}$. Thus, we always
have that $A^{\prime}=A_{R^{\prime}_{2}}=A_{R_{2}}$ (with the same ordering)
and $R^{\prime}_{1}=R_{1}=Id_{A^{\prime}}$. Because of this, there is no need
to specify $R_{1}$, $R^{\prime}_{1}$, $R_{4}$, or an ordering on $A^{\prime}$.

Applying Lemma 8.14 for all $\sigma$ and $\sigma^{\prime}$ simultaneously, we
obtain the following corollary.

######  Definition 8.15.

For all $U,V\in\mathcal{I}_{mid}$, given a $\gamma\in\Gamma_{U,V}$ and a
vector $v$ indexed by left shapes $\sigma\in\mathcal{L}_{V}$, define
$v^{-\gamma}$ to be the vector indexed by left shapes
$\sigma_{2}\in\mathcal{L}_{U}$ such that
$v^{-\gamma}(\sigma_{2})=v(\sigma_{2}\circ\gamma)$ if
$\sigma_{2}\circ\gamma\in\mathcal{L}_{V}$ and $v^{-\gamma}(\sigma_{2})=0$
otherwise.

######  Proposition 8.16.

For all composable $\gamma_{2},\gamma_{1}\in\Gamma$ and all vectors $v$
indexed by left shapes in $\mathcal{L}_{V_{\gamma_{1}}}$,
$(v^{-\gamma_{1}})^{-\gamma_{2}}=v^{-\gamma_{2}\circ\gamma_{1}}$

######  Corollary 8.17.

For all $\tau\in\mathcal{M}^{\prime}$, for all left $\tau$-vectors $v$ and all
right $\tau$-vectors $w$,

$\displaystyle
M^{orth}_{\tau}(vw^{T})=M^{fact}_{\tau}(vw^{T})-\sum_{\gamma\in\Gamma_{*,U_{\tau}}}{\frac{1}{|Aut(U_{\gamma})|}\sum_{P\in\mathcal{P}_{\gamma,\tau,Id_{V_{\tau}}}}N(P)M^{orth}_{\tau_{P}}(v^{-\gamma}w^{T})}$
$\displaystyle-\sum_{\gamma^{\prime}\in\Gamma_{*,V_{\tau}}}{\frac{1}{|Aut(U_{\gamma^{\prime}})|}\sum_{P\in\mathcal{P}_{Id_{U_{\tau}},\tau,{\gamma^{\prime}}^{T}}}N(P)M^{orth}_{\tau_{P}}(v(w^{-\gamma})^{T})}$
$\displaystyle-\sum_{\gamma\in\Gamma_{*,U_{\tau}}}{\sum_{\gamma^{\prime}\in\Gamma_{*,V_{\tau}}}{\frac{1}{|Aut(U_{\gamma})|\cdot|Aut(U_{\gamma^{\prime}})|}\sum_{P\in\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}}N(P)M^{orth}_{\tau_{P}}(v^{-\gamma}(w^{-\gamma^{\prime}})^{T})}}$

Applying Corollary 8.17 iteratively, we obtain the following theorem:

######  Definition 8.18.

Given $\gamma,\gamma^{\prime}\in\Gamma\cup\\{Id_{U}:U\in\mathcal{I}_{mid}\\}$
and $j>0$, let $\Gamma_{\gamma,\gamma^{\prime},j}$ be the set of all
$\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma\cup\\{Id_{U}:U\in\mathcal{I}_{mid}\\}$
such that:

  1. 1.

$\gamma_{j},\ldots,\gamma_{1}$ are composable and
$\gamma_{j}\circ\ldots\circ\gamma_{1}=\gamma$

  2. 2.

$\gamma^{\prime}_{j},\ldots,\gamma^{\prime}_{1}$ are composable and
$\gamma^{\prime}_{j}\circ\ldots\circ\gamma^{\prime}_{1}=\gamma^{\prime}$

  3. 3.

For all $i\in[1,j]$, $\gamma_{i}$ or $\gamma^{\prime}_{i}$ is non-trivial
(i.e. $\gamma_{i}\neq Id_{U_{\gamma_{i}}}$ or $\gamma^{\prime}_{i}\neq
Id_{U_{\gamma^{\prime}_{i}}}$).

######  Remark 8.19.

Note that if $\gamma=Id_{U}$ and $\gamma^{\prime}=Id_{V}$ then for all $j>0$,
$\Gamma_{\gamma,\gamma^{\prime},j}=\emptyset$.

######  Theorem 8.20.

For all $\tau\in\mathcal{M}^{\prime}$, left $\tau$-vectors $v$, and right
$\tau$-vetors $w$,

$\displaystyle M^{orth}_{\tau}(v{w^{T}})=M^{fact}_{\tau}(v{w^{T}})+$
$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}\sum_{j>0}{(-1)^{j}\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}$
$\displaystyle\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)M^{fact}_{\tau_{P_{j}}}(v^{-\gamma}{(w^{-\gamma^{\prime}})^{T}})}$

where we take $\tau_{P_{0}}=\tau$.

###  8.4 Bounding the difference between $M^{fact}$ and $M^{orth}$

In this subsection, we bound the difference between
$M^{fact}_{\tau}(H_{\tau})$ and $M^{orth}_{\tau}(H_{\tau})$. We recall the
following conditions on $B(\gamma)$, $N(\gamma)$, and $c(\gamma)$:

  1. 1.

For all $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$, and
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\left(\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\right)\left(\prod_{i:\gamma^{\prime}_{i}\text{
is non-trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}\right)}}$
$\displaystyle\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}\leq\frac{N(\gamma)N(\gamma^{\prime})}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-trivial}}}}$

  2. 2.

For all $\tau\in\mathcal{M}^{\prime}$, $\gamma\in\Gamma_{*,U_{\tau}}$, and
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}$, for all
$P\in\mathcal{P}_{\gamma,\tau,{\gamma^{\prime}}^{T}}$, $B_{norm}(\tau_{P})\leq
B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

  3. 3.

$\forall
V\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{*,V}}{\frac{1}{|Aut(U_{\gamma})|c(\gamma)}}\leq\varepsilon^{\prime}\leq\frac{1}{20}$

With these conditions, we can now bound the difference between $M^{fact}$ and
$M^{orth}$.

######  Lemma 8.21.

If the norm bounds and the conditions on $B(\gamma)$, $N(\gamma)$, and
$c(\gamma)$ hold then for all $\tau\in\mathcal{M}^{\prime}$, left
$\tau$-vectors $v$, and right $\tau$-vetors $w$,

$\displaystyle\left(M^{fact}_{\tau}(v{w^{T}})+M^{fact}_{{\tau}^{T}}(w{v^{T}})\right)-\left(M^{orth}_{\tau}(v{w^{T}})+M^{orth}_{{\tau}^{T}}(w{v^{T}})\right)\preceq$
$\displaystyle{\varepsilon^{\prime}}B_{norm}(\tau)M^{fact}_{Id_{U_{\tau}}}(vv^{T})+2\sum_{\gamma\in\Gamma_{*,U_{\tau}}}{\frac{B(\gamma)^{2}N(\gamma)^{2}B_{norm}(\tau){c(\gamma)}}{|Aut(U_{\gamma})|}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})}+$
$\displaystyle{\varepsilon^{\prime}}B_{norm}(\tau)M^{fact}_{Id_{V_{\tau}}}(ww^{T})+2\sum_{\gamma^{\prime}\in\Gamma_{*,V_{\tau}}}{\frac{B(\gamma^{\prime})^{2}N(\gamma^{\prime})^{2}B_{norm}(\tau){c(\gamma^{\prime})}}{|Aut(U_{\gamma^{\prime}})|}M^{fact}_{Id_{U_{\gamma^{\prime}}}}(w^{-\gamma^{\prime}}(w^{-\gamma^{\prime}})^{T})}$

###### Proof.

By Theorem 8.20, taking $\tau_{P_{0}}=\tau$,

$\displaystyle M^{orth}_{\tau}(v{w^{T}})=M^{fact}_{\tau}(v{w^{T}})+$
$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}\sum_{j>0}{(-1)^{j}\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}$
$\displaystyle\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)M^{fact}_{\tau_{P_{j}}}(v^{-\gamma}{(w^{-\gamma^{\prime}})^{T}})}$

Taking the transpose of this equation gives

$\displaystyle
M^{orth}_{{\tau}^{T}}(w{v^{T}})=M^{fact}_{{\tau}^{T}}(w{v^{T}})+$
$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}\sum_{j>0}{(-1)^{j}\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}$
$\displaystyle\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)M^{fact}_{\tau^{T}_{P_{j}}}({w^{-\gamma^{\prime}}(v^{-\gamma})^{T}})}$

Now observe that by Lemma 8.5, if the norm bounds hold,

$\displaystyle{\pm}\left(M^{fact}_{\tau_{P_{j}}}(v^{-\gamma}{(w^{-\gamma^{\prime}})^{T}})+M^{fact}_{\tau^{T}_{P_{j}}}({w^{-\gamma^{\prime}}(v^{-\gamma})^{T}})\right)=$
$\displaystyle{\pm}M^{fact}_{\tau_{P_{j}}}\left(\left(\sqrt{\frac{N(\gamma)B(\gamma){c(\gamma)}}{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}}v^{-\gamma}\right)\left(\sqrt{\frac{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}{N(\gamma)B(\gamma){c(\gamma)}}}{(w^{-\gamma^{\prime}})^{T}}\right)\right)\pm$
$\displaystyle
M^{fact}_{\tau^{T}_{P_{j}}}\left(\left(\sqrt{\frac{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}{N(\gamma)B(\gamma){c(\gamma)}}}w^{-\gamma^{\prime}}\right)\left(\sqrt{\frac{N(\gamma)B(\gamma){c(\gamma)}}{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}}{(v^{-\gamma})^{T}}\right)\right)\preceq$
$\displaystyle
B_{norm}(\tau_{P_{j}})\left(\frac{N(\gamma)B(\gamma){c(\gamma)}}{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})+\frac{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}{N(\gamma)B(\gamma){c(\gamma)}}M^{fact}_{Id_{U_{\gamma^{\prime}}}}(w^{-\gamma^{\prime}}(w^{-\gamma^{\prime}})^{T})\right)$

Combining these equations,

$\displaystyle\left(M^{fact}_{\tau}(v{w^{T}})+M^{fact}_{{\tau}^{T}}(w{v^{T}})\right)-\left(M^{orth}_{\tau}(v{w^{T}})+M^{orth}_{{\tau}^{T}}(w{v^{T}})\right)\preceq$
$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}$
$\displaystyle\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)B_{norm}(\tau_{P_{j}})}$
$\displaystyle\left(\frac{N(\gamma)B(\gamma){c(\gamma)}}{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})+\frac{N(\gamma^{\prime})B(\gamma^{\prime}){c(\gamma^{\prime})}}{N(\gamma)B(\gamma){c(\gamma)}}M^{fact}_{Id_{U_{\gamma^{\prime}}}}(w^{-\gamma^{\prime}}(w^{-\gamma^{\prime}})^{T})\right)$

From the conditions on $B(\gamma)$ and $N(\gamma)$,

  1. 1.

$B_{norm}(\tau_{P_{j}})\leq B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

  2. 2.

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\left(\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\right)\left(\prod_{i:\gamma^{\prime}_{i}\text{
is non-trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}\right)}}$
$\displaystyle\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}\leq\frac{N(\gamma)N(\gamma^{\prime})}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-trivial}}}}$

Putting these equations together,

$\displaystyle\left(M^{fact}_{\tau}(v{w^{T}})+M^{fact}_{{\tau}^{T}}(w{v^{T}})\right)-\left(M^{orth}_{\tau}(v{w^{T}})+M^{orth}_{{\tau}^{T}}(w{v^{T}})\right)\preceq$
$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}{\frac{B(\gamma)^{2}N(\gamma)^{2}B_{norm}(\tau){c(\gamma)}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-
trivial}}}{c(\gamma^{\prime})}}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})}+$
$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}{\frac{B(\gamma^{\prime})^{2}N(\gamma^{\prime})^{2}B_{norm}(\tau){c(\gamma^{\prime})}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-
trivial}}}{c(\gamma)}}M^{fact}_{Id_{U_{\gamma^{\prime}}}}(w^{-\gamma^{\prime}}(w^{-\gamma^{\prime}})^{T})}$

Now observe that

$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}{\frac{B(\gamma)^{2}N(\gamma)^{2}B_{norm}(\tau){c(\gamma)}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-
trivial}}}{c(\gamma^{\prime})}}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})}\preceq$
$\displaystyle\left(\sum_{\gamma^{\prime}\in\Gamma_{*,V_{\tau}}}{\frac{1}{|Aut(U_{\gamma^{\prime}})|{c(\gamma^{\prime})}}}\right)B_{norm}(\tau)M^{fact}_{Id_{U_{\tau}}}(vv^{T})+$
$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}}{\left(\sum_{\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}}{\frac{1}{(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{
is non-
trivial}}}{c(\gamma^{\prime})}}}\right)\frac{B(\gamma)^{2}N(\gamma)^{2}B_{norm}(\tau){c(\gamma)}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-
trivial}}}}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})}\preceq$
$\displaystyle{\varepsilon^{\prime}}B_{norm}(\tau)M^{fact}_{Id_{U_{\tau}}}(vv^{T})+2\sum_{\gamma\in\Gamma_{*,U_{\tau}}}{\frac{B(\gamma)^{2}N(\gamma)^{2}B_{norm}(\tau){c(\gamma)}}{|Aut(U_{\gamma})|}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})}$

Following similar logic,

$\displaystyle\sum_{\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\},\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}:\atop\gamma\text{
or }\gamma^{\prime}\text{ is non-trivial
}}{\frac{B(\gamma^{\prime})^{2}N(\gamma^{\prime})^{2}B_{norm}(\tau){c(\gamma^{\prime})}}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-
trivial}}}{c(\gamma)}}M^{fact}_{Id_{U_{\gamma^{\prime}}}}(w^{-\gamma^{\prime}}(w^{-\gamma^{\prime}})^{T})}\preceq$
$\displaystyle{\varepsilon^{\prime}}B_{norm}(\tau)M^{fact}_{Id_{V_{\tau}}}(ww^{T})+2\sum_{\gamma^{\prime}\in\Gamma_{*,V_{\tau}}}{\frac{B(\gamma^{\prime})^{2}N(\gamma^{\prime})^{2}B_{norm}(\tau){c(\gamma^{\prime})}}{|Aut(U_{\gamma^{\prime}})|}M^{fact}_{Id_{U_{\gamma^{\prime}}}}(w^{-\gamma^{\prime}}(w^{-\gamma^{\prime}})^{T})}$

Putting everything together,

$\displaystyle\left(M^{fact}_{\tau}(v{w^{T}})+M^{fact}_{{\tau}^{T}}(w{v^{T}})\right)-\left(M^{orth}_{\tau}(v{w^{T}})+M^{orth}_{{\tau}^{T}}(w{v^{T}})\right)\preceq$
$\displaystyle{\varepsilon^{\prime}}B_{norm}(\tau)M^{fact}_{Id_{U_{\tau}}}(vv^{T})+2\sum_{\gamma\in\Gamma_{*,U_{\tau}}}{\frac{B(\gamma)^{2}N(\gamma)^{2}B_{norm}(\tau){c(\gamma)}}{|Aut(U_{\gamma})|}M^{fact}_{Id_{U_{\gamma}}}(v^{-\gamma}(v^{-\gamma})^{T})}+$
$\displaystyle{\varepsilon^{\prime}}B_{norm}(\tau)M^{fact}_{Id_{V_{\tau}}}(ww^{T})+2\sum_{\gamma^{\prime}\in\Gamma_{*,V_{\tau}}}{\frac{B(\gamma^{\prime})^{2}N(\gamma^{\prime})^{2}B_{norm}(\tau){c(\gamma^{\prime})}}{|Aut(U_{\gamma^{\prime}})|}M^{fact}_{Id_{U_{\gamma^{\prime}}}}(w^{-\gamma^{\prime}}(w^{-\gamma^{\prime}})^{T})}$

as needed.

Using Lemma 8.21 we have the following corollaries:

######  Corollary 8.22.

For all $U\in\mathcal{I}_{mid}$, if the norm bounds and the conditions on
$B(\gamma)$, $N(\gamma)$, and $c(\gamma)$ hold and $H_{Id_{U}}\succeq 0$ then

$M^{fact}_{Id_{U}}(H_{Id_{U}})-M^{orth}_{Id_{U}}(H_{Id_{U}})\preceq{\varepsilon^{\prime}}M^{fact}_{Id_{U}}(H_{Id_{U}})+2\sum_{\gamma\in\Gamma_{*,U}}{\frac{B(\gamma)^{2}N(\gamma)^{2}{c(\gamma)}}{|Aut(U_{\gamma})|}M^{fact}_{Id_{U_{\gamma}}}(H^{-\gamma,\gamma}_{Id_{U}})}$

######  Corollary 8.23.

For all $U\in\mathcal{I}_{mid}$ and all $\tau\in\mathcal{M}_{U}$, if the norm
bounds and the conditions on $B(\gamma)$, $N(\gamma)$, and $c(\gamma)$ hold
and

$\left[{\begin{array}[]{cc}\frac{1}{||Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{array}}\right]\succeq
0$

then

$\displaystyle\left(M^{fact}_{\tau}(H_{\tau})+M^{fact}_{{\tau}^{T}}(H^{T}_{\tau})\right)-\left(M^{orth}_{\tau}(H_{\tau})+M^{orth}_{{\tau}^{T}}(H^{T}_{\tau})\right)\preceq$
$\displaystyle
2{\varepsilon^{\prime}}\frac{1}{|Aut(U)|c(\tau)}M^{fact}_{Id_{U}}(H_{Id_{U}})+4\sum_{\gamma\in\Gamma_{*,U}}{\frac{B(\gamma)^{2}N(\gamma)^{2}{c(\gamma)}}{|Aut(U_{\gamma})|\cdot|Aut(U)|c(\tau)}M^{fact}_{Id_{U_{\gamma}}}(H_{Id_{U}}^{-\gamma,\gamma}})$

###  8.5 Proof of the Main Theorem

We now prove the following theorem which is a slight modification of Theorem
8.1 and which implies Theorem 8.1.

######  Theorem 8.24.

For all $\varepsilon>0$ and all $\varepsilon^{\prime}\in(0,\frac{1}{20}]$, for
any moment matrix

$\Lambda=\sum_{U\in\mathcal{I}_{mid}}{M^{orth}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{orth}_{\tau}(H_{\tau})}},$

if we have that for all $\alpha\in\mathcal{M}^{\prime},||M_{\alpha}||\leq
B_{norm}(\alpha)$ and $B(\gamma)$, $N(\gamma)$, and $c(\alpha)$ are functions
such that

  1. 1.

For all $\tau\in\mathcal{M}^{\prime}$, $\gamma\in\Gamma_{*,U_{\tau}}$,
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}$, and all intersection patterns
$P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$B_{norm}(\tau_{P})\leq B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

  2. 2.

For all composable $\gamma_{1},\gamma_{2}$,
$B(\gamma_{1})B(\gamma_{2})=B(\gamma_{1}\circ\gamma_{2})$.

  3. 3.

$\forall
U\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{U,*}}{\frac{1}{|Aut(U)|c(\gamma)}}<\varepsilon^{\prime}$

  4. 4.

$\forall
V\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{*,V}}{\frac{1}{|Aut(U_{\gamma})|c(\gamma)}}<\varepsilon^{\prime}$

  5. 5.

$\forall
U\in\mathcal{I}_{mid},\sum_{\tau\in\mathcal{M}_{U}}{\frac{1}{|Aut(U)|c(\tau)}}<\varepsilon^{\prime}$

  6. 6.

For all $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$, and
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma_{i}})|}}\prod_{i:\gamma^{\prime}_{i}\text{
is non-
trivial}}{\frac{1}{|Aut(U_{\gamma^{\prime}_{i}})|}}}}\sum_{P_{1},\cdots,P_{j}:P_{i}\in\mathcal{P}_{\gamma_{i},\tau_{P_{i-1}},{\gamma^{\prime}_{i}}^{T}}}{\left(\prod_{i=1}^{j}{N(P_{i})}\right)}$
$\displaystyle\leq\frac{N(\gamma)N(\gamma^{\prime})}{(|Aut(U_{\gamma})|)^{1_{\gamma\text{
is non-trivial}}}(|Aut(U_{\gamma^{\prime}})|)^{1_{\gamma^{\prime}\text{ is
non-trivial}}}}$

and we have SOS-symmetric coefficient matrices
$\\{H^{\prime}_{\gamma}:\gamma\in\Gamma\\}$ such that the following conditions
hold:

  1. 1.

For all $U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$

  2. 2.

For all $U\in\mathcal{I}_{mid}$ and $\tau\in\mathcal{M}_{U}$,

$\left[{\begin{array}[]{cc}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H^{T}_{\tau}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{array}}\right]\succeq
0$

  3. 3.

For all $U,V\in\mathcal{I}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}{N(\gamma)}^{2}{B(\gamma)^{2}}H^{-\gamma,\gamma}_{Id_{V}}\preceq
H^{\prime}_{\gamma}$

then

$\Lambda\succeq\frac{1}{2}\left(\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\right)-3\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

If it is also true that

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

then $\Lambda\succeq 0$.

###### Proof.

We make the following observations:

  1. 1.

By Theorem 8.2,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{fact}_{\tau}(H_{\tau})}\succeq(1-2\varepsilon^{\prime})\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}}$

  2. 2.

By Corollary 8.22,

$\sum_{U\in\mathcal{I}_{mid}}{\left(M^{fact}_{Id_{U}}(H_{Id_{U}})-M^{orth}_{Id_{U}}(H_{Id_{U}})\right)}\preceq{\varepsilon^{\prime}}\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}+2\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{*,U}}{\frac{M^{fact}_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma})}{c(\gamma)|Aut(U_{\gamma})|}}}$

  3. 3.

By Corollary 8.23,

$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{\left(M^{fact}_{\tau}(H_{\tau})-M^{orth}_{\tau}(H_{\tau})\right)}}\preceq$
$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{\left(\frac{2{\varepsilon^{\prime}}}{|Aut(U)|c(\tau)}M^{fact}_{Id_{U}}(H_{Id_{U}})+4\sum_{\gamma\in\Gamma_{*,U}}{\frac{B(\gamma)^{2}N(\gamma)^{2}{c(\gamma)}}{|Aut(U_{\gamma})|\cdot|Aut(U)|c(\tau)}M^{fact}_{Id_{U_{\gamma}}}(H_{Id_{U}}^{-\gamma,\gamma})}\right)}}\preceq$
$\displaystyle
2{\varepsilon^{\prime}}^{2}\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}+4{\varepsilon^{\prime}}\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{*,U}}{\frac{M^{fact}_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma})}{c(\gamma)|Aut(U_{\gamma})|}}}$

  4. 4.

$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{*,U}}{\frac{M^{fact}_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma})}{c(\gamma)|Aut(U_{\gamma})|}}}=\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{*,U}}{\frac{M^{fact}_{Id_{U_{\gamma}}}(H_{Id_{U_{\gamma}}})+\left(M^{fact}_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma})-M^{fact}_{Id_{U_{\gamma}}}(H_{Id_{U_{\gamma}}})\right)}{c(\gamma)|Aut(U_{\gamma})|}}}\preceq$
$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{*,U}}{\frac{M^{fact}_{Id_{U_{\gamma}}}(H_{Id_{U_{\gamma}}})}{c(\gamma)|Aut(U_{\gamma})|}}}+\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma},H_{Id_{U_{\gamma}}})}{|Aut(U_{\gamma})|c(\gamma)}}}\right)Id_{sym}\preceq$
$\displaystyle{\varepsilon^{\prime}}\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{U}(H_{Id_{U}})}+\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma},H_{Id_{U_{\gamma}}})}{|Aut(U_{\gamma})|c(\gamma)}}}\right)Id_{sym}$

Putting everything together,

$\displaystyle\Lambda=\sum_{U\in\mathcal{I}_{mid}}{M^{orth}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{orth}_{\tau}(H_{\tau})}}=$
$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}+\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{M^{fact}_{\tau}(H_{\tau})}}+\sum_{U\in\mathcal{I}_{mid}}{\left(M^{fact}_{Id_{U}}(H_{Id_{U}})-M^{orth}_{Id_{U}}(H_{Id_{U}})\right)}+$
$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{\sum_{\tau\in\mathcal{M}_{U}}{\left(M^{fact}_{\tau}(H_{\tau})-M^{orth}_{\tau}(H_{\tau})\right)}}\succeq$
$\displaystyle(1-3{\varepsilon^{\prime}}-2{\varepsilon^{\prime}}^{2})\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}-(2+4\varepsilon^{\prime})\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{*,U}}{\frac{M^{fact}_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma})}{c(\gamma)|Aut(U_{\gamma})|}}}\succeq$
$\displaystyle(1-5{\varepsilon^{\prime}}-6{\varepsilon^{\prime}}^{2})\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}-(2+4\varepsilon^{\prime})\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma},H_{Id_{U_{\gamma}}})}{|Aut(U_{\gamma})|c(\gamma)}}}\right)Id_{sym}\succeq$
$\displaystyle\frac{1}{2}\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}(H_{Id_{U}})}-3\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U_{\gamma}}}(H^{\prime}_{\gamma},H_{Id_{U_{\gamma}}})}{|Aut(U_{\gamma})|c(\gamma)}}}\right)Id_{sym}$

##  9 Choosing the functions $B_{norm}(\alpha)$, $B(\gamma)$, $N(\gamma)$, and
$c(\alpha)$

In this subsection, we give functions $B_{norm}(\alpha)$, $B(\gamma)$,
$N(\gamma)$, and $c(\alpha)$ which satisfy the conditions needed for our
machinery.

###  9.1 Theorem Statements

Recall the following definitions from Section 7.10.

######  Definition 9.1.

We define $S_{\alpha}$ to be the leftmost minimum vertex separator of $\alpha$

######  Definition 9.2 (Simplified Isolated Vertices).

Under our simplifying assumptions, we define

$I_{\alpha}=\\{v\in W_{\alpha}:v\text{ is not incident to any edges in
}E(\alpha)\\}$

######  Theorem 9.3 (Simplified $B_{norm}(\alpha)$, $B(\gamma)$, $N(\gamma)$,
and $c(\alpha)$).

Under our simplifying assumptions, for all
$\varepsilon,\varepsilon^{\prime}>0$ and all $D_{V}\in\mathbb{N}$, if we take

  1. 1.

$q=3\left\lceil{{D_{V}}ln(n)+\frac{ln(\frac{1}{\varepsilon})}{3}+{D_{V}}ln(5)+3{D^{2}_{V}}ln(2)}\right\rceil$

  2. 2.

$B_{vertex}=6{D_{V}}\sqrt[4]{2eq}$

  3. 3.

$B_{norm}(\alpha)={B_{vertex}^{|V(\alpha)\setminus
U_{\alpha}|+|V(\alpha)\setminus
V_{\alpha}|}}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}$

  4. 4.

$B(\gamma)=B_{vertex}^{|V(\gamma)\setminus U_{\gamma}|+|V(\gamma)\setminus
V_{\gamma}|}n^{\frac{w(V(\gamma)\setminus U_{\gamma})}{2}}$

  5. 5.

$N(\gamma)=(3D_{V})^{2|V(\gamma)\setminus V_{\gamma}|+|V(\gamma)\setminus
U_{\gamma}|}$

  6. 6.

$c(\alpha)=\frac{5(3D_{V})^{|U_{\alpha}\setminus
V_{\alpha}|+|V_{\alpha}\setminus
U_{\alpha}|+2|E(\alpha)|}2^{|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|}}{\varepsilon^{\prime}}$

then the following conditions hold:

  1. 1.

With probability at least $(1-\varepsilon)$,
$\forall\alpha\in\mathcal{M}^{\prime}$, $||M_{\alpha}||\leq B_{norm}(\alpha)$

  2. 2.

For all $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$,
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$, and
intersection patterns $P\in\mathcal{P}_{\gamma,\tau,\gamma^{\prime}}$,

$B_{norm}(\tau_{P})\leq B(\gamma)B(\gamma^{\prime})B_{norm}(\tau)$

  3. 3.

For all composable $\gamma_{1},\gamma_{2}$,
$B(\gamma_{1})B(\gamma_{2})=B(\gamma_{1}\circ\gamma_{2})$.

  4. 4.

$\forall
U\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{U,*}}{\frac{1}{|Aut(U)|c(\gamma)}}<\varepsilon^{\prime}$

  5. 5.

$\forall
V\in\mathcal{I}_{mid},\sum_{\gamma\in\Gamma_{*,V}}{\frac{1}{|Aut(U_{\gamma})|c(\gamma)}}<\varepsilon^{\prime}$

  6. 6.

$\forall
U\in\mathcal{I}_{mid},\sum_{\tau\in\mathcal{M}_{U}}{\frac{1}{|Aut(U)|c(\tau)}}<\varepsilon^{\prime}$

  7. 7.

For all $\tau\in\mathcal{M}^{\prime}$,
$\gamma\in\Gamma_{*,U_{\tau}}\cup\\{Id_{U_{\tau}}\\}$, and
$\gamma^{\prime}\in\Gamma_{*,V_{\tau}}\cup\\{Id_{V_{\tau}}\\}$,

$\displaystyle\sum_{j>0}{\sum_{\gamma_{1},\gamma^{\prime}_{1},\cdots,\gamma_{j},\gamma^{\prime}_{j}\in\Gamma_{\gamma,\gamma^{\prime},j}}{\prod_{i:\gamma_{i}\text{
is non-