Mutual information for the sparse

stochastic block model

Tomas DominguezDepartment of Mathematics, University of Toronto<EMAIL_ADDRESS>Jean-Christophe MourratDepartment of Mathematics, ENS Lyon and CNRS<EMAIL_ADDRESS>
We consider the problem of recovering the community structure in the stochastic block model with two communities. We aim to describe the mutual information between the observed network and the actual community structure in the sparse regime, where the total number of nodes diverges while the average degree of a given node remains bounded. Our main contributions are a conjecture for the limit of this quantity, which we express in terms of a Hamilton-Jacobi equation posed over a space of probability measures, and a proof that this conjectured limit provides a lower bound for the asymptotic mutual information. The well-posedness of the Hamilton-Jacobi equation is obtained in our companion paper. In the case when links across communities are more likely than links within communities, the asymptotic mutual information is known to be given by a variational formula. We also show that our conjectured limit coincides with this formula in this case.

§ INTRODUCTION AND MAIN RESULTS

The stochastic block model is the simplest generative model for networks with a community structure. It was first introduced in the machine learning and statistics literature [32, 34, 61, 62] but soon emerged independently in a variety of other scientific disciplines. In the theoretical computer science community it is often termed the planted partition model [15, 17, 31] while the mathematics literature often refers to it as the inhomogeneous random graph model [14]. Since its introduction, the stochastic block model has become a test bed for clustering and community detection algorithms used in social networks [49], protein-to-protein interaction networks [23], recommendation systems [40], medical prognosis [60], DNA folding [18], image segmentation [59] and natural language processing [9] among others. In this paper we focus on the sparse stochastic block model with two communities which we now describe.

Consider $N$ individuals belonging to exactly one of two communities; it will be convenient to describe the communities using vectors of $\pm 1$ with the agreement that people with the same label belong to the same group. In this way, a vector

\begin{equation}
\sigma^*=\big(\sigma^*_1,\ldots,\sigma^*_N\big)\in \Sigma_N=\{-1,+1\}^N
\end{equation}

can be used to encode the two communities. The labels $\sigma^*_i\sim P^*$ are taken to be i.i.d. Bernoulli random variables with probability of success $p\in (0,1)$ and expectation $\m$,

\begin{equation}
p=P^*(1)=\P\{\sigma_i^*=1\} \quad \text{and} \quad \m=\E \sigma_1^*=2p-1.
\end{equation}

The case $p=1/2$ is termed the symmetric stochastic block model, and for reasons that will become apparent below has received the greatest attention. The assignment vector $\sigma^*$ follows a product distribution,

\begin{equation}
\sigma^*\sim P_N^*=(P^*)^{\otimes N},
\end{equation}

so the expected sizes of the communities are $Np$ and $N(1-p)$. Using the assignment vector $\sigma^*$, a random undirected graph $\mathbf{G}_N$ with vertex set $\{1,\ldots,N\}$ is constructed by stipulating that an edge between node $i$ and node $j$ is present with conditional probability

\begin{equation}\label{eqn: SBM edge probabilities aNbN}
\P\big\{G_{ij}=1|\sigma^*\big\}=\begin{cases}
a_N & \text{if } \sigma^*_i=\sigma^*_j\\
b_N & \text{if } \sigma^*_i\neq \sigma^*_j
\end{cases}
\end{equation}

for some $a_N,b_N\in (0,1)$ independently of all other edges. In other words, the probability that an edge is present between node $i$ and node $j$ depends only on whether or not the individuals $i$ and $j$ belong to the same community. To express (<ref>) more succinctly, it is convenient to introduce the average and the gap of $a_N$ and $b_N$,

\begin{equation}
c_N=\frac{a_N+b_N}{2} \quad \text{and} \quad \Delta_N=\frac{a_N-b_N}{2}\in (-c_N,c_N),
\end{equation}

in such a way that

\begin{equation}\label{eqn: SBM edge probabilities cNdN}
\P\{G_{ij}=1|\sigma^*\}=c_N+\sigma^*_i\sigma^*_j\Delta_N.
\end{equation}

The data $\mathbf{G}_N=(G_{ij})$ is said to be sampled from the stochastic block model, and the inference task is to recover the assignment vector $\sigma^*$ as accurately as possible given the graph $\mathbf{G}_N$. In the case when $\Delta_N\leq 0$, it is more likely for an edge to be present between nodes in different communities and the model is called disassortative. When $\Delta_N>0$ connections are more likely between individuals in the same community and the model is termed assortative.

Recently, the stochastic block model has attracted much renewed attention. On a practical level, we mention for instance extensions allowing for overlapping communities [8] that have proved to be a good fit for real data sets in massive networks [33]. On a theoretical level, the predictions put forth in [27] using deep but non-rigorous statistical physics arguments have been particularly stimulating. The theoretical study of the stochastic block model has seen significant progress in two main directions: exact recovery and detection. The exact recovery task aims to determine the regimes of $a_N$ and $b_N$ for which there exists an algorithm that completely recovers the two communities with high probability. Of course, a necessary condition for exact recovery is connectivity of the random graph $\mathbf{G}_N$; this makes exact recovery impossible in the sparse regime. The sharp threshold for exact recovery was obtained in [2, 44], where it was shown that in the symmetric dense regime, $p=1/2$, $a_N=a\log(N)/N$ and $b_N=b\log(N)/N$,  exact recovery is possible, and efficiently so, if and only if $\sqrt{a} - \sqrt{b} \ge 2 $. On the other hand, the detection task is to construct a partition of the graph $\mathbf{G}_N$ that is positively correlated with the assignment vector $\sigma^*$ with high probability. The sharp threshold for detection in the sparse regime was obtained in [41, 42, 45], where it was shown that in the symmetric sparse regime, $p=1/2$, $a_N=a/N$ and $b_N=b/N$, detection is solvable, and efficiently so, if and only if $(a-b)^2>2(a+b)$. Notice that detection is much easier in the asymmetric case [19]. Indeed, the expected degree of node $i$ conditional on its community membership is given by

\begin{equation}
\E[\deg(i)|\sigma^*_i]=(N-1)(c_N+\m\Delta_N\si^*_i),
\end{equation}

so meaningful information about the community structure is revealed from the degrees of nodes.

Despite this clear picture regarding the thresholds for exact recovery and detection in the setting of two communities, several questions remain open. In particular, the problem of quantifying how much information about the communities can be recovered by observing the graph $\mathbf{G}_N$ is not fully understood. Besides, when more than two communities are present, our understanding of the problem is much more limited; we refer the interested reader to [1, 5, 6] for more on this.

The information about the assignment vector $\sigma^*$ that can be recovered from observing the graph $\mathbf{G}_N$ is quantified by the mutual information

\begin{equation}\label{eqn: SBM mutual information}
I(\mathbf{G}_N; \sigma^*)=\E\log\frac{\P(\mathbf{G}_N,\sigma^*)}{\P(\mathbf{G}_N)\P(\sigma^*)}=\E\log \frac{\P(\mathbf{G}_N|\sigma^*)}{\P(\mathbf{G}_N)}.
\end{equation}

The asymptotic value of this mutual information has been computed in the dense regime [10, 28, 39] and the sparse disassortative regime [4, 25]. Its value in the assortative sparse regime remains open despite recent progress in [3, 36, 43, 46]; this is the problem we explore in this paper.

Henceforth, we focus exclusively on the sparse stochastic block model with

\begin{equation}
c_N=\frac{c}{N} \quad \text{and} \quad \Delta_N=\frac{\Delta}{N}
\end{equation}

for some $c>0$ and some non-zero $\Delta\in (-c,c)$. The case $\Delta=0$ is trivial since it corresponds to the case where the graph $\mathbf{G}_N$ and the assignment vector $\sigma^*$ are independent.
The probability (<ref>) that an edge is present between node $i$ and node $j$ becomes

\begin{equation}\label{eqn: SBM edge probabilities}
\P\{G_{ij}=1|\sigma^*\}=\frac{c+\Delta \sigma_i^*\sigma_j^*}{N}
\end{equation}

for the family of conditionally independent Bernoulli random variables $\mathbf{G}_N=(G_{ij})$. The expected degree of any node $i$ remains bounded with $N$,

\begin{equation}
\E \deg(i)=\frac{N-1}{N}\big(c+\Delta \m^2\big),
\end{equation}

so we are indeed in the sparse regime. The likelihood of the model is given by

\begin{equation}\label{eqn: SBM likelihood}
\P\big\{\mathbf{G}_N=(G_{ij})|\sigma^*=\sigma\big\}=\prod_{i<j}\Big(\frac{c+\Delta \sigma_i\sigma_j}{N}\Big)^{G_{ij}}\Big(1-\frac{c+\Delta \sigma_i\sigma_j}{N}\Big)^{1-G_{ij}}=\frac{\exp\big(H_N^\circ(\sigma)\big)}{N^{\sum_{i<j}G_{ij}}},
\end{equation}

while Bayes' formula implies that the posterior of the model is the Gibbs measure

\begin{equation}\label{eqn: SBM posterior}
\P\big\{\sigma^*=\sigma|\mathbf{G}_N=(G_{ij})\big\}=\frac{\exp\big(H_N^\circ(\sigma)\big)P_N^*(\sigma)}{\int_{\Sigma_N}\exp\big(H_N^\circ(\tau)\big)\ud P_N^*(\tau)}
\end{equation}

associated with the Hamiltonian

\begin{equation}\label{eqn: SBM Hamiltonian 0}
H_N^\circ(\sigma)=\sum_{i<j}\log\bigg[\big(c+\Delta \sigma_i\sigma_j\big)^{G_{ij}}\Big(1-\frac{c+\Delta \sigma_i\sigma_j}{N}\Big)^{1-G_{ij}}\bigg].
\end{equation}

This connection between statistical inference and statistical physics is reinforced by noticing that, up to an error vanishing with $N$ and a simple additive constant, the normalized mutual information (<ref>) coincides with the free energy

\begin{equation}\label{eqn: SBM free energy 0}
\overline{F}_N^\circ=\frac{1}{N}\E\log \int_{\Sigma_N}\exp H_N^\circ(\sigma)\ud P_N^*(\sigma).
\end{equation}

Indeed, (<ref>) and Bayes' formula imply that

\begin{equation}
I(\mathbf{G}_N;\sigma^*)=\binom{N}{2}\E\log(c+\Delta \sigma_1^*\sigma_2^*)^{G_{12}}\Big(1-\frac{c+\Delta \sigma_1^*\sigma_2^*}{N}\Big)^{1-G_{12}}-N\overline{F}_N^\circ.
\end{equation}

Averaging with respect to the randomness of $G_{12}$ and Taylor expanding the logarithm reveals that

\begin{equation}\label{eqn: SBM MI and free energy 0}
\frac{1}{N}I(\mathbf{G}_N;\sigma^*)=\frac{1}{2}\E\big(c+\Delta \sigma_1^*\sigma_2^*\big)\log\big(c+\Delta \sigma_1^*\sigma_2^*\big)-\frac{c}{2}-\frac{\Delta \m^2}{2}-\overline{F}_N^\circ+\BigO\big(N^{-1}\big).
\end{equation}

To study the mutual information (<ref>) we take the perspective of statistical physics and instead focus on the free energy (<ref>). Notice that the mutual information between two independent random variables is zero, so for $\Delta=0$, the free energy is found by setting the right-hand side of (<ref>) equal to zero.

For technical reasons, it will be convenient to modify the free energy (<ref>) without changing its limiting value. Conditionally on $\sigma^*$, the modified Hamiltonian will be a sum of independent random variables, and the sum will be over a Poisson-distributed number of terms. The main advantage of this construction is that we can then conveniently vary the continuous parameter encoding the Poisson random variable, and in particular study derivatives with respect to this parameter. To be more precise, we introduce a random variable $\smash{\Pi_{1}\sim\Poi\binom{N}{2}}$ as well as an independent family of i.i.d. random matrices $\smash{(G^k)_{k \in \N}}$ each having independent entries $\smash{(G_{i,j}^k)_{i,j\leq N}}$ with conditional distribution

\begin{equation}\label{eqn: SBM G distribution}
\P\big\{G_{i,j}^k=1|\sigma^*\big\}=\frac{c+\Delta \sigma_{i}^*\sigma_{j}^*}{N}.
\end{equation}

Given a collection of random indices $\smash{(i_k,j_k)_{k\in \N}}$ sampled uniformly at random from $\smash{\{1,\ldots,N\}^2}$, independently of the other random variables, we define the Hamiltonian $H_N$ on $\Sigma_N$ by

\begin{equation}\label{eqn: SBM Hamiltonian}
H_N(\sigma)=\sum_{k\leq \Pi_{1}}\log \bigg[\big(c+\Delta \sigma_{i_k}\sigma_{j_k}\big)^{G^k_{i_k,j_k}}\Big(1-\frac{c+\Delta \sigma_{i_k}\sigma_{j_k}}{N}\Big)^{1-G^k_{i_k,j_k}}\bigg],
\end{equation}

and write

\begin{equation}\label{eqn: SBM free energy}
\overline{F}_N=\frac{1}{N}\E\log \int_{\Sigma_N} \exp H_N(\sigma)\ud P_N^*(\sigma)
\end{equation}

for its associated free energy. We show in <Ref> that the difference between the free energies in (<ref>) and (<ref>) tends to $0$ as $N$ tends to infinity. Together with (<ref>), this implies that

\begin{equation}\label{eqn: SBM MI and FE}
\frac{1}{N}I(\mathbf{G}_N;\sigma^*)=\frac{1}{2}\E\big(c+\Delta \sigma_1^*\sigma_2^*\big)\log\big(c+\Delta \sigma_1^*\sigma_2^*\big)-\frac{c}{2}-\frac{\Delta \m^2}{2}-\overline{F}_N+o_N(1).
\end{equation}

The problem of finding the asymptotic value of the mutual information (<ref>) has therefore been reduced to the task of determining the limit of the free energy (<ref>). The main contributions of this work are the conjecture that

\begin{equation}
\lim_{N\to \infty}\overline{F}_N=f(1,0),
\end{equation}

where $f(t,\mu)$ is the solution to an infinite-dimensional Hamilton-Jacobi equation defined in (<ref>), and a proof that $f(1,0)$ provides an upper bound for the limit of the free energy; the matching lower bound will remain open.

To motivate and define the infinite-dimensional Hamilton-Jacobi equation (<ref>), we will introduce an “enriched” free energy functional
by transforming the free energy (<ref>) into a function of a “time” variable $t \ge 0$ and a non-negative measure $\mu$. The “time” variable will be used to vary the intensity of the Poisson point process $\Pi_1$ appearing in the Hamiltonian (<ref>). We introduced the Hamiltonian $H_N$ to replace $H_N^\circ$ in order to allow for convenient integration-by-parts-like calculations as we study derivatives with respect to this parameter $t$. The non-negative measure $\mu$ will be decomposed as $\mu = s \bar{\mu}$ for $s \geq 0$ and a probability measure $\bar{\mu}$. It will be used to consider a situation in which we also observe the graph of connections of a simpler setting in which each individual $i$ can form connections with its own set of neighbour candidates. To be more specific, each individual $i$ will have an independent number $\Poi(s)$ of neighbour candidates indexed by the pairs $(i,k)$ for $k \leq \Poi(s)$. Each candidate neighbour $(i,k)$ will be independently assigned a random “type” $x_{i,k}$ sampled from the distribution $\bar{\mu}$, and an edge will be present between individual $i$ and its candidate neighbour $(i,k)$ with probability $N^{-1} (c+ \Delta \sigma_i^* x_{i,k})$. In the inference problem, the “types” $x_{i,k}$ are revealed to the statistician. The lack of interactions between individuals makes this piece of information much simpler to understand than the original community detection problem we aim to make progress upon. In total, this allows us to define an “enriched” free energy, function of $t$ and $\mu$, and the quantity in (<ref>) can then be recovered by evaluating this enriched free energy at $t = 1$ and $\mu = 0$. We next aim to study whether variations in the $t$ variable can be suitably compensated by variations in the $\mu$ variable, leaving the free energy roughly constant. More precisely, we hope to discover that the derivative in $t$ of this functional can be expressed, up to a small error, as a function of its derivative in $\mu$. On a heuristic level, one can see that this indeed seems to be possible, as will be clarified below. Combining ideas from the theory of viscosity solutions with the multi-overlap concentration result in [12], we will be able to prove one inequality between the limit free energy and the solution to the partial differential equation that arises. Although we expect the converse bound to also be valid, significant technical challenges prevent us from proving it at the moment. The difficulty is that the control we have on the “small error” appearing in the equation at finite $N$ is relatively weak. In particular, we cannot show, and do not expect, that it becomes small as $N$ tends to infinity for each individual choice of $t$ and $\mu$. On the other hand, controlling the error after we perform a small averaging over $t$ and $\mu$ is possible, but does not suffice for the identification of the limit.

Let us now define the enriched free energy precisely. Denote by $\Pr[-1,1]$ the set of probability measures on $[-1,1]$, and given $\mu \in \Pr[-1,1]$, consider a sequence $x=(x_{i,k})$ of i.i.d. random variables with law $\mu$. For each $s>0$ and $i\geq 1$, let $\Pi_{i,s}\sim \Poi(sN)$ be independent over $i\geq 1$, and introduce the Hamiltonian on $\Sigma_N$,

\begin{equation}\label{eqn: SBM Hamiltonian s}
\widetilde{H}_N^{s,\mu}(\sigma)=\sum_{i\leq N}\sum_{k\leq \Pi_{i,s}}\log\bigg[\big(c+\Delta \sigma_ix_{i,k}\big)^{\tG_{i,k}^x}\Big(1-\frac{c+\Delta \sigma_ix_{i,k}}{N}\Big)^{1-\tG_{i,k}^x}\bigg],
\end{equation}

where the random variables $(\tG_{i,k}^x)$ are independent with conditional distribution

\begin{equation}\label{eqn: SBM tG distribution}
\P\big\{\tG_{i,k}^x=1|\sigma^*,x\big\}=\frac{c+\Delta \sigma_i^*x_{i,k}}{N}.
\end{equation}

As alluded to above, this is the Hamiltonian associated with the task of inferring the signal $\sigma^*$ from the data

\begin{equation}
\widetilde{\D}_N^{s,\mu}=\big(\Pi_{i,s}, (x_{i,k})_{k\leq \Pi_{i,s}}, (\tG_{i,k})_{k\leq \Pi_{i,s}}\big)_{i\leq N},
\end{equation}

in the sense that the Gibbs measure associated with  $\smash{\widetilde{H}_N^{s,\mu}}$ is the conditional law of $\si^*$ given the data $\smash{\widetilde{\D}_N^{s,\mu}}$ (as in the identity (<ref>) for the Hamiltonian $H_N^\circ$ and the data $\mathbf G_N$).
For each $t\geq 0$, let $\smash{\Pi_t\sim \Poi t\binom{N}{2}}$, and consider a time-dependent version of the Hamiltonian (<ref>) defined on $\Sigma_N$ by

\begin{equation}\label{eqn: SBM Hamiltonian t}
H_N^t(\sigma)=\sum_{k\leq \Pi_t}\log \bigg[\big(c+\Delta \sigma_{i_k}\sigma_{j_k}\big)^{G^k_{i_k,j_k}}\Big(1-\frac{c+\Delta \sigma_{i_k}\sigma_{j_k}}{N}\Big)^{1-G^k_{i_k,j_k}}\bigg].
\end{equation}

Notice that this is the Hamiltonian associated with the task of inferring the signal $\sigma^*$ from the data

\begin{equation}
\D_N^t=\big(\Pi_t, (i_k,j_k)_{k\leq \Pi_t},(G^k_{i_k,j_k})_{k\leq \Pi_t}\big).
\end{equation}

Introduce an enriched Hamiltonian on $\Sigma_N$,

\begin{equation}\label{eqn: SBM enriched Hamiltonian s}
\widetilde{H}_N^{t,s,\mu}(\sigma)=H_N^t(\sigma)+\widetilde{H}_N^{s,\mu}(\sigma),
\end{equation}

and denote by

\begin{equation}\label{eqn: SBM enriched free energy s}
\widetilde{F}_N(t,s,\mu)=\frac{1}{N}\E\log \int_{\Sigma_N} \exp \widetilde{H}_N^{t,s,\mu}(\sigma)\ud P_N^*(\sigma)
\end{equation}

its associated free energy. Observe that $\widetilde{F}_N(1,0,\mu)=\overline{F}_N$ and that (<ref>) is the Hamiltonian associated with inferring the signal $\sigma^*$ from the data

\begin{equation}\label{eqn: SBM enriched data}
\widetilde{\D}_N^{t,s,\mu}=(\D_N^t, \widetilde{\D}_N^{s,\mu}),
\end{equation}

where the randomness in these two data sets is taken to be independent conditionally on $\sigma^*$. To obtain a Hamilton-Jacobi equation, it will be convenient to reinterpret the enriched free energy (<ref>) as a function of the time-parameter $t>0$ and a finite measure $\mu$; the parameter $s$ will become the total mass of this finite measure.

We denote by $\M_s$ the space of signed measures on $[-1,1]$,

\begin{equation}
\M_s=\big\{\mu \mid \mu \text{ is a signed measure on } [-1,1]\big\},
\end{equation}

and by $\M_+$ the cone of non-negative measures on this interval,

\begin{equation}\label{eqn: SBME M+}
\M_+=\big\{\mu \in \M_s\mid \mu \text{ is a non-negative measure}\big\}.
\end{equation}

We follow the convention that a signed measure can only take finite values, and in particular, every $\mu \in \M_+$ must have finite total mass. This implies that every non-zero measure $\mu \in \M_+$ induces a probability measure,

\begin{equation}
\bar{\mu}=\frac{\mu}{\mu[-1,1]}\in \Pr[-1,1].
\end{equation}

Given a measure $\mu \in \M_+$, we define the Hamiltonian $\smash{H_N^{t,\mu}}$ on $\Sigma_N$ by

\begin{equation}\label{eqn: SBM enriched Hamiltonian}
\end{equation}

where $\widetilde{H}_N^{0,0}=0$ for the zero measure by continuity. The free energy associated with this Hamiltonian is given by

\begin{equation}\label{eqn: SBM enriched free energy}
\overline{F}_N(t,\mu)=\widetilde{F}_N\big(t,\mu[-1,1],\bar{\mu}\big),
\end{equation}

and once again $\overline{F}_N = \overline{F}_N(1,0)$, where $0$ denotes the zero measure. The free energy in (<ref>) will be termed the enriched free energy, and in <Ref> we will show that, up to a “small error”, it satisfies an infinite-dimensional Hamilton-Jacobi equation which we now describe.

Introduce the function $g:[-1,1]\to \R$ defined by

\begin{equation}\label{eqn: SBM g function}
g(z)=(c+\Delta z)\big(\log(c+\Delta z)-1\big)=(c+\Delta z)\log(c)+c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}z^n-c
\end{equation}

as well as the cone of functions

\begin{equation}\label{eqn: SBM cone of functions}
\CC_\infty=\bigg\{G_\mu : [-1,1]\to\R \mid G_\mu(x)=\int_{-1}^1 g(xy)\ud \mu(y) \text{ for some } \mu\in \M_+\bigg\}
\end{equation}

and the non-linearity $\C_\infty: \CC_\infty\to \R$ given by

\begin{equation}\label{eqn: SBM infinite non-linearity}
\C_\infty(G_\mu)=\frac{1}{2}\int_{-1}^1 G_\mu(x)\ud \mu(x).
\end{equation}

This non-linearity is well-defined by the Fubini-Tonelli theorem (see equations (6)-(7) in [30]). Given a function $f:[0,\infty)\times \M_+\to \R$ and measures $\mu,\nu\in \M_+$, we denote by $D_\mu f(t,\mu;\nu)$ the Gateaux derivative of the function $f(t,\cdot)$ at the measure $\mu$ in the direction $\nu$,

\begin{equation}\label{eqn: SBME Gateaux derivative}
D_\mu f(t,\mu;\nu)=\lim_{\epsilon \to 0}\frac{f(t,\mu+\epsilon \nu)-f(t,\mu)}{\epsilon}.
\end{equation}

We will say that the Gateaux derivative of $f$ admits a density at the measure $\mu \in \M_+$ if there exists a bounded measurable function $x\mapsto D_\mu f(t,\mu,x)$ defined on the interval $[-1,1]$ with

\begin{equation}\label{eqn: SBME Gateaux derivative density}
D_\mu f(t,\mu;\nu)=\int_{-1}^1 D_\mu f(t,\mu,x)\ud \nu(x)
\end{equation}

for every measure $\nu \in \M_+$. We will often abuse notation and identify the density $D_\mu f(t,\mu,\cdot)$ with the Gateaux derivative $D_\mu f(t,\mu)$. In <Ref> we will show that, up to an error vanishing with $N$, the Gateaux derivative of the enriched free energy is indeed of the form $G_{\mu^*}$ for some $\mu^* \in \M_+$. In fact, the measure $\mu^*$ is the law of the Gibbs average of a uniformly sampled spin coordinate for the Gibbs measure associated with the Hamiltonian (<ref>). We will also argue that, if this Gibbs measure satisfies suitable overlap concentration properties, then the time derivative of the free energy is essentially given by $\int_{-1}^1 g(xy) \ud \mu^*(x) \ud \mu^*(y)$. In short, assuming the validity of these overlap concentration properties, we are led to believe that the large-$N$ limit of the free energy (<ref>) should satisfy the infinite-dimensional Hamilton-Jacobi equation

\begin{equation}\label{eqn: SBM enriched free energy HJ equation}
\left\{
\begin{aligned}
\partial_t f(t,\mu)&=\C_\infty\big(D_\mu f(t,\mu)\big) & \text{on }& \Rpp\times \M_+,\\
f(0,\mu)&=\psi(\mu)& \text{on }& \M_+,
\end{aligned}
\right.
\end{equation}

where the initial condition $\smash{\psi:\M_+\to\R}$ is the limit of $\smash{F_N(0,\cdot)}$ and can be readily computed, see Lemma <ref>.
The well-posedness of this equation will be established using the main result in [30], and leads to the conjecture that the enriched free energy converges to the solution to this equation. Remembering (<ref>), this translates into a conjecture for the asymptotic mutual information.

If $f$ denotes the unique viscosity solution to the infinite-dimensional Hamilton-Jacobi equation (<ref>), then the limit of the free energy (<ref>) is given by

\begin{equation}
\lim_{N\to \infty}\overline{F}_N=f(1,0).
\end{equation}

In particular, the asymptotic value of the mutual information (<ref>) is

\begin{align}
\lim_{N\to\infty}\frac{1}{N}I(\mathbf{G}_N;\sigma^*)=\frac{1}{2}\E\big(c+\Delta \sigma_1^*\sigma_2^*\big)\log\big(c+\Delta \sigma_1^*\sigma_2^*\big)-\frac{c}{2}-\frac{\Delta\m^2}{2}-f(1,0).
\end{align}

The main result of this paper is a proof of the upper bound in <Ref>.

Denote by $f$ the unique viscosity solution to the infinite-dimensional Hamilton-Jacobi equation (<ref>). For every $t\geq 0$ and  $\mu\in \M_+$, the limit of the enriched free energy (<ref>) satisfies the upper bound $\smash{\limsup_{N\to \infty}\overline{F}_N(t,\mu)\leq f(t,\mu)}$.
In particular, the free energy (<ref>) satisfies the upper bound

\begin{equation}
\label{e.SBM.main}
\limsup_{N\to \infty}\overline{F}_N\leq f(1,0).
\end{equation}

Although the matching lower bound still remains open, we give some support in favor of <Ref> by proving that, in the disassortative regime, it matches the variational formula for the asymptotic free energy obtained in [25]. We state this formula using the notation in [11], where a more direct proof is obtained using an interpolation argument and a cavity computation. Denote by

\begin{equation}
\M_p=\bigg\{\mu\in \Pr[-1,1]\mid \int_{-1}^1 x\ud \mu=\m\bigg\}
\end{equation}

the set of probability measures with mean $\m=2p-1$, and introduce the functional $\Par:\M_p\to \R$ defined by

\begin{equation}\label{eqn: SBM Parisi functional}
\Par(\mu)=\psi(\mu)+\frac{c}{2}+\frac{\Delta\m^2}{2}-\frac{1}{2}\E(c+\Delta x_1x_2)\log(c+\Delta x_1x_2),
\end{equation}

where $x_1$ and $x_2$ are independent samples from the probability measure $\mu$.

In the disassortative sparse stochastic block model with $\Delta\leq 0$, the limit of the free energy (<ref>) is given by

\begin{equation}\label{eqn: SBM disassortative Hopf-Lax}
\lim_{N\to \infty}\overline{F}_N=\sup_{\mu \in \M_p}\Par(\mu) = f(1,0).
\end{equation}

We now give a brief outline of the paper. In <Ref> we show that, up to an error vanishing with $N$, the enriched free energy (<ref>) satisfies the infinite-dimensional Hamilton-Jacobi equation (<ref>), provided that all multi-overlaps concentrate.
The derivative computations that lead to the Hamilton-Jacobi equation are similar in spirit to those in Lemma 6 of [51], with some new ideas required to compute the Gateaux derivative. <Ref> is devoted to establishing the well-posedness of the infinite-dimensional Hamilton-Jacobi equation (<ref>) using the results in [30], which in turn follows ideas from [21, 22, 47, 48].
In <Ref>, a finitary version of the multi-overlap concentration result in [12] is combined with the strategy introduced in [47, 48] to prove <Ref>. The final section is devoted to the proof of <Ref>. Using the Hopf-Lax formula established in [30], the variational expression in (<ref>) is shown to coincide with the right side of (<ref>), and we can thus appeal to <Ref> to obtain an upper bound for the limit free energy. The matching lower bound is obtained through an interpolation argument taken from [11]. So as to not disrupt the flow of the paper, a number of technical arguments have been postponed to the appendices. In <Ref>, it is shown that the free energy functionals (<ref>) and (<ref>) are asymptotically equivalent. The proof relies on the binomial-Poisson approximation [58]. <Ref> is devoted to proving that a perturbed version of the enriched free energy (<ref>) is self-averaging, in the sense that the unaveraged free energy concentrates around its average value. This concentration result plays an important part in the proof of <Ref> and relies upon the generalized Efron-Stein inequality [16]. In <Ref>, a finitary version of the multi-overlap concentration result in [12] is established. In addition to being finitary, the most notable difference between our multi-overlap result and that in [12] is that we show multi-overlap concentration for any perturbation parameter satisfying a condition that may be verified in practice, as opposed to obtaining multi-overlap concentration on average over the set of perturbation parameters. This additional control on the choice of parameters is essential in the proof of <Ref>.

We plan to tackle the lower bound in Conjecture 1 in future work, following some of the ideas introduced in [20]. Using also the vector spin techniques developed in [54, 56, 57] and applied in [7, 13, 24, 26, 29, 35, 38, 47], we are optimistic that our results should extend to the setting of an arbitrary finite number of communities.

We would like to warmly thank Dmitry Panchenko and Jean Barbier for sharing their notes [11] on the free energy in the disassortative sparse stochastic block model with us, which provided us with a very useful starting point and helped us with many of the computations in <Ref>.

§ THE HAMILTON-JACOBI EQUATION

In this section, we compute the derivative of the enriched free energy (<ref>) with respect to $t\geq 0$ and $\mu \in\M_+$. This will allow us to see that, up to an error vanishing with $N$, the enriched free energy heuristically satisfies (<ref>). It will be convenient to write $\langle \cdot \rangle$ for the average with respect to the Gibbs measure associated with the Hamiltonian (<ref>). This means that for any bounded and measurable function $f=f(\sigma^1,\ldots,\sigma^n)$ of finitely many replicas,

\begin{equation}\label{eqn: SBM Gibbs average}
\langle f(\si^1, \ldots, \si^n) \rangle = \langle f\rangle   =\frac{\int_{\Sigma_N^n}f(\sigma^1,\ldots,\sigma^n)\prod_{\ell\leq n}\exp H_N^{t,\mu}(\sigma^\ell)\ud P_N^*(\sigma^\ell)}{\big(\int_{\Sigma_N} \exp H_N^{t,\mu}(\sigma)\ud P_N^*(\sigma)\big)^n}.
\end{equation}

In this notation, the replicas $\si^1,\ldots,\si^n$ represent i.i.d. samples under the random measure $\langle \cdot\rangle$.
By construction, we have that

\begin{equation}
\label{eqn: SBM Gibbs conditional}
\langle f(\si^1) \rangle = \E \big[ f(\sigma^*) \big \vert \D_N^{t,\mu} \big],
\end{equation}

where $\smash{\D_N^{t,\mu}=\widetilde{\D}_N^{t,\mu[-1,1],\bar{\mu}}}$ is the data defined in (<ref>).

Our computations will be considerably simplified by the Nishimori identity. This fundamental identity will allow us to freely interchange one replica $\sigma^\ell$ by the signal $\sigma^*$ when taking an average with respect to all sources of randomness, thus avoiding a cascade of new replicas as we differentiate the free energy. This identity states that, for every bounded and measurable function $f=f(\sigma^1,\ldots,\sigma^n,\D_N^{t,\mu})$ of finitely many replicas and the data,

\begin{equation}\label{eqn: SBM Nishimori identity}
\E\big\langle f\big(\sigma^1,\sigma^2,\ldots,\sigma^n, \D_N^{t,\mu}\big)\big\rangle=\E\big\langle f\big(\sigma^*,\sigma^2,\ldots,\sigma^n, \D_N^{t,\mu}\big)\big\rangle.
\end{equation}

This can be first verified for functions of product form using (<ref>), and then extended to all bounded and measurable functions by a monotone class argument.

We now turn our attention to the computation of the time derivative of the enriched free energy (<ref>). We fix a finite measure $\mu \in \M_+$ and proceed as in Lemma 6 of [51]. For each parameter $\lambda>0$ and every integer $m\geq 0$, we denote by

\begin{equation}\label{eqn: SBM Poisson density}
\pi(\lambda,m)=\frac{\lambda^m}{m!}e^{-\lambda}
\end{equation}

the mass attributed to the atom $m$ by a $\Poi(\lambda)$ distribution. It will be convenient to set the convention that $\pi(\lambda,-1) = 0$. We write

\begin{equation}\label{eqn: SBM conditioned Hamiltonian 1}
H_{N,m}(\sigma)=\sum_{k\leq m}\log \bigg[\big(c+\Delta \sigma_{i_k}\sigma_{j_k}\big)^{G^k_{i_k,j_k}}\Big(1-\frac{c+\Delta \sigma_{i_k}\sigma_{j_k}}{N}\Big)^{1-G^k_{i_k,j_k}}\bigg]
\end{equation}

for the Hamiltonian (<ref>) conditional on there being $m$ terms in the sum, and introduce the partition function

\begin{equation}
Z_{N,m}=\int_{\Sigma_N} \exp\Big(H_{N,m}(\sigma)+\widetilde{H}_N^{\mu[-1,1],\bar{\mu}}(\sigma)\Big)\ud P_N^*(\sigma).
\end{equation}

In this notation, the enriched free energy (<ref>) may be expressed as

\begin{equation}\label{eqn: SBM enriched free energy rep1}
\overline{F}_N(t,\mu)=\frac{1}{N}\sum_{m\geq 0}\pi\Big(t\binom{N}{2},m\Big)\E \log Z_{N,m}.
\end{equation}

To take the time derivative of this expression, we will rely upon the simple fact that

\begin{equation}\label{eqn: SBM Poisson density derivative}
\partial_\lambda\pi(\lambda,m)=\pi(\lambda,m-1)-\pi(\lambda,m).
\end{equation}

For any $t>0$ and $\mu \in \M_+$,

\begin{equation}\label{eqn: SBM enriched free energy time derivative}
\partial_t\overline{F}_N(t,\mu)=\frac{1}{2}\E \big(c+\Delta \langle \sigma_i\sigma_j\rangle\big)\log \big( c+\Delta \langle \sigma_i\sigma_j\rangle\big)-\frac{\Delta \m^2}{2}-\frac{c}{2}+\BigO(N^{-1}),
\end{equation}

where the indices $i,j\in \{1,\ldots,N\}$ are uniformly sampled independently of all other sources of randomness.

To simplify notation, let $\lambda(t)=t\binom{N}{2}$. Leveraging (<ref>) to differentiate the right-hand side of (<ref>) yields

\begin{align}\label{eqn: SBM enriched free energy time derivative key}
\partial_t\overline{F}_N(t,\mu)&=\frac{1}{N}\binom{N}{2}\sum_{m\geq 0} \big(\pi(\lambda(t),m-1)-\pi(\lambda(t),m)\big) \E \log Z_{N,m}\notag\\
&=\frac{1}{N}\binom{N}{2}\sum_{m\geq 0}\pi(\lambda(t),m)\E \log \frac{Z_{N,m+1}}{Z_{N,m}}.
\end{align}

Denote by $i,j\in \{1,\ldots,N\}$ uniformly sampled indices, and write $G_{i,j}$ for a random variable with conditional distribution (<ref>). These random variables are taken to be independent of all other sources of randomness and of each other. Since

$$Z_{N,m+1}\stackrel{d}{=} \int_{\Sigma_N} \big(c+\Delta \sigma_i\sigma_j\big)^{G_{i,j}}\Big(1-\frac{c+\Delta \sigma_i\sigma_j}{N}\Big)^{1-G_{i,j}}\exp \Big(H_{N,m}(\sigma)+H_N^{\mu[-1,1],\bar{\mu}}(\sigma)\Big)\ud P_N^*(\sigma),$$

it follows by (<ref>) and the definition of the Gibbs average in (<ref>) that

$$\partial_t \overline{F}_N(t,\mu)=\frac{1}{N}\binom{N}{2}\E \log \bigg\langle \big(c+\Delta \sigma_i\sigma_j\big)^{G_{i,j}}\Big(1-\frac{c+\Delta \sigma_i\sigma_j}{N}\Big)^{1-G_{i,j}}\bigg\rangle.$$

Remembering the explicit form of the conditional distribution (<ref>), and averaging with respect to the randomness of $G_{i,j}$ reveals that

\begin{align*}
\partial_t \overline{F}_N(t,s,\mu)=\frac{1}{2}\E\big(c+\Delta \sigma_i^*\sigma_j^*\big)& \log \langle c+\Delta \sigma_i\sigma_j\rangle\\
&+\frac{N}{2}\E\bigg(1-\frac{c+\Delta \sigma_i^*\sigma_j^*}{N}\bigg)\log \Big\langle 1-\frac{c+\Delta \sigma_i\sigma_j}{N}\Big\rangle+\BigO(N^{-1}),
\end{align*}

Taylor expanding the logarithm and keeping only first order terms reduces this to

\begin{align*}
\partial_t \overline{F}_N(t,\mu)&=\frac{1}{2}\E \big(c+\Delta \sigma_i^*\sigma_j^*\big)\log \langle c+\Delta \sigma_i\sigma_j\rangle-\frac{\Delta}{2}\E \langle\sigma_i\sigma_j\rangle-\frac{c}{2}+\BigO(N^{-1})\\
&=\frac{1}{2}\E \big(c+\Delta \sigma_i^*\sigma_j^*\big)\log \langle c+\Delta \sigma_i\sigma_j\rangle-\frac{\Delta}{2}\E \sigma_i^*\sigma_j^*-\frac{c}{2}+\BigO(N^{-1})\\
&=\frac{1}{2}\E \big(c+\Delta \sigma_i^*\sigma_j^*\big)\log \big(c+\Delta \langle\sigma_i\sigma_j\rangle\big)-\frac{\Delta\m^2}{2}-\frac{c}{2}+\BigO(N^{-1}),
\end{align*}

where the second equality uses the Nishimori identity (<ref>) and the third equality uses the fact that $i$ and $j$ are distinct with overwhelming probability. Noticing that the Gibbs average $\langle \sigma_i\sigma_j\rangle$ is a measurable function of the data by (<ref>), and applying the Nishimori identity (<ref>) completes the proof.

To compare (<ref>) with the Gateaux derivative of the enriched free energy which we will compute below, it will be convenient to Taylor expand the logarithm. This will make the dependence of the time-derivative of the enriched free energy on the multi-overlaps

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

associated with the enriched Hamiltonian (<ref>) explicit. Here $(\sigma^\ell)$ denotes a sequence of i.i.d. replicas sampled from the Gibbs measure (<ref>). To simplify notation, we will write $R_{[n]}=R_{1,\ldots,n}$.

For any $t>0$ and $\mu \in \M_+$,

\begin{equation}
\partial_t \overline{F}_N(t,\mu)=\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-\frac{c}{2}+\BigO(N^{-1}).
\end{equation}

A Taylor expansion of the logarithm shows that

$$\log\big( c+\Delta \langle\sigma_i\sigma_j\rangle\big)=\log(c)+\log \Big(1+\frac{\Delta}{c}\langle \sigma_i\sigma_j\rangle\Big)=\log(c)-\sum_{n\geq 1}\frac{(-\Delta/c)^n}{n}\langle \sigma_i\sigma_j\rangle^n.$$

Together with the Nishimori identity (<ref>) this implies that

\begin{align}\label{eqn: SBM enriched free energy time derivative rep2 key}
\E\big(c+\Delta \langle \sigma_i \sigma_j\rangle\big)\log\big( c+\Delta \langle\sigma_i\sigma_j\rangle\big)=\big(c+\Delta \m^2\big)&\log(c)\notag\\
&-\sum_{n\geq 1}\frac{(-\Delta/c)^n}{n}\E\big(c+\Delta\langle \sigma_i\sigma_j\rangle\big)\langle \sigma_i\sigma_j\rangle^n.
\end{align}

Since the indices $i,j\in \{1,\ldots,N\}$ are distinct with overwhelming probability, the Nishimori identity (<ref>) reveals that

$$\E\big(c+\Delta\langle \sigma_i\sigma_j\rangle \big)\langle \sigma_i\sigma_j\rangle^n=c\E\big\langle R_{[n]}^2\big\rangle+\Delta \E\big\langle R_{[n+1]}^2\big\rangle+\BigO(N^{-1}).$$

Remembering that $\abs{\Delta}<c$ and noticing that $\E\langle R_1^2\rangle=\m^2+\BigO(N^{-1})$ by the Nishimori identity, it follows that, up-to an error vanishing with $N$,

\begin{align*}
\sum_{n\geq 1}\frac{(-\Delta/c)^n}{n}\E\big(c+\Delta\langle \sigma_i\sigma_j\rangle\big)\langle \sigma_i\sigma_j\rangle^n&=-\Delta\E\big\langle R_1^2\big\rangle+c\sum_{n\geq 2}\bigg(\frac{(-\Delta/c)^n}{n}-\frac{(-\Delta/c)^n}{n-1}\bigg)\E\big\langle R_{[n]}^2\big\rangle\\
&=-\Delta \m^2-c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\big\langle R_{[n]}^2\big\rangle +\BigO(N^{-1}).
\end{align*}

Substituting this into (<ref>) and invoking <Ref> completes the proof.

The computation of the Gateaux derivative of the enriched free energy (<ref>) at a measure $\smash{\mu \in \M_+}$ in the direction of a probability measure $\smash{\nu\in \Pr[-1,1]}$,

\begin{equation}\label{eqn: SBM free energy Gateaux derivative}
D_\mu \overline{F}_N(t,\mu; \nu)=\lim_{\epsilon \to 0}\frac{\overline{F}_N(t,\mu+\epsilon \nu)-\overline{F}_N(t,\mu)}{\epsilon},
\end{equation}

is slightly more involved. It will be useful to compute the derivative of the free energy (<ref>) with respect to the parameter $s\geq 0$ first. Fix a probability measure $\mu\in \Pr[-1,1]$ and a time $t\geq 0$. For each $i\leq N$ write

\begin{align}\label{eqn: SBM conditioned Hamiltonian 2}
\widetilde{H}_{N,m}^{s,i}(\sigma)=\sum_{j\neq i}\sum_{k\leq \Pi_{j,s}}\log&\bigg[\big(c+\Delta \sigma_jx_{j,k}\big)^{\tG_{j,k}^x}\Big(1-\frac{c+\Delta \sigma_jx_{j,k}}{N}\Big)^{1-\tG_{j,k}^x}\bigg]\notag\\
& +\sum_{k\leq m}\log\bigg[\big(c+\Delta \sigma_ix_{i,k}\big)^{\tG_{i,k}^x}\Big(1-\frac{c+\Delta \sigma_ix_{i,k}}{N}\Big)^{1-\tG_{i,k}^x}\bigg]
\end{align}

for the Hamiltonian (<ref>) conditional on the $i$'th Poisson sum containing $m$ terms, and denote by

\begin{equation}
Z_{N,m}^{s,i}=\int_{\Sigma_N} \exp \big(H_{N}^t(\sigma)+\widetilde{H}^{s,i}_{N,m}(\sigma)\big)\ud P_N^*(\sigma)
\end{equation}

its associated partition function. In this notation, the free energy (<ref>) may be expressed as

\begin{equation}\label{eqn: SBM enriched free energy rep2}
\widetilde{F}_N(t,s,\mu)=\frac{1}{N}\sum_{m\geq 0}\pi(sN,m)\E \log Z_{N,m}^{s,i}.
\end{equation}

For any $t>0$, $s>0$ and $\mu \in \Pr[-1,1]$,

\begin{equation}\label{eqn: SBM enriched free energy s derivative}
\partial_s \widetilde{F}_N(t,s,\mu)=\E\big(c+\Delta \langle \sigma_i\rangle x_i\big)\log \big(c+\Delta \langle\sigma_i\rangle x_i\big)-c-\Delta \m \E x_1+\BigO(N^{-1}),
\end{equation}

where the index $i\in \{1,\ldots,N\}$ is uniformly sampled and the random variables $(x_i)$ are sampled from the measure $\mu$ independently of all other sources of randomness.

Conditioning on the number of terms in each of the Poisson sums that appear in the definition of the free energy (<ref>) and leveraging the product rule as well as equations (<ref>) and (<ref>), we see that

\begin{align}\label{eqn: SBM enriched free energy s derivative key}
\partial_s \widetilde{F}_N(t,s,\mu)&=\frac{1}{N}\sum_{i\leq N}\sum_{m\geq 0}\partial_s\pi(sN,m)\E \log Z_{N,m}^{s,i}=\sum_{i\leq N}\sum_{m\geq 0}\pi(sN,m)\E\log \frac{Z_{N,m+1}^{s,i}}{Z_{N,m}^{s,i}}.
\end{align}

For each $i\leq N$, denote by $x_i$ a sample from the measure $\mu$, and write $\tG_i^x$ for a random variable with conditional distribution (<ref>). These random variables are taken to be independent for different values of $i\leq N$, and independent of all other sources of randomness. Since

\begin{equation}\label{eqn: SBM s derivative distributional equality}
Z_{N,m+1}^{s,i}\stackrel{d}{=}\int_{\Sigma_N} \big(c+\Delta \sigma_ix_i\big)^{\tG_i^x}\Big(1-\frac{c+\Delta \sigma_ix_i}{N}\Big)^{1-\tG_i^x}\exp \big(H_N^t(\sigma)+\widetilde{H}_{N,m}^{s,i}(\sigma)\big)\ud P_N^*(\sigma),
\end{equation}

it follows by (<ref>) and the definition of the Gibbs average in (<ref>) that

\begin{equation}\label{eqn: SBM enriched free energy s derivative exact}
\partial_s \widetilde{F}_N(t,s,\mu)=\sum_{i\leq N}\E \log \bigg\langle\big(c+\Delta \sigma_ix_i\big)^{\tG_i^x}\Big(1-\frac{c+\Delta \sigma_ix_i}{N}\Big)^{1-\tG_i^x} \bigg\rangle.
\end{equation}

Remembering the explicit form of the conditional distribution (<ref>) reveals that

\begin{align*}
\partial_s \widetilde{F}_N(t,s,\mu)=\frac{1}{N}\sum_{i\leq N}\E\big(c+\Delta \sigma_i^*x_i\big)\log \langle c&+\Delta \sigma_ix_i\rangle\\
&+\sum_{i\leq N}\E\Big(1-\frac{c+\Delta \sigma_i^* x_i}{N}\Big)\log \Big\langle 1-\frac{c+\Delta \sigma_ix_i}{N}\Big\rangle.
\end{align*}

Taylor expanding the logarithm and keeping only first order terms reduces this to

\begin{align*}
\partial_s \widetilde{F}_N(t,s,\mu)&=\frac{1}{N}\sum_{i\leq N}\E\big(c+\Delta \sigma_i^*x_i\big)\log \langle c+\Delta \sigma_ix_i\rangle-c-\frac{\Delta}{N}\sum_{i\leq N}\E x_i\E\langle \sigma_i\rangle+\BigO(N^{-1})\\
&=\frac{1}{N}\sum_{i\leq N}\E\big(c+\Delta \sigma_i^* x_i\big)\log \big(c+\Delta \langle \sigma_i\rangle x_i\big)-c-\Delta \m \E x_1+\BigO(N^{-1}),
\end{align*}

where the second equality uses the Nishimori identity (<ref>). Noticing that the Gibbs average $\langle \sigma_i\rangle$ is a measurable function of the data by (<ref>) and applying the Nishimori identity (<ref>) completes the proof.

Before leveraging this result to compute the Gateaux derivative (<ref>), we begin with some distributional identities which will simplify the calculation. Fix a finite measure $\mu\in \M_+$ and a probability measure $\nu\in \Pr[-1,1]$. Let $s=\mu[-1,1]$ and fix $\epsilon>0$. Introduce the measure $\lambda=\mu+\epsilon \nu$ and observe that

\begin{equation}\label{eqn: SBM sum of measures is mixture}
\bar{\lambda}=\frac{\lambda}{s+\epsilon}=\frac{s}{s+\epsilon}\bar{\mu}+\frac{\epsilon}{s+\epsilon}\nu.
\end{equation}

Denote by $(x_{i,k})$ i.i.d. random variables sampled from the measure $\bar{\mu}$, and write $(y_{i,k})$ for i.i.d. random variables sampled from the measure $\nu$. Given i.i.d. random variables $(w_{i,k})$ with distribution $\smash{\Ber(\frac{s}{s+\epsilon})}$, notice that by (<ref>) the random variables

\begin{equation}
\end{equation}

are i.i.d. with distribution $\bar{\lambda}$. In particular, if $(\tG_{i,k}^z)$ are independent random variables with conditional distribution (<ref>), the Hamiltonian (<ref>) may be expressed as

\begin{equation}\label{eqn: SBM GD distributional identity}
\widetilde{H}_N^{s+\epsilon,\bar{\lambda}}(\sigma)\stackrel{d}{=}\sum_{i\leq N}\sum_{k\leq \Pi_{i,s+\epsilon}}\log\bigg[\big(c+\Delta \sigma_iz_{i,k}\big)^{\tG_{i,k}^z}\Big(1-\frac{c+\Delta \sigma_iz_{i,k}}{N}\Big)^{1-\tG_{i,k}^z}\bigg].
\end{equation}

This identity will allow us to linearize the enriched free energy (<ref>) upon realizing that

\begin{equation}
\overline{F}_N(t,\mu+\epsilon \nu)=\widetilde{F}_N\big(t,s+\epsilon,\bar \lambda\big).
\end{equation}

To make the computation as clear as possible, it will be convenient to introduce additional notation. In the same spirit as (<ref>), for each $i\leq N$, write

\begin{align}\label{eqn: SBM conditioned Hamiltonian 3}
\widetilde{H}_{N,m}^{s,i,+}(\sigma)&=\widetilde{H}_{N,m}^{s,i}+\log\bigg[\big(c+\Delta \sigma_iy_i\big)^{\tG_{i}^y}\Big(1-\frac{c+\Delta \sigma_iy_{i}}{N}\Big)^{1-\tG_{i}^y}\bigg]
\end{align}

for the Hamiltonian (<ref>) conditional on the $i$'th Poisson sum containing $m+1$ terms one of which is sampled from the measure $\nu$. Denote by

\begin{equation}
Z_{N,m}^{s,i,+}=\int_{\Sigma_N} \exp\big(H_N^t(\sigma)+\widetilde{H}_{N,m}^{s,i,+}(\sigma)\big)\ud P_N^*
\end{equation}

its associated partition function. It will be useful to record the following consequence of Taylor's theorem,

\begin{equation}\label{eqn: SBM GD Taylor}
\Big(\frac{s}{s+\epsilon}\Big)^{\sum_{i\leq N}m_i}=1-\frac{\epsilon}{s+\epsilon}\sum_{i\leq N}m_i+o(\epsilon),
\end{equation}

as well as the elementary identity,

\begin{equation}\label{eqn: SBM Poisson density multiplication}
\end{equation}

For any $t>0$, $\mu \in \M_+$ and $\nu \in \Pr[-1,1]$,

\begin{align}\label{eqn: SBM enriched free energy Gateaux derivative}
D_\mu \overline{F}_N(t,\mu; \nu)=\E\big(c+\Delta \langle \sigma_i\rangle y_i\big)\log\big(c&+\Delta\langle \sigma_i\rangle y_i\big)\notag\\
&+N\E\Big(1-\frac{c+\Delta \langle \sigma_i\rangle y_i}{N}\Big)\log\Big(1-\frac{c+\Delta\langle \sigma_i\rangle y_i}{N}\Big)
\end{align}

where the index $i\in \{1,\ldots,N\}$ is uniformly sampled and the random variables $(y_i)$ are sampled from the measure $\nu$ independently of all other sources of randomness.

Leveraging (<ref>), conditioning on the number of random variables $(w_{i,k})$ that are equal to one and using (<ref>), we see that

\begin{align*}
\widetilde{F}_N(t,s+\epsilon,\bar \lambda)=\widetilde{F}_N(t,s+\epsilon, \bar \mu)&-\frac{\epsilon}{s+\epsilon}\sum_{i\leq N}\sum_{m\geq 0}m\pi((s+\epsilon)N,m)\frac{1}{N}\E\log Z_{n,m}^{s+\epsilon,i}\\
&+\frac{\epsilon}{\epsilon+s}\sum_{i\leq N}\sum_{m\geq 0}(m+1)\pi((s+\epsilon)N,m+1)\frac{1}{N}\E\log Z_{N,m}^{s+\epsilon,i,+}+o(\epsilon).
\end{align*}

Keeping in mind (<ref>), this simplifies to

\begin{align}\label{eqn: SBM enriched free energy GD key}
\widetilde{F}_N\big(t,s+\epsilon,\bar{\lambda}\big)=\widetilde{F}_N&(t,s+\epsilon,\bar{\mu})\notag\\
&+\epsilon \sum_{i\leq N}\sum_{m\geq 0}\pi\big((s+\epsilon)N,m\big)\bigg(\E\log \frac{Z_{N,m}^{s+\epsilon,i,+}}{Z_{N,m}^{s+\epsilon,i}}-\E\log \frac{Z_{N,m+1}^{s+\epsilon,i}}{Z_{N,m}^{s+\epsilon,i}}\bigg)+o(\epsilon).
\end{align}

For each $i\leq N$, denote by $x_i$ a sample from the measure $\bar{\mu}$ and by $y_i$ a sample from the measure $\nu$. Write $\tG_i^x$ and $\tG_i^y$ for random variables with conditional distribution (<ref>). These random variables are taken to be independent for different values of $i\leq N$, and independent of all other sources of randomness. Combining (<ref>) with (<ref>) and the distributional identity

$$Z_{N,m}^{s+\epsilon,i,+}\stackrel{d}{=}\int_{\Sigma_N} \big(c+\Delta \sigma_i y_i\big)^{\tG_i^y}\Big(1-\frac{c+\Delta \sigma_i y_i}{N}\Big)^{1-\tG_i^y}\exp\big(H_N^t(\sigma)+\widetilde{H}_{N,m}^{s+\epsilon,i}(\sigma)\big)\ud P_N^*(\sigma)$$

\begin{align}\label{eqn: SBM enriched free energy Gateaux derivative key}
\widetilde{F}_N(t,s+\epsilon,\bar{\lambda})=\widetilde{F}_N(t,s+&\epsilon,\bar{\mu})+\epsilon \sum_{i\leq N}\E\log \bigg\langle\big(c+\Delta \sigma_iy_i\big)^{\tG_i^y}\Big(1-\frac{c+\Delta \sigma_iy_i}{N}\Big)^{1-\tG_i^y} \bigg\rangle\notag\\
&\quad -\epsilon \sum_{i\leq N}\E\log \bigg\langle\big(c+\Delta \sigma_ix_i\big)^{\tG_i^x}\Big(1-\frac{c+\Delta \sigma_ix_i}{N}\Big)^{1-\tG_i^x} \bigg\rangle+o(\epsilon).
\end{align}

Together with (<ref>), this implies that

\begin{align*}
D_\mu \overline{F}_N(t,\mu;\nu)&=\lim_{\epsilon \to 0}\frac{\widetilde{F}_N(t,s+\epsilon,\bar{\lambda})-\widetilde{F}_N(t,s+\epsilon,\bar{\mu})}{\epsilon}+\partial_s \overline{F}_N(t,s,\bar{\mu})\\
&=\sum_{i\leq N}\E\log \bigg\langle \big(c+\Delta \sigma_iy_i\big)^{\tG_i^y}\Big(1-\frac{c+\Delta \sigma_iy_i}{N}\Big)^{1-\tG_i^y} \bigg\rangle.
\end{align*}

Notice that the Gibbs averages in (<ref>) depend on $\epsilon$, so in taking this limit we have implicitly used the fact that this dependence is continuous. Proceeding exactly as in the proof of <Ref> (after display (<ref>)) completes the proof.

To compare (<ref>) with the time-derivative of the enriched free energy in <Ref> it will be convenient to once again Taylor expand the logarithm. We will write

\begin{align}\label{eqn: SBM Gateaux derivative density}
D_\mu \overline{F}_N(t,\mu,x)=\E\big(c+\Delta \langle \sigma_i\rangle x\big)\log\big(c&+\Delta\langle \sigma_i\rangle x\big)\notag\\
&+N\E\Big(1-\frac{c+\Delta \langle \sigma_i\rangle x}{N}\Big)\log\Big(1-\frac{c+\Delta\langle \sigma_i\rangle x}{N}\Big)
\end{align}

for the density of the Gateaux derivative $\smash{D_\mu \overline{F}_N(t,\mu)}$. Taylor expanding the logarithm shows that

\begin{equation}\label{eqn: SBM enriched free energy approximate Gateaux derivative}
D_\mu \overline{F}_N(t,\mu,x)=\E\big(c+\Delta \langle \sigma_i\rangle x\big)\log \big(c+\Delta \langle\sigma_i\rangle x\big)-c-\Delta \m x+\BigO(N^{-1}).
\end{equation}

For every $t>0$ and $\mu \in \M_+$,

\begin{equation}\label{eqn: SBM enriched free energy Gateaux derivative Taylor}
D_\mu \overline{F}_N(t,\mu,x)=\big(c+\Delta \m x\big)\log(c)+c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\langle R_{[n]}\rangle x^n-c+\BigO(N^{-1}).
\end{equation}

Fix $\nu\in \Pr[-1,1]$. A Taylor expansion of the logarithm shows that

\begin{align}\label{eqn: SBM enriched free energy Gateaux derivative rep1 key}
\E\big(c+\Delta \langle \sigma_i\rangle y_i\big)\log\big(c+\Delta \langle \sigma_i\rangle y_i\big)=\big(c+\Delta \m \E y_1\big)&\log(c)\notag\\
&-\sum_{n\geq 1}\frac{(-\Delta/c)^n}{n}\E\big(c+\Delta\langle\sigma_i\rangle y_i\big)y_i^n\langle \sigma_i\rangle^n,
\end{align}

where we have used that $y_i$ is sampled from $\nu\in \Pr[-1,1]$ and is independent of all other sources of randomness.
Since $\abs{\Delta}\leq c$ and $\E \langle \sigma_i\rangle=\m$ by the Nishimori identity,

\begin{align*}
\sum_{n\geq 1}\frac{(-\Delta/c)^n}{n}\E\big(c+\Delta \langle \sigma_i\rangle y_i\big)y_i^n\langle \sigma_i\rangle^n&=\sum_{n\geq 1}\frac{(-\Delta/c)^n}{n}\big(c\E y_i^n\E\langle \sigma_i\rangle^n+\Delta \E y_i^{n+1}\E \langle\sigma_i\rangle^{n+1}\big)\\
&=-\Delta \E y_i\E\langle \sigma_i\rangle+c\sum_{n\geq 2}\bigg(\frac{(-\Delta/c)^n}{n}-\frac{(-\Delta/c)^n}{n-1}\bigg)\E y_i^n\E\langle \sigma_i\rangle^n\\
&=-\Delta \m \E y_1-c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)} \E\langle R_{[n]}\rangle\E y_i^n.
\end{align*}

Substituting this into (<ref>) and recalling (<ref>) completes the proof.

This result implies that the Gateaux derivative density (<ref>) is close to an element in the cone of functions (<ref>). Indeed, if $\mu^*=\L(\langle \sigma_i\rangle)$ denotes the law of the Gibbs average of a uniformly sampled spin coordinate, then (<ref>) may be formally rewritten as

\begin{equation}\label{eqn: SBM enriched free energy in cone}
D_\mu \overline{F}_N(t,\mu,x)\approx \int_{-1}^1 g(xy)\ud \mu^*(y)=G_{\mu^*}(x),
\end{equation}

using the Nishimori identity (<ref>) to assert that $\E\langle \sigma_i \rangle = \m$. It follows by another application of the Nishimori identity that

\begin{equation}
\C_\infty\big(D_\mu \overline{F}_N(t,\mu)\big)\approx \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\langle R_{[n]}\rangle\big)^2-\frac{c}{2}.
\end{equation}

Comparing this with the expression in <Ref>, and assuming the approximate concentration of all the multi-overlaps,

\begin{equation}\label{eqn: SBM approximate multioverlap concentration}
\E\langle R_{[n]}^2\rangle\approx \big(\E\langle R_{[n]}\rangle\big)^2,
\end{equation}

reveals that, up to a small error, the enriched free energy (<ref>) formally satisfies the infinite-dimensional Hamilton-Jacobi equation (<ref>),

\begin{equation}
\partial_t f(t,\mu)=\C_\infty(D_\mu f(t,\mu)) \,\,\, \text{ on } \Rpp\times \M_+.
\end{equation}

As already mentioned in the introduction, the difficulty in making this informal derivation rigorous is that we do not expect the concentration of the multi-overlaps (<ref>) to be valid for each choice of the parameters $t$ and $\mu$. On the positive side, the arguments in [12] reveal that the concentration of the multi-overlaps can be enforced through a small perturbation of the Hamiltonian which does not affect the limit of the free energy, for most values of the perturbation parameters. Yet, the solution theory to Hamilton-Jacobi equations is rather sensitive to details, and in particular, this control “for most values” or after a suitable local averaging is not sufficient to allow us to conclude. The next section will clarify the nature of this solution theory.

§ WELL-POSEDNESS OF THE HAMILTON-JACOBI EQUATION

In this section, we leverage the main result in [30] to establish the well-posedness of the infinite-dimensional Hamilton-Jacobi equation  (<ref>). The first order of business will be to identify the initial condition in  (<ref>). For each integer $N\geq 1$, let

\begin{equation}\label{eqn: SBM HJ initial condition}
\psi_N(\mu)=\overline{F}_N(0,\mu)=\widetilde{F}_N(0,\mu[-1,1],\bar \mu),
\end{equation}

and notice that the initial condition $\psi:\M_+\to \R$ in  (<ref>) should be the limit of the initial conditions $(\psi_N)$. Following [11], we will first compute this limit for discrete measures $\mu \in \M_+$, and later show that the convergence may be extended to all measures in $\M_+$ through a density argument. Given a measure $\mu\in \M_+$, it will be convenient to write $\Pi_{\pm}(\mu)$ for the generalized Poisson point process with mean measure $(c\pm \Delta x)\ud \mu(x)$ on $[-1,1]$. By generalized Poisson process we mean that an atom $a\in [-1,1]$ with $\mu(\{a\})>0$ is counted with independent Poisson multiplicity having mean $(c\pm \Delta a)\mu(\{a\})$. It turns out that the limit of the initial conditions (<ref>) is given by an appropriate average with respect to the randomness of the generalized Poisson point processes $\Pi_\pm(\mu)$, which we denote by $\E$ as usual.

For any discrete measure $\mu \in \M_+$, the sequence $(\psi_N(\mu))$ converges to

\begin{align}\label{eqn: SBM asymptotic initial condition}
\psi(\mu)=-\mu[-1,1] c+&p\E \log \int_{\Sigma_1} e^{-\mu[-1,1]\Delta \sigma \E x_{1}}\prod_{x\in \Pi_+(\mu)}(c+\Delta \sigma x)\ud P^*(\sigma)\notag\\
&+(1-p)\E \log \int_{\Sigma_1} e^{-\mu[-1,1]\Delta \sigma \E x_{1}}\prod_{x\in \Pi_-(\mu)}(c+\Delta \sigma x)\ud P^*(\sigma),
\end{align}

where $x_{1}$ has law $\bar \mu$.

Since $\mu\in\M_+$ is a discrete measure, it may be expressed as

$$\mu=\sum_{\ell\leq K}p_\ell\delta_{a_\ell}$$

for some integer $K\geq 1$, some atoms $a_\ell\in [-1,1]$ and some weights $p_\ell\geq 0$. Let $s=\mu[-1,1]$, and introduce independent Poisson random variables $\Pi_{i,s}\sim \Poi(sN)$ in such a way that

$$\psi_N(\mu)=\frac{1}{N}\sum_{i\leq N}\E \log \int_{\Sigma_1} \exp \sum_{k\leq \Pi_{i,s}}\log\bigg[(c+\Delta \sigma x_{i,k})^{\tG_{i,k}^x}\Big(1-\frac{c+\Delta \sigma x_{i,k}}{N}\Big)^{1-\tG_{i,k}^x}\bigg]\ud P^*(\sigma),$$

where $(x_{i,k})$ are i.i.d. random variables with law $\bar \mu$. Since each of the expectations in this average is the same,

\begin{equation}\label{eqn: SBM asymptotic initial condition psi}
\psi_N(\mu)=\E \log \int_{\Sigma_1} \exp \sum_{k\leq \Pi_{1,s}}\log\bigg[(c+\Delta \sigma x_{k})^{\tG_{k}^x}\Big(1-\frac{c+\Delta \sigma x_{k}}{N}\Big)^{1-\tG_{k}^x}\bigg]\ud P^*(\sigma),
\end{equation}

where $(x_k)$ are i.i.d. random variables with law $\bar \mu$ and $\tG_k^x$ has conditional distribution (<ref>) for $i=1$ and $x_{1,k}$ is replaced by $x_k$. To simplify this further, introduce the random index sets

$$\I_0=\big\{k\leq \Pi_{1,s}\mid \tG_{k}^x=0\big\} \quad \text{and} \quad \I_1=\big\{k\leq \Pi_{1,s}\mid \tG_{k}^x=1\big\}.$$

Decomposing the sum in (<ref>) according to the partition $\{k\leq \Pi_{1,s}\}=\I_0\sqcup \I_1$ and applying Taylor's theorem to the logarithm reveals that

$$\psi_N(\mu)=\E\log \int_{\Sigma_1}\prod_{k\in \I_1}(c+\Delta \sigma x_{k})\exp\Big(-\frac{\Delta \sigma}{N}\sum_{k\in \I_0}x_{k}\Big)\ud P^*(\sigma)-\Big(\frac{c}{N}+\BigO\big(N^{-2}\big)\Big)\E\lvert \I_0\rvert.$$

Conditionally on $\sigma^*$, $\Pi_{1,s}$ and $(x_{k})$, the random variable $\abs{\I_0}$ is a sum of Bernoulli random variables with probability of success $\smash{1-\frac{c+\Delta \sigma_1^*x_{k}}{N}}$. It therefore has mean

\begin{equation}\label{eqn: SBM asymptotic initial condition I0 mean}
\E\lvert \I_0\rvert=\E\Pi_{1,s}\E\Big(1-\frac{c+\Delta \sigma_1^*x_{1}}{N}\Big)=sN\Big(1-\frac{c+\Delta \m \E x_{1}}{N}\Big)
\end{equation}

and variance bounded by

\begin{equation}\label{eqn: SBM asymptotic initial condition I0 variance}
\Var\abs{\I_0}=\E\Pi_{1,s}\E\Big(1-\frac{c+\Delta \sigma_1^*x_{1}}{N}\Big)\Big(\frac{c+\Delta \sigma_1^*x_{1}}{N}\Big)\leq s(c+\abs{\Delta}).
\end{equation}

Using (<ref>) and introducing the random index sets $\I_1^\ell = \{k\in \I_1\mid x_{k}=a_\ell\}$ reveals that

$$\psi_N(\mu)=\E\log \int_{\Sigma_1}\prod_{\ell\leq K}\prod_{k\in \I_1^\ell}(c+\Delta \sigma a_\ell)\exp\Big(-\frac{\Delta \sigma}{N}\sum_{k\in \I_0}x_{k}\Big)\ud P^*(\sigma)-cs+\BigO\big(N^{-1}\big).$$

Observe that for any $\sigma\in \Sigma_1$,

\begin{align*}
\E \Big\lvert -\frac{\Delta \sigma}{N}\sum_{k\in \I_0}x_{k}+\Delta \sigma s \E x_{1}\Big\rvert&\leq \abs{\Delta}s \E \Big\lvert \frac{1}{Ns}\sum_{k\in \I_0}x_{k}-\E x_{1}\Big\rvert\\
&\leq \abs{\Delta}s \E\Big\lvert \frac{1}{Ns}\sum_{k\leq Ns}x_{k}-\E x_{1}\Big\rvert+\frac{\Delta}{N}\big(\Var\abs{\I_0}+\lvert \E\abs{\I_0}-Ns\rvert\big)
\end{align*}

where we have used the fact that $\abs{x_{k}}\leq 1$ and Jensen's inequality in the second inequality. Recalling (<ref>) and invoking the strong law of large numbers shows that

\begin{equation}\label{eqn: SBM asymptotic initial condition pre-limit}
\psi_N(\mu)=\E\log \int_{\Sigma_1}e^{-\Delta \sigma s\E x_{1}}\prod_{\ell\leq K}\prod_{k\in \I_1^\ell}(c+\Delta \sigma a_\ell)\ud P^*(\sigma)-cs+o_N(1).
\end{equation}

The Poisson coloring theorem (see Chapter 5 in [37]) implies that $\abs{\I_1^\ell}$ is a Poisson random variable with mean

$$\E\Pi_{1,s}\cdot \P\{\tG_{1}^x=1, x_{1}=a_\ell\}=sN\cdot \frac{c+\Delta \sigma_1^*a_\ell}{N}\cdot \bar \mu(a_\ell)=\big(c+\Delta \sigma_1^*a_\ell\big) \mu(a_\ell),$$

so averaging (<ref>) over the randomness of $\sigma^*$ yields

\begin{align*}
\psi_N(\mu)=-&cs+p\E\log \int_{\Sigma_1}e^{-\Delta \sigma s\E x_{1}}\prod_{x\in \Pi_+(\mu)}(c+\Delta \sigma x)\ud P^*(\sigma)\\
&+(1-p)\E\log \int_{\Sigma_1}e^{-\Delta \sigma s\E x_{1}}\prod_{x\in \Pi_-(\mu)}(c+\Delta \sigma x)\ud P^*(\sigma)+o_N(1).
\end{align*}

This completes the proof.

To extend this convergence to all measures in $\M_+$, we will rely upon the continuity of the functional (<ref>) with respect to the Wasserstein distance on the space of probability measures,

\begin{align}
W(\P,\Q)&=\sup\bigg\{\Big\lvert \int_{-1}^1 h(x)\ud \P(x)-\int_{-1}^1 h(x)\ud \Q(x)\Big\rvert \mid \norm{h}_{\text{Lip}}\leq 1\bigg\} \label{eqn: SBM Wasserstein}\\
&=\inf\bigg\{\Big\lvert \int_{[-1,1]^2}\abs{x-y}\ud\nu(x,y) \mid \nu\in \Pr\big([-1,1]^2\big) \text{ has marginals } \P \text{ and } \Q\bigg\}.\label{eqn: SBM Wasserstein inf}
\end{align}

Here $\norm{\cdot}_{\mathrm{Lip}}$ denotes the Lipschitz semi-norm

\begin{equation}
\norm{h}_{\mathrm{Lip}}=\sup_{x\neq x'\in [-1,1]}\frac{\abs{h(x)-h(x')}}{\abs{x-x'}}
\end{equation}

defined on the space of functions $h:[-1,1]\to \R$. This continuity will be obtained as a consequence of the following uniform bound on the spatial derivatives of the Gateaux derivative density (<ref>).

For every $N$ large enough (relative to $c$), $\mu\in \M_+$, $t\geq 0$ and $x\in [-1,1]$,

\begin{align}
\big\lvert D_\mu \overline{F}_N(t,\mu,x)\big\rvert&\leq 2c\big(2+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta})}\big),\label{eqn: SBM Gateux density bound}\\
\big\lvert \partial_x D_\mu \overline{F}_N(t,\mu,x)\big\rvert&\leq c\big(1+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta})}\big).\label{eqn: SBM derivative of Gateux density bound}
\end{align}

Recall from (<ref>) that

\begin{align*}
D_\mu \overline{F}_N(t,\mu,x)=\E\big(c+\Delta \langle \sigma_i\rangle x\big)\log\big(c&+\Delta\langle \sigma_i\rangle x\big)\notag\\
&+N\E\Big(1-\frac{c+\Delta \langle \sigma_i\rangle x}{N}\Big)\log\Big(1-\frac{c+\Delta\langle \sigma_i\rangle x}{N}\Big).
\end{align*}

It follows by a direct computation that

$$\partial_x D_\mu \overline{F}_N(t,\mu,x)=\Delta \E \langle \sigma_i\rangle\log\big(c+\Delta\langle \sigma_i\rangle x\big)-\Delta \E\langle \sigma_i\rangle \log\Big(1-\frac{c+\Delta\langle \sigma_i\rangle x}{N}\Big).$$

Since all spin configuration coordinates are bounded by one and $\abs{\Delta}<c$, Taylor's theorem implies that for $N$ large enough,

\begin{align*}
\big\lvert D_\mu \overline{F}_N(t,\mu,x)\big\rvert&\leq 2c\big(2+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta})}\big),\\
\big\lvert \partial_x D_\mu \overline{F}_N(t,\mu,x)\big\rvert&\leq c\big(1+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta}\big)}\big).
\end{align*}

Notice that the choice of $N$ only depends on $c$ as $x\in [-1,1]$ and $\abs{\Delta}\leq c$. This completes the proof.

The initial condition $\psi_N$ satisfies the Lipschitz bound

\begin{equation}
\abs{\psi_N(\P)-\psi_N(\Q)}\leq c\big(1+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta})}\big)\big)W(\P,\Q)
\end{equation}

for all probability measures $\P,\Q\in \Pr[-1,1]$.

The fundamental theorem of calculus and the definition of the Gateaux derivative in (<ref>) imply that

$$\psi_N(\P)-\psi_N(\Q)=\int_0^1 \frac{\mathrm{d}}{\mathrm{d} t}\psi_N\big(\Q+t(\P-\Q)\big)\ud t=\int_0^1 D_\mu\psi_N \big(\Q+t(\P-\Q); \P-\Q\big)\ud t.$$

Since the Gateaux derivative of the initial condition admits a continuously differentiable density,

$$\abs{\psi_N(\P)-\psi_N(\Q)}\leq \int_0^1\Big\lvert  \int_{-1}^1 f_t(x)\ud \P(x)-\int_{-1}^1 f_t(x)\ud \Q(x)\Big\rvert\ud t$$

for the continuously differentiable function $f_t(x)=D_\mu\psi_N(\Q+t(\P-\Q),x)$. The mean value theorem and (<ref>) reveal that $\smash{\norm{f_t}_{\text{Lip}}\leq c\big(1+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta})}\big)}$. It follows by definition of the Wasserstein distance (<ref>) that

$$\abs{\psi_N(\mu)-\psi_N(\nu)}\leq  c\big(1+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta})}\big)W(\P,\Q).$$

This completes the proof.

The functional $\psi:\M_+\to \R$ defined by (<ref>) is continuous with respect to the weak convergence of measures. This means that for any sequence of measures $(\mu_n)\subset \M_+$ converging weakly to a measure $\mu\in \M_+$, we have

\begin{equation}
\lim_{N\to \infty}\psi(\mu_n)=\psi(\mu).
\end{equation}

To alleviate the exposition, we will instead prove the continuity of the functional

$$\psi^1(\mu)=\E\log\int_{\Sigma_1}e^{-\mu[-1,1]\Delta \sigma \E x_1}\prod_{x\in \Pi_+(\mu)}(c+\Delta \sigma x)\ud P^*(\sigma)$$

with respect to the weak convergence of measures. Up to an additive constant, the asymptotic initial condition $\psi(\mu)$ is the weighted average of $\psi^1(\mu)$ and another functional of the same form whose continuity can be established using an identical argument, so this suffices. For each measure $\mu\in \M_+$ introduce the Hamiltonian

$$H(\sigma,\mu)=-\Delta \sigma \int_{-1}^1 x\ud \mu(x)+\sum_{x\in \Pi_+(\mu)}(c+\Delta\sigma x)$$

in such a way that the asymptotic initial condition is its associated free energy,

$$\psi^1(\mu)=\E\log\int_{\Sigma_1}\exp H(\sigma,\mu)\ud P^*(\sigma).$$

Consider a sequence of measures $(\mu_n)\subset \M_+$ converging weakly to a measure $\mu\in \M_+$, and let $\Pi_n$ and $\Pi$ be independent Poisson random variables with means $\mu_n[-1,1]$ and $\mu[-1,1]$, respectively. Introduce a collection $\smash{(X_k^n,X_k)_{k\in \N}}$ of i.i.d. random vectors with joint law $\smash{\nu\in \Pr\big([-1,1]^2\big)}$ having marginals $\smash{\bar{\mu}_n}$ and $\smash{\bar{\mu}}$. In this way, the coordinates $\smash{(X_k^n)_{k\in \N}}$ are i.i.d. with law $\smash{\bar{\mu}_n}$, the coordinates $\smash{(X_k)_{k\in \N}}$ are i.i.d. with law $\smash{\bar \mu}$, and we have the equalities in distribution

$$\sum_{x\in \Pi_+(\mu_n)}(c+\Delta \sigma x)\stackrel{d}{=}\sum_{k\leq \Pi_n}\big(c+\Delta \sigma X_k^n\big) \quad \text{and} \quad \sum_{x\in \Pi_+(\mu)}(c+\Delta x)\stackrel{d}{=}\sum_{k\leq \Pi}\big(c+\Delta \sigma X_k\big).$$

It follows that for any $\sigma\in \Sigma_1$,

$$\abs{H(\sigma,\mu_n)-H(\sigma,\mu)}\leq \abs{\Delta}\Big\lvert \int_{-1}^1 x\ud \mu_n(x)-\int_{-1}^1 x\ud \mu(x)\Big\rvert+c\big\lvert \Pi_n-\Pi\big\rvert+\abs{\Delta}\Big\lvert \sum_{k\leq \Pi_n}X_k^n-\sum_{k\leq \Pi}X_k\Big\rvert,$$

and therefore,

$$\big\lvert \psi^1(\mu_n)-\psi^1(\mu)\big\rvert\leq \abs{\Delta}\Big\lvert \int_{-1}^1 x\ud \mu_n(x)-\int_{-1}^1 x\ud \mu(x)\Big\rvert+c\E\big\lvert \Pi_n-\Pi\big\rvert+\abs{\Delta}\E\Big\lvert \sum_{k\leq \Pi_n}X_k^n-\sum_{k\leq \Pi}X_k\Big\rvert.$$

To simplify this further, define the random variable $\Pi'_n=\min(\Pi_n,\Pi)$, introduce a Poisson random variable $\smash{\Pi''_n}$ independent of all other sources of randomness with mean $\smash{\abs{\mu_n[-1,1]-\mu[-1,1]}}$, and define the collection of random variables $\smash{(Z_k^n)}$ by

X_k^n& \text{if } \Pi_n'=\Pi\\
X_k& \text{otherwise}
\end{cases}.$$

The basic properties of Poisson random variables and the fact that $\smash{\abs{Z_k^n}\leq 1}$ imply that

\begin{align*}
\big\lvert \psi^1(\mu_n)-\psi^1(\mu)\big\rvert&\leq c\abs{\Delta}\Big\lvert \int_{-1}^1 x\ud(\mu_n-\mu)(x)\Big\rvert+c\E\Pi_n''+\abs{\Delta}\E\sum_{k\leq \Pi_n''}\big\lvert Z_k^n\big\rvert+\abs{\Delta}\E\sum_{k\leq \Pi_n'}\big\lvert X_k^n-X_k\big\rvert\\
&\leq c\bigg(\Big\lvert \int_{-1}^1 x\ud(\mu_n-\mu)(x)\Big\rvert+2\E\Pi_n''+\E\Pi_n'\int_{[-1,1]^2}\abs{x-y}\ud \nu(x,y)\rvert\bigg).
\end{align*}

Taking the infimum over all couplings $\smash{\nu\in \Pr\big([-1,1]^2\big)}$ with marginals $\smash{\bar{\mu}_n}$ and $\smash{\bar \mu}$ reveals that for $n$ large enough,

$$\big\lvert \psi^1(\mu_n)-\psi^1(\mu)\big\rvert\leq c\bigg(\Big\lvert \int_{-1}^1 x\ud(\mu_n-\mu)(x)\Big\rvert+2\big\lvert\mu_n[-1,1]-\mu[-1,1]\big\rvert+3\mu[-1,1]W\big(\bar{\mu}_n,\bar \mu\big)\bigg),$$

where we have used that $\E \Pi_n'\leq \E \Pi+\E\Pi_n\leq 3\mu[-1,1]$ for $n$ large enough as $\mu_n$ converges weakly to $\mu$. Letting $n$ tend to infinity and recalling that the Wasserstein distance (<ref>) metrizes the weak convergence of probability measures completes the proof.

For any measure $\mu \in \M_+$, the sequence $(\psi_N(\mu))$ converges to (<ref>).

Consider a sequence $(\mu_n)_{n\geq 1}$ of discrete measures such that $\mu_n[-1,1]=\mu[-1,1]$ for all $n\geq 1$ and $\bar \mu_n\to \bar \mu$ with respect to the Wasserstein distance (<ref>). By the triangle inequality and <Ref>,

\begin{align*}
\big\lvert \psi(\mu)-\psi_N(\mu)\big\rvert&\leq \big\lvert \psi(\mu)-\psi(\mu_n)\big\rvert+\big\lvert \psi(\mu_n)-\psi_N(\mu_n)\big\rvert+\big\lvert \psi_N(\mu_n)-\psi_N(\mu)\big\rvert\notag\\
&\leq \big\lvert \psi(\mu)-\psi(\mu_n)\big\rvert+\big\lvert \psi(\mu_n)-\psi_N(\mu_n)\big\rvert\\
&\qquad\qquad\qquad\quad\,\,\,\,\,\,\,+c\big(1+\abs{\log(2c)}+\abs{\log(c-\abs{\Delta})}\big)W\big(\bar{\mu}_n,\bar \mu\big)
\end{align*}

where we have used the fact that $\mu_n[-1,1]=\mu[-1,1]$. Combining <Ref> with <Ref> to let $N\to \infty$ and then $n\to \infty$ completes the proof.

This result identifies the initial condition for the infinite-dimensional Hamilton-Jacobi equation (<ref>).
We may now leverage the main result in [30] to establish the well-posedness of this infinite-dimensional Hamilton-Jacobi equation. Before we do this, let us introduce the notation used in [30]; for more details and motivation regarding this notation, we encourage the reader to consult [30].
Given an integer $K\geq 1$, we write

\begin{equation}\label{eqn: SBME dyadic rationals}
\D_K=\Big\{k=\frac{i}{2^K} \mid -2^K\leq i<  2^K\Big\}
\end{equation}

for the set of dyadic rationals on $[-1,1]$ at scale $K$.
We denote the set of discrete measures supported on the dyadic rationals at scale $K$ in the interval $[-1,1]$ by

\begin{equation}
\M^{(K)}_+=\Big\{\mu\in \M_+\mid \mu=\frac{1}{\abs{\D_K}}\sum_{k\in \D_K}x_k\delta_k\text{ for some } x=(x_k)_{k\in \D_K}\in \Rp^{\D_K}\Big\},
\end{equation}

and we project a general measure $\mu \in \M_+$ onto $\M_+^{(K)}$ via the mapping

\begin{equation}\label{eqn: SBME weights of dyadic measure}
x^{(K)}(\mu)=\big(\abs{\D_K}\mu\big[k,k+2^{-K}\big)\big)_{k\in \D_K}
\in \Rp^{\D_K},
\end{equation}

whose inverse assigns to each $\smash{x \in \Rp^{\D_K}}$ the measure

\begin{equation}
\mu^{(K)}_x=\frac{1}{\abs{\D_K}}\sum_{k\in \D_K}x_{k}\delta_k \in \M_+^{(K)}.
\end{equation}

We identify any real-valued function $\smash{f:\Rp\times \M_+^{(K)}\to \R}$ with the function

\begin{equation}
\end{equation}

defined on $\smash{\Rp\times \Rp^{\D_K}}$, and we identify the projection of the initial condition with the function

\begin{equation}\label{eqn: SBM projected modified initial condition}
\psi^{(K)}(x)=\psi\big(\mu_x^{(K)}\big)
\end{equation}

defined on $\smash{\Rp^{\D_K}}$. The Gateaux derivative of a real-valued function $\smash{f:\Rp\times \M_+^{(K)}\to \R}$ at the measure $\smash{\mu\in \M_+^{(K)}}$ becomes the gradient $\smash{\abs{\D_K}\nabla f^{(K)}(t,x^{(K)}(\mu))}$ by duality. Indeed,

\begin{equation}\label{eqn: SBM Gateux derivative projection}
D_\mu f(t,\mu; \nu)=\frac{\mathrm{d}}{\mathrm{d} \epsilon}\Big|_{\epsilon=0}f^{(K)}(t,x^{(K)}(\mu)+\epsilon x^{(K)}(\nu))=\nabla f^{(K)}(t,x^{(K)}(\mu))\cdot x^{(K)}(\nu)
\end{equation}

for any direction $\smash{\nu\in \M_+^{(K)}}$. We fix $b>0$ large enough so the modified kernel

\begin{equation}
\label{e.def.tdg}
\td g_b (z) = g(z) + b
\end{equation}

is strictly positive, and we introduce the symmetric matrices

\begin{equation}\label{eqn: SBM matrix tGK}
G^{(K)}=\frac{1}{\abs{\D_K}^2}\big(g(kk')\big)_{k,k'\in \D_K} \quad \text{and} \quad \td G_b^{(K)}=\frac{1}{\abs{\D_K}^2}\big(\td g_b(kk')\big)_{k,k'\in \D_K}
\end{equation}

in $\smash{\R^{\D_K\times \D_K}}$. We also define the projected cone

\begin{equation}
\widetilde{\CC}_{b,K}=\Big\{\widetilde{G}_b^{(K)}x\in \R^{\D_K}\mid x\in \Rp^{\D_K}\Big\},
\end{equation}

the projected non-linearity $\widetilde{\C}_{b,K}:\widetilde{\CC}_{b,K}\to \R$ given by

\begin{equation}\label{eqn: projected non-linearity b}
\widetilde{\C}_{b,K}\big(\widetilde{G}^{(K)}_bx\big)=\frac{1}{2}\widetilde{G}_b^{(K)}x\cdot x=\frac{1}{2\abs{\D_K}^2}\sum_{k,k'\in \D_K}\td g_b(kk')x_kx_{k'},
\end{equation}

and the closed convex set

\begin{equation}
\K_{=1,K}=\Big\{G^{(K)}x\in \R^{\D_K}\mid x\in \Rp^{\D_K}\text{ and } \Norm{x}_1= a\Big\}.
\end{equation}

We will measure quantities in the normalized $\ell^1$ and $\ell^{1,*}$ norms,

\begin{equation}\label{eqn: SBME normalized norms}
\Norm{x}_1=\frac{1}{\abs{\D_K}}\sum_{k\in \D_K}\abs{x_{k}} \quad \text{and} \quad \dNorm{1}{y}=\max_{k\in \D_K}\abs{\D_K}\abs{y_{k}},
\end{equation}

and it will be convenient to write
\begin{equation}
B_{K,R}=\big\{y\in \R^{\D_K}\mid \dNorm{1}{y}\leq R\big\}
\end{equation}

for the ball of radius $R>0$ centered at the origin with respect to the normalized-$\ell^{1,*}$ norm in $\smash{\R^{\D_K}}$. Recall that a function $\smash{h:\R^d\to \R}$ is said to be non-decreasing if $h(y)\leq h(y')$ for all $\smash{y,y'\in \R^d}$ with $\smash{y'-y\in \Rp^d}$. Proposition 2.3 in [30] will give the existence of a uniformly Lipschitz continuous and non-decreasing non-linearity $\smash{\td \H_{b,K,R}}$ which agrees with $\smash{\td \C_{b,K}}$ on the ball $\smash{\td \CC_{b,K}\cap B_{K,R}}$, and we will define the solution to the infinite-dimensional Hamilton-Jacobi equation (<ref>) by

\begin{equation}\label{eqn: SBM inf HJ eqn solution}
f(t,\mu)=\lim_{K\to \infty}\bigg(\td f_{b,R}^{(K)}\big(t,x^{(K)}(\mu)\big)-b\Norm{x^{(K)}(\mu)}_1-\frac{bt}{2}\bigg),
\end{equation}

where $\td f^{(K)}_{b,R}:[0,\infty)\times \Rp^{\D_K}\to \R$ is the unique solution to the Hamilton-Jacobi equation

\begin{equation}\label{eqn: SBM projected HJ eqn b}
\partial_t \td f^{(K)}(t,x)=\widetilde{\H}_{b,K, R}\big(\nabla \td f^{(K)}(t,x)\big) \quad\text{on}\quad \Rpp\times \Rpp^{\D_K}
\end{equation}

subject to the projection of the initial condition $\td \psi_{b}:\M_+\to \R$ defined by

\begin{equation}\label{e.def.tdpsi}
\td \psi_{b}(\mu)=\psi(\mu)+b\int_{-1}^1 \ud \mu.
\end{equation}

The fact that the function $f$ defined by (<ref>) does not depend on the choice of the constants $b \in \R$ and $R > 0$ sufficiently large is one of the results established in [30]. To justify this construction rigorously, we must verify that the initial condition $\psi$ satisfies a certain number of hypotheses introduced in [30]. To state these hypotheses, given a closed convex set $\smash{\K\subset \R^{\D_K}}$, write

\begin{equation}\label{eqn: SBM enlarged set}
\K'=\K+B_{K,2^{-K/2}}
\end{equation}

for the neighbourhood of radius $\smash{2^{-K/2}}$ around $\K$ in the normalized-$\ell^{1,*}$ norm, and denote by

\begin{equation}\label{eqn: SBM TV metric}
\TV(\mu,\nu)=\sup\big\{\abs{\mu(A)-\nu(A)}\mid A \text{ is a measurable subset of } [-1,1]\big\}
\end{equation}

the total variation distance on $\M_+$. A non-differential criterion for the gradient of a Lipschitz continuous function to lie in a closed convex set is given in Proposition B.2 of [30].

* The initial condition $\psi:\M_+\to \R$ is Lipschitz continuous with respect to the total variation distance (<ref>),

\begin{equation}
\abs{\psi(\mu)-\psi(\nu)}\leq \norm{\psi}_{\mathrm{Lip},\TV}\TV(\mu,\nu)
\end{equation}

for all measures $\nu,\mu\in \M_+$.

The initial condition $\smash{\psi:\M_+\to \R}$ has the property that each of the projected initial conditions has its gradient in the set $\K_{=1,K}'$,

\begin{equation}
\nabla \psi^{(K)}\in L^\infty\big(\Rp^d;\K_{=1,K}'\big).
\end{equation}

* The initial condition $\psi:\Pr[-1,1]\to \R$ is Lipschitz continuous with respect to the Wasserstein distance (<ref>),

\begin{equation}
\abs{\psi(\P)-\psi(\Q)}\leq \norm{\psi}_{\mathrm{Lip},W} W(\P,\Q)
\end{equation}

for all probability measures $\P,\Q\in \Pr[-1,1]$.

The initial condition $\psi$ in (<ref>) satisfies (<ref>)-(<ref>).

Recall that <Ref> implies the existence of a constant $C>0$ which depends only on $c$ and $\Delta$ such that for every integer $N\geq 1$, $\mu \in \M_+$ and $t\geq 0$,

\begin{equation}\label{eqn: SBM Gateaux derivative bounds modified IC}
\big\lvert D_\mu \overline{F}_N(t, \mu,x)\big\rvert\leq C\quad \text{and} \quad \big\lvert \partial_x D_\mu \overline{F}_N(t,\mu,x)\big\rvert\leq C.
\end{equation}

To establish (<ref>) notice that for every integer $N\geq 1$ and $\mu,\nu\in \M_+$,

$$\psi_N(\mu)-\psi_N(\nu)=\int_0^1 D_\mu\psi_N \big(\nu+t(\mu-\nu); \mu-\nu\big)\ud t=\int_0^1 \int_{-1}^1f_t(x)\ud \big( \mu-\nu\big)(x)\ud t$$

for the continuously differentiable function $\smash{f_t(x)=D_\mu\psi_N \big(\nu+t(\mu-\nu),x\big)}$. To bound this integral by the total variation distance, let $\eta=\mu-\nu\in \M_s$, and use the Hahn-Jordan decomposition to write $\smash{\eta=\eta^+-\eta^-}$ for measures $\smash{\eta^+,\eta^-\in \M_+}$ with the property that for some measurable set $D\subset[-1,1]$ and all measurable sets $E\subset [-1,1]$,

$$\eta^+(E)=\eta(E\cap D)\geq 0\quad \text{and} \quad \eta^-(E)=-\eta(E\cap D^c)\geq 0.$$

The triangle inequality and the first bound in (<ref>) imply that

\begin{align*}
\abs{\psi_N(\mu)-\psi_N(\nu)}&\leq \Big\lvert \int_0^1 \int_{-1}^1 f_t(x)\ud \eta^+(x)\Big\rvert+\Big\lvert\int_0^1 \int_{-1}^1 f_t(x)\ud \eta^-(x)\Big\rvert\\
&\leq C\big(\eta^+[-1,1]+\eta^-[-1,1]\big)\\
&\leq 2C\TV(\mu,\nu).
\end{align*}

Using <Ref> to let $N$ tend to infinity establishes (<ref>). To prove (<ref>) notice that by (<ref>) and (<ref>), for every $\smash{y\in \Rp^{\D_K}}$, there exists some probability measure $\mu^*\in \Pr[-1,1]$ with

If $\mu^*_K=\mu^{(K)}_{x^{(K)}(\mu^*)}\in \M_+^{(K)}$ denotes the projection of $\mu^*$ onto $\M_+^{(K)}$, then the mean value theorem implies that

$$\abs{G_{\mu^*}(k)-G_{\mu^*_K}(k)}\leq \sum_{k'\in \D_K}\int_{k'}^{k'+2^{-K}}\abs{g(ky)-g(kk')}\ud \mu^*(y)\leq \frac{\norm{g'}_\infty}{2^K},$$

where we have used that $\mu^*_K(k')=\mu^*[k',k'+2^{-K})$ for every dyadic $k'\in \D_K$. This means that

so, for $K$ large enough, we have $\smash{\nabla \psi^{(K)}_N(y)=w+\BigO\big(N^{-1}\big)}$ for some $\smash{w\in \K'_{=1,K}}$. At this point fix $c\in \R$ and $\smash{x,x'\in \R^d}$ with  $(x'-x)\cdot z\geq c$ for every $\smash{z\in \K_{=1,K}'}$. The fundamental theorem of calculus reveals that

$$\psi_N^{(K)}(x')-\psi_N^{(K)}(x)=\int_0^1 \nabla \psi_N^{(K)}\big(tx'+(1-t)x\big)\cdot (x'-x)\ud t\geq c+ \BigO\big(N^{-1}\big).$$

Using <Ref> to let $N$ tend to infinity shows that $\smash{\psi^{(K)}(x')-\psi^{(K)}(x)\geq c}$ and Proposition B.2 in [30] gives (<ref>). Finally, (<ref>) is a consequence of <Ref> and <Ref>. This completes the proof.

This result allows us to invoke Proposition 2.3 in [30] to extend the non-linearity $\smash{\td \C_{b,K}}$ in (<ref>). It will be convenient to write $M_b=\max_{[-1,1]}\td g_b$ and $m_b=\min_{[-1,1]}\td g_b>0$.

For every $R>0$, there exists a non-decreasing non-linearity $\smash{\widetilde{\H}_{b,K,R}:\R^{\D_K}\to \R}$ which agrees with $\smash{\widetilde{\C}_{b,K}}$ on $\smash{\widetilde{\CC}_{b,K}\cap B_{K,R}}$ and satisfies the Lipschitz continuity property

\begin{equation}\label{eqn: SBM extending the non-linearity}
\big\lvert \widetilde{\H}_{b,K,R}(y)-\widetilde{\H}_{b,K,R}(y')\big\rvert\leq \frac{8RM_b}{m_b^2}\dNorm{1}{y-y'}
\end{equation}

for all $y,y'\in \R^{\D_K}$.

The well-posedness of the Hamilton-Jacobi equation (<ref>) is the content of Theorem 1.1 in [30]. Before stating this result, let us remind the reader of the notion of a viscosity solution and introduce some more notation.

An upper semi-continuous function $\smash{u:[0,\infty)\times  \Rp^{\D_K}\to \R}$ is said to be a viscosity subsolution to (<ref>) if, given any $\smash{\phi\in C^\infty\big((0,\infty)\times  \Rpp^{\D_K}\big)}$ with the property that $u-\phi$ has a local maximum at $\smash{(t^*,x^*)\in (0,\infty)\times \Rpp^{\D_K}}$,

\begin{equation}\label{eqn: SBM subsolution conditions}
\big(\partial_t \phi-\td \H_{b,K,R}(\nabla \phi)\big)(t^*,x^*)\leq 0.
\end{equation}

A lower semi-continuous function $\smash{v:[0,\infty)\times \Rp^{\D_K}\to \R}$ is said to be a viscosity supersolution to (<ref>) if, given any $\smash{\phi\in C^\infty\big((0,\infty)\times  \Rpp^{\D_K}\big)}$ with the property that $v-\phi$ has a local minimum at $\smash{(t^*,x^*)\in (0,\infty)\times \Rpp^{\D_K}}$,

\begin{equation}\label{eqn: SBM supersolution conditions}
\big(\partial_t \phi-\td \H_{b,K,R}(\nabla \phi)\big)(t^*,x^*)\geq 0.
\end{equation}

A continuous function $\smash{f\in C\big([0,\infty)\times \Rp^{\D_K}\big)}$ is said to be a viscosity solution to (<ref>) if it is both a viscosity subsolution and a viscosity supersolution to (<ref>).

Given functions $h:\Rp^{\D_K}\to \R$ and $\smash{u:[0,\infty)\times \Rp^{\D_K}\to \R}$, define the semi-norms

\begin{equation}\label{eqn: SBM projected modified non-linearity Lipschitz}
\Norm{h}_{\mathrm{Lip},1}=\sup_{x\neq x'\in\Rp^{\D_K}}\frac{\abs{h(x)-h(x')}}{\Norm{x-x'}_1} \quad \text{and} \quad [u]_{0}=\sup_{\substack{t>0\\ x\in \Rp^{\D_K}}}\frac{\abs{u(t,x)-u(0,x)}}{t}.
\end{equation}

Introduce the space of functions with Lipschitz initial condition that grow at most linearly in time,

\begin{equation}
\mathfrak{L}=\big\{u:[0,\infty)\times \Rp^{\D_K}\to \R\mid u(0,\cdot) \text{ is Lipschitz continuous and } [u]_0<\infty\big\},
\end{equation}

and its subset of uniformly Lipschitz functions,

\begin{equation}
\mathfrak{L}_{\mathrm{unif}}=\Big\{u\in \mathfrak{L}\mid \sup_{t\geq 0}\Norm{u(t,\cdot)}_{\mathrm{Lip},1}<\infty\Big\}.
\end{equation}

Combining Theorem 1.1 with the arguments leading to the second conclusion of Lemma 6.1 in [30] gives the following well-posedness result for the Hamilton-Jacobi equation (<ref>).

For every $R>0$, the Hamilton-Jacobi equation (<ref>) admits  a unique viscosity solution $\smash{\td f^{(K)}_{b,R}\in \mathfrak{L}_{\mathrm{unif}}}$ subject to the initial condition $\smash{\td \psi_b^{(K)}}$. Moreover, the solution has its gradient in the closed convex set $\smash{\td \K_{=1,K}'}$,

\begin{equation}
\nabla \td f^{(K)}_{b,R} \in L^\infty\big([0,\infty)\times \Rp^{\D_K}; \td \K_{=1,K}'\big),
\end{equation}

and it satisfies the Lipschitz bound

\begin{equation}
\sup_{t>0}\Norm{\td f_{b,R}^{(K)}(t,\cdot)}_{\mathrm{Lip},1}=\Norm{\td \psi_b^{(K)}}_{\mathrm{Lip},1}\leq \norm{\td \psi_b}_{\mathrm{Lip},\TV}.
\end{equation}

In addition to this existence and uniqueness result, it will be important to record the following comparison principle for the projected Hamilton-Jacobi equation (<ref>). This comparison principle is a consequence of Corollary A.12 in [30].

If $\smash{u,v\in \mathfrak{L}_{\mathrm{unif}}}$ are respectively a continuous subsolution and a continuous supersolution to (<ref>), then

\begin{equation}
\sup_{\Rp\times \Rp^{\D_K}}\big(u(t,x)-v(t,x)\big)=\sup_{\Rp^{\D_K}}\big(u(0,x)-v(0,x)\big).
\end{equation}

The existence of the limit (<ref>) defining $f(t,\mu)$ is a consequence of Theorems 1.2 and 1.4 in [30].

Let $b \in \R$ be such that the kernel $\smash{\td g_b}$ defined in (<ref>) is positive on $[-1,1]$, let $\smash{\td \psi_{b}}$ be defined by (<ref>), and for each integer $K\geq 1$ and $\smash{R>\norm{\td \psi_b}_{\mathrm{Lip},\TV}}$, denote by $\smash{\td f_{b,R}^{(K)}}$ the unique viscosity solution to the Hamilton-Jacobi equation (<ref>) subject to the initial condition $\smash{\td \psi_b^{(K)}}$. The limit (<ref>) exists, is finite and is independent of $R$ and $b$. This limit is defined to be the solution to the infinite-dimensional Hamilton-Jacobi equation (<ref>).

To establish <Ref>, the idea will be to show that the enriched free energy (<ref>) is essentially a viscosity subsolution to the infinite-dimensional Hamilton-Jacobi equation (<ref>).

§ THE FREE ENERGY UPPER BOUND

In this section, we combine the computations in <Ref> with the arguments in [48] to essentially show that the enriched free energy (<ref>) is a viscosity subsolution to the infinite-dimensional Hamilton-Jacobi equation (<ref>). This equation is given a precise meaning by <Ref>. As alluded to in <Ref>, we will perturb the enriched Hamiltonian (<ref>) to enforce the concentration of all the multi-overlaps (<ref>) without changing the limit of the associated free energy. The perturbation Hamiltonian we will now describe was introduced in [12] to prove a general multi-overlap concentration result whose finitary version we establish in <Ref>.

Fix an integer $K_+$ which will be chosen sufficiently large in the course of this section, and write $\lambda=(\lambda_0,\lambda_1,\ldots,\lambda_{K_+})$ for a perturbation parameter with $\lambda_0\in [1/2,1]$ and $\lambda_k\in [2^{-k-1},2^{-k}]$ for $1\leq k\leq K_+$. Given a sequence $(\epsilon_N)$ with $\epsilon_N=N^\gamma$ for some $-1/8<\gamma<0$ and a standard Gaussian vector $Z_0=(Z_{0,1},\ldots,Z_{0,N})$ in $\R^N$, introduce the Gaussian perturbation Hamiltonian

\begin{equation}\label{eqn: SBM gaussian perturbation}
H_N^{\mathrm{gauss}}(\sigma,\lambda_0)=\HH_0=\sum_{i\leq N}\big(\lambda_0\epsilon_N \sigma^*_i\sigma_i+\sqrt{\lambda_0\epsilon_N}Z_{0,i}\sigma_i\big)
\end{equation}

associated with the task of recovering the signal $\sigma^*$ from the data

\begin{equation}
\end{equation}

Notice that

\begin{equation}\label{eqn: SBM epsilon sequence}
1\geq \epsilon_N \to 0 \quad \text{and} \quad N\epsilon_N\to \infty.
\end{equation}

Similarly, consider a sequence $(s_N)$ with $s_N=N^\eta$ for $4/5<\eta<1$ in such a way that

\begin{equation}\label{eqn: SBM s sequence}
\frac{s_N}{N}\to 0\quad \text{and} \quad \frac{s_N}{\sqrt{N}}\to \infty.
\end{equation}

Fix a sequence of i.i.d. random variables $(\pi_k)$ with $\Poi(s_N)$ distribution as well as a sequence $e=(e_{jk})$ of random variables with $\Exp(1)$ distribution.
For every $j\leq \pi_k$, sample i.i.d. random indices $i_{jk}$ uniformly from the set $\{1,\ldots,N\}$, and define the exponential perturbation Hamiltonian by

\begin{equation}\label{eqn: SBM exponential perturbation}
\HH_k=\sum_{j\leq \pi_k}\Big(\log(1+\lambda_k\sigma_{i_{jk}}\big)-\frac{\lambda_k e_{jk}\sigma_{i_{jk}}}{1+\lambda_k\sigma_{i_{jk}}^*}\Big) \quad \text{and}\quad H_N^{\mathrm{exp}}(\sigma)=\sum_{1\leq k\leq K_+} \HH_k.
\end{equation}

Observe that this is the Hamiltonian associated with the task of recovering the signal $\sigma^*$ from the independently generated data

\begin{equation}
\end{equation}

for $j\leq \pi_k$ and $k\geq 1$. Introduce the perturbed Hamiltonian

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

as well as its associated free energy

\begin{equation}\label{eqn: SBM perturbed free energy}
\overline{F}_N^{\text{pert}}(t,\mu,\lambda)=\frac{1}{N}\E\log\int_{\Sigma_N}\exp H_N(\sigma,\lambda)\ud P_N^*(\sigma).
\end{equation}

Since the Hamiltonian in (<ref>) corresponds to a statistical inference problem, analogously to (<ref>), the Gibbs measure associated with this Hamiltonian (<ref>) still satisfies  the Nishimori identity (<ref>). An essential property of the perturbation Hamiltonians (<ref>) and (<ref>) is that they do not affect the asymptotic behavior of the enriched free energy (<ref>).

For every $t>0$, $\mu \in \M_+$ and $\lambda$, the enriched free energy (<ref>) and the perturbed free energy (<ref>) are asymptotically equivalent,

\begin{equation}
\lim_{N\to \infty}\big\lvert \overline{F}_N^{\mathrm{pert}}(t,\mu,\lambda)-\overline{F}_N(t,\mu)\big\rvert=0.
\end{equation}

A direct computation reveals that

$$\big\lvert \overline{F}_N^{\mathrm{pert}}(t,\mu,\lambda)-\overline{F}_N(t,\mu)\big\rvert\leq \frac{1}{N}\E \max_{\sigma \in \Sigma_N}\big\lvert H_N^{\mathrm{gauss}}(\sigma,\lambda_0)\big\rvert+\frac{1}{N}\E \max_{\sigma \in \Sigma_N}\big\lvert H_N^{\mathrm{exp}}(\sigma,\lambda)\big\rvert.$$

For any spin configuration $\sigma\in \Sigma_N$,

$$\big\lvert H_N^{\mathrm{gauss}}(\sigma,\lambda_0)\big\rvert\leq N\epsilon_N+\sqrt{\epsilon_N}\sum_{i\leq N}\abs{Z_{0,i}}$$

$$\big\lvert H_N^{\mathrm{exp}}(\sigma,\lambda)\big\rvert\leq \sum_{1\leq k\leq K'}\sum_{j\leq \pi_k}\Big(\log(1+\lambda_k)+\frac{\lambda_ke_{jk}}{1-\lambda_k}\Big).$$

Since these bounds are uniform in $\sigma$, it follows that

$$\big\lvert \overline{F}_N^{\mathrm{pert}}(t,\mu,\lambda)-\overline{F}_N(t,\mu)\big\rvert\leq \epsilon_N+\sqrt{\epsilon_N}\E Z_{0,1}+\frac{s_N}{N}\sum_{k\geq 1}\Big(\log(1+\lambda_k)+\frac{\lambda_k}{1-\lambda_k}\Big).$$

The third term was obtained by taking the expectation with respect to the randomness of $e$ first and then with respect to the randomness of $(\pi_k)$. Leveraging (<ref>) and (<ref>) to let $N$ tend to infinity completes the proof.

With this result in mind, we abuse notation and redefine the perturbed free energy (<ref>),

\begin{equation}
F_N(t,\mu,\lambda)=\frac{1}{N}\log\int_{\Sigma_N}\exp H_N(\sigma,\lambda)\ud P_N^*(\sigma) \quad \text{and} \quad \overline{F}_N(t,\mu,\lambda)=\E F_N(t,\mu,\lambda).
\end{equation}

For every integer $K\geq 1$ and $x\in \Rp^{\D_K}$, we denote by

\begin{equation}\label{eqn: SBM projected perturbed free energy}
F_N^{(K)}(t,x,\lambda)=F_N\big(t,\mu_x^{(K)},\lambda\big) \quad \text{and} \quad \overline{F}_N^{(K)}(t,x,\lambda)=\E F_N^{(K)}(t,x,\lambda)
\end{equation}

the finite-dimensional projections of these perturbed free energy functionals. In the same spirit as (<ref>), given $b\in \R$ such that the kernel $\td g_b$ defined in (<ref>) is positive on $[-1,1]$, introduce translated versions of these free energy functionals,

\begin{equation}\label{eqn: SBM modified free energy}
F_N'(t,\mu, \lambda)=F_N(t,\mu,\lambda)+b\int_{-1}^1 \ud \mu+\frac{bt}{2} \quad \text{and} \quad \overline{F}_N'(t,\mu,\lambda)=\E F_N'(t,\mu,\lambda).
\end{equation}

For every integer $K\geq 1$ and $x\in \Rp^{\D_K}$, we denote by

\begin{equation}\label{eqn: SBM projected modified free energy}
F_N'^{(K)}(t,x,\lambda)=F_N'\big(t,\mu_x^{(K)},\lambda\big) \quad \text{and} \quad \overline{F}_N'^{(K)}(t,x,\lambda)=\E F_N'^{(K)}(t,x,\lambda)
\end{equation}

the finite-dimensional projections of these modified free energy functionals. Similarly, we write

\begin{equation}\label{eqn: SBM projected free energy}
\overline{F}_N^{(K)}(t,x)=\overline{F}_N\big(t,\mu_x^{(K)}\big) \quad \text{and} \quad \overline{F}_N'^{(K)}(t,x)=\overline{F}_N^{(K)}(t,x)+b\Norm{x}_1+\frac{bt}{2}
\end{equation}

for the finite-dimensional projections of the enriched free energy (<ref>) and its translation according to (<ref>). Combining Lemmas <ref>, <ref> and <ref> with the Arzela-Ascoli theorem, it is possible to extract a subsequential limit $\smash{\td F^{(K)}}$ from the sequence defined by (<ref>) for varying $N$. Passing to a further subsequence and using a diagonalization argument, it is also possible to ensure that

\begin{equation}\label{eqn: SBM modified FE limsup}
\td F^{(K)}(t,x)=\limsup_{N\to \infty}\overline{F}_N'^{(K)}(t,x)
\end{equation}

for all $\smash{(t,x)\in (0,\infty)\times \Rp^{\D_K}}$. The key to establishing <Ref> will be to show that, in some sense, the subsequential limit $\smash{\td F^{(K)}}$ is an approximate subsolution to the Hamilton-Jacobi equation (<ref>) for some $\smash{R>\norm{\td \psi_b}_{\mathrm{Lip},\TV}+\norm{\td g_b}_\infty+\norm{\td g_b'}_\infty+1}$ which will remain fixed throughout this section.

We fix a smooth function $\smash{\phi \in C^\infty\big((0,\infty)\times \Rpp^{\D_K}\big)}$ with the property that the difference $\smash{\td F^{(K)}-\phi}$ achieves a local maximum at some point $\smash{(t_\infty, x_\infty)\in (0,\infty)\times \Rpp^{\D_K}}$. Recalling that the index $K_+$ controls the number of terms in the perturbation Hamiltonian (<ref>), we introduce the parameter

\begin{equation}\label{eqn: SBM asymptotic perturbation parameter}
\lambda_\infty=\frac{\big(1, 2^{-1}, 2^{-2},\ldots,2^{-K_+}\big)+\big(2^{-1},2^{-2},2^{-3},\ldots,2^{-K_+-1}\big)}{2}
\end{equation}

as well as the smooth function

\begin{equation}
\td \phi(t,x,\lambda)=\phi(t,x)+(t-t_\infty)^2+\norm{x-x_\infty}_2^2+\norm{\lambda-\lambda_\infty}_2^2.
\end{equation}

It is clear that $\smash{(t,x,\lambda)\mapsto \td F^{(K)}(t,x)-\td \phi(t,x,\lambda)}$ has a strict local maximum at $(t_\infty,x_\infty,\lambda_\infty)$. Arguing as in the proof of <Ref> shows that $\smash{(t,x,\lambda)\mapsto \overline{F}_N'^{(K)}(t,x,\lambda)}$ converges to $\smash{(t,x,\lambda)\mapsto \td F^{(K)}(t,x)}$ locally uniformly. It is therefore possible to find a sequence $(t_N,x_N,\lambda_N)$ which converges to the point $(t_\infty,x_\infty,\lambda_\infty)$ and has the property that $\smash{(t,x,\lambda)\mapsto \overline{F}_N'^{(K)}(t,x,\lambda)-\td \phi(t,x,\lambda)}$ attains a local maximum at $(t_N,x_N,\lambda_N)$. More precisely, it is possible to find a constant $C<\infty$ which is allowed to depend on $K$, $K_+$, $t_\infty$, $x_\infty$ and the function $\phi$ such that

\begin{align}\label{eqn: SBM free energy subsolution maximum}
\Big(\overline{F}_N'^{(K)}-\td \phi\Big)&(t_N,x_N,\lambda_N)\notag\\
&=\sup\Big\{\Big(\overline{F}_N'^{(K)}-\td \phi\Big)(t,x,\lambda)\mid \abs{t-t_N}+\norm{x-x_N}_2+\norm{\lambda-\lambda_N}_2\leq C^{-1}\Big\}.
\end{align}

We will use such a constant $C < \infty$ at various places in this proof, and we understand that its value may need to be increased as we proceed; the important point is that it does not depend on $N$.
The choices of $\lambda_\infty$ in (<ref>) and $\smash{x_\infty\in \Rpp^{\D_K}}$ ensure that when $N$ is large enough $(\lambda_N)_k\in (2^{-k-1},2^{-k})$ for $0\leq k\leq K_+$ and $\smash{x_N\in \Rpp^{\D_K}}$. Increasing $C<\infty$ if necessary, it is therefore possible to guarantee that for $N$ large enough the supremum on the right-hand side of (<ref>) is taken over triples $(t,x,\lambda)$ with $t>0$, $\smash{x\in \Rpp^{\D_K}}$ and $\lambda_k\in [2^{-k-1},2^{-k}]$ for $1\leq k\leq K_+$. It follows that

\begin{equation}\label{eqn: SBM free energy subsolution spacetime derivative}
\partial_t\Big(\overline{F}_N'^{(K)}-\td \phi\Big)(t_N,x_N,\lambda_N)=0, \qquad
\nabla_x\Big(\overline{F}_N'^{(K)}-\td \phi\Big)(t_N,x_N,\lambda_N)=0
\end{equation}

\begin{equation}\label{eqn: SBM free energy subsolution perturbation derivative}
\nabla_\lambda\Big(\overline{F}_N^{(K)}-\td\phi\Big)(t_N,x_N,\lambda_N)=\nabla_\lambda\Big(\overline{F}_N'^{(K)}-\td \phi\Big)(t_N,x_N,\lambda_N)=0.
\end{equation}

The majority of this section will be devoted to using the second equality in (<ref>) in conjunction with the main result in <Ref> to show the concentration of a finite but very large number of the multi-overlaps (<ref>). We will then combine this finitary multi-overlap concentration result with the computations in <Ref> to establish the following crucial result.

Fix $\smash{R>\norm{\td \psi_b}_{\mathrm{Lip},\TV}+\norm{\td g_b}_\infty+\norm{\td g_b'}_\infty+1}$. For every $\epsilon>0$, there exists a choice of integer $K_+\geq 1$ in the perturbed Hamiltonian (<ref>) with the property that for any integer $K\geq 1$, it is possible to find a constant $\smash{\EE_{\epsilon,K}}$ with

\begin{equation}
\limsup_{N\to \infty}\Big\lvert \Big(\partial_t\overline{F}_N'^{(K)}-\widetilde{\H}_{b,K,R}\Big(\nabla_x \overline{F}_N'^{(K)}\Big)\Big)(t_N,x_N,\lambda_N)\Big\rvert\leq \EE_{\epsilon,K}
\end{equation}

and $\lim_{\epsilon\to 0}\lim_{K\to \infty}\EE_{\epsilon,K}=0$.

For the time being, let us prove <Ref> assuming <Ref>.

Given $\epsilon>0$, invoke <Ref> to find an integer $K_+\geq 1$ in the perturbed Hamiltonian (<ref>) with the property that for any integer $K\geq 1$, it is possible to find a constant $\smash{\EE_{\epsilon,K}}$ with

\begin{equation}\label{eqn: SBM free energy approximate solution at contact point}
\limsup_{N\to \infty}\Big\lvert \Big(\partial_t\overline{F}_N'^{(K)}-\widetilde{\H}_{b,K,R}\Big(\nabla_x \overline{F}_N'^{(K)}\Big)\Big)(t_N,x_N,\lambda_N)\Big\rvert\leq \EE_{\epsilon,K}
\end{equation}

and $\lim_{\epsilon\to 0}\lim_{K\to \infty}\EE_{\epsilon,K}=0$. Given an integer $K\geq 1$, the idea will be to show that the test function $\smash{\phi\in C^\infty\big((0,\infty)\times \Rpp^{\D_K}\big)}$ introduced above satisfies the subsolution condition in (<ref>) for the non-linearity $\smash{\widetilde{\H}_{b,K,R}}$ at the point of contact $(t_\infty,x_\infty)$ up to the small error $\EE_{\epsilon,K}$. This will mean that the subsequential limit $\smash{\td F^{(K)}}$ of the modified free energy (<ref>) is a viscosity subsolution to the Hamilton-Jacobi equation (<ref>) up to a small error. More precisely, the function

\begin{equation}\label{eqn: SBM main result proof corrected FE}
\td F^{(K)}_\epsilon=\td F^{(K)}-t\EE_{\epsilon,K}
\end{equation}

will be a viscosity subsolution to (<ref>). This observation will allow us to leverage the comparison principle in <Ref> to bound the limit superior of the enriched free energy (<ref>) by the solution $f$ to the infinite-dimensional Hamilton-Jacobi equation (<ref>) constructed in <Ref>. We proceed in two steps.

1: $\td F_\epsilon^{(K)}$ subsolution.

Since $\smash{x_N\to x_\infty}$ assume without loss of generality that $\smash{(x_N)\subset \Rpp^{\D_K}}$. It follows by (<ref>) that

$$\big(\partial_t\td \phi-\widetilde{\H}_{b,K,R}\big(\nabla_x\td \phi\big)\big)(t_N,x_N,\lambda_N)=\Big(\partial_t\overline{F}_N'^{(K)}-\widetilde{\H}_{b,K,R}\Big(\nabla_x \overline{F}_N'^{(K)}\Big)\Big)(t_N,x_N,\lambda_N),$$

so letting $N$ tend to infinity and combining the definition of $\td \phi$ with (<ref>) yields

$$\big(\partial_t\td \phi-\widetilde{\H}_{b,K,R}\big(\nabla_x\td \phi\big)\big)(t_\infty, x_\infty)\leq \EE_{\epsilon,K}.$$

This shows that the function (<ref>) satisfies the subsolution condition in (<ref>).

2: comparison principle.

The comparison principle in <Ref> gives the upper bound

\begin{equation}\label{eqn: SBM main result comparison principle}
\td F^{(K)}(t,x)\leq \td f^{(K)}_{b,R}(t,x)+t\EE_{\epsilon,K}.
\end{equation}

We have implicitly used that $\smash{\td F^{(K)}}$ and $\smash{\td f_{b,R}^{(K)}}$ are continuous and have the same initial condition by <Ref>. We have also used that they both belong to the solution space $\smash{\mathfrak{L}_{\mathrm{unif}}}$ by <Ref>, (<ref>), (<ref>) and a simple application of the mean value theorem. With (<ref>) in mind, fix a finite measure $\mu\in \M_+$, and introduce the discrete measure

It is readily verified that $\smash{\bar{\mu}^{(K)}\to \bar{\mu}}$ with respect to the Wasserstein distance (<ref>). Moreover, an identical argument to that in <Ref> leveraging the second bound in (<ref>) reveals that

$${\overline{F}_N}(t,\mu)\leq C'\mu[-1,1]W\big(\bar \mu,\bar\mu^{(K)}\big)+\overline{F}_N^{(K)}\big(t,x^{(K)}(\mu)\big)$$

for some constant $C'$ that depends only on $c$. We use the letter $C'$ instead of $C$ to emphasize that the constant $C'$ does not depend on $K$.
Letting $N$ tend to infinity, recalling (<ref>),  (<ref>) and leveraging (<ref>) yields

$$\limsup_{N\to \infty}\overline{F}_N(t,\mu)\leq C'\mu[-1,1]W\big(\bar \mu,\bar\mu^{(K)}\big)+\td f_{b,R}^{(K)}\big(t,x^{(K)}(\mu)\big)-b\Norm{x^{(K)}(\mu)}_1-\frac{bt}{2}+t\EE_{\epsilon,K}.$$

Invoking <Ref> and <Ref> to let $K$ tend to infinity and then $\epsilon$ tend to zero completes the proof.

The rest of this section is devoted to the proof of <Ref> which will be obtained by combining the computations of <Ref> with the main result of <Ref> to show the concentration of a finite but very large number of the multi-overlaps (<ref>). In the notation of [12], for any perturbation parameter $\lambda$, let

\begin{equation}
\lambda_{0,N}=\epsilon_N\lambda_0,
\end{equation}

and introduce the quantities

\begin{align}
\L_0&=\frac{\HH_0'}{N\epsilon_N}, \quad \text{ where } \quad  \HH_0'=\partial_{\lambda_0} H_N^{\mathrm{gauss}}(\sigma,\lambda_0)=\epsilon_N\bigg(\sigma\cdot \sigma^*+\frac{\sigma\cdot Z_0}{2\sqrt{\lambda_{0,N}}}\bigg),\label{eqn: SBM lambda 0 derivative of Hamiltonian}\\
\L_k&=\frac{\HH_k'}{s_N}, \quad \text{ where } \quad  \HH_k'=\partial_{\lambda_k} H_N^{\mathrm{exp}}(\sigma,\lambda)=\sum_{j\leq \pi_k}\sigma_{i_{jk}}\bigg(\frac{1}{1+\lambda_k\sigma_{i_{jk}}}-\frac{e_{jk}}{(1+\lambda_k\sigma^*_{i_{jk}})^2}\bigg) \label{eqn: SBM lambda k derivative of Hamiltonian}
\end{align}

for $1\leq k\leq K_+$. The importance of these quantities stems from the fact that

\begin{align}
\partial_{\lambda_0} F_N^{(K)}(t,x,\lambda)=\frac{1}{N}\big\langle \HH_0'\big\rangle,&\,\,\,\,\,\,\, \partial^2_{\lambda_0} F_N^{(K)}(t,x,\lambda)=\frac{1}{N}\Big(\big\langle (\HH_0'-\langle \HH_0'\rangle)^2\big\rangle-\frac{\epsilon_N^2}{4\lambda_{0,N}^{3/2}}\langle \sigma\rangle \cdot Z_0\Big),\label{eqn: SBM lambda 0 derivatives}\\
\partial_{\lambda_k} F_N^{(K)}(t,x,\lambda)=\frac{1}{N}\big\langle \HH_k'\big\rangle, &\,\,\,\,\,\,\, \partial^2_{\lambda_k} F_N^{(K)}(t,x,\lambda)=\frac{1}{N}\big(\big\langle (\HH_k'-\langle \HH_k'\rangle)^2\big\rangle+\big\langle \HH_k''\big\rangle\big)\label{eqn: SBM lambda k derivatives}
\end{align}

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

\begin{equation}\label{eqn: SBM lambda kj derivative}
\partial_{\lambda_k\lambda_j} F_N^{(K)}(t,x,\lambda)=\frac{1}{N}\big(\langle \HH'_j\HH'_k\rangle-\langle \HH'_j\rangle \langle \HH'_k\rangle\big)
\end{equation}

for $0\leq j\neq k\leq K_+$.
Here, and for the remainder of this section, the Gibbs average $\langle \cdot \rangle$ will always be associated with the perturbed Hamiltonian (<ref>) evaluated at a triple $(t,x,\lambda)$ which will be clear from the context. It will also be convenient to record that for $1\leq k\leq K_+$,

\begin{equation}\label{eqn: SBM Hk second derivative}
\HH_k''=\partial_{\lambda_k}^2 H_N^{\mathrm{exp}}(\sigma,\lambda)=\sum_{j\leq \pi_k}\bigg(-\frac{1}{(1+\lambda_k\sigma_{i_{jk}})^2}+2\frac{\sigma_{i_{jk}}\sigma^*_{i_{jk}}e_{jk}}{(1+\lambda_k\sigma^*_{i_{jk}})^3}\bigg) \text{ and }  \big\lvert \E \big\langle \HH_k''\big\rangle\big\rvert\leq Cs_N.
\end{equation}

To obtain the concentration of the multi-overlaps (<ref>) we will show the concentration (<ref>) of the quantities $\L_k$ for the Gibbs measure with parameters given by the contact point $(t_N,x_N,\lambda_N)$. This concentration will be deduced from the fact that the averaged free energy is being “touched from above” by a smooth function at the contact point, thereby constraining its Hessian at this point, together with the concentration of the free energy $\smash{F_N^{(K)}}$ about its average $\smash{\overline{F}_N^{(K)}}$. Due to the constraint on the Hessian at the contact point, we will be able to extend the concentration result on the free energy into an estimate on the concentration of its gradient. We decompose this argument into a series of four lemmas: the first two essentially bound the Hessian of the perturbed free energy (<ref>) from above and from below; the third leverages the free energy concentration result in <Ref> to estimate the uniform $L^p$-distance between the quenched and averaged free energies (<ref>); while the fourth extends this to a control on the gradient of the free energy.

For any perturbation parameter $\lambda$ with $\norm{\lambda}_2\leq C^{-1}$,

\begin{equation}\label{eqn: SBM perturbed free energy Hessian bounded above}
\overline{F}_N^{(K)}(t_N,x_N,\lambda_N+\lambda)-\overline{F}_N^{(K)}(t_N,x_N,\lambda_N)-\lambda\cdot \nabla_{\lambda} \overline{F}_N^{(K)}(t_N,x_N,\lambda_N)\leq C\norm{\lambda}_2^2.
\end{equation}

Fix a perturbation parameter $\lambda$ with $\norm{\lambda}_2\leq C^{-1}$, and notice that (<ref>) gives

$$\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N+\lambda)-\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N)\leq \td \phi(t_N,x_N,\lambda_N+\lambda)-\td \phi(t_N,x_N,\lambda_N).$$

On the other hand, Taylor's formula with integral remainder implies that

\begin{align}\label{eqn: SBM perturbed free energy Hessian bounded above key}
\overline{F}_N'^{(K)}(t_N,&x_N,\lambda_N+\lambda)-\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N) \notag\\
&=\lambda\cdot \nabla_{\lambda} \overline{F}_N'^{(K)}(t_N,x_N,\lambda_N)+\int_0^1 (1-s)\lambda\cdot \nabla_{\lambda}^2\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N+s\lambda)\lambda \ud s,
\end{align}

and similarly,

\begin{align*}
\td \phi(t_N,x_N,\lambda_N&+\lambda)-\td \phi(t_N,x_N,\lambda_N)\\
&=\lambda\cdot \nabla_\lambda \td \phi(t_N,x_N,\lambda_N) +\int_0^1 (1-s)\lambda\cdot \nabla_\lambda^2\td \phi(t_N,x_N,\lambda_N+s\lambda)\lambda \ud s.
\end{align*}

Combining (<ref>) with the chain rule shows that $\lambda\cdot \nabla_\lambda \widetilde{\phi}(t_N,x_N,\lambda_N)=\lambda\cdot \nabla_{\lambda}\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N)$, and therefore

\begin{align*}
\int_0^1 (1-s)\lambda\cdot \nabla_{\lambda}^2\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N+s\lambda)\lambda \ud s&\leq \int_0^1 (1-s)\lambda\cdot \nabla_\lambda^2\td \phi(t_N,x_N,\lambda_N+s\lambda)\lambda \ud s\\
&\leq C\norm{\lambda}_2^2.
\end{align*}

Substituting this into (<ref>) gives

\begin{align*}
\overline{F}_N^{(K)}(t_N,x_N,\lambda_N+\lambda)-\overline{F}_N^{(K)}(t_N,x_N,\lambda_N)&=\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N+\lambda)-\overline{F}_N'^{(K)}(t_N,x_N,\lambda_N)\\
&\leq \lambda\cdot \nabla_{\lambda} \overline{F}_N'^{(K)}(t_N,x_N,\lambda_N)+C\norm{\lambda}_2^2\\
&=\lambda\cdot \nabla_{\lambda} \overline{F}_N^{(K)}(t_N,x_N,\lambda_N)+C\norm{\lambda}_2^2.
\end{align*}

This completes the proof.

There exists a random variable $X$ with $\E X^2\leq C$ such that, for all perturbation parameters $\lambda$ with $\norm{\lambda}_2\leq C^{-1}$,

\begin{equation}\label{eqn: SBM perturbed free energy Hessian bounded below}
F_N^{(K)}(t_N,x_N,\lambda_N+\lambda)-F_N^{(K)}(t_N,x_N,\lambda_N)-\lambda\cdot \nabla_{\lambda} F_N^{(K)}(t_N,x_N,\lambda_N)\geq -X\norm{\lambda}_2^2.
\end{equation}

Since $t_N$ and $x_N$ remain fixed throughout, write $\smash{F_N^{(K)}(\lambda)}$ for $\smash{F_N^{(K)}(t_N,x_N,\lambda)}$. Introduce the function

\begin{equation}\label{eqn: SBM perturbed free energy Hessian bounded below convexification}
h(\lambda)=F_N^{(K)}(\lambda)-\frac{\sqrt{\lambda_{0,N}}}{N}\sum_{i\leq N}\abs{Z_{0,i}}+\frac{1}{N}\sum_{1\leq k\leq K_+}\sum_{j\leq \pi_k}\big(8\lambda_k^2e_{jk}-\log(1-\lambda_k)\big).
\end{equation}

Leveraging (<ref>) and Hölder's inequality, one can see that

$$\partial_{\lambda_0}^2h(\lambda)=\frac{1}{N}\big\langle (\HH_0'-\langle \HH_0'\rangle)^2\big\rangle-\frac{\epsilon_N^2}{4N\lambda_{0,N}^{3/2}}\langle \sigma\rangle \cdot Z_0+\frac{\epsilon_N^2}{4N\lambda_{0,N}^{3/2}}\sum_{i\leq N}\abs{Z_{0,i}}\geq \frac{1}{N}\big\langle (\HH_0'-\langle \HH_0'\rangle)^2\big\rangle.$$

Using (<ref>) and (<ref>) reveals that for $1\leq k\leq K_+$,

\begin{align*}
\partial_{\lambda_k}^2h(\lambda)=\frac{1}{N}\big\langle &(\HH_k'-\langle \HH_k'\rangle)^2\big\rangle\\
&+\frac{1}{N}\bigg\langle \sum_{j\leq \pi_k}\Big(-\frac{1}{(1+\lambda_k\sigma_{i_{jk}})^2}+2\frac{\sigma_{i_{jk}}\sigma^*_{i_{jk}}e_{jk}}{(1+\lambda_k\sigma^*_{i_{jk}})^3}+16e_{jk}+\frac{1}{(1-\lambda_k)^2}\Big)\bigg\rangle.
\end{align*}

Since $\lambda_k\leq 1/2$ and all spin configuration coordinates are bounded by one, it is actually the case that

$$\partial_{\lambda_k}^2h(\lambda)\geq \frac{1}{N}\big\langle (\HH_k'-\langle \HH_k'\rangle)^2\big\rangle.$$

Together with (<ref>), this shows that $\nabla_\lambda^2h$ is positive definite and therefore $h$ is convex. It follows that for any perturbation parameter $\lambda$ with $\norm{\lambda}_2\leq C^{-1}$,

$$h(\lambda_N+\lambda)\geq h(\lambda_N)+\lambda \cdot\nabla_{\lambda} h(\lambda_N).$$

Remembering the definition of $h$ in (<ref>), this shows that the left-hand side of (<ref>) is bounded from below by

\begin{align*}
\frac{1}{N}& \bigg(\sqrt{(\lambda_N)_{0,N}+\lambda_{0,N}}-\sqrt{(\lambda_N)_{0,N}}-\frac{\lambda_{0,N}}{2\sqrt{(\lambda_N)_{0,N}}}\bigg)\sum_{i\leq N}\abs{Z_{0,i}}\\
&\qquad\qquad+\frac{1}{N}\sum_{1\leq k\leq K_+}\sum_{j\leq \pi_k}8e_{jk}\Big((\lambda_N)_k^2+2\lambda_k(\lambda_N)_k-\big((\lambda_N)_k+\lambda_k\big)^2\Big)\\
&\qquad\qquad\qquad\qquad +\frac{1}{N}\sum_{1\leq k\leq K_+}\sum_{j\leq \pi_k}\bigg(\log\bigg(\frac{1-(\lambda_N)_k-\lambda_k}{1-(\lambda_N)_k}\bigg)+\frac{\lambda_k}{1-(\lambda_N)_k}\bigg).
\end{align*}

Increasing $C$ if necessary, Taylor's theorem with differential remainder gives a perturbation parameter $\tilde{\lambda}$ with $\tilde{\lambda}_k\in [2^{-k-1},2^{-k}]$ for $0\leq k\leq K_+$ whose value might not be the same at each occurrence such that

\begin{align*}
\sqrt{(\lambda_N)_{0,N}+\lambda_{0,N}}-\sqrt{(\lambda_N)_{0,N}}-\frac{\lambda_{0,N}}{2\sqrt{(\lambda_N)_{0,N}}}&=-\frac{(\lambda_{0,N})^2}{8\tilde{\lambda}_{0,N}^{3/2}}\geq -\sqrt{\epsilon_N}\lambda_0^2\geq -\lambda_0^2\\
\log\bigg(\frac{1-(\lambda_N)_k-\lambda_k}{1-(\lambda_N)_k}\bigg)+\frac{\lambda_k}{1-(\lambda_N)_k}&=-\frac{\lambda_k^2}{2(1-\tilde{\lambda}_k)^2}\geq -2\lambda_k^2.
\end{align*}

It follows that the left-hand side of (<ref>) is bounded from below by

$$-\frac{\lambda_0^2}{N}\sum_{i\leq N}\abs{Z_{0,i}}-\frac{1}{N}\sum_{1\leq k\leq K_+}\lambda_k^2\sum_{j\leq \pi_k}(8e_{jk}+2)\geq -X\norm{\lambda}_2^2$$

for the random variable

$$X=\frac{1}{N}\sum_{i\leq N}\abs{Z_{0,i}}+\frac{1}{N}\sum_{1\leq k\leq K_+}\sum_{j\leq \pi_k}(8e_{jk}+2).$$

Using the Cauchy-Schwarz inequality, taking the average with respect to the randomness of $(e_{jk})$ before the average with respect to the randomness of $(\pi_k)$ and remembering (<ref>) shows that

\begin{align*}
\E X^2&\leq \frac{C}{N^2}\bigg(\E\Big(\sum_{i\leq N}\abs{Z_{0,i}}\Big)^2+\sum_{1\leq k\leq K_+}\E\Big(\sum_{j\leq \pi_k}(8 e_{jk}+2)\Big)^2\bigg)\\
&\leq \frac{C}{N^2}\Big(N\E\abs{Z_{0,1}}+(N^2-N)\E\abs{Z_{0,1}Z_{0,2}}+\sum_{1\leq k\leq K_+} \E\pi_k\sum_{j\leq \pi_k}(8e_{jk}+2)^2\Big)\\
&\leq \frac{C}{N^2}\big(N^2+s_N^2+s_N\big)\leq C.
\end{align*}

This completes the proof.

For every $M > 0$ small enough, $p \in [1,\infty)$ and $\epsilon>0$, there exists $C < \infty$ not depending on $N$ such that

\begin{equation}
\bigg(\E\sup_{\norm{\lambda}_\infty\leq M}\Big\lvert\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N+\lambda)\Big\rvert^p\bigg)^{\frac{1}{p}}\leq CN^{-\frac{1}{2}+\epsilon}.
\end{equation}

Let $0<M<1/2$ be small enough so that $(\lambda_N+\lambda)_k\in [2^{-k-1},2^{-k}]$ for $0\leq k\leq K_+$ whenever $\norm{\lambda}_\infty\leq M$, and for each perturbation parameter $\lambda$ introduce the random variable

$$Y(\lambda)=\frac{1}{N}\sum_{0\leq k\leq K_+}\abs{\langle \HH_k'\rangle},$$

where the Gibbs average is associated with the perturbed Hamiltonian (<ref>) evaluated at the triple $(t_N,x_N,\lambda_N+\lambda)$. The relevance of these random variables stems from the fact that by the mean value theorem, (<ref>) and (<ref>), for every $\lambda,\lambda'$ in the $\ell^\infty$-ball of radius $M$,

$$\big\lvert F_N^{(K)}(t_N,x_N,\lambda_N+\lambda)-F_N^{(K)}(t_N,x_N,\lambda_N+\lambda')\big\rvert\leq C\sup_{\norm{\eta}_\infty\leq M}Y(\eta)\norm{\lambda-\lambda'}_1.$$

Averaging this inequality also shows that for every $\lambda,\lambda'$ in the $\ell^\infty$-ball of radius $M$,

$$\big\lvert \overline{F}_N^{(K)}(t_N,x_N,\lambda_N+\lambda)-\overline{F}_N^{(K)}(t_N,x_N,\lambda_N+\lambda')\big\rvert\leq\E\sup_{\norm{\eta}_\infty\leq M}Y(\eta)\norm{\lambda-\lambda'}_1$$

These two bounds imply that for any even integer $q\geq 2$,

\begin{align*}
\E\sup_{\norm{\lambda}_\infty\leq M}\Big\lvert\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N+\lambda)\Big\rvert^q\leq \E\sup_{\lambda \in A_\epsilon}\Big\lvert\Big(F_N^{(K)}-\overline{F}_N^{(K)}&\Big)(t_N,x_N,\lambda_N+\lambda)\Big\rvert^q\\
&\quad +C\epsilon^{q}\E\sup_{\norm{\lambda}_\infty\leq M}Y(\lambda)^q
\end{align*}

for $A_\epsilon=\epsilon \Z^{1+K_+}\cap\{\norm{\lambda}_\infty\leq M\}$. Indeed, every $\lambda$ is at most at distance $\epsilon (K_++1)$ from an element in $A_\epsilon$ with respect to the $\ell^1$-norm. Bounding the supremum over $A_\epsilon$ by the sum over $A_\epsilon$ and invoking the free energy concentration result in <Ref> shows that

\begin{equation}\label{eqn: SBM free energy uniform concentration key}
\E\sup_{\norm{\lambda}_\infty\leq M}\Big\lvert\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N+\lambda)\Big\rvert^q\leq C \abs{A_\epsilon}N^{-\frac{q}{2}}+C\epsilon^q\E\sup_{\norm{\lambda}_\infty\leq M}\abs{Y(\lambda)}^q.
\end{equation}

To bound the moments of $\smash{\sup_{\norm{\lambda}_\infty\leq M}\abs{Y(\lambda)}}$ fix $1\leq k\leq K_+$. Hölder's inequality and (<ref>) reveal that

\begin{align*}
\E \sup_{\norm{\lambda}_\infty\leq M}\abs{\langle \HH_k'\rangle}^q&\leq \E\sup_{\norm{\lambda}_\infty\leq M} \bigg\lvert\sum_{j\leq \pi_k}\frac{1}{1-(\lambda_N+\lambda)_k}+\frac{e_{jk}}{(1-(\lambda_N+\lambda)_k)^2}\bigg\rvert^q\\
&\leq \E \bigg\lvert \sum_{j\leq \pi_k}\frac{4(1+e_{jk})}{(1-2M)^2}\bigg\rvert^q\leq \E \pi_k^{q-1}\sum_{j\leq \pi_k}\sum_{j\leq \pi_k}\bigg\lvert \frac{4(1+e_{jk})}{(1-2M)^2}\bigg\rvert^q\\
&\leq C\E \pi_k^q,
\end{align*}

where the last inequality is found by averaging over the randomness of $(e_{jk})$. Similarly (<ref>) and Hölder's inequality give

\begin{align*}
\E \sup_{\norm{\lambda}_\infty\leq M}\abs{\langle \HH_0'\rangle}^q&\leq\epsilon_N^q \E\sup_{\norm{\lambda}_\infty\leq M}\bigg\lvert \abs{\sigma\cdot \sigma^*}+\frac{\abs{\sigma\cdot Z_0}}{2\epsilon_N^{q/2}((\lambda_N)_0+\lambda_0)^{q/2}}\bigg\rvert^q\\
&\leq C\epsilon_N^{q}\bigg(N^q+\frac{2^q\E\abs{\sigma\cdot Z_0}^q}{2\epsilon_N^{q/2}(1-2M)^q}\bigg)\leq C \epsilon_N^{\frac{q}{2}}N^q.
\end{align*}

Combining these two inequalities with <Ref> and recalling the choices (<ref>) and (<ref>) of $\epsilon_N$ and $s_N$ shows that

\begin{equation}\label{eqn: SBM Lipschitz constant of unaveraged free energy finite}
\E \sup_{\norm{\lambda}_\infty\leq M}\abs{Y(\lambda)}^q\leq C.
\end{equation}

Substituting this into (<ref>) and noticing that $\abs{A_\epsilon}$ is of order $\epsilon^{-(K_++1)}$ yields

$$\E\sup_{\norm{\lambda}_\infty\leq M}\Big\lvert\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N+\lambda)\Big\rvert^q\leq C\big(\epsilon^{-(K_++1)}N^{-\frac{q}{2}}+\epsilon^q\big).$$

Taking $1/q$'th powers and choosing $\epsilon=N^{-\frac{q}{2(q+K_++1)}}$ gives

$$\bigg(\E\sup_{\norm{\lambda}_\infty\leq M}\Big\lvert\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N+\lambda)\Big\rvert^q\bigg)^{\frac{1}{q}}\leq CN^{-\frac{q}{2(q+K_++1)}}.$$

Notice that the power on the right-hand side can be made arbitrarily close to $-\frac{1}{2}$ by taking $q$ large enough. Invoking Jensen's inequality completes the proof.

For every $\epsilon>0$, there exists a constant $C<\infty$ not depending on $N$ such that

\begin{equation}
\E\Big\lVert\nabla_{\lambda}\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N)\Big\rVert_2^2\leq CN^{-\frac{1}{2}+\epsilon}.
\end{equation}

Given $\mu \in [0,C^{-1}]$, consider the random perturbation parameter

$$\lambda=\mu \cdot \frac{\nabla_{\lambda}\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N)}{\Big\lVert \nabla_{\lambda}\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N)\Big\rVert_2}.$$

Combining <Ref> with <Ref> shows that

\begin{align*}
\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N+\lambda)-\Big(&F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N)\\
&\geq \mu\Big\lVert \nabla_{\lambda}\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N)\Big\rVert_2-(C+X)\norm{\lambda}_2^2.
\end{align*}

Rearranging, squaring and taking expectations yields

\begin{align*}
\mu^2\E\Big\lVert\nabla_{\lambda}\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N)\Big\rVert_2^2\leq C\bigg(\E\sup_{\norm{\lambda}_{\infty}\leq C^{-1}}\Big\rvert\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N&+\lambda)\Big\rvert^2+\mu^4\bigg),
\end{align*}

where we have used the fact that $\E X^2\leq C$ and $\norm{\lambda}_2=\mu$. Invoking <Ref> gives

$$\E\Big\lVert\nabla_{\lambda}\Big(F_N^{(K)}-\overline{F}_N^{(K)}\Big)(t_N,x_N,\lambda_N)\Big\rVert_2^2\leq C\bigg(\frac{1}{N^{1-2\epsilon}\mu^2}+\mu^2\bigg).$$

Optimizing over $\mu$ leads to the choice $\mu=N^{-\frac{1}{4}+\frac{\epsilon}{2}}$ and completes the proof.

For any $1\leq k\leq K_+$, there exists a constant $C<\infty$ not depending on $N$ such that

\begin{equation}\label{eqn: SBM concentration of FDS Hamiltonians}
\E \big\langle (\L_0-\E\langle \L_0\rangle)^2\big\rangle\leq CN^{-\frac{1}{4}} \quad \text{and} \quad \E \big\langle (\L_k-\E\langle \L_k\rangle)^2\big\rangle\leq CN^{-\frac{1}{20}}.
\end{equation}

Here, the Gibbs average $\langle \cdot \rangle$ is associated with the perturbed Hamiltonian (<ref>) evaluated at the contact point $(t_N,x_N,\lambda_N)$.

A direct computation using (<ref>) shows that

\begin{align*}
N^2\epsilon_N^2\E \big\langle (\L_0-\E\langle \L_0\rangle)^2\big\rangle&=\E \big\langle (\HH_0'-\langle \HH_0'\rangle)^2\big\rangle+\E \big(\langle \HH_0'\rangle-\E\langle \HH'_0\rangle\big)^2\\
&=N\partial_{\lambda_0}^2\overline{F}_N^{(K)}(t_N,x_N,\lambda_N)+\frac{\epsilon_N^2}{4\lambda_{0,N}^{3/2}}\E\langle \sigma\rangle \cdot Z_0\\
&\qquad\qquad\qquad\qquad\quad+N^2\E\Big(\partial_{\lambda_0}\Big(F_N^{(K)}-\overline{F}_N^{(K)} \Big)(t_N,x_N,\lambda_N)\Big)^2.
\end{align*}

It follows by  <Ref> and <Ref> that for any $\epsilon>0$,

$$\E \big\langle (\L_0-\E\langle \L_0\rangle)^2\big\rangle\leq \frac{C}{N^2\epsilon_N^2}\Big(N+N\epsilon_N^{2-\frac{3}{2}}+N^{2-\frac{1}{2}+\epsilon}\Big)=C\Big(N^{2\abs{\gamma}-1}+N^{\frac{3}{2}\abs{\gamma}-1}+N^{2\abs{\gamma}+\epsilon-\frac{1}{2}}\Big).$$

Remembering that $-1/8<\gamma<0$ gives the first bound in (<ref>). To establish the second bound, fix $1\leq k\leq K_+$. A direct computation using (<ref>) yields

\begin{align*}
s_N^2\E \big\langle (\L_k-\E\langle \L_k\rangle)^2\big\rangle&=\E \big\langle (\HH_k'-\langle \HH_k'\rangle)^2\big\rangle+\E \big(\langle \HH_k'\rangle-\E\langle \HH'_k\rangle\big)^2\\
&=N\partial_{\lambda_k}^2 \overline{F}_N^{(K)}(t_N,x_N,\lambda_N)-\E\langle \HH_k''\rangle\\
&\qquad\qquad\qquad\qquad\quad+N^2\E\Big(\partial_{\lambda_k}\Big(F_N^{(K)}-\overline{F}_N^{(K)} \Big)(t_N,x_N,\lambda_N)\Big)^2.
\end{align*}

Invoking (<ref>), <Ref> and <Ref> reveals that for any $\epsilon>0$,

$$\E \big\langle (\L_k-\E\langle \L_k\rangle)^2\big\rangle\leq \frac{C}{s_N^2}\Big(N+s_N+N^{\frac{3}{2}+\epsilon}\Big)=C\Big(N^{1-2\eta}+N^{-\eta}+N^{\frac{3}{2}+\epsilon-2\eta}\Big).$$

Choosing $\epsilon=1/20$, and recalling that $-1/8<\gamma<0$ and $4/5<\eta<1$ completes the proof.

This result implies the fundamental assumption (<ref>) in <Ref>. Combining this with <Ref>, <Ref> and <Ref> and fixing $\epsilon>0$, it is possible to find $\delta>0$ so the statement of <Ref> holds. In particular, setting $K_+=\lfloor \delta^{-1}\rfloor$ in the perturbed Hamiltonian (<ref>) ensures that

\begin{equation}\label{eqn: SBM multi-overlap concentration}
\E\big\langle (R_{[m]}-\E\langle R_{[m]}\rangle)^2\big\rangle\leq \epsilon
\end{equation}

for $1\leq m\leq \lfloor \epsilon^{-1}\rfloor$. Together with the computations in <Ref>, this multi-overlap concentration allows us to finally give a proof of <Ref>.

To alleviate notation, we always implicitly assume that $\overline{F}_N^{(K)}$ and its derivatives are evaluated at the contact point $(t_N,x_N,\lambda_N)$. The definition of the modified free energy in (<ref>) and <Ref> reveal that

\begin{equation}\label{eqn: SBM free energy approximate solution at contact time-derivative}
\partial_t\overline{F}_N'^{(K)}=\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-\frac{c}{2}+\frac{b}{2}+\BigO(N^{-1}).
\end{equation}

On the other hand, the duality relation (<ref>), the definition of the modified free energy in (<ref>) and <Ref> imply that for any $k\in \D_K$,

\begin{align*}
\partial_{x_k}\overline{F}_N'^{(K)}&=\frac{1}{\abs{\D_K}}\bigg(\big(c+\Delta \m k\big)\log(c)+c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\langle R_{[n]}\rangle k^n-c+b\bigg)+\BigO(N^{-1}).
\end{align*}

If we denote by $\mu^*=\L(\langle \sigma_i\rangle)$ the law of the Gibbs average of a uniformly sampled spin coordinate, then the Nishimori identity (<ref>) and the definition of $\td g_b$ in (<ref>) allow us to rewrite this as

$$\partial_{x_{k}}\overline{F}_N'^{(K)}=\frac{1}{\abs{\D_K}}\int_{-1}^1 \td g_b(ky)\ud \mu^*(y)+\BigO\big(N^{-1}\big).$$

The mean value theorem shows that

\begin{align*}
\abs{\D_K}\Big\lvert \frac{1}{\abs{\D_K}}\int_{-1}^1 \td g_b(ky)\ud \mu^*(y) - \widetilde{G}_b^{(K)}x^{(K)}(\mu^*)_{k}\Big\rvert
&\leq \sum_{k'\in \D_K}\int_{k'}^{k'+2^{-K}}\abs{\td g_b(ky)-\td g_b(kk')}\ud \mu^*(y)\\
&\leq \frac{\norm{\td g_b'}_\infty}{2^K},
\end{align*}

which means that

$$\dNorm{1}{\nabla_x \overline{F}_N'^{(K)}-\widetilde{G}_b^{(K)}x^{(K)}(\mu^*)}\leq \frac{\norm{\td g'_b}_\infty}{2^K}+\BigO\big(N^{-1}\big).$$

In particular,

$$\dNorm{1}{\widetilde{G}_b^{(K)}x^{(K)}(\mu^*)}\leq \dNorm{1}{\nabla_x \overline{F}_N'^{(K)}}+\frac{\norm{\td g_b'}_\infty}{2^K}+\BigO\big(N^{-1}\big)\leq \norm{\td g_b}_\infty+\norm{\td g_b'}_\infty+\BigO\big(N^{-1}\big)\leq R$$

for $N$ large enough.
Remembering that $\smash{\widetilde{\H}_{b,K,R}}$ coincides with $\smash{\widetilde{\C}_{b,K}}$ on $\smash{\td \CC_{b,K}\cap B_{K,R}}$ and leveraging the Lipschitz continuity of $\smash{\widetilde{\H}_{b,K,R}}$ in <Ref> gives

$$\Big\lvert \widetilde{\H}_{b,K,R}\Big(\nabla_x \overline{F}_N'^{(K)}\Big)-\widetilde{\C}_{b,K}\big(\widetilde{G}_b^{(K)}x^{(K)}(\mu^*)\big)\Big\rvert\leq \frac{8RM_b\norm{\td g_b'}_\infty}{2^Km_b^2}+\BigO\big(N^{-1}\big).$$

Another application of the mean value theorem shows that

$$\Big\lvert \widetilde{\C}_{b,K}\big(\widetilde{G}_b^{(K)}x^{(K)}(\mu^*)\big)-\frac{1}{2}\int_{-1}^1 \int_{-1}^1 \td g_b(xy)\ud \mu^*(y)\ud \mu^*(x)\Big\rvert\leq \frac{\norm{\td g_b'}_\infty}{2^K},

while a direct computation using the Nishimori identity (<ref>) reveals that

$$\frac{1}{2}\int_{-1}^1 \td g_b(xy)\ud \mu^*(y)\ud\mu^*(x)=\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\langle R_{[n]}\rangle\big)^2-\frac{c}{2}+\frac{b}{2}.$$

It follows by (<ref>) that up to an error vanishing with $N$,

$$\Big\lvert \partial_t\overline{F}_N'^{(K)}-\widetilde{\H}_{K,R}\Big(\nabla_x \overline{F}_N'^{(K)}\Big)\Big\rvert\leq \Big\lvert\frac{c}{2}\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\E\big\langle (R_{[n]}-\E\langle R_{[n]}\rangle)^2\big\rangle\Big\rvert+\frac{8RM_b\norm{\td g_b'}_\infty}{2^Km_b^2}+\frac{\norm{\td g'}_\infty}{2^K}.$$

Invoking the multi-overlap concentration (<ref>), noticing that the multi-overlaps are bounded by one and using the formula for the sum of a geometric series implies that, up to an error vanishing with $N$,

$$\Big\lvert \partial_t\overline{F}_N'^{(K)}-\widetilde{\H}_{K,R}\Big(\nabla_x \overline{F}_N'^{(K)}\Big)\Big\rvert\leq \frac{\epsilon c^2}{2(c-\abs{\Delta})}+\frac{c}{2}\sum_{n\geq \lfloor\epsilon^{-1}\rfloor}\big(\abs{\Delta}/c\big)^n+\frac{8RM_b\norm{\td g_b'}_\infty}{2^Km_b^2}+\frac{\norm{\td g'}_\infty}{2^K}.$$

Defining $\EE_{\epsilon,K}$ to be the right-hand side of this expression completes the proof.

§ THE DISASSORTATIVE SPARSE STOCHASTIC BLOCK MODEL

In this section, we leverage <Ref> to recover the known variational formula for the sparse stochastic block model in the disassortative regime, $\Delta\leq 0$. The idea will be to apply Theorem 1.5 in [30] to the infinite-dimensional Hamilton-Jacobi equation (<ref>) and obtain an infinite-dimensional Hopf-Lax formula. This Hopf-Lax formula will coincide with the standard variational formula obtained in [11, 25] and stated in <Ref>. The key insight will be that in the disassortative setting, for $b$ large enough, the function $\td g_b$ in (<ref>) is such that

\begin{equation}\label{eqn: SBME tg non-negative definite}
\int_{-1}^1 \int_{-1}^1\td g_b(xy) \ud \mu(x)\ud \mu(y)\geq 0
\end{equation}

for every signed measures $\mu \in \M_s$. This assumption is equivalent to the non-negative definiteness of each of the matrices $\smash{\td G_b^{(K)}}$ and to the convexity of each of the projected non-linearities (<ref>).

If $\Delta\leq0$ and $b$ is large enough, then the function $\td g_b:[-1,1]\to \R$ defined in (<ref>) satisfies (<ref>).

By a simple approximation argument, it suffices to establish (<ref>) for a discrete signed measure of the form

$$\mu=\frac{1}{\abs{\D_K}}\sum_{k\in \D_K} x_k \delta_k$$

for some $\smash{x\in \R^{\D_K}}$. For such a measure,

$$\int_{-1}^1 \int_{-1}^1\td g_b(xy) \ud \mu(x)\ud \mu(y)=\frac{1}{\abs{\D_K}^2}\sum_{k,k'\in\D_K}\td g_b(kk')x_kx_{k'}=x^T\widetilde{G}_b^{(K)}x,$$

so (<ref>) is equivalent to the non-negative definiteness of each of the matrices $\smash{\widetilde{G}_b^{(K)}}$. Observe that for any $k,k'\in \D_K$,

$$\big(\widetilde{G}_b^{(K)}\big)_{kk'}=\frac{1}{\abs{\D_K}^2}\td g_b(kk')=\frac{1}{\abs{\D_K}^2}\bigg(b+c\log(c)-c+\Delta kk'\log(c)+c\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}(kk')^n\bigg).$$

If we introduce the vectors $\mathbf{k}=(k)_{k\in \D_K}$ and $\mathbf{\iota}=(1)_{k\in \D_K}$, and write $\otimes n$ for the $n$-fold Hadamard product on the space of $\D_K\times \D_K$ matrices, this implies that

$$\widetilde{G}_b^{(K)}=\frac{1}{\abs{\D_K}^2}\bigg((b+c\log(c)-c)\mathbf{\iota}\mathbf{\iota}^T+\Delta\log(c)\mathbf{k}\mathbf{k}^T+\sum_{n\geq 2}\frac{(-\Delta/c)^n}{n(n-1)}\big(\mathbf{k}\mathbf{k}^T\big)^{\otimes n}\bigg)=\lim_{M\to \infty}\widetilde{G}^{(K)}_{b,M}$$

for the matrix

$$\widetilde{G}^{(K)}_{b,M}=\frac{1}{\abs{\D_K}^2}\bigg((b+c\log(c)-c)\mathbf{\iota}\mathbf{\iota}^T+\Delta\log(c)\mathbf{k}\mathbf{k}^T+\sum_{2\leq n\leq M}\frac{(-\Delta/c)^n}{n(n-1)}\big(\mathbf{k}\mathbf{k}^T\big)^{\otimes n}\bigg).$$

Choosing $b>2c\abs{\log(c)}+c$ ensures that the first two terms in this sum define a non-negative definite matrix. Using that $\Delta \le 0$ and the Schur product theorem, we see that the matrix $\smash{\widetilde{G}^{(K)}_{b,M}}$ is a positive linear combination of non-negative definite matrices, and is therefore non-negative definite. Noticing that the limit of non-negative definite matrices is again non-negative definite completes the proof.

This result allows us to apply Theorem 1.5 in [30] to the infinite-dimensional Hamilton-Jacobi equation (<ref>) and obtain a variational formula for its solution. To state this formula concisely, through a slight abuse of notation,
introduce the functional $\smash{\Par:\Rpp\times \M_+\times \M_+\to \R}$ defined by

\begin{equation}
\Par(t,\mu,\nu)=\psi(\mu+t\nu)-\frac{t}{2}\int_{-1}^1 G_\nu(y)\ud \nu(y).
\end{equation}

Theorem 1.5 in [30] and (<ref>) imply that the unique solution to the infinite-dimensional Hamilton-Jacobi equation (<ref>) is given by the Hopf-Lax formula

\begin{equation}\label{eqn: SBM modified FE Hopf-Lax}
f(t,\mu)=\sup_{\nu\in \Pr[-1,1]}\Par(t,\mu,\nu)
\end{equation}

for every $t>0$ and $\mu \in \M_+$. Combining this representation formula with <Ref> and a simple interpolation argument taken from [11], we now prove <Ref>.

By <Ref> and the Hopf-Lax formula (<ref>), the limit of the free energy (<ref>) satisfies the upper bound

\begin{equation}\label{eqn: SBM disassortative Hopf-Lax upper bound key}
\limsup_{N\to \infty}\overline{F}_N\leq \sup_{\nu\in \Pr[-1,1]}\Par(1,0,\nu),
\end{equation}

where $0$ denotes the zero measure. To show that the right-hand side of this expression may be bounded by the supremum of the functional (<ref>) over measures $\mu\in \M_p$, for $b>1$ large enough so the function $\td g_b$ defined in (<ref>) is strictly positive on $[-1,1]$ and each integer $N\geq 1$, introduce the functional $\smash{\td\Par_{b,N}: \Rp\times \M_+\times \M_+\to \R}$ defined by

$$\td \Par_{b,N}(t,\mu,\nu)=\td \psi_{b,N}(\mu+t\nu)-\frac{t}{2}\int_{-1}^1 \td G_{b,\nu}(y)\ud \nu(y).$$

Here $\td \psi_{b,N}:\M_+\to \R$ denotes the initial condition

$$\td \psi_{b,N}(\mu)=\psi_N(\mu)+b\int_{-1}^1 \ud \mu$$

and $\td G_{b,\nu}:[-1,1]\to \R$ denotes the function

$$\td G_{b,\nu}(x)=\int_{-1}^1 \td g_b(xy)\ud \nu(y).$$

By Theorem 1.5 in [30], there exists a probability measure $\td \nu\in \Pr[-1,1]$ which maximizes the right-hand side of (<ref>). It follows by <Ref> that

\begin{equation}\label{eqn: SBM disassortative Hopf-Lax upper bound P pre}
\sup_{\nu\in \Pr[-1,1]}\Par(1,0,\nu)=\lim_{N\to \infty}\td \Par_{b,N}(1,0,\td \nu)-\frac{b}{2}\leq \limsup_{N\to \infty}\sup_{\nu\in \M_+}\td \Par_{b,N}(1,0,\nu)-\frac{b}{2}.
\end{equation}

An identical argument to that in Lemma 5.1 of [30] gives a sequence of maximizing measures $(\nu_N)\subset \M_+$ with

\begin{equation}\label{eqn: SBM disassortative Hopf-Lax upper bound P maximizer}
\sup_{\nu\in \M_+}\td \Par_{b,N}(1,0,\nu)=\td \Par_{b,N}(1,0,\nu_N).
\end{equation}

By <Ref> and (<ref>), the Gateaux derivative density of the initial condition $\smash{\td \psi_{b,N}}$ at the measure $\nu_N$ is given by