$\eta=\frac{1}{\sqrt{n}}$ kicks in. This inequality means that an extra decay
factor of $\eta^{2}=\frac{1}{n}$ is available to us when we compare to the
”expected pseudocalibration” coefficient of $\beta$. We will use this factor
to charge the new square vertex of degree $0$.

We now make these ideas formal.

Let $Q=U_{\beta}\cap V_{\beta},P=(U_{\beta}\cup V_{\beta})\setminus Q$ and let
$P^{\prime}$ be the set of degree $1$ square vertices in $\beta$ that are not
in $S_{min}$. Let $s_{0}$ be the number of degree $0$ square vertices in
$V(\beta)\setminus Q$. All the square vertices outside $P^{\prime}\cup Q\cup
S_{min}$ have degree at least $2$, let there be $s_{\geq 2}$ of them.

Because of parity constraints, Remark 4.18, and because there are no circle
vertices in $U_{\beta}\cup V_{\beta}$, all circle vertices have even degree in
$\beta$. Let $c_{0}$ be the number of degree $0$ circle vertices in $\beta$.
Let $c_{2},c_{\geq 4}$ be the number of degree $2$ circle vertices and the
number of circle vertices of degree at least $4$ in $V(\beta)\setminus
S_{min}$ respectively. Then, we have

$n^{\frac{w(V(\beta))-w(S_{\min})+w(W_{iso})}{2}}\leq
n^{\frac{|P^{\prime}|+s_{\geq 2}+(1.5-\varepsilon)(c_{2}+c_{\geq 4})}{2}}\cdot
n^{s_{0}+(1.5-\varepsilon)c_{0}}$

Using $\eta=\frac{1}{\sqrt{n}}$, it suffices to show

$\displaystyle\left\lvert E(\alpha)\right\rvert+$
$\displaystyle(|U_{\alpha}|+|V_{\alpha}|-|U_{\beta}|-|V_{\beta}|)$
$\displaystyle\geq|P^{\prime}|+s_{\geq 2}+(1.5-\varepsilon)(c_{2}+c_{\geq
4})+2s_{0}+2(1.5-\varepsilon)c_{0}+\Omega(\varepsilon\left\lvert
E(\alpha)\right\rvert)$

There can be many ways to collapse $\alpha$ to $\beta$, fix any one. We first
use a charging argument for the degree $0$ square vertices.

######  Lemma 4.45.

$|U_{\alpha}|+|V_{\alpha}|-|U_{\beta}|-|V_{\beta}|\geq 2s_{0}$

###### Proof.

In the collapse process, in each step, a vertex $\scalebox{0.85}{\footnotesize
\leavevmode\hbox to9.48pt{\vbox to9.48pt{\pgfpicture\makeatletter\hbox{\hskip
4.74158pt\lower-4.74158pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{}{}{}{{}}{}{{}{}}{{}{}}{}{{}{}}{}{{}{}}{}{{}\pgfsys@moveto{4.54158pt}{4.54158pt}\pgfsys@lineto{-4.54158pt}{4.54158pt}\pgfsys@lineto{-4.54158pt}{-4.54158pt}\pgfsys@lineto{4.54158pt}{-4.54158pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.71138pt}{-2.63809pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$i$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\in
U_{\gamma}\setminus(U_{\gamma}\cap V_{\gamma})$ or
$\scalebox{0.85}{\footnotesize \leavevmode\hbox to9.48pt{\vbox
to9.48pt{\pgfpicture\makeatletter\hbox{\hskip 4.74158pt\lower-4.74158pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{}{}{}{{}}{}{{}{}}{{}{}}{}{{}{}}{}{{}{}}{}{{}\pgfsys@moveto{4.54158pt}{4.54158pt}\pgfsys@lineto{-4.54158pt}{4.54158pt}\pgfsys@lineto{-4.54158pt}{-4.54158pt}\pgfsys@lineto{4.54158pt}{-4.54158pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.71138pt}{-2.63809pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$i$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\in
V_{\gamma}\setminus(U_{\gamma}\cap V_{\gamma})$ of degree $1$ in an
intermediate shape $\gamma$ collapses with another square vertex $k$ . We have
that $|U_{\gamma}|+|V_{\gamma}|$ decreases precisely when $i$ collapses with
$\scalebox{0.85}{\footnotesize \leavevmode\hbox to11.83pt{\vbox
to11.83pt{\pgfpicture\makeatletter\hbox{\hskip 5.91579pt\lower-5.91579pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{}{}{}{{}}{}{{}{}}{{}{}}{}{{}{}}{}{{}{}}{}{{}\pgfsys@moveto{5.71579pt}{5.71579pt}\pgfsys@lineto{-5.71579pt}{5.71579pt}\pgfsys@lineto{-5.71579pt}{-5.71579pt}\pgfsys@lineto{5.71579pt}{-5.71579pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.54167pt}{-2.77777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$k$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\in U_{\gamma}$
(resp. $\scalebox{0.85}{\footnotesize \leavevmode\hbox to11.83pt{\vbox
to11.83pt{\pgfpicture\makeatletter\hbox{\hskip 5.91579pt\lower-5.91579pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{}{}{}{{}}{}{{}{}}{{}{}}{}{{}{}}{}{{}{}}{}{{}\pgfsys@moveto{5.71579pt}{5.71579pt}\pgfsys@lineto{-5.71579pt}{5.71579pt}\pgfsys@lineto{-5.71579pt}{-5.71579pt}\pgfsys@lineto{5.71579pt}{-5.71579pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.54167pt}{-2.77777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$k$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\in V_{\gamma}$). In
either case, the quantity decreases by exactly $2$ which we allocate to this
new merged vertex. Each degree $0$ square vertex in $V(\beta)\setminus Q$ must
have arisen from a collapse, and hence must have had at least an additive
quantity of $2$ allocated to it. This proves that
$|U_{\alpha}|+|V_{\alpha}|-|U_{\beta}|-|V_{\beta}|\geq 2s_{0}$.

We will now prove a structural lemma.

######  Lemma 4.46.

Any vertex $u$ that has degree at least $2$ in $V(\beta)\setminus S_{min}$ is
adjacent to at most $1$ vertex of $P^{\prime}$.

###### Proof.

Observe that $u$ cannot be adjacent to $3$ vertices in $P^{\prime}$ because
otherwise, at least $2$ of them would be in $U_{\beta}\setminus Q$ or in
$V_{\beta}\setminus Q$ which means $\beta$ would be a spider which is a
contradiction. If $u$ is adjacent to $2$ vertices in $P^{\prime}$, then one of
them is in $U_{\beta}\setminus Q$ and the other is in $V_{\beta}\setminus Q$
respectively. Since both of these vertices are not in $S_{min}$, it follows
that $u$ is in $S_{min}$ since there is no path from $U_{\beta}$ to
$V_{\beta}$ that doesn’t pass through $S_{min}$. This is a contradiction.
Therefore, $u$ is adjacent to at most $1$ vertex in $P^{\prime}$.

This lemma immediately implies $|P^{\prime}|\leq c_{2}+c_{\geq 4}$.

To account for edges of $\alpha$ that are not in $\beta$, we let
$\widetilde{\beta}$ be the result of improperly collapsing $\alpha$ to
$\beta$; note that $\left\lvert E(\alpha)\right\rvert=\left\lvert
E(\widetilde{\beta})\right\rvert$. We call the edges that disappeared when
properly collapsing “phantom” edges. Let
$\deg_{\widetilde{\beta}}(\scalebox{0.85}{\footnotesize \leavevmode\hbox
to9.48pt{\vbox to9.48pt{\pgfpicture\makeatletter\hbox{\hskip
4.74158pt\lower-4.74158pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{}{}{}{{}}{}{{}{}}{{}{}}{}{{}{}}{}{{}{}}{}{{}\pgfsys@moveto{4.54158pt}{4.54158pt}\pgfsys@lineto{-4.54158pt}{4.54158pt}\pgfsys@lineto{-4.54158pt}{-4.54158pt}\pgfsys@lineto{4.54158pt}{-4.54158pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.71138pt}{-2.63809pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$i$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})$ (resp.
$\deg_{\widetilde{\beta}}(\scalebox{0.85}{\footnotesize \leavevmode\hbox
to12.49pt{\vbox to12.49pt{\pgfpicture\makeatletter\hbox{\hskip
6.2437pt\lower-6.2437pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.0437pt}{0.0pt}\pgfsys@curveto{6.0437pt}{3.33788pt}{3.33788pt}{6.0437pt}{0.0pt}{6.0437pt}\pgfsys@curveto{-3.33788pt}{6.0437pt}{-6.0437pt}{3.33788pt}{-6.0437pt}{0.0pt}\pgfsys@curveto{-6.0437pt}{-3.33788pt}{-3.33788pt}{-6.0437pt}{0.0pt}{-6.0437pt}\pgfsys@curveto{3.33788pt}{-6.0437pt}{6.0437pt}{-3.33788pt}{6.0437pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.62317pt}{-1.72221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$u$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})$) denote the degree
of vertex $i$ (resp. $u$ ) in $\widetilde{\beta}$. Observe that any circle
vertex $u$ in $V(\beta)$ has
$deg_{\widetilde{\beta}}(\scalebox{0.85}{\footnotesize \leavevmode\hbox
to12.49pt{\vbox to12.49pt{\pgfpicture\makeatletter\hbox{\hskip
6.2437pt\lower-6.2437pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.0437pt}{0.0pt}\pgfsys@curveto{6.0437pt}{3.33788pt}{3.33788pt}{6.0437pt}{0.0pt}{6.0437pt}\pgfsys@curveto{-3.33788pt}{6.0437pt}{-6.0437pt}{3.33788pt}{-6.0437pt}{0.0pt}\pgfsys@curveto{-6.0437pt}{-3.33788pt}{-3.33788pt}{-6.0437pt}{0.0pt}{-6.0437pt}\pgfsys@curveto{3.33788pt}{-6.0437pt}{6.0437pt}{-3.33788pt}{6.0437pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.62317pt}{-1.72221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$u$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})\geq 4$.

######  Lemma 4.47.

$\left\lvert E(\alpha)\right\rvert\geq|P^{\prime}|+s_{\geq
2}+(1.5-\varepsilon)(c_{2}+c_{\geq
4})+2(1.5-\varepsilon)c_{0}+\Omega(\varepsilon\left\lvert
E(\alpha)\right\rvert)$

###### Proof.

We will use the following charging scheme. Each edge of $\beta$ incident on
$P^{\prime}$ allocates $1$ to the incident square vertex, which is in
$P^{\prime}$. Every other edge of $\beta$ allocates $\frac{1}{2}$ to the
incident square vertex and $\frac{1}{2}-\frac{\varepsilon}{10}$ to the
incident circle vertex. Each phantom edge allocates $1-\frac{\varepsilon}{10}$
to the incident circle vertex $u$ . So, a total of
$\frac{\varepsilon}{10}(\left\lvert E(\alpha)\right\rvert-|P^{\prime}|)$ has
not been allocated.

All square vertices in $P^{\prime}$ have been allocated a value of $1$. And
observe that all square vertices of degree at least $2$ in $\beta$ have been
allocated at least $1$ from the incident edges of $\beta$, for a total value
of $s_{\geq 2}$. So, the square vertices get a total allocation of at least
$|P^{\prime}|+s_{\geq 2}$.

Consider any degree-$0$ circle vertex $u$ in $V(\beta)$. It must be incident
to at least $4$ phantom edges and hence, must be allocated at least a value of
$4(1-\frac{\varepsilon}{10})>2(1.5-\varepsilon)$. Hence, the degree-$0$ circle
vertices in $V(\beta$) have a total allocation of at least
$2(1.5-\varepsilon)c_{0}$.

Suppose the degree of $u$ in $V(\beta)$ is $2$. Then, it is incident on at
least $2$ phantom edges. By Lemma 4.46, it is also adjacent to at most one
vertex of $P^{\prime}$ and so, must have been allocated a value of at least
$2(1-\frac{\varepsilon}{10})+(deg_{\widetilde{\beta}}(\scalebox{0.85}{\footnotesize
\leavevmode\hbox to12.49pt{\vbox
to12.49pt{\pgfpicture\makeatletter\hbox{\hskip 6.2437pt\lower-6.2437pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.0437pt}{0.0pt}\pgfsys@curveto{6.0437pt}{3.33788pt}{3.33788pt}{6.0437pt}{0.0pt}{6.0437pt}\pgfsys@curveto{-3.33788pt}{6.0437pt}{-6.0437pt}{3.33788pt}{-6.0437pt}{0.0pt}\pgfsys@curveto{-6.0437pt}{-3.33788pt}{-3.33788pt}{-6.0437pt}{0.0pt}{-6.0437pt}\pgfsys@curveto{3.33788pt}{-6.0437pt}{6.0437pt}{-3.33788pt}{6.0437pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.62317pt}{-1.72221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$u$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})-3)(\frac{1}{2}-\frac{\varepsilon}{10})$.
This is at least $1.5-\varepsilon+\frac{\varepsilon}{10}$.

Suppose the degree of $u$ in $V(\beta)$ is at least $4$. By Lemma 4.46, it is
adjacent to at most one vertex of $P^{\prime}$. Then it must have been
allocated a value of at least
$(deg_{\widetilde{\beta}}(\scalebox{0.85}{\footnotesize \leavevmode\hbox
to12.49pt{\vbox to12.49pt{\pgfpicture\makeatletter\hbox{\hskip
6.2437pt\lower-6.2437pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.0437pt}{0.0pt}\pgfsys@curveto{6.0437pt}{3.33788pt}{3.33788pt}{6.0437pt}{0.0pt}{6.0437pt}\pgfsys@curveto{-3.33788pt}{6.0437pt}{-6.0437pt}{3.33788pt}{-6.0437pt}{0.0pt}\pgfsys@curveto{-6.0437pt}{-3.33788pt}{-3.33788pt}{-6.0437pt}{0.0pt}{-6.0437pt}\pgfsys@curveto{3.33788pt}{-6.0437pt}{6.0437pt}{-3.33788pt}{6.0437pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.62317pt}{-1.72221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$u$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})-1)(\frac{1}{2}-\frac{\varepsilon}{10})$.
Using $deg_{\widetilde{\beta}}(\scalebox{0.85}{\footnotesize \leavevmode\hbox
to12.49pt{\vbox to12.49pt{\pgfpicture\makeatletter\hbox{\hskip
6.2437pt\lower-6.2437pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.0437pt}{0.0pt}\pgfsys@curveto{6.0437pt}{3.33788pt}{3.33788pt}{6.0437pt}{0.0pt}{6.0437pt}\pgfsys@curveto{-3.33788pt}{6.0437pt}{-6.0437pt}{3.33788pt}{-6.0437pt}{0.0pt}\pgfsys@curveto{-6.0437pt}{-3.33788pt}{-3.33788pt}{-6.0437pt}{0.0pt}{-6.0437pt}\pgfsys@curveto{3.33788pt}{-6.0437pt}{6.0437pt}{-3.33788pt}{6.0437pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.62317pt}{-1.72221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$u$ }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}})\geq 4$, this is at
least $1.5-\varepsilon+\frac{\varepsilon}{10}$.

This implies

$\left\lvert E(\alpha)\right\rvert\geq|P^{\prime}|+s_{\geq
2}+2(1.5-\varepsilon)c_{0}+(1.5-\varepsilon+\frac{\varepsilon}{10})(c_{2}+c_{\geq
4})+\frac{\varepsilon}{10}(\left\lvert E(\alpha)\right\rvert-|P^{\prime}|)$

Using $|P^{\prime}|\leq c_{2}+c_{\geq 4}$ completes the proof.

Adding Lemma 4.45 and Lemma 4.47, we get the result.

######  Corollary 4.48.

If $\beta$ is a nontrivial non-spider and $\beta\in W(\alpha)$ for some spider
$\alpha\in{\mathcal{L}}$, then

$\eta^{\left\lvert U_{\alpha}\right\rvert+\left\lvert
V_{\alpha}\right\rvert}\cdot\frac{1}{n^{\left\lvert
E(\alpha)\right\rvert/2}}\left\lVert
M_{\beta}\right\rVert\leq\eta^{\left\lvert U_{\beta}\right\rvert+\left\lvert
V_{\beta}\right\rvert}\cdot\frac{1}{n^{\Omega(\varepsilon\left\lvert
E(\alpha)\right\rvert)}}$

###### Proof.

From Lemma 6.3, we have

$\left\lVert M_{\beta}\right\rVert\leq 2\cdot\left(\left\lvert
V(\beta)\right\rvert\cdot(1+\left\lvert
E(\beta)\right\rvert)\cdot\log(n)\right)^{C\cdot(\left\lvert
V_{rel}(\beta)\right\rvert+\left\lvert E(\beta)\right\rvert)}\cdot
n^{\frac{w(V(\beta))-w(S_{\min})+w(W_{iso})}{2}}$

We have $\left\lvert V(\beta)\right\rvert\cdot(1+\left\lvert
E(\beta)\right\rvert)\cdot\log(n)\leq n^{O(\tau)}$. Also,
$|V_{rel}(\beta)|\leq 2(|E(\alpha)|+|E(\beta)|)$ since all the degree $0$
vertices in $V_{rel}(\beta)$ would have had vertices of $V_{rel}(\alpha)$
collapse into it in the chain of collapses and there are no degree $0$
vertices in $V_{rel}(\alpha)$. Finally, since $|E(\alpha)|\geq|E(\beta)|$, the
factor $2\cdot(\left\lvert V(\beta)\right\rvert\cdot(1+\left\lvert
E(\beta)\right\rvert)\cdot\log(n))^{C\cdot(\left\lvert
V_{rel}(\beta)\right\rvert+\left\lvert E(\beta)\right\rvert)}$ can be absorbed
into $\frac{1}{n^{\Omega(\varepsilon\left\lvert E(\alpha)\right\rvert)}}$. The
result follows from Lemma 4.44.

######  Proposition 4.49.

If $\beta$ is a trivial shape, $\lambda_{\beta}^{+}=\lambda_{\beta}$.

###### Proof.

A trivial shape cannot appear in $W(\alpha)$ for any $\alpha$, since every
collapse of a spider always keeps its circle vertices around.

######  Lemma 4.50.

For $k,l\in\\{0,1,\dots,D/2\\}$, let ${\mathcal{B}}_{k,l}$ denote the set of
nontrivial non-spiders on block $(k,l)$. Then

$\displaystyle\sum_{\beta\in{\mathcal{B}}_{k,l}}\left\lvert\lambda_{\beta}^{+}\right\rvert\left\lVert
M_{\beta}\right\rVert\leq\eta^{k+l}\cdot\frac{1}{n^{\Omega(\varepsilon)}}$

###### Proof.

$\displaystyle\displaystyle\sum_{\beta\in{\mathcal{B}}_{k,l}}\left\lVert\lambda_{\beta}^{+}M_{\beta}\right\rVert\leq$
$\displaystyle\sum_{\beta\in{\mathcal{B}}_{k,l}}\left\lvert\lambda_{\beta}\right\rvert\left\lVert
M_{\beta}\right\rVert+\sum_{\beta\in{\mathcal{B}}_{k,l}}\sum_{\begin{subarray}{c}\text{spiders
}\alpha:\\\ \beta\in W(\alpha)\end{subarray}}\left\lvert
v_{\beta}\right\rvert\left\lvert\lambda_{\alpha}\right\rvert\left\lVert
M_{\beta}\right\rVert$

To bound the first term, we checked previously in Corollary 4.14 that the
total norm of nontrivial non-spiders appearing in the pseudocalibration (i.e.
this term) is $\eta^{k+l}o_{n}(1)$. For the second term, via Lemma 4.41 we
have a bound on the accumulations $v_{\gamma}$ of one spider on one non-
spider, so it is at most

$\leq\sum_{\beta\in{\mathcal{B}}_{k,l}}\displaystyle\sum_{\begin{subarray}{c}\text{spiders
}\alpha:\\\ \beta\in W(\alpha)\end{subarray}}(C_{1}\left\lvert
V(\alpha)\right\rvert\cdot\left\lvert E(\alpha)\right\rvert)^{C_{2}\left\lvert
E(\alpha)\right\rvert}\cdot\left\lvert\lambda_{\alpha}\right\rvert\left\lVert
M_{\beta}\right\rVert.$

Use the bound on the coefficients $\left\lvert\lambda_{\alpha}\right\rvert$,
Proposition 4.13,

$\displaystyle\leq\sum_{\beta\in{\mathcal{B}}_{k,l}}\displaystyle\sum_{\begin{subarray}{c}\text{spiders
}\alpha:\\\ \beta\in W(\alpha)\end{subarray}}(C_{1}\left\lvert
V(\alpha)\right\rvert\cdot\left\lvert E(\alpha)\right\rvert)^{C_{2}\left\lvert
E(\alpha)\right\rvert}\cdot\eta^{\left\lvert
U_{\alpha}\right\rvert+\left\lvert
V_{\alpha}\right\rvert}\cdot\frac{\left\lvert
E(\alpha)\right\rvert^{3\left\lvert E(\alpha)\right\rvert}}{n^{\left\lvert
E(\alpha)\right\rvert/2}}\cdot\left\lVert M_{\beta}\right\rVert$

Invoking the norm bound for non-spiders which are collapses, Corollary 4.48,

$\displaystyle\leq\eta^{k+l}\cdot\sum_{\beta\in{\mathcal{B}}_{k,l}}\displaystyle\sum_{\begin{subarray}{c}\text{spiders
}\alpha:\\\ \beta\in W(\alpha)\end{subarray}}\left(\frac{C_{1}\left\lvert
V(\alpha)\right\rvert\cdot\left\lvert
E(\alpha)\right\rvert}{n^{\Omega(\varepsilon)}}\right)^{C_{2}^{\prime}\left\lvert
E(\alpha)\right\rvert}$
$\displaystyle\leq\eta^{k+l}\cdot\sum_{\beta\in{\mathcal{B}}_{k,l}}\displaystyle\sum_{\begin{subarray}{c}\text{spiders
}\alpha:\\\ \beta\in W(\alpha)\end{subarray}}\left(\frac{C_{1}n^{\tau}\cdot
n^{\tau}}{n^{\Omega(\varepsilon)}}\right)^{C_{2}^{\prime}\left\lvert
E(\alpha)\right\rvert}.$

Bound the sum over all spiders by the sum over all shapes. By Proposition
4.12, the number of shapes with $i$ edges is $n^{O(\tau(i+1))}$. Summing by
the number of edges, observe that $\left\lvert
E(\alpha)\right\rvert\geq\max(\left\lvert E(\beta)\right\rvert,2)$ since
spiders always have at least $2$ edges.

$\displaystyle\leq\eta^{k+l}\sum_{\beta\in{\mathcal{B}}_{k,l}}\displaystyle\sum_{i=\max(\left\lvert
E(\beta)\right\rvert,2)}^{\infty}n^{O(\tau(i+1))}\cdot\left(\frac{C_{1}n^{\tau}\cdot
n^{\tau}}{n^{\Omega(\varepsilon)}}\right)^{C_{2}^{\prime}i}$
$\displaystyle\leq\eta^{k+l}\sum_{\beta\in{\mathcal{B}}_{k,l}}\frac{1}{n^{\Omega(\varepsilon\max(\left\lvert
E(\beta)\right\rvert,2))}}$
$\displaystyle\leq\eta^{k+l}\sum_{i=0}^{\infty}\frac{n^{O(\delta(i+1))}}{n^{\Omega(\varepsilon\max(i,2))}}$
$\displaystyle=\eta^{k+l}\cdot\frac{1}{n^{\Omega(\varepsilon)}}\qquad\hbox{\vrule
width=6.0pt,height=6.0pt,depth=0.0pt}$

######  Corollary 4.51.

For $k\in\\{0,\dots,D/2\\}$, the $(k,k)$ block of ${\mathcal{M}}^{+}$ has
minimum singular value at least
$\eta^{2k}(1-\frac{1}{n^{\Omega(\varepsilon)}})$, and for
$k,l\in\\{0,\dots,D/2\\},l\neq k$, the $(k,l)$ off-diagonal block has norm at
most $\eta^{k+l}\cdot\frac{1}{n^{\Omega(\varepsilon)}}$.

###### Proof.

By Proposition 4.49 the identity matrix appears on the $(k,k)$ blocks with
coefficient $\eta^{2k}$. By construction, ${\mathcal{M}}^{+}$ has no spider
shapes. By Lemma 4.50, the total norm of the non-spider shapes on the $(k,l)$
block is at most $\eta^{k+l}\cdot\frac{1}{n^{\Omega(\varepsilon)}}$.

######  Theorem 4.52.

W.h.p. ${\mathcal{M}}_{fix}\succeq 0$.

###### Proof.

For any $x\in\operatorname{Null}({\mathcal{M}}_{fix})$, we of course have
$x^{\intercal}{\mathcal{M}}_{fix}x=0$. For any
$x\perp\operatorname{Null}({\mathcal{M}}_{fix})$ with $\left\lVert
x\right\rVert_{2}=1$,

$\displaystyle x^{\intercal}{\mathcal{M}}_{fix}x$
$\displaystyle=x^{\intercal}({\mathcal{M}}+{\mathcal{E}})x$
$\displaystyle=x^{\intercal}{\mathcal{M}}^{+}x+x^{\intercal}\left(\displaystyle\sum_{\text{spiders
}\alpha}\lambda_{\alpha}\left({\mathcal{M}}_{\alpha}-\sum_{\text{leaves
}\gamma\text{ of
}W(\alpha)}v_{\gamma}M_{\gamma}\right)\right)x+x^{\intercal}{\mathcal{E}}x$
$\displaystyle=x^{\intercal}({\mathcal{M}}^{+}+{\mathcal{E}})x$

where the last equality follows from Proposition 4.37. Because the norm bound
on ${\mathcal{E}}$ is significantly less than $\eta^{D}=n^{-n^{\delta}}$ (see
[sklowerbounds]), the bound on the norm of each block of ${\mathcal{M}}^{+}$
in Corollary 4.51 also applies to the blocks of
${\mathcal{M}}^{+}+{\mathcal{E}}$. Therefore, we use Lemma 4.2 to conclude
${\mathcal{M}}^{+}+{\mathcal{E}}\succeq 0$ and the above expression is
nonnegative.

###  5 Sherrington-Kirkpatrick Lower Bounds

Here, we prove Theorem 1.5 and Theorem 1.2.

Recall that in the Planted Boolean Vector problem, we wish to optimize

$\operatorname{OPT}(V):=\frac{1}{n}\max_{b\in\\{\pm
1\\}^{n}}b^{\intercal}\Pi_{V}b,$

where $V$ is a uniformly random $p$-dimensional subspace of $\mathbb{R}^{n}$.

See 1.5

###### Proof.

We wish to produce an SoS solution $\widetilde{{\mathbb{E}}}$ on boolean
variables $b_{1},\ldots,b_{n}$ such that
$\widetilde{{\mathbb{E}}}[b^{\intercal}\Pi_{V}b]=n$. Instead of sampling a
uniformly random $p$-dimensional subspace $V$ of $\mathbb{R}^{n}$, we first
sample $d_{1},\ldots,d_{n}$ i.i.d. $p$-dimensional Gaussian vectors from
$\mathcal{N}(0,I)$, then form an $n$-by-$p$ matrix $A$ with rows
$d_{1},\dots,d_{n}$, and finally take $V$ to be the span of the columns of
$A$. Since the columns of $A$ are isotropic i.i.d. random Gaussian vectors, we
have that $V$ is a uniform $p$-dimensional subspace555Except for a zero
measure event.  of $\mathbb{R}^{n}$.

We will consider $V$ as the input for the Planted Boolean Vector problem while
the vectors $d_{1},\dots,d_{n}$ will be used to construct a pseudoexpectation
operator for the Planted Affine Planes problem666Note that the vectors $d_{u}$
are not “given” in the Planted Boolean Vector problem, though the construction
of $\widetilde{{\mathbb{E}}}$ is not required to be algorithmic in any sense
anyway.. Since $n\leq p^{3/2-\Omega(\varepsilon)}$, by Theorem 1.4, for all
$\delta\leq c\varepsilon$ for a constant $c>0$, w.h.p., there exists a
degree-$n^{\delta}$ pseudoexpectation operator
$\widetilde{{\mathbb{E}}}^{\prime}$ on formal variables
$v=(v_{1},\dots,v_{p})$ such that $\widetilde{{\mathbb{E}}}^{\prime}[\langle
v,d_{u}\rangle^{2}]=1$ for every $u\in[n]$.

Define $\widetilde{{\mathbb{E}}}$ by
$\widetilde{{\mathbb{E}}}[b_{u}]:=\widetilde{{\mathbb{E}}}^{\prime}[\langle
v,d_{u}\rangle]$ for all $u\in[n]$ and extending it to all polynomials on
$\\{b_{u}\\}$ by multilinearity. This is well defined because
$\widetilde{{\mathbb{E}}}^{\prime}[\langle v,d_{u}\rangle^{2}]=1$. Note that
$\widetilde{{\mathbb{E}}}$ is a valid pseudoexpectation operator of the same
degree as $\widetilde{{\mathbb{E}}}^{\prime}$. Finally, observe that

$\displaystyle\frac{1}{n}\widetilde{{\mathbb{E}}}[b^{\intercal}\Pi_{V}b]=\frac{1}{n}\widetilde{{\mathbb{E}}}^{\prime}[v^{\intercal}A^{\intercal}\Pi_{V}Av]=\frac{1}{n}\widetilde{{\mathbb{E}}}^{\prime}[v^{\intercal}A^{\intercal}Av]=1.$

Now we prove lower bounds for the Sherrington-Kirkpatrick problem, using a
reduction and proof due to [mohanty2020lifting]. We include it here for
completeness. Recall that the SK problem is to compute

$\operatorname{OPT}(W):=\max_{x\in\\{\pm 1\\}^{n}}x^{\intercal}Wx,$

where $W$ is sampled from $\operatorname{GOE}(n)$.

See 1.2

We will use the following standard results from random matrix theory of
$\operatorname{GOE}(n)$.

######  Fact 5.1.

Let $\lambda_{1}\geq\ldots\geq\lambda_{n}$ be the eigenvalues of
$W\sim\operatorname{GOE}(n)$ with corresponding normalized eigenvectors
$w_{1},\ldots,w_{n}$. Then,

  1. 1.

For every $p\in[n]$, the span of $w_{1},\ldots,w_{p}$ is a uniformly random
$p$-dimensional subspace of $\mathbb{R}^{n}$ (see e.g. [OVW16, Section 2]).

  2. 2.

W.h.p., $\lambda_{n^{0.67}}\geq(2-\operatorname{o}(1))\sqrt{n}$ (Corollary of
Wigner’s semicircle law [Wig93])

  * Proof of Theorem 1.2:  Let $p=n^{0.67}$ and $W\sim\operatorname{GOE}(n)$. Let $\lambda_{1}\geq\ldots\geq\lambda_{n}$ be the eigenvalues of $W$ with corresponding orthonormal set of eigenvectors $w_{1},\ldots,w_{n}$. By 5.1, we have that $\lambda_{p}\geq(2-\operatorname{o}(1))\sqrt{n}$ and that $w_{1},\ldots,w_{p}$ span a uniformly random $p$-dimensional subspace $V$ of $\mathbb{R}^{n}$.

We consider $V$ as the input of the Boolean Planted Vector problem and by
Theorem 1.5, for some constant $\delta>0$, w.h.p. there exists a
degree-$n^{\delta}$ pseudoexpectation operator $\widetilde{{\mathbb{E}}}$ such
that $\widetilde{{\mathbb{E}}}[x_{i}^{2}]=1$ and
$\widetilde{{\mathbb{E}}}[\sum_{i=1}^{p}\langle
x,w_{i}\rangle^{2}]=\widetilde{{\mathbb{E}}}[x^{\intercal}\Pi_{V}x]=n$. Now,

$\displaystyle\widetilde{{\mathbb{E}}}[x^{\intercal}Wx]$
$\displaystyle=\widetilde{{\mathbb{E}}}[\sum_{i=1}^{n}\lambda_{i}\langle
x,w_{i}\rangle^{2}]$
$\displaystyle\geq\lambda_{p}\widetilde{{\mathbb{E}}}[x^{\intercal}\Pi_{V}x]-\left\lvert\lambda_{n}\right\rvert\widetilde{{\mathbb{E}}}[\sum_{i=p+1}^{n}\langle
x,w_{i}\rangle^{2}]$
$\displaystyle\geq(2-\operatorname{o}(1))n^{3/2}-\left\lvert\lambda_{n}\right\rvert\widetilde{{\mathbb{E}}}[\langle
x,x\rangle-\sum_{i=1}^{p}\langle x,w_{i}\rangle^{2}]$
$\displaystyle=(2-\operatorname{o}(1))n^{3/2}.$

######  Remark 5.2.

Using the same proof as above, we can obtain Theorem 1.2 even if we were only
able to prove SoS lower bounds for Planted Affine Planes for some
$m=\omega(n)$. So, pushing the value of $m$ up to $n^{3/2-\varepsilon}$, which
is Theorem 1.4, offers only a modest improvement.

###  6 Omitted technical details

####  1 Norm Bounds

The precise norm bounds we use come from applying the trace power method in
[ahn2016graph], but qualitatively, the bounds from Chapter 1 also work. The
paper [ahn2016graph] uses a slightly different definition of matrix index.
They define a matrix index piece as a tuple of distinct elements from either
${\mathcal{C}}_{m}$ or ${\mathcal{S}}_{n}$ along with a fixed integer denoting
multiplicity. A matrix index is then a set of matrix index pieces. Our graph
matrix $M_{\alpha}$ appears as a submatrix of those matrices: for a given set
of square vertices, order the squares in increasing order in a tuple, and
assign it multiplicity 1. Hence the same norm bounds apply.

Boolean norm bounds:

######  Lemma 6.1.

Let $V_{rel}(\alpha):=V(\alpha)\setminus(U_{\alpha}\cap V_{\alpha})$. There is
a universal constant $C$ such that the following norm bound holds for all
proper shapes $\alpha$ w.h.p.:

$\left\lVert M_{\alpha}\right\rVert\leq 2\cdot\left(\left\lvert
V(\alpha)\right\rvert\cdot\log(n)\right)^{C\cdot\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$

###### Proof.

From Corollary 8.13 of [ahn2016graph], with probability at least
$1-\varepsilon$ for a fixed shape $\alpha$,

$\left\lVert M_{\alpha}\right\rVert\leq 2\left\lvert
V(\alpha)\right\rvert^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot\left(6e\left\lceil\frac{\log\left(\frac{n^{w(S_{\min})}}{\varepsilon}\right)}{6\left\lvert
V_{rel}(\alpha)\right\rvert}\right\rceil\right)^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$

Letting $N_{k}$ be the number of distinct shapes on $k$ vertices (either
circles or squares), we apply the corollary with
$\varepsilon=1/(mnN_{\left\lvert V(\alpha)\right\rvert})$. Union bounding, the
failure probability across all shapes of size $k$ is at most $1/mn$, and since
the number of vertices in a shape is at most $m+n\leq 2m$, we have a bound
that holds with high probability for all shapes. It remains to simplify the
exact bound.

######  Proposition 6.2.

$N_{k}\leq 8^{k}2^{k^{2}}$

###### Proof.

The following process forms all shapes on $k$ vertices: starting from $k$
formal variables, assign each variable to be either a circle or a square,
decide whether each variable is in $U_{\alpha}$ and/or $V_{\alpha}$, then
among the $k^{2}$ variable pairs put any number of edges.

We also bound $n^{w(S_{\min})}\leq(mn)^{\left\lvert V(\alpha)\right\rvert}$.

$\displaystyle\left\lVert M_{\alpha}\right\rVert$ $\displaystyle\leq
2\left\lvert V(\alpha)\right\rvert^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot\left(6e\left\lceil\frac{\log\left(n^{w(S_{\min})}\cdot
mnN_{\left\lvert V(\alpha)\right\rvert}\right)}{6\left\lvert
V_{rel}(\alpha)\right\rvert}\right\rceil\right)^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$ $\displaystyle\leq
2\left\lvert V(\alpha)\right\rvert^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot\left(12e\log\left(n^{w(S_{\min})}\cdot
mnN_{\left\lvert V(\alpha)\right\rvert}\right)\right)^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$ $\displaystyle\leq
2\left\lvert V(\alpha)\right\rvert^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot\left(12e\log\left((mn)^{\left\lvert
V(\alpha)\right\rvert}\cdot mn\cdot 8^{\left\lvert
V(\alpha)\right\rvert}2^{\left\lvert
V(\alpha)\right\rvert^{2}}\right)\right)^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$ $\displaystyle\leq
2\left\lvert V(\alpha)\right\rvert^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot\left(100e\left\lvert
V(\alpha)\right\rvert^{2}\log\left(mn\right)\right)^{\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$ $\displaystyle\leq
2\cdot\left(\left\lvert
V(\alpha)\right\rvert\cdot\log(mn)\right)^{3\cdot\left\lvert
V_{rel}(\alpha)\right\rvert}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$

Note that we now assume $m\leq n^{2}$.

We have the following norm bound for Hermite shapes. For a Hermite shape
$\alpha$, define the total size to be $\left\lvert
U_{\alpha}\right\rvert+\left\lvert V_{\alpha}\right\rvert+\left\lvert
W_{\alpha}\right\rvert+\left\lvert E(\alpha)\right\rvert$.

######  Lemma 6.3.

Let $V_{rel}(\alpha):=V(\alpha)\setminus(U_{\alpha}\cap V_{\alpha})$ as sets.
There is a universal constant $C$ such that the following norm bound holds for
all proper shapes $\alpha$ with total size at most $n$ w.h.p.:

$\left\lVert M_{\alpha}\right\rVert\leq 2\cdot\left(\left\lvert
V(\alpha)\right\rvert\cdot(1+\left\lvert
E(\alpha)\right\rvert)\cdot\log(n)\right)^{C\cdot(\left\lvert
V_{rel}(\alpha)\right\rvert+\left\lvert E(\alpha)\right\rvert)}\cdot
n^{\frac{w(V(\alpha))-w(S_{\min})+w(W_{iso})}{2}}$

The proof performs the same calculation starting from [ahn2016graph, Corollary
8.15]. Note that in our notation, $l(\alpha)=\left\lvert
E(\alpha)\right\rvert$. There is a further difference which is that
[ahn2016graph] uses normalized Hermite polynomials whereas we use unnormalized
Hermite polynomials; this contributes the additional term $\prod_{e\in
E(\alpha)}l(e)!\leq(1+\left\lvert E(\alpha)\right\rvert)^{\left\lvert
E(\alpha)\right\rvert}$. We must replace Proposition 6.2 with the following:

######  Proposition 6.4.

The number of Hermite shapes with total size $k$ is at most
$k2^{k}(k+1)^{2k+k^{2}}$.

###### Proof.

Such a shape has at most $k$ distinct variable vertices. Each of these is
either a circle or a square. Each variable can be in $U_{\alpha}$ with
multiplicity between 0 and (at most) $k$, and also in $V_{\alpha}$ with
multiplicity between 0 and $k$. The $k^{2}$ possible pairs of vertices can
have edge multiplicity in $E(\alpha)$ between 0 and $k$.

####  2 Properties of $e(k)$

In this section, we establish some properties of the $e(k)$ used in the
analysis. Recall that
$e(k)={\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots x_{k}\right]$
where $\mathcal{S}(\sqrt{n})\coloneqq\\{x\in\\{\pm
1\\}^{n}\mid\sum_{i=1}^{n}x_{i}=\sqrt{n}\\}$.

######  Claim 6.5.

$e(2)=0$.

###### Proof.

Fix $y\in\mathcal{S}(\sqrt{n})$. Note that $(\sum_{i=1}^{n}y_{i})^{2}=n$
implying $\sum_{i<j}y_{i}y_{j}=0$. Using this fact, we get

${\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}x_{2}\right]={\mathbb{E}}_{\sigma\in
S_{n}}y_{\sigma(1)}y_{\sigma(2)}=0,$

concluding the proof.

######  Definition 6.6.

We say that a tuple $\lambda=(\lambda_{1},\dots,\lambda_{k})$ of non-negative
integers is a partition of $k$ provided $\sum_{i=1}^{k}\lambda_{i}=k$ and
$\lambda_{1}\geq\cdots\geq\lambda_{k}$. We use the notation $\lambda\vdash k$
to denote a partition of $k$. We refer to $\lambda_{i}$ as a row/part of
$\lambda$.

In the following, we will dealing with polynomials that can be indexed by
integer partitions. For this reason, we now fix a notation for partitions and
some associated objects.

######  Definition 6.7.

The transpose of partition $\lambda=(\lambda_{1},\dots,\lambda_{k})$ is
denoted $\lambda^{t}$ and defined as
$\lambda^{t}_{i}=\left\lvert\\{j\in[k]\mid\lambda_{j}\geq i\\}\right\rvert$.

######  Remark 6.8.

For a partition $\lambda\vdash k$, $\lambda^{t}_{1}$ is the number of
rows/parts of $\lambda$.

######  Definition 6.9.

The automorphism group of a partition
$\operatorname{\operatorname{Aut}}(\lambda)\leq S_{\lambda^{t}_{1}}$ is the
group generated by transpositions $(i,j)$ of rows $\lambda_{i}=\lambda_{j}$.

######  Remark 6.10.

Let $\lambda\vdash k$ and $p_{1}(\lambda),\dots,p_{k}(\lambda)$ be such that
$p_{i}(\lambda)=\left\lvert\\{j\in[\lambda_{1}^{t}]\mid\lambda_{j}=i\\}\right\rvert$.
Then $\operatorname{\operatorname{Aut}}(\lambda)\simeq
S_{p_{1}}\times\cdots\times S_{p_{k}}$.

######  Lemma 6.11.

We have

$\sum_{\lambda\vdash
k}\frac{\lambda!}{\lambda_{1}!\cdots\lambda_{k}!}\cdot\frac{(n)_{\lambda^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]=n^{k/2}.$

###### Proof.

For $x\in\mathcal{S}(\sqrt{n})$, we have $(\sum_{i=1}^{n}x_{i})^{k}=n^{k/2}$.
Then expanding $(\sum_{i=1}^{n}x_{i})^{k}$ in the previous equations and
taking the expectation over $\mathcal{S}(\sqrt{n})$ on both sides yields the
result of the lemma (after appropriately collecting terms).

######  Claim 6.12.

Let $\lambda\vdash k$. We have

$(n)_{\lambda^{t}_{1}}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert\leq 3^{k^{3}}\cdot n^{k/2}.$

###### Proof.

We induct on $k$. For $k=1$, we have
$n\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\right]\right\rvert=\sqrt{n}\leq
3\cdot n^{1/2}$. Now, suppose $k\geq 2$. We consider three cases:

  1. 1.

Case $\lambda_{1}\geq 3$: Let $\lambda^{\prime}$ be the partition obtained
from $\lambda$ by removing two boxes from $\lambda_{1}$. Note that
$\lambda_{1}^{t}=(\lambda^{\prime})^{t}_{1}\leq k-2$ and
${\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}^{\prime}}\dots
x_{k-2}^{\lambda_{k-2}^{\prime}}\right]={\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k-2}^{\lambda_{k-2}}\right]$. By the induction hypothesis, we have
$(n)_{(\lambda^{\prime})^{t}_{1}}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}^{\prime}}\dots
x_{k-2}^{\lambda_{k-2}^{\prime}}\right]\right\rvert\leq 3^{(k-2)^{2}}\cdot
n^{(k-2)/2}$.

  2. 2.

Case $\lambda_{1}=2$: Let $\lambda^{\prime}$ be the partition obtained from
$\lambda$ by removing $\lambda_{1}$. Note that
$\lambda_{1}^{t}=(\lambda^{\prime})^{t}_{1}+1\leq k-2$. By the induction
hypothesis, we have

$\displaystyle(n)_{\lambda^{t}_{1}}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k-2}^{\lambda_{k-2}}\right]\right\rvert$ $\displaystyle\leq
n\cdot(n)_{(\lambda^{\prime})^{t}_{1}}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}^{\prime}}\dots
x_{k-2}^{\lambda_{k-2}^{\prime}}\right]\right\rvert$ $\displaystyle\leq
3^{(k-2)^{3}}\cdot n^{k/2}.$

  3. 3.

Case $\lambda_{1}=1$: To bound
$(n)_{k}\cdot{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]$, we use Lemma 6.11 and the two preceding cases.
Let $p(k)$ be the partition function, i.e., $p(k)=\left\lvert\\{\lambda\vdash
k\\}\right\rvert$. We deduce that

$\displaystyle(n)_{k}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert$ $\displaystyle\leq
n^{k/2}+\sum_{\lambda\vdash k\colon\lambda_{1}\geq
2}\frac{\lambda!}{\lambda_{1}!\cdots\lambda_{k}!}\cdot\frac{(n)_{\lambda^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert$ $\displaystyle\leq
n^{k/2}+k!\sum_{\lambda\vdash k\colon\lambda_{1}\geq
2}(n)_{\lambda^{t}_{1}}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert$ $\displaystyle\leq
n^{k/2}+k!\sum_{\lambda\vdash k\colon\lambda_{1}\geq
3}(n)_{\lambda^{t}_{1}}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert+$ $\displaystyle\qquad\qquad
k!\sum_{\lambda\vdash
k\colon\lambda_{1}=2}(n)_{\lambda^{t}_{1}}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert$ $\displaystyle\leq 3^{(k-2)^{3}}\cdot
k!\cdot(1+p(k)+k)\cdot n^{k/2}\leq 3^{k^{3}}\cdot n^{k/2},$

as desired.

######  Claim 6.13.

Suppose $k<\sqrt{n}/2$. We have

$\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k}\right]\right\rvert\leq 2\cdot 3^{k^{3}}\cdot n^{-k/2}.$

###### Proof.

Follows from 6.12 and the bound on $k$.

######  Remark 6.14.

In 6.13, the factor $3^{k^{3}}$ is too lossy to allow a meaningful bound with
$k=n^{\varepsilon}$, where $\varepsilon>0$ is a constant.

Refining the ideas of 6.12, we prove a stronger lemma below which will imply a
tighter bound on $e(k)$ sufficient for our application.

######  Lemma 6.15.

There exists a universal constant $C\geq 1$ such that

$\sum_{\lambda\vdash
k}\frac{\lambda!}{\lambda_{1}!\cdots\lambda_{k}!}\cdot\frac{(n)_{\lambda^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert\leq k^{C\cdot k}\cdot n^{k/2}.$ (1)

In particular, for $n\geq 6$, Eq. 1 holds with $C=2$.

###### Proof.

We induct on $k$. For $k=1$, we have
$n\cdot\left\lvert{\mathbb{E}}_{x\in\operatorname{\mathcal{S}}(\sqrt{n})}x_{1}\right\rvert\leq\sqrt{n}$
as desired. Using $e(2)=0$ from 6.5 and the case $k=1$ of Eq. 1, we get that
Lemma 6.15 also holds for $k=2$. Now, consider $k\geq 3$. Let
$\Lambda_{1}=\\{\lambda\vdash k\mid\lambda_{1}=1\\}$,
$\Lambda_{2}=\\{\lambda\vdash k\mid\lambda_{1}=2\\}$ and $\Lambda_{\geq
3}=\\{\lambda\vdash k\mid\lambda_{1}=3\\}$. Note that
$\Lambda_{1}\sqcup\Lambda_{2}\sqcup\Lambda_{\geq 3}=\\{\lambda\vdash k\\}$ and
$\left\lvert\Lambda_{1}\right\rvert=1$.

For convenience define $a_{\lambda}$ to be the term associated to
$\lambda\vdash k$ on the LHS of Eq. 1, i.e.,

$a_{\lambda}=\frac{\lambda!}{\lambda_{1}!\cdots\lambda_{k}!}\cdot\frac{(n)_{\lambda^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert.$

First we bound the contribution of the terms associated to partitions from
$\Lambda_{\geq 3}$ in the LHS of Eq. 1. Let $\lambda^{\prime}$ be the
partition obtained from $\lambda$ by removing two boxes from $\lambda_{1}$.
Note that $\lambda_{1}^{t}=(\lambda^{\prime})^{t}_{1}\leq k-2$ and
${\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}^{\prime}}\dots
x_{k-2}^{\lambda_{k-2}^{\prime}}\right]={\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k-2}^{\lambda_{k-2}}\right]$. Thus,

$\displaystyle
a_{\lambda}=\frac{\lambda!}{\lambda_{1}!\cdots\lambda_{k}!}\cdot\frac{(n)_{\lambda^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert$
$\displaystyle\qquad=\frac{k(k-1)}{\lambda_{1}(\lambda_{1}-1)}\cdot\frac{\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\frac{\lambda^{\prime}!}{\lambda_{1}^{\prime}!\cdots\lambda_{k}^{\prime}!}\cdot\frac{(n)_{(\lambda^{\prime})^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}^{\prime}}\dots
x_{k-2}^{\lambda_{k-2}^{\prime}}\right]\right\rvert$
$\displaystyle\qquad=k^{2}\cdot\frac{\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot
a_{\lambda^{\prime}}\leq k^{3}\cdot a_{\lambda^{\prime}},$

since
$\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert/\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert\leq
k-2\leq k$. For each $\lambda^{\prime}\vdash k-2$, we can form a partition
$\lambda\vdash k$ in $k-2\leq k$ ways by adding two blocks to a single row of
$\lambda^{\prime}$. Hence, we have

$\sum_{\lambda\in\Lambda_{\geq 3}}a_{\lambda}\leq
k\cdot\sum_{\lambda^{\prime}\vdash k-2}k^{3}\cdot a_{\lambda^{\prime}}\leq
k^{4}\cdot k^{C\cdot(k-2)}\cdot n^{(k-2)/2},$ (2)

where the last equality follows from the induction hypothesis.

Now we bound the contribution of the terms $a_{\lambda}$ associated to
partitions $\lambda$ from $\Lambda_{2}$ in the LHS of Eq. 1. Let $i\geq 1$ be
the number of parts of size two of $\lambda$ and let $\lambda^{\prime}$ be the
partition obtained from $\lambda$ by removing these $i$ parts of size two.
Note that $\lambda_{1}^{t}=(\lambda^{\prime})^{t}_{1}+i\leq k-1$. We have

$\displaystyle
a_{\lambda}=\frac{\lambda!}{\lambda_{1}!\cdots\lambda_{k}!}\cdot\frac{(n)_{\lambda^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert$ $\displaystyle\qquad\leq
n^{i}\cdot\frac{(k)_{i}}{2^{i}}\cdot\frac{\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot\frac{\lambda^{\prime}!}{\lambda_{1}^{\prime}!\cdots\lambda_{k}^{\prime}!}\cdot\frac{(n)_{(\lambda^{\prime})^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k-2i}\right]\right\rvert$
$\displaystyle\qquad=n^{i}\cdot\frac{(k)_{i}}{2^{i}}\cdot\frac{1}{i!}\cdot\frac{\lambda^{\prime}!}{\lambda_{1}^{\prime}!\cdots\lambda_{k}^{\prime}!}\cdot\frac{(n)_{(\lambda^{\prime})^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k-2i}\right]\right\rvert,$

where in the last equality we used
$\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert/\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert=1/(i!)$.
Since $\lambda\in\Lambda_{2}$ is uniquely specified by its number of parts of
size two, applying the induction hypothesis we have

$\displaystyle\sum_{\lambda\in\Lambda_{2}}a_{\lambda}$
$\displaystyle\leq\sum_{i=1}^{\lfloor
k/2\rfloor}n^{i}\cdot\frac{(k)_{i}}{2^{i}}\cdot\frac{1}{i!}\cdot\left(\frac{\lambda^{\prime}!}{\lambda_{1}^{\prime}!\cdots\lambda_{k}^{\prime}!}\cdot\frac{(n)_{(\lambda^{\prime})^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda^{\prime})\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k-2i}\right]\right\rvert\right)$ $\displaystyle\leq\sum_{i=1}^{\lfloor
k/2\rfloor}n^{i}\cdot\frac{(k)_{i}}{2^{i}}\cdot\frac{1}{i!}\cdot
k^{C\cdot(k-2i)}\cdot n^{(k-2i)/2}$ $\displaystyle\leq k^{C\cdot(k-1)}\cdot
n^{k/2}\cdot\sum_{i=0}^{\infty}k^{-C\cdot i}\leq\frac{3}{2}\cdot
k^{C\cdot(k-1)}\cdot n^{k/2},$

where in the last inequality we used $k\geq 3$ and $C\geq 1$.

Finally, we consider the case $\lambda_{1}=1$. To bound $a_{\lambda}$, we use
Lemma 6.11 and the two preceding cases. We deduce that

$\displaystyle a_{\lambda}$ $\displaystyle\leq
n^{k/2}+\sum_{\mu\in\Lambda_{2}}a_{\mu}+\sum_{\mu\in\Lambda_{\geq
3}}a_{\mu}\leq n^{k/2}+k^{4}\cdot k^{C\cdot(k-2)}\cdot
n^{(k-2)/2}+\frac{3}{2}\cdot k^{C\cdot(k-1)}\cdot n^{k/2}$
$\displaystyle=k^{C\cdot k}\cdot n^{k/2}\left(\frac{1}{k^{C\cdot
k}}+\frac{k^{4}}{n\cdot k^{2\cdot C}}+\frac{3}{2\cdot k^{C}}\right).$

We can bound the LHS of Eq. 1 as

$\displaystyle\sum_{\mu\in\Lambda_{1}}a_{\mu}+\sum_{\mu\in\Lambda_{2}}a_{\mu}+\sum_{\mu\in\Lambda_{\geq
3}}a_{\mu}$ $\displaystyle\leq k^{C\cdot k}\cdot
n^{k/2}\left(\frac{1}{k^{C\cdot k}}+\frac{2\cdot k^{4}}{n\cdot k^{2\cdot
C}}+\frac{3}{k^{C}}\right)$ $\displaystyle\leq k^{C\cdot k}\cdot n^{k/2},$

provided $C>0$ is a sufficiently large constant. In particular, the constant
$C$ can be taken to be $2$ for $n\geq 6$.

######  Corollary 6.16.

We have

$\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k}\right]\right\rvert\leq k^{3\cdot k}\cdot n^{-k/2}.$

###### Proof.

Suppose $k\leq\sqrt{n}$. Note that Lemma 6.15 implies that for $\lambda\vdash
k$ with $\lambda_{1}$ there exists a constant $C>0$ such that

$\displaystyle\frac{\lambda!}{\lambda_{1}!\cdots\lambda_{k}!}\cdot\frac{(n)_{\lambda^{t}_{1}}}{\left\lvert\operatorname{\operatorname{Aut}}(\lambda)\right\rvert}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}^{\lambda_{1}}\dots
x_{k}^{\lambda_{k}}\right]\right\rvert$
$\displaystyle=(n)_{k}\cdot\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k}\right]\right\rvert$ $\displaystyle\leq k^{C\cdot k}\cdot n^{k/2}.$

Simplifying and using the assumption $k\leq\sqrt{n}$, we obtain

$\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k}\right]\right\rvert\leq\frac{k^{C\cdot k}\cdot
n^{-k/2}}{\prod_{i=1}^{k-1}\left(1-\frac{i}{n}\right)}\leq 2\cdot k^{C\cdot
k}\cdot n^{-k/2}.$

Furthermore, for $n\geq 6$, Lemma 6.15 allows us to choose $C=2$. Since
$\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\right]\right\rvert=1/\sqrt{n}$,
the simpler bound applies for all values of $k$

$\left\lvert{\mathbb{E}}_{x\in\mathcal{S}(\sqrt{n})}\left[x_{1}\dots
x_{k}\right]\right\rvert\leq k^{3\cdot k}\cdot n^{-k/2},$

Now the assumption $n\geq 6$ can be removed since, for $k\geq 2$, we
have$(k^{3}/\sqrt{n})^{k}\geq 1$, where $1$ is the trivial bound. Similarly,
our initial assumption of $k\leq\sqrt{n}$ can also be removed as the bound
also becomes trivial in the regime $k>\sqrt{n}$.

##  Chapter 5 The machinery and Qualitative bounds

In this chapter, we first state the main machinery that we use to prove our
results. The machinery is a meta theorem that shows that under several linear
algebraic conditions, a large random matrix is positive semidefinite (PSD)
with high probability. This is similar in spirit to the PSDness argument in
the SoS lower bounds for the Sherrington-Kirkpatrick Hamiltonian from the last
chapter, although it’s quite a bit more involved.

The machinery originally appeared in [potechin2020machinery, potechin2022sub],
where the complete proof can be found. In Section 1, we state the machinery.
Compared to that work, we significantly simplify the required definitions
needed to state and apply the machinery. Such a decluttering of the
definitions is possible since we don’t provide the proof and simply apply the
theorem. For example, we don’t define ribbons, we don’t formally define the
technical matrix $M^{orth}_{\tau}(H)$ and we work in the simplified setting of
Rademacher or Gaussian variables instead of arbitrary distributions with
finite moments. Moreover, we interpret the conditions of the machinery as
conditions of the problem itself, rather than computational linear algebraic
conditions on the moment matrix as in [potechin2020machinery]. Cast in this
framework, this makes clear the potential connection to the low degree
likelihood ratio hypothesis as described in Chapter 2 and Chapter 7.

After stating the machinery in Section 1, we exhibit the qualitative bounds
for applying the machinery to our problems of interest. The material in these
sections is also adapted from [potechin2020machinery]. The main difference is
that we improve the exposition by fixing various typos and clarifying various
technical arguments.

###  1 The machinery

In this section, we describe the machinery we apply to show SoS lower bounds.
As we have already seen in Chapter 4, the general idea to show SoS lower
bounds in this work is to decompose the moment matrix into graph matrices,
which are matrix-valued functions of the input entries, and then show PSDness
by exhibiting an approximate PSD decomposition. The machinery takes a similar
approach and provides an approximate PSD decomposition, using certain decay
properties of the Fourier coefficients as well as norm bounds similar to the
ones obtained in Chapter 1.

Consider a hypothesis testing problem ${\mathcal{P}}$. We will assume the
setup in Section 3. Therefore, ${\mathcal{P}}$ is a distinguishing problem
between two distributions – the random distribution (null hypothesis) and the
planted distribution (alternative hypothesis). As we saw earlier, we could use
the technique of pseudo-calibration to obtain a candidate moment matrix
$\Lambda$, such that $\Lambda$ can potentially serve as an SoS lower bound for
the related optimization task on the random distribution. The machinery gives
general conditions on $\Lambda$ that ensure feasibility with high probability.
In particular, the machinery is a set of linear algebraic conditions on
$\Lambda$ that imply positivity of $\Lambda$ w.h.p. and as we saw earlier, the
other required feasibility conditions follow easily from pseudo-calibration.

In this work, we slightly diverge from this viewpoint (originally presented in
[potechin2020machinery]) and instead view these conditions as properties of
the problem ${\mathcal{P}}$ directly. Therefore, the machinery can be
construed as a claim of feasibility of the pseudo-cailbrated pseudo-
expectation operator, under certain conditions on the problem ${\mathcal{P}}$.
To state the machinery in this language, we need some definitions that follow
next.

####  1 Shapes and graph matrices

Consider the setting when the input distribution is a Rademacher $G_{n,1/2}$
graph with the input entries being $\chi_{e}\in\\{-1,1\\}$. For
$T\subseteq\binom{[n]}{2}$, let $\chi_{T}=\prod_{e\in T}\chi_{e}$ be the
standard Fourier basis. In this setting, shapes were already defined in
Chapter 1. Here, for technical reasons, we slightly modify the definitions so
that the rows and columns are indexed by sub-tuples of $[n]$ rather than
subsets of $[n]$. The techniques developed in Chapter 1 still carry over to
bound the norms of such graph matrices.

######  Definition 1.1 (Shapes in the setting of Rademacher $G_{n,1/2}$
inputs).

A shape $\alpha=(V(\alpha),E(\alpha),U_{\alpha},V_{\alpha})$ is a graph on
vertices $V(\alpha)$ and edges $E(\alpha)$ with two distinguished tuples of
vertices $U_{\alpha},V_{\alpha}\subseteq V(\alpha)$. Note that
$U_{\alpha},V_{\alpha}$ are ordered subsets (tuples).

As we saw earlier, we can define corresponding matrices for each shape, that
are termed graph matrices. Recall that a realization is an injective map from
$V(\alpha)$ to $[n]$. The main difference here, as compared to Chapter 1, is
that in the definition of graph matrices, we sum over realizations $\varphi$
that correspond to distinct characters, rather than all realizations
$\varphi$.

To capture this notion precisely, we use the following definition. Define two
realizations (injective maps from $V(\alpha)$ to $[n]$)
$\varphi,\varphi^{\prime}$ to be equivalent if
$\varphi(U_{\alpha})=\varphi^{\prime}(U_{\alpha}),\varphi(V_{\alpha})=\varphi^{\prime}(V_{\alpha})$
as tuples and $\varphi(E(\alpha))=\varphi^{\prime}(E(\alpha))$ as sets. Let
the set of non-equivalent realizations of $\alpha$ be denoted
$\mathrm{Real}(\alpha)$.

######  Definition 1.2 (Graph matrices in the setting of Rademacher
$G_{n,1/2}$ inputs).

For a shape $\alpha$, the graph matrix $M_{\alpha}$ is a matrix-valued
function with rows and columns indexed by sub-tuples of $[n]$ of sizes
$|U_{\alpha}|,|V_{\alpha}|$ respectively, which is defined as follows: It maps
input graph $G\in\\{\pm 1\\}^{\binom{n}{2}}$ (wich associated fourier
characters $\chi_{E}$) to a matrix with the $A,B$-th entry being

$M_{\alpha}(A,B)=\sum_{\begin{subarray}{c}\varphi(U_{\alpha})=A,\varphi(V_{\alpha})=B\\\
\varphi\in\mathrm{Real}(\alpha)\end{subarray}}{\chi_{E(\alpha)}}$

######  Definition 1.3 (Shape transposes).

For a shape $\alpha=(V(\alpha),E(\alpha),U_{\alpha},V_{\alpha})$, define its
transpose $\alpha^{T}$ to be
$\alpha^{T}=(V(\alpha),E(\alpha),V_{\alpha},U_{\alpha})$. Note that
$M_{\alpha^{T}}=M_{\alpha}^{T}$ as matrix transpose.

######  Example 1.4.

In Fig. 1, consider the shape $\alpha$ as shown. We have
$U_{\alpha}=(u_{1},u_{2}),V_{\alpha}=(v_{1}),V(\alpha)=\\{u_{1},u_{2},v_{1},w_{1}\\}$
and $E(\alpha)=\\{\\{u_{1},w_{1}\\},\\{u_{2},w_{1}\\},\\{w_{1},v_{1}\\}\\}$.
$M_{\alpha}$ is a matrix with rows and columns indexed by tuples of length
$|U_{\alpha}|=2$ and $|V_{\alpha}|=1$ respectively. The nonzero entries will
have rows and columns indexed by $(a_{1},a_{2})$ and $b_{1}$ respectively for
all distinct $a_{1},a_{2},b_{1}$, with the corresponding entry being
$M_{\alpha}((a_{1},a_{2}),(b_{1}))=\sum_{c_{1}\in[n]\setminus\\{a_{1},a_{2},b_{1}\\}}\chi_{a_{1},c_{1}}\chi_{a_{2},c_{1}}\chi_{c_{1},b_{1}}$.
Here, the injective map $\varphi$ maps the vertices $u_{1},u_{2},w_{1},v_{1}$
to $a_{1},a_{2},c_{1},b_{1}$ respectively and we sum over all such maps (as
they are all pairwise non-equivalent). Succinctly,

$M_{\alpha}=\blockarray{rl<EMAIL_ADDRESS>$(b_{1})$}\\\
\,\downarrow\\\ \block{r(l@{}c@{}r)}\vdots\\\ \text{row
}(a_{1},a_{2})\rightarrow\mkern-9.0mu\raisebox{2.15277pt}{\makebox[32.00002pt][l]{\dotfill}}\sum_{c_{1}\in[n]\setminus\\{a_{1},a_{2},b_{1}\\}}\chi_{a_{1},c_{1}}\chi_{a_{2},c_{1}}\chi_{c_{1},b_{1}}\raisebox{2.15277pt}{\makebox[42.00003pt][r]{\dotfill}}\\\
\vdots\\\ $

Figure 1: Example of a shape

Some simple matrices such as the adjacency matrix of a graph and the identity
matrix are also graph matrices, as we see below

  * •

Take $\alpha$ to be a shape with two vertices $u,v$ with
$U_{\alpha}=(u),V_{\alpha}=(v)$ and exactly one edge $\\{u,v\\}$. Then,
$M_{\alpha}$ has rows and columns indexed by $[n]$ (more specifically tuples
of length $1$) with the $i,j$-th entry being $G_{ij}$ if $i\neq j$ and $0$
otherwise. Therefore, $M_{\alpha}$ is just the $\pm 1$ adjacency matrix of the
graph $G$.

  * •

Take $\alpha$ to be the shape with exactly $1$ vertex $u$, no edges and
$U_{\alpha}=V_{\alpha}=(u)$. Then, $M_{\alpha}$ is the identity matrix of size
$n\times n$.

For more examples of graph matrices and why they can be a useful tool to work
with, see [ahn2016graph]. We now define some terms to capture the rows and
columns of graph matrices.

###### Matrix indices and index shapes

In the above setting of Rademacher $G_{n,1/2}$ inputs, a matrix index $A$ is a
tuple of indices $(a_{1},\ldots,a_{|A|})$ where $a_{i}\in[n]$. When the SoS
variables are $y_{1},\ldots,y_{n}$, we associate to this matrix index $A$ the
monomial $\prod_{i\leq|A|}y_{a_{i}}$. With this definition, graph matrices
have as rows and columns matrix indices.

Define an index shape $U=(u_{1},\ldots,u_{|U|})$ to be a tuple of formal
variables $u_{i}$, or in other words, unspecified indices. If $|U|=t$, we say
that any matrix index $A$ of length $t$ has shape $U$. We say two index shapes
$U,V$ are equivalent, denoted $U\equiv V$ if $|U|=|V|$. Finally, define the
weight of $U$ to be $w(U)=|U|$ and the automorphism group $Aut(U)=S_{|U|}$
(the permutations of the elements of $U$). The latter definition is needed for
describing coefficients.

###### Shape definitions

We say a shape $\alpha$ is proper if it has no isolated vertices (i.e. no
degree $0$ vertices) outside $U_{\alpha}\cup V_{\alpha}$. We say a shape
$\alpha$ is trivial if $U_{\alpha}$ and $V_{\alpha}$ are equal as sets, and
they constitute all the vertices in $\alpha$. and moreover, there are no edges
in $\alpha$.

A path is a sequence of vertices of $V(\alpha)$ such that every consecutive
pair of vertices form an edge in $V(\alpha)$. A vertex separator of $\alpha$
is a set of vertices $S$ such that every path from $U_{\alpha}$ to
$V_{\alpha}$ passes through $S$. As we saw in Chapter 1, the norm bounds of
the graph matrix $M_{\alpha}$ rely on the size of the minimum vertex separator
of $\alpha$. Define the weight of a vertex separator $S$ as $|S|$.

The above definitions are sufficient for the application to the Planted
Slightly Denser subgraph problem. But when we work with Tensor PCA and Sparse
PCA, we need to generalize the notion of shapes and graph matrices. These
generalized shapes and graph matrices were studied in [ahn2016graph]. Now, we
describe the required generalizations.

##### Definitions for Tensor PCA

In the Tensor PCA application, the input is a tensor
$A\in\mathbb{R}^{[n]^{k}}$. To incorporate this, we modify our definitions of
shapes and index shapes accordingly. The input entries are now sampled from
the distribution $\mathcal{N}(0,1)$ instead of $\\{-1,1\\}$. So, we will work
with the Hermite basis of polynomials. Let the standard unnormalized Hermite
polynomials be denoted as $h_{0}(x)=1,h_{1}(x)=x,h_{2}(x)=x^{2}-1,\ldots$.
Then, we work with the basis $h_{a}(A):=\prod_{e\in[n]^{k}}h_{e}(A_{e})$ over
$a\in\mathbb{N}^{[n]^{k}}$. Accordingly, we will modify the graphs that
represent shapes, to have labeled hyperedges of arity $k$. So, an hyperedge
$e$ with a label $t$ will correspond to the hermite polynomial $h_{t}(A_{e})$.

######  Definition 1.5 (Hyperedges).

Instead of standard edges, we will have labeled hyperedges of arity $k$ in the
underlying graphs for our ribbons as well as shapes. The label for an
hyperedge $e$, denoted $l_{e}$, is an element of $\mathbb{N}$ which will
correspond to the Hermite polynomial being evaluated on that entry.

Note that our hyperedges are ordered since the tensor $A$ is not necessarily
symmetric. For variables $x_{1},\ldots,x_{n}$, the rows and columns of our
moment matrix will now correspond to monomials of the form $\prod_{i\leq
n}x_{i}^{p_{i}}$ for $p_{i}\geq 0$. To capture this, we use the notion of
index shape pieces and index shapes. Informally, we split the above monomial
product into groups based on their powers and each such group will form an
index shape piece.

######  Definition 1.6 (Index shape piece).

An index shape piece $U_{i}=((U_{i,1},\ldots,U_{i,t}),p_{i})$ is a tuple of
indices $(U_{i,1},\ldots,U_{i,t})$ along with a power $p_{i}\in\mathbb{N}$.
Let $V(U_{i})$ be the set $\\{U_{i,1},\ldots,U_{i,t}\\}$ of vertices of this
index shape piece. When clear from context, we use $U_{i}$ instead of
$V(U_{i})$.

If we realize $U_{i,1},\ldots,U_{i,t}$ to be indices
$a_{1},\ldots,a_{t}\in[n]$, then this realization of this index shape piece
corresponds to the monomial $\prod_{j\leq t}x_{a_{j}}^{p_{i}}$.

######  Definition 1.7 (Index shape).

An index shape $U$ is a set of index shape pieces $U_{i}$ that have different
powers. Let $V(U)$ be the set of vertices $\cup_{i}V(U_{i})$. When clear from
context, we use $U$ instead of $V(U)$.

Observe that each realization of an index shape corresponds to a row or column
of the moment matrix. Equivalence of index shapes is analogous, namely, for
two index shapes $U,V$, we write $U\equiv V$ if for all powers $p$, the index
shape pieces of power $p$ in $U$ and $V$ have the same length. We also define
the automorphism group of $U$ as $Aut(U)=\prod_{U_{i}\in U}{Aut(U_{i})}$ where
the automorphism group of an index shape piece $U_{i}$ is
$Aut(U_{i})=S_{|U_{i}|}$. In the definition of shapes, the distinguished set
of vertices should now be replaced by index shapes.

######  Definition 1.8 (Shapes).

Shapes are tuples $\alpha=(V(\alpha),E(\alpha),U_{\alpha},V_{\alpha})$ where
$(V(\alpha),E(\alpha))$ is a graph with hyperedges of arity $k$ and
$U_{\alpha},V_{\alpha}$ are index shapes such that
$U_{\alpha},V_{\alpha}\subseteq V(\alpha)$.

A shape $\alpha$ is proper if it has no isolated vertices outside
$U_{\alpha}\cup V_{\alpha}$, no multi-edges and all the edges have a nonzero
label. To define the notion of vertex separators, we accordingly modify the
notion of paths for hyperedges instead of edges. Formally, a path is a
sequence of vertices $u_{1},\ldots,u_{t}$ such that $u_{i},u_{i+1}$ are in the
same hyperedge, for all $i\leq t-1$. The notion of vertex separator is
identically defined with the above notion of hyperedges and paths. Finally,
the definition of trivial shape $\tau$ is similar, the only change being that
we now require $U_{\tau}\equiv V_{\tau}$ instead of saying they’re equal as
sets.

##### Definitions for Sparse PCA

We are given the $m$ vectors $v_{1},\ldots,v_{m}\in\mathbb{R}^{d}$ as input.
Similar to Tensor PCA, we will work with the Hermite basis of polynomials
since the entries are sampled from the distribution $\mathcal{N}(0,1)$. In
particular, if we denote the unnormalized Hermite polynomials by
$h_{0}(x)=1,h_{1}(x)=x,h_{2}(x)=x^{2}-1,\ldots$, then, we work with the basis
$h_{a}(v):=\prod_{i\in[m],j\in[n]}h_{a_{i,j}}(v_{i,j})$ over
$a\in\mathbb{N}^{m\times n}$. To capture this basis, we will modify the graphs
that represent shapes to be bipartite graphs with two types of vertices, and
have labeled edges that go across vertices of different types. So, an edge
$(i,j)$ with label $t$ between a vertex $i$ of type $1$ and a vertex $j$ of
type $2$ will correspond to $h_{t}(v_{i,j})$.

Formally, we will have two types of vertices, the vertices corresponding to
the $m$ input vectors that we call type $1$ vertices and the vertices
corresponding to ambient dimension of the space that we call type $2$
vertices. For a shape with such vertices, edges will go across vertices of
different types, thereby forming a bipartite graph. An edge between a type $1$
vertex $i$ and a type 2 vertex $j$ corresonds to the input entry $v_{i,j}$.
Each edge will have a label in $\mathbb{N}$ corresponding to the Hermite
polynomial evaluated on that entry.

We will have variables $x_{1},\ldots,x_{n}$ in our SoS program, so we will
work with index shape pieces and index shapes as in Tensor PCA, since the rows
and columns of our moment matrix will now correspond to monomials of the form
$\prod_{i\leq n}x_{i}^{p_{i}}$ for $p_{i}\geq 0$. But since we have $2$ types
of vertices, we need to slightly modify the notion of index shape pieces and
index shapes.

######  Definition 1.9 (Index shape piece).

An index shape piece $U_{i}=((U_{i,1},\ldots,U_{i,t}),t_{i},p_{i})$ is a tuple
of indices $(U_{i,1},\ldots,U_{i,t})$ along a type $t_{i}\in\\{1,2\\}$ with a
power $p_{i}\in\mathbb{N}$. Let $V(U_{i})$ be the set
$\\{U_{i,1},\ldots,U_{i,t}\\}$ of vertices of this index shape piece. When
clear from context, we use $U_{i}$ instead of $V(U_{i})$.

For an index shape piece $((U_{i,1},\ldots,U_{i,t}),t_{i},p_{i})$ with type
$t_{i}=2$, if we realize $U_{i_{1}},\ldots,U_{i_{t}}$ to be indices
$a_{1},\ldots,a_{t}\in[n]$, then, this index shape pieces correspond this to
the monomial $\prod_{j\leq n}x_{a_{j}}^{p_{i}}$.

######  Definition 1.10 (Index shape).

An index shape $U$ is a set of index shape pieces $U_{i}$ that have either
have different types or different powers. Let $V(U)$ be the set of vertices
$\cup_{i}V(U_{i})$. When clear from context, we use $U$ instead of $V(U)$.

Each realization of an index shape will correspond to a row or column of the
moment matrix. For our moment matrix, the only nonzero rows correspond to
index shapes that have only index shape pieces of type $2$, since the only SoS
variables are $x_{1}\ldots,x_{n}$, but in order to do our analysis, we need to
work with the generalized notion of index shapes that allow index shape pieces
of both types.

Analogous to our previous definitions, for two index shapes $U,V$, we write
$U\equiv V$ if for all types $t$ and all powers $p$, the index shape pieces of
type $t$ and power $p$ in $U$ and $V$ have the same length. Since we are
working with standard graphs, the original notion of path and vertex separator
will work , but we will now use the minimum weight vertex separator instead of
the minimum vertex separator where we define the weight as follows.

######  Definition 1.11 (Weight of an index shape).

Suppose we have an index shape $U=\\{U_{1},U_{2}\\}\in{\mathcal{I}}_{mid}$
where $U_{1}=((U_{1,1},\ldots,U_{1,|U_{1}|}),1,1)$ is an index shape piece of
type $1$ and $U_{2}=((U_{2,1},\ldots,U_{2,|U_{2}|}),2,1)$ is an index shape
piece of type $2$. Then, define the weight of this index shape to be
$w(U)=\sqrt{m}^{|U_{1}|}\sqrt{n}^{|U_{2}|}$.

The definition carries over for a vertex separator as well. We also define the
automorphism group of $U$ as $Aut(U)=\prod_{U_{i}\in U}{Aut(U_{i})}$ where the
automorphism group of an index shape piece $U_{i}$ is
$Aut(U_{i})=S_{|U_{i}|}$. We now give the modified definition of shapes.

######  Definition 1.12 (Shapes).

Shapes are tuples $\alpha=(V(\alpha),E(\alpha),U_{\alpha},V_{\alpha})$ where
$(V(\alpha),E(\alpha))$ is a graph with two types of vertices, has labeled
edges only across vertices of different types and $U_{\alpha},V_{\alpha}$ are
index shapes such that $U_{\alpha},V_{\alpha}\subseteq V(\alpha)$.

The other definitions that follow are analogous. A shape $\alpha$ is proper if
it has no isolated vertices outside $U_{\alpha}\cup V_{\alpha}$, no multi-
edges and all the edges have a nonzero label. In the definition of trivial
shape $\tau$, just as in Tensor PCA, we require $U_{\tau}\equiv V_{\tau}$
instead of saying they’re equal as sets.

####  2 Decomposing shapes

Compared to the lower bound strategy in the Sherrington-Kirkpatrick lower
bound in Chapter 4, the main strategy in the machinery is to provide an
approximate PSD decomposition by decomposing shapes $\alpha$ into three other
shapes $\sigma,\tau,\sigma^{\prime T}$ such that $M_{\alpha}\approx
M_{\sigma}M_{\tau}M_{\sigma^{\prime T}}$. Then, the idea is to argue that the
graph matrix coefficients of the moment matrix also decompose similarly,
ending with a PSD decomposition showing that the moment matrix is PSD.

We first need to define composition of shapes. We say that shapes $\alpha$ and
$\beta$ are composable if $U_{\beta}\equiv V_{\alpha}$. In this case, define
their composition to be the shape $\alpha\circ\beta$ which is obtained by
concatenating $\alpha,\beta$ while gluing together $U_{\beta},V_{\alpha}$.
Formally, $\alpha\circ\beta$ is such that $U_{\alpha\circ\beta}=U_{\alpha}$,
$V_{\alpha\circ\beta}=V_{\beta}$, and after setting $U_{\beta}=V_{\alpha}$, we
take $V(\alpha\circ\beta)=V(\alpha)\cup V(\beta)$, and finally,
$E(\alpha\circ\beta)=E(\alpha)\cup E(\beta)$.

Note that by doing this, the concatenated shape could become improper if edges
repeat. We remark that shape composition is not necessarily commutative, but
it is associative.

Figure 2: Illustration of shape composition and decomposition.

######  Example 1.13.

Fig. 2 illustrates an example of shape composition in the setting where there
is only one type of vertex. Observe how the shapes $\sigma\circ\sigma^{\prime
T}$ and $\sigma\circ\tau\circ\sigma^{\prime T}$ are obtained from the shapes
$\sigma,\tau$ and $\sigma^{\prime T}$.

######  Example 1.14.

Fig. 3 illustrates an example of shape composition in the setting where there
are two types of vertices. We have two types of vertices that we
diagrammaticaly represent by squares and circles. Observe how the shapes
$\sigma\circ\sigma^{\prime T}$ and $\sigma\circ\tau\circ\sigma^{\prime T}$ are
obtained from the shapes $\sigma,\tau$ and $\sigma^{\prime T}$.

Figure 3: Illustration of shape composition and decomposition.

Previously, we defined the notion of minimum vertex separators (and
analogously, minimum weight vertex separators). In what follows, we
collectively term either of them as minimum weight vertex separators. by
Define the leftmost (resp. rightmost) minimum-weight vertex separator $S$
(resp. $T$) to be a minimum-weight vertex separator such that for every other
minimum-weight vertex separator $S^{\prime}$ (resp. $T^{\prime}$), $S$
separates $U_{\alpha}$ from $S^{\prime}$ (resp. $T^{\prime}$ from
$V_{\alpha}$). In [BHKKMP16, potechin2020machinery], it’s shown that these are
well-defined.

With these definitions in hand, we can now define how to decompose a shape
$\alpha$ into its left, middle and right parts $\sigma,\tau,\sigma^{\prime T}$
respectively.

######  Definition 1.15 (Shape decomposition).

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

  * •

We define the left part $\sigma$ of $\alpha$ to be the shape formed by taking
the induced subgraph on all of the vertices of $\alpha$ reachable from
$U_{\alpha}$ without passing through $S$ (but including the vertices of $S$)
where all edges and hyperedges within $S$ are removed, and we take
$U_{\sigma}=U_{\alpha}$ and $V_{\sigma}=(S,O_{S})$.

  * •

We define the right part ${\sigma^{\prime}}^{T}$ of $\alpha$ to be the shape
formed by taking the induced subgraph on all of the vertices of $\alpha$
reachable from $V_{\alpha}$ without passing through $T$ (but we include the
vertices of $T$) where all edges and hyperedges within $T$ are removed, and we
take $V_{{\sigma^{\prime}}^{T}}=V_{\alpha}$ and
$U_{{\sigma^{\prime}}^{T}}=(T,O_{T})$.

  * •

Finally, we define the middle part $\tau$ of $\alpha$ to be the shape formed
by the induced subgraph on all of the vertices of $\alpha$ which are not
reachable from $U_{\alpha}$ and $V_{\alpha}$ without touching $S$ and $T$
respectively (but we include the vertices of $S$ and $T$), where we also
include the edges or hyperedges entirely within $S$ and the edges or
hyperedges entirely within $T$, and we take $U_{\tau}=(S,O_{S})$ and
$V_{\tau}=(T,O_{T})$.

It’s evident from the definition that
$\alpha=\sigma\circ\tau\circ\sigma^{\prime T}$.

######  Example 1.16.

Fig. 2 illustrates an example decomposition in the setting where there is only
one type of vertex.

  1. 1.

If we start with the shape $\alpha$ denoted as $\sigma\circ\sigma^{\prime T}$,
observe that there is a unique minimum vertex separator, which consists of the
middle vertex of degree $5$, i.e. the one that’s not in either
$U_{\sigma\circ\sigma^{\prime T}}$ or $V_{\sigma\circ\sigma^{\prime T}}$.
Then, $\alpha$ is decomposed in to the left part $\sigma$, a trivial middle
part $\tau$ (not shown in this figure) which has
$V(\tau)=\\{u\\},U_{\tau}=V_{\tau}=(u),E(\tau)=\emptyset$, and the right part
$\sigma^{\prime T}$.

  2. 2.

If we start with the shape $\alpha$ denoted as
$\sigma\circ\tau\circ\sigma^{\prime T}$, then the leftmost minimum vertex
separator is the vertex of degree $4$ and the rightmost minimum vertex
separator is the vertex of degree $5$. Then, $\alpha$ is decomposed into the
left part $\sigma$, the middle part $\tau$ and the right part $\sigma^{\prime
T}$, which are all shown in this figure.

######  Example 1.17.

Fig. 3 illustrates an example decomposition in the setting where there are two
types of vertices. We have two types of vertices that we diagrammatically
represent by squares and circles. In this example, we assume that the set
containing a single circle vertex has a lower weight compared to a set of two
square vertices.

  1. 1.

If we start with the shape $\sigma\circ\sigma^{\prime T}$, then it can be
decomposed uniquely in to the composition of the left shape $\sigma$, the
right shape $\sigma^{\prime T}$. In this case, the middle shape (not shown in
this figure) is trivial.

  2. 2.

If we start with the shape $\sigma\circ\tau\circ\sigma^{\prime T}$, then it
can be decomposed uniquely into the composition of the left shape $\sigma$,
the middle shape $\tau$ and the right shape $\sigma^{\prime T}$, which are all
shown in this figure.

At this point, the definitions of left shapes, middle shapes and right shapes
are natural. 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}$. Similarly, 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$. We do not define improper middle shapes,
which are needed in the machinery proof, but not here. Finally, we say that a
shape ${\sigma}^{T}$ is a right shape if it is the transpose of a left shape.

####  3 Coefficient matrices

We have all the necessary definitions in place for shapes and graph matrices.
To apply the machinery, we will decompose the given moment matrix $\Lambda$ as
$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$ where the sum is over all shapes
$\alpha$. The coefficients $\lambda_{\alpha}$ are then assembled into
matrices, termed coefficient matrices, that we will define next. The
conditions of the machinery will be in terms of these coefficient matrices.

We will begin with some notations for different sets of index shapes. Given a
moment matrix $\Lambda$, define $\mathcal{I}(\Lambda)$ to the set of matrix
shapes $U$ such that some row or column index of $\Lambda$ has shape $U$.
Define $w_{max}=\max{\\{w(U):U\in\mathcal{I}(\Lambda)\\}}$ to be the maximum
possible weight of an index shape in ${\mathcal{I}}(\Lambda)$. Finally, define
$\mathcal{I}_{mid}$ to be $\mathcal{I}_{mid}=\\{U:w(U)\leq w_{max},\forall
U_{i}\in U,p_{i}=1\\}$. Observe that in the setting of Rademacher $G_{n,1/2}$
inputs, we have $\mathcal{I}_{mid}=\\{U:|U|\leq w_{max}\\}$.

In pseudo-calibration, we only keep the shapes that satisfy certain truncation
parameters that we choose. Formally, satisfication of truncation parameters is
defined as follows.

######  Definition 1.18 (Truncation parameters for the setting of Rademacher
$G_{n,1/2}$ inputs).

For integers $D_{sos},D_{V}\geq 0$, say that a shape $\alpha$ satisfies the
truncation parameters $D_{sos},D_{V}$ if

  * •

The degrees of the monomials that $U_{\alpha}$ and $V_{\alpha}$ correspond to,
are at most $\frac{D_{sos}}{2}$

  * •

The left part $\sigma$, the middle part $\tau$ and the right part
$\sigma^{\prime}$ of $\alpha$ satisfy the bounds
$|V(\sigma)|,|V(\tau)|,|V(\sigma^{\prime})|\leq D_{V}$.

######  Definition 1.19 (Truncation parameters for Tensor PCA and Sparse PCA).

For integers $D_{sos},D_{V},D_{E}\geq 0$, say that a shape $\alpha$ satisfies
the truncation parameters $D_{sos},D_{V},D_{E}$ if

  * •

The degrees of the monomials that $U_{\alpha}$ and $V_{\alpha}$ correspond to,
are at most $\frac{D_{sos}}{2}$

  * •

The left part $\sigma$, the middle part $\tau$ and the right part
$\sigma^{\prime T}$ of $\alpha$ satisfy the bounds
$|V(\sigma)|,|V(\tau)|,|V(\sigma^{\prime T})|\leq D_{V}$

  * •

For each $e\in E(\alpha)$, $l_{e}\leq D_{E}$.

We also need to define the sets of shapes which can appear when analyzing
$\Lambda$. Given a moment matrix $\Lambda$, define
$\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}\\}$. Moreover, given
$V\in\mathcal{I}_{mid}$, define
$\mathcal{L}_{V}=\\{\sigma\in\mathcal{L}:V_{\sigma}\equiv V\\}$. Finally,
given $U\in\mathcal{I}_{mid}$, 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}\\}$.

We are now ready to define coefficient matrices. Given a moment matrix
$\Lambda$, a coefficient matrix is a matrix $H$ whose rows and columns are
indexed by left shapes $\sigma,\sigma^{\prime}\in\mathcal{L}$. $H$ is called
SoS-symmetric if $H(\sigma,\sigma^{\prime})$ is invariant under the action of
the symmetric group, i.e. if we permute the vertices of $U_{\sigma}$ and the
vertices of $U_{\sigma^{\prime}}$ (where we only permute within the same type)
under the same permutation, then the entry doesn’t change.

For 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}}$. 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.

As stated earlier, the coefficients $\lambda_{\alpha}$ of the moment matrix
$\Lambda$ are assembled to form coefficient matrices, which are used to state
the machinery conditions. Given a shape $\tau$ and a $\tau$-coefficient matrix
$H$, we consider the matrix-valued function $M^{fact}_{\tau}(H)$ defined as

$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}}$

The motivation for this definition is as follows. First observe that $\Lambda$
is essentially an expression of the form
$\sum_{\tau}\sum_{\sigma,\sigma^{\prime}}{H(\sigma,\sigma^{\prime})M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}}$.
For each $\tau$, the inner expression sort of looks like $M_{\tau}^{fact}(H)$.
However, there is a technical difference. Recall that if we expand out the
definition of the graph matrices $M_{\sigma},M_{\tau}$ and
$M_{\sigma^{\prime}}^{T}$, then $M_{\tau}^{fact}(H)$ sums over non-equivalent
realizations coming from the sets
$\textrm{Real}(\sigma),\textrm{Real}(\tau),\textrm{Real}(\sigma^{\prime T})$
respectively. Apriori, it’s not guaranteed that for each choice of
realizations $\varphi_{1},\varphi_{2},\varphi_{3}$ from these sets, the
corresponding subset of labels
$\varphi_{1}(V(\sigma)),\varphi_{2}(V(\tau)),\varphi_{3}(V(\sigma^{\prime
T}))\subseteq[n]$ are disjoint. However, if we enforce that they are disjoint,
then we will obtain a matrix closely related to what we desire. The work
[potechin2020machinery] terms this matrix obtained by enforcing disjointness
of the realizations as $M^{orth}_{\tau}(H)$.

As they remark, it is not true that
$M^{orth}_{\tau}(H)=\sum_{\sigma,\sigma^{\prime}}{H(\sigma,\sigma^{\prime})M_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}}$
because of additional terms involving automorphism groups. Nevertheless,
because of this enforced condition that the realizations don’t overlap,
$\Lambda$ can be easily expressed in terms of $M^{orth}$. Indeed, as they show
via careful counting,
$\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})}}$,
where $H_{Id_{U}}$ and $H_{\tau}$, formally defined below, are simple
coefficient matrices assembled from $\lambda_{\alpha}$

Despite wanting to work with $M^{orth}$, the machinery instead works with
$M^{fact}$ instead because showing PSDness is easier with $M^{fact}$ due to
the product structure. The proof strategy in the machinery is to then show
that the error terms when going from $M^{fact}$ to $M^{orth}$ (and therefore,
$\Lambda$) are negligible with high probability, concluding the PSDness proof.

Given a matrix-valued function $\Lambda$, we assemble the following
coefficient matrices.

######  Definition 1.20.

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}$, set
$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}$, set
$H_{\tau}(\sigma,\sigma^{\prime})=\frac{1}{|Aut(U_{\tau})|\cdot|Aut(V_{\tau})|}\lambda_{\sigma\circ\tau\circ{\sigma^{\prime}}^{T}}$

We need a final definition, that of the coefficient matrix
$H^{-\gamma,\gamma}$. In order to handle error terms in the approximate PSD
decomposition, the machinery has to further decompose left shapes $\sigma$ as
$\sigma=\sigma_{2}\circ\gamma$ where $\sigma_{2}$ and $\gamma$ are themselves
left shapes. In order to capture this operation, the following definitions are
needed.

Given a moment matrix $\Lambda$, define $\Gamma=\\{\gamma:\gamma\text{ is a
non-trivial left shape with
}U_{\gamma},V_{\gamma}\in\mathcal{I}_{mid},|V(\gamma)|\leq D_{V},\forall e\in
E(\gamma),l_{e}\leq D_{E}\\}$. Moreover, 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\\}$. Finally, given $U\in\mathcal{I}_{mid}$, define
$\Gamma_{U,*}=\\{\gamma\in\Gamma:U_{\gamma}\equiv U\\}$.

We finally define the coefficient matrix $H^{-\gamma,\gamma}$ given the
truncation parameter $D_{V}$. Given a shape $\tau$ with $U_{\tau}\equiv
V_{\tau}$, left shape $\gamma\in{\Gamma}_{*,U_{\tau}}$ (and therefore,
$\gamma\in{\Gamma}_{*,V_{\tau}}$), and a $\tau$-coefficient matrix $H$, define
$H^{-\gamma,\gamma}$ to be the
$(\gamma\circ\tau\circ{\gamma}^{T})$-coefficient matrix with entries

  * •

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

  * •

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

####  4 Main theorems

For a problem ${\mathcal{P}}$, let $\Lambda_{{\mathcal{P}}}$ be the moment
matrix obtained via pseudo-calibration. We then state the conditions that the
machinery requires in order to show positivity with high probability. We will
use the following notion of distance between coefficient matrices, which will
be useful to bound truncation error.

######  Definition 1.21.

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

$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})}$

We also define $Id_{Sym}$, which is the SoS-symmetric analogue of the identity
matrix. For a matrix index $A$, denote by $p_{A}$ the formal monomial (in
terms of the SoS program variables) it corresponds to. Define $Id_{Sym}$ to be
the matrix such that the rows and columns of $Id_{Sym}$ are indexed by the
matrix indices $A,B$ whose index shape is in $\mathcal{I}(\Lambda)$ and
$Id_{Sym}(A,B)=1$ if $p_{A}=p_{B}$ and $Id_{Sym}(A,B)=0$ if $p_{A}\neq p_{B}$.

We introduce a few more notations about shapes in order to state our
parameters. Define $\mathcal{M}^{\prime}$ to be the set of all shapes $\alpha$
such that $|V(\alpha)|\leq 3D_{V}$, $\forall e\in E(\alpha),l_{e}\leq D_{E}$
and all edges $e\in E(\alpha)$ have multiplicity at most $3D_{V}$. Note that
the latter two conditions are not needed for the setting of Rademacher
$G_{n,1/2}$ inputs but they’re needed in the setting of Gaussian inputs. In
the setting of Rademacher $G_{n,1/2}$ inputs, for a shape $\alpha$, define
$S_{\alpha}$ to be the leftmost minimum vertex separator of $\alpha$ and
define $I_{\alpha}$ to be the set of vertices in
$V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})$ which are isolated. In the
setting of Gaussian $\mathcal{N}(0,1)$ inputs, for 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. Moreover, 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 multiplicity at least $2$.

##### Choice of parameters in the setting of Rademacher $G_{n,1/2}$ inputs

We first state some parameters we will use in this work and then state the
main conditions that are needed for the main theorem statement, which is
stated after this.

Let $\varepsilon>0$ and $D_{V},D_{E}$ be truncation parameters. Define

  * •

$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$

  * •

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

  * •

$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}}$

  * •

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

  * •

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

  * •

$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})|}$

In our application, as stated earlier, we show SoS lower bounds for
degree-$n^{\varepsilon}$ SoS, where the input size is $n^{O(1)}$. In this
setting, we take $D_{V},D_{E}$ to be of the order of $n^{O(\varepsilon)}$.
Therefore, for simplicity, we can interpret the parameters as

$q=n^{O(\varepsilon)},B_{vertex}=n^{O(\varepsilon)},B_{norm}(\alpha)=n^{O(\varepsilon)|V(\alpha)|}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha})}{2}}$
$B(\gamma)=n^{O(\varepsilon)|V(\gamma)|}n^{\frac{w(V(\gamma)\setminus
U_{\gamma})}{2}},N(\gamma)=n^{O(\varepsilon)|V(\gamma)|},c(\alpha)=n^{O(\varepsilon)|V(\alpha)|}$

##### Choice of parameters in the setting of Gaussian inputs on hypergraphs

We now state the parameters needed for the more general statement of the
machinery where we have Gaussian inputs on hypergraphs. In this setting, let
there be at most $t_{max}$ types of vertices and let $k$ be the maximum arity
of an hyperedge. In the setting of Tensor PCA, we take $t_{max}=1$ and in the
setting of Sparse PCA, we take $k=t_{max}=2$. For all $\varepsilon>0$ and
truncation parameters $D_{V},D_{E}$, define

  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)=\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})|}$

In our applications, we can interpret the above parameters in a much simpler
manner again. More specifically, $k$ is a constant and we work with SoS degree
$n^{\varepsilon}$. Then, we can think of each vertex or edge of the shape
$\alpha$ or $\gamma$ essentially contributing a factor of $n^{\varepsilon}$.
Therefore, we can interpret

$q=n^{O(\varepsilon)},B_{vertex}=n^{O(\varepsilon)},B_{edge}=n^{O(\varepsilon)|E(\alpha)|}$
$B_{norm}(\alpha)=n^{O(\varepsilon)(|V(\alpha)|+|E(\alpha)|)}n^{\frac{w(V(\alpha))+w(I_{\alpha})-w(S_{\alpha,min})}{2}}$
$B(\gamma)=n^{O(\varepsilon)(|V(\gamma)|+|E(\gamma)|)}n^{\frac{w(V(\gamma)\setminus
U_{\gamma})}{2}}$
$N(\gamma)=n^{O(\varepsilon)|V(\gamma)|},c(\alpha)=n^{O(\varepsilon)(|V(\alpha)|+|E(\alpha)|)}$

##### Statement of the machinery

As discussed above, consider the appropriate choice of parameters suited for
the problem. Now, we can state our conditions on the problem ${\mathcal{P}}$
in terms of its correspondingly constructed pseudo-calibrated moment matrix
$\Lambda_{{\mathcal{P}}}$ and coefficient matrices $H_{Id_{U}},H_{\tau}$.

######  Definition 1.22 (PSD mass).

We say that ${\mathcal{P}}$ satisfies (PSD mass) if for all
$U\in\mathcal{I}_{mid}$, $H_{Id_{U}}\succeq 0$.

######  Definition 1.23 (Middle shape bounds).

We say that ${\mathcal{P}}$ satisfies (Middle shape bounds) if 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$

######  Definition 1.24 (Intersection term bounds).

For some SoS-symmetric coefficient matrices
$\\{H^{\prime}_{\gamma}:\gamma\in\Gamma\\}$, ${\mathcal{P}}$ satisfies
(Intersection term bounds) with respect to them if 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}$

######  Definition 1.25 (Truncation error bounds).

For some SoS-symmetric coefficient matrices
$\\{H^{\prime}_{\gamma}:\gamma\in\Gamma\\}$, ${\mathcal{P}}$ satisfies
(Truncation error bounds) with respect to them if the following condition
holds: 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}$

Finally, we can state our main theorem.

######  Theorem 1.26.

For all $\varepsilon>0$, if we take the parameters defined above, and we have
SoS-symmetric coefficient matrices $\\{H^{\prime}_{\gamma}:\gamma\in\Gamma\\}$
such that ${\mathcal{P}}$ satisfies (PSD mass) , (Middle shape bounds) ,
(Intersection term bounds) and (Truncation error bounds) , then with
probability at least $1-\varepsilon$, $\Lambda_{{\mathcal{P}}}\succeq 0$.

In our applications, for problems ${\mathcal{P}}$ of interest, we pseudo-
calibrate, decompose into graph matrices, exhibit the desired conditions on
${\mathcal{P}}$ and invoke the machinery to prove our lower bounds.

##### Choice of $H^{\prime}_{\gamma}$ for our applications

In our applications, we choose $H^{\prime}_{\gamma}$ as follows.

  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}$.

Then, the truncation error that we need to bound 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})}$

###  2 Qualitative bounds for Planted slightly denser subgraph

####  1 Pseudo-calibration

We will pseudo-calibrate with respect the following pair of random and planted
distributions which we denote $\nu$ and $\mu$ respectively.

See 4

We assume that the input is given as $G_{i,j}$ for $i,j\in\binom{[n]}{2}$
where $G_{i,j}$ is $1$ if the edge $(i,j)$ is present in the graph and $-1$
otherwise. We work with the Fourier basis $\chi_{E}$ defined as
$\chi_{E}(G):=\prod_{(i,j)\in E}G_{i,j}$. For a subset $I\subseteq[n]$, define
$x_{I}:=\prod_{i\in I}x_{I}$.

######  Lemma 2.1.

Let $I\subseteq[n],E\subseteq\binom{[n]}{2}$. Then,

$\mathop{\mathbb{E}}_{\mu}[x_{I}\chi_{E}(G)]=\left(\frac{k}{n}\right)^{|I\cup
V(E)|}(2p-1)^{|E|}$

###### Proof.

When we sample $(G,S)$ from $\mu$, we condition on whether $I\cup
V(E)\subseteq S$.

$\displaystyle\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)]$
$\displaystyle=Pr_{(G,S)\sim\mu}[I\cup V(E)\subseteq
S]\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\subseteq S]$
$\displaystyle\qquad+Pr_{(G,S)\sim\mu}[I\cup V(E)\not\subseteq
S]\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\not\subseteq
S]$

We claim that the second term is $0$. In particular,
$\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\not\subseteq
S]=0$ because when $I\cup V(E)\not\subseteq S$, either $S$ doesn’t contain a
vertex in $I$ or an edge $(i,j)\in E$ is outside $S$. If $S$ doesn’t contain a
vertex in $I$, then $x_{I}=0$ and hence, the quantity is $0$. And if an edge
$(i,j)\in E$ is outside $S$, since this edge is sampled with probability
$\frac{1}{2}$, by taking expectations, the quantity
$\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\not\subseteq
S]$ is $0$.

Finally, note that $Pr_{(G,S)\sim\mu}[I\cup V(E)\subseteq
S]=\left(\frac{k}{n}\right)^{|I\cup V(E)|}$ and

$\mathop{\mathbb{E}}_{(G,S)\sim\mu}[x_{I}\chi_{E}(G)|I\cup V(E)\subseteq
S]=\mathop{\mathbb{E}}_{(G,S)\sim\mu}[\chi_{E}(G)|V(E)\subseteq
S]=(2p-1)^{|E|}$

The last equality follows because for each edge $e\in E$, since $e$ is present
independently with probability $p$, the expected value of $\chi_{e}$ is
$1\cdot p+(-1)\cdot(1-p)=2p-1$.

Define the degree of SoS to be $D_{sos}=n^{C_{sos}\varepsilon}$ for some
constant $C_{sos}>0$ that we choose later. And define the truncation parameter
to be $D_{V}=n^{C_{V}\varepsilon}$ for some constant $C_{V}>0$.

######  Remark 2.2 (Choice of parameters).

We first set $\varepsilon$ to be a sufficiently small constant. Based on this
choice, we will set $C_{V}$ to be a sufficiently small constant to satisfy all
the inequalities we use in our proof. Based on these choices, we can choose
$C_{sos}$ to be sufficiently small to satisfy the inequalities we use.

We will now describe the decomposition of the moment matrix $\Lambda$.

######  Definition 2.3.

If a shape $\alpha$ satisfies the following properties:

  * •

$\alpha$ is proper,

  * •

$\alpha$ satisfies the truncation parameter $D_{sos},D_{V}$.

then define

$\lambda_{\alpha}=\left(\frac{k}{n}\right)^{|V(\alpha)|}(2p-1)^{|E(\alpha)|}$

######  Corollary 2.4.

$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$.

####  2 Qualitative machinery bounds

In this section, we will prove the PSD mass condition and the qualitative
versions of the middle shape and intersection term bounds.

######  Lemma 2.5 (PSD mass).

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

While this is easy to prove directly, we would like to introduce appropriate
notation so that this lemma as well as the qualitative bounds to follow are
immediate. Therefore, we state the qualitative conditions next and then prove
them all together. Now, we define the following quantities which capture the
contribution of the vertices within $\tau,\gamma$ to the Fourier coefficients.

######  Definition 2.6.

For $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, define
$S(\tau)=\left(\frac{k}{n}\right)^{|V(\tau)|-|U_{\tau}|}(2p-1)^{|E(\tau)|}$.
And for all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and
$\gamma\in\Gamma_{U,V}$, define
$S(\gamma)=\left(\frac{k}{n}\right)^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}(2p-1)^{|E(\gamma)|}$.

We can now state our qualitative bounds, which we prove shortly.

######  Lemma 2.7 (Qualitative middle shape bounds).

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

$\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$

In the following qualitative intersection term bounds, we use the canonical
definition of $H_{\gamma}^{\prime}$ from Section 4.

######  Lemma 2.8 (Qualitative intersection term bounds).

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

$\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}=H_{\gamma}^{\prime}$

In order to prove these bounds, we define the following quantity to capture
the contribution of the vertices within $\sigma$ to the Fourier coefficients.

######  Definition 2.9.

For a shape $\sigma\in{\mathcal{L}}$, define
$T(\sigma)=\left(\frac{k}{n}\right)^{|V(\sigma)|-\frac{|V_{\sigma}|}{2}}(2p-1)^{|E(\sigma)|}$.
For $U\in{\mathcal{I}}_{mid}$, define $v_{U}$ to be the vector indexed by
$\sigma\in{\mathcal{L}}$ such that $v_{U}(\sigma)=T(\sigma)$ if
$\sigma\in{\mathcal{L}}_{U}$ and $0$ otherwise.

The following propositions are immediate from Definition 2.3.

######  Proposition 2.10.

For all $U\in{\mathcal{I}}_{mid},\rho\in{\mathcal{P}}_{U}$,
$H_{Id_{U}}=\frac{1}{|Aut(U)|}v_{U}v_{U}^{T}$.

######  Proposition 2.11.

For any $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,
$H_{\tau}=\frac{1}{|Aut(U)|^{2}}S(\tau)v_{U}v_{U}^{T}$.

The first proposition implies that for all $U\in{\mathcal{I}}_{mid}$,
$H_{Id_{U}}\succeq 0$, which is the PSD mass condition Lemma 2.5. Lemma 2.7
and Lemma 2.8 also follow easily.

###### Proof of Lemma 2.7.

$\displaystyle\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}v_{U}v_{U}^{T}&\frac{S(\tau)}{|Aut(U)|^{2}}v_{U}v_{U}^{T}\\\
\frac{S(\tau)}{|Aut(U)|^{2}}v_{U}v_{U}^{T}&\frac{S(\tau)}{|Aut(U)|}v_{U}v_{U}^{T}\end{bmatrix}\succeq
0$

###### Proof of Lemma 2.8.

Fix $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$ such that
$|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$. Note that
$|V(\sigma)|-\frac{|V_{\sigma}|}{2}+|V(\sigma^{\prime})|-\frac{|V_{\sigma^{\prime}}|}{2}+2(|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2})=|V(\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T})|$. Using Definition 2.3, we can easily verify that
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}}=T(\sigma)T(\sigma^{\prime})S(\gamma)^{2}$. Therefore, we have
$H_{Id_{V}}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=\frac{|Aut(U)|}{|Aut(V)|}S(\gamma)^{2}H_{Id_{U}}(\sigma,\sigma^{\prime})$.
Since
$H^{\prime}_{\gamma}(\sigma,\sigma^{\prime})=H_{Id_{U}}(\sigma,\sigma^{\prime})$
whenever $|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$,
this completes the proof.

###  3 Qualitative bounds for Tensor PCA

####  1 Pseudo-calibration

######  Definition 3.1 (Slack parameter).

Define the slack parameter to be $\Delta=n^{-C_{\Delta}\varepsilon}$ for a
constant $C_{\Delta}>0$.

We will pseudo-calibrate with respect the following pair of random and planted
distributions which we denote $\nu$ and $\mu$ respectively.

See 3

Let the Hermite polynomials be
$h_{0}(x)=1,h_{1}(x)=x,h_{2}(x)=x^{2}-1,\ldots$. For
$a\in\mathbb{N}^{[n]^{k}}$ and variables $A_{e}$ for $e\in[n]^{k}$, define
$h_{a}(A):=\prod_{e\in[n]^{k}}h_{e}(A_{e})$. We will work with this Hermite
basis.

######  Lemma 3.2.

Let $I\in\mathbb{N}^{n},a\in\mathbb{N}^{[n]^{k}}$. For $i\in[n]$, let
$d_{i}=\sum_{i\in e\in[n]^{k}}a_{e}$. Let $c$ be the number of $i$ such that
$I_{i}+d_{i}$ is nonzero. Then, if $I_{i}+d_{i}$ are all even, we have

$\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(A)]=\Delta^{c}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{|I|}\prod_{e\in[n]^{k}}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{a_{e}}$

Else, $\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(v)]=0$.

###### Proof.

When $A\sim\mu$, for all $e\in[n]^{k}$, we have
$A_{e}=B_{e}+\lambda\prod_{i\leq k}u_{e_{i}}$. where
$B_{e}\sim\mathcal{N}(0,1)$. Let’s analyze when the required expectation is
nonzero. We can first condition on $u$ and use the fact that for a fixed $t$,
$\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[h_{k}(g+t)]=t^{k}$ to obtain

$\mathop{\mathbb{E}}_{(u_{i},w_{e})\sim\mu}[u^{I}h_{a}(A)]=\mathop{\mathbb{E}}_{(u_{i})\sim\mu}[u^{I}\prod_{e\in[n]^{k}}(\lambda\prod_{i\leq
k}u_{e_{i}})^{a_{e}}]=\mathop{\mathbb{E}}_{(u_{i})\sim\mu}[\prod_{i\in[n]}u_{i}^{I_{i}+d_{i}}]\prod_{e\in[n]^{k}}\lambda^{a_{e}}$

Observe that this is nonzero precisely when all $I_{i}+d_{i}$ are even, in
which case

$\mathop{\mathbb{E}}_{(u_{i})\sim\mu}[\prod_{i\in[n]}u_{i}^{I_{i}+d_{i}}]=\Delta^{c}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{\sum_{i\leq n}I_{i}+d_{i}}=\Delta^{c}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{|I|}\prod_{e\in[n]^{k}}\left(\frac{1}{(\Delta
n)^{\frac{k}{2}}}\right)^{a_{e}}$

where we used the fact that $\sum_{e\in[n]^{k}}a_{e}=k\sum_{i\in[n]}d_{i}$.
This completes the proof.

Define the degree of SoS to be $D_{sos}=n^{C_{sos}\varepsilon}$ for some
constant $C_{sos}>0$ that we choose later. And define the truncation
parameters to be $D_{V}=n^{C_{V}\varepsilon},D_{E}=n^{C_{E}\varepsilon}$ for
some constants $C_{V},C_{E}>0$.

######  Remark 3.3 (Choice of parameters).

We first set $\varepsilon$ to be a sufficiently small constant. Based on the
choice of $\varepsilon$, we will set the constant $C_{\Delta}>0$ sufficiently
small so that the planted distribution is well defined. Based on these
choices, just as in 2.2 we choose $C_{V},C_{E},C_{sos}$ in that order.

The underlying graphs for the graph matrices have the following structure;
There will be $n$ vertices of a single type and the edges will be ordered
hyperedges of arity $k$. For the analysis of Tensor PCA, we will use the
following notation.

  * •

For an index shape $U$ and a vertex $i$, define $deg^{U}(i)$ as follows: If
$i\in V(U)$, then it is the power of the unique index shape piece $A\in U$
such that $i\in V(A)$. Otherwise, it is $0$.

  * •

For an index shape $U$, define $deg(U)=\sum_{i\in V(U)}deg^{U}(i)$. This is
also the degree of the monomial that $U$ corresponds to.

  * •

For a shape $\alpha$ and vertex $i$ in $\alpha$, let
$deg^{\alpha}(i)=\sum_{i\in e\in E(\alpha)}l_{e}$.

  * •

For any shape $\alpha$, let $deg(\alpha)=deg(U_{\alpha})+deg(V_{\alpha})$.

We will now describe the decomposition of the moment matrix $\Lambda$.

######  Definition 3.4.

If a shape $\alpha$ satisfies the following properties:

  * •

$deg^{\alpha}(i)+deg^{U_{\alpha}}(i)+deg^{V_{\alpha}}(i)$ is even for all
$i\in V(\alpha)$,

  * •

$\alpha$ is proper,

  * •

$\alpha$ satisfies the truncation parameters $D_{sos},D_{V},D_{E}$.

then define

$\lambda_{\alpha}=\Delta^{|V(\alpha)|}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{deg(\alpha)}\prod_{e\in E(\alpha)}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $\lambda_{\alpha}=0$.

######  Corollary 3.5.

$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$.

####  2 Qualitative machinery bounds

Just as in planted slightly denser subgraph, we prove the PSD mass condition
and the qualitative middle shape and intersection term bounds, by first
stating them and then introducing appropriate notation to prove them all in a
unified manner.

######  Lemma 3.6 (PSD mass).

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

We define the following quantities to capture the contribution of the vertices
within $\tau,\gamma$ to the Fourier coefficients.

######  Definition 3.7.

For $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, if
$deg^{\tau}(i)$ is even for all vertices $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, define

$S(\tau)=\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}\left(\frac{\lambda}{(\Delta n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $S(\tau)=0$. For all $U,V\in{\mathcal{I}}_{mid}$ where
$w(U)>w(V)$ and $\gamma\in\Gamma_{U,V}$, if $deg^{\gamma}(i)$ is even for all
vertices $i$ in $V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$, define

$S(\gamma)=\Delta^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}\prod_{e\in
E(\gamma)}\left(\frac{\lambda}{(\Delta n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $S(\gamma)=0$.

We now state the qualitative bounds in terms of these quantities.

######  Lemma 3.8 (Qualitative middle shape bounds).

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

$\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$

We again use the canonical definition of $H_{\gamma}^{\prime}$ from Section 4.

######  Lemma 3.9 (Qualitative intersection term bounds).

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

$\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

##### Proof of PSD mass condition

We introduce some notation which makes it easy to show the qualitative bounds
and which also sheds light on the structure of the coefficient matrices. When
we compose shapes $\sigma,\sigma^{\prime}$, from Definition 3.4, in order for
$\lambda_{\sigma\circ\sigma^{\prime}}$ to be nonzero, observe that all
vertices $i$ in $\lambda_{\sigma\circ\sigma^{\prime}}$ should have
$deg^{\sigma\circ\sigma^{\prime}}(i)+deg^{U_{\sigma\circ\sigma^{\prime}}}(i)+deg^{V_{\sigma\circ\sigma^{\prime}}}(i)$
to be even. To partially capture this notion conveniently, we will introduce
the notion of parity vectors.

######  Definition 3.10.

Define a parity vector $\rho$ to be a vector whose entries are in $\\{0,1\\}$.
For $U\in{\mathcal{I}}_{mid}$, define ${\mathcal{P}}_{U}$ to be the set of
parity vectors $\rho$ whose coordinates are indexed by $U$.

######  Definition 3.11.

For a left shape $\sigma$, define
$\rho_{\sigma}\in{\mathcal{P}}_{V_{\sigma}}$, called the parity vector of
$\sigma$, to be the parity vector such that for each vertex $i\in V_{\sigma}$,
the $i$-th entry of $\rho_{\sigma}$ is the parity of
$deg^{U_{\sigma}}(i)+deg^{\sigma}(i)$, that is $(\rho_{\sigma})_{i}\equiv
deg^{U_{\sigma}}(i)+deg^{\sigma}(i)\pmod{2}$. For $U\in{\mathcal{I}}_{mid}$
and $\rho\in{\mathcal{P}}_{U}$, let ${\mathcal{L}}_{U,\rho}$ be the set of all
left shapes $\sigma\in{\mathcal{L}}_{U}$ such that $\rho_{\sigma}=\rho$, that
is, the set of all left shapes with parity vector $\rho$.

For a shape $\tau$, for a $\tau$ coefficient matrix $H_{\tau}$ and parity
vectors
$\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}$,
define the $\tau$-coefficient matrix $H_{\tau,\rho,\rho^{\prime}}$ as
$H_{\tau,\rho,\rho^{\prime}}(\sigma,\sigma^{\prime})=H_{\tau}(\sigma,\sigma^{\prime})$
if
$\sigma\in{\mathcal{L}}_{U_{\tau},\rho},\sigma^{\prime}\in{\mathcal{L}}_{V_{\tau},\rho^{\prime}}$
and $0$ otherwise. The following proposition is immediate.

######  Proposition 3.12.

For any shape $\tau$ and $\tau$-coefficient matrix $H_{\tau}$, we have the
equality
$H_{\tau}=\sum_{\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}}H_{\tau,\rho,\rho^{\prime}}$

######  Proposition 3.13.

For any $U\in{\mathcal{I}}_{mid}$,
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}$

###### Proof.

For any $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$, using Definition 3.4,
note that in order for $H_{Id_{U}}(\sigma,\sigma^{\prime})$ to be nonzero, we
must have $\rho_{\sigma}=\rho_{\sigma^{\prime}}$.

We define the following quantity to capture the contribution of the vertices
within $\sigma$ to the Fourier coefficients.

######  Definition 3.14.

For a shape $\sigma\in{\mathcal{L}}$, if $deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$
is even for all vertices $i\in V(\sigma)\setminus V_{\sigma}$, define

$T(\sigma)=\Delta^{|V(\sigma)|-\frac{|V_{\sigma}|}{2}}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{deg(U_{\sigma})}\prod_{e\in E(\sigma)}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{l_{e}}$

Otherwise, define $T(\sigma)=0$. For $U\in{\mathcal{I}}_{mid}$ and
$\rho\in{\mathcal{P}}_{U}$, define $v_{\rho}$ to be the vector indexed by
$\sigma\in{\mathcal{L}}$ such that $v_{\rho}(\sigma)$ is $T(\sigma)$ if
$\sigma\in{\mathcal{L}}_{U,\rho}$ and $0$ otherwise.

With this notation, the PSD mass condition is easily shown.

###### Proof of the PSD mass condition Lemma 3.6.

For all $U\in{\mathcal{I}}_{mid},\rho\in{\mathcal{P}}_{U}$, Definition 3.4
implies $H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}v_{\rho}v_{\rho}^{T}$.
Therefore,

$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}\sum_{\rho\in{\mathcal{P}}_{U}}v_{\rho}v_{\rho}^{T}\succeq
0$

##### Qualitative middle shape bounds

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

######  Proposition 3.15.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, there exist
two sets of parity vectors $P_{\tau},Q_{\tau}\subseteq{\mathcal{P}}_{U}$ and a
bijection $\pi:P_{\tau}\rightarrow Q_{\tau}$ such that $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}$.

###### Proof.

Using Definition 3.4, in order for $H_{\tau}(\sigma,\sigma^{\prime})$ to be
nonzero, in $\sigma\circ\tau\circ\sigma^{\prime}$, we must have that for all
$i\in U_{\tau}\cup V_{\tau}$,
$deg^{U_{\sigma}}(i)+deg^{U_{\sigma^{\prime}}}(i)+deg^{\sigma\circ\tau\circ\sigma^{\prime
T}}(i)$ must be even. In other words, for any $\rho\in{\mathcal{P}}_{U}$,
there is at most one $\rho^{\prime}\in{\mathcal{P}}_{U}$ such that if we take
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U}$ with
$H_{\tau}(\sigma,\sigma^{\prime})$ nonzero, then the parity of
$\sigma^{\prime}$ is $\rho^{\prime}$. Also, observe that $\rho^{\prime}$
determines $\rho$. We then take $P_{\tau}$ to be the set of $\rho$ such that
$\rho^{\prime}$ exists, $Q_{\tau}$ to be the set of $\rho^{\prime}$ and in
this case, we define $\pi(\rho)=\rho^{\prime}$.

A straightforward verification of the conditions of Definition 3.4 implies the
following proposition.

######  Proposition 3.16.

For any $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose we
take $\rho\in P_{\tau}$. Let $\pi$ be the bijection from 3.15 so that
$\pi(\rho)\in Q_{\tau}$. Then,
$H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)v_{\rho}v_{\pi(\rho)}^{T}$.

We can now prove the qualitative middle shape bounds.

###### Proof of the qualitative middle shape bounds Lemma 3.8.

Let $P_{\tau},Q_{\tau},\pi$ be from 3.15. For
$\rho,\rho^{\prime}\in{\mathcal{P}}_{U}$, let
$W_{\rho,\rho^{\prime}}=v_{\rho}(v_{\rho^{\prime}})^{T}$. Then,
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}$
and $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}$. We have

$\displaystyle\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$
$\displaystyle=\frac{S(\tau)}{|Aut(U)|^{2}}\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\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}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}\succeq
0$. Consider

$\displaystyle\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}=$
$\displaystyle\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}\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\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}}v_{\rho}v_{\rho}^{T}\succeq 0$. Similarly,
$\sum_{\rho\in{\mathcal{P}}_{U}\setminus Q_{\tau}}W_{\rho,\rho}\succeq 0$ and
so, the first term in the above expression,
$\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}\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}W_{\rho,\pi(\rho)}^{T}&\sum_{\rho\in
P_{\tau}}W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$ $\displaystyle=\sum_{\rho\in
P_{\tau}}\begin{bmatrix}W_{\rho,\rho}&W_{\rho,\pi(\rho)}\\\
W_{\rho,\pi(\rho)}^{T}&W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$
$\displaystyle=\sum_{\rho\in
P_{\tau}}\begin{bmatrix}v_{\rho}v_{\rho}^{T}&v_{\rho}(v_{\pi(\rho)})^{T}\\\
v_{\pi(\rho)}(v_{\rho})^{T}&v_{\pi(\rho)}(v_{\pi(\rho)})^{T}\end{bmatrix}$
$\displaystyle=\sum_{\rho\in P_{\tau}}\begin{bmatrix}v_{\rho}\\\
v_{\pi(\rho)}\end{bmatrix}\begin{bmatrix}v_{\rho}&v_{\pi(\rho)}\end{bmatrix}$
$\displaystyle\succeq 0$

##### Qualitative intersection term bounds

Similar to 3.15, 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^{\prime T}\circ\sigma^{\prime T}}$ to
be nonzero, the parities of the degrees of the merged vertices should add up
correspondingly.

We use the following notation. 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 3.17.

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 3.4, 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}$.

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. The
following proposition is immediate from the definition.

######  Proposition 3.18.

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}$.

######  Proposition 3.19.

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

$H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}=\frac{|Aut(U)|}{|Aut(V)|}S(\gamma)^{2}H^{\prime}_{\gamma,\rho,\rho}$

###### 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
$|V(\sigma)|-\frac{|V_{\sigma}|}{2}+|V(\sigma^{\prime})|-\frac{|V_{\sigma^{\prime}}|}{2}+2(|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2})=|V(\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T})|$. Using Definition 3.4, we can easily verify that
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}}=T(\sigma)T(\sigma^{\prime})S(\gamma)^{2}$. Therefore,
$H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}(\sigma,\sigma^{\prime})=\frac{|Aut(U)|}{|Aut(V)|}S(\gamma)^{2}H_{Id_{U},\rho,\rho}(\sigma,\sigma^{\prime})$.
Since
$H^{\prime}_{\gamma,\rho,\rho}(\sigma,\sigma^{\prime})=H_{Id_{U},\rho,\rho}(\sigma,\sigma^{\prime})$
whenever we have $|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq
D_{V}$, this completes the proof.

With this, we can prove the qualitative intersection term bounds.

###### Proof of qualitative intersection term bounds Lemma 3.9.

We have

$\displaystyle\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}=\sum_{\rho\in
P_{\gamma}}\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}}H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}=\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}$

where we used the fact that for all $\rho\in{\mathcal{P}}_{U}$, we have
$H^{\prime}_{\gamma,\rho,\rho}\succeq 0$.

###  4 Qualitative bounds for Sparse PCA

####  1 Pseudo-calibration

######  Definition 4.1 (Slack parameter).

Define the slack parameter to be $\Delta=d^{-C_{\Delta}\varepsilon}$ for a
constant $C_{\Delta}>0$.

We will pseudo-calibrate with respect the following pair of random and planted
distributions which we denote $\nu$ and $\mu$ respectively.

See 2

We will again work with the Hermite basis of polynomials. For
$a\in\mathbb{N}^{m\times d}$ and variables $v_{i,j}$ for $i\in[m],j\in[n]$,
define $h_{a}(v):=\prod_{i\in[m],j\in[n]}h_{a_{i,j}}(v_{i,j})$. For a
nonnegative integer $t$, define $t!!=\frac{(2t)!}{t!2^{t}}=1\times
3\times\ldots\times t$ if $t$ is odd and $0$ otherwise.

######  Lemma 4.2.

Let $I\in\mathbb{N}^{d},a\in\mathbb{N}^{m\times d}$. For $i\in[m]$, let
$e_{i}=\sum_{j\in[d]}a_{ij}$ and for $j\in[d]$, let
$f_{j}=I_{j}+\sum_{i\in[m]}a_{ij}$. Let $c_{1}$ (resp. $c_{2}$) be the number
of $i$ (resp. $j$) such that $e_{i}>0$ (resp. $f_{j}>0$). Then, if
$e_{i},f_{j}$ are all even, we have

$\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(v)]=\left(\frac{1}{\sqrt{k}}\right)^{|I|}\left(\frac{k}{d}\right)^{c_{2}}\Delta^{c_{1}}\prod_{i\in[m]}(e_{i}-1)!!\prod_{i,j}\frac{\sqrt{\lambda}^{a_{ij}}}{\sqrt{k}^{a_{ij}}}$

Else, $\mathop{\mathbb{E}}_{\mu}[u^{I}h_{a}(v)]=0$.

###### Proof.

$v_{1},\ldots,v_{m}\sim\mu$ can be written as
$v_{i}=g_{i}+\sqrt{\lambda}b_{i}l_{i}u$ where
$g_{i}\sim\mathcal{N}(0,I_{d}),l_{i}\sim\mathcal{N}(0,1),b_{i}\in\\{0,1\\}$
where $b_{i}=1$ with probability $\Delta$. Let’s analyze when the required
expectation is nonzero. We can first condition on $b_{i},l_{i},u$ and use the
fact that for a fixed $t$,
$\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[h_{k}(g+t)]=t^{k}$ to obtain

$\displaystyle\mathop{\mathbb{E}}_{(u,l_{i},b_{i},g_{i})\sim\mu}[u^{I}h_{a}(v)]$
$\displaystyle=\mathop{\mathbb{E}}_{(u,l_{i},b_{i})\sim\mu}[u^{I}\prod_{i,j}(\sqrt{\lambda}b_{i}l_{i}u_{j})^{a_{ij}}]$
$\displaystyle=\mathop{\mathbb{E}}_{(u,l_{i},b_{i})\sim\mu}[\prod_{i\in[m]}(b_{i}l_{i})^{e_{i}}\prod_{j\in[d]}u_{j}^{f_{j}}]\prod_{i,j}\sqrt{\lambda}^{a_{ij}}$

For this to be nonzero, the set of $c_{1}$ indices $i$ such that $e_{i}>0$,
should not have been resampled otherwise $b_{i}=0$, each of which happens
independently with probability $\Delta$. And the set of $c_{2}$ indices $j$
such that $f_{j}>0$ should have been such that $u_{j}$ is nonzero, each of
which happens independently with probability $\frac{k}{d}$. Since
$l_{i},u_{j}$ are have zero expectation in $\nu$, we need $e_{i},f_{j}$ to be
even. The expectation then becomes