$\smash{D_\mu \td \psi_{b,N}(\nu_N,\cdot)=\td G_{b,\nu_N^*}+\BigO\big(N^{-1}\big)}$ for some measure $\nu_N^*\in \M_p$. Up to adding errors of $\BigO(N^{-1})$ throughout, the proof of Theorem 1.3 in [30] applies and reveals that each maximizer $\nu_N\in \M_+$ satisfies the approximate first order condition

$$D_\mu \td \psi_{b,N}(\nu_N,\cdot)=\td G_{b,\nu_N}+\BigO\big(N^{-1}\big).$$

This means that

$$\td G_{b,\nu_N^*}=D_\mu\td \psi_{b,N}(\nu_N,\cdot)+\BigO\big(N^{-1}\big)=\td G_{b,\nu_N}+\BigO\big(N^{-1}\big).$$

Together with the definition of $\smash{\td g_b}$ in (<ref>), this implies that

\begin{align*}
(b+c\log(c)-c)&\int_{-1}^1 \ud \nu_N(y)+\Delta\log(c)\int_{-1}^1 y\ud \nu_N(y)x+c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\int_{-1}^1 y^n\ud \nu_N(y)x^n\\
&=(b+c\log(c)-c)+\Delta \log(c)\m x+c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\int_{-1}^1 y^n\ud \nu_N^*(y)x^n+\BigO\big(N^{-1}\big).
\end{align*}

Since $b>1$ and $c\log(c)-c\geq -1$, we must have

$$\int_{-1}^1 \ud \nu_N(y)=1+\BigO\big(N^{-1}\big) \quad \text{and} \quad \int_{-1}^1 y^n\ud \nu_N(y)=\int_{-1}^1 y^n\ud \nu_N^*(y)+\BigO\big(N^{-1}\big)$$

for all $n\geq 2$.
We have used the fact that $\Delta\neq 0$ and accounted for the fact that $c$ could be equal to one. Applying the Prokhorov theorem and passing to a subsequence if necessary, it is therefore possible to ensure that the sequences $\smash{(\nu_N)}$ and $\smash{(\nu_N^*)}$ converge weakly to probability measures $\smash{\nu\in \Pr[-1,1]}$ and $\smash{\nu^*\in \M_p}$ with

$$\int_{-1}^1 y^n\ud \nu(y)=\int_{-1}^1 y^n\ud \nu^*(y)$$

for all $n\neq 1$. Since the set of polynomials with degree one coefficient equal to zero form of a sub-algebra of the space of continuous functions on the compact set $[-1,1]$, the Stone-Weierstrass theorem implies that $\smash{\nu=\nu^*\in \M_p}$. Recalling that we denote $\bar \nu_N$ for the probability measure induced by $\nu_N$, and arguing as in the proof of <Ref>, we have

\begin{align*}
\big\lvert \td \psi_{b,N}(\nu_N)-\td \psi_b(\nu^*)\big\rvert
\leq \big\lvert \td\psi_{b,N}(\nu_N)-\td \psi_{b,N}(\bar \nu_N)\big\rvert + \big\lvert \td\psi_{b,N}(\bar \nu_N)-\td \psi_{b,N}(\nu^*)\big\rvert+\big\lvert \td \psi_{b,N}(\nu^*)-\td \psi_b(\nu^*)\big\rvert\\
\leq C\TV(\nu_N,\bar \nu_N) +C W(\bar \nu_N, \nu^*)  + \big\lvert \td \psi_{b,N}(\nu^*)-\td \psi_b(\nu^*)\big\rvert,
\end{align*}

for some constant $C>0$ that depends only on $c$.
Recalling that the Wasserstein distance (<ref>) metrizes the weak convergence of probability measures on $[-1,1]$, observing that

$$\TV(\nu_N,\bar \nu_N) = \big|1- {\nu_N[-1,1]}  \big|, $$

and using <Ref> and (<ref>) to let $N$ tend to infinity in (<ref>) shows that

\begin{align*}
\sup_{\nu\in \Pr[-1,1]}\Par(1,0,\nu)&\leq \limsup_{N\to \infty}\widetilde{\Par}_{b,N}(1,0,\nu_N)-\frac{b}{2}=\td \psi_b(\nu^*)-\frac{1}{2}\int_{-1}^1 \td G_{b,\nu^*}(y)\ud \nu^*(y)-\frac{b}{2}\\
&\leq \sup_{\nu \in \M_p}\Par(1,0,\nu).
\end{align*}

Substituting this upper bound into (<ref>) yields

$$\limsup_{N\to \infty}\overline{F}_N\leq \sup_{\nu \in \M_p}\Par(1,0,\nu).$$

To express this upper bound in terms of the functional (<ref>), fix $\nu \in \M_p$ and denote by $x_1$ and $x_2$ two independent samples from the probability measure $\nu$. The definition of $g$ in (<ref>) implies that

$$\Par(1,0,\nu)=\psi(\nu)+\frac{c}{2}-\frac{1}{2}\big(c+\Delta \m^2\big)\log(c)-\frac{c}{2}\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\big(\E x_1^n\big)^2.$$

A Taylor expansion of the logarithm shows that

\begin{equation}\label{eqn: SBM Taylor for mixed expectation}
c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\big(\E x^n\big)^2=\E(c+\Delta x_1x_2)\log(c+\Delta x_1x_2)-\big(c+\Delta \m^2\big)\log(c)-\Delta \m^2
\end{equation}

from which it follows that

$$\Par(1,0,\nu)=\psi(\nu)+\frac{c}{2}-\frac{1}{2}\E(c+\Delta x_1x_2)\log(c+\Delta x_1x_2)+\frac{\Delta\m^2}{2}=\Par(\nu),$$

and therefore

$$\limsup_{N\to \infty}\overline{F}_N\leq \sup_{\nu\in \M_p}\Par(\nu).$$

This establishes the upper bound in (<ref>). To prove the corresponding lower bound, we follow [11] and proceed by interpolation. Given a measure $\nu \in \M_p$, introduce the interpolating free energy

\begin{equation}
\p(t)=\widetilde{F}_N(t, 1-t, \nu)
\end{equation}

for the free energy $\widetilde{F}_N$ defined in (<ref>). The derivative computations in <Ref> and <Ref> together with a computation identical to that in <Ref> imply that

\begin{align*}
\p'(t)&=\partial_t\widetilde{F}_N(t,1-t,\nu)- \partial_s\widetilde{F}_N(t,1-t,\nu)\\
&=\frac{c}{2}-\frac{1}{2}\big(c+\Delta \m^2\big)\log(c)+\frac{c}{2}\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\big\langle R_{[n]}^2\big\rangle- c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\langle R_{[n]}\rangle \E x_1^n.\\
&=\frac{c}{2}-\frac{1}{2}\big(c+\Delta \m^2\big)\log(c)- \frac{c}{2}\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\big(\E x_1^n\big)^2+\frac{c}{2}\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\big\langle (R_{[n]}- \E x_1^n)^2\big\rangle.
\end{align*}

It follows by (<ref>) that

$$\p'(t)=\frac{c}{2}+\frac{\Delta\m^2}{2}-\frac{1}{2}\E(c+\Delta x_1 x_2)\log(c+\Delta x_1x_2)+\frac{c}{2}\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\big\langle (R_{[n]}- \E x_1^n)^2\big\rangle.$$

Since the final term in this equality is non-negative, the fundamental theorem of calculus reveals that

$$\overline{F}_N\geq \psi_N(\nu)+\frac{c}{2}+\frac{\Delta\m^2}{2}-\frac{1}{2}\E(c+\Delta x_1 x_2)\log(c+\Delta x_1x_2),$$

where we have used that $\p(1)=\overline{F}_N$ and $\p(0)=\psi_N(\nu)$. Using <Ref> to let $N$ tend to infinity gives the lower bound

$$\liminf_{N\to \infty}\overline{F}_N\geq \psi(\nu)+\frac{c}{2}+\frac{\Delta\m^2}{2}-\frac{1}{2}\E(c+\Delta x_1 x_2)\log(c+\Delta x_1x_2)=\Par(\nu).$$

Taking the supremum over all measures $\nu\in \M_p$ completes the proof.

§ ASYMPTOTIC EQUIVALENCE OF FREE ENERGY FUNCTIONALS

In this appendix we show that the free energy functionals $\overline{F}_N^\circ$ and $\overline{F}_N$ defined in (<ref>) and (<ref>), respectively, are asymptotically equivalent. This will be a consequence of the binomial-Poisson approximation. To state this result concisely, given a separable metric space $S$, recall the definition of the total variation distance

\begin{equation}
\TV(\P,\Q)=\sup\big\{\abs{\P(A)-\Q(A)}\mid A \text{ is a measurable subset of } S\big\}
\end{equation}

between probability measures $\P,\Q\in \Pr(S)$. Approximating any measurable function with values in $S$ by a sequence of simple functions, one can check that the total variation distance admits the dual representation

\begin{equation}
\TV(\P,\Q)=\sup\bigg\{\Big\lvert \int_{-1}^1 f(x)\ud \P(x)-\int_{-1}^1 f(x)\ud \Q(x)\Big\rvert \mid f:S\to [0,1] \text{ measurable}\bigg\}.
\end{equation}

Using the Hahn-Jordan decomposition, it is also possible to show that

\begin{equation}\label{eqn: SBM dual total variation}
\TV(\P,\Q)=\inf\big\{\P\{X\neq Y\}\mid X\sim \P \text{ and } Y\sim \Q\big\}.
\end{equation}

We will use this result for discrete probability measures supported on the set of natural numbers in which case this representation follows from the Kantorovich-Rubinstein theorem (see Theorem 4.15 in [58]). The binomial-Poisson approximation is an upper bound on the total variation distance between the convolution of Bernoulli distributions and an appropriate Poisson distribution.

Consider independent Bernoulli random variables $X_i\sim \Ber(p_i)$ for $i\leq n$, and let $\smash{\lambda_n=\sum_{i\leq n}p_i}$. If $\smash{S_n=\sum_{i\leq n}X_i}$ and $\smash{\Pi_n\sim \Poi(\lambda_n)}$, then

\begin{equation}
\TV(S_n,\Pi_n)\leq \sum_{i\leq n}p_i^2.
\end{equation}

See Theorem 2.4 in [58].

The free energies (<ref>) and (<ref>) are asymptotically equivalent,

\begin{equation}
\lim_{N\to \infty}\big\lvert \overline{F}_N-\overline{F}_N^\circ\big\rvert=0.
\end{equation}

Introduce the Hamiltonians

\begin{align*}
\widetilde{H}_N^\circ(\sigma)&=\sum_{i<j}\bigg(G_{ij}\log(c+\Delta \sigma_i\sigma_j)-\frac{c+\Delta\sigma_i\sigma_j}{N}\bigg)\\
\widetilde{H}_N(\sigma)&=\sum_{k\leq \Pi_1}\bigg(G_{i_k,j_k}^k\log(c+\Delta \sigma_{i_k}\sigma_{j_k})-\frac{c+\Delta\sigma_{i_k}\sigma_{j_k}}{N}\bigg)
\end{align*}

on $\Sigma_N$, and denote by

$$\widetilde{F}_N^\circ=\frac{1}{N}\E\log\int_{\Sigma_N}\exp \widetilde{H}_N^\circ(\sigma)\ud P_N^*(\sigma) \quad \text{and} \quad \widetilde{F}_N=\frac{1}{N}\E\log\int_{\Sigma_N}\exp \widetilde{H}_N(\sigma)\ud P_N^*(\sigma)$$

their associated free energy functionals. A Taylor expansion of the logarithm shows that for any $\sigma\in \Sigma_N$,

\begin{align*}
\big\lvert H_N^\circ(\sigma)-\widetilde{H}_N^\circ(\sigma)\big\rvert&\leq \sum_{i<j}\Big\lvert\frac{c+\Delta\sigma_i\sigma_j}{N} -(1-G_{ij})\Big(\frac{c+\Delta \sigma_i\sigma_j}{N}\Big)\Big\rvert+\BigO(1)\\
&\leq \frac{c+\abs{\Delta}}{N}\sum_{i<j}G_{ij}+\BigO(1)
\end{align*}

\begin{align*}
\big\lvert H_N(\sigma)-\widetilde{H}_N(\sigma)\big\rvert&\leq \sum_{k\leq \Pi_1}\Big\lvert\frac{c+\Delta\sigma_{i_k}\sigma_{j_k}}{N} -(1-G_{i_k,j_k}^k)\Big(\frac{c+\Delta \sigma_{i_k}\sigma_{j_k}}{N}\Big)\Big\rvert+\BigO\big(\Pi_1/N^2\big)\\
&\leq \frac{c+\abs{\Delta}}{N}\sum_{k\leq \Pi_1}G_{i_k,j_k}^k+\BigO\big(\Pi_1/N^2\big).
\end{align*}

Since these bounds are uniform in $\sigma\in \Sigma_N$ and $\E\Pi_1=\binom{N}{2}$,

\begin{align*}
\big\lvert \overline{F}_N^\circ-\widetilde{F}_N^\circ\big\rvert&\leq \frac{c+\abs{\Delta}}{N^2}\sum_{i<j}\E G_{ij}+\BigO\big(N^{-1}\big) \leq \frac{(c+\abs{\Delta})^2}{N}+\BigO\big(N^{-1}\big)=\BigO\big(N^{-1}\big),\\
\big\lvert \overline{F}_N-\widetilde{F}_N\big\rvert&\leq \frac{c+\abs{\Delta}}{N^2}\E \sum_{k\leq \Pi_1} G_{i_k,j_k}^k+\BigO\big(\E\Pi_1/N^3\big) \leq \frac{(c+\abs{\Delta})^2}{N^3}\E\Pi_1+\BigO\big(N^{-1}\big)=\BigO\big(N^{-1}\big).
\end{align*}

By the triangle inequality, it therefore suffices to show that

\begin{equation}\label{eqn: SBM equivalence simplification 1}
\lim_{N\to \infty}\big\lvert \widetilde{F}_N-\widetilde{F}_N^\circ\big\rvert = 0.
\end{equation}

We now rewrite $\smash{\widetilde{F}_N}$ in a way that more closely resembles $\smash{\widetilde{F}_N^\circ}$. For each pair $i\leq j$ introduce the random index set

$$\I_{i,j}=\big\{k\leq \Pi_1\mid (i_k,j_k)=(i,j) \text{ or } (i_k,j_k)=(j,i)\big\},$$

and observe that

\begin{align*}
\widetilde{H}_N(\sigma)&=\sum_{i\leq j} \sum_{k\in \I_{i,j}}\bigg(G_{i_k,j_k}^k \log(c+\Delta \sigma_{i_k}\sigma_{j_k})-\frac{c+\Delta \sigma_{i_k}\sigma_{j_k}}{N}\bigg)\\
&=\sum_{i<j}\bigg(\widetilde{G}_{i,j}\log(c+\Delta \sigma_i\sigma_j)-\frac{c+\Delta \sigma_i\sigma_j}{N}\bigg)-\sum_{i\leq N}\bigg(\widetilde{G}_{i,i}\log(c+\Delta)-\frac{c+\Delta}{N}\bigg)
\end{align*}

for the random variables

$$\widetilde{G}_{i,j}=\sum_{k\in \I_{i,j}}G_{i,j}^k.$$

The Poisson coloring theorem (see Chapter 5 in [37]) implies that $\smash{\widetilde{G}_{i,j}}$ is a Poisson random variable with mean

$$\widetilde{\lambda}_{i,j}=\E \Pi_1 \cdot \P\{(i_1,j_1)=(i,j) \text{ or } (i_1,j_1)=(j,i)\}\cdot \P\{G^1_{i,j}=1\}=\begin{cases}
\frac{N-1}{N}\cdot \frac{c+\Delta \sigma_i^*\sigma_j^*}{N}& \text{if }i< j,\\
\frac{N-1}{2N}\cdot \frac{c+\Delta}{N}& \text{if } i=j.
\end{cases}$$

If we introduce the Hamiltonian

$$\widetilde{H}_N'(\sigma)=\sum_{i<j}\bigg(\widetilde{G}_{i,j}\log(c+\Delta \sigma_i\sigma_j)-\frac{c+\Delta \sigma_i\sigma_j}{N}\bigg)$$

and its associated free energy

$$\widetilde{F}_N'=\frac{1}{N}\E\log\int_{\Sigma_N}\exp \widetilde{H}_N'(\sigma)\ud P_N^*(\sigma),$$

$$\big\lvert \widetilde{F}_N'-\widetilde{F}_N\big\rvert\leq \frac{\abs{\log(c+\Delta)}}{N}\sum_{i\leq N}\E\widetilde{G}_{i,i}+\frac{c+\abs{\Delta}}{N}\leq \frac{\abs{\log(c+\Delta)}}{N}\sum_{i\leq N}\widetilde{\lambda}_{i,i}+\frac{2c}{N}=\BigO\big(N^{-1}\big).$$

Together with (<ref>) and the triangle inequality, this means that it suffices to show that

\begin{equation}\label{eqn: SBM equivalence simplification 2}
\lim_{N\to \infty}\big\lvert \widetilde{F}_N'-\widetilde{F}_N^\circ\big\rvert=0.
\end{equation}

At this point, for any random vector $Y=(Y_{i,j})_{i<j}$ introduce the Hamiltonian

$$\widetilde{H}_N(\sigma,Y)=\sum_{i<j}Y_{i,j}\log(c+\Delta \sigma_i\sigma_j)$$

and the measure

$$\widetilde{P}_N^*(\sigma)=\exp\Big(-\sum_{i<j}\frac{c+\Delta \sigma_i\sigma_j}{N}\Big)P_N^*(\sigma).$$

$$F_N(Y)=\frac{1}{N}\log \int_{\Sigma_N}\exp \widetilde{H}_N(\sigma,Y)\ud \widetilde{P}_N^*(\sigma)\quad \text{and} \quad \widetilde{F}_N(Y)=\E F_N(Y)$$

for the associated free energy functionals, and denote by $\Pi_{i,j}$ a Poisson random variable with distribution

$$\Pi_{i,j}\sim \Poi\Big(\frac{c+\Delta\sigma_i^*\sigma_j^*}{N}\Big)$$

conditionally on $\sigma^*$. Observe that

$$\partial_{Y_{i,j}}F_N(Y)=\frac{1}{N}\big\langle \partial_{Y_{i,j}}\widetilde{H}_N(\sigma,Y)\big\rangle=\frac{1}{N}\langle \log(c+\Delta \sigma_i\sigma_j)\rangle\leq \frac{C}{N}$$

for some deterministic constant $C>0$ that depends only on $c$. Here, the bracket $\langle \cdot \rangle$ denotes the Gibbs measure associated with the Hamiltonian $\smash{\widetilde{H}_N(\sigma,Y)}$. It follows by the mean value theorem that

\begin{align*}
\big\lvert \widetilde{F}_N'-\widetilde{F}_N(\Pi)\big\rvert&=\big\lvert \widetilde{F}_N(\widetilde{G})-\widetilde{F}_N(\Pi)\big\rvert\leq \frac{C}{N}\sum_{i<j}\E\big\lvert  \widetilde{G}_{i,j}-\Pi_{i,j}\big\rvert\\
\big\lvert \widetilde{F}_N(\Pi)-\widetilde{F}_N^\circ\big\rvert&=\big\lvert \widetilde{F}_N(\Pi)-\widetilde{F}_N(G)\big\rvert\leq \frac{C}{N}\sum_{i<j}\E\big\lvert \Pi_{i,j}-G_{ij}\big\rvert.
\end{align*}

To bound the first of the sums observe that $\smash{\Pi_{i,j}\stackrel{d}{=} \widetilde{G}_{i,j}+\Pi'_{i,j}}$ for a Poisson random variable with distribution

$$\Pi'_{i,j}\sim\Poi\Big(\frac{c+\Delta \sigma_i^*\sigma_j^*}{N^2}\Big)$$

conditionally on $\sigma^*$. This means that

$$\big\lvert\widetilde{F}_N'-\widetilde{F}_N(\Pi)\big\rvert\leq \frac{C}{N}\sum_{i<j}\E\Pi'_{i,j}\leq \frac{Cc}{N}=\BigO\big(N^{-1}\big),$$

and therefore,

\begin{equation}\label{eqn: SBM equivalence simplification 3}
\big\lvert \widetilde{F}_N'-\widetilde{F}_N^\circ\big\rvert\leq \frac{C}{N}\sum_{i<j}\E\big\lvert \Pi_{i,j}-G_{ij}\big\rvert +\BigO\big(N^{-1}\big).
\end{equation}

If we write $\smash{\lambda_{i,j}=\frac{c+\Delta\sigma_i^*\sigma_j^*}{N}}$, then

\begin{align*}
\E\big\lvert \Pi_{i,j}-G_{ij}\big\rvert&\leq \E\lvert \Pi_{i,j}-G_{ij}\big\rvert\1\{\Pi_{i,j}\geq 2\}+\E\lvert \Pi_{i,j}-G_{ij}\big\rvert\1\{\Pi_{i,j}\leq 2\}\1\{\Pi_{i,j}\neq G_{ij}\}\\
&\leq \E\Pi_{i,j}\1\{\Pi_{i,j}\geq 2\}+\P\{\Pi_{i,j}\geq 2\}+3\P\{\Pi_{i,j}\neq G_{ij}\}\\
&\leq 3\P\{\Pi_{i,j}\neq G_{ij}\}+\BigO\big(\lambda_{i,j}^2\big),
\end{align*}

where we have used the fact that $\abs{G_{ij}}\leq 1$. Taking the infimum over all couplings of $\Pi_{i,j}$ and $G_{ij}$, recalling the definition of the total variation distance in (<ref>) and invoking the binomial-Poisson approximation in <Ref> shows that

$$\E\big\lvert \Pi_{i,j}-G_{ij}\big\rvert\leq 3\TV\big(\Pi_{i,j},G_{ij}\big)+\BigO\big(\lambda_{i,j}^2\big)=\BigO\big(\lambda_{i,j}^2\big)=\BigO\big(N^{-2}\big).$$

Substituting this into (<ref>) and letting $N$ tend to infinity establishes (<ref>). This completes the proof.

§ CONCENTRATION OF THE FREE ENERGY

In this appendix we discuss the concentration of the free energy associated with the perturbed Hamiltonian (<ref>). For simplicity of notation, we will ignore the Hamiltonian (<ref>) and focus instead on the perturbed Hamiltonian

\begin{equation}\label{eqn: SBMA perturbed Hamiltonian}
\end{equation}

where the randomness of each of the Hamiltonians (<ref>), (<ref>) and (<ref>) is independent of the randomness of the other Hamiltonians. The more general case is treated in an identical fashion but the notation becomes too cumbersome for comfort. We will often need to make the dependence of the perturbed Hamiltonian (<ref>) on one of its sources of randomness $\smash{\sigma^*}$, $\smash{\Pi_t}$, $\smash{\I_1=(i_k,j_k)_{k\leq \Pi_t}}$, $\smash{\G=(G_{i_k,j_k}^k)_{k\leq \Pi_t}}$, $\smash{e=(e_{jk})}$, $\smash{\Pi'=(\pi_k)_{k\geq 0}}$, $\smash{\I_2=(i_{jk})_{j\leq \Pi'}}$ and $\smash{Z=(Z_{0,i})_{i\leq N}}$ explicit. To do so, we will abuse notation and write $\smash{H_N'(X)}$ when we want to study the dependence on the source of randomness $X$. The main objects of study will be the free energy,

\begin{equation}
F_N'=\frac{1}{N}\log \int \exp H_N'(\sigma)\ud P_N^*(\sigma),
\end{equation}

and its average

\begin{equation}\label{eqn: SBMA perturbed free energy}
\overline{F}_N'=\frac{1}{N}\E \log \int \exp H_N'(\sigma)\ud P_N^*(\sigma).
\end{equation}

For each even $p\geq 2$, we will bound the concentration function,

\begin{equation}
v_{N,p}=\sup\Big\{\E\big\lvert F_N'-\overline{F}'_N\big\rvert^p\mid \lambda_k\in [2^{-k-1},2^{-k}] \text{ for all } k\geq 0\Big\},
\end{equation}

by means of the generalized Efron-Stein inequality (see Theorem 15.5 of [16]).

Let $X=(X_1,\ldots,X_n)$ and $X'=(X_1',\ldots,X_n')$ be two independent copies of a vector of independent random variables, and let $f:\R^n\to \R$ be a measurable function. Introduce the random variable $Z=f(X)$, and for each $1\leq i\leq n$ let $Z_i'=f(X_1,\ldots,X_{i-1},X_i',X_{i+1},\ldots,X_n)$. If $q\geq 2$, then

\begin{equation}
\E\abs{Z-\E Z}^q\leq C \E \Big\lvert \sum_{i\leq n} \E_{X'}(Z- Z_i')^2\Big\rvert^{\frac{q}{2}},
\end{equation}

where $C>0$ is a constant that depends only on $q$.

A key observation that will be used repeatedly without further explanation is the following: given two sources of randomness $X$ and $X'$, a configuration-independent bound on the difference of the Hamiltonians $H_N'(X)$ and $H_N'(X')$,

\begin{equation}
\max_{\sigma\in \Sigma_N}\big\lvert H_N'(X)-H_N'(X')\big\rvert\leq Y,
\end{equation}

gives a control by the possibly random $Y$ on the difference of the free energy functionals $F_N'(X)$ and $F_N'(X')$,

\begin{equation}
\big\lvert F_N'(X)-F_N'(X')\big\rvert\leq \frac{Y}{N}.
\end{equation}

The following bounds on the moments of Poisson and binomial random variables will also play their part.

If $\Pi$ is a $\Poi(\lambda)$ random variable for some $\lambda\geq 1$ and $k\geq 2$ is an integer, then

\begin{equation}\label{eqn: SBMA Poisson moment bounds}
\E \Pi^k\leq C\lambda^k \quad \text{and} \quad \E \big(\Pi-\E \Pi)^k\leq C\lambda^{\lfloor k/2\rfloor}
\end{equation}

for some constant $C>0$ that depends only on $k$.

Denote by $\smash{\left\{\genfrac{}{}{0pt}{}{k}{j}\right\}}$ the number of ways to partition a $k$ element set into $j$ non-empty subsets. In combinatorics, such numbers are known as Stirling numbers of the second kind, and they have the property that for any integer $m\geq 0$,

\begin{equation}\label{SBMA Stirling numbers}
m^k=\sum_{ j\leq k} \left\{\genfrac{}{}{0pt}{}{k}{j}\right\}(m)_j,
\end{equation}

where $(m)_j=m(m-1)\cdots (m-j+1)$ is the falling factorial. The basic properties of the Poisson distribution imply that

\begin{align*}
\E \Pi^k&=\sum_{m\geq 0}\sum_{j \leq k} \left\{\genfrac{}{}{0pt}{}{k}{j}\right\}(m)_j\frac{\lambda^m}{m!}e^{-\lambda}=\sum_{j \leq k} \left\{\genfrac{}{}{0pt}{}{k}{j}\right\}\lambda^j\sum_{m\geq j}\frac{\lambda^{m-j}}{(m-j)!}e^{-\lambda}=\sum_{j\leq k} \left\{\genfrac{}{}{0pt}{}{k}{j}\right\}\lambda^j\\
&\leq \max(1,\lambda^k)B_k,
\end{align*}

where $B_k$ denotes the $k$'th Bell number. This establishes the first bound in (<ref>). We now prove by induction that for each $k\geq 2$, the function $M_k(\lambda)=\E(\Pi-\E\Pi)^k$ is a polynomial of degree $\lfloor k/2\rfloor$. The base case holds since $M_2(\lambda)=\Var \Pi=\lambda$, so assume the result holds for all $2\leq i\leq k$. By the product rule

\begin{align*}
M_{k}'(\lambda)&=-\sum_{m\geq 0}k(m-\lambda)^{k-1}\frac{\lambda^m}{m!}e^{-\lambda}+\sum_{m\geq 0}(m-\lambda)^km\frac{\lambda^{m-1}}{m!}e^{-\lambda}-M_k(\lambda)\\
&=-kM_{k-1}(\lambda)+\sum_{m\geq 0}(m-\lambda)^k(m-\lambda+\lambda)\frac{\lambda^{m-1}}{m!}e^{-\lambda}-M_k(\lambda)\\
&=-kM_{k-1}(\lambda)+\frac{1}{\lambda}\big(M_{k+1}(\lambda)+\lambda M_k(\lambda)\big)-M_k(\lambda)\\
\end{align*}

Invoking the induction hypothesis shows that $M_{k+1}(\lambda)$ has degree $\max(\lfloor k/2\rfloor, 1+\lfloor (k-1)/2\rfloor)$. This completes the proof.

If $X$ is a $\Bin(n,p)$ random variable with $np\geq 1$ and $k\geq 1$ is an integer, then

\begin{equation}
\E X^k\leq C(np)^k
\end{equation}

for some constant $C>0$ that depends only on $k$.

Using (<ref>) and identifying the probability density function of a $\Bin(n-j,p)$ shows that

\begin{align*}
\E X^k&=\sum_{m \leq n}\sum_{j \leq k} \left\{\genfrac{}{}{0pt}{}{k}{j}\right\}(m)_j\frac{n!}{(n-m)!m!}p^m(1-p)^{n-m}\\
&\leq \sum_{j \leq k}\left\{\genfrac{}{}{0pt}{}{k}{j}\right\}(np)^j \sum_{j\leq m \leq n} \frac{(n-j)!}{(n-m)!(m-j)!}p^{m-j}(1-p)^{n-m}\\
&\leq \max(1,(np)^k)B_k,
\end{align*}

where $B_k$ denotes the $k$'th Bell number. This completes the proof.

For any two sequences $(\epsilon_N)$ and $(s_N)$ satisfying (<ref>) and (<ref>) respectively and every even $p\geq 2$,

\begin{equation}
v_{N,p}\leq \frac{C(1+t^p)}{N^{p/2}}
\end{equation}

for some constant $C>0$ that depends only on $p$, $c$ and $\Delta$.

To alleviate notation, write $C>0$ for a constant that depends only on $p$, $c$ and $\Delta$ whose value might not be the same at each occurrence. Given a source of randomness $X$, write $\E_X$ for the average with respect to the randomness of $X$. The proof will rely upon the generalized Efron-Stein inequality in <Ref> and the fact that

Introduce the averaged free energy functionals

$$\widehat{F}_N'=\E_{\Pi_t}\E_{\I_1}\E_{\G|\sigma^*}F_N'\qquad \text{and}\qquad \widetilde{F}_N'=\E_Z\E_{\Pi'}\E_{\I_2}\E_{e}\widehat{F}_N'$$

in such a way that

\begin{equation}\label{eqn: SBMA free energy concentration key}
\E\big(F_N'-\overline{F}_N'\big)^p\leq C\Big(\E\big(F_N'-\widehat{F}_N'\big)^p+\E\big(\widehat{F}_N'-\widetilde{F}_N'\big)^p+\E\big(\widetilde{F}_N'-\overline{F}_N'\big)^p\Big).
\end{equation}

We will now bound each of these terms separately.

1: proving $\E\big(F_N'-\widehat{F}_N'\big)^p=\BigO\big((t/N)^{p/2}\big)$.

We decompose this further into

\begin{align}\label{eqn: SBMA step 1 key}
\E\big(F_N'-\widehat{F}_N'\big)^p\leq C\Big( \E\big(F_N'-\E_{\G|\sigma^*}F_N'\big)^p&+\E\big(\E_{\G|\sigma^*}F_N'-\E_{\I_1}\E_{\G|\sigma^*}F_N'\big)^p\notag\\
\end{align}

and proceed to bound $I$, $II$ and $III$ individually. By the generalized Efron-Stein inequality

$$I\leq C\E\bigg\lvert \sum_{\ell\leq \Pi_t}\E_{\G^{(\ell)}|\sigma^*}\Big(F_N'(\G)-F_N'\big(\G^{(\ell)}\big)\Big)^2\bigg\rvert^{p/2},$$

where $\smash{\big(\tG^{(\ell)}_{i,j}\big)_{i,j\in \N}}$ is an independent copy of $\smash{\big(G^{(\ell)}_{i,j}\big)_{i,j\in \N}}$. Since $\abs{\Delta}< c$ and all spin configuration coordinates are bounded by one,

\begin{align*}
\big\vert H_N'(\G)-H_N'\big(\G^{(\ell)}\big)\big\rvert\leq \abs{\log(c+&\Delta \sigma_{i_\ell}\sigma_{j_\ell})}\big\lvert G^\ell_{i_\ell,j_\ell}-\widetilde{G}_{i_\ell,j_\ell}^\ell\big\rvert\\
&+\Big\lvert \log\Big(1-\frac{c+\Delta \sigma_{i_\ell}\sigma_{j_\ell}}{N}\Big)\Big\rvert\big\lvert G_{i_\ell,j_\ell}^\ell-\widetilde{G}_{i_\ell,j_\ell}^\ell\big\rvert\leq C\big\lvert G^\ell_{i_\ell,j_\ell}-\widetilde{G}_{i_\ell,j_\ell}^\ell\big\rvert.
\end{align*}

It follows that

\begin{align*}
I&\leq \frac{C}{N^p}\E\Big\lvert \sum_{\ell\leq \Pi_t}\E_{\G^{(\ell)}|\sigma^*}\big\lvert G^\ell_{i_\ell,j_\ell}-\widetilde{G}_{i_\ell,j_\ell}^\ell\big\rvert^2\Big\rvert^{p/2}\leq \frac{C}{N^p}\E\Big\lvert \sum_{\ell\leq \Pi_t}\Big(\Big(1-\frac{2}{N}\Big)G_{i_\ell,j_\ell}^\ell+\frac{1}{N}\Big)\Big\rvert^{p/2}\\
&\leq \frac{C}{N^p}\Big(\E \Big\lvert \sum_{\ell\leq \Pi_t}G_{i_\ell,j_\ell}^\ell\Big\rvert^{p/2}+\frac{1}{N^{p/2}}\E \Pi_t^{p/2}\Big).
\end{align*}

Notice that $\smash{\sum_{\ell\leq \Pi_t}G_{i_\ell,j_\ell}^\ell}$ follows a $\smash{\Bin\Big(\Pi_t,\frac{c+\Delta \sigma_{i_\ell}^*\sigma_{j_\ell}^*}{N}\Big)}$ distribution conditionally on $\Pi_t$. Invoking <Ref> and <Ref> yields

\begin{equation}\label{eqn: SBMA step 1 I}
I\leq \frac{C}{N^{p+\frac{p}{2}}}\E\Pi_t^{p/2}\leq \frac{Ct^{p/2}}{N^{p/2}}.
\end{equation}

Another application of the generalized Efron-Stein inequality gives

$$II\leq \E \bigg\lvert \sum_{\ell\leq \Pi_t}\E_{\I_1^{(\ell)}}\Big(\E_{\G|\sigma^*}F_N'(\I_1)-\E_{\G|\sigma^*}F_N'\big(\I_1^{(\ell)}\big)\Big)^2\bigg\rvert^{p/2},$$

where $\I_1^{(\ell)}$ has an independent copy $\smash{(i_\ell',j_\ell')}$ of $\smash{(i_\ell,j_\ell)}$ at the $\ell$'th coordinate but otherwise coincides with $\I_1$. Taylor expanding the logarithm and remembering that $\smash{G_{i_\ell,j_\ell}^\ell\in\{0,1\}}$, it is readily verified that

$$\big\lvert H_N'(\I_1)\big\rvert\leq \big\lvert G_{i_\ell,j_\ell}^\ell\big\rvert\abs{\log(c+\Delta \sigma_{i_\ell}\sigma_{j_l})}+\big\lvert 1-G_{i_\ell,j_\ell}^\ell\big\rvert \Big\lvert \log\Big(1-\frac{c+\Delta \sigma_{i_\ell}\sigma_{j_\ell}}{N}\Big)\Big\rvert\leq C\Big(\big\lvert G_{i_\ell,j_\ell}^\ell\big\rvert+\frac{1}{N}\Big).$$

This means that $\smash{\big\lvert H_N'(\I_1)-H_N'\big(\I_1^{(\ell)})\big\rvert\leq C\big(\abs{G_{i_\ell,j_\ell}^\ell}+\abs{G_{i'_\ell,j'_\ell}^\ell}+\frac{1}{N}\big)}$, and therefore

$$\Big(\E_{\G|\sigma^*}F_N'(\I_1)-\E_{\G|\sigma^*}F_N'\big(\I_1^{(\ell)}\big)\Big)^2\leq \frac{C}{N^2}\Big(\E_{\G|\sigma^*}\big\lvert G_{i_\ell,j_\ell}^\ell\big\rvert+\E_{\G|\sigma^*}\big\lvert G_{i_\ell',j_\ell'}^\ell\big\rvert+\frac{1}{N}\Big)^2\leq \frac{C}{N^4}.$$

It follows that

\begin{equation}\label{eqn: SBMA step 1 II}
II\leq \frac{C}{N^{2p}}\E \Pi_t^{p/2}\leq \frac{Ct^{p/2}}{N^p}\leq \frac{Ct^{p/2}}{N^{p/2}}.
\end{equation}

A final application of the generalized Efron-Stein inequality reveals that

$$III\leq \E\Big\lvert \E_{\Pi_t'}\big(\E_{\I_1}\E_{\G|\sigma^*}F_N'(\Pi_t)-\E_{\I_1}\E_{\G|\sigma^*}F_N'(\Pi'_t)\big)^2\Big\rvert^{p/2},$$

where $\Pi_t'$ is an independent copy of $\Pi_t$. Slightly abusing notation and redefining $\Pi_t'$ to be the maximum between $\Pi_t$ and $\Pi_t'$, we see that

\begin{align*}
\big\lvert H_N'(\Pi_t')-H_N'(\Pi_t)\big\rvert&\leq \sum_{\Pi_t\leq k\leq \Pi_t'}\bigg(\big\lvert G_{i_k,j_k}^k\big\rvert\abs{\log(c+\Delta \sigma_{i_k}\sigma_{j_k})}+\big\lvert 1-G_{i_k,j_k}^k\big\rvert\Big\lvert \log\Big(1-\frac{c+\Delta \sigma_{i_k}\sigma_{j_k}}{N}\Big)\Big\rvert\bigg)\\
&\leq C\sum_{\Pi_t\leq k\leq \Pi_t'}\Big(\big\lvert G_{i_k,j_k}^k\big\rvert+\frac{1}{N}\Big).
\end{align*}

It follows that

$$\big\lvert \E_{\I_1}\E_{\G|\sigma^*}F_N'(\Pi_t)-\E_{\I_1}\E_{\G|\sigma^*}F_N'(\Pi'_t)\big\rvert\leq \frac{C}{N} \E_{\I_1}\E_{\G|\sigma^*} \sum_{\Pi_t\leq k\leq\Pi_t'}\Big(\big\lvert G_{i_k,j_k}^k\big\rvert+\frac{1}{N}\Big)\leq \frac{C}{N^2}\abs{\Pi_t'-\Pi_t},$$

and by Jensen's inequality and <Ref>,

\begin{equation}\label{eqn: SBMA step 1 III}
III\leq \frac{C}{N^{2p}}\E\big\lvert \E_{\Pi_t'}\abs{\Pi_t'-\Pi_t}^2\big\rvert^{p/2}\leq \frac{C}{N^{2p}}\E \lvert \Pi_t-\E \Pi_t\rvert^p\leq \frac{Ct^{p/2}}{N^p}\leq \frac{Ct^{p/2}}{N^{p/2}}.
\end{equation}

Combining (<ref>), (<ref>), (<ref>) and (<ref>) reveals that $\E\big(F_N'-\widehat{F}_N'\big)^p=\BigO\big((t/N)^{p/2}\big)$.

2: proving $\E\big(\widehat{F}_N'-\widetilde{F}_N'\big)^p=\BigO\big(N^{-p/2}\big).$

We decompose this further into

\begin{align}\label{eqn: SBMA step 2 key}
\E\big(\widehat{F}_N'-\widetilde{F}_N'\big)^p\leq C\Big(\E\big(\widehat{F}_N'-&\E_e\widehat{F}_N'\big)^p+\E\big(\E_e\widehat{F}_N'-\E_{\I_2}\E_e\widehat{F}_N'\big)^p+\E\big(\E_{\I_2}\E_e\widehat{F}_N'-\E_{\Pi'}\E_{\I_2}\E_{e}\widehat{F}_N'\big)^p\notag\\
\end{align}

and proceed to bound $I$, $II$, $III$ and $IV$ individually.  By the generalized Efron-Stein inequality

$$I\leq\E \bigg\lvert \sum_{k\geq 0}\sum_{j\leq \pi_k}\E_{e^{(jk)}}\Big(\widehat{F}_N'(e)-\widehat{F}_N'\big(e^{(jk)}\big)\Big)^2\bigg\rvert^{p/2},$$

where $e^{(jk)}$ has an independent copy $e_{jk}'$ of $e_{jk}$ at the $jk$'th coordinate but otherwise coincides with $e$. Since

$$\big\lvert H_N'(e)-H_N'\big(e^{(jk)}\big)\big\rvert\leq \frac{\abs{\lambda_k\sigma_{i_{jk}}}}{\abs{1+\lambda_k\sigma_{i_{jk}}^*}}\big \lvert e_{jk}-e'_{jk}\big\rvert\leq \frac{\lambda_k}{1-\lambda_k}\big\lvert e_{jk}-e'_{jk}\big\rvert,$$

and $\lambda_k\in [2^{-k-1},2^{-k}]$, we have

$$I\leq \frac{C}{N^{p}}\E \Big\lvert \sum_{k\geq 0}\frac{1}{2^{k}}\cdot \frac{1}{2^k}\sum_{j\leq \pi_k}\E_{e_{jk}'}\big\lvert e_{jk}-e'_{jk}\big\rvert^2 \Big\rvert^{p/2}.$$

It follows by two applications of Hölder's inequality and Jensen's inequality that

$$I\leq \frac{C}{N^p}\E \sum_{k\geq 0}\Big(\frac{1}{2^k}\sum_{j\leq \pi_k}\E_{e_{jk}'}\big\lvert e_{jk}-e_{jk}'\big\rvert^2\Big)^{p/2}\leq \frac{C}{N^p}\E\sum_{k\geq 0}\frac{1}{2^{\frac{kp}{2}}}\pi_k^{\frac{p}{2}-1}\sum_{j\leq \pi_k}\E_{e_{jk}'}\big\lvert e_{jk}-e_{jk}'\big\rvert^p.$$

Recalling that $e_{jk}\sim \Exp(1)$ while $\pi_{jk}\sim \Poi(s_N)$ and invoking <Ref> gives

\begin{equation}\label{eqn: SBMA step 2 I}
I\leq \frac{C}{N^p}\sum_{k\geq 0}\frac{1}{2^{\frac{kp}{2}}}\E\pi_k^{\frac{p}{2}}\leq C\Big(\frac{s_N}{N^2}\Big)^{p/2}\leq \frac{C}{N^{p/2}}.
\end{equation}

Similarly, by the generalized Efron-Stein inequality,

$$II\leq C\E\bigg\lvert \sum_{k\geq 0}\sum_{j\leq \pi_k}\E_{\I_2^{(jk)}}\Big(\E_e\widehat{F}_N'(\I_2)-\E_e\widehat{F}_N'\big(\I_2^{(jk)}\big)\Big)^2\bigg\rvert^{p/2},$$

where $\I_2^{(jk)}$ has an independent copy $i'_{jk}$ of $i_{jk}$ at the $jk$'th coordinate but otherwise coincides with $\I_2$. By the mean value theorem,

\begin{align*}
\big\lvert H_N'(\I_2)-H_N'\big(\I^{(jk)}_2\big)\big\rvert &\leq \abs{\log(1+\lambda_k\sigma_{i_{jk}})-\log(1+\lambda_k\sigma_{i_{jk}'})}+\lambda_ke_{jk}\Big\lvert \frac{\sigma_{i_{jk}}}{1+\lambda_k\sigma^*_{i_{jk}}}-\frac{\sigma_{i_{jk}'}}{1+\lambda_k\sigma^*_{i_{jk}'}}\Big\rvert\\
&\leq C\lambda_k(1+e_{jk}).
\end{align*}

It follows once again by two applications of Hölder's inequality and <Ref> that

\begin{equation}\label{eqn: SBMA step 2 II}
II\leq \frac{C}{N^p}\E \sum_{k\geq 0}\frac{1}{2^{\frac{kp}{2}}}\pi_k^{\frac{p}{2}-1}\sum_{j\leq \pi_k}(1+e_{jk})^p\leq C\Big(\frac{s_N}{N^2}\Big)^{p/2}\leq \frac{C}{N^{p/2}}.
\end{equation}

Another application of the generalized Efron-Stein inequality yields

$$III\leq C\E\bigg\lvert \sum_{k\geq 0} \E_{\Pi'^{(k)}}\Big(\E_{\I_2}\E_e\widehat{F}_N'(\Pi')-\E_{\I_2}\E_e\widehat{F}_N'\big(\Pi'^{(k)}\big)\Big)^2\bigg\rvert^{p/2},$$

where $\smash{\Pi'^{(k)}}$ has an independent copy $\pi_k'$ of $\pi_k$ at the $k$'th coordinate but otherwise coincides with $\Pi'$. Slightly abusing notation and redefining $\smash{\Pi'^{(k)}}$ to be the process with the larger $k$'th coordinate, we see that

\begin{align*}
\big\lvert H_N'(\Pi')-H_N'(\Pi'^{(k)})\big\rvert&\leq \sum_{\pi_k\leq j\leq \pi_k'}\Big\lvert \log(1+\lambda_k\sigma_{i_{jk}})-\frac{\lambda_ke_{jk}\sigma_{i_{jk}}}{1+\lambda_k\sigma^*_{i_{jk}}}\Big\rvert\\
&\leq \sum_{\pi_k\leq j\leq \pi_k'}\bigg(\Big\lvert\lambda_k\sigma_{i_{jk}}-\frac{\lambda_ke_{jk}\sigma_{i_{jk}}}{1+\lambda_k\sigma^*_{i_{jk}}}\Big\rvert+C\lambda_k^2\bigg)\\
&\leq \sum_{\pi_k\leq j\leq \pi_k'}\bigg(\lambda_k\Big\lvert 1-\frac{e_{jk}}{1+\lambda_k\sigma^*_{i_{jk}}}\Big\rvert +C\lambda_k^2\bigg)\\
&\leq \lambda_k\sum_{\pi_k\leq j\leq \pi_k'}\bigg(\frac{\abs{1-e_{jk}}+\lambda_k}{1-\lambda_k}+C\lambda_k\bigg).
\end{align*}

It follows by two applications of the Cauchy-Schwarz inequality that

\begin{align*}
III&\leq \frac{C}{N^p}\E \sum_{k\geq 0}\frac{1}{2^{\frac{kp}{2}}}\bigg(\sum_{\pi_k\leq j\leq \pi_k'}\bigg(\frac{\abs{1-e_{jk}}+\lambda_k}{1-\lambda_k}+C\lambda_k\bigg)\bigg)^p\\
&\leq \frac{C}{N^p}\E \sum_{k\geq 0}\frac{1}{2^{\frac{kp}{2}}}\abs{\pi_k-\pi_k'}^{p-1}\sum_{\pi_k\leq j\leq \pi_k'}\bigg(\frac{\abs{1-e_{jk}}+\lambda_k}{1-\lambda_k}+C\lambda_k\bigg)^p\\
&\leq \frac{C}{N^p} \sum_{k\geq 0}\frac{1}{2^{\frac{kp}{2}}}\E \abs{\pi_k-\pi_k'}^p.
\end{align*}

Since $\E\abs{\pi_k-\pi_k'}^p\leq C\E\abs{\pi_k-\E\pi_k}^p\leq s_N^{p/2}$ by <Ref>, this implies that

\begin{equation}\label{eqn: SBMA step 2 III}
III\leq C\Big(\frac{s_N}{N^2}\Big)^{p/2}\leq \frac{C}{N^{p/2}}.
\end{equation}

A final application of the generalized Efron-Stein inequality gives

$$IV\leq C\E \bigg\lvert \sum_{i\leq N}\E_{Z^{(i)}}\Big(\E_{\Pi'}\E_{\I_2}\E_e\widehat{F}_N'(Z)-\E_{\Pi'}\E_{\I_2}\E_e\widehat{F}_N'\big(Z^{(i)}\big)\Big)^2\bigg\rvert^{p/2},$$

where $Z^{(i)}$ has an independent copy $Z_{i,0}'$ of $Z_{i,0}$ at the $i$'th coordinate but otherwise coincides with $Z$. Combining Hölder's inequality with the bound

$$\big\lvert H_N'(Z)-H_N'\big(Z^{(i)}\big)\big\rvert\leq \sqrt{\lambda_0\epsilon_N}\big\lvert Z_{i,0}-Z_{i,0}'\big\rvert$$

reveals that

\begin{equation}\label{eqn: SBMA step 2 IV}
IV\leq C\Big(\frac{\lambda_0 \epsilon_N}{N}\Big)^p\E \Big\lvert \sum_{i\leq N}\E_{Z^{(i)}}\big\lvert Z_{i,0}-Z_{i,0}'\big\rvert^2\Big\rvert^{p/2}\leq \frac{C}{N^p}N^{\frac{p}{2}-1}\sum_{i\leq N}\E \big\lvert Z_{i,0}-Z_{i,0}'\big\rvert^p\leq \frac{C}{N^{p/2}}.
\end{equation}

Together with (<ref>), (<ref>), (<ref>) and (<ref>), this shows that $\E\big(\widehat{F}_N'-\widetilde{F}_N'\big)^p=\BigO\big(N^{-p/2}\big)$.

3: proving $\E\big(\widetilde{F}_N'-\overline{F}_N'\big)^p=\BigO\big((t^2/N)^{p/2}\big)$

Controlling the final term in (<ref>) requires more care since $\widetilde{F}_N'$ depends on $\sigma^*$ both through $F_N'$ and through the conditional expectation $\E_{\G|\sigma^*}$. To simplify notation, write $\E'=\E_Z\E_{\Pi'}\E_{\I_2}\E_{e}\E_{\Pi_t}\E_{\I_1}$ in such a way that by the generalized Efron-Stein inequality

\begin{align}\label{eqn: SBMA step 3 key}
\E\big(\widetilde{F}_N'-\overline{F}_N'\big)^p&\leq C\E\bigg\lvert \sum_{\ell\leq N}\E_{\sigma^{*,(\ell)}}\Big(\E'\E_{\G|\sigma^*}F_N'(\sigma^*)-\E'\E_{\G|\sigma^{*,(\ell)}}F_N'\big(\sigma^{*,(\ell)}\big)\Big)^2\bigg\rvert^{p/2}\notag\\
&\leq C\E\bigg\lvert \sum_{\ell\leq N}\E_{\sigma^{*,(\ell)}}\Big(\E'\E_{\G|\sigma^*}F_N'(\sigma^*)-\E'\E_{\G|\sigma^{*}}F_N'\big(\sigma^{*,(\ell)}\big)\Big)^2\bigg\rvert^{p/2}\notag\\
&\quad +C\E\bigg\lvert \sum_{\ell\leq N}\E_{\sigma^{*,(\ell)}}\Big(\E'\E_{\G|\sigma^*}F_N'\big(\sigma^{*,(\ell)}\big)-\E'\E_{\G|\sigma^{*,(\ell)}}F_N'\big(\sigma^{*,(\ell)}\big)\Big)^2\bigg\rvert^{p/2}\notag\\
\end{align}

where $\sigma^{*,(\ell)}$ has an independent copy $\widetilde{\sigma}^*_\ell$ of $\sigma^*_\ell$ at the $\ell$'th coordinate but otherwise coincides with $\sigma^*$. Since

\begin{align*}
\big\lvert H_N'(\sigma^*)-H_N'(\sigma^{*,(l)})\big\rvert&\leq \lambda_0\epsilon_N\abs{\sigma_i}\big\lvert \sigma^*_\ell-\widetilde{\sigma}_\ell^*\big\rvert+\sum_{k\geq 1}\sum_{j:i_{jk}=\ell}\bigg\lvert \frac{\lambda_ke_{jk}\sigma_\ell}{1+\lambda_k\sigma^*_\ell}-\frac{\lambda_ke_{jk}\sigma_\ell}{1+\lambda_k\widetilde{\sigma}^*_\ell}\bigg\rvert\\
&\leq 2 \epsilon_N+\sum_{k\geq 1}\sum_{j:i_{jk}=\ell}\frac{2\lambda_k^2e_{jk}}{(1-\lambda_k)^2},
\end{align*}

and $\E e_{jk}=1$, the Fubini-Tonelli theorem and the basic properties of the multinomial distribution imply that

\begin{align*}
\big\lvert \E'\E_{\G|\sigma^*}F_N'(\sigma^*)-\E'\E_{\G|\sigma^*}F_N'\big(\sigma^{*,(\ell)}\big)\big\rvert&\leq \frac{2\epsilon_N}{N}+\frac{1}{N}\E_{\Pi'}\sum_{k\geq 1}\frac{2\lambda_k^2}{(1-\lambda_k)^2}\E_{\I_2}\abs{\{j:i_k=\ell\}}\\
&\leq \frac{2}{N}+\frac{1}{N^2}\E_{\Pi'}\sum_{k\geq 1}\frac{2\lambda_k^2}{(1-\lambda_k)^2}\pi_k\leq \frac{2}{N}+\frac{s_N}{N^2}\leq \frac{3}{N}.
\end{align*}

It follows that

\begin{equation}\label{eqn: SBMA step 3 I}
I\leq C\Big(\frac{N}{N^2}\Big)^{p/2}=\frac{C}{N^{p/2}}.
\end{equation}

To bound $II$ we will use an interpolation argument. Fix $1\leq \ell\leq N$ and condition on all sources of randomness other than $\G$. For each $u\in [0,1]$, $G\in \{0,1\}^{\Pi_t}$ and $k\leq \Pi_t$, let

\begin{align*}
\end{align*}

where $\sigma_{\ell}^{*,u}=(1-u)\sigma^*_{\ell}+u\widetilde{\sigma}^*_{\ell}$.
Write $\sigma^{*,u}$ for the configuration with $\ell$'th coordinate $\sigma_\ell^{*,u}$ which otherwise coincides with $\sigma^*$, and introduce the sets

_1^1   ={k|i_k=l  and  j_k≠l}            _1^3   ={k|i_k=j_k=l}

_1^2   ={k|i_k≠l  and  j_k=l}            _1^4   ={k|i_k≠l≠j_k}.

Denote $\widetilde{\G}=(\G_k)_{k\in \I_1^4}$, $\G^{(k)}=\G\setminus \G_k$, $\widetilde{G}=(G_k)_{k\in \I_1^4}$ and $G^{(k)}=G\setminus G_k$. Define the interpolating free energy

$$\p(u)=\sum_{G\in \{0,1\}^{\Pi_t}}F_N'\big(\sigma^{*,(\ell)},G\big)\P\big\{\widetilde{\G}=\widetilde{G}|\sigma^*\big\}\cdot \prod_{k\in \I_1^1}P_u^{1,k}(G)\prod_{k\in \I_1^2}P_u^{2,k}(G)\prod_{k\in \I_1^3}P_u^{3,k}(G)$$

in such a way that $\p(1)=\E_{\G|\sigma^*}F_N'\big(\sigma^{*,(\ell)}\big)$ and $\p(0)=\E_{\G|\sigma^{*,(\ell)}}F_N'\big(\sigma^{*,(\ell)}\big)$. By the product rule,

\begin{align*}
\p'(u)&=\sum_{k\in \cup_{i\leq 3}\I_1^i}\sum_{G\in \{0,1\}^{\Pi_t}}F_N'\big(\sigma^{*,(\ell)},G\big)\P\big\{\G^{(k)}=G^{(k)}|\sigma^{*,u}\big\}(2G_k-1)\\
&\qquad\qquad\qquad\qquad\qquad\Bigg(\frac{\Delta(\widetilde{\sigma}_\ell^*-\sigma^*_\ell)(\sigma_{j_k}^*\1_{\{k\in \I_1^1\}}+\sigma_{i_k}^*\1_{\{k\in \I_1^2\}}+2\sigma_\ell^{*,u}\1_{\{k\in \I_1^3\}})}{N}\Bigg)\\
&=\sum_{k\in \I_1^1}D_k\frac{\Delta(\widetilde{\sigma}_\ell^*-\sigma^*_\ell)\sigma_{j_k}^*}{N}+\sum_{k\in \I_1^2}D_k\frac{\Delta(\widetilde{\sigma}_\ell^*-\sigma^*_\ell)\sigma_{i_k}^*}{N}\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{k\in \I_1^3}D_k\frac{2\Delta\big((1-u)\sigma_\ell^*+u\widetilde{\sigma}_\ell^*\big)(\widetilde{\sigma}_\ell^*-\sigma_\ell^*)}{N}
\end{align*}

for $D_k=\E_{\G^{(k)}|\sigma^{*,u}}F_N'\big(\sigma^{*,(\ell)},\G^{(k)},\G_k=1\big)-\E_{\G^{(k)}|\sigma^{*,u}}F_N'\big(\sigma^{*,(\ell)},\G^{(k)},\G_k=0\big)$. Since

$$\big\lvert H_N'\big(\G^{(k)}, \G_k=1\big)-H_N'\big(\G^{(k)},\G_k=0\big)\big\rvert\leq \Big\rvert\log(c+\Delta \sigma_{i_k}\sigma_{j_k})-\log\Big(1-\frac{c+\Delta \sigma_{i_k}\sigma_{j_k}}{N}\Big)\Big\lvert\leq C,$$

we have $\abs{D_k}\leq \frac{C}{N}$, so the fundamental theorem of calculus yields

$$\big\lvert \E_{\G|\sigma^*}F_N'\big(\sigma^{*,(\ell)}\big)-\E_{\G|\sigma^{*,(\ell)}}F_N'\big(\sigma^{*,(l)}\big)\big\rvert\leq \sup_{u\in (0,1)}\abs{\p'(u)}\leq \frac{C}{N^2}\big(\abs{\I_1^1}+\abs{\I_1^2}+\abs{\I_1^3}\big).$$

It follows by the basic properties of the binomial distribution that

\begin{align*}
\Big(\E'\E_{\G|\sigma^*}F_N'\big(\sigma^{*,(\ell)}\big)-\E'\E_{\G|\sigma^{*,(\ell)}}F_N'\big(\sigma^{*,(\ell)}\big)\Big)^2&\leq \frac{C}{N^4}\sum_{1 \leq i \leq 3} \big(\E_{\Pi_t}\abs{\I_1^i}\big)^2=\frac{C}{N^4}\sum_{1\leq i \leq 3} \Big(\E_{\Pi_t}\frac{\Pi_t}{N}\Big)^2\\
&\leq \frac{Ct^2}{N^2},
\end{align*}

and thus

\begin{equation}\label{eqn: SBMA step 3 II}
II\leq C\bigg(\frac{N t^2}{N^2}\bigg)^{p/2}=\frac{Ct^p}{N^{p/2}}.
\end{equation}

Combining (<ref>), (<ref>) and (<ref>) reveals that $\E\big(\widetilde{F}_N'-\overline{F}_N'\big)^p=\BigO\big((t^2/N)^{p/2}\big)$. Together with (<ref>), step $1$ and step $2$ this completes the proof.

§ MULTI-OVERLAP CONCENTRATION

In this appendix we prove a finitary version of the main result in [12] regarding the concentration of the multi-overlaps (<ref>). Instead of focusing on the stochastic block model (<ref>) or (<ref>), we will work in the general setting of optimal Bayesian inference; this presents no additional difficulty, and we suspect that our restatement of the multi-overlap concentration result in [12] will be useful for the analysis of other statistical inference models.

Let us describe a general optimal Bayesian inference model following [12]. We consider a ground-truth signal $\sigma^*\in \Sigma_N=\{-1,+1\}^N$ with independent coordinates generated from a prior distribution $P^*$,

\begin{equation}
\sigma^*\sim P^*=\prod_{i\leq N}P_i^*.
\end{equation}

We suppose that the data $\D=\D(\sigma^*)$ is sampled conditionally on the unknown signal $\sigma^*$ from a probability distribution $P_{\mathrm{out}}$,

\begin{equation}
\D\sim P_{\text{out}}\{\cdot|\sigma^*\}.
\end{equation}

The inference task is to recover the signal $\sigma^*$ as accurately as possible given the data $\D$ under the assumption that the likelihood $P_{\text{out}}$ and the prior $P^*$ are known to the statistician. In this setting the posterior of the model can be written explicitly. Indeed, if

\begin{equation}\label{eqn: SBMA log-likelihood}
H_N(\sigma)=\log P_{\text{out}}\big\{\D|\sigma^*=\sigma\big\}
\end{equation}

denotes the Hamiltonian or log-likelihood of the model, then the Gibbs measure or posterior distribution of the model is given by Bayes' formula,

\begin{equation}\label{eqn: SBMA generic Gibbs measure}
G_N(\ud \sigma)=\P\{\sigma^*\in \ud \sigma|\D\}=\frac{\exp H_N(\sigma) P^*(\ud \sigma)}{\int \exp H_N(\tau)P^*(\ud \tau)}.
\end{equation}

In addition to working in the context of optimal Bayesian inference, we will assume that the Hamiltonian (<ref>) satisfies symmetry between sites. This means that for any permutation $\rho$ of the spin indices,

\begin{equation}\label{eqn: SBMA symmetry between sites}
\P\{\sigma^*\in \ud \sigma|\D\}\stackrel{d}{=}\P\{\rho(\sigma^*)\in \ud \sigma|\D\}.
\end{equation}

Notice that both the stochastic block model (<ref>) and its enriched version (<ref>) fall into the setting we have just described. For instance, in the enriched stochastic block model we have $P_i^*=\Ber(p)$ and $\smash{\D=\widetilde{\D}^{t,\mu[-1,1],\bar \mu}}$, where the data $\smash{\widetilde{\D}^{t,s,\mu}}$ was defined in (<ref>).

The concentration of the multi-overlaps (<ref>) associated with the Hamiltonian (<ref>) will be enforced through a small perturbation which will not affect the limit of the associated free energy (<ref>). Recall the choice of the sequences $(\epsilon_N)$ and $(s_N)$ satisfying (<ref>) and (<ref>), respectively. Fix an integer $K_+\geq 1$, and for each perturbation parameter $\lambda \in \R^{1+K_+}$ with $\lambda_k\in [2^{-k-1},2^{-k}]$ for $0\leq k\leq K_+$ recall the definition of the perturbation Hamiltonians (<ref>) and (<ref>). Introduce the perturbed Hamiltonian

\begin{equation}\label{eqn: SBMA perturbed generic Hamiltonian}
\end{equation}

where the randomness of each Hamiltonian is independent of the randomness of the other Hamiltonians. The multi-overlaps associated with this perturbed Hamiltonian are defined as in (<ref>),

\begin{equation}\label{eqn: SBMA generic multi-overlaps}
R_{\ell_1,\ldots,\ell_n}=\frac{1}{N}\sum_{i\leq N}\sigma_i^{\ell_1}\cdots \sigma_i^{\ell_n},
\end{equation}

where $(\sigma^\ell)$ denotes a sequence of i.i.d. replicas sampled from the Gibbs measure $\langle \cdot \rangle$ associated with the perturbed Hamiltonian (<ref>). It is actually these multi-overlaps that will be shown to concentrate. The proof of <Ref> shows that the free energy functionals associated with the Hamiltonians (<ref>) and (<ref>) are asymptotically equivalent; for our purposes these two Hamiltonians can therefore be thought to describe the same model.

To establish the concentration of the multi-overlaps (<ref>) we will closely follow the arguments in [12]. The authors in [12] obtain the concentration of the multi-overlaps (<ref>) for some perturbation parameter $\lambda$ by showing that it holds on average over the set of admissible perturbation parameters. In the proof of <Ref> we will need to be able to obtain multi-overlap concentration for a specific perturbation parameter. Following the strategy in [12], we will propose a verifiable condition on a perturbation parameter $\lambda$ which ensures the concentration of its associated multi-overlaps. To be more precise, we will obtain the concentration of the multi-overlaps (<ref>) up to a small error for any sequence of perturbation parameters $(\lambda^N)$ with

\begin{equation}\label{eqn: SBMA limits to get FDS}
\lim_{N\to \infty}\E\big\langle (\L_k-\E\langle \L_k\rangle)^2\big\rangle=0.
\end{equation}

The quantities $\L_k$ are defined in (<ref>) and (<ref>) for $0\leq k\leq K_+$, and, through a slight abuse of notation, we have written $\smash{\langle \cdot \rangle}$ for the Gibbs average with respect to the perturbed Hamiltonian (<ref>) associated with the perturbation parameters $\smash{(\lambda^N)}$. If necessary, we will write $\langle \cdot \rangle_N$ to emphasize the dependence of this Gibbs measure on $N$.

We begin by showing that (<ref>) implies the concentration of the magnetization $R_1$ and of the overlap $R_{1,2}$; the former will be immediate from the Nishimori identity (<ref>) while the latter will follow from a standard application of the Gaussian integration by parts formula (see Lemma 1.4 in [50]).

For any integer $N\geq 1$,

\begin{equation}
\E\big\langle (R_1-\E\langle R_1\rangle)^2\big\rangle\leq \frac{1}{N}.
\end{equation}

Applying the Nishimori identity reveals that

$$\E\big\langle (R_1-\E\langle R_1\rangle)^2\big\rangle=\frac{1}{N^2}\sum_{i\leq N}\E\big(\sigma_i^*-\E \sigma_i^*\big)^2\leq \frac{1}{N}.$$

This completes the proof.

For any integer $N\geq 1$,

\begin{equation}
\E\big\langle (R_{1,2}-\E\langle R_{1,2}\rangle)^2\big \rangle\leq 4\E\big\langle (\L_0-\E\langle \L_0\rangle)^2\big\rangle.
\end{equation}

The proof is taken from the Appendix of [12], and it consists in testing the concentration of the overlap $\smash{R_{1,*}=\frac{\sigma\cdot \sigma^*}{N}}$ against the Hamiltonian $\L_0$ by means of the Gaussian integration by parts formula. Using (<ref>) shows that

\begin{align}\label{SBMA concentration of R2 covariance}
\E\big\langle (R_{1,*}-\E\langle R_{1,*}\rangle)(\L_0-\E\langle \L_0\rangle)\big\rangle
=\E\big\langle R_{1,*}(&R_{1,*}-\E\langle R_{1,*}\rangle)\big\rangle\notag\\
&+\frac{1}{2N\sqrt{\lambda_{0,N}}}\E\big\langle R_{1,*}(\sigma\cdot Z_0-\E\langle \sigma\cdot Z_0\rangle)\big\rangle.
\end{align}

The Gaussian integration by parts formula and the Nishimori identity imply that

$$\E\langle \sigma\cdot Z\rangle=N\sqrt{\lambda_{0,N}}\big(1-\E\langle R_{1,*}\rangle\big)\quad \text{and} \quad \E\big\langle R_{1,*}\sigma\cdot Z\big\rangle=N\sqrt{\lambda_{0,N}}\big(\E\langle R_{1,*}\rangle -\E\langle R_{1,*}\rangle^2\big).$$

Substituting these two equalities into (<ref>) reveals that

$$\E\big\langle (R_{1,*}-\E\langle R_{1,*}\rangle)(\L_0-\E\langle \L_0\rangle)\big\rangle=\frac{1}{2}\E\big\langle (R_{1,*}-\langle R_{1,*}\rangle)^2 \big\rangle+\frac{1}{2}\E\big\langle(R_{1,*}-\E\langle R_{1,*}\rangle)^2\big\rangle.$$

(There seems to be a sign error in equation (5.2) of [12].)
It follows by the Nishimori identity that

$$\E\big\langle (R_{1,*}-\E\langle R_{1,*}\rangle)(\L_0-\E\langle \L_0\rangle)\big\rangle\geq \frac{1}{2}\E\big\langle(R_{1,2}-\E\langle R_{1,2}\rangle)^2\big\rangle.$$

Invoking the Cauchy-Schwarz inequality and the Nishimori identity completes the proof.

The concentration of the multi-overlaps (<ref>) is considerably more complicated to obtain, and follows from the Franz-de Sanctis identities described in [12]. The first section of this appendix will be devoted to establishing this implication. In the second section we will prove a finitary version of the multi-overlap concentration result in [12] which will be uniform over an appropriate class of random probability measures. This uniformity plays its part in the proof <Ref>.

§.§ Franz-de Sanctis identities

The Franz-de Sanctis identities may be thought of as the Ghirlanda-Guerra identities of optimal Bayesian inference. A random probability measure which satisfies the Ghirlanda-Guerra identities must have an ultrametric support; a deep insight which leads to the appearance of the intricate Poisson-Dirichlet probability cascades in many spin glass models [50]. The Franz-de Sanctis identities enforce a much simpler and more rigid structure on a random probability measure which we will describe in due course. To state these identities, it will be convenient to fix a uniform index $i\in \{1,\ldots,N\}$ and an exponential random variable $e\sim \Exp(1)$ independent of all other sources of randomness, and introduce the random variables

\begin{equation}\label{eqn: SBMA Franz de Sanctis variables}
y_{ik}=\frac{e}{1+\lambda_k\sigma_i^*}, \quad \theta_{ik}^\ell=\log(1+\lambda_k\sigma_i^\ell)-\lambda_ky_{ik}\sigma_i^\ell,\quad \text{and} \quad d_{ik}^\ell=\frac{y_{ik}\sigma_i^\ell}{1+\lambda_k\sigma_i^*}
\end{equation}

for $1\leq k\leq K_+$.

For any $1\leq k\leq K_+$ and any function $f_n$ of finitely many spins on $n$ replicas and of the signal $\sigma^*$ with $\norm{f_n}_{L^\infty}\leq 1$,

\begin{equation}
\bigg\lvert \E \frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle}{\langle e^{\theta_{ik}}\rangle^n}-\E\langle f_n\rangle \E\frac{\langle d_{ik}e^{\theta_{ik}}\rangle}{\langle e^{\theta_{ik}}\rangle}\bigg\rvert\leq \bigg(2\E\big\langle( \L_k-\E\langle \L_k\rangle)^2\big\rangle+\frac{16}{s_N}\bigg)^{1/2}.
\end{equation}

The Franz-de Sanctis identities are proved in a similar fashion to the Ghirlanda-Guerra identities by testing the concentration of the quantities

\begin{equation}
\widetilde{\L}_k=\frac{1}{s_N}\sum_{j\leq \pi_k}\frac{\sigma_{i_{jk}}e_{jk}}{(1+\lambda_k\sigma^*_{i_{jk}})^2}
\end{equation}

defined for $1\leq k\leq K_+$ against an arbitrary function of finitely many spins and of the signal $\sigma^*$. Notice that  $\smash{\widetilde{\L}_k}$ is none other than the second term in the sum defining each $\L_k$ in (<ref>). The reason for focusing only on the second term is that the first term concentrates automatically by the Nishimori identity. This is the content of Proposition 3.4 in [12] which we reproduce here for completeness. We present a slightly simpler proof than that in [12] which was kindly shared with us by Dmitry Panchenko.

For any $1\leq k\leq K_+$ and every large enough $N\geq 1$,

\begin{equation}
\E\Big\langle \big(\widetilde{\L}_k-\E\langle \widetilde{\L}_k\rangle\big)^2\Big\rangle\leq 2\E\big(\langle \L_k-\E\langle \L_k\rangle)^2\big\rangle+\frac{16}{s_N}.
\end{equation}

Introduce the quantity
$$g(\sigma,\pi_k)=\sum_{j\leq \pi_k}\frac{ \sigma_{i_{jk}}}{1+\lambda_k\sigma_{i_{jk}}}$$

in such a way that $\smash{\widetilde{\L}_k=s_N^{-1}g(\sigma,\pi_k)}-\L_k$. Write $\Var$ for the variance with respect to the measure $\E\langle\cdot \rangle$. Since the variance of a sum of two random variables is bounded by twice the sum of the variance of each of the random variables,

\begin{equation}\label{eqn: SBMA L tilde concentration key}
\Var \big(\widetilde{\L}_k\big)\leq 2 \Big(\Var(\L_k)+\frac{1}{s_N^2}\Var(g)\Big).
\end{equation}

By the Nishimori identity and a direct computation,

\begin{equation}\label{eqn: SBMA L tilde concentration Var g decomposition}
\Var\big(g(\sigma,\pi_k)\big)=\E\bigg(\sum_{j\leq \pi_k}\frac{\sigma^*_{i_{jk}}}{1+\lambda_k\sigma^*_{i_{jk}}}\bigg)^2-\bigg(\E\sum_{j\leq \pi_k}\frac{\sigma^*_{i_{jk}}}{1+\lambda_k\sigma^*_{i_{jk}}}\bigg)^2.
\end{equation}

Recalling that the coordinates of the signal $\sigma^*$ are i.i.d. and averaging with respect to the randomness of the indices $(i_{jk})$ reveals that

\begin{align*}
\E\bigg(\sum_{j\leq \pi_k}\frac{\sigma^*_{i_{jk}}}{1+\lambda_k\sigma^*_{i_{jk}}}\bigg)^2&=\frac{1}{N}\E\sum_{j,j'\leq \pi_k}\frac{1}{(1+\lambda_k\sigma_1^*)^2}+\frac{N^2-N}{N}\E\sum_{j,j'\leq \pi_k}\frac{\sigma_1^*\sigma_2^*}{(1+\lambda_k \sigma_1^*)(1+\lambda_k\sigma_2^*)}\\
&\leq \frac{4\E\pi_k^2}{N}+\E\pi_k^2\Big(\E\frac{\sigma_1^*}{1+\lambda_k\sigma_1^*}\Big)^2,
\end{align*}

where we have used that $\sigma_1^2=1$ and $\lambda_k\leq 1/2$. Similarly,

$$\bigg(\E\sum_{j\leq \pi_k}\frac{\sigma^*_{i_{jk}}}{1+\lambda_k\sigma^*_{i_{jk}}}\bigg)^2=\big(\E\pi_k\big)^2\Big(\E\frac{\sigma_1^*}{1+\lambda_k\sigma_1^*}\Big)^2.$$

Substituting these two bounds into (<ref>), recalling (<ref>) and choosing $N$ large enough yields

$$\Var\big(g(\sigma,\pi_k)\big)\leq \frac{4 \E\pi_k^2}{N}+\Var (\pi_k)\Big(\E\frac{\sigma_1^*}{1+\lambda_k\sigma_1^*}\Big)^2\leq 8s_N.$$

Plugging this into (<ref>) completes the proof.

We follow the proof of Theorem 3.3 in [12]; we will not give full details, and instead encourage the interested reader to consult [12]. The Cauchy-Schwarz inequality and the fact that $\norm{f_n}_{L^\infty}\leq 1$ imply that

\begin{align*}
\big\lvert\E \big\langle f_n\widetilde{\L}_k(\sigma^1)\big\rangle-\E\langle f_n\rangle \E\big\langle \widetilde{\L}_k(\sigma)\big\rangle\big\rvert&\leq \E\big\langle (f_n-\langle f_n\rangle)^2\big\rangle^{1/2}\E\Big\langle\big( \widetilde{\L}_k-\E\langle \widetilde{\L}_k\rangle\big)^2\Big\rangle^{1/2}\\
&\leq \E\Big\langle\big( \widetilde{\L}_k-\E\langle \widetilde{\L}_k\rangle\big)^2\Big\rangle^{1/2}.
\end{align*}

By <Ref> it is therefore sufficient to prove that

\begin{equation}
\E\big\langle f_n\widetilde{\L}_k(\sigma^1)\big\rangle=\E \frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle}{\langle e^{\theta_{ik}}\rangle^n} \quad \text{and} \quad \E\big\langle\widetilde{\L}_k(\sigma)\big\rangle=\E\frac{\langle d_{ik}e^{\theta_{ik}}\rangle}{\langle e^{\theta_{ik}}\rangle}.\label{eqn: SBMA Franz de Sanctis goal}
\end{equation}

Since $\pi_k$ is independent of all other sources of randomness, taking the expectation with respect to this random variable first shows that

\begin{equation}\label{eqn: SBMA Franz de Sanctis key}
\E\big\langle f_n\widetilde{\L}_k(\sigma^1)\big\rangle=\sum_{r\geq 1}\frac{s_N^{r-1}}{(r-1)!}e^{-s_N}\E\big\langle f_nD_{1k}^1\big\rangle_{\pi_k=r},
\end{equation}

where $D_{1k}^1=\sigma_{i_{1k}}^1e_{1k}/(1+\lambda_k\sigma^*_{i_{1k}})^2$.
To simplify this expression, we will isolate the first replica $\sigma^1$ appearing in each of the averages. It will be convenient to introduce the quantities

$$\Theta_{jk}^\ell=\log(1+\lambda_k\sigma_{i_{jk}}^\ell)-\frac{\lambda_ke_{jk}\sigma_{i_{jk}}^\ell}{1+\lambda_k\sigma^*_{i_{jk}}} \quad \text{and} \quad \HH_k^{r-1}(\sigma^\ell)=\sum_{2\leq j\leq r}\Theta_{jk}^\ell$$

as well as the partially perturbed Hamiltonian

\begin{equation}\label{eqn: SBM Franz de Sanctis partially perturbed Hamiltonian}
H_N'(\sigma)=H_N(\sigma)+H_N^{\mathrm{gauss}}(\sigma)+\sum_{\substack{1\leq k'\leq K_+\\k'\neq k}}\HH_{k'},
\end{equation}

where $\HH_k$ is defined in (<ref>). Denoting by $\langle \cdot\rangle_{\pi_k=r}'$ the Gibbs measure corresponding to the Hamiltonian $H_N'(\sigma)+\HH_k^{r-1}(\sigma^\ell)$, we have

\begin{equation}\label{eqn: SBMA Franz de Sanctis distributional identity}
\E\big\langle f_nD_{1k}^1\big\rangle_{\pi_k=r}=\E\E_{i_{1k}}\E_{e_{1k}}\frac{ \langle f_nD_{1k}^1e^{\sum_{\ell\leq n}\Theta^\ell_{1k}}\rangle'_{\pi_k=r}}{(\langle e^{\Theta_{1k}}\rangle'_{\pi_k=r})^n}
\end{equation}

for each $r\geq 1$.
Since the uniform random variable $i_{1k}$ and the exponential random variable $e_{1k}$ no longer appear in the Gibbs average $\langle \cdot \rangle_{\pi_k=r}'$, we may replace them by a uniform random variable $i\in \{1,\ldots,N\}$ and an exponential random variable $e\sim \Exp(1)$ independent of all other sources of randomness as in the statement of the theorem. To emphasize this change, we also replace $D_{1k}^1$ and $\Theta_{1k}^\ell$ by $d_{ik}^1=\sigma_i^1e/(1+\lambda_k\sigma_i^*)^2$ and $\theta_{ik}^\ell=\log(1+\lambda_k\sigma_i^\ell)-\lambda_k\sigma_i^\ell e/(1+\lambda_k\sigma_i^*)$, respectively. Notice that this matches the definitions in (<ref>). In this new notation (<ref>) reads

$$\E\big\langle f_nD_{1k}^1\big\rangle_{\pi_k=r}=\E\frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle'_{\pi_k=r}}{(\langle e^{\theta_{ik}}\rangle'_{\pi_k=r})^n}.$$

Substituting this into (<ref>) and making the change of variables $m=r-1$ reveals that

$$\E\big\langle f_n\widetilde{\L}_k(\sigma^1)\big\rangle=\sum_{m\geq 0}\frac{s_N^m}{m!}e^{-s_N}\E\frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle'_{\pi_k=m+1}}{(\langle e^{\theta_{ik}}\rangle'_{\pi_k=m+1})^n}.$$

Notice that whenever $\pi_k=m+1$, the Hamiltonian defining the Gibbs average $\smash{\langle \cdot\rangle'_{\pi_k=m+1}}$ is given by $\smash{H_N'(\sigma)+\HH_k^{m}(\sigma)}$. This Hamiltonian has the same distribution as the Hamiltonian in (<ref>) defining the original Gibbs average $\langle \cdot\rangle_{\pi_k=m}$. It follows that

$$\E\big\langle f_n\widetilde{\L}_k(\sigma^1)\big\rangle=\sum_{m\geq 0}\frac{s_N^m}{m!}e^{-s_N}\E\frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle_{\pi_k=m}}{(\langle e^{\theta_{ik}}\rangle_{\pi_k=m})^n}=\E\frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle}{\langle e^{\theta_{ik}}\rangle^n}.$$

This is the first equality in (<ref>). The second equality in (<ref>) is obtained by taking $n=1$ and $f_1=1$ in the first equality. This completes the proof.

Applying this result along a sequence of perturbation parameters $\smash{(\lambda^N)}$ satisfying (<ref>) reveals that

\begin{equation}\label{eqn: SBMA overlap and Franz de Sanctis in limit 0}
\lim_{N\to \infty}\Big\lvert \E \frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle_N}{\langle e^{\theta_{ik}}\rangle_N^n}-\E\langle f_n\rangle_N \E\frac{\langle d_{ik}e^{\theta_{ik}}\rangle_N}{\langle e^{\theta_{ik}}\rangle_N}\Big\rvert=0
\end{equation}

for any $1\leq k\leq K_+$ and any function $f_n$ of finitely many spins on $n$ replicas and of the signal $\sigma^*$ with $\norm{f_n}_{L^\infty}\leq 1$. Observing that the denominators $\langle e^{\theta_{ik}}\rangle_N$ do not depend on the signal $\sigma^*$, it is possible to use the Nishimori identity (<ref>) to replace all occurrences of the signal $\sigma^*$ in (<ref>) by another replica. For convenience of notation we will denote this new replica by $\sigma^\diamond$ to distinguish it from the signal $\sigma^*$ and at the same time not occupy any specific index. The equations in (<ref>) now read

\begin{equation}\label{eqn: SBMA overlap and Franz de Sanctis in limit 1}
\lim_{N\to \infty}\Big\lvert \E\E_\diamond \frac{\langle f_nd_{ik}^1e^{\sum_{\ell\leq n}\theta_{ik}^\ell}\rangle_N}{\langle e^{\theta_{ik}}\rangle_N^n}-\E\E_\diamond\langle f_n\rangle_N \E\E_\diamond\frac{\langle d_{ik}e^{\theta_{ik}}\rangle_N}{\langle e^{\theta_{ik}}\rangle_N}\Big\rvert=0,
\end{equation}

where $\E_\diamond$ denotes the Gibbs average with respect to the replica $\sigma^\diamond$ only, the bracket $\langle \cdot\rangle_N$ denotes the Gibbs average with respect to all other standard replicas, the function $f_n$ depends on finitely many spins on the $n$ standard replicas and on $\sigma^\diamond$, and, with some abuse of notation,

\begin{equation}
y_{ik}=\frac{e}{1+\lambda_k\sigma_i^\diamond}, \quad \theta_{ik}^\ell=\log(1+\lambda_k\sigma_i^\ell)-\lambda_ky_{ik}\sigma_i^\ell,\quad \text{and} \quad d_{ik}^\ell=\frac{y_{ik}\sigma_i^\ell}{1+\lambda_k\sigma_i^\diamond}
\end{equation}

with $\lambda_k=\lambda_k^N$ for $1\leq k\leq K_+$. We now simplify (<ref>) for functions $f_n$ that do not depend on the spin coordinate indexed by $1$.  Introduce the collection of functions

\begin{align}
\F_n=\big\{\text{f}&\text{unctions } f_n \text{ of }\text{ finitely many spins } \sigma_i^\ell, \sigma_i^\diamond  \text{ with } 2\leq i\leq N \notag\\
& \text{ of the } n \text{ standard replicas }  (\sigma^\ell)_{\ell\leq n} \text{ and the special replica }\sigma^\diamond \text{ with } \norm{f_n}_{L^\infty}\leq 1\big\}
\end{align}

and the quantities

\begin{equation}\label{eqn: SBMA Franz de Sanctis asymptotic variables}
y_{k}=\frac{e}{1+\lambda_k\sigma_1^\diamond}, \quad \theta_{k}^\ell=\log(1+\lambda_k\sigma_1^\ell)-\lambda_ky_{k}\sigma_1^\ell,\quad \text{and} \quad d_{k}^\ell=\frac{y_{k}\sigma_1^\ell}{1+\lambda_k\sigma_1^\diamond}.
\end{equation}

For functions $f_n\in \F_n$, the symmetry between sites (<ref>) and the fact that $i\in \{2,\ldots,N\}$ with overwhelming probability in the limit, allow us to replace the uniform random index $i\in \{1,\ldots,N\}$ by the index $1$. The Franz de-Sanctis identities together with assumption (<ref>) therefore have the following important implication.

If (<ref>) holds, then for every $1\leq k\leq K_+$ and all functions $f_n\in \F_n$,

\begin{equation}\label{eqn: SBMA overlap and Franz de Sanctis in limit 2}
\lim_{N\to \infty}\Big\lvert \E\E_\diamond \frac{\langle f_nd_{k}^1e^{\sum_{\ell\leq n}\theta_{k}^\ell}\rangle_N}{\langle e^{\theta_{k}}\rangle_N^n}-\E\E_\diamond\langle f_n\rangle_N \E\E_\diamond\frac{\langle d_{k}e^{\theta_{k}}\rangle_N}{\langle e^{\theta_{k}}\rangle_N}\Big\rvert=0.
\end{equation}

§.§ Finitary multi-overlap concentration

The finitary version of the multi-overlap concentration result in [12] will be uniform over an appropriate class of random probability measures which we now describe. For each integer $N\geq 1$ consider the set of random probability measures on $\Sigma_N$ thought of as a subset of $\{-1,0,1\}^\N$,

\begin{equation}
\G_N=\Big\{G\mid G \text{ is a random probability measure on } \Sigma_N\times \{0\}^\N\Big\},
\end{equation}

and say that a measure $G\in \G_N$ satisfies symmetry between sites if, for any sequence of i.i.d. replicas $(\sigma^\ell)_{\ell\geq 1}$ sampled from $G$,

\begin{equation}\label{eqn: SBMA generic symmetry between sites}
\big(\sigma_i^\ell)_{i,\ell\geq 1}\stackrel{d}{=}\big(\sigma_{\rho_1(i)}^{\rho_2(\ell)}\big)_{i,\ell\geq 1}
\end{equation}

for any permutation $\rho_1$ on the finite set $\{1,\ldots,N\}$ and any permutation $\rho_2$ of finitely many indices. Denote by $\G_N^s$ the subset of $\G_N$ which satisfies symmetry between sites. Notice that each Gibbs measure $G_N$ defined by (<ref>) can be thought of as an element of $\G_N$ by setting $\sigma_i=0$ when $i>N$ for any replica $\sigma\in \Sigma_N$ sampled from $G_N$. In this way, the symmetry between sites in (<ref>) and (<ref>) coincide, so in fact $G_N\in \G_N^s$. This identification also suggests that the appropriate notion of the multi-overlap (<ref>) for a random probability measure $G\in \G_N$ should be

\begin{equation}\label{eqn: SBMA generic multi-overlaps 2}
R_{\ell_1,\ldots,\ell_n}=\frac{1}{N}\sum_{i\leq N}\sigma_i^{\ell_1}\cdots \sigma_i^{\ell_n},
\end{equation}

where $(\sigma^\ell)$ denotes a sequence of i.i.d. replicas sampled from the Gibbs measure $G$. Denoting by $\langle \cdot \rangle_G$ the average with respect to the random probability measure $G$ we may now sate the main result of this appendix.

For every $\epsilon>0$ there exists $\delta>0$ such that the following holds. Let $N\geq \lfloor\delta^{-1}\rfloor$ and $G\in \G_N$ be a random probability measure such that for all $1\leq k\leq K_+=\lfloor \delta^{-1}\rfloor$ and any function $f_n\in \F_n$,

\begin{align}\label{eqn: SBMA finitray MOC assumptions}
\E\big\langle (R_1-&\E\langle R_1\rangle_G)^2\big\rangle_G \leq \delta, \qquad\qquad  \E\big\langle (R_{1,2}-\E\langle R_{1,2}\rangle_G )^2\big\rangle_G\leq \delta,\\
&\Big\lvert \E\E_\diamond \frac{\langle f_nd_{k}^1e^{\sum_{\ell\leq n}\theta_{k}^\ell}\rangle_G}{\langle e^{\theta_{k}}\rangle^n_G}-\E\E_\diamond\langle f_n\rangle_G \E\E_\diamond\frac{\langle d_{k}e^{\theta_{k}}\rangle_G}{\langle e^{\theta_{k}}\rangle_G}\Big\rvert\leq \delta.
\end{align}

Then for any $1\leq m\leq \lfloor \epsilon^{-1}\rfloor$, we have

\begin{equation}
\E\big\langle (R_{1,\ldots,m}-\E\langle R_{1,\ldots,m}\rangle_G)^2\big\rangle_G\leq \epsilon.
\end{equation}

The proof proceeds by contradiction and closely follows Section 3.5 and Section 3.7 of [12]. Suppose there exists some $\epsilon>0$ such that no matter the choice of $\delta>0$, it is always possible to find some integer $N=N(\delta)\geq \lfloor \delta^{-1}\rfloor$ and some random probability measure $G=G(\delta)\in \G_N$ with

\begin{align}
\E\big\langle (R_1-&\E\langle R_1\rangle_G)^2\big\rangle_G \leq \delta, \qquad\qquad  \E\big\langle (R_{1,2}-\E\langle R_{1,2}\rangle_G )^2\big\rangle_G\leq \delta,\label{eqn: SBMA multi-overlap concentration assumption 1}\\
&\Big\lvert \E\E_\diamond \frac{\langle f_nd_{k}^1e^{\sum_{\ell\leq n}\theta_{k}^\ell}\rangle_G}{\langle e^{\theta_{k}}\rangle^n_G}-\E\E_\diamond\langle f_n\rangle_G \E\E_\diamond\frac{\langle d_{k}e^{\theta_{k}}\rangle_G}{\langle e^{\theta_{k}}\rangle_G}\Big\rvert\leq \delta\label{eqn: SBMA multi-overlap concentration assumption 2}
\end{align}

for any $1\leq k\leq K_+=\lfloor \delta^{-1}\rfloor$ and any $f_n\in \F_n$ for which there exists some $1\leq m=m(\delta) \leq \lfloor \epsilon ^{-1}\rfloor$ with

\begin{equation}\label{eqn: SBMA multi-overlap concentration absurd}
\E\big\langle (R_{1,\ldots,m}-\E\langle R_{1,\ldots,m}\rangle_G)^2\big\rangle_G > \epsilon.
\end{equation}

Applying the Prokhorov theorem on the compact metric space $\{-1,0,+1\}^{\N^2}$ and noticing that there are only finitely many choices for $m=m(\delta)$, it is possible to find a subsequence with $\delta\to 0$ along which the distribution of the array $\smash{\big(\sigma_i^\ell\big)_{i,\ell\geq 1}}$ under the averaged Gibbs measure $\smash{\E\langle \cdot \rangle_{G(\delta)}}$ converges in the sense of finite dimensional distributions and along which (<ref>), (<ref>) and (<ref>) hold for every $k\geq 1$ and a fixed $1\leq m\leq \lfloor \epsilon^{-1}\rfloor$. Since $\smash{N(\delta)\to \infty}$ and $\smash{G(\delta)\in \G_N}$, in the limit, the distribution of spins will be a measure on $\{-1,+1\}^{\N^2}$ which will inherit the symmetry between sites (<ref>). By the Aldous-Hoover representation (see Theorem 1.4 in [50]), this symmetry implies the existence of some function $\sigma:[0,1]^4\to \{-1,+1\}$ with

\begin{equation}\label{eqn: SBMA Aldous-Hoover}
\big(\sigma_i^\ell)_{i,\ell\geq 1}\stackrel{d}{=}\big(\sigma(w,u_\ell,v_i,x_{i,\ell})\big)_{i,\ell\geq 1},
\end{equation}

where $w$, $(u_\ell)$, $(v_i)$ and $(x_{i,\ell})$ are i.i.d. uniform random variables on $[0,1]$. Since $\sigma$ takes values in $\{-1,+1\}$, the distribution of the array $(\sigma_i^\ell)$ is encoded by the function

\begin{equation}
\bar{\sigma}(w,u,v)=\E_{x_{i,\ell}}\sigma(w,u,v,x_{i,\ell})=\int_0^1 \sigma(w,u,v,x)\ud x.
\end{equation}

Indeed, the last coordinate $x_{i,\ell}$ is a dummy variable that
corresponds to flipping a biased coin to generate a Bernoulli random variable with expected value $\bar{\sigma}(w,u,v)$. To clarify this further, let $\ud u$ and $\ud v$ denote Lebesgue measure on $[0,1]$, and define the random probability measure

\begin{equation}
G=G_w=\ud u\circ \big(u\mapsto \bar{\sigma}(w,u,\cdot)\big)^{-1}
\end{equation}

on the space of functions of $v\in [0,1]$,

\begin{equation}\label{eqn: SBMA Hilbert space}
H=L^2\big([0,1],\ud v\big)\cap \big\{\norm{\bar{\sigma}}_{L^\infty}\leq 1\big\},
\end{equation}

equipped with the topology of $L^2([0,1],\ud v)$. As described in Section 2 of [55], the whole process of generating spins can be broken into the following steps:

* generate the asymptotic Gibbs measure $G=G_w$ using the uniform random variable $w$;

* consider an i.i.d. sequence $\bar{\sigma}^\ell=\bar{\sigma}(w,u_\ell,\cdot)$ of replicas from $G$, which are functions in $H$;

* plug in i.i.d. uniform random variables $(v_i)_{i\geq 1}$ to obtain the array $\bar{\sigma}^\ell(v_i)=\bar{\sigma}(w,u_\ell,v_i)$;

* finally, use the random variables $(x_{i,\ell})$ to generate $(\sigma_i^\ell)$ by flipping a coin with expected value $\bar{\sigma}^\ell(v_i)$,

\begin{equation}
\sigma_i^\ell=2\1\Big\{x_{i,\ell}\leq \frac{1+\bar{\sigma}^\ell(v_i)}{2}\Big\}-1.
\end{equation}

This suggests that the asymptotic Gibbs average should be the average with respect to the random variables $(u_\ell)$ and $(x_{i,\ell})$ that depend on the replica indices, which we will denote by

\begin{equation}\label{eqn: SBMA asymptotic Gibbs measure}
\langle\cdot \rangle=\E_{(u_\ell),(x_{i,\ell})}.
\end{equation}

We can also expect the asymptotic multi-overlap to be given by

\begin{equation}\label{eqn: SBMA asymptotic multi-overlaps}
R^\infty_{\ell_1,\ldots,\ell_n}(w,(u_{\ell_j})_{j\leq n})=\E_v\prod_{j\leq n}\bar{\sigma}(w,u_{\ell_j},v)=\int_0^1 \prod_{j\leq n}\bar{\sigma}(w,u_{\ell_j},v)\ud v.
\end{equation}

This intuition is confirmed by the two following results adapted from Section 3.5 and the Appendix in [12].

For any finite set of $n$ replicas and every collection $\{\CC_\ell\}_{\ell\leq n}$ of finite indices,

\begin{equation}
\lim_{\delta \to 0}\E\prod_{\ell\leq n}\Big\langle \prod_{i\in \CC_\ell}\sigma_i^\ell\Big\rangle_{G(\delta)}=\E_{w,(v_i)}\prod_{\ell\leq n}\Big\langle \prod_{i\in \CC_\ell} \sigma_i^\ell\Big\rangle.
\end{equation}

Let $\CC=\{(i,\ell)\mid \ell \leq n \text{ and } i\in \CC_\ell\}$. By definition of weak convergence in the sense of finite-dimensional marginal distributions,

$$\lim_{\delta \to 0}\E\prod_{\ell\leq n}\Big\langle \prod_{i\in \CC_\ell}\sigma_i^\ell\Big\rangle_{G(\delta)}=\lim_{\delta \to 0}\E\Big\langle\prod_{(i,\ell)\in \CC}\sigma_i^\ell\Big\rangle_{G(\delta)}=\E \prod_{(i,\ell)\in \CC}\sigma(w,u_\ell,v_i,x_{i,\ell}).$$

Recalling the notation (<ref>),

$$\E \prod_{(i,\ell)\in \CC}\sigma(w,u_\ell,v_i,x_{i,\ell})=\E_{w,(v_i)}\prod_{\ell\leq n}\E_{(u_\ell)}\prod_{i\in \CC_\ell}\E_{(x_{i,\ell})}\sigma(w,u_\ell,v_i,x_{i,\ell})=\E_{w,(v_i)}\prod_{\ell\leq n}\Big\langle \prod_{i\in \CC_\ell} \sigma_i^\ell\Big\rangle.$$

as required.

For any collection of sets $\{\L_i\}_{i\geq 1}$ only finitely many of which are non-empty,

\begin{equation}
\lim_{\delta\to 0}\E\Big\langle\prod_{i\geq 1} R_{\L_i}\Big\rangle_{G(\delta)}=\E_w\Big\langle \prod_{i\geq 1}R_{\L_i}^\infty\Big\rangle.
\end{equation}

Write $N\geq \lfloor \delta^{-1}\rfloor$ for the unique integer with $G(\delta)\in \G_{N}$ and suppose without loss of generality that the sets $\L_i$ for $i\leq j$ are non-empty while the sets $\L_i$ for $i>j$ are empty. From (<ref>),

$$\E\Big\langle\prod_{i\geq 1} R_{\L_i}\Big\rangle_{G(\delta)}=\frac{1}{N^j}\sum_{i_1,\ldots,i_j}\E\Big\langle \prod_{\ell_1\in \L_1}\cdots \prod_{\ell_j\in \L_j}\sigma_{i_1}^{\ell_1}\cdots \sigma_{i_j}^{\ell_j}\Big\rangle_{G(\delta)}.$$

The number of terms in this sum for which at least two of the indices $i_1,\ldots,i_j$ are equal is of order $N^{j-1}$ and is therefore negligible in the limit. Moreover, the symmetry between sites (<ref>) implies that whenever $i_1,\ldots,i_j$ are all distinct

$$\E\Big\langle \prod_{\ell_1\in \L_1}\cdots \prod_{\ell_j\in \L_j}\sigma_{i_1}^{\ell_1},\cdots \sigma_{i_j}^{\ell_j}\Big\rangle_{G(\delta)}=\E\Big\langle \prod_{\ell_1\in \L_1}\cdots \prod_{\ell_j\in \L_j}\sigma_{1}^{\ell_1},\cdots \sigma_{j}^{\ell_j}\Big\rangle_{G(\delta)}=\E\Big\langle \prod_{i\geq 1}\prod_{\ell\in \L_i}\sigma^\ell_i\Big\rangle_{G(\delta)}.$$

(This seems to fix a small typo in the second-to-last display of the Appendix in [12]). Combining these two observations shows that

$$\lim_{\delta \to 0}\E\Big\langle\prod_{i\geq 1} R_{\L_i}\Big\rangle_{G(\delta)}=\E_{w,(u_\ell)}\prod_{i\geq 1}\E_{v_i}\prod_{\ell\in \L_i}\E_{x_{i,\ell}}\sigma(w,u_\ell,v_i,x_{i,\ell})=\E_{w,(u_\ell)}\prod_{i\geq 1}R_{\L_i}^\infty.$$

This completes the proof.

In the notation of (<ref>) and (<ref>), the asymptotic version of (<ref>) and (<ref>) therefore reads

\begin{align}
\E \langle (R_1&^\infty)^2\rangle=\big(\E \langle R_1^\infty\rangle\big)^2, \qquad \E \langle (R_{1,2}^\infty)^2\rangle=\big(\E \langle R_{1,2}^\infty\rangle\big)^2 \label{eqn: SBMA asymtotic overlap and Franz de Sanctis 1}\\
&\E\E_\diamond \frac{\langle f_nd_{k}^1e^{\sum_{\ell\leq n}\theta_{k}^\ell}\rangle}{\langle e^{\theta_{k}}\rangle^n}=\E\E_\diamond\langle f_n\rangle \E\E_\diamond\frac{\langle d_{k}e^{\theta_{k}}\rangle}{\langle e^{\theta_{k}}\rangle}\label{eqn: SBMA asymtotic overlap and Franz de Sanctis 2}
\end{align}

for any $k\geq 1$ and any function $f_n\in \F_n$, while the asymptotic version of (<ref>) becomes

\begin{equation}\label{eqn: SBMA multi-overlap concentration asymptotic absurd}
\E\big\langle (R_{1,\ldots,m}^\infty-\E\langle R_{1,\ldots,m}^\infty \rangle)^2\big\rangle > \epsilon
\end{equation}

for some $1\leq m\leq \lfloor \epsilon^{-1}\rfloor$. We now derive the two most important consequences of the identities in (<ref>) and (<ref>) that will allow us to establish multi-overlap concentration. On the one hand, the concentration of the overlap $\E\langle (R_{1,2}^\infty)^2\rangle=(\E\langle R_{1,2}^\infty\rangle)^2$ implies that the system lies in a “thermal pure state” and that the function $\bar{\sigma}(w,u,v)$ is therefore almost surely independent of $u$. The proof of this fact is taken from Theorem 3.1 in [52].

If $\E\langle (R_{1,2}^\infty)^2\rangle=(\E\langle R_{1,2}^\infty\rangle)^2$, then for almost all $u,v,w\in [0,1]$,

\begin{equation}
\bar{\sigma}(w,u,v)=\E_u\bar{\sigma}(w,u,v).
\end{equation}

Denote by $\cdot$ the inner product on the Hilbert space (<ref>),

$$\bar{\sigma}^1\cdot \bar{\sigma}^2=\E_{v}\bar{\sigma}^1(w,u_1,v)\bar{\sigma}^2(w,u_2,v)=R_{1,2}^\infty,$$

and observe that

\begin{align*}
0&=\E_{w,(u_\ell)} \big(R_{1,2}^\infty\big)^2-\E_{w,(u_\ell)} R_{1,2}^\infty R_{3,4}^\infty=\E_w\Var_{(u_\ell)}\bar{\sigma}^1\cdot \bar{\sigma}^2.
\end{align*}

It follows that for almost all $w\in [0,1]$, the inner product $\bar{\sigma}^1\cdot \bar{\sigma}^2$ of any two replicas sampled from the Gibbs measure $G_w$ is constant almost surely. In other words, the measure $G_w$ is concentrated on a single function which may depend on $w$. This completes the proof.

The second identity in (<ref>) therefore implies that, instead of the equality in distribution (<ref>), we actually have

\begin{equation}\label{eqn: SBMA Aldous-Hoover pure state}
\big(\sigma_i^\ell\big)_{i,\ell\geq 1}\stackrel{d}{=}\big(\sigma(w,v_i,x_{i,\ell})\big)_{i,\ell\geq 1}
\end{equation}

for any function $\sigma:[0,1]^3\to \{-1,+1\}$ such that $\int_0^1 \sigma(w,v,x)\ud x=\bar{\sigma}(w,v)$. In particular, the Gibbs average (<ref>) simplifies to

\begin{equation}\label{eqn: SBMA asymptotic Gibbs measure pure state}
\langle\cdot \rangle=\E_{(x_{i,\ell})}
\end{equation}

while the multi-overlap (<ref>) becomes

\begin{equation}
R_{\ell_1,\ldots,\ell_n}^\infty(w)=\E_v\prod_{j\leq n}\bar{\sigma}(w,v)=\E_v\big(\bar{\sigma}(w,v)^n\big)=\int_0^1 \bar{\sigma}(w,v)^n\ud v.
\end{equation}

On the other hand, the asymptotic Franz-de Sanctis identities in (<ref>) imply the following decoupling property of the asymptotic Gibbs measure. This is lemma 3.5 in [12].

Fix $\lambda\in \{\lambda_k\mid k\geq 1\}$. If $e_1,e_2$ are independent $\Exp(1)$ random variables and, for $j=1,2$,

\begin{equation}
y_j=\frac{e_j}{1+\lambda \sigma_j^\diamond},\quad \theta_j=\log(1+\lambda \sigma_j)-\lambda y_j\sigma_j,\quad\text{and}\quad d_j=\frac{y_j\sigma_j}{1+\lambda \sigma_j^\diamond},
\end{equation}

\begin{equation}\label{eqn: SBMA decoupling lemma}
\E\E_\diamond \frac{\langle d_1e^{\theta_1}d_2e^{\theta_2}\rangle}{\langle e^{\theta_1}e^{\theta_2}\rangle}=\E\E_\diamond \frac{\langle d_1e^{\theta_1}\rangle}{\langle e^{\theta_1}\rangle}\E\E_\diamond \frac{\langle d_2e^{\theta_2}\rangle}{\langle e^{\theta_2}\rangle}.
\end{equation}

The idea is to combine a technical truncation argument with the Weierstrass approximation theorem and an application of (<ref>) to the function $f_{n+1}=d_2^1\exp \sum_{\ell\leq n+1}\theta_2^\ell$; we encourage the interested reader to consult [12].

We are finally in a position to contradict (<ref>) and prove <Ref>. The calculations are very similar in spirit to those in [53, 55], and are taken from Theorem 2.2 in [12].

We follow the proof of Theorem 2.2 in [12]; we will not give full details, and instead encourage the interested reader to consult [12]. Recall from (<ref>) that $\smash{\sigma_j=\sigma(w,v_j,x_j)}$ and $\smash{\sigma_j^\diamond=\sigma(w,v_j,x_j^\diamond)}$. Since all random variables indexed by $j=1,2$ are independent, if we denote by $\smash{\E_{|w}=\E_{(e_j),(v_j),x_j,x_j^\diamond}}$ the conditional expectation given $w$ and we introduce the random variable

$$Y(w)=\E_{|w}\frac{\langle d_1e^{\theta_1}\rangle}{\langle e^{\theta_1}\rangle}=\E_{|w}\frac{y_1}{1+\lambda\sigma_1^\diamond}\frac{\langle \sigma_1e^{\theta_1}\rangle}{\langle e^{\theta_1}\rangle},$$

which depends implicitly on $\lambda$ through $y_1$ and $\theta_1$, then (<ref>) reads

$$\E \Big(\E_{|w}\frac{\langle d_1e^{\theta_1}\rangle}{\langle e^{\theta_1}\rangle}\Big)\Big(\E_{|w}\frac{\langle d_2e^{\theta_2}\rangle}{\langle e^{\theta_2}\rangle}\Big)-\Big(\E \frac{\langle d_1e^{\theta_1}\rangle}{\langle e^{\theta_1}\rangle}\Big)\Big(\E\frac{\langle d_2e^{\theta_2}\rangle}{\langle e^{\theta_2}\rangle}\Big)=\E\Var_{|w}Y(w)=0.$$

This means that $Y=\E Y$ almost surely. To exploit this fact, through a slight abuse of notation, write $\sigma$ for $\sigma_1$ and observe that conditionally on $\sigma_1^\diamond$,

$$Y(w)=\E_{|w}\int_0^\infty \langle e^{-\lambda \sigma y}\rangle \frac{\langle \sigma (1+\lambda \sigma)e^{-\lambda y\sigma}\rangle}{\langle (1+\lambda \sigma)e^{-\lambda y \sigma}\rangle}ye^{-y}\ud y.$$

Using the analyticity of both

$$g_w:\gamma\mapsto g_w(\gamma)=\E_{|w}\int_0^\infty \langle e^{-\gamma \sigma y}\rangle\frac{\langle \sigma(1+\gamma \sigma)e^{-\gamma y \sigma}\rangle}{\langle (1+\gamma \sigma)e^{-\gamma y \sigma}\rangle}ye^{-y}\ud y$$

for a fixed $w$ as well as its $w$-expectation $\E g_w(\gamma)$, it is possible to deduce that $Y(w)=\E Y$ for all $\lambda$ in a small neighbourhood of the origin. With this in mind, introduce the random variable

$$Z(w)=\E_{|w}\int_0^\infty \langle \sigma(1+\lambda \sigma)e^{-\lambda \sigma}\rangle ye^{-y}\ud y$$

which is deterministic by the first identity in (<ref>). This implies that the random variable

$$X(w)=\frac{Z(w)-Y(w)}{\lambda}=\E_{|w}\int_0^\infty \langle \sigma e^{-\lambda y\sigma}\rangle\frac{\langle \sigma (1+\lambda \sigma)e^{-\lambda y\sigma}\rangle}{\langle (1+\lambda \sigma)e^{-\lambda y\sigma}\rangle}ye^{-y}\ud y$$

is deterministic for all $\lambda$ in a small neighbourhood of the origin. In particular, all its $\lambda$-derivatives are also independent of $w$. We will now deduce from this observation that all multi-overlaps concentrate. Given $n\geq 1$, applying $\frac{\partial^n}{\partial \lambda^n}$ to the denominator in the expression inside the integral defining $X$ and evaluating at $\lambda=0$ yields the term

$$n!R_{1,\ldots,n+2}\E e(e-1)^n,$$

where $e$ is an $\Exp(1)$ random variable. Since $\E e(e-1)^n=\E(e-1)^{n+1}+\E(e-1)^n>0$ for all $n\geq 1$, the term obtained by applying all derivatives to the denominator in the expression inside the integral defining $X$ produces the multi-overlap $\smash{R_{1,\ldots,n+2}^\infty}$. If along the way we apply a derivative of $\lambda$ to any factor other than the denominator, this will not create a new replica, so all those terms will produce a linear combination of multi-overlaps on strictly less than $n+2$ replicas which by induction we assume to be independent of $w$. This establishes the concentration of all multi-overlaps and contradicts (<ref>) thus completing the proof.

[1]
E. Abbe.
Community Detection and Stochastic Block Models.
Foundations and trends in communications and information theory. Now
Publishers, 2018.

[2]
E. Abbe, A. S. Bandeira, and G. Hall.
Exact recovery in the stochastic block model.
IEEE Transactions on Information Theory, 62(1):471–487, 2016.

[3]
E. Abbe, E. Cornacchia, Y. Gu, and Y. Polyanskiy.
Stochastic block model entropy and broadcasting on trees with survey.
In Proceedings of Thirty Fourth Conference on Learning Theory,
volume 134, pages 1–25. PMLR, 2021.

[4]
E. Abbe and A. Montanari.
Conditional random fields, planted constraint satisfaction, and
entropy concentration.
Theory of Computing, 11:413–443, 12 2015.

[5]
E. Abbe and C. Sandon.
Detection in the stochastic block model with multiple clusters: proof
of the achievability conjectures, acyclic BP, and the
information-computation gap.
arXiv e-prints, 2015.

[6]
E. Abbe and C. Sandon.
Recovering communities in the general stochastic block model without
knowing the parameters.
In Advances in Neural Information Processing Systems,
volume 28. Curran Associates, Inc., 2015.

[7]
A. Adhikari and C. Brennecke.
Free energy of the quantum Sherrington–Kirkpatrick spin-glass
model with transverse field.
J. Math. Phys., 61(083302), 2020.

[8]
E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing.
Mixed membership stochastic blockmodels.
Journal of Machine Learning Research, 9(65):1981–2014, 2008.

[9]
B. Ball, B. Karrer, and M. E. J. Newman.
Efficient and principled method for detecting communities in
Physical Review E, 84(3), 2011.

[10]
J. Barbier, C. L. Chan, and N. Macris.
Mutual information for the stochastic block model by the adaptive
interpolation method.
In 2019 IEEE International Symposium on Information Theory,
page 405–409. IEEE Press, 2019.

[11]
J. Barbier and D. Panchenko.
Free energy in the stochastic block model in sparse regime:
Disassortative case.
Personal communication.

[12]
J. Barbier and D. Panchenko.
Strong replica symmetry in high-dimensional optimal Bayesian
Communications in Mathematical Physics, 393:1199–1239, 2022.

[13]
G. Ben Arous and A. Jagannath.
Spectral gap estimates in mean field spin glasses.
Communications in Mathematical Physics, 361(1):1–52, 2018.

[14]
B. Bollobás, S. Janson, and O. Riordan.
The phase transition in inhomogeneous random graphs.
Random Struct. Algorithms, 31(1):3–122, 2007.

[15]
R. B. Boppana.
Eigenvalues and graph bisection: An average-case analysis.
In 28th Annual Symposium on Foundations of Computer Science,
pages 280–285, 1987.

[16]
S. Boucheron, G. Lugosi, and P. Massart.
Concentration inequalities.
Oxford University Press, Oxford, 2013.

[17]
T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser.
Graph bisection algorithms with good average case behavior.
Combinatorica, 7(2):171–191, 1987.

[18]
I. Cabreros, E. Abbe, and A. Tsirigos.
Detecting community structures in Hi-C genomic data.
In Conference on Information Science and Systems, pages
584–589, 2016.

[19]
F. Caltagirone, M. Lelarge, and L. Miolane.
Recovering asymmetric communities in the stochastic block model.
IEEE Transactions on Network Science and Engineering,
5(3):237–246, 2018.

[20]
H.-B. Chen, J.-C. Mourrat, and J. Xia.
Statistical inference of finite-rank tensors.
arXiv e-prints, 2022.

[21]
H.-B. Chen and J. Xia.
Hamilton-Jacobi equations from mean-field spin glasses.
arXiv e-prints, 2022.

[22]
H.-B. Chen and J. Xia.
Hamilton-Jacobi equations with monotone nonlinearities on convex
arXiv e-prints, 2022.

[23]
J. Chen and B. Yuan.
Detecting functional modules in the yeast protein-protein interaction
Bioinformatics, 22(18):2283–2290, 2006.

[24]
W.-K. Chen.
Phase transition in the spiked random tensor with rademacher prior.
The Annals of Statistics, 47, 2017.

[25]
A. Coja-Oghlan, F. Krzakala, W. Perkins, and L. Zdeborová.
Information-theoretic thresholds from the cavity method.
Advances in Mathematics, 333:694–795, 2018.

[26]
P. Contucci and E. Mingione.
A multi-scale spin-glass mean-field model.
Communications in Mathematical Physics, 368(3):1323–1344,

[27]
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová.
Asymptotic analysis of the stochastic block model for modular
networks and its algorithmic applications.
Physical Review E, 84:066106, 2011.

[28]
Y. Deshpande, E. Abbe, and A. Montanari.
Asymptotic mutual information for the balanced binary stochastic
block model.
Information and Inference: A Journal of the IMA, 6(2):125–170,

[29]
T. Dominguez.
The ${\ell ^{p}}$-Gaussian-Grothendieck problem with vector spins.
Electronic Journal of Probability, 27:1–46, 2022.

[30]
T. Dominguez and J.-C. Mourrat.
Infinite-dimensional Hamilton-Jacobi equations for statistical
inference on sparse graphs.
arXiv e-prints, 2022.

[31]
M. Dyer and A. Frieze.
The solution of some random np-hard problems in polynomial expected
Journal of Algorithms, 10(4):451–489, 1989.

[32]
S. E. Fienberg, M. M. Meyer, and S. S. Wasserman.
Statistical analysis of multiple sociometric relations.
Journal of the American Statistical Association,
80(389):51–67, 1985.

[33]
P. K. Gopalan and D. M. Blei.
Efficient discovery of overlapping communities in massive networks.
Proc. Natl. Acad. Sci. USA, 110(36):14534–14539, 2013.

[34]
P. W. Holland, K. B. Laskey, and S. Leinhardt.
Stochastic blockmodels: First steps.
Social Networks, 5(2):109–137, 1983.

[35]
A. Jagannath, J. Ko, and S. Sen.
Max $\kappa$-cut and the inhomogeneous Potts spin glass.
The Annals of Applied Probability, 28(3):1536–1572, 2018.

[36]
V. Kanade, E. Mossel, and T. Schramm.
Global and local information in clustering labeled block models.
IEEE Transactions on Information Theory, 62(10):5906–5917,

[37]
J. Kingman.
Poisson Processes.
Oxford Studies in Probability. Clarendon Press, 1992.

[38]
J. Ko.
Free energy of multiple systems of spherical spin glasses with
constrained overlaps.
Electronic Journal of Probability, 25:1–34, 2020.

[39]
M. Lelarge and L. Miolane.
Fundamental limits of symmetric low-rank matrix estimation.
Probability Theory and Related Fields, 173(3):859–929, 2019.

[40]
G. Linden, B. Smith, and J. York.
Amazon.com recommendations: Item-to-item collaborative filtering.
IEEE Internet Comput., 7:76–80, 2003.

[41]
L. Massoulié.
Community detection thresholds and the weak ramanujan property.
In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory
of Computing, page 694–703. Association for Computing Machinery, 2014.

[42]
E. Mossel, J. Neeman, and A. Sly.
Reconstruction and estimation in the planted partition model.
Probab. Theory Related Fields, 162(3-4):431–461, 2015.

[43]
E. Mossel, J. Neeman, and A. Sly.
Belief propagation, robust reconstruction and optimal recovery of
block models.
The Annals of Applied Probability, 26(4):2211–2256, 2016.

[44]
E. Mossel, J. Neeman, and A. Sly.
Consistency thresholds for the planted bisection model.
Electronic Journal of Probability, 21:1–24, 2016.

[45]
E. Mossel, J. Neeman, and A. Sly.
A proof of the block model threshold conjecture.
Combinatorica, 38(3):665–708, 2018.

[46]
E. Mossel and J. Xu.
Local algorithms for block models with side information.
In Proceedings of the 2016 ACM Conference on Innovations in
Theoretical Computer Science, pages 71–80, 2016.

[47]
J.-C. Mourrat.
Free energy upper bound for mean-field vector spin glasses.
arXiv e-prints, 2021.

[48]
J.-C. Mourrat.
Nonconvex interactions in mean-field spin glasses.
Probability and Mathematical Physics, 2(2):61–119, 2021.

[49]
M. E. J. Newman, D. J. Watts, and S. SH.
Random graph models of social networks.
Proc. Natl. Acad. Sci. USA, 99:2566–2572, 2002.

[50]
D. Panchenko.
The Sherrington-Kirkpatrick model.
Springer Monographs in Mathematics. Springer, New York, 2013.

[51]
D. Panchenko.
Spin glass models from the point of view of spin distributions.
The Annals of Probability, 41(3A):1315–1361, 2013.

[52]
D. Panchenko.
On the replica symmetric solution of the K-sat model.
Electronic Journal of Probability, 19(67):1–17, 2014.

[53]
D. Panchenko.
Structure of $1$-RSB asymptotic Gibbs measures in the diluted
$p$-spin models.
Journal of Statistical Physics, 155(1):1–22, 2014.

[54]
D. Panchenko.
The free energy in a multi-species
Sherrington–Kirkpatrick model.
Annals of Probability, 43(6):3494–3513, 2015.

[55]
D. Panchenko.
Structure of finite-RSB asymptotic Gibbs measures in the diluted
spin glass models.
Journal of Statistical Physics, 162(1):1–42, 2015.

[56]
D. Panchenko.
Free energy in the mixed $p$-spin models with vector spins.
Annals of Probability, 46:865–896, 2018.

[57]
D. Panchenko.
Free energy in the potts spin glass.
Annals of Probability, 46:829–864, 2018.

[58]
D. Panchenko.
Lecture notes on probability theory.

[59]
J. Shi and J. Malik.
Normalized cuts and image segmentation.
IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888–905, 2000.

[60]
T. Sørlie, C. M. Perou, et al.
Gene expression patterns of breast carcinomas distinguish tumor
subclasses with clinical implications.
Proc. Natl. Acad. Sci. USA, 98(19):10869–10874, 2001.

[61]
Y. J. Wang and G. Y. Wong.
Stochastic blockmodels for directed graphs.
Journal of the American Statistical Association, 82(397):8–19,

[62]
H. C. White, S. A. Boorman, and R. L. Breiger.
Social structure from multiple networks. i. blockmodels of roles and
American Journal of Sociology, 81(4):730–780, 1976.