# Distribution of the threshold for the symmetric perceptron

Ashwin Sah  and  Mehtaab Sawhney  Department of Mathematics, Massachusetts
Institute of Technology, Cambridge, MA 02139, USA<EMAIL_ADDRESS>
###### Abstract.

We derive an explicit distribution for the threshold sequence of the symmetric
binary perceptron with Gaussian disorder, proving that the critical window is
of constant width.

Sah and Sawhney were supported by NSF Graduate Research Fellowship Program
DGE-1745302. Sah was supported by the PD Soros Fellowship. Sawhney was
supported by the Churchill Foundation.

##  1\. Introduction

We fix a real number $\kappa>0$ throughout the rest of this paper.

######  Definition 1.1.

Let $\Sigma_{n}=\\{\pm 1\\}^{n}$. Given an infinite sequence $M=(M_{j})_{j\geq
1}$ of vectors in $\mathbb{R}^{n}$, let

$S_{j}(M):=\\{x\in\Sigma_{n}\colon|\langle
x,M_{j}\rangle|\leq\kappa\sqrt{n}\\},\qquad
S^{m}(M):=\bigcap_{j=1}^{m}S_{j}(M).$

Furthermore, define the _threshold_ $\tau=\tau(M)$ as the first index such
that

$S^{\tau-1}(M)\neq\emptyset\text{ ~{}and }S^{\tau}(M)=\emptyset,$

or $+\infty$ if it does not exist. Let $G=(G_{j})_{j\geq 1}$ be a sequence of
independent standard $n$-dimensional Gaussian vectors, i.e.,
$G_{j}\sim\mathcal{N}(0,I_{n})$. The _threshold for the symmetric binary
perceptron with Gaussian disorder_ is $\tau=\tau(G)$ (note $\tau(G)<+\infty$
almost surely).

We note that the threshold as defined in Definition 1.1 is up to rescaling
equivalent to the _storage capacity_ of the binary perceptron model. We have
chosen to work with Gaussian disorder as it marginally simplifies certain
computations. The limiting distribution can immediately be extended to
Rademacher disorder, although various quantitative error terms will differ and
the mean and variance of an associated log-normal distribution $Z^{\ast}$ must
be slightly changed.

We will require the following basic special functions.

######  Definition 1.2.

Let $Z,Z_{1},Z_{2}\sim\mathcal{N}(0,1)$ be independent standard Gaussians. Let
$p=\mathbb{P}[|Z|\leq\kappa]$ and define the critical value

$\alpha_{c}:=-\log 2/\log p.$

We also define

$\mu_{2}=\frac{\mathbb{E}[Z^{2}\mathbbm{1}_{|Z|\leq\kappa}]}{p},\quad\beta=-\frac{\sqrt{\alpha_{c}}}{2}(1-\mu_{2}).$

Finally we define the _pair probability function_

$q(\gamma)=\mathbb{P}\big{[}|\sqrt{\gamma}Z_{1}+\sqrt{1-\gamma}Z_{2}|\leq\kappa\wedge|\sqrt{\gamma}Z_{1}-\sqrt{1-\gamma}Z_{2}|\leq\kappa\big{]}.$

We note that $-1/2<\beta<0$ follows from [3, (3.8)]. We now state our main
theorem.

######  Theorem 1.3.

Let $G$ and $\tau=\tau(G)$ be as in Definition 1.1. There exists $\theta>0$
such that the following holds for all sufficiently large $n$. Let
$Z^{\ast}\sim\mathcal{N}(\frac{1}{4}\log(1-4\beta^{2}),-\frac{1}{2}\log(1-4\beta^{2}))$
and choose $k$ with $k+\alpha_{c}n\in\mathbb{Z}$. We have

$\bigg{|}\mathbb{P}[\tau\leq
k+\alpha_{c}n]-\mathbb{E}\bigg{[}\exp\bigg{(}\frac{-e^{Z^{\ast}}p^{k}}{2}\bigg{)}\bigg{]}\bigg{|}\leq
n^{-\theta}.$

######  Remark 1.4.

The polynomial rate specified by Theorem 1.3 is essentially the limit of our
method. Combining the statement of Theorem 1.3 with the tails bounds given by
Altschuler [3, Theorem 2], one can prove that there exists $C$ such that for
any fixed $q\geq 1$ and $n$ large in terms of $q$:

$\mathbb{E}|\tau-\alpha_{c}n|^{q}\leq C^{q}.$

We also note that Theorem 1.3 disproves [3, Conjecture 1] since the upper tail
$\mathbb{P}[\tau\geq k+\alpha_{c}n]$ is of exponential type in $k>0$.

###  1.1. Previous work

A toy model for neural networks, the (asymmetric) perceptron model has been a
model of substantial interest, in part stemming from conjectures on the
asymptotic threshold due to Krauth and Mezard [13]. Despite progress on a
number of related problems, progress on the perceptron has proved considerably
more difficult. In this direction, groundbreaking work of Ding and Sun [8]
establishes the conjectural lower bound for the threshold and recent work of
Xu [19] has established an analog of Friedgut’s sharp threshold theorem [11]
for such models (see work of Nakajima and Sun [15] for an alternate proof). In
particular these sharp threshold results establish that for general perceptron
models, $\tau$ typically lives within an interval of length $o(n)$.

The symmetric perceptron model, introduced in work of Aubin, Perkins, and
Zdeborová [4], has proven to be considerably more tractable at a mathematical
level due the availability of the moment method applied directly to the number
of solutions (while for the asymmetric perceptron model a substantially more
involved conditioning scheme is required). It provides a test-bed for various
conjectural phenomena since the solution space geometries of symmetric and
asymmetric perceptron are expected to behave similarly. In particular, work of
Aubin, Perkins, and Zdeborová [4] established that w.h.p.
$\tau<(\alpha_{c}+\epsilon)n$ and with positive probability that
$\tau>(\alpha_{c}-\epsilon)n$. The determination of the threshold (with
scaling window $o(n)$) at $\alpha_{c}n$ with high probability was proven
independently by Abbe, Li, and Sly [2] and Perkins and Xu [17]111We note that
the work of Aubin, Perkins, and Zdeborová [4] and Perkins and Xu [17] was
conditional on a numerical hypothesis which was verified in the work of Abbe,
Li, and Sly [2].. Both the works of Abbe, Li, and Sly [2] and Perkins and Xu
[17] establish that $\log|S^{m}(G)|$ concentrates around
$\log\mathbb{E}[|S^{m}(G)|]$. Furthermore, the work of Abbe, Li, and Sly [2]
establishes that $S^{m}(G)$ has a log-normal distribution (when $m$ is
linearly bounded away from the threshold) via a modification of “small
subgraph conditioning” made suitable for dense models. Finally, in recent work
Altschuler [3] substantially improved the concentration window by proving that
the first and second moment of number of solutions at
$\lceil\alpha_{c}n\rceil$ match up to a constant. Adapting the argument for
concentration given by Perkins and Xu [17], Altschuler derived that the window
of concentration is $O(\log n)$ w.h.p. We refer the reader to [3, Section 2]
for a more extensive discussion of previous works on the threshold, discussion
of threshold for more general constraint satisfaction problems, and related
work.

We also note that there has recently been work on understanding efficient
algorithms for the symmetric perceptron; in particular work of Abbe, Li, and
Sly [1] proves that efficient algorithms can find exponentially rare clusters
at sufficiently low density and work of Gamarnik, Kızıldağ, Perkins, and Xu
[12] examines the limits of efficient algorithms for the symmetric perceptron
through the lens of the multi-Overlap Gap Property.

###  1.2. Stopping time and Poisson sampling heuristic

The key ingredient our in work is an early stopping time argument, which
combined with an understanding of the geometry of the remaining solutions is
sufficient to derive a distribution for the threshold. More precisely, define
the (non-random) cutoff time $\tau_{\mathrm{pre}}=\lfloor\alpha_{c}n-\eta\log
n\rfloor$ for some sufficiently small constant $\eta>0$. By mimicking the
techniques of Abbe, Li, and Sly [2] (for Gaussian disorder), one can prove
that the number of solutions to the perceptron at $\tau_{\mathrm{pre}}$
follows a log-normal distribution; we note here that the fact that the second
and first moments match so close to the threshold is a critical insight found
in the work of Altschuler [3]. Furthermore, the moment computations of
Altschuler (in particular the “frozen” nature of typical solutions) can be
used to prove that all pairs of solutions are essentially orthogonal (e.g.
have dot product bounded in magnitude by $n^{1/2}\log n$).

The crucial idea at this point is to note that since w.h.p. at
$\tau_{\mathrm{pre}}$ there are a small polynomial number of solutions, the
pairwise dot product of solutions being near zero can be translated to near-
independence of the event of whether these solutions will survive the next
slices. In particular, the total variation distance between the true
distribution and a natural product distribution is polynomially small. The
desired result then follows noting that there are only logarithmically more
steps and thus the computation of the threshold sequence reduces to a
computation with product distributions: we have some set $S$ of solutions at
time $\tau_{\mathrm{pre}}$ and each solution is retained for
$t-\tau_{\mathrm{pre}}$ extra slices with probability
$p^{t-\tau_{\mathrm{pre}}}$, so an independence heuristic suggests that
$\mathbb{P}[\mathrm{Bin}(|S|,p^{t-\tau_{\mathrm{pre}}})=0]$ is roughly the
chance that we empty the solution set in $t$ steps, where $\mathrm{Bin}$
denotes a binomial random variable. In our regime, this can be approximated
via a Poissonian heuristic that gives rise to the expression in Theorem 1.3
(after incorporating the fact that $|S|/\mathbb{E}|S|$ satisfies a log-normal
distribution). We note that the strange factor of $2$ arising in the
distribution in Theorem 1.3 stems from the fact that $v\in S$ if and only if
$-v\in S$.

We note that in implementing the above sketch in order to give polynomial
error rates, the primary difficulty is quantifying the work of Abbe, Li, and
Sly [2] (and adjusting it to both handle when the number of hyperplanes is
near the threshold and to allow for Gaussian disorder). In order to provide a
quantitative rate we transform the necessary cycle count distributional claims
under conditional models to distributional questions about unconditioned
Gaussian polynomials (via orthogonal invariance of Gaussians and various
expectation and variance computations) and then provide quantitative rates via
Stein’s method (in paricular through the use of exchangeable pairs), rather
than the method of moments used in [2]. We note one curious feature is that
the distribution of solutions at $\tau_{\mathrm{pre}}$, while still being log-
normal, does not have the same mean and variance parameters as the Rademacher
case derived in [2]. The difference ultimately arises from the fact that if
$M\sim\mathcal{N}(0,1)$, then $M^{2}$ has nontrivial variance whereas $M^{2}$
is constant if $M\sim\mathrm{Unif}(\\{\pm 1\\})$. (This difference manifests
in the need to track the degenerate $2$-cycle count corresponding to $k=1$ in
Definition 3.2; we note that the $k=1$ expression in the Rademacher case would
be deterministic, hence the difference.)

We note that the methods of this paper appear to more generally applicable; in
particular, our approach can likely be adapted give a precise characterization
of the threshold for solutions in constrained $k$-XORSAT which was shown to
have an $O(1)$-size scaling window by Pittel and Sorkin [18] (see also [9,
7]). We intend to return to this subject in future work.

### Organization

The remainder of the paper is organized as follows. In Section 2, we prove
Theorem 1.3 conditional on the “strong freezing” of the solution space and on
the log-normality of the number of solutions (Proposition 2.1). This argument
implements the main thrust of the paper outlined in Section 1.2. We reduce
Proposition 2.1 to a concrete moment computation (Lemma 2.7) in Section 2.1.
In Section 3, we state preliminaries used to verify the moment computation
including a suitable quantification of cycle count convergence as defined in
the work of Abbe, Li, and Sly [2]. Finally, in Section 4, we prove the
necessary moment estimates to imply Proposition 2.1, which in turn closely
follows the work of Altschuler [3] and Abbe, Li, and Sly [2].

### Acknowledgements

We thank Will Perkins for bringing this problem to our attention and pointing
out the work of Pittel and Sorkin [18], and for various useful comments on the
draft. We also thank Mark Sellke for finding a number of typos and Michael Ren
for useful conversations.

### Notation

All dependences of notation or asymptotics on $\kappa$ have been suppressed,
and we treat it as a fixed absolute constant throughout the paper. We write
$f=O(g)$ to mean that $f\leq Cg$ for some absolute constant $C$, and
$g=\Omega(f)$ and $f\lesssim g$ to mean the same. We write $f=o(g)$ if for all
$c>0$ we have $f\leq cg$ once the implicit growing parameter (typically $n$)
grows large enough, and $g=\omega(f)$ means the same. Furthermore throughout
this paper all logarithms are base $e$.

For positive semidefinite $\Sigma\in\mathbb{R}^{d\times d}$ we let
$\mathcal{N}(0,\Sigma)$ be the Gaussian vector with covariance matrix
$\Sigma$. A common choice is $\Sigma=I_{d}$, the standard Gaussian vector with
identity covariance. For a discrete random variable $X$ with nonzero
probabilities $p_{1},\ldots,p_{m}$ for its atoms, its entropy is

$H(X)=-\sum_{i=1}^{m}p_{i}\log p_{i}.$

The Kullback–Leibler divergence between $X,Y$ defined on the same atom set
with probabilities $q_{i},r_{i}$ respectively is

$\operatorname{KL}(X\parallel Y)=\sum_{i=1}^{m}q_{i}\log\frac{q_{i}}{r_{i}}$

and we define the real function $H(x)=H(\mathrm{Ber}(x))=-x\log
x-(1-x)\log(1-x)$. If $X,Y$ are supported on $\mathbb{R}^{d}$ with probability
densities $q,r$ their KL divergence is

$\operatorname{KL}(q\parallel
r)=\int_{\mathbb{R}^{d}}q(x)\log\frac{q(x)}{r(x)}dx.$

For real matrices $A$ and $B$, let

$\langle
A,B\rangle=\operatorname{tr}(A^{T}B),\qquad\|A\|_{\mathrm{HS}}=\sqrt{\operatorname{tr}(A^{T}A)}=\sqrt{\langle
A,A\rangle}.$

Furthermore for an order $k$ tensor define

$\|A\|_{\mathrm{op}}=\sup_{|v_{i}|=1}|A(v_{1},v_{2},\ldots,v_{k})|.$

Finally for $f\in\mathcal{C}^{k}(\mathbb{R}^{n})$ define the $k^{th}$
derivative (tensor) operators evaluated at
$u_{1},\ldots,u_{k}\in\mathbb{R}^{n}$ as

$\langle
D^{k}f(x),(u_{1},\ldots,u_{k})\rangle=\sum_{i_{1},i_{2},\ldots,i_{k}\in[n]}\frac{\partial^{k}f}{\partial
x_{i_{1}}\ldots\partial x_{i_{k}}}(u_{1})_{i_{1}}\ldots(u_{k})_{i_{k}}$

and define

$M_{r}(g)=\sup_{x\in\mathbb{R}^{n}}\|D^{r}g(x)\|_{\mathrm{op}}.$

For a matrix $A$ define $\lVert
A\rVert_{\mathrm{HS}}^{2}=\sum_{i,j}|a_{ij}|^{2}$.

##  2\. Proof of Theorem 1.3

In order to derive our main result we will assume the following pair of
structural properties of the solution space and its size. Here and beyond, we
fix some $\eta>0$ that will be chosen small in terms of only $\kappa$ at the
end of the argument. For now, we leave it unspecified in the various
statements that appear, merely using that it is sufficiently small in the
proofs.

######  Proposition 2.1.

There exists $\gamma>0$ such that the following holds. Let
$\tau_{\mathrm{pre}}=\lfloor\alpha_{c}n-\eta\log n\rfloor$. For $n$
sufficiently large, we have the following pair of estimates on the size of the
solution space $X(G):=|S_{\tau_{\mathrm{pre}}}(G)|$ for $n$ sufficiently
large.

  1. 1.

With probability at least $1-n^{-1}$ there do not exist $x_{1},x_{2}\in
S_{\tau_{\mathrm{pre}}}(G)$ such that $|\langle
x_{1},x_{2}\rangle|\in[n^{1/2}\log n,n-1]$.

  2. 2.

Let
$Z^{\ast}=\mathcal{N}(\frac{1}{4}\log(1-4\beta^{2}),-\frac{1}{2}\log(1-4\beta^{2}))$.
Then for all $t\in\mathbb{R}$,

$\mathbb{P}\bigg{[}\frac{X(G)}{\mathbb{E}X(G)}\geq
e^{t}\bigg{]}=\mathbb{P}[Z^{\ast}\geq t]\pm n^{-\gamma}.$

We will also require the following tail bounds on the number of solutions. The
second appears explicitly as [3, Theorem 3] which in turns builds closely on
work of Perkins and Xu [17].

######  Proposition 2.2 ([3, Theorem 3]).

We have the following.

  1. 1.

For all $t\geq 0$ we have

$\mathbb{P}[|S_{t}(G)|\geq 1]\leq 2^{n}p^{t}.$

  2. 2.

There exists a constant $c=c_{\ref{prop:tails}}>0$ such that following holds.
Fix $H\geq c^{-1}$. Suppose that $n$ is sufficiently large in terms of $H$.
Then

$\mathbb{P}[S_{\lfloor\alpha_{c}n-H\log
n\rfloor}(G)=\emptyset]\leq\exp(-cH\log n).$

We require the following basic bound on the total variation distance between a
pair of normal distributions.

######  Lemma 2.3.

For positive definite symmetric matrices
$\Sigma_{1},\Sigma_{2}\in\mathbb{R}^{d\times d}$, we have

$2\operatorname{TV}(\mathcal{N}(0,\Sigma_{1}),\mathcal{N}(0,\Sigma_{2}))^{2}\leq\operatorname{KL}(\mathcal{N}(0,\Sigma_{1})\parallel\mathcal{N}(0,\Sigma_{2}))=\frac{1}{2}\big{(}\log(\det(\Sigma_{2}\Sigma_{1}^{-1}))-d+\operatorname{tr}(\Sigma_{2}^{-1}\Sigma_{1})\big{)}.$

###### Proof.

The first inequality is by Pinsker’s inequality (see e.g. [6, Lemma 2]),
holding for general distributions. The equality is a straightforward Gaussian
integral (see e.g. [10, Page 13]). ∎

Now we prove Theorem 1.3 given these inputs.

###### Proof of Theorem 1.3.

Let $\tau_{\mathrm{pre}}$, $\eta$ and $X(G)$ be as in Proposition 2.1. Let

$\mathcal{E}_{1}=\\{X(G)\geq\mathbb{E}[X(G)]\cdot\exp((\log
n)^{3/4})\\}\cup\\{X(G)\leq\mathbb{E}[X(G)]\cdot\exp(-(\log n)^{3/4})\\}$

and

$\mathcal{E}_{2}=\\{|\langle x_{1},x_{2}\rangle|\in[n^{1/2}\log
n,n-1]:x_{1},x_{2}\in S_{\tau_{\mathrm{pre}}}\\}.$

We now reveal set $S=S_{\tau_{\mathrm{pre}}}(G)\cap\\{x:x_{1}=1\\}$ and note
that $\mathcal{E}_{1}$, $\mathcal{E}_{2}$, and $X(G)$ are deterministic given
$S_{\tau_{\mathrm{pre}}}(G)$. We note that Proposition 2.1 implies that
$\mathbb{P}[\mathcal{E}_{1}\cup\mathcal{E}_{2}]\leq n^{-\Omega(1)}$ (since
$|Z^{\ast}|\leq(\log n)^{3/4}$ occurs with super-polynomially good
probability). We condition on a revelation of $S$ such that
$\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}$ holds.

We now consider $G_{t}$ for
$t\in(\tau_{\mathrm{pre}},\tau_{\mathrm{pre}}+2\eta\log n]$ and consider the
distribution induced by

$\\{\langle G_{t},x_{i}\rangle/\sqrt{n}:x_{i}\in
S,t\in(\tau_{\mathrm{pre}},\tau_{\mathrm{pre}}+2\eta\log n]\\}.$

Note that $G_{t}$ are independent for
$t\in(\tau_{\mathrm{pre}},\tau_{\mathrm{pre}}+2\eta\log n]$. Let $M$ denote a
$X(G)/2$ by $n$ matrix where each row corresponds to an entry of $S$. Notice
that for each $t\in(\tau_{\mathrm{pre}},\tau_{\mathrm{pre}}+\lceil 2\eta\log
n\rceil]$ we have that

$\\{\langle G_{t},x_{i}\rangle/\sqrt{n}:x_{i}\in
S\\}\sim\mathcal{N}(0,MM^{T}/n).$

The crucial point is that since $MM^{T}/n$ is sufficiently diagonally dominant
we will be able to prove that the distribution is close in total variation
distance to $\mathcal{N}(0,I_{|S|})$. To prove this, note that

$\displaystyle\lVert MM^{T}/n-I_{|S|}\rVert_{\mathrm{op}}^{2}$
$\displaystyle\leq\lVert
MM^{T}/n-I_{|S|}\rVert_{\operatorname{F}}^{2}\leq|S|^{2}\max_{\begin{subarray}{c}x_{1},x_{2}\in
S\\\ x_{1}\neq x_{2}\end{subarray}}|\langle x_{1},x_{2}\rangle|^{2}/n^{2}$
$\displaystyle\leq|S|^{2}\cdot n^{-3/4}\leq n^{-1/2}$

due to $\mathcal{E}_{2}^{c}$ holding and the fact that $S$ does not
simultaneously contain any pair $\\{x,-x\\}$.

This immediately implies that all the eigenvalues of $MM^{T}/n$ are of the
form $1\pm n^{-1/4}$ and therefore by Lemma 2.3 we have that

$\displaystyle\operatorname{TV}(\mathcal{N}(0,I_{|S|}),\mathcal{N}(0,MM^{T}/n))$
$\displaystyle\leq(\operatorname{Tr}(MM^{T}/n)-|S|+\log(\det(MM^{T}/n)))/2$
$\displaystyle\leq|S|n^{-1/4}+|S|\log(1+n^{-1/4})\leq n^{-1/5}.$

The last inequality comes from $|S|=X(G)/2\leq\mathbb{E}X(G)\cdot\exp((\log
n)^{3/4})\leq n^{O(\eta)}$ by the choice of $\tau_{\mathrm{pre}}$, and
assuming $\eta$ is small enough.

As we are restricting attention to
$t\in(\tau_{\mathrm{pre}},\tau_{\mathrm{pre}}+\lceil 2\eta\log n\rceil]$ we
have that

$\operatorname{TV}((\\{\langle G_{t},x_{i}\rangle/\sqrt{n}:x_{i}\in
S\\})_{t\in(\tau_{\mathrm{pre}},\tau_{\mathrm{pre}}+\lceil 2\eta\log
n\rceil]},\mathcal{N}(0,I_{|S|})^{\otimes\lceil 2\eta\log n\rceil}))\leq
n^{-1/6}.$

Since $S$ satisfies $\mathcal{E}_{1}^{c}\cup\mathcal{E}_{2}^{c}$, this implies
that for $t\in(\tau_{\mathrm{pre}},\tau_{\mathrm{pre}}+\lceil 2\eta\log
n\rceil]$ we have

$\mathbb{P}[S_{t}=\emptyset|S_{\tau_{\mathrm{pre}}}]=(1-p^{t-\tau_{\mathrm{pre}}})^{X(G)/2}\pm
n^{-1/6}.$

We now choose a constant $\rho>0$ which is sufficiently small with respect to
$\eta$. We first isolate the case where $t\in[\lceil\alpha_{c}n-\rho\log
n\rceil,\lceil\alpha_{c}n+\rho\log n\rceil]$. Notice that we therefore have
that

$\displaystyle\mathbb{P}[S_{t}=\emptyset]$
$\displaystyle=\mathbb{P}[S_{t}=\emptyset\cap(\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c})]\pm\mathbb{P}[\mathcal{E}_{1}\cup\mathcal{E}_{2}]$
$\displaystyle=\mathbb{P}[S_{t}=\emptyset\cap(\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c})]\pm
n^{-\Omega(1)}$
$\displaystyle=\mathbb{E}[(1-p^{t-\tau_{\mathrm{pre}}})^{X(G)/2}\mathbbm{1}_{\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}}]\pm
n^{-\Omega(1)}$
$\displaystyle=\mathbb{E}\bigg{[}\exp\bigg{(}\frac{-p^{t-\tau_{\mathrm{pre}}}\cdot
X(G)}{2}\bigg{)}\mathbbm{1}_{\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}}\bigg{]}\pm
n^{-\Omega(1)}.$

The final equality requires justification: note that
$(1-p)^{t-\tau_{\mathrm{pre}}})^{X(G)}\leq 1$, $1-x=e^{-x+O(x^{2})}$ for all
$|x|\leq 1/2$, and

$\exp(p^{2(t-\tau_{\mathrm{pre}})}\cdot X(G))\leq 1+n^{-\Omega(1)}$

by using that $\mathcal{E}_{1}^{c}$ holds and some basic computation.

Let $Z^{\ast}$ be as in Proposition 2.1. This implies that

$\displaystyle\mathbb{E}\bigg{[}\exp\bigg{(}\frac{-p^{t-\tau_{\mathrm{pre}}}\cdot
X(G)}{2}\bigg{)}\mathbbm{1}_{\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}}\bigg{]}$
$\displaystyle=\int_{0}^{1}\mathbb{P}\bigg{[}\exp\bigg{(}\frac{-p^{t-\tau_{\mathrm{pre}}}\cdot
X(G)}{2}\bigg{)}\mathbbm{1}_{\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}}\geq
u\bigg{]}du$
$\displaystyle=\int_{0}^{1}\mathbb{P}\bigg{[}\exp\bigg{(}\frac{-e^{Z^{\ast}}\mathbb{E}[X(G)]p^{t-\tau_{\mathrm{pre}}}}{2}\bigg{)}\geq
u\bigg{]}du\pm n^{-\Omega(1)}$
$\displaystyle=\mathbb{E}\bigg{[}\exp\bigg{(}\frac{-e^{Z^{\ast}}\mathbb{E}[X(G)]p^{t-\tau_{\mathrm{pre}}}}{2}\bigg{)}\bigg{]}\pm
n^{-\Omega(1)}$ $\displaystyle=\mathbb{E}[\exp(-e^{Z^{\ast}}2^{n-1}p^{t})]\pm
n^{-\Omega(1)}.$

This implies the desired result for $t$ in the specified interval.

For $t\leq\alpha_{c}n-\gamma\log n$, we have that

$\mathbb{P}[|S_{t}|=\emptyset]\leq\mathbb{P}[|S_{\lfloor\alpha_{c}n-\gamma\log
n\rfloor}|=\emptyset]\leq n^{-\Omega(1)},$

using what we have established for $t=\lfloor\alpha_{c}n-\gamma\log n\rfloor$
and explicitly computing $\mathbb{E}\exp(e^{-Z^{\ast}}2^{n-1}p^{t})$, which
implies the desired result in this range. Finally for
$t\geq\alpha_{c}n+\gamma\log n$, we have that

$\mathbb{P}[|S_{t}|\neq\emptyset]\leq\mathbb{E}[|S_{t}|]\leq p^{(\gamma\log
n)/2}\leq n^{-\Omega(1)}$

from Proposition 2.2(1) which immediately implies the desired result in this
range. This finishes the proof. ∎

We also prove the remark following Theorem 1.3.

###### Proof of Remark 1.4.

Fix $q\geq 1$. Let $\tau^{\ast}$ be the random variable such that
$\mathbb{P}[\tau^{\ast}\leq
k+\alpha_{c}n]=\mathbb{E}\big{[}\exp\big{(}-\frac{e^{Z^{\ast}}p^{k}}{2}\big{)}\big{]}$
for all choices of $k+\alpha_{c}n\in\mathbb{Z}$. Taking $H=2qc^{-1}$ and
applying Proposition 2.2(1,2), we have that

$\displaystyle\mathbb{E}|\tau-\alpha_{c}n|^{q}$
$\displaystyle\leq\mathbb{E}[|\tau-\alpha_{c}n|^{q}\mathbbm{1}_{|\tau-\alpha_{c}n|\leq
H\log n}]+\mathbb{E}[|\tau-\alpha_{c}n|^{q}\mathbbm{1}_{|\tau-\alpha_{c}n|\geq
H\log n}]$
$\displaystyle\leq\mathbb{E}[|\tau-\alpha_{c}n|^{q}\mathbbm{1}_{|\tau-\alpha_{c}n|\leq
H\log n}]+(2\alpha_{c}n)^{q}\exp(-2q\log
n)+\mathbb{E}[\tau^{q}\mathbbm{1}_{\tau\geq 2\alpha_{c}n}]$
$\displaystyle\leq\mathbb{E}[|\tau-\alpha_{c}n|^{q}\mathbbm{1}_{|\tau-\alpha_{c}n|\leq
H\log n}]+n^{-q/2}$
$\displaystyle\leq\mathbb{E}[|\tau^{\ast}-\alpha_{c}n|^{q}\mathbbm{1}_{|\tau-\alpha_{c}n|\leq
H\log n}]+n^{-\Omega(1)}$
$\displaystyle\leq\mathbb{E}|\tau^{\ast}-\alpha_{c}n|^{q}+n^{-\Omega(1)}$
$\displaystyle\leq C^{q}$

Note that bounds derived on the upper tail for $\tau$ are an immediate
consequence of Proposition 2.2(1) and the final inequality follows from noting
that $\tau^{\ast}$ has subexponential tails by direct calculation. ∎

###  2.1. Reduction to normalized second moment computation

We now formally state the second moment computation that we perform in the
remainder of the paper and use these results to prove Proposition 2.1. We
first define the key random variables used for small graph conditioning used
in the definition of the moments.

######  Definition 2.4.

The _$2k$ -cycle count_ of a sequence of vectors $M=(M_{j})_{j\geq 1}$ is

$C_{k}(m,M)=\bigg{(}\frac{1}{\sqrt{n}}\bigg{)}^{k}\bigg{(}\frac{1}{\sqrt{m}}\bigg{)}^{k}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in[n]\text{
distinct}\\\ j_{1},\ldots,j_{k}\in[m]\text{
distinct}\end{subarray}}\prod_{i=1}^{k}M_{j_{\ell},i_{\ell}}M_{j_{\ell},i_{\ell+1}}-\mathbbm{1}_{k=1}\sqrt{mn},$

where we let $i_{k+1}=i_{1}$. Then the _$K$ -weighted cycle count_ is

$Y_{K}(m,M)=\sum_{k=1}^{K}\frac{2(2\beta)^{k}C_{k}(m,M)-(2\beta)^{2k}}{4k}.$

######  Remark 2.5.

Notice that for $k=1$, this is a shifted sum of squares of Gaussians. Such an
expression is trivial in the Rademacher setting and hence is not required in
the work of Abbe, Li, and Sly [2].

We also define certain planted conditional distributions that are key in
computing the moments.

######  Definition 2.6.

For $t\in[-n,n]$ with $t\equiv n\pmod{2}$ define
$v_{t}=(1,\ldots,1,-1,\ldots,-1)\in\mathbb{R}^{n}$ where there are $(n+t)/2$
many $1$s. Let $\Delta_{0}\sim\mathcal{N}(0,1)^{\otimes n}$. Let $\Delta_{1}$
be $x\sim\Delta_{0}$ conditional on the event $\\{|\langle
x,v_{n}\rangle|\leq\kappa\sqrt{n}\\}$. Let $\Delta_{2}(t)$ be
$x\sim\Delta_{1}$ conditional on the further event $\\{|\langle
x,v_{t}\rangle|\leq\kappa\sqrt{n}\\}$. Then let $G^{(0)}=G$, which has its
vectors drawn from $\Delta_{0}$, and let $G^{(1)}=(G^{(1)}_{j})_{j\geq 1}$
have vectors drawn independently from $\Delta_{1}$ and
$G^{(2)}(t)=(G^{(2)}_{j}(t))_{j\geq 1}$ have vectors drawn independently from
$\Delta_{2}(t)$.

We have the following weighted moment estimate.

######  Lemma 2.7.

There exists $\gamma>0$ such that the following holds. Let
$m=\tau_{\mathrm{pre}}=\lfloor\alpha_{c}n-\eta\log n\rfloor$ and suppose $n$
is large. With $L=\eta\log n$, $K=\lceil\eta\log n\rceil$, and
$\delta=n^{-\gamma}$ we have

$\displaystyle\mathbb{E}\bigg{[}\frac{X(G)}{\exp(Y_{K}(m,G)\mathbbm{1}[Y_{K}(m,G)\geq-L])}\bigg{]}\geq(1-\delta)\mathbb{E}X(G)$
(2.1)
$\displaystyle\mathbb{E}\bigg{[}\frac{X(G)^{2}}{\exp(2Y_{K}(m,G)\mathbbm{1}[Y_{K}(m,G)\geq-L])}\bigg{]}\leq(1+\delta)\mathbb{E}X(G)^{2}.$
(2.2)

Additionally, we have

$\sum_{t\in[-(n-1),-n^{1/2}\log n]\cup[n^{1/2}\log
n,n-1]}2^{n}\binom{n}{(n+t)/2}\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\mathrm{pre}}}(G)]\leq\exp(-(\log n)^{3/2}).$ (2.3)

To prove this moment estimate we will use Bayes’ theorem, requiring an
understanding of the $L$-weighted cycle count when the vectors of $M$ are
drawn from the planted conditional distributions.

######  Lemma 2.8.

Let $m=\tau_{\mathrm{pre}}=\lfloor\alpha_{c}n-\eta\log n\rfloor$,
$K=\lceil\eta\log n\rceil$, and $|t|\leq\sqrt{n}\log n$. We define

$V(M):=\bigg{(}\frac{C_{1}(m,M)}{\sqrt{2\cdot
1}},\ldots,\frac{C_{K}(m,M)}{\sqrt{2K}}\bigg{)},\quad\mu:=\bigg{(}\frac{(2\beta)^{1}}{\sqrt{2\cdot
1}},\ldots,\frac{(2\beta)^{K}}{\sqrt{2K}}\bigg{)}.$

For $g\in\mathcal{C}^{3}(\mathbb{R}^{K})$ and $n$ sufficiently large we have

$\displaystyle|\mathbb{E}[g(V(G^{(0)}))]-\mathbb{E}_{Z\sim\mathcal{N}(0,I_{K}))}[g(Z)]|$
$\displaystyle\leq(M_{1}(g)+M_{2}(g)+M_{3}(g))n^{-1/5},$ (2.4)
$\displaystyle|\mathbb{E}[g(V(G^{(1)})-\mu)]-\mathbb{E}_{Z\sim\mathcal{N}(0,I_{K}))}[g(Z)]|$
$\displaystyle\leq(M_{1}(g)+M_{2}(g)+M_{3}(g))n^{-1/5},$ (2.5)
$\displaystyle|\mathbb{E}[g(V(G^{(2)}(t))-2\mu)]-\mathbb{E}_{Z\sim\mathcal{N}(0,I_{K}))}[g(Z)]|$
$\displaystyle\leq(M_{1}(g)+M_{2}(g)+M_{3}(g))n^{-1/5},$ (2.6)

Now we prove Proposition 2.1.

###### Proof of Proposition 2.1.

We prove each of the items of Proposition 2.1 in turn. For the first item
notice by linearity of expectation that

$\displaystyle\mathbb{E}[|\\{x_{1},x_{2}\in
S_{\tau_{\operatorname{pre}}}(G)\colon$ $\displaystyle|\langle
x_{1},x_{2}\rangle|\in[-(n-1),-n^{2/3}]\cup[n^{2/3},n-1]\\}|]$
$\displaystyle=\sum_{t\in[-(n-1),-n^{1/2}\log n]\cup[n^{1/2}\log
n,n-1]}2^{n}\binom{n}{(n+t)/2}\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\mathrm{pre}}}(G)]$ $\displaystyle\leq\exp(-(\log n)^{3/2})$

by using 2.3. The first item then follows immediately by Markov’s inequality.

For the second item, let
$\widetilde{X}(G)=\frac{X(G)}{\exp(Y_{K}(m,G)\mathbbm{1}[Y_{K}(m,G)\geq-L])}$.
By 2.1 and 2.2 we have that

$\mathbb{E}\bigg{[}\bigg{(}\frac{\widetilde{X}(G)}{\mathbb{E}[X(G)]}-1\bigg{)}^{2}\bigg{]}\leq
3n^{-\gamma}.$

Therefore with probability $1-n^{-\Omega(1)}$ we have that
$\widetilde{X}(G)=(1\pm n^{-\Omega(1)})\mathbb{E}[X(G)]$. Equivalently this
implies that with probability $1-n^{-\Omega(1)}$,

$X(G)/\mathbb{E}[X(G)]=(1\pm
n^{-\Omega(1)})\exp(Y_{K}(m,G)\mathbbm{1}[Y_{K}(m,G)\geq-L]).$

The result then follows from Lemma 2.8: $Y_{k}(m,G)$ is a function of the
coordinates of $V(G)$, which is close in test function distance to
$\mathcal{N}(0,I_{K})$. Therefore, the distribution of $X(G)/\mathbb{E}X(G)$
ought to look like an exponential of an appropriate Gaussian with mean
$\sum_{k=1}^{K}\frac{-(2\beta)^{2k}}{4k}\approx(1/4)\log(1-4\beta^{2})$ and
variance
$\sum_{k=1}^{K}\bigg{(}\frac{(2\beta)^{k}}{\sqrt{2k}}\bigg{)}^{2}\approx-(1/2)\log(1-4\beta^{2})$
(these terms come from the linear expression of $Y_{K}(m,G)$ in terms of
$V(G)$).

To make this quantitative, we choose appropriate bump functions $g$ in 2.4 and
use the fact that Gaussian distributions are appropriately anticoncentrated;
we omit the routine justification (see e.g. [5, Lemma 7.1]; see also Section
4.1 for a similar computation). ∎

##  3\. Preliminaries for moment computations

###  3.1. Estimates on Gaussian pair probabilities

We will require the following special function estimates on the pair point
probabilities derived in the work of Abbe, Li, and Sly [2] and in work of
Altschuler [3]. The first bullet is equivalent to the first bullet of [3,
Lemma 3.1], the next three bullets appear exactly as in [3, Lemma 3.1] (these
were originally established in [2, Section 4.7]), the fifth appears as [3,
(4.6)], and the sixth appears as [3, (4.3)].

######  Lemma 3.1 (From [3, Lemma 3.1], [3, (4.6)], [3, (4.3)]).

There exists $\varepsilon=\varepsilon_{\ref{lem:computation}}>0$ such that the
following hold. Let $F(\gamma):=H(\gamma)+\alpha_{c}\log q(\gamma)$.

  1. bxS2

$q^{\prime\prime}(1/2)=\frac{8\kappa^{2}e^{-\kappa^{2}}}{\pi}$

  2. bxS2

$F^{\prime\prime}(1/2)\leq-\varepsilon$.

  3. bxS2

$F(\gamma)$ is decreasing for $\gamma\in[0,\varepsilon]$.

  4. bxS2

For any $0\leq a\leq b\leq 1/2$,

$\max_{\beta\in[a,b]}F(\gamma)=\max\\{F(a),F(b),F(1/2)-\varepsilon\\}.$

  5. bxS2

$F(1/n)\leq F(0)-\varepsilon/\sqrt{n}.$

  6. bxS2

$(1-\mu_{2})p=\sqrt{\frac{2}{\pi}}\kappa e^{-\kappa^{2}/2}$

###  3.2. Quantification of Gaussian convergence

In order to prove the required Gaussian convergence of the random variables
$Y_{K}$, we will prove Lemma 2.8 in this section, essentially following the
approach of Abbe, Li, and Sly [2, Lemma 3.2]. We note their argument is
written for Rademacher disorder, and additionally in order to prove Remark
1.4, we will need to adapt various arguments in order to prove a stronger
convergence result. To do so, we proceed indirectly via a linear algebraic
change using the Gaussian structure. Specifically, we will first show that in
a sense, sampling the vectors of $M$ from the conditional distributions
$\Delta_{1}$ or $\Delta_{2}(t)$ for $|t|$ small (i.e., setting $M=G^{(1)}$ or
$M=G^{(2)}(t)$) is very similar to sampling from
$\Delta_{0}=\mathcal{N}(0,I_{n})$ (i.e., $M=G^{(0)}=G$) up to a mean shift.
Then we will show the necessary multivariate central limit theorem for
$\Delta_{0}$ using multidimensional Stein’s method machinery adapted from
Meckes [14]. As our argument essentially serves as a more effective version of
the bounds given in [2, Lemma 3.2] in the Gaussian case, we will be brief with
certain basic calculations.

To reduce to $\Delta_{0}$, we introduce a slightly more general cycle count
which allows us to plug in different conditional distributions.

######  Definition 3.2.

Given $M$ and $-n<t<n$ with $t\equiv n\pmod{2}$, we define

$\displaystyle\sigma_{j,i}(t,M)$
$\displaystyle=\frac{1}{(n+t)/2}\sum_{i^{\prime}=1}^{(n+t)/2}M_{j,i^{\prime}},$
$\displaystyle\widetilde{M}_{j,i}(t)=M_{j,i}-\sigma_{j,i}(t,M),\qquad$
$\displaystyle\text{for }1\leq i\leq\frac{n+t}{2},$
$\displaystyle\sigma_{j,i}(t,M)$
$\displaystyle=\frac{1}{(n-t)/2}\sum_{i^{\prime}=(n+t)/2+1}^{n}M_{j,i^{\prime}},$
$\displaystyle\widetilde{M}_{j,i}(t)=M_{j,i}-\sigma_{j,i}(t,M),\qquad$
$\displaystyle\text{for }\frac{n+t}{2}<i\leq n.$

If we are further given a sequence of $\mathbb{R}^{n}$ vectors
$\sigma=(\sigma_{j})_{j\geq 1}$, we define

$\widetilde{C}_{k}(m,t,M,\sigma)=\frac{1}{(mn)^{k/2}}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in[n]\text{
distinct}\\\ j_{1},\ldots,j_{k}\in[m]\text{
distinct}\end{subarray}}\prod_{\ell=1}^{k}\bigg{(}\widetilde{M}_{j_{\ell},i_{\ell}}(t)+\sigma_{j_{\ell},i_{\ell}}\bigg{)}\bigg{(}\widetilde{M}_{j_{\ell},i_{\ell+1}}(t)+\sigma_{j_{\ell},i_{\ell+1}}\bigg{)}-\mathbbm{1}_{k=1}\sqrt{mn}.$

The key point of this definition is that

$C_{k}(m,M)=\widetilde{C}_{k}(m,t,M,\sigma(t,M))$

and the distributions of $\widetilde{M}(t)$ and $\sigma(t,M)$ are independent
in all relevant cases (namely $M=G^{(0)},G^{(1)},G^{(2)}(t)$). Furthermore,
across all relevant cases we have that the distribution of $\widetilde{M}(t)$
is identical, so the distributions of $C_{k}(m,M)$ and
$\widetilde{C}_{k}(m,t,G,\sigma(t,M))$ are identical. Thus it suffices to
understand the differences in the models via the parameters $\sigma$, which
merely encode the average of the first $(n+t)/2$ and last $(n-t)/2$ elements
of each vector. Therefore, we prove the following, which essentially shows the
resulting statistics $V(M)$ are the same up to shifting of means.

######  Lemma 3.3.

Let $m=\tau_{\mathrm{pre}}=\lfloor\alpha_{c}n-\eta\log n\rfloor$ and
$K=\lceil\eta\log n\rceil$. Given $1\leq k\leq K$ and $|t|\leq\sqrt{n}\log n$,
we have

$\displaystyle\mathbb{E}\big{[}\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(1)}))-C_{k}(m,G)\big{]}$
$\displaystyle=(1+\widetilde{O}(n^{-1}))(2\beta)^{k},$ (3.1)
$\displaystyle\mathbb{E}\big{[}\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(2)}(t)))-C_{k}(m,G)\big{]}$
$\displaystyle=(1+\widetilde{O}(n^{-1/4}))2\cdot(2\beta)^{k},$ (3.2)
$\displaystyle\operatorname{Var}\big{[}\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(1)}))-C_{k}(m,G)\big{]}$
$\displaystyle=O(n^{-5/6}\operatorname{Var}[C_{k}(m,G)]),$ (3.3)
$\displaystyle\operatorname{Var}\big{[}\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(2)}(t)))-C_{k}(m,G)\big{]}$
$\displaystyle=O(n^{-5/6}\operatorname{Var}[C_{k}(m,G)]).$ (3.4)

###### Proof.

We define

$\rho_{1}^{(0)}=\sigma_{1,1}(t,G^{(0)}),\rho_{2}^{(0)}=\sigma_{1,n}(t,G^{(0)})$

and similar for $G^{(1)},G^{(2)}(t)$. Note that $\sigma_{1,i}$ for all
$i\in\\{1,\ldots,(n+t)/2\\}$ will give exactly $\rho_{1}$ and $\sigma_{1,i}$
for all $i\in\\{(n+t)/2+1,\ldots,n\\}$ will give exactly $\rho_{2}$.
Furthermore, as we vary $j$ in $\sigma_{j,i}$, we do not have the exact same
value but we have an independent value that is drawn from the same
distribution. For instance, note that
$\rho_{1}^{(0)}=(G_{1,1}+\cdots+G_{1,(n+t)/2})/((n+t)/2)$ and $\rho_{2}^{(0)}$
some Gaussians, while $(\rho_{1}^{(1)},\rho_{2}^{(1)})$ have the distribution
of $(x,y)=(\rho_{1}^{(0)},\rho_{2}^{(0)})$ conditioned on
$|(n+t)x/2+(n-t)y/2|\leq\kappa\sqrt{n}$, and $(\rho_{1}^{(2)},\rho_{2}^{(2)})$
have the distribution of $(x,y)=(\rho_{1}^{(1)},\rho_{2}^{(1)})$ further
conditioned on $|(n+t)x/2-(n-t)y/2|\leq\kappa\sqrt{n}$.

We first note that

$\mathbb{E}\rho_{1}^{(b)}=\mathbb{E}\rho_{2}^{(b)}=0$ (3.5)

for all $b\in\\{0,1,2\\}$, and

$\mathbb{E}\rho_{1}^{(b)}\rho_{2}^{(b)}=0$ (3.6)

for $b\in\\{0,2\\}$. This can be seen from symmetry. Note that $b=1$ does have
some covariance. Additionally, we have

$\mathbb{E}(\rho_{1}^{(0)})^{2}=\frac{1}{(n+t)/2},\quad\mathbb{E}(\rho_{2}^{(0)})^{2}=\frac{1}{(n-t)/2}.$

Finally, we can compute

$\mathbb{E}(\rho_{1}^{(2)})^{2}=(1+\widetilde{O}(n^{-1/4}))\frac{2\mu_{2}}{n+t},\quad\mathbb{E}(\rho_{2}^{(2)})^{2}=(1+\widetilde{O}(n^{-1/4}))\frac{2\mu_{2}}{n-t},$

using that the distribution of $(\rho_{1}^{(2)},\rho_{2}^{(2)})$ is that of
$(\rho_{1}^{(0)},\rho_{2}^{(0)})$, which are independent Gaussians,
conditional on two explicit linear inequalities. (The error term comes from
the possible deviation in $t$; if $t=0$ these are easily seen to be precise
equalities.)

We first consider 3.2 and 3.4. For the expectation, note that $G,G^{(2)}(t)$
are independent and $G,G^{(2)}(t)$ are mean $0$ (the latter since we are in
the symmetric perceptron), so for $k>1$

$\displaystyle\mathbb{E}$
$\displaystyle[\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(2)}(t)))-C_{k}(m,G)]=\mathbb{E}[\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(2)}(t)))]$
$\displaystyle=\frac{1}{(mn)^{k/2}}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in[n]\text{
distinct}\\\ j_{1},\ldots,j_{k}\in[m]\text{
distinct}\end{subarray}}\mathbb{E}\bigg{[}\prod_{\ell=1}^{k}\big{(}\widetilde{G}_{j_{\ell},i_{\ell}}+\sigma_{j_{\ell},i_{\ell}}(t,G^{(2)}(t))\big{)}\big{(}\widetilde{G}_{j_{\ell},i_{\ell+1}}+\sigma_{j_{\ell},i_{\ell+1}}(t,G^{(2)}(t))\big{)}\bigg{]}$
$\displaystyle=\frac{1}{(mn)^{k/2}}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in[n]\text{
distinct}\\\ j_{1},\ldots,j_{k}\in[m]\text{
distinct}\end{subarray}}\bigg{(}\prod_{\ell=1}^{k}\mathbb{E}[\widetilde{G}_{j_{\ell},i_{\ell}}\widetilde{G}_{j_{\ell},i_{\ell+1}}+\sigma_{j_{\ell},i_{\ell}}(t,G^{(2)}(t))\sigma_{j_{\ell},i_{\ell+1}}(t,G^{(2)}(t))]\bigg{)}$
$\displaystyle=\frac{(m)\cdots(m-k+1)}{(mn)^{k/2}}\sum_{i_{1},\ldots,i_{k}\in[n]\text{
distinct}}\bigg{(}\prod_{\ell=1}^{k}\mathbb{E}[\widetilde{G}_{j_{\ell},i_{\ell}}\widetilde{G}_{j_{\ell},i_{\ell+1}}+\sigma_{j_{\ell},i_{\ell}}(t,G^{(2)}(t))\sigma_{j_{\ell},i_{\ell+1}}(t,G^{(2)}(t))]\bigg{)}.$

Now if any $i_{\ell},i_{\ell+1}$ are not in the same group
$\\{1,\ldots,(n+t)/2\\},\\{(n+t)/2+1,\ldots,n\\}$ then the corresponding terms
are $0$ by 3.6. Thus we must either choose all $i_{\ell}$ to be in one group
or the other to have nonzero contribution. Additionally, the choice of
$j_{1},\ldots,j_{k}$ does not impact the inner term, which implies

$\displaystyle\mathbb{E}$
$\displaystyle[\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(2)}(t)))-C_{k}(m,G)]=\mathbb{E}[\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(2)}(t)))]$
$\displaystyle=\frac{(m)\cdots(m-k+1)}{(mn)^{k/2}}\bigg{(}\bigg{(}\frac{n+t}{2}\bigg{)}\cdots\bigg{(}\frac{n+t}{2}-k+1\bigg{)}\bigg{(}-\frac{2}{n+t}+\mathbb{E}(\rho_{1}^{(2)})^{2}\bigg{)}^{k}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\bigg{(}\frac{n-t}{2}\bigg{)}\cdots\bigg{(}\frac{n-t}{2}-k+1\bigg{)}\bigg{(}-\frac{2}{n-t}+\mathbb{E}(\rho_{2}^{(2)})^{2}\bigg{)}^{k}\bigg{)}$
$\displaystyle=(1+\widetilde{O}(n^{-1/4}))\alpha_{c}^{k/2}(2(\mu_{2}-1)^{k})=(1+\widetilde{O}(n^{-1/4}))2(2\beta)^{k}$

We used that $\mathbb{E}\widetilde{G}_{j,1}\widetilde{G}_{j,2}=-2/(n+t)$ and
similar for the other index group. This establishes 3.2 for $k>1$. For $k=1$,
we again see $\mathbb{E}C_{1}(m,G)=0$ so we obtain

$\displaystyle\frac{m}{\sqrt{mn}}$
$\displaystyle\bigg{(}\sum_{i=1}^{n}\mathbb{E}\widetilde{G}_{1,i}^{2}+\mathbb{E}\sigma_{1,1}(t,G^{(2)}(t))^{2}+\mathbb{E}\sigma_{1,n}(t,G^{(2)}(t))^{2}\bigg{)}-\sqrt{mn}$
$\displaystyle=\frac{m}{\sqrt{mn}}\bigg{(}\frac{n+t}{2}-1+\frac{n-t}{2}-1+(1+\widetilde{O}(n^{-1/4}))(\mu_{2}+\mu_{2})\bigg{)}-\sqrt{mn}=(1+\widetilde{O}(n^{-1/4}))2(2\beta).$

For 3.4, we easily compute
$\operatorname{Var}[C_{k}(m,G)]=(1+\widetilde{O}(n^{-1}))2k$ (using that cycle
terms have covariance $0$ unless they represent the exact same cycle, and
using that there are $2k$ ways to represent each particular cycle). Thus it
suffices to bound the desired variance by a smaller than constant order. We
expand and compute the order of magnitude of each covariance term that
appears. Writing $X_{j,i}^{(0)}=Y_{j,i}^{(0)}=\widetilde{G}_{j,i}$ and
$X_{j,i}^{(1)}=\sigma_{j,i}(t,G^{(2)}(t))$ and
$Y_{j,i}^{(1)}=\sigma_{j,i}(t,G)$, we have

$\displaystyle\operatorname{Var}[\widetilde{C}_{k}(m,t,$ $\displaystyle
G,\sigma(t,G^{(2)}(t)))-C_{k}(m,G)]$
$\displaystyle\leq\frac{2^{2k}}{(mn)^{k}}\sum_{b\in\\{0,1\\}^{2k}}\operatorname{Var}\bigg{[}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in[n]\\\
j_{1},\ldots,j_{k}\in[m]\end{subarray}}\bigg{(}\prod_{\ell=1}^{k}X_{j_{\ell},i_{\ell}}^{(b_{2\ell-1})}X_{j_{\ell},i_{\ell+1}}^{(b_{2\ell})}-\prod_{\ell=1}^{k}Y_{j_{\ell},i_{\ell}}^{(b_{2\ell-1})}Y_{j_{\ell},i_{\ell+1}}^{(b_{2\ell})}\bigg{)}\bigg{]}$

by the Cauchy–Schwarz inequality. Now we compute the order of magnitude of a
single contribution corresponding to a fixed $b\in\\{0,1\\}^{2k}$. We obtain

$\sum_{i,j,i^{\prime},j^{\prime}}\mathbb{E}\bigg{[}\bigg{(}\prod_{\ell=1}^{k}X_{j_{\ell},i_{\ell}}^{(b_{2\ell-1})}X_{j_{\ell},i_{\ell+1}}^{(b_{2\ell})}-\prod_{\ell=1}^{k}Y_{j_{\ell},i_{\ell}}^{(b_{2\ell-1})}Y_{j_{\ell},i_{\ell+1}}^{(b_{2\ell})}-\mathbb{E}[\cdot]\bigg{)}\bigg{(}\prod_{\ell=1}^{k}X_{j_{\ell}^{\prime},i_{\ell}^{\prime}}^{(b_{2\ell-1})}X_{j_{\ell}^{\prime},i_{\ell+1}^{\prime}}^{(b_{2\ell})}-\prod_{\ell=1}^{k}Y_{j_{\ell}^{\prime},i_{\ell}^{\prime}}^{(b_{2\ell-1})}Y_{j_{\ell}^{\prime},i_{\ell+1}^{\prime}}^{(b_{2\ell})}-\mathbb{E}[\cdot]\bigg{)}\bigg{]}$
(3.7)

where each $\cdot$ is replaced with the preceding difference of products and
where $i,j,i^{\prime},j^{\prime}$ are summing over sequences of distinct
values over the appropriate ranges.

To estimate this, we first consider the order of magnitude of an individual
term. Any such term is composed of values $\widetilde{G}_{j,i},\sigma_{j,i}$.
Furthermore, to avoid the expectation being $0$, we must have an even number
of $\sigma_{j,i}$ terms for each possible index $j$, and an even number of
$\widetilde{G}_{j,i}$ for each $j$. Note that
$\mathbb{E}\sigma_{j,i}^{2a}=O_{a}(n^{-a})$ for either version of $\sigma$
(coming from $G^{(0)},G^{(2)}(t)$). Additionally,

$\mathbb{E}\widetilde{G}_{1,1}\widetilde{G}_{1,2}=O(1/n),\quad\mathbb{E}\widetilde{G}_{1,1}\widetilde{G}_{1,2}\widetilde{G}_{1,3}\widetilde{G}_{1,4}=O(1/n^{2}),\quad\mathbb{E}\widetilde{G}_{1,1}^{2}\widetilde{G}_{1,3}\widetilde{G}_{1,4}=O(1/n)$

follows from explicit computation.

Therefore, we easily find that (using independence of the random variables
associated to different $j$ and using that every $j$ can only appear once in
$(j_{\ell})_{\ell\in[k]},(j_{\ell}^{\prime})_{\ell\in[k]}$):

$\displaystyle\mathbb{E}$
$\displaystyle\bigg{[}\bigg{(}\prod_{\ell=1}^{k}X_{j_{\ell},i_{\ell}}^{(b_{2\ell-1})}X_{j_{\ell},i_{\ell+1}}^{(b_{2\ell})}-\prod_{\ell=1}^{k}Y_{j_{\ell},i_{\ell}}^{(b_{2\ell-1})}Y_{j_{\ell},i_{\ell+1}}^{(b_{2\ell})}-\mathbb{E}[\cdot]\bigg{)}\bigg{(}\prod_{\ell=1}^{k}X_{j_{\ell}^{\prime},i_{\ell}^{\prime}}^{(b_{2\ell-1})}X_{j_{\ell}^{\prime},i_{\ell+1}^{\prime}}^{(b_{2\ell})}-\prod_{\ell=1}^{k}Y_{j_{\ell}^{\prime},i_{\ell}^{\prime}}^{(b_{2\ell-1})}Y_{j_{\ell}^{\prime},i_{\ell+1}^{\prime}}^{(b_{2\ell})}-\mathbb{E}[\cdot]\bigg{)}\bigg{]}$
$\displaystyle=(O(1/n))^{2k-t},$

where $r$ is the number of $\widetilde{G}^{2}$ terms that occur in the
expanded product. We used that there are $4k$ total terms $X,Y$ in any
resulting product (the inner expectation terms can be handled similarly). This
means that the $2k$-cycle formed by
$(i_{\ell})_{\ell\in[k]},(j_{\ell})_{\ell\in[k]}$ and the $2k$-cycle formed by
$(i_{\ell}^{\prime})_{\ell\in[k]},(j_{\ell}^{\prime})_{\ell\in[k]}$ must
overlap in at least $r$ edges that form a $\widetilde{G}^{2}$. In the case
$r=2k$, note that we must have $b_{\ell}=0$ for all $\ell\in[2k]$ and then the
fact that we subtract $X,Y$ means that the term is in fact precisely $0$. Thus
we may assume $r<2k$. Therefore we may suppose these $r\geq 0$ edges form
$s\geq 0$ connected components which are all paths. The number of choices for
$i,j,i^{\prime},j^{\prime}$ is then easily seen to be
$(O(k))^{O(s)}\cdot(O(n))^{4k-r-s}$. When $s=0$, we have $r=0$, and we can
save an extra factor of $n$ compared to the bound $(O(n))^{4k}$ for the
counting given above: if $(j_{\ell})_{\ell\in[k]}$ and
$(j_{\ell}^{\prime})_{\ell\in[k]}$ share no values, then the two parts of the
covariance are independence and we obtain a $0$ contribution, so we can ignore
the bulk of those terms. The number of ways to choose
$i,j,i^{\prime},j^{\prime}$ to have such an overlap is at most
$k^{2}m^{2k-1}n^{2k}=(O(n))^{4k-1}$.

Therefore, we deduce

$\displaystyle\operatorname{Var}[\widetilde{C}_{k}$
$\displaystyle(m,t,G,\sigma(t,G^{(2)}(t)))-C_{k}(m,G)]$
$\displaystyle\leq\sum_{r,s}\frac{2^{2k}}{(mn)^{k}}\cdot
2^{2k}\cdot(O(1/n))^{2k-r}\cdot\min\\{(O(k))^{O(s)}(O(n))^{4k-r-s},(O(n))^{4k-1}\\}$
$\displaystyle\leq(O(1))^{k}\cdot\min\\{(k^{O(1)}/n)^{s},1/n\\}\leq
n^{-5/6}\operatorname{Var}[C_{k}(m,G)].$

We used $k=\eta\log n$ where recall $\eta>0$ will be chosen sufficiently
small. This completes the justification of 3.4 for $k>1$; $k=1$ is easily
checked by hand.

For 3.1 and 3.3 the argument is similar, but the expectation computation is
complicated by the fact that $\mathbb{E}\rho_{1}^{(1)}\rho_{2}^{(1)}\neq 0$.
In fact, instead of conditioning on the values
$M_{1}+\cdots+M_{(n+t)/2},M_{(n+t)/2+1}+\cdots+M_{n}$ that appear, it is
easier to only condition on the total sum $M_{1}+\cdots+M_{n}$ (since we are
only conditioning on information related to it for this computation), and to
modify Definition 3.2 appropriately. Additionally, since the value $t$ plays
no role if we compute the expectation this way, we actually have the better
error term listed in 3.1. However, we do omit these details here (note that
[2, Lemma 3.2] implies that our claimed mean shift is in fact what comes out
of doing the necessary computations). ∎

Finally, in order to prove the Gaussian convergence of $C_{k}$ when the matrix
is sampled from $\Delta_{0}$, we rely on an argument based on exchangeable
pairs and Stein’s method. Let us first define the notion of a pair of
exchangeable random variables.

######  Definition 3.4.

$X^{\prime}$ and $X$ are exchangeable random variables if $(X^{\prime},X)$ and
$(X,X^{\prime})$ have the same distribution.

The key probability theoretic statement we will use is a multivariate version
of the method of exchangeable random variables for proving convergence to a
Gaussian. This form is due to Meckes [14].

######  Theorem 3.5 (Specialization of [14, Theorem 3]).

Let $(X,X^{\prime})$ be an exchangeable pair of random vectors in
$\mathbb{R}^{d}$. Suppose that there is an invertible matrix $\Lambda$ and a
random matrix $E^{\prime}$ such that

  * •

$\mathbb{E}\mathopen{}\mathclose{{}\left[X^{\prime}-X\big{|}X}\right]=-\Lambda
X$

  * •

$\mathbb{E}\mathopen{}\mathclose{{}\left[(X^{\prime}-X)(X^{\prime}-X)^{T}\big{|}X}\right]=2\Lambda+\mathbb{E}\mathopen{}\mathclose{{}\left[E^{\prime}\big{|}X}\right].$

Then for $g\in\mathcal{C}^{3}(\mathbb{R}^{d})$,

$\big{|}\mathbb{E}g(X)-\mathbb{E}g(Z)\big{|}\leq\|\Lambda^{-1}\|_{\mathrm{op}}\mathopen{}\mathclose{{}\left[\frac{\sqrt{d}}{4}M_{2}(g)\mathbb{E}\|E^{\prime}\|_{\mathrm{HS}}+\frac{1}{9}M_{3}(g)\mathbb{E}\lVert
X^{\prime}-X\rVert_{2}^{3}}\right]$ (3.8)

where $Z$ is a standard Gaussian random vector in $\mathbb{R}^{d}$.

We will need the following bound on moments of standard Gaussian random
variables (which is a special case of a phenomenon called
_hypercontractivity_).

######  Theorem 3.6 ([16, Theorem 9.21]).

Let $f$ be a polynomial in $n$ variables of degree at most $d$. Let
$\vec{x}=(x_{1},\ldots,x_{n})$ either be a vector of independent Rademacher
random variables or a vector of independent standard Gaussian random
variables. Then for any real number $q\geq 2$, we have

$\mathbb{E}\big{[}|f(\vec{x})|^{q}\big{]}^{1/q}\leq\big{(}\sqrt{q-1}\big{)}^{d}\mathbb{E}\big{[}f(\vec{x})^{2}\big{]}^{1/2}.$

######  Proposition 3.7.

Let $m=\tau_{\mathrm{pre}}=\lfloor\alpha_{c}n-\eta\log n\rfloor$ and
$K=\lceil\eta\log n\rceil$. We define $V(M)$ as in Lemma 2.8 and consider $n$
sufficiently large. For $g\in\mathcal{C}^{3}(\mathbb{R}^{K})$, we have

$\big{|}\mathbb{E}g(V(G^{(0)}))-\mathbb{E}_{Z\sim\mathcal{N}(0,I_{K})}g(Z)\big{|}\leq(M_{2}(g)+M_{3}(g))n^{-1/4}.$

###### Proof.

We now define the setup for our exchangeable pairs. Let

$G=G^{(0)}=(g_{j,i})_{(j,i)\in[m]\times[n]}$

and

$G^{\prime}=(g_{i,j})_{(j,i)\in([m]\times[n])\setminus I}\cup(g_{I})$

where $I$ is an index sampled from $[m]\times[n]$ uniformly at random and the
$g_{I}$ is an independent standard Gaussian. The exchangeable pair of random
variables we will consider is:

$V=\bigg{(}\frac{C_{1}(m,G)}{\sqrt{2\cdot
1}},\ldots,\frac{C_{K}(m,G)}{\sqrt{2K}}\bigg{)},\qquad
V^{\prime}=\bigg{(}\frac{C_{1}(m,G^{\prime})}{\sqrt{2\cdot
1}},\ldots,\frac{C_{K}(m,G^{\prime})}{\sqrt{2K}}\bigg{)}.$

Since $I$ is a uniformly random element from $[m]\times[n]$ notice that

$\mathbb{E}[V^{\prime}-V|V]=-\text{diag}\bigg{(}\frac{2k-\mathbbm{1}_{k=1}}{mn}\bigg{)}_{k\in[K]}V$

so define

$\Lambda=\text{diag}\bigg{(}\frac{2k-\mathbbm{1}_{k=1}}{mn}\bigg{)}_{k\in[K]}.$

In order to apply Theorem 3.5, we take

$E^{\prime}=\mathbb{E}[(V^{\prime}-V)(V^{\prime}-V)^{T}-2\Lambda|G]$

and note that this satisfies the required condition for $E^{\prime}$ as $V$ is
a measurable function of $G$.

We bound each of the terms appearing in 3.8. First,
$\lVert\Lambda^{-1}\rVert_{\mathrm{op}}=mn$. Second, note that

$\displaystyle\mathbb{E}\lVert X^{\prime}-X\rVert_{2}^{3}$
$\displaystyle\leq\mathbb{E}\bigg{[}\bigg{(}\sum_{k=1}^{K}(C_{k}(m,G)-C_{k}(m,G^{\prime}))^{2}\bigg{)}^{3/2}\bigg{]}$
$\displaystyle\leq
K^{1/2}\cdot\mathbb{E}\bigg{[}\sum_{k=1}^{K}|C_{k}(m,G)-C_{k}(m,G^{\prime})|^{3}\bigg{]}$
$\displaystyle\leq
n^{1/5}\cdot\sum_{k=1}^{K}\bigg{(}\mathbb{E}\bigg{[}\bigg{|}C_{k}(m,G)-C_{k}(m,G^{\prime})\bigg{|}^{2}\bigg{]}\bigg{)}^{3/2}$
$\displaystyle=n^{1/5}\cdot\sum_{k=1}^{K}(2k/(mn)\mathbb{E}[C_{k}(m,G)^{2}])^{3/2}$
$\displaystyle\leq n^{-11/4}$

where we have applied Holder’s inequality, Theorem 3.6, and computed the
variance using orthogonality of various monomials in order to prove the
desired result (note that all but at most $2k/(mn)$ fraction of the monomials
are canceled in $C_{k}(m,G)-C_{k}(m,G^{\prime})$).

Finally, we compute

$\displaystyle\mathbb{E}\lVert E^{\prime}\rVert_{\mathrm{HS}}$
$\displaystyle\leq(\mathbb{E}\lVert E^{\prime}\rVert_{\mathrm{HS}}^{2})^{1/2}$
$\displaystyle\leq\bigg{(}2\sum_{1\leq k_{1}<k_{2}\leq
K}\mathbb{E}\big{[}\mathbb{E}[(C_{k_{1}}(m,G)-C_{k_{1}}(m,G^{\prime}))(C_{k_{2}}(m,G)-C_{k_{2}}(m,G^{\prime}))|G]^{2}\big{]}$
$\displaystyle\qquad+\sum_{1\leq k\leq
K}\operatorname{Var}\big{[}\mathbb{E}[(C_{k}(m,G)-C_{k}(m,G^{\prime}))^{2}|G]\big{]}\bigg{)}^{1/2}$

where we have used that
$2k(E^{\prime})_{k,k}=\mathbb{E}[(C_{k}(m,G)-C_{k}(m,G^{\prime}))^{2}|G]-\mathbb{E}[(C_{k}(m,G)-C_{k}(m,G^{\prime}))^{2}]$.
We now handle the off-diagonal and on-diagonal contribution separately. For
ease of notation, given an index $I\in[m]\times[n]$ we define

$\displaystyle C_{k}(m,M,I)$
$\displaystyle=\bigg{(}\frac{1}{\sqrt{n}}\bigg{)}^{k}\bigg{(}\frac{1}{\sqrt{m}}\bigg{)}^{k}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in[n]\text{
distinct}\\\ j_{1},\ldots,j_{k}\in[m]\text{ distinct}\\\
I\in\bigcup_{k=1}^{\ell}\\{(j_{\ell},i_{\ell}),(j_{\ell},i_{\ell+1})\\}\end{subarray}}\prod_{i=1}^{k}M_{j_{\ell},i_{\ell}}M_{j_{\ell},i_{\ell+1}},$
$\displaystyle C_{k}^{\ast}(m,M,I)$
$\displaystyle=\bigg{(}\frac{1}{\sqrt{n}}\bigg{)}^{k}\bigg{(}\frac{1}{\sqrt{m}}\bigg{)}^{k}\sum_{\begin{subarray}{c}i_{1},\ldots,i_{k}\in[n]\text{
distinct}\\\ j_{1},\ldots,j_{k}\in[m]\text{ distinct}\\\
I\in\bigcup_{k=1}^{\ell}\\{(j_{\ell},i_{\ell}),(j_{\ell},i_{\ell+1})\\}\end{subarray}}\prod_{(j,i)\in\bigcup_{k=1}^{\ell}\\{(j_{\ell},i_{\ell}),(j_{\ell},i_{\ell+1})\\}\setminus
I}M_{j,i}.$

We consider the off-diagonal contribution first. We have

$\displaystyle\mathbb{E}\big{[}\mathbb{E}[(C_{k_{1}}(m,G)-C_{k_{1}}(m,G^{\prime}))(C_{k_{2}}(m,G)-C_{k_{2}}(m,G^{\prime}))|G]^{2}\big{]}$
$\displaystyle=\frac{1}{m^{2}n^{2}}\mathbb{E}\bigg{[}\bigg{(}\sum_{I\in[m]\times[n]}C_{k_{1}}(m,G,I)C_{k_{2}}(m,G,I)+C_{k_{1}}^{\ast}(m,G,I)C_{k_{2}}^{\ast}(m,G,I)\bigg{)}^{2}\bigg{]}$
$\displaystyle\leq\frac{2}{m^{2}n^{2}}\mathbb{E}\bigg{[}\bigg{(}\sum_{I\in[m]\times[n]}C_{k_{1}}(m,G,I)C_{k_{2}}(m,G,I)\bigg{)}^{2}+\bigg{(}\sum_{I\in[m]\times[n]}C_{k_{1}}^{\ast}(m,G,I)C_{k_{2}}^{\ast}(m,G,I)\bigg{)}^{2}\bigg{]}.$

Note that as $k_{1}\neq k_{2}$, we have that
$C_{k_{1}}(m,G,I)C_{k_{2}}(m,G,I)$ and
$C_{k_{1}}^{\ast}(m,G,I)C_{k_{2}}^{\ast}(m,G,I)$ are mean zero random
variables. We will bound

$\mathbb{E}\bigg{[}\bigg{(}\sum_{I\in[m]\times[n]}C_{k_{1}}(m,G,I)C_{k_{2}}(m,G,I)\bigg{)}^{2}\bigg{]}.$

Expanding, each term is of the form
$C_{k_{1}}(m,G,I_{1})C_{k_{2}}(m,G,I_{1})C_{k_{1}}(m,G,I_{2})C_{k_{2}}(m,G,I_{2})$.
A term contributes precisely if the monomial in $G$ has all even powers.
Furthermore, any $G_{j,i}$ appears at most $4$ times, which means any
contribution is of size at most $3^{4K}=(O(1))^{K}$. Therefore, we are
primarily interested in counting the number of nonzero terms that arise. We
have a multigraph $H$ coming from layering two cycles of length $k_{1}$ and
two cycles of length $k_{2}$, with possible overlaps (including two guaranteed
overlaps at edges $I_{1},I_{2}$). Let there be $v$ vertices, and let
$H^{\prime}$ be the multigraph formed by halving the multiplicities of $H$.
Note that each vertex has at least two outgoing edges to different vertices in
$H^{\prime}$, and the total multiplicity of edges is $2k_{1}+2k_{2}$. We
deduce that there are at most $2k_{1}+2k_{2}$ vertices, with equality
precisely when $H^{\prime}$ is a disjoint union of cycles. However,
$H^{\prime}$ must be connected and can be seen to not be a single cycle since
$k_{1}\neq k_{2}$. Thus in fact $v\leq 2k_{1}+2k_{2}-1$.

If $v\leq 2k_{1}+2k_{2}-8\log\log n$ then there are at most
$(8k)^{8k}n^{v}\leq n^{2k_{1}+2k_{2}-4}$ choices of term, using $k\leq\eta\log
n$. Otherwise let $r=2k_{1}+2k_{2}-v$ and note $1\leq r\leq 8\log\log n$. We
see that $H^{\prime}$ has at most $O(r)$ many vertices of degree at least $3$,
where we include multiplicity (since there are $2k_{1}+2k_{2}$ edges with
multiplicity, $2k_{1}+2k_{2}-r$ vertices, and each vertex has at least two
distinct neighbors). Notice that between such vertices, $H^{\prime}$ must have
paths and there are at most $K^{r^{2}}$ ways to choose the sizes of all these
paths. After doing so, there are $4^{O(K)}$ ways to assign these edges to
various cycles. Finally, there are at most $e^{O(K)}$ ways to order these into
cycles: outside of the $r$ higher degree vertices, we have bounded degree so a
bounded number of choices for the next edge at every stage, and among $r\leq
8\log\log n=O(\log K)$ vertices we have at most $O(K)$ choices, for $K^{O(\log
K)}$ choices. Since $K^{r^{2}}=K^{O((\log K)^{2})}$ we easily find a total of
at most $(O(1))^{K}n^{2k_{1}+2k_{2}-1}$ total terms.

Plugging in, we find the contribution to $(\mathbb{E}\lVert
E^{\prime}\rVert_{\mathrm{HS}})^{2}$ from these off-diagonal terms is at most

$\frac{1}{m^{2}n^{2}}\cdot(O(1))^{K}n^{2k_{1}+2k_{2}-1}\cdot\bigg{(}\frac{1}{(mn)^{k_{1}}}\bigg{)}\bigg{(}\frac{1}{(mn)^{k_{2}}}\bigg{)}.$

The total contribution is at most $n^{-5+1/6}$. The situation for $C^{\ast}$
is even simpler, and we can obtain a bound of $n^{-5+1/6}$ analogously.
Additionally, this analysis is easily seen to hold when $k_{1}=1$.

For the on-diagonal contribution, the analysis is quite similar. For $k=1$,
straightforward computation gives a contribution to $(\mathbb{E}\lVert
E^{\prime}\rVert_{\mathrm{HS}})^{2}$ of at most $O(n^{-6})$.

For $k\geq 2$, note that we have

$\displaystyle\operatorname{Var}\big{[}\mathbb{E}[(C_{k}(m,G)-C_{k}(m,G^{\prime}))^{2}|G]\big{]}$
$\displaystyle=\frac{1}{m^{2}n^{2}}\operatorname{Var}\bigg{[}\sum_{I\in[m]\times[n]}(C_{k}(m,G,I)^{2}+C_{k}^{\ast}(m,G,I)^{2})\bigg{]}$
$\displaystyle\leq\frac{2}{m^{2}n^{2}}\bigg{(}\operatorname{Var}\bigg{[}\sum_{I\in[m]\times[n]}C_{k}(m,G,I)^{2}\bigg{]}+\operatorname{Var}\bigg{[}\sum_{I\in[m]\times[n]}C_{k}^{\ast}(m,G,I)^{2}\bigg{]}\bigg{)}.$

As before we consider the $C$ term, since the $C^{\ast}$ term can be analyzed
analogously. We have

$\operatorname{Var}\bigg{[}\bigg{(}\sum_{I\in[m]\times[n]}C_{k}(m,G,I)^{2}\bigg{)}\bigg{]}=\mathbb{E}\bigg{[}\bigg{(}\sum_{I\in[m]\times[n]}C_{k}(m,G,I)^{2}\bigg{)}^{2}\bigg{]}-\mathbb{E}\bigg{[}\sum_{I\in[m]\times[n]}C_{k}(m,G,I)^{2}\bigg{]}^{2}.$

Again view this as an expansion into $4$ overlapping cycles as in the off-
diagonal case. Here however as the two cycles in each pair coming from
$k_{1},k_{2}$ are isomorphic, one can overlap them perfectly, which was not
allowed in the prior analysis (which was used to argue that in fact $v\leq
2k_{1}+2k_{2}-1$, ruling out $v=2k_{1}+2k_{2}$). In this remaining case, we
can see the contribution is exactly cancelled however by the subtracted term.
The proof can thus proceed similarly to the off-diagonal case, and we obtain a
bound $n^{-5+1/6}$ in this case as well.

Now we deduce

$\lVert\Lambda^{-1}\rVert_{\mathrm{op}}\bigg{(}\frac{\sqrt{k}}{4}\mathbb{E}\lVert
E^{\prime}\rVert_{\mathrm{HS}}+\frac{1}{9}\mathbb{E}\lVert
X^{\prime}-X\rVert_{2}^{3}\bigg{)}\leq mn(\sqrt{\log
n}(4n^{-5+1/6})^{1/2}+n^{-11/4})\leq n^{-1/3},$

and therefore Theorem 3.5 finishes. ∎

We are finally in position to deduce Lemma 2.8.

###### Proof of Lemma 2.8.

The result is ultimately a straightforward combination of Lemma 3.3 and
Proposition 3.7. We prove the statement for $G^{(2)}(t)$; the proof in the
other two cases are identical. Note that

$\displaystyle\mathbb{E}\lVert V(G^{(2)}(t))-2\mu-V(G^{(0)})\rVert_{2}$
$\displaystyle\leq(\mathbb{E}\lVert
V(G^{(2)}(t))-2\mu-V(G^{(0)})\rVert_{2}^{2})^{1/2}$
$\displaystyle\leq\bigg{(}\lVert\mathbb{E}[V(G^{(2)}(t))-2\mu-V(G^{(0)})]\rVert_{2}^{2}+\sum_{1\leq
k\leq
K}\operatorname{Var}[\widetilde{C}_{k}(m,t,G,\sigma(t,G^{(2)}(t)))-C_{k}(m,G)]\bigg{)}$
$\displaystyle\leq n^{-1/5}$

where we have applied Lemma 3.3. This immediately implies that

$\displaystyle|\mathbb{E}[g(V(G^{(2)}(t))-2\mu)-g(V(G^{(0)})]|$
$\displaystyle\leq M_{1}(g)\cdot\mathbb{E}[\lVert
V(G^{(2)}(t))-2\mu-V(G^{(0)})\rVert_{2}]$ $\displaystyle\leq M_{1}(g)\cdot
n^{-1/5}.$

The desired result then follows from triangle inequality and Proposition 3.7.
∎

###  3.3. Miscellaneous estimates

Finally, we will additionally require the following basic estimate on the
binomial coefficient.

######  Claim 3.8.

For $1\leq k\leq n-1$ we have that

$\binom{n}{k}\leq\sqrt{n/(k(n-k))}\exp\bigg{(}-k\log\bigg{(}\frac{k}{n}\bigg{)}-(n-k)\log\bigg{(}\frac{n-k}{n}\bigg{)}\bigg{)}.$

Furthermore for $|k|\leq\sqrt{n}\log n$ and $n$ sufficiently large such that
$(n+k)/2\in\mathbb{Z}$, we have that

$\binom{n}{(n+k)/2}=\frac{2^{n}\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{k^{2}}{2n}\pm n^{-1/2}\bigg{)}.$

##  4\. Moment computations

In this section we prove Lemma 2.7 using the tools we have developed so far.
We separate the first and second moment computations.

###  4.1. First moment

We first prove the first moment.

###### Proof of 2.1.

We choose a function $h\colon\mathbb{R}\to[0,1]$ which is $1$ on
$[-L,\infty]$, $0$ on $[-\infty,-L-1]$ and in
$\mathcal{C}^{\infty}(\mathbb{R})$. Notice that linearity of expectation
yields $\mathbb{E}[X(G)]=2^{n}p^{m}$ and

$\displaystyle\mathbb{E}[X(G)\exp(-Y_{K}(m,G)$
$\displaystyle\mathbbm{1}[Y_{K}(m,G)\geq-L])]\geq\mathbb{E}[X(G)\exp(-Y_{K}(m,G)h(Y_{K}(m,G))]$
$\displaystyle=2^{n}\mathbb{E}[\mathbbm{1}_{v_{n}\in
S_{\tau_{\mathrm{pre}}}(G)}\exp(-Y_{K}(m,G)h(Y_{K}(m,G))]$
$\displaystyle=2^{n}p^{m}\mathbb{E}[\exp(-Y_{K}(m,G^{(1)})h(Y_{K}(m,G^{(1)}))].$

(Recall $v_{n}\in\mathbb{R}^{n}$ is all $1$s.) Note

$Y_{K}(m,M)=\sum_{k=1}^{K}\frac{2(2\beta)^{k}C_{k}(m,M)-(2\beta)^{2k}}{4k}=\sum_{k=1}^{K}\frac{(2\beta)^{k}}{\sqrt{2k}}\cdot\frac{C_{k}(m,M)}{\sqrt{2k}}-\sum_{k=1}^{K}\frac{(2\beta)^{2k}}{4k}.$

Viewing $\exp(-Y_{K}(m,G^{(1)})h(Y_{K}(m,G^{(1)}))$ as a function of
$C_{k}(m,G^{(1)})$ for $k\in[K]$, by the product rule we see that the function
has first, second, and third derivatives of size $O(n^{2\eta})$. Let
$Z\sim\mathcal{N}(\mu^{\ast},\sigma^{2})$ with

$\mu^{\ast}=\sum_{k=1}^{K}\frac{(2\beta)^{k}}{\sqrt{2k}}\cdot\frac{(2\beta)^{k}}{\sqrt{2k}}-\sum_{k=1}^{K}\frac{(2\beta)^{2k}}{4k}=\sum_{k=1}^{K}\frac{(2\beta)^{2k}}{4k},\qquad\sigma^{2}=\sum_{k=1}^{K}\frac{(2\beta)^{2k}}{2k}.$

Applying 2.5 of Lemma 2.8, we find that

$\displaystyle\mathbb{E}[X(G)\exp(-Y_{K}(m,G)\mathbbm{1}[Y_{K}(m,G)\geq-L])]$
$\displaystyle\geq 2^{n}p^{m}(\mathbb{E}[\exp(-Zh(Z))]-n^{2\eta-1/6})$
$\displaystyle\geq 2^{n}p^{m}(1-n^{-1/8})$

where we have used that $\eta$ is a sufficiently small constant in the final
bound, and that

$\mathbb{E}\exp(-Zh(Z))=(1\pm n^{-2})\mathbb{E}\exp(-Z)=(1\pm
n^{-2})\exp\bigg{(}-\mu^{\ast}+\frac{\sigma^{2}}{2}\bigg{)}=1\pm
n^{-1/2}.\qed$

###  4.2. Second moment

The second moment computation in Lemma 2.7 closely follows the computation
given in the work of Abbe, Li, and Sly [2]; we thus provide a proof tracking
quantitative aspects but omitting various routine calculations. We first prove
2.3 which handles the majority of the range of overlaps; here our approach is
essentially identical to that of Altschuler [3].

###### Proof of 2.3.

By Claim 3.8, symmetry, and independence of the vectors of $G$ note that

$\displaystyle\sum_{t\in[-(n-1),-n^{1/2}\log n]\cup[n^{1/2}\log
n,n-1]}2^{n}\binom{n}{(n+t)/2}\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\mathrm{pre}}}(G)]$ $\displaystyle\leq 2n\sum_{t\in[n^{1/2}\log
n,n-1]}2^{n}\exp(nH(1/2+t/(2n)))\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\mathrm{pre}}}(G)]$ $\displaystyle=2n\sum_{1\leq t\leq
n/2-\sqrt{n}\log n}2^{n}\exp(nH(t/n))(q(t/n))^{m}$ $\displaystyle\leq
n^{2}\sum_{1\leq t\leq n/2-\sqrt{n}\log
n}2^{n}\exp(nH(t/n))(q(t/n))^{\alpha_{c}n}$

where we have used that by the Gaussian correlation inequality that $q(t)\geq
q(1/2)=\mathbb{P}[|Z|\leq\kappa]^{2}>0$ and that $\eta$ is a sufficiently
small constant. We first handle $1\leq t\leq\epsilon n/2$. Notice that

$\displaystyle\sum_{1\leq t\leq\epsilon
n/2}2^{n}\exp(nH(t/n))(q(t/n))^{\alpha_{c}n}$ $\displaystyle\leq
n\cdot\max_{1/n\leq
t\leq\epsilon/2}2^{n}\exp(nH(t/n))\cdot(q(t/n))^{\alpha_{c}n}$
$\displaystyle\leq n\cdot 2^{n}\exp(nH(1/n))\cdot(q(1/n))^{\alpha_{c}n}$
$\displaystyle\leq n\cdot\exp(-\Omega(\sqrt{n})).$

We have implicitly used Items 3 and 5 from Lemma 3.1 as well as the fact that
$q(0)^{\alpha_{c}n}=p^{\alpha_{c}n}=2^{-n}$.

Next, notice that the function $F(\gamma)$ is easily seen to have bounded
derivatives away from the endpoints of the interval $[0,1]$ and therefore as
$F^{\prime}(1/2)=0$ (by symmetry) and $F^{\prime\prime}(1/2)\leq-\varepsilon$
(Item 2), we have that there exists $\delta>0$ such that

$F(1/2+\tau)\leq F(1/2)-\delta\tau^{2}$

for $|\tau|\leq\delta$. This implies that

$\displaystyle\sum_{(1/2-\delta)n\leq t\leq n/2-\sqrt{n}\log
n}2^{n}\exp(nH(t/n))(q(t/n))^{\alpha_{c}n}$ $\displaystyle\leq n\cdot
2^{n}(F(1/2)-\delta(\log n)^{2}/n)^{n}\leq\exp(-(\log n)^{5/3})$

given that $n$ is sufficiently large. Finally for the intermediate range, note
that

$\displaystyle\sum_{\epsilon n/2\leq
t\leq(1/2-\delta)n}2^{n}\exp(-nH(t/n))(q(t/n))^{\alpha_{c}n}$
$\displaystyle\leq n\cdot 2^{n}\cdot\max_{\epsilon/2\leq\beta\leq
1/2-\delta}F(\beta)^{n}$ $\displaystyle\leq\exp(-\Omega(n))$

where we have used Item 4 with $a=\varepsilon,b=1/2-\delta$ (the above
analysis demonstrates that $F(\varepsilon)<F(0)$ and $F(1/2-\delta)\leq
F(1/2)-\delta^{3}$). ∎

We now handle the second moment in full generality.

###### Proof of 2.2.

Notice that linearity of expectation and conditioning gives

$\displaystyle\mathbb{E}[X(G)^{2}\exp(-2Y_{K}(m,G)\mathbbm{1}[Y_{K}(m,G)\geq-L])]$
$\displaystyle=\sum_{\begin{subarray}{c}-n\leq t\leq n\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}2^{n}\binom{n}{(n+t)/2}\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\operatorname{pre}}}(G)]\mathbb{E}[\exp(-2Y_{K}(m,G^{(2)}(t))\mathbbm{1}[Y_{K}(m,G^{(2)}(t))\geq-L])].$

We first handle the range when $n^{1/2}\log n\leq|t|\leq n-1$. By 2.3 we have
that

$\displaystyle\sum_{\begin{subarray}{c}n^{1/2}\log n\leq|t|\leq n-1\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}2^{n}\binom{n}{(n+t)/2}\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\operatorname{pre}}}(G)]\mathbb{E}[\exp(-2Y_{K}(m,G^{(2)}(t))\mathbbm{1}[Y_{K}(m,G^{(2)}(t))\geq-L])]$
$\displaystyle\leq\exp(2L)\cdot\sum_{\begin{subarray}{c}n^{1/2}\log
n\leq|t|\leq n-1\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}2^{n}\binom{n}{(n+t)/2}\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\operatorname{pre}}}(G)]$ $\displaystyle\leq n^{2\eta}\exp(-(\log
n)^{3/2})\leq\exp(-(\log n)^{4/3})$

which is decaying faster than any polynomial. We next handle the case where
$t=\pm n$; notice the contribution in this case is

$\displaystyle 2\cdot 2^{n}\mathbb{P}[v_{n}\in
S_{\tau_{\operatorname{pre}}}(G)]\mathbb{E}[\exp(-2Y_{K}(m,G^{(2)}(n))\mathbbm{1}[Y_{K}(m,G^{(2)}(n))\geq-L])]$
$\displaystyle=2\mathbb{E}[X(G)]\cdot\mathbb{E}[\exp(-2Y_{K}(m,G^{(1)})\mathbbm{1}[Y_{K}(m,G^{(1)})\geq-L])]$
$\displaystyle\lesssim\mathbb{E}[X(G)]\leq
n^{-\Omega(1)}\mathbb{E}[X(G)]^{2}.$

We used 2.5 of Lemma 2.8 with an appropriate test function $g$ (an exponential
of a linear function with smooth cutoff) to bound the quantity
$\mathbb{E}[\exp(-2Y_{K}(m,G^{(1)})\mathbbm{1}[Y_{K}(m,G^{(1)})\geq-L])]$ by a
constant, similar to in the proof of 2.1. The final inequality follows since
$\tau_{\mathrm{pre}}$ is such that $\mathbb{E}X(G)=n^{\Theta(\eta)}$ is of
polynomial size.

Finally we handle the case where $|t|\leq n^{1/2}\log n$. For the sake of
brevity, we define
$\widetilde{Y}(t)=\mathbb{E}[\exp(-2Y_{K}(m,G^{(2)}(t))\mathbbm{1}[Y_{K}(m,G^{(2)}(t))\geq-L])]$.
Now

$\displaystyle\sum_{\begin{subarray}{c}|t|\leq n^{1/2}\log n\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}2^{n}\binom{n}{(n+t)/2}\mathbb{P}[v_{n},v_{t}\in
S_{\tau_{\operatorname{pre}}}(G)]\widetilde{Y}(t)$
$\displaystyle=\sum_{\begin{subarray}{c}|t|\leq n^{1/2}\log n\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}\frac{4^{n}\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}\pm
n^{-1/2}\bigg{)}q\bigg{(}\frac{n+t}{2n}\bigg{)}^{m}\widetilde{Y}(t)$
$\displaystyle=q(1/2)^{m-\alpha_{c}n}\sum_{\begin{subarray}{c}|t|\leq
n^{1/2}\log n\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}\frac{4^{n}\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}\pm
n^{-1/4}\bigg{)}q\bigg{(}\frac{n+t}{2n}\bigg{)}^{\alpha_{c}n}\widetilde{Y}(t)$
$\displaystyle=q(1/2)^{m-\alpha_{c}n}\sum_{\begin{subarray}{c}|t|\leq
n^{1/2}\log n\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}\frac{4^{n}\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}\pm
n^{-1/4}\bigg{)}\bigg{(}q\bigg{(}\frac{1}{2}\bigg{)}+\frac{t^{2}q^{\prime\prime}(1/2)}{8n^{2}}\pm
n^{-5/4}\bigg{)}^{\alpha_{c}n}\widetilde{Y}(t)$
$\displaystyle=q(1/2)^{m-\alpha_{c}n}\sum_{\begin{subarray}{c}|t|\leq
n^{1/2}\log n\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}\frac{4^{n}\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}\pm
n^{-1/6}\bigg{)}\bigg{(}q\bigg{(}\frac{1}{2}\bigg{)}+\frac{t^{2}q^{\prime\prime}(1/2)}{8n^{2}}\bigg{)}^{\alpha_{c}n}\widetilde{Y}(0).$

We used Claim 3.8 in the first line, used that $q(\cdot)$ has bounded first,
second, third derivatives in the neighborhood of $1/2$ in the second and third
lines, and that $\widetilde{Y}(t)=(1\pm n^{-2/11})\widetilde{Y}(0)$ (which is
an immediate consequence of Lemma 2.8 and an argument identical to that in the
proof of 2.1) in the final line.

Continuing,

$\displaystyle q(1/2)^{m-\alpha_{c}n}$
$\displaystyle\sum_{\begin{subarray}{c}|t|\leq n^{1/2}\log n\\\
(n+t)/2\in\mathbb{Z}\end{subarray}}\frac{4^{n}\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}\pm
n^{-1/6}\bigg{)}\bigg{(}q\bigg{(}\frac{1}{2}\bigg{)}+\frac{t^{2}q^{\prime\prime}(1/2)}{8n^{2}}\bigg{)}^{\alpha_{c}n}\widetilde{Y}(0)$
$\displaystyle=4^{n}p^{2m}\widetilde{Y}(0)\sum_{\begin{subarray}{c}|t|\leq
n^{1/2}\log n\\\ (n+t)/2\in\mathbb{Z}\end{subarray}}\frac{\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}\pm
n^{-1/6}\bigg{)}\bigg{(}1+\frac{t^{2}q^{\prime\prime}(1/2)}{8n^{2}p^{2}}\bigg{)}^{\alpha_{c}n}$
$\displaystyle=4^{n}p^{2m}\widetilde{Y}(0)\sum_{\begin{subarray}{c}|t|\leq
n^{1/2}\log n\\\ (n+t)/2\in\mathbb{Z}\end{subarray}}\frac{\sqrt{2}}{\sqrt{\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}+\frac{t^{2}q^{\prime\prime}(1/2)\alpha_{c}}{8np^{2}}\pm
n^{-2/13}\bigg{)}$
$\displaystyle\leq(1+n^{-1/7})\mathbb{E}[X(G)]^{2}\widetilde{Y}(0)\sum_{\begin{subarray}{c}t\in\mathbb{Z}\end{subarray}}\frac{1}{\sqrt{2\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}+\frac{t^{2}q^{\prime\prime}(1/2)\alpha_{c}}{8np^{2}}\bigg{)}$
$\displaystyle=(1+n^{-1/7})\mathbb{E}[X(G)]^{2}\widetilde{Y}(0)\sum_{\begin{subarray}{c}t\in\mathbb{Z}\end{subarray}}\frac{1}{\sqrt{2\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}+\frac{t^{2}\kappa^{2}e^{-\kappa^{2}}\alpha_{c}}{\pi
np^{2}}\bigg{)}$
$\displaystyle=(1+n^{-1/7})\mathbb{E}[X(G)]^{2}\widetilde{Y}(0)\sum_{\begin{subarray}{c}t\in\mathbb{Z}\end{subarray}}\frac{1}{\sqrt{2\pi
n}}\exp\bigg{(}-\frac{t^{2}}{2n}+\frac{t^{2}\alpha_{c}(1-\mu_{2})^{2}}{2n}\bigg{)}$
$\displaystyle=(1+n^{-1/7})\mathbb{E}[X(G)]^{2}\widetilde{Y}(0)\sum_{\begin{subarray}{c}t\in\mathbb{Z}\end{subarray}}\frac{1}{\sqrt{2\pi
n}}\exp\bigg{(}-\frac{t^{2}(1-4\beta^{2})}{2n}\bigg{)}$ $\displaystyle=(1\pm
n^{-1/8})\mathbb{E}[X(G)]^{2}\widetilde{Y}(0)\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\exp\bigg{(}-\frac{x^{2}(1-4\beta^{2})}{2}\bigg{)}~{}dx$
$\displaystyle=(1\pm
n^{-1/8})\mathbb{E}[X(G)]^{2}\widetilde{Y}(0)\frac{1}{\sqrt{1-4\beta^{2}}}$

where we have used that $q(1/2)=p^{2}$, the values of
$q^{\prime\prime}(1/2),(1-\mu_{2})p$ and identities relating this value to
$\beta$ via Items 1 and 6 of Lemma 3.1, and finally using the Euler–Maclaurin
formula to transfer from the final sum to an integral.

The final remaining task is therefore to bound

$\widetilde{Y}(0)=\mathbb{E}[\exp(-2Y_{K}(m,G^{(2)}(0))\mathbbm{1}[Y_{K}(m,G^{(2)}(0))\geq-L])].$

Note that $Y_{K}(m,G^{(2)}(0))$ is approximately normally distributed as
$Z\sim\mathcal{N}(\mu^{\ast},\sigma^{2})$ with

$\mu^{\ast}=\sum_{k=1}^{K}\frac{(2\beta)^{k}}{\sqrt{2k}}\cdot\frac{2(2\beta)^{k}}{\sqrt{2k}}-\sum_{k=1}^{K}\frac{(2\beta)^{2k}}{4k}=\sum_{k=1}^{K}\frac{3(2\beta)^{2k}}{4k},\qquad\sigma^{2}=\sum_{k=1}^{K}\frac{(2\beta)^{2k}}{2k}.$

Via an argument essentially identical to that in the proof of 2.1, we have
that

$\displaystyle\widetilde{Y}(0)$ $\displaystyle=(1\pm
n^{-1/4})\mathbb{E}[\exp(-2Z)]$ $\displaystyle=(1\pm
n^{-1/4})\exp(-2\mu^{\ast}+2\sigma^{2})$ $\displaystyle=(1\pm
n^{-1/4})\exp\bigg{(}-\sum_{k=1}^{K}\frac{(2\beta)^{2k}}{2k}\bigg{)}$
$\displaystyle=(1\pm n^{-\Omega(1)})\sqrt{1-4\beta^{2}}.$

Finally, putting everything together we have

$\mathbb{E}[X(G)^{2}\exp(-2Y_{K}(m,G)\mathbbm{1}[Y_{K}(m,G)\geq-L])]\leq
n^{-\Omega(1)}\mathbb{E}X(G)^{2}+e^{-(\log n)^{4/3}}+(1\pm
n^{-\Omega(1)})\mathbb{E}X(G)^{2},$

so the desired result follows immediately. ∎

## References

  * [1] Emmanuel Abbe, Shuangping Li, and Allan Sly, _Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster_ , STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2022] ©2022, pp. 860–873.
  * [2] Emmanuel Abbe, Shuangping Li, and Allan Sly, _Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron_ , 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022, pp. 327–338.
  * [3] Dylan J Altschuler, _Critical Window of The Symmetric Perceptron_ , arXiv:2205.02319.
  * [4] Benjamin Aubin, Will Perkins, and Lenka Zdeborová, _Storage capacity in symmetric binary perceptrons_ , J. Phys. A 52 (2019), 294003, 32.
  * [5] Ross Berkowitz, Ashwin Sah, and Mehtaab Sawhney, _Number of arithmetic progressions in dense random subsets of $\mathbb{Z}/n\mathbb{Z}$_, Israel J. Math. 244 (2021), 589–620.
  * [6] Clément L Canonne, _A short note on an inequality between KL and TV_ , arXiv:2202.07198.
  * [7] Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink, _Tight thresholds for cuckoo hashing via xorsat_ , International Colloquium on Automata, Languages, and Programming, Springer, 2010, pp. 213–225.
  * [8] Jian Ding and Nike Sun, _Capacity lower bound for the Ising perceptron_ , STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, pp. 816–827.
  * [9] Olivier Dubois and Jacques Mandler, _The 3-XORSAT threshold_ , C. R. Math. Acad. Sci. Paris 335 (2002), 963–966.
  * [10] John Duchi, _Derivations for linear algebra and optimization._ , http://web.stanford.edu/~jduchi/projects/general_notes.pdf.
  * [11] Ehud Friedgut, _Sharp thresholds of graph properties, and the $k$-sat problem_, J. Amer. Math. Soc. 12 (1999), 1017–1054, With an appendix by Jean Bourgain.
  * [12] David Gamarnik, Eren C Kızıldağ, Will Perkins, and Changji Xu, _Algorithms and barriers in the symmetric binary perceptron model_ , arXiv:2203.15667.
  * [13] Werner Krauth and Marc Mézard, _Storage capacity of memory networks with binary couplings_ , Journal de Physique 50 (1989), 3057–3066.
  * [14] Elizabeth Meckes, _On Stein’s method for multivariate normal approximation_ , High dimensional probability V: the Luminy volume, Inst. Math. Stat. (IMS) Collect., vol. 5, Inst. Math. Statist., Beachwood, OH, 2009, pp. 153–178.
  * [15] Shuta Nakajima and Nike Sun, _Sharp threshold sequence and universality for Ising perceptron models_ , arXiv:2204.03469.
  * [16] Ryan O’Donnell, _Analysis of Boolean functions_ , Cambridge University Press, New York, 2014.
  * [17] Will Perkins and Changji Xu, _Frozen 1-RSB structure of the symmetric Ising perceptron_ , STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2021] ©2021, pp. 1579–1588.
  * [18] Boris Pittel and Gregory B. Sorkin, _The satisfiability threshold for $k$-XORSAT_, Combin. Probab. Comput. 25 (2016), 236–268.
  * [19] Changji Xu, _Sharp threshold for the Ising perceptron model_ , Ann. Probab. 49 (2021), 2399–2415.