B^{\prime}}-\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B)^{2}\big{\rangle}_{B}+o_{L^{\circlearrowleft}}(1),$

where $o_{L^{\circlearrowleft}}(1)\to 0$ as $L^{\circlearrowleft}\to\infty$
for almost all $t\in[0,1]$ and all $\eta\in[0,\eta_{0}]$. Now we use Corollary
6.7 and Lemma 6.8 to deduce that for almost all $t$,

$\lim_{\eta\to 0}\lim_{L^{\circlearrowleft}\to
0}\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cup
B^{\prime})^{2}\big{\rangle}_{B\cup
B^{\prime}}-\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B)^{2}\big{\rangle}_{B}=0.$

The same result obviously holds if $B$ is replaced by $B^{\prime}$ in the
above argument. Therefore we can substitute $B$ and $B^{\prime}$ with $B\cup
B^{\prime}$ in the conditional expectations in the expression of
$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]$, Eq.(7.3): as
$L^{\circlearrowleft}\to 0$ then $\eta\to 0$ we have

$\displaystyle\Big{|}$
$\displaystyle\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]$
$\displaystyle-\frac{1}{|B|\cdot|B^{\prime}|\cdot|B\cap B^{\prime}|}\sum_{x\in
B\cap B^{\prime},y\in B,z\in
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}\operatorname{\mathbb{E}}[\theta_{y}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}\Big{]}\Big{|}\longrightarrow 0.$

#### Step 2: replacing the domain of summation.

The next step is to replace the domains of summation in the above sum to
$B\cup B^{\prime}$ for the three indices. The above sum can be written as

$\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B)R_{2,3}(B\cap
B^{\prime})R_{3,1}(B^{\prime})\big{\rangle}_{B\cup B^{\prime}}.$

Since each of the three overlaps above is locked to $R_{a,b}(B\cup
B^{\prime})$ for the appropriate replica pair $(a,b)$ (this is again a
straightforward application of Proposition 6.6, the above expression is equal
to

$\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cup B^{\prime})R_{2,3}(B\cup
B^{\prime})R_{3,1}(B\cup B^{\prime})\big{\rangle}_{B\cup
B^{\prime}}+o_{L^{\circlearrowleft}}(1),$

where again $o_{L^{\circlearrowleft}}(1)\to 0$ as
$L^{\circlearrowleft}\to\infty$ for almost all $t\in[0,1]$ and all
$\eta\in[0,\eta_{0}]$. As explained in the sketch of the proof, the above
triangular product can be expressed as follows:

$\displaystyle\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cup B^{\prime})$
$\displaystyle R_{2,3}(B\cup B^{\prime})R_{3,1}(B\cup
B^{\prime})\big{\rangle}_{B\cup B^{\prime}}$ $\displaystyle=\frac{1}{|B\cup
B^{\prime}|^{3}}\sum_{x,y,z\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{y}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}\Big{]}$
$\displaystyle=\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{3}),$

where $\chi$ is the susceptibility matrix (7.4).

#### Step 3: structure of the susceptibility matrix.

Next, we prove that
$\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{3})\to
q_{\star\star}^{3}(\delta)$ for almost all $t\in[0,1]$. We proceed by showing
upper and lower bounds separately. For the upper bound, we observe that as
$L^{\circlearrowleft}\to\infty$ then $\eta\to 0$, we have

$\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{2})=\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B\cup B^{\prime})^{2}\right\rangle_{B\cup B^{\prime}}\longrightarrow
q_{\star\star}^{2}(\delta).$

This is obtained through previously employed arguments: Corollary 6.7 and
Lemma 6.8. Moreover, by monotonicity of the $\ell_{p}$ norm and the fact that
$\chi$ is a symmetric and positive semi-definite (PSD) matrix,

$\operatorname{trace}(\chi^{3})^{1/3}\leq\operatorname{trace}(\chi^{2})^{1/2}.$

Thus,
$\operatorname{\mathbb{E}}[\operatorname{trace}(\chi^{3})]\leq\operatorname{\mathbb{E}}[\operatorname{trace}(\chi^{2})^{3/2}]$.
Now, since

$\operatorname{\mathbb{E}}\big{[}\operatorname{trace}(\chi^{2})^{2}\big{]}-\operatorname{\mathbb{E}}\big{[}\operatorname{trace}(\chi^{2})\big{]}^{2}=\operatorname{\mathbb{E}}\big{[}M_{B}^{4}\big{]}-\operatorname{\mathbb{E}}\big{[}M_{B}^{2}\big{]}^{2}=\operatorname{var}(M_{B}^{2}),$

which, according to Theorem 4.3, item 1, converges to zero as
$L^{\circlearrowleft}\to 0$ then $\eta\to 0$, we have

$\limsup_{\eta\to
0}\limsup_{L^{\circlearrowleft}\to\infty}\Big{(}\operatorname{\mathbb{E}}[\operatorname{trace}(\chi^{2})^{3/2}]-\operatorname{\mathbb{E}}[\operatorname{trace}(\chi^{2})]^{3/2}\Big{)}=0.$

Further, since
$\operatorname{\mathbb{E}}[\operatorname{trace}(\chi^{2})]^{3/2}\to
q_{\star\star}^{3}(\delta)$ as $L^{\circlearrowleft}\to\infty$ then $\eta\to
0$, this establishes the upper bound

$\limsup_{\eta\to
0}\limsup_{L^{\circlearrowleft}\to\infty}\operatorname{\mathbb{E}}\big{[}\operatorname{trace}(\chi^{3})\big{]}\leq
q_{\star\star}^{3}(\delta).$

As for the lower bound, we have
$\operatorname{trace}(\chi^{3})\geq\|\chi\|_{\textup{op}}^{3}$ since $\chi$ is
PSD. We will prove that

$\liminf_{\eta\to
0}\liminf_{L^{\circlearrowleft}\to\infty}\operatorname{\mathbb{E}}\|\chi\|_{\textup{op}}\geq
q_{\star\star}(\delta).$ (7.5)

This implies a matching lower bound through Jensen’s inequality. We have the
following characterization of the operator norm for a PSD matrix:

$\|\chi\|_{\textup{op}}=\sup_{|u|=1}u^{\intercal}\chi u,$

where $|\cdot|$ is the $\ell_{2}$ norm of a vector. Now it suffices to exhibit
a candidate unit vector $u$ that (approximately) achieves the required bound.
Our candidate is $u=\hat{u}/|\hat{u}|$, where

$\hat{u}_{x}=\frac{1}{\sqrt{|B\cup
B^{\prime}|}}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y_{B\cup
B^{\prime}}^{\delta,\eta,\lambda}\big{]},~{}~{}~{}x\in B\cup B^{\prime},$
(7.6)

where we have added additional side information from the scalar Gaussian noise
channel (6.1) with SNR $\lambda>0$ on $B\cup B^{\prime}$. We show next that as
$\lambda\to 0$, the (sequence of) vector(s) $u$ achieves the supremum. We use
the decoupling Lemma 6.11 (with $A=B\cup B^{\prime}$) to obtain

$\displaystyle\operatorname{\mathbb{E}}\big{[}\hat{u}^{\intercal}\chi\hat{u}\big{]}$
$\displaystyle=\frac{1}{|B\cup B^{\prime}|^{2}}\sum_{x,y\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{B\cup
B^{\prime}}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y_{B\cup
B^{\prime}}^{\delta,\eta,\lambda}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{y}|Y_{B\cup
B^{\prime}}^{\delta,\eta,\lambda}\big{]}\Big{]}$
$\displaystyle=\frac{1}{|B\cup B^{\prime}|^{2}}\sum_{x,y\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{B\cup
B^{\prime}}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}^{\delta,\eta,\lambda}\big{]}\Big{]}+o_{L^{\circlearrowleft}}(1),$

for almost every $\lambda>0$. Moreover, according to Lemma 6.12 we can remove
the scalar side information and incur a small error:

$\displaystyle\operatorname{\mathbb{E}}\big{[}\hat{u}^{\intercal}\chi\hat{u}\big{]}$
$\displaystyle=\frac{1}{|B\cup B^{\prime}|^{2}}\sum_{x,y\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}+\mbox{error}$
$\displaystyle=\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{2})+\mbox{error},$

where $\mbox{error}\to 0$ as $L^{\circlearrowleft}\to\infty$ and then
$\lambda\to 0$ for almost every $\eta>0$. We have already established that
$\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{2})\to
q_{\star\star}^{2}(\delta)$ as $L^{\circlearrowleft}\to\infty$ and $\eta\to
0$. Now it remains to analyze $|\hat{u}|$. We have

$\operatorname{\mathbb{E}}\big{[}|\hat{u}|^{2}\big{]}=\frac{1}{|B\cup
B^{\prime}|}\sum_{x\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}=\varphi^{\mbox{\rm\tiny v}}_{B\cup
B^{\prime}}(\delta,\eta,\lambda).$

Now we examine the fourth moment of $|\hat{u}|$:

$\displaystyle\operatorname{\mathbb{E}}\big{[}|\hat{u}|^{4}\big{]}$
$\displaystyle=\frac{1}{|B\cup B^{\prime}|^{2}}\sum_{x,y\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B\cup
B^{\prime}}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{y}|Y^{\delta,\eta,\lambda}_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}$ $\displaystyle=\frac{1}{|B\cup
B^{\prime}|^{2}}\sum_{x,y\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}+\mbox{error}_{1}$
$\displaystyle=\varphi^{\mbox{\rm\tiny e}}_{B\cup
B^{\prime}}(\delta,\eta,\lambda)+\mbox{error}_{1},$

where, similarly to previous arguments, $\mbox{error}_{1}\to 0$ for almost
every $\lambda>0$ and all $\eta>0$. Now observe that by virtue of Lemma 6.10,

$\varphi^{\mbox{\rm\tiny e}}_{B\cup
B^{\prime}}(\delta,\eta,\lambda)-\varphi^{\mbox{\rm\tiny v}}_{B\cup
B^{\prime}}(\delta,\eta,\lambda)^{2}\to
0,~{}~{}\mbox{as}~{}~{}L^{\circlearrowleft}\to\infty.$

Thus $\operatorname{var}(|\hat{u}|^{2})\to 0$. As a consequence, we have

$\displaystyle\operatorname{\mathbb{E}}\big{[}u^{\intercal}\chi u\big{]}$
$\displaystyle=\operatorname{\mathbb{E}}\Big{[}\frac{\hat{u}^{\intercal}\chi\hat{u}}{|\hat{u}|^{2}}\Big{]}=\operatorname{\mathbb{E}}\Big{[}\frac{\hat{u}^{\intercal}\chi\hat{u}}{\operatorname{\mathbb{E}}[|\hat{u}|^{2}]}\Big{]}+\mbox{error},$

where

$\displaystyle|\mbox{error}|$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\frac{|\hat{u}^{\intercal}\chi\hat{u}|\cdot|\Delta|}{\operatorname{\mathbb{E}}[|\hat{u}|^{2}]\cdot|\hat{u}|^{2}}\right],~{}~{}~{}\Delta=|\hat{u}|^{2}-\operatorname{\mathbb{E}}[|\hat{u}|^{2}]$
$\displaystyle\leq\frac{\operatorname{\mathbb{E}}[|\Delta|\mathds{1}\\{|\hat{u}|<\epsilon\\}]}{\operatorname{\mathbb{E}}[|\hat{u}|^{2}]}+\operatorname{\mathbb{E}}\left[\frac{|\hat{u}^{\intercal}\chi\hat{u}|\cdot|\Delta|}{\operatorname{\mathbb{E}}[|\hat{u}|^{2}]\cdot|\hat{u}|^{2}}\mathds{1}\\{|\hat{u}|\geq\epsilon\\}\right],~{}~{}~{}(\mbox{for
}\epsilon>0)$ $\displaystyle\leq
2\operatorname{\mathbb{P}}(|\hat{u}|<\epsilon)+\frac{\operatorname{\mathbb{E}}[|\Delta|]}{\epsilon^{2}\operatorname{\mathbb{E}}[|\hat{u}|^{2}]}.$

By Chebychev’s inequality,
$\operatorname{\mathbb{P}}(|\hat{u}|<\epsilon)\leq\operatorname{var}(|\hat{u}|^{2})/(\operatorname{\mathbb{E}}[|\hat{u}|^{2}]-\epsilon^{2})$
for $\epsilon<\operatorname{\mathbb{E}}[|\hat{u}|^{2}]^{1/2}$. On the other
hand
$\operatorname{\mathbb{E}}[|\Delta|]\leq\operatorname{var}(|\hat{u}|^{2})^{1/2}$.
When $\delta>\delta_{c}$, $q_{\star\star}(\delta)>0$ and
$\operatorname{\mathbb{E}}[|\hat{u}|^{2}]>0$ for $L^{\circlearrowleft}$ large
enough, and the above tends to zero. Therefore, we have
$\operatorname{\mathbb{E}}[u^{\intercal}\chi u]\to q_{\star\star}(\delta)$
when $\delta>\delta_{c}$ as $L^{\circlearrowleft}\to\infty$ then $\eta\to 0$.
This implies the desired lower bound (7.5).

Putting the upper and lower bounds together we deduce that

$\lim_{\eta\to
0}\lim_{L^{\circlearrowleft}\to\infty}\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{3})=q_{\star\star}^{3}(\delta).$

###  7.4 Proof of Theorem 1.3

For any $T$ with output values in $\\{\pm 1\\}$ and $L_{n}\geq 1$, Cauchy-
Schwarz inequality implies

$\displaystyle|\mathcal{R}_{\Lambda_{n}}(T)|$
$\displaystyle=\frac{1}{|\Lambda_{n}|^{2}}\left|\sum_{u,v\in\Lambda_{n}}\operatorname{\mathbb{E}}\Big{[}T_{uv}(Y_{\Lambda_{n}}^{\delta,\eta,L_{n}})\operatorname{\mathbb{E}}\big{[}\theta_{u}\theta_{v}|Y_{\Lambda_{n}}^{\delta},Y_{\Lambda_{n}}^{\eta,L_{n}}\big{]}\Big{]}\right|$
$\displaystyle\leq\Big{(}\frac{1}{|\Lambda_{n}|^{2}}\sum_{u,v\in\Lambda_{n}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{u}\theta_{v}|Y_{\Lambda_{n}}^{\delta},Y_{\Lambda_{n}}^{\eta,L_{n}}\big{]}^{2}\Big{]}\Big{)}^{1/2}.$

We add auxiliary GOE side information with SNR parameter $\eta_{2}$ and
interaction range $L=2n+1$, (i.e., there is a measurement $Y_{uv}^{\eta_{2}}$
available for any pair $(u,v)$ in $\Lambda_{n}$) and let

$\tilde{\varphi}_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}:=\frac{1}{|\Lambda_{n}|^{2}}\sum_{u,v\in\Lambda_{n}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{u}\theta_{v}|Y_{\Lambda_{n}}^{\delta},Y_{\Lambda_{n}}^{\eta,L_{n}},Y_{\Lambda_{n}}^{\eta_{2}}\big{]}^{2}\Big{]}.$

We clearly have
$|\mathcal{R}_{\Lambda_{n}}(T)|\leq\big{(}\tilde{\varphi}_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}\big{)}^{1/2}$. Now recall the definition of
$\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny e}}$:

$\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta_{2}):=\frac{1}{|\Lambda_{n}|^{2}}\sum_{u,v\in\Lambda_{n}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{u}\theta_{v}|Y_{\Lambda_{n}}^{\delta},Y_{\Lambda_{n}}^{\eta_{2}}\big{]}^{2}\Big{]}.$

The crucial point is that $\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta_{2})$ and $\tilde{\varphi}_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta,\eta_{2})$ are close when $\eta$ is small:

######  Lemma 7.1.

For almost all $\eta_{2}>0$,

$\lim_{\eta\to
0}\liminf_{n\to\infty}(\tilde{\varphi}_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}-\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny e}})=0.$

###### Proof.

The proof is similar to that of Lemma 6.12. Let
$\tilde{f}_{n}(\delta,\eta,L_{n},\eta_{2})=\frac{1}{|\Lambda_{n}|}\operatorname{\mathbb{E}}\log
Z_{\Lambda_{n}}$ where $Z_{\Lambda_{n}}$ is the partition function of
$\operatorname{\mathbb{P}}(\cdot\,|Y_{\Lambda_{n}}^{\delta},Y_{\Lambda_{n}}^{\eta,L_{n}},Y_{\Lambda_{n}}^{\eta_{2}})$.
Then $\eta\mapsto\tilde{f}_{n}(\delta,\eta,L_{n},\eta_{2})$ is
$\frac{1}{2}$-Lipschitz as seen by taking the $\eta$-derivative of
$\tilde{f}_{n}$:

$\frac{\mathrm{d}}{\mathrm{d}\eta}\tilde{f}_{n}=\frac{1}{2|\Lambda_{n}|L_{n}^{d}}\sum_{u\in\Lambda_{n}}\sum_{\underset{|u-v|\leq
L_{n}}{v\in\Lambda_{n}}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{u}\theta_{v}|Y_{\Lambda_{n}}^{\delta},Y_{\Lambda_{n}}^{\eta,L_{n}},Y_{\Lambda_{n}}^{\eta_{2}}\big{]}^{2}\Big{]}\leq\frac{1}{2}.$

On the other hand, the $\eta_{2}$-derivative of $\tilde{f}_{n}$ is
$\frac{1}{2}\tilde{\varphi}_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta,\eta_{2})$. Therefore, for all $\eta_{2}$,

$\displaystyle\int_{0}^{\eta_{2}}(\tilde{\varphi}_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta,\eta_{2}^{\prime})-\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta_{2}^{\prime}))\mathrm{d}\eta_{2}^{\prime}$
$\displaystyle=2(\tilde{f}_{n}(\delta,\eta,L_{n},\eta_{2})-\tilde{f}_{n}(\delta,\eta,L_{n},0))$
$\displaystyle~{}~{}~{}-2(\tilde{f}_{n}(\delta,0,L_{n},\eta_{2})-\tilde{f}_{n}(\delta,0,L_{n},0))$
$\displaystyle=2(\tilde{f}_{n}(\delta,\eta,L_{n},\eta_{2})-\tilde{f}_{n}(\delta,0,L_{n},\eta_{2}))$
$\displaystyle~{}~{}~{}-2(\tilde{f}_{n}(\delta,\eta,L_{n},0)-\tilde{f}_{n}(\delta,0,L_{n},0))$
$\displaystyle\leq 2\eta.$

We used the Lipschitz property of $\tilde{f}_{n}$ in $\eta$ to obtain the last
line. Since the integrand is nonnegative, Fatou’s lemma implies

$\int_{0}^{\eta_{2}}\liminf_{n\to\infty}(\tilde{\varphi}_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta,\eta_{2}^{\prime})-\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta_{2}^{\prime}))\mathrm{d}\eta_{2}^{\prime}\leq 2\eta.$

Now, letting $\eta\to 0$ implies the result. $\blacksquare$

Given the above result, we have for almost all $\eta_{2}>0$,

$\limsup_{\eta\to
0}\liminf_{n\to\infty}|\mathcal{R}_{\Lambda_{n}}(T)|\leq\lim_{n\to\infty}\big{(}\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta_{2})\big{)}^{1/2}.$

Since $\underset{\eta_{2}\to
0}{\lim}\,\underset{n\to\infty}{\lim}\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}(\delta,\eta_{2})=0$ when $\delta<\delta_{c}$ we have

$\lim_{\eta\to 0}\liminf_{n\to\infty}|\mathcal{R}_{\Lambda_{n}}(T)|=0.$

##  8 Limits of the free energies

In this section we prove convergence of the various free energies defined in
Section 6, i.e., we prove Propositions 6.1, 6.3, 6.5 and 6.9.

###  8.1 Proof of Proposition 6.1

We start with the free energy $f^{\textup{{sc}}}_{B_{n}}(\delta,\lambda)$ in
Eq. (6.5). The argument is standard and we follow Friedli and Velenik’s
exposition [FV17, Chapter 3]. Minor changes need to be made in order to
accommodate our setting with disorder and the additional Hamiltonian
$H^{\lambda}_{B_{n}}$ encoding the scalar side information. We start with the
special case where $B_{n}=D_{n}=\\{0,1,\cdots,2^{n}\\}^{d}$, we then extend
the convergence to a general van Hove sequence.

Observe that $D_{n+1}$ can be partitioned disjointly into $2^{d}$ translates
of $D_{n}$; call them $D_{n}^{(1)},\cdots,D_{n}^{(2^{d})}$. Moreover, the
Hamiltonian (6.3) corresponding to the information $Y^{\delta}_{D_{n}}$
observed in the edges of the lattice can be decomposed as follows:

$\displaystyle H_{D_{n+1}}^{\delta}(\theta)$
$\displaystyle=\beta\sum_{\underset{|u-v|=1}{u,v\in
D_{n+1}}}Y^{\delta}_{uv}\theta_{u}\theta_{v},$
$\displaystyle=\sum_{i=1}^{2^{d}}H_{D_{n}^{(i)}}^{\delta}(\theta)+R,$

where $H_{D_{n}^{(i)}}^{\delta}(\theta)$ are defined exactly as in (6.3)
(observe that they are identical in law), and $R$ collects the terms
corresponding to the edges whose endpoints belong to two different sub-blocks
$D_{n}^{(i)}$. Since there are at most $|\partial D_{n+1}|=\beta
d2^{(n+1)(d-1)}$ such edges, and all individual terms in the above Hamiltonian
are bounded by one in absolute value, we have $|R|\leq\beta d2^{(n+1)(d-1)}$.
Therefore, denoting by $Z_{D_{n+1}}$ and $Z_{D^{(i)}_{n}}$ the partition
functions we have

$\prod_{i=1}^{2^{d}}Z_{D_{n}^{(i)}}\cdot e^{-\beta d2^{(n+1)(d-1)}}\leq
Z_{D_{n+1}}\leq\prod_{i=1}^{2^{d}}Z_{D_{n}^{(i)}}\cdot e^{\beta
d2^{(n+1)(d-1)}}.$

Since $\\{Z_{D_{n}^{(i)}}:i=1,\cdots,2^{d}\\}$ are all equal in distribution,
taking logarithms and then expectations, we get

$\frac{2^{d}|D_{n}|}{|D_{n+1}|}f^{\textup{{sc}}}_{D_{n}}-\beta
d\frac{2^{(n+1)(d-1)}}{|D_{n+1}|}\leq
f^{\textup{{sc}}}_{D_{n+1}}\leq\frac{2^{d}|D_{n}|}{|D_{n+1}|}f^{\textup{{sc}}}_{D_{n}}+\beta
d\frac{2^{(n+1)(d-1)}}{|D_{n+1}|}.$

Since $|D_{n}|=2^{nd}$ for all $n$, this yields

$|f^{\textup{{sc}}}_{D_{n+1}}-f^{\textup{{sc}}}_{D_{n}}|\leq\frac{\beta
d}{2^{n+1}}.$

We deduce from this that the sequence $(f^{\textup{{sc}}}_{D_{n}})_{n\geq 0}$
is Cauchy: $|f^{\textup{{sc}}}_{D_{m}}-f^{\textup{{sc}}}_{D_{n}}|\leq\beta
d2^{-n}$ for all $m\geq n$. Hence it converges to a limit $f^{\textup{{sc}}}$
as $n\to\infty$, and the convergence is uniform on any interval
$[0,\beta_{0}]$ with $\beta_{0}<\infty$.

Consider now an arbitrary van Hove sequence $(B_{n})_{n\geq 0}$. Fix an
integer $k$ and partition $\mathbb{Z}^{d}$ into disjoint translates of
$D_{k}=\\{0,1,\cdots,2^{k}\\}^{d}$. For each $n$ let $[B]_{n}$ be the minimal
cover of $B_{n}$ by translates of $D_{k}$. We have

$|f^{\textup{{sc}}}_{B_{n}}-f^{\textup{{sc}}}|\leq|f^{\textup{{sc}}}_{B_{n}}-f^{\textup{{sc}}}_{[B]_{n}}|+|f^{\textup{{sc}}}_{[B]_{n}}-f^{\textup{{sc}}}_{D_{k}}|+|f^{\textup{{sc}}}_{D_{k}}-f^{\textup{{sc}}}|.$

Now we bound each one of these three terms. For the first term, we let
$\Delta_{n}=[B]_{n}\setminus B_{n}$. We then have

$Z_{B_{n}}\cdot\widetilde{Z}_{\Delta_{n}}\cdot e^{-2d\beta|\Delta_{n}|}\leq
Z_{[B]_{n}}\leq Z_{B_{n}}\cdot\widetilde{Z}_{\Delta_{n}}\cdot
e^{2d\beta|\Delta_{n}|},$

where

$\widetilde{Z}_{\Delta_{n}}=2^{-|\Delta_{n}|}\sum_{\theta\in\\{\pm
1\\}^{\Delta_{n}}}e^{H^{\lambda}_{\Delta_{n}}(\theta)}.$

Therefore, letting
$\vartheta=\frac{1}{|\Delta_{n}|}\operatorname{\mathbb{E}}\log\widetilde{Z}_{\Delta_{n}}=\operatorname{\mathbb{E}}\log\cosh(\sqrt{\lambda}z+\lambda)$
with $z\sim N(0,1)$, we have

$\Big{|}f^{\textup{{sc}}}_{[B]_{n}}-\frac{|B_{n}|}{|[B]_{n}|}f^{\textup{{sc}}}_{B_{n}}-\frac{|\Delta_{n}|}{|[B]_{n}|}\vartheta\Big{|}\leq\frac{2d\beta|\Delta_{n}|}{|[B]_{n}|}.$

On the one hand, $[B]_{n}$ is a minimal cover of $B_{n}$ by translates of
$D_{k}$, so we have $|\Delta_{n}|\leq|D_{k}|\cdot|\partial B_{n}|$. On the
other hand $|[B]_{n}|\geq|B_{n}|$, and $f^{\textup{{sc}}}_{B_{n}}$ is
uniformly bounded by $2\beta d+\vartheta$. Thus

$|f^{\textup{{sc}}}_{B_{n}}-f^{\textup{{sc}}}_{[B]_{n}}|\leq C\frac{|\partial
B_{n}|}{|B_{n}|}\xrightarrow[n\to\infty]{}0$

for some constant $C=C(\beta,d,k,\lambda)>0$. Convergence is again uniform on
$[0,\beta_{0}]\times[0,\lambda_{0}]$ for any $\beta_{0},\lambda_{0}>0$. Next,
we address the second term. The same estimates previously conducted show that

$\displaystyle|f^{\textup{{sc}}}_{[B]_{n}}-f^{\textup{{sc}}}_{D_{k}}|$
$\displaystyle\leq\frac{\beta|\partial[B]_{n}|}{|[B]_{n}|}\leq\frac{\beta|\partial
D_{k}|}{|D_{k}|}\leq\beta d2^{-k}.$

Lastly, we already know that $|f^{\textup{{sc}}}_{D_{k}}-f^{\textup{{sc}}}|\to
0$ as $k\to\infty$. Now we take $n\to\infty$ then $k\to\infty$ to conclude the
proof.

###  8.2 Proof of Proposition 6.3

Here we prove convergence of the free energy $f_{B_{n}}(\delta,\eta)$ with GOE
side information with SNR $\eta>0$. The argument relies on Guerra’s
interpolation method [GT02] and concentration of measure arguments. It is
almost identical to the proof in the spiked GOE case with no lattice
information ($\delta=0$). We follow the exposition in [AK18]. The lower and
upper bounds are proved separately. We start with the lower bound. We use the
interpolating Hamiltonian

$\displaystyle H_{s}(\theta)$
$\displaystyle=H^{\delta}_{B_{n}}(\theta)+\sum_{u,v\in
B_{n}}\Big{(}\sqrt{\frac{s\eta}{|B_{n}|}}Y_{uv}^{s\eta}\theta_{u}\theta_{v}-\frac{s\eta}{2|B_{n}|}\Big{)}$
$\displaystyle~{}~{}~{}+\sum_{u\in B_{n}}\Big{(}\sqrt{(1-s)\eta
q}\,y^{\lambda}_{u}\theta_{u}-\frac{(1-s)\eta q}{2}\Big{)},$

where $q\geq 0$ is a fixed constant to be chosen later,
$Y_{uv}^{s\eta}=\sqrt{\frac{s\eta}{|B_{n}|}}\theta_{0u}\theta_{0v}+Z_{uv}$ and
$y^{\lambda}=\sqrt{\lambda}\theta_{0u}+z_{u}$ with $\lambda=(1-s)\eta q$ and
$Z_{uv}$ and $z_{u}$ are independent $N(0,1)$ r.v.’s. From now on we denote
the hidden assignment by $(\theta_{0u})_{u\in B_{n}}$ in order to distinguish
it from a generic vector $(\theta_{u})_{u\in B_{n}}$. The interpolating free
energy is

$\varphi(s)=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{H_{s}(\theta)}\Big{\\}}.$

Note that $\varphi(1)=f_{B_{n}}(\delta,\eta)$. On the other end of the
interpolation,

$\displaystyle\varphi(0)$
$\displaystyle=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{H^{\delta}_{B_{n}}(\theta)+\underset{u\in
B_{n}}{\sum}(\sqrt{\eta q}y^{\lambda}_{u}\theta_{u}-\frac{\eta
q}{2})}\Big{\\}}$ $\displaystyle=f^{\textup{{sc}}}_{B_{n}}(\delta,\eta q).$

We compute the derivative of $\varphi$ using gaussian integration by parts to
obtain

$\varphi^{\prime}(s)=-\frac{\eta}{4}\operatorname{\mathbb{E}}\big{\langle}(R_{1,2}(B_{n})-q)^{2}\big{\rangle}_{s}+\frac{\eta}{2}\operatorname{\mathbb{E}}\big{\langle}(R_{1,0}(B_{n})-q)^{2}\big{\rangle}_{s}-\frac{\eta
q^{2}}{4},$

where $\langle\cdot\rangle_{s}$ is the Gibbs measure associated to the
Hamiltonian $H_{s}$. (Here and from now on,
$R_{1,0}(B_{n}):=\frac{1}{|B_{n}|}\sum_{u\in B_{n}}\theta_{u}\theta_{0u}$.) By
Bayes’ rule $R_{1,2}(B_{n})$ and $R_{1,0}(B_{n})$ are identical in law, and we
obtain

$\varphi^{\prime}(s)=\frac{\eta}{4}\operatorname{\mathbb{E}}\big{\langle}(R_{1,2}(B_{n})-q)^{2}\big{\rangle}_{s}-\frac{\eta
q^{2}}{4}.$

Since the first in the right-hand side in the above display is non-negative,
we obtain the lower bound $\varphi^{\prime}(s)\geq-\frac{\eta q^{2}}{4}$ for
all $s$. Integrating w.r.t. $s$ yields the lower bound

$f_{B_{n}}(\delta,\eta)\geq f^{\textup{{sc}}}_{B_{n}}(\delta,\eta
q)-\frac{\eta q^{2}}{4},$

valid for all $n$ and all $q$. From Proposition 6.1,
$f^{\textup{{sc}}}_{B_{n}}$ converges to $f^{\textup{{sc}}}$ as $n\to\infty$,
hence the lower bound

$\liminf_{n\to\infty}f_{B_{n}}(\delta,\eta)\geq\sup_{q\geq
0}\Big{\\{}f^{\textup{{sc}}}(\delta,\eta q)-\frac{\eta q^{2}}{4}\Big{\\}}.$
(8.1)

As for the upper, we use the same argument while fixing the value of the
overlap $R_{1,0}(B_{n})$ to a prescribed value $m$ along the interpolation.
Define the set $O_{n}:=\\{k/|B_{n}|:k\in\mathbb{Z},|k|\leq|B_{n}|\\}$ and let
$m\in O_{n}$. Consider the constrained free energy

$\varphi(s;m)=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{\tilde{H}_{s}(\theta)}\mathbf{1}_{R_{1,0}(B_{n})=m}\Big{\\}},$

where

$\displaystyle\tilde{H}_{s}(\theta)$
$\displaystyle=H^{\delta}_{B_{n}}(\theta)+\sum_{u,v\in
B_{n}}\Big{(}\sqrt{\frac{s\eta}{|B_{n}|}}Z_{uv}\theta_{u}\theta_{v}+\frac{s\eta}{|B_{n}|}\theta_{u}\theta_{v}\theta_{0u}\theta_{0v}-\frac{s\eta}{2|B_{n}|}\Big{)}$
$\displaystyle~{}~{}~{}+\sum_{u\in B_{n}}\Big{(}\sqrt{(1-s)\eta
q}\,z_{u}\theta_{u}+(1-s)\eta m\theta_{u}\theta_{0u}-\frac{(1-s)\eta
q}{2}\Big{)}.$

(Note that this Hamiltonian no longer corresponds to an inference problem as
before.) The derivative reads

$\varphi^{\prime}(s)=-\frac{\eta}{4}\operatorname{\mathbb{E}}\big{\langle}(R_{1,2}(B_{n})-q)^{2}\big{\rangle}_{s}+\frac{\eta}{2}\operatorname{\mathbb{E}}\big{\langle}(R_{1,0}(B_{n})-m)^{2}\big{\rangle}_{s}-\frac{\eta
m^{2}}{2}+\frac{\eta q^{2}}{4}.$

The middle term vanishes due the constraint on $R_{1,0}(B_{n})$ and we obtain
the upper bound $\varphi^{\prime}(s)\leq-\frac{\eta m^{2}}{2}+\frac{\eta
q^{2}}{4}$. Therefore

$\varphi(1;m)\leq\inf_{q\geq 0}\Big{\\{}\varphi(0;m)-\frac{\eta
m^{2}}{2}+\frac{\eta q^{2}}{4}\Big{\\}}.$ (8.2)

On the one hand we have
$\varphi(0;m)\leq\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,\eta m,\eta q)$,
where

$\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,\eta m,\eta
q):=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{H^{\delta}_{B_{n}}(\theta)+\underset{u\in
B_{n}}{\sum}(\sqrt{\eta q}z_{u}\theta_{u}+\eta
m\theta_{u}\theta_{0u}-\frac{\eta q}{2})}\Big{\\}}.$ (8.3)

We can follow the exact same argument leading to Proposition 6.1 to prove that
$\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,\eta m,\eta q)$ converges to a
limit $f^{\textup{{sc}}}(\delta,\eta m,\eta q)$ as $n\to\infty$; the only
difference being $m$ and $q$ are not necessarily equal, but this does not
alter the argument in any significant way. Moreover, the convergence is
uniform on any compact set
$K\subset[0,1]\times\mathbb{R}_{+}\times\mathbb{R}_{+}$.

On the other hand, let $Z_{n}(m)=2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{H_{B_{n}}^{\delta}(\theta)+H_{B_{n}}^{\eta}(\theta)}\mathbf{1}_{R_{1,0}(B_{n})=m}$.
We have

$\displaystyle f_{B_{n}}$
$\displaystyle=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\sum_{m\in
O_{n}}Z_{n}(m)$
$\displaystyle\leq\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\max_{m\in
O_{n}}Z_{n}(m)+\frac{\log(2|B_{n}|+1)}{|B_{n}|}$
$\displaystyle=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\max_{m\in O_{n}}\log
Z_{n}(m)+\frac{\log(2|B_{n}|+1)}{|B_{n}|}.$ (8.4)

At this point we want to show concentration of the random variables
$F_{n}(m):=\log Z_{n}(m)$ so that we can compare
$\operatorname{\mathbb{E}}\max_{m}F_{n}(m)$ with
$\max_{m}\operatorname{\mathbb{E}}F_{n}(m)$. First, the random variables
$\theta_{0u}$ are irrelevant as they can be absorbed in $\theta_{u}$ through
the change of variables $\theta_{u}\theta_{0u}\mapsto\theta_{u}$ without
changing the distribution of $\\{F_{n}(m):m\in O_{n}\\}$. So without loss of
generality we set $\theta_{0u}=1$ for all $u\in B_{n}$. Now we deal with the
randomness of $Z_{uv}$ and $Y^{\delta}_{uv}$. We use the so-called entropy
method. We see $F_{n}(m)$ as a measurable Lipschitz function of the random
variables $(Z_{uv})_{u,v\in B_{n}}$ and $(Y^{\delta}_{uv})_{u,v\in
B_{n},|u-v|=1}$. Since we are only interested in an upper tail bound, it is
enough to prove a logarithmic Sobolev inequality of the form

$\mathds{H}\big{(}e^{\gamma
F_{n}}\big{)}\leq\frac{\gamma^{2}\sigma_{n}^{2}}{2}\operatorname{\mathbb{E}}\big{[}e^{\gamma
F_{n}}\big{]}~{}~{}~{}\mbox{for all}~{}~{}\gamma\geq 0,$ (8.5)

for some $\sigma_{n}>0$, where we define the ‘entropy’ functional of a
positive random variable $Y$ by

$\mathds{H}(Y):=\operatorname{\mathbb{E}}Y\log
Y-\operatorname{\mathbb{E}}Y\log\operatorname{\mathbb{E}}Y.$

In our particular case, we will show that (8.5) holds with
$\sigma_{n}^{2}=(\frac{\eta}{2}+2dc(\beta))|B_{n}|$ for some finite constant
$c(\beta)>0$. We momentarily assume this to be true in order to finish the
general argument, and then return to its proof later on. Herbst’s argument;
see [BLM13], then implies a sub-Gaussian bound on the moment generating
function:

$\operatorname{\mathbb{E}}e^{\gamma(F_{n}-\operatorname{\mathbb{E}}F_{n})}\leq
e^{\gamma^{2}\sigma_{n}^{2}/2}~{}~{}~{}\mbox{for all}~{}~{}\gamma\geq 0.$

This in turn implies a bound on the expected maximum deviation
$\operatorname{\mathbb{E}}\max(F_{n}-\operatorname{\mathbb{E}}F_{n})$:

$\displaystyle\operatorname{\mathbb{E}}\Big{[}\max_{m\in
O_{n}}\\{F_{n}(m)-\operatorname{\mathbb{E}}F_{n}(m)\\}\Big{]}$
$\displaystyle\leq\frac{1}{\gamma}\log\Big{\\{}\sum_{m\in
O_{n}}\operatorname{\mathbb{E}}e^{\gamma(F_{n}(m)-\operatorname{\mathbb{E}}F_{n}(m))}\Big{\\}}$
$\displaystyle\leq\frac{\log(2|B_{n}|+1)}{\gamma}+\frac{\gamma\sigma_{n}^{2}}{2}.$

We let $\gamma=1/\sqrt{|B_{n}|}$ and obtain that the above is bounded by
$\mathcal{O}\big{(}\sqrt{|B_{n}|}\log|B_{n}|\big{)}$. Now, coming back to
(8.2), we obtain

$f_{B_{n}}\leq\frac{1}{|B_{n}|}\max_{m\in O_{n}}\operatorname{\mathbb{E}}\log
Z_{n}(m)+\mathcal{O}\Big{(}\frac{\log|B_{n}|}{\sqrt{|B_{n}|}}\Big{)}.$

We notice that $\operatorname{\mathbb{E}}\log Z_{n}(m)=\varphi(1;m)$, thus the
interpolation upper bound (8.2) and (8.3) imply

$f_{B_{n}}\leq\sup_{m\in[-1,1]}\inf_{q\geq
0}\Big{\\{}\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,\eta m,\eta
q)-\frac{\eta m^{2}}{2}+\frac{\eta
q^{2}}{4}\Big{\\}}+\mathcal{O}\Big{(}\frac{\log|B_{n}|}{\sqrt{|B_{n}|}}\Big{)}.$
(8.6)

Since $\widetilde{f^{\textup{{sc}}}_{B_{n}}}$ converges uniformly to
$\widetilde{f^{\textup{{sc}}}}$ on any compact set, this implies the upper
bound

$\limsup_{n\to\infty}f_{B_{n}}\leq\sup_{m\in[-1,1]}\inf_{q\geq
0}\Big{\\{}\widetilde{f^{\textup{{sc}}}}(\delta,\eta m,\eta q)-\frac{\eta
m^{2}}{2}+\frac{\eta q^{2}}{4}\Big{\\}}.$ (8.7)

Next, we show that the upper and lower bounds (8.7) and (8.1) match. For any
$m\in[-1,1]$ we obtain an upper bound on (8.7) by letting $q=|m|$. Now observe
that the map $r\mapsto\widetilde{f^{\textup{{sc}}}}(\delta,r,s)$ is even since
$r\mapsto\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,r,s)$ is even. This
implies the bound

$\limsup_{n\to\infty}f_{B_{n}}\leq\sup_{m\in[-1,1]}\Big{\\{}\widetilde{f^{\textup{{sc}}}}(\delta,\eta|m|,\eta|m|)-\frac{\eta|m|^{2}}{4}\Big{\\}},$

which is identical to the lower bound since
$\widetilde{f^{\textup{{sc}}}}(\delta,r,r)=f^{\textup{{sc}}}(\delta,r)$ for
$r\geq 0$, and thus we conclude that $f_{B_{n}}$ has a limit given by the
above variational formula.

Now it remains to prove the log-Sobolev inequality (8.5).

###### Proof of the bound (8.5).

We lighten the notation and denote by $X=(X_{1},\cdots,X_{N})$ the random
variables $\\{Z_{uv}:u,v\in B_{n}\\}\cup\\{Y^{\delta}_{uv}:u,v\in
B_{n},|u-v|=1\\}$: we have $X_{i}=Z_{uv}$ for some one-to-one mapping
$(u,v)\mapsto i$ for $1\leq i\leq N_{1}$, and $X_{i}=Y^{\delta}_{uv}$ for
$N_{1}+1\leq i\leq N$. Denote $F=F(X_{1},\cdots,X_{N})$ the random variable
$F_{n}(m)=\log Z_{n}(m)$. Denote $X^{\setminus
k}=(X_{1},\cdots,X_{k-1},X_{k+1},\cdots,X_{N})$. The following tensorization
formula for the entropy $\mathds{H}$ is well known; see e.g. [BLM13]: for all
$\gamma\geq 0$,

$\mathds{H}\big{(}e^{\gamma
F}\big{)}\leq\operatorname{\mathbb{E}}\Big{[}\sum_{k=1}^{N}\mathds{H}\big{(}e^{\gamma
F}\big{|}X^{\setminus k}\big{)}\Big{]}.$ (8.8)

Therefore is suffices to bound the entropies $\mathds{H}\big{(}e^{\gamma
F}\big{|}X^{\setminus k}\big{)}$ in which $F$ is seen as a univariate function
of $X_{k}$. For $1\leq k\leq N_{1}$ the variable $X_{k}$ is Gaussian $N(0,1)$.
We use the Gaussian logarithmic Sobolev inequality (Theorem 5.4 in [BLM13])

$\mathds{H}\big{(}e^{\gamma F}\big{|}X^{\setminus
k}\big{)}\leq\frac{\gamma^{2}}{2}\operatorname{\mathbb{E}}\big{[}(\partial_{k}F)^{2}e^{\gamma
F}\big{|}X^{\setminus k}\big{]},$

valid for all $\gamma\geq 0$. Since
$\partial_{k}F=\sqrt{\frac{\eta}{|B_{n}|}}\langle\theta_{u}\theta_{v}\rangle$,
we have $|\partial_{k}F|\leq\sqrt{\frac{\eta}{|B_{n}|}}$, and therefore

$\mathds{H}\big{(}e^{\gamma F}\big{|}X^{\setminus
k}\big{)}\leq\frac{\gamma^{2}\eta}{2|B_{n}|}\operatorname{\mathbb{E}}\big{[}e^{\gamma
F}\big{|}X^{\setminus k}\big{]}.$ (8.9)

For $N_{1}+1\leq k\leq N$ the variable $X_{k}$ is Rademacher with probability
$1-p$ for taking the value $1$ and probability $p$ for $-1$. We use the
following logarithmic Sobolev inequality for Rademacher random variables
(Theorem 5.2 in [BLM13]) :

$\mathds{H}\big{(}e^{\gamma F}\big{|}X^{\setminus
k}\big{)}\leq\frac{c(p)}{2}\operatorname{\mathbb{E}}\Big{[}\big{(}e^{\gamma
F/2}-e^{\gamma\tilde{F}^{(k)}/2}\big{)}^{2}\big{|}X^{\setminus k}\Big{]},$

where $c(p)=\frac{1}{1-2p}\log(\frac{1-p}{p})=2\beta/\delta$ and
$\tilde{F}^{(k)}=F(X_{1},\cdots,X_{k}^{\prime},\cdots,X_{N})$ where
$X_{k}^{\prime}$ is an independent copy of $X_{k}$. By convexity of the
exponential, $e^{t}\leq e^{s}+(t-s)e^{t}$ for all $t,s\in\mathbb{R}$, so

$\displaystyle\operatorname{\mathbb{E}}\Big{[}\big{(}e^{\gamma
F/2}-e^{\gamma\tilde{F}^{(k)}/2}\big{)}^{2}\big{|}X^{\setminus k}\Big{]}$
$\displaystyle\leq\frac{\gamma^{2}}{4}\operatorname{\mathbb{E}}\Big{[}(F-\tilde{F}^{(k)})^{2}e^{\gamma
F}\mathbf{1}_{F\geq\tilde{F}^{(k)}}\big{|}X^{\setminus k}\Big{]}$
$\displaystyle~{}~{}+\frac{\gamma^{2}}{4}\operatorname{\mathbb{E}}\Big{[}(\tilde{F}^{(k)}-F)^{2}e^{\gamma\tilde{F}^{(k)}}\mathbf{1}_{F\leq\tilde{F}^{(k)}}\big{|}X^{\setminus
k}\Big{]}$
$\displaystyle=\frac{\gamma^{2}}{2}\operatorname{\mathbb{E}}\Big{[}(F-\tilde{F}^{(k)})^{2}e^{\gamma
F}\mathbf{1}_{F\geq\tilde{F}^{(k)}}\big{|}X^{\setminus k}\Big{]}.$

The last line follows since the two terms in the first inequality are
identical. Now since $\partial_{k}F=\beta\langle\theta_{u}\theta_{v}\rangle$
which is $\leq\beta$ in absolute value, we have
$|F-\tilde{F}^{(k)}|\leq\beta|X_{k}-X_{k}^{\prime}|\leq 2\beta$. Plugging this
estimate into the above bounds we obtain

$\mathds{H}\big{(}e^{\gamma F}\big{|}X^{\setminus k}\big{)}\leq
c(p)\beta^{2}\gamma^{2}\operatorname{\mathbb{E}}\big{[}e^{\gamma
F}\big{|}X^{\setminus k}\big{]}.$ (8.10)

Now we combine the two bounds (8.9) and (8.10) into (8.8) to obtain

$\displaystyle\mathds{H}\big{(}e^{\gamma F}\big{)}$
$\displaystyle\leq\Big{(}\frac{\gamma^{2}\eta}{2|B_{n}|}{|B_{n}|\choose
2}+c(p)\beta^{2}\gamma^{2}d|B_{n}|\Big{)}\operatorname{\mathbb{E}}\big{[}e^{\gamma
F}\big{]}$
$\displaystyle\leq\frac{\gamma^{2}\sigma_{n}^{2}}{2}\operatorname{\mathbb{E}}\big{[}e^{\gamma
F}\big{]},$

with $\sigma_{n}^{2}=(\frac{\eta}{2}+2c(p)\beta^{2}d)|B_{n}|$. $\blacksquare$

###  8.3 Proof of Propositions 6.5 and 6.9

In this subsection we prove convergence of the free energies of the one-block
and two-block posteriors respectively. The difference with the setting of
Proposition 6.3 is the inhomogeneity of the SNR in the GOE side information,
e.g., pairs of vertices in $B\setminus B^{\prime}$ have a different SNR than
the ones in $B\cap B^{\prime}$. Although we apply the same approach, the
inhomogeneity will lead to technical complications which prevent us from
proving equality of the upper and lower bounds achieved via the interpolation
method. Nevertheless, Assumption 1 allows us to salvage this situation for
small $\eta$.

We only write a detailed argument for Proposition 6.5; the proof extends
verbatim to Proposition 6.9.

Recall that for a given block $B$, the one-block posterior is given by

$\operatorname{\mathbb{P}}\Big{(}\big{(}\theta_{x}\big{)}_{x\in
B}\big{|}Y^{\delta}_{B},Y^{\eta}_{B}\Big{)}=\frac{1}{Z_{B}}\omega^{\mbox{\rm\tiny
SK}}_{B}(\theta)\cdot e^{H_{B}^{\delta}(\theta)},$

and for two adjacent blocks $B$ and $B^{\prime}$, the two-block posterior is

$\operatorname{\mathbb{P}}\Big{(}\big{(}\theta_{x}\big{)}_{x\in B\cup
B^{\prime}}\big{|}\bigcup_{A\in\\{B,B^{\prime}\\}}\\{Y^{\delta}_{A},Y^{\eta}_{A}\\}\Big{)}=\frac{1}{Z_{B\cup
B^{\prime}}}\omega_{B\cup B^{\prime}}^{\mbox{\rm\tiny SK}}(\theta)\cdot
e^{H_{B\cup B^{\prime}}^{\delta}(\theta)},$

where

$H_{B\cup B^{\prime}}^{\delta}(\theta):=\beta\sum_{\underset{|u-v|=1}{u,v\in
B\cup B^{\prime}}}Y^{\delta}_{uv}\theta_{u}\theta_{v},$

and for $\theta=(\theta_{B},\theta_{B^{\prime}})\in\\{\pm 1\\}^{B\cup
B^{\prime}}$,

$\displaystyle\omega_{B\cup B^{\prime}}^{\mbox{\rm\tiny SK}}(\theta)$
$\displaystyle:=\prod_{B^{\prime\prime}\sim
B}e^{H^{\eta}_{B^{\prime\prime}}(\theta_{B})}\cdot\prod_{B^{\prime\prime}\sim
B^{\prime}}e^{H^{\eta}_{B^{\prime\prime}}(\theta_{B^{\prime}})}.$

The free energies of the above posteriors are

$\displaystyle f_{B}$
$\displaystyle=\frac{1}{|B|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B|}\sum_{\theta\in\\{\pm
1\\}^{B}}\omega^{\mbox{\rm\tiny SK}}_{B}(\theta)\cdot
e^{H_{B}^{\delta}(\theta)}\Big{\\}}~{}~{}~{}\mbox{and}$ $\displaystyle
f_{B\cup B^{\prime}}$
$\displaystyle=\frac{1}{|B|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B\cup
B^{\prime}|}\sum_{\theta\in\\{\pm 1\\}^{B\cup
B^{\prime}}}\omega^{\mbox{\rm\tiny SK}}_{B\cup B^{\prime}}(\theta)\cdot
e^{H_{B\cup B^{\prime}}^{\delta}(\theta)}\Big{\\}}.$

###  8.4 Limit of $f_{B}$

The same arguments already used can be applied: rather than having one
parameter in the interpolation argument, we will have several, each one
assigned to a specific spatial region. As before, we prove the lower and upper
bounds separately. The overlap replacement in the interpolation proceeds
according to the following table with $2d+1$ free parameters:

$\displaystyle R_{1,2}\big{(}B^{\bullet}\big{)}~{}$
$\displaystyle\longleftrightarrow~{}q^{\bullet}$ $\displaystyle R_{1,2}(B\cap
B^{\prime})~{}$ $\displaystyle\longleftrightarrow~{}q_{B\cap
B^{\prime}},~{}~{}~{}\forall~{}B^{\prime}\sim B,$

In the above, we denote $B^{\bullet}=B\setminus\underset{B^{\prime}\sim
B}{\cup}B^{\prime}$. Overlaps in other regions are then obtained as convex
combinations of $\\{q^{\bullet},q_{B\cap B^{\prime}}:B^{\prime}\sim B\\}$. For
instance, with $\alpha^{\prime}=\frac{|B\cap B^{\prime}|}{|B|}$, we have

$\displaystyle R_{1,2}(B)~{}$
$\displaystyle\longleftrightarrow~{}q_{B}:=(1-2d\alpha^{\prime})q^{\bullet}+\sum_{B^{\prime}\sim
B}\alpha^{\prime}q_{B\cap B^{\prime}},$ $\displaystyle R_{1,2}(B\setminus
B^{\prime})~{}$ $\displaystyle\longleftrightarrow~{}q_{B\setminus
B^{\prime}}:=\frac{1-2d\alpha^{\prime}}{1-\alpha^{\prime}}q^{\bullet}+\sum_{\underset{B^{\prime\prime}\neq
B^{\prime}}{B^{\prime\prime}\sim
B}}\frac{\alpha^{\prime}}{1-\alpha^{\prime}}q_{B\cap B^{\prime\prime}}.$

For all the arguments to come, we will be neglecting a
$\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{\scalebox{0.7}{$\scriptscriptstyle\mathcal{O}$}}_{L^{\circlearrowleft}}(1)$
error stemming from replacing $\alpha^{\prime}$ which a priori varies with
$L^{\circlearrowleft}$ with its limit $\alpha$. This can be safely done
because all involved quantities are Lipschitz in $\alpha^{\prime}$. So tacitly
assume $\alpha^{\prime}=\alpha$ with no further comment.

We let $h^{\textup{{sc}}}(\theta_{B};\lambda):=\sum_{x\in
B}(\sqrt{\lambda}y_{x}\theta_{x}-\lambda/2)$, where
$y_{x}=\sqrt{\lambda}\theta_{x}+z_{x}$. With this notation, we interpolate
between the two Hamiltonians

$\displaystyle H^{\eta}_{B^{\prime}}(\theta_{B})~{}$
$\displaystyle\longleftrightarrow~{}h^{\textup{{sc}}}(\theta_{B};t\eta
q_{B})+h^{\textup{{sc}}}(\theta_{B\cap B^{\prime}};(1-t)\eta q_{B\cap
B^{\prime}})+h^{\textup{{sc}}}(\theta_{B\setminus B^{\prime}};(1-t)\eta
q_{B\setminus B^{\prime}}).$

Interpolating à la Guerra, the derivative along the interpolation path reads

$\displaystyle\varphi^{\prime}$ $\displaystyle=\sum_{B^{\prime}\sim
B}\Big{\\{}\frac{t\eta}{4}\Big{(}\operatorname{\mathbb{E}}\big{\langle}\big{(}R_{1,2}(B)-q_{B}\big{)}^{2}\big{\rangle}-q_{B}^{2}\Big{)}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\alpha\frac{(1-t)\eta}{4}\Big{(}\operatorname{\mathbb{E}}\big{\langle}\big{(}R_{1,2}(B\cap
B^{\prime})-q_{B\cap B^{\prime}}\big{)}^{2}\big{\rangle}-q_{B\cap
B^{\prime}}^{2}\Big{)}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+(1-\alpha)\frac{(1-t)\eta}{4}\Big{(}\operatorname{\mathbb{E}}\big{\langle}\big{(}R_{1,2}(B\setminus
B^{\prime})-q_{B\setminus B^{\prime}}\big{)}^{2}\big{\rangle}-q_{B\setminus
B^{\prime}}^{2}\Big{)}\Big{\\}}.$

Dropping the squared differences which are nonnegative we obtain a lower bound

$\displaystyle\varphi^{\prime}$
$\displaystyle\geq-\frac{\eta}{4}\sum_{B^{\prime}\sim
B}\Big{(}tq_{B}^{2}+\alpha(1-t)q_{B\cap
B^{\prime}}^{2}+(1-\alpha)(1-t)q_{B\setminus B^{\prime}}^{2}\Big{)}.$

At the decoupled end of the interpolation, the free energy reads

$\displaystyle\varphi(0)=\frac{1}{|B|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B|}\sum_{\theta\in\\{\pm
1\\}^{B}}e^{H_{B}^{\delta}(\theta)}\omega(\theta)\Big{\\}},$

where

$\displaystyle\omega(\theta)$ $\displaystyle=\prod_{B^{\prime}\sim
B}\exp\Big{\\{}h^{\textup{{sc}}}(\theta_{B};t\eta
q_{B})+h^{\textup{{sc}}}(\theta_{B\cap B^{\prime}};(1-t)\eta q_{B\cap
B^{\prime}})+h^{\textup{{sc}}}(\theta_{B\setminus B^{\prime}};(1-t)\eta
q_{B\setminus B^{\prime}})\Big{\\}}$ $\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\exp\big{\\{}h^{\textup{{sc}}}(\theta_{B^{\bullet}};r^{\bullet})\\}\cdot\prod_{B^{\prime}\sim
B}\exp\big{\\{}h^{\textup{{sc}}}(\theta_{B\cap B^{\prime}};r_{B\cap
B^{\prime}})\big{\\}},$

where

$\displaystyle r^{\bullet}$ $\displaystyle:=\sum_{B^{\prime}\sim B}(t\eta
q_{B}+(1-t)\eta q_{B\setminus B^{\prime}}),$ (8.11) $\displaystyle r_{B\cap
B^{\prime}}$ $\displaystyle:=2dt\eta q_{B}+(1-t)\eta q_{B\cap
B^{\prime}}+\sum_{\underset{B^{\prime\prime}\neq
B^{\prime}}{B^{\prime\prime}\sim B}}(1-t)\eta q_{B\setminus
B^{\prime\prime}}.$ (8.12)

From this expression we can obtain an asymptotic formula for $\varphi(0)$ as
$L^{\circlearrowleft}\to\infty$. We partition $B$ into
$B^{\bullet}\cup_{B^{\prime}\sim B}(B\cap B^{\prime})$, and observe that
omitting the interactions corresponding to the edges of $\mathbb{Z}^{d}$
crossing the boundaries of this partition in the Hamiltonian
$H^{\delta}_{B}(\theta)$ contributes an error term
$o_{L^{\circlearrowleft}}(1)$:

$\lim_{L^{\circlearrowleft}\to\infty}\varphi(0)=(1-2d\alpha)f^{\textup{{sc}}}(\delta;r^{\bullet})+\alpha\sum_{B^{\prime}\sim
B}f^{\textup{{sc}}}(\delta;r_{B^{\prime}}).$

Thus we obtain a lower bound on the free energy $f_{B}$:

$\liminf_{L^{\circlearrowleft}\to\infty}f_{B}\geq\phi_{1},$ (8.13)

where, letting $\underline{q}=\\{q^{\bullet},q_{B\cap
B^{\prime}}:B^{\prime}\sim B\\}$,

$\displaystyle\phi_{1}:=$
$\displaystyle\sup_{\underline{q}\in[0,1]^{2d+1}}\Big{\\{}(1-2d\alpha)f^{\textup{{sc}}}(\delta;r^{\bullet})+\alpha\sum_{B^{\prime}\sim
B}f^{\textup{{sc}}}(\delta;r_{B\cap B^{\prime}})$ $\displaystyle\hskip
56.9055pt-\frac{1}{4}\sum_{B^{\prime}\sim B}\Big{(}t\eta
q_{B}^{2}+\alpha(1-t)\eta q_{B\cap B^{\prime}}^{2}+(1-\alpha)(1-t)\eta
q_{B\setminus B^{\prime}}^{2}\Big{)}\Big{\\}}.$ (8.14)

Now we prove an upper bound by restricting to configurations of fixed overlaps
$\underline{m}=\\{m^{\bullet},m_{B\cap B^{\prime}}:B^{\prime}\sim B\\}$,
exactly in the same way as done for $f_{B_{n}}(\delta,\eta)$. We consider the
restricted free energy

$\varphi(s;\underline{m})=\frac{1}{|B|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B|}\sum_{\theta\in\\{\pm
1\\}^{B}}\omega_{B}^{\mbox{\rm\tiny
SK}}(\theta;s)e^{H^{\delta}_{B}(\theta)}\mathbf{1}_{\underset{R_{1,0}(B^{\bullet})=m^{\bullet}}{R_{1,0}(B\cap
B^{\prime})=m_{B\cap B^{\prime}}\forall B^{\prime}\sim B,}}\Big{\\}}$

where

$\omega_{B}^{\mbox{\rm\tiny SK}}(\theta;s)=\prod_{B^{\prime}\sim
B}e^{H^{\eta}_{B^{\prime}}(\theta;s)},$

and for each $B^{\prime}\sim B$,

$H^{\eta}_{B^{\prime}}(\theta;s)=I+II+III,$ $\displaystyle I$
$\displaystyle=\sum_{u,v\in
B}\Big{(}\sqrt{\frac{ts\eta}{|B|}}Z_{uv}^{(a,\bullet)}\theta_{u}\theta_{v}+\frac{ts\eta}{|B|}\theta_{u}\theta_{v}\theta_{0u}\theta_{0v}-\frac{ts\eta}{2|B|}\Big{)}$
$\displaystyle~{}~{}~{}+\sum_{u\in B}\Big{(}\sqrt{(1-s)t\eta
q_{B}}\,z^{(a,\bullet)}_{u}\theta_{u}+(1-s)t\eta
m_{B}\theta_{u}\theta_{0u}-\frac{(1-s)t\eta q_{B}}{2}\Big{)},$ $\displaystyle
II$ $\displaystyle=\sum_{u,v\in B\cap
B^{\prime}}\Big{(}\sqrt{\frac{(1-t)s\eta}{|B\cap
B^{\prime}|}}Z_{uv}^{(a,\cap)}\theta_{u}\theta_{v}+\frac{(1-t)s\eta}{|B\cap
B^{\prime}|}\theta_{u}\theta_{v}\theta_{0u}\theta_{0v}-\frac{(1-t)s\eta}{2|B\cap
B^{\prime}|}\Big{)}$ $\displaystyle~{}~{}~{}+\sum_{u\in B\cap
B^{\prime}}\Big{(}\sqrt{(1-t)(1-s)\eta q_{B\cap
B^{\prime}}}\,z_{u}^{(a,\cap)}\theta_{u}+(1-s)(1-t)\eta m_{B\cap
B^{\prime}}\theta_{u}\theta_{0u}-\frac{(1-t)(1-s)\eta q_{B\cap
B^{\prime}}}{2}\Big{)}$ $\displaystyle III$ $\displaystyle=\sum_{u,v\in
B\setminus B^{\prime}}\Big{(}\sqrt{\frac{(1-t)s\eta}{|B\setminus
B^{\prime}|}}Z_{uv}^{(a,\setminus)}\theta_{u}\theta_{v}+\frac{(1-t)s\eta}{|B\setminus
B^{\prime}|}\theta_{u}\theta_{v}\theta_{0u}\theta_{0v}-\frac{(1-t)s\eta}{2|B\setminus
B^{\prime}|}\Big{)}$ $\displaystyle~{}~{}~{}+\sum_{u\in B\setminus
B^{\prime}}\Big{(}\sqrt{(1-t)(1-s)\eta q_{B\setminus
B^{\prime}}}\,z_{u}^{(a,\setminus)}\theta_{u}+(1-s)(1-t)\eta m_{B\setminus
B^{\prime}}\theta_{u}\theta_{0u}-\frac{(1-t)(1-s)\eta q_{B\setminus
B^{\prime}}}{2}\Big{)},$

where

$\displaystyle m_{B}$
$\displaystyle=(1-2d\alpha)m^{\bullet}+\sum_{B^{\prime}\sim B}\alpha m_{B\cap
B^{\prime}}~{}~{}~{}\mbox{and}$ $\displaystyle m_{B\setminus B^{\prime}}$
$\displaystyle=\frac{1-2d\alpha}{1-\alpha}m^{\bullet}+\sum_{\underset{B^{\prime\prime}\neq
B^{\prime}}{B^{\prime\prime}\sim B}}\frac{\alpha}{1-\alpha}m_{B\cap
B^{\prime\prime}}.$

Observe that at $s=1$ the Hamiltonian $H^{\eta}_{B^{\prime}}(\theta;s)$ is
equal to the $H^{\eta}_{B^{\prime}}(\theta)$ given in Eq. (6.15). Conducting
exactly the same argument as in subsection 8.2 we obtain an upper bound

$\limsup_{L^{\circlearrowleft}\to\infty}f_{B}\leq\tilde{\phi}_{1},$ (8.15)

where

$\displaystyle\tilde{\phi}_{1}$
$\displaystyle=\sup_{\underline{m}\in[-1,1]^{2d+1}}\inf_{\underline{q}\in[0,1]^{2d+1}}\Big{\\{}(1-2d\alpha)\widetilde{f^{\textup{{sc}}}}(\delta,s^{\bullet},r^{\bullet})+\alpha\sum_{B^{\prime}\sim
B}\widetilde{f^{\textup{{sc}}}}(\delta;s_{B\cap B^{\prime}},r_{B\cap
B^{\prime}})$ $\displaystyle\hskip 56.9055pt-\frac{1}{2}\sum_{B^{\prime}\sim
B}\Big{(}t\eta m_{B}^{2}+\alpha(1-t)\eta m_{B\cap
B^{\prime}}^{2}+(1-\alpha)(1-t)\eta m_{B\setminus B^{\prime}}^{2}\Big{)}$
$\displaystyle\hskip 56.9055pt+\frac{1}{4}\sum_{B^{\prime}\sim B}\Big{(}t\eta
q_{B}^{2}+\alpha(1-t)\eta q_{B\cap B^{\prime}}^{2}+(1-\alpha)(1-t)\eta
q_{B\setminus B^{\prime}}^{2}\Big{)}\Big{\\}},$ (8.16)

where $r^{\bullet}$ and $r_{B\cap B^{\prime}}$ are defined in (8.11) and
(8.12) respectively, and $s^{\bullet}$ and $s_{B\cap B^{\prime}}$ are defined
similarly, with $m_{B}$, $m_{B\cap B^{\prime}}$ and $m_{B\setminus
B^{\prime}}$ replacing $q_{B}$, $q_{B\cap B^{\prime}}$ and $q_{B\setminus
B^{\prime}}$ respectively in those definitions.

Next, if we could argue that the supremum in $\underline{m}$ in formula (8.4)
is achieved when all coordinates of $\underline{m}$ are nonnegative, then we
can see that this formula matches the lower bound (8.4) simply by setting
$q^{\bullet}=m^{\bullet}$ and $q_{B\cap B^{\prime}}=m_{B\cap B^{\prime}}$ for
all $B^{\prime}\sim B$, and we would be able prove that
$\underset{L^{\circlearrowleft}\to\infty}{\lim}f_{B}=\phi_{1}$. Unfortunately
we are unable to follow this line of reasoning: The fact that the map
$s\mapsto\widetilde{f^{\textup{{sc}}}}(\delta;s,r)$ is even provides little
leverage to argue about every single coordinate of $\underline{m}$.
Nevertheless we will see that under Assumption 1 both formulas can be
simplified: the optimal values of the parameters must all be equal, and this
implies equality of $\phi_{1}$ and $\tilde{\phi}_{1}$.

###  8.5 Reducing the number of parameters

We show that under Assumption 1, the variational formulas defining $\phi_{1}$
Eq. (8.4) and $\tilde{\phi}_{1}$ Eq. (8.4) are achieved when all the overlap
parameters become equal when $\eta$ is small. This allows to argue that
$\phi_{1}=\tilde{\phi}_{1}$ in this regime, and thus leads to the simplified
formula $\phi_{1}=\phi(\delta,2d\eta)$, Eq.(6.19).

We start by writing the first-order stationarity conditions for the optimality
of $\underline{q}$. Let $F=F(\underline{q})$ be the potential being maximized
in (8.4). Via straightforward computations we can write the derivatives of the
potential $F$ w.r.t. $\underline{q}$ in a condensed form. We fix an ordering
of the variables $\\{q^{\bullet},q_{B\cap B^{\prime}}:B^{\prime}\sim B\\}$ and
consider $\underline{q}$ as a vector of size $2d+1$. For all $i\in[2d+1]$,

$\displaystyle\frac{\mathrm{d}F}{\mathrm{d}\underline{q}_{i}}$
$\displaystyle=(1-2\alpha
d)\frac{\mathrm{d}r^{\bullet}}{\mathrm{d}\underline{q}_{i}}\cdot\big{(}{f^{\textup{{sc}}}}^{\prime}(\delta;r^{\bullet})-\frac{q^{\bullet}}{2}\big{)}+\alpha\sum_{B^{\prime}\sim
B}\frac{\mathrm{d}r_{B\cap
B^{\prime}}}{\mathrm{d}\underline{q}_{i}}\cdot\big{(}{f^{\textup{{sc}}}}^{\prime}(\delta;r_{B\cap
B^{\prime}})-\frac{q_{B\cap B^{\prime}}}{2}\big{)}.$

Observe from the above formula that optimizers $\underline{q}$ of (8.4) are in
the interior of $\mathbb{R}_{+}^{2d+1}$ if $\delta>\delta_{c}$. Indeed, since
$\frac{\mathrm{d}}{\mathrm{d}\lambda}f^{\textup{{sc}}}(\delta;\lambda)\geq\frac{\mathrm{d}}{\mathrm{d}\lambda}f^{\textup{{sc}}}(\delta;0^{+})>0$
when $\delta>\delta_{c}$, so the value $F(\underline{q})$ for a point
$\underline{q}$ on the boundary can always be improved.

Define the $2d+1\times 2d+1$ Jacobian matrix $J$ whose columns are the vectors
$(1-2\alpha
d)(\frac{\mathrm{d}r^{\bullet}}{\mathrm{d}\underline{q}_{i}})_{i\in[2d+1]}$,
$\alpha(\frac{\mathrm{d}r_{B^{\prime}}}{\mathrm{d}\underline{q}_{i}})_{i\in[2d+1]}$
for $B^{\prime}\sim B$. With this notation the gradient of the potential $F$
is given by

$\Big{(}\frac{\mathrm{d}F}{\mathrm{d}\underline{q}_{i}}\Big{)}_{i\in[2d+1]}=J\underline{x},$

where $\underline{x}\in\mathbb{R}^{2d+1}$ has coordinates
${f^{\textup{{sc}}}}^{\prime}(\delta;r^{\bullet})-\frac{q^{\bullet}}{2}$ and
${f^{\textup{{sc}}}}^{\prime}(\delta;r_{B\cap B^{\prime}})-\frac{q_{B\cap
B^{\prime}}}{2}$, $B^{\prime}\sim B$. This matrix only depends on the
parameters $t$ and $\eta$. Moreover,

######  Lemma 8.1.

If $t<1$ and $2\alpha d<1$ then the matrix $J$ is invertible.

###### Proof.

After some manipulations, the matrix $J$ can be written as

$\displaystyle J=\begin{pmatrix}a&\gamma&\cdots&\cdots&\gamma\\\
\gamma&b&\beta&\cdots&\beta\\\ \vdots&\beta&\ddots&\ddots&\vdots\\\
\vdots&\vdots&\ddots&\ddots&\beta\\\
\gamma&\beta&\cdots&\beta&b\end{pmatrix}\,,$

where

$\displaystyle a$ $\displaystyle=2d(1-2\alpha d)^{2}\frac{1-\alpha
t}{1-\alpha},~{}~{}~{}b=\alpha(1-(1-2\alpha d)t),$ $\displaystyle\beta$
$\displaystyle=\frac{\alpha^{2}}{1-\alpha}(2d-1+(1-2\alpha
d)t),~{}~{}~{}\gamma=\frac{\alpha}{1-\alpha}(1-2\alpha d)(2d-1+(1-2\alpha
d)t).$

Let $A$ be the lower principal minor of size $2d\times 2d$ (i.e., $A$ is
obtained by excluding the first row and first column of $J$). We can see that
$A=(b-\beta)I+\beta\mathbf{1}\mathbf{1}^{\top}$. Schur’s complement formula
implies that $J$ is invertible if and only if $a\neq 0$ and
$A-\frac{\gamma^{2}}{a}\mathbf{1}\mathbf{1}^{\top}$ is invertible. We have

$A-\frac{\gamma^{2}}{a}\mathbf{1}\mathbf{1}^{\top}=(b-\beta)I+(\beta-\frac{\gamma^{2}}{a})\mathbf{1}\mathbf{1}^{\top}.$

Direct computations show that

$\displaystyle b-\beta$ $\displaystyle=\frac{\alpha}{1-\alpha}(1-t)(1-2\alpha
d),$ $\displaystyle\beta-\frac{\gamma^{2}}{a}$
$\displaystyle=\frac{\alpha^{2}D}{(1-\alpha)(1-\alpha
t)}\big{(}(1-(1-\alpha)^{2})(2d-1+(1-2\alpha d)t)+1-t\big{)},$

with $D=\frac{2d-1+(1-2\alpha d)t}{2d}$. The above quantities are strictly
positive when $t<1$ and $2\alpha d<1$ so $J$ is invertible under these
conditions. $\blacksquare$

Therefore, the first-order stationarity conditions for $F$ imply
$\underline{x}=0$, i.e.,

${f^{\textup{{sc}}}}^{\prime}(\delta;r^{\bullet})=\frac{q^{\bullet}}{2}\quad\mbox{and}\quad{f^{\textup{{sc}}}}^{\prime}(\delta;r_{B\cap
B^{\prime}})=\frac{q_{B\cap B^{\prime}}}{2}~{}~{}~{}\forall~{}B^{\prime}\sim
B.$ (8.17)

######  Lemma 8.2.

Under Assumption 1, there exists $\eta_{0}>0$ depending on $d$, $\alpha$ and
$L$ such that if $\eta<\eta_{0}$, then all solutions $\underline{q}$ to (8.17)
must satisfy

$q^{\bullet}=q_{B\cap B^{\prime}}~{}~{}~{}\mbox{for all}~{}B^{\prime}\sim B.$

###### Proof.

We compute pairwise differences of the equations in (8.17) and use the assumed
Lipchitz property of
$\frac{\mathrm{d}}{\mathrm{d}\lambda}{f^{\textup{{sc}}}}$, as per item A1 of
Assumption 1: for $B^{\prime}$ and $B^{\prime\prime}$ two neighbors of $B$ we
have

$\displaystyle|q^{\bullet}-q_{B\cap B^{\prime}}|$ $\displaystyle\leq
2L|r^{\bullet}-r_{B\cap B^{\prime}}|,$ $\displaystyle|q_{B\cap
B^{\prime}}-q_{B\cap B^{\prime\prime}}|$ $\displaystyle\leq 2L|r_{B\cap
B^{\prime}}-r_{B\cap B^{\prime\prime}}|.$

On the other hand we have

$\displaystyle r^{\bullet}-r_{B\cap B^{\prime}}$
$\displaystyle=(1-t)\eta(q_{B\setminus B^{\prime}}-q_{B\cap B^{\prime}})$
$\displaystyle=\frac{(1-t)\eta}{1-\alpha}(q_{B}-q_{B\cap B^{\prime}}),$
$\displaystyle r_{B\cap B^{\prime}}-r_{B\cap B^{\prime\prime}}$
$\displaystyle=(1-t)\eta\big{(}(q_{B\cap B^{\prime}}-q_{B\cap
B^{\prime\prime}})-(q_{B\setminus B^{\prime}}-q_{B\setminus
B^{\prime\prime}})\big{)}$
$\displaystyle~{}~{}~{}=\frac{(1-t)\eta}{1-\alpha}(q_{B\cap
B^{\prime}}-q_{B\cap B^{\prime\prime}}).$

so

$\displaystyle|q^{\bullet}-q_{B\cap B^{\prime}}|$
$\displaystyle\leq\frac{2L\eta}{1-\alpha}|q_{B}-q_{B\cap B^{\prime}}|,$
$\displaystyle|q_{B\cap B^{\prime}}-q_{B\cap B^{\prime\prime}}|$
$\displaystyle\leq\frac{2L\eta}{1-\alpha}|q_{B\cap B^{\prime}}-q_{B\cap
B^{\prime\prime}}|.$

If $\frac{2L\eta}{1-\alpha}<1$ then the second inequality implies $q_{B\cap
B^{\prime}}=q_{B\cap B^{\prime\prime}}$ and so
$q_{B}=(1-2d\alpha)q^{\bullet}+2d\alpha q_{B\cap B^{\prime}}$ for any
$B^{\prime}\sim B$. The first inequality then implies

$|q^{\bullet}-q_{B\cap
B^{\prime}}|\leq\frac{2L\eta}{1-\alpha}(1-2d\alpha)|q^{\bullet}-q_{B\cap
B^{\prime}}|.$

If $\frac{2L\eta}{1-\alpha}(1-2d\alpha)<1$ then $q^{\bullet}=q_{B\cap
B^{\prime}}$ for all $B^{\prime}\sim B$. $\blacksquare$

Lemma 8.2 implies that the variational formula (8.4) can be simplified when
$\eta$ is small:

######  Corollary 8.3.

Under Assumption 1, there exists $\eta_{0}>0$ such that for
$\eta\in\mathbb{R}_{+}\setminus\mathcal{D}$ and $\eta\leq\eta_{0}$,

$\phi_{1}=\sup_{q\in[0,1]}\Big{\\{}f^{\textup{{sc}}}(\delta;2d\eta
q)-\frac{d}{2}\eta{q}^{2}\Big{\\}}.$

In particular, $\phi_{1}$ doesn’t depend on $t$.

Now we consider $\tilde{\phi}_{1}$ and apply the same argument. The saddle
point conditions of optimality of $\underline{m}$ and $\underline{q}$ in the
max-min problem (8.4) are

$\displaystyle\frac{\partial F}{\partial m_{i}}$
$\displaystyle=0~{}~{}\mbox{for all}~{}i\in[2d+1],$ (8.18)
$\displaystyle\frac{\partial F}{\partial q_{i}}$
$\displaystyle=0~{}~{}~{}\mbox{or}~{}~{}~{}q_{i}=0~{}~{}\mbox{for
all}~{}i\in[2d+1],.$ (8.19)

Condition (8.18) can be rewritten as $J\underline{x}=0$ where $J$ is the
matrix of Lemma 8.1 and $\underline{x}$ has coordinates
$\partial_{s}\tilde{f^{\textup{{sc}}}}(\delta;s^{\bullet},r^{\bullet})-m^{\bullet}$
and $\partial_{s}\tilde{f^{\textup{{sc}}}}(\delta;s_{B\cap
B^{\prime}},r_{B\cap B^{\prime}})-m_{B\cap B^{\prime}}$, $B^{\prime}\sim B$.

######  Lemma 8.4.

Under Assumption 1, there exists $\eta_{0}>0$ depending on $d$, $\alpha$ and
$L$ such that if $\eta<\eta_{0}$, then all solutions
$(\underline{m},\underline{q})$ to (8.18)-(8.19) must satisfy

$m^{\bullet}=m_{B\cap B^{\prime}}~{}~{}~{}\mbox{for all}~{}B^{\prime}\sim B.$

###### Proof.

Item A2 of Assumption 1 says that the map
$s\mapsto\partial_{s}\widetilde{f^{\textup{{sc}}}}(\delta;s,r)$ is Lipschitz
uniformly in $r$. Therefore the same argument of Lemma 8.2 can be applied to
reason that (8.18) implies $m^{\bullet}=m_{B\cap B^{\prime}}$ for all
$B^{\prime}\sim B$. $\blacksquare$

Given the result of the above lemma, we can simplify the formula (8.4) for
$\tilde{\phi}_{1}$ as follows:

$\displaystyle\tilde{\phi}_{1}$
$\displaystyle=\sup_{m\in[-1,1]}\inf_{\underline{q}\in[0,1]^{2d+1}}\Big{\\{}(1-2d\alpha)\widetilde{f^{\textup{{sc}}}}(\delta,2d\eta
m,r^{\bullet})+\alpha\sum_{B^{\prime}\sim
B}\widetilde{f^{\textup{{sc}}}}(\delta;2d\eta m,r_{B\cap B^{\prime}})$
$\displaystyle\hskip 113.81102pt-d\eta m^{2}$ $\displaystyle\hskip
56.9055pt+\frac{1}{4}\sum_{B^{\prime}\sim B}\Big{(}t\eta
q_{B}^{2}+\alpha(1-t)\eta q_{B\cap B^{\prime}}^{2}+(1-\alpha)(1-t)\eta
q_{B\setminus B^{\prime}}^{2}\Big{)}\Big{\\}}.$

Since $s\mapsto\widetilde{f^{\textup{{sc}}}}(\delta;s,r)$ is even there is no
loss in generality in assuming $m\geq 0$. Now we obtain
$\tilde{\phi}_{1}\leq\phi_{1}$ by setting all coordinates of $\underline{q}$
to the common value $m$. Finally, this implies equality:

######  Corollary 8.5.

Under Assumption 1, there exists $\eta_{0}>0$ such that for
$\eta\in\mathbb{R}_{+}\setminus\mathcal{D}$ and $\eta\leq\eta_{0}$ and for all
$t\in[0,1]$ we have

$\tilde{\phi}_{1}=\phi_{1}=\sup_{q\in[0,1]}\Big{\\{}f^{\textup{{sc}}}(\delta;2d\eta
q)-\frac{d}{2}\eta{q}^{2}\Big{\\}}.$

Hence the one-block free energy has a limit

$\underset{L^{\circlearrowleft}\to\infty}{\lim}f_{B}=\phi_{1}.$

###  8.6 Limit of $f_{B\cup B^{\prime}}$

We proceed similarly to the case of the one-block free energy. In this case we
have $4d+1$ free parameters. Recall the definition of the core $B^{\bullet}$
of a block $B$: $B^{\bullet}=B\setminus\underset{B^{\prime\prime}\sim
B}{\cup}B^{\prime\prime}$, and
${B^{\prime}}^{\bullet}=B^{\prime}\setminus\underset{B^{\prime\prime}\sim
B^{\prime}}{\cup}B^{\prime\prime}$. We summarize the correspondence between
overlaps and free parameters in the following table:

$\displaystyle R_{1,2}\big{(}B^{\bullet}\big{)}~{}$
$\displaystyle\longleftrightarrow~{}q^{\bullet}_{B}$ $\displaystyle
R_{1,2}\big{(}{B^{\prime}}^{\bullet}\big{)}~{}$
$\displaystyle\longleftrightarrow~{}q^{\bullet}_{B^{\prime}}$ $\displaystyle
R_{1,2}(B\cap B^{\prime\prime})~{}$
$\displaystyle\longleftrightarrow~{}q_{B\cap
B^{\prime\prime}},~{}~{}~{}\forall~{}B^{\prime\prime}\sim B,$ $\displaystyle
R_{1,2}(B^{\prime}\cap B^{\prime\prime})~{}$
$\displaystyle\longleftrightarrow~{}q_{B^{\prime}\cap
B^{\prime\prime}},~{}~{}~{}\forall~{}B^{\prime\prime}\sim B^{\prime}.$

We obtain the remaining relevant overlaps as

$\displaystyle R_{1,2}(B)~{}$
$\displaystyle\longleftrightarrow~{}q_{B}:=(1-2d\alpha)q^{\bullet}_{B}+\sum_{B^{\prime\prime}\sim
B}\alpha q_{B\cap B^{\prime\prime}},$ $\displaystyle R_{1,2}(B^{\prime})~{}$
$\displaystyle\longleftrightarrow~{}q_{B^{\prime}}:=(1-2d\alpha)q^{\bullet}_{B^{\prime}}+\sum_{B^{\prime\prime}\sim
B^{\prime}}\alpha q_{B^{\prime}\cap B^{\prime\prime}},$ $\displaystyle
R_{1,2}(B\setminus B^{\prime\prime})~{}$
$\displaystyle\longleftrightarrow~{}q_{B\setminus
B^{\prime\prime}}:=\frac{1-2d\alpha}{1-\alpha}q^{\bullet}_{B}+\frac{\alpha}{1-\alpha}\sum_{B^{\prime\prime\prime}\sim
B}q_{B\cap B^{\prime\prime\prime}},~{}~{}\forall B^{\prime\prime}\sim B,$
$\displaystyle R_{1,2}(B^{\prime}\setminus B^{\prime\prime})~{}$
$\displaystyle\longleftrightarrow~{}q_{B^{\prime}\setminus
B^{\prime\prime}}:=\frac{1-2d\alpha}{1-\alpha}q^{\bullet}_{B^{\prime}}+\sum_{B^{\prime\prime\prime}\sim
B^{\prime}}\frac{\alpha}{1-\alpha}q_{B^{\prime}\cap
B^{\prime\prime\prime}},~{}~{}\forall B^{\prime\prime}\sim B^{\prime}.$

We execute the same interpolation as in the previous section:

$\displaystyle H^{\eta}_{B^{\prime\prime}}(\theta_{B})~{}$
$\displaystyle\longleftrightarrow~{}h^{\textup{{sc}}}(\theta_{B};t\eta
q_{B})+h^{\textup{{sc}}}(\theta_{B\cap B^{\prime\prime}};(1-t)\eta q_{B\cap
B^{\prime\prime}})\qquad\forall~{}B^{\prime\prime}\sim B$ $\displaystyle\hskip
28.45274pt+h^{\textup{{sc}}}(\theta_{B\setminus B^{\prime\prime}};(1-t)\eta
q_{B\setminus B^{\prime\prime}}),$ $\displaystyle
H^{\eta}_{B^{\prime\prime}}(\theta_{B^{\prime}})~{}$
$\displaystyle\longleftrightarrow~{}h^{\textup{{sc}}}(\theta_{B^{\prime}};t\eta
q_{B^{\prime}})+h^{\textup{{sc}}}(\theta_{B^{\prime}\cap
B^{\prime\prime}};(1-t)\eta q_{B^{\prime}\cap
B^{\prime\prime}})\qquad\forall~{}B^{\prime\prime}\sim B^{\prime}$
$\displaystyle\hskip 28.45274pt+h^{\textup{{sc}}}(\theta_{B^{\prime}\setminus
B^{\prime\prime}};(1-t)\eta q_{B^{\prime}\setminus B^{\prime\prime}}).$

We proceed exactly as for the computation of $f_{B}$, and obtain upper and
lower bounds on limiting free energy:

$\liminf_{L^{\circlearrowleft}\to\infty}f_{B\cup
B^{\prime}}\geq\phi_{2},~{}~{}~{}\mbox{and}~{}~{}~{}\limsup_{L^{\circlearrowleft}\to\infty}f_{B\cup
B^{\prime}}\leq\tilde{\phi}_{2},$

with

$\displaystyle\phi_{2}:=\sup_{\underline{q}\in[0,1]^{4d+1}}\Big{\\{}$
$\displaystyle(1-2d\alpha)f^{\textup{{sc}}}(\delta;r^{\bullet}_{B})+(1-2d\alpha)f^{\textup{{sc}}}(\delta;r^{\bullet}_{B^{\prime}})+\alpha
f^{\textup{{sc}}}(\delta;r_{B\cap B^{\prime}})$ (8.20)
$\displaystyle+\sum_{\underset{B^{\prime\prime}\neq
B^{\prime}}{B^{\prime\prime}\sim B}}\alpha f^{\textup{{sc}}}(\delta;r_{B\cap
B^{\prime\prime}})+\sum_{\underset{B^{\prime\prime}\neq
B}{B^{\prime\prime}\sim B^{\prime}}}\alpha
f^{\textup{{sc}}}(\delta;r_{B^{\prime}\cap B^{\prime\prime}})$
$\displaystyle-\frac{1}{4}\sum_{B^{\prime\prime}\sim B}\Big{(}t\eta
q_{B}^{2}+\alpha(1-t)\eta q_{B\cap B^{\prime\prime}}^{2}+(1-\alpha)(1-t)\eta
q_{B\setminus B^{\prime\prime}}^{2}\Big{)}$
$\displaystyle-\frac{1}{4}\sum_{B^{\prime\prime}\sim B^{\prime}}\Big{(}t\eta
q_{B^{\prime}}^{2}+\alpha(1-t)\eta q_{B^{\prime}\cap
B^{\prime\prime}}^{2}+(1-\alpha)(1-t)\eta q_{B^{\prime}\setminus
B^{\prime\prime}}^{2}\Big{)}\Big{\\}}.$

and

$\displaystyle\tilde{\phi}_{2}:=\inf_{\underline{m}\in[-1,1]^{4d+1}}\sup_{\underline{q}\in[0,1]^{4d+1}}\Big{\\{}$
$\displaystyle(1-2d\alpha)\widetilde{f^{\textup{{sc}}}}(\delta;s^{\bullet}_{B},r^{\bullet}_{B})+(1-2d\alpha)\widetilde{f^{\textup{{sc}}}}(\delta;s^{\bullet}_{B^{\prime}},r^{\bullet}_{B^{\prime}})+\alpha\widetilde{f^{\textup{{sc}}}}(\delta;s_{B\cap
B^{\prime}},r_{B\cap B^{\prime}})$
$\displaystyle+\sum_{\underset{B^{\prime\prime}\neq
B^{\prime}}{B^{\prime\prime}\sim
B}}\alpha\widetilde{f^{\textup{{sc}}}}(\delta;s_{B\cap
B^{\prime\prime}},r_{B\cap
B^{\prime\prime}})+\sum_{\underset{B^{\prime\prime}\neq
B}{B^{\prime\prime}\sim
B^{\prime}}}\alpha\widetilde{f^{\textup{{sc}}}}(\delta;s_{B^{\prime}\cap
B^{\prime\prime}},r_{B^{\prime}\cap B^{\prime\prime}})$
$\displaystyle-\frac{1}{2}\sum_{B^{\prime\prime}\sim B}\Big{(}t\eta
m_{B}^{2}+\alpha(1-t)\eta m_{B\cap B^{\prime\prime}}^{2}+(1-\alpha)(1-t)\eta
m_{B\setminus B^{\prime\prime}}^{2}\Big{)}$
$\displaystyle-\frac{1}{2}\sum_{B^{\prime\prime}\sim B^{\prime}}\Big{(}t\eta
m_{B^{\prime}}^{2}+\alpha(1-t)\eta m_{B^{\prime}\cap
B^{\prime\prime}}^{2}+(1-\alpha)(1-t)\eta m_{B^{\prime}\setminus
B^{\prime\prime}}^{2}\Big{)}$
$\displaystyle+\frac{1}{4}\sum_{B^{\prime\prime}\sim B}\Big{(}t\eta
q_{B}^{2}+\alpha(1-t)\eta q_{B\cap B^{\prime\prime}}^{2}+(1-\alpha)(1-t)\eta
q_{B\setminus B^{\prime\prime}}^{2}\Big{)}$
$\displaystyle+\frac{1}{4}\sum_{B^{\prime\prime}\sim B^{\prime}}\Big{(}t\eta
q_{B^{\prime}}^{2}+\alpha(1-t)\eta q_{B^{\prime}\cap
B^{\prime\prime}}^{2}+(1-\alpha)(1-t)\eta q_{B^{\prime}\setminus
B^{\prime\prime}}^{2}\Big{)}\Big{\\}}.$ (8.21)

With ‘$r$’ parameters

$\displaystyle r^{\bullet}_{B}$ $\displaystyle=\sum_{B^{\prime\prime}\sim
B}(t\eta q_{B}+(1-t)\eta q_{B\setminus B^{\prime\prime}}),$ $\displaystyle
r^{\bullet}_{B^{\prime}}$ $\displaystyle=\sum_{B^{\prime\prime}\sim
B^{\prime}}(t\eta q_{B^{\prime}}+(1-t)\eta q_{B^{\prime}\setminus
B^{\prime\prime}}),$ $\displaystyle r_{B\cap B^{\prime}}$ $\displaystyle=t\eta
q_{B}+2(1-t)\eta q_{B\cap B^{\prime}}+t\eta q_{B^{\prime}}$
$\displaystyle~{}~{}~{}+\sum_{\underset{B^{\prime\prime}\neq
B^{\prime}}{B^{\prime\prime}\sim B}}(t\eta q_{B}+(1-t)\eta q_{B\setminus
B^{\prime\prime}})+\sum_{\underset{B^{\prime\prime}\neq
B}{B^{\prime\prime}\sim B^{\prime}}}(t\eta q_{B^{\prime}}+(1-t)\eta
q_{B^{\prime}\setminus B^{\prime\prime}}),$ $\displaystyle r_{B\cap
B^{\prime\prime}}$ $\displaystyle=t\eta q_{B}+(1-t)\eta q_{B\cap
B^{\prime\prime}}+\sum_{\underset{B^{\prime\prime\prime}\neq
B^{\prime\prime}}{B^{\prime\prime\prime}\sim B}}(t\eta q_{B}+(1-t)\eta
q_{B\setminus B^{\prime\prime\prime}}),~{}~{}~{}\forall B^{\prime\prime}\neq
B^{\prime},$ $\displaystyle r_{B^{\prime}\cap B^{\prime\prime}}$
$\displaystyle=t\eta q_{B^{\prime}}+(1-t)\eta q_{B^{\prime}\cap
B^{\prime\prime}}+\sum_{\underset{B^{\prime\prime\prime}\neq
B^{\prime\prime}}{B^{\prime\prime\prime}\sim B^{\prime}}}(t\eta
q_{B^{\prime}}+(1-t)\eta q_{B^{\prime}\setminus
B^{\prime\prime\prime}}),~{}~{}~{}\forall B^{\prime\prime}\neq B,$

and ‘$s$’ parameters defined similarly where the ‘$q$’ variables are replaced
by ‘$m$’ variables. Now we can reduce the number of parameters in the above
variational problems in the same way as for $f_{B}$ under Assumption 1:

######  Corollary 8.6.

Under Assumption 1, there exists $\eta_{0}>0$ such that for
$\eta\in\mathbb{R}_{+}\setminus\mathcal{D}$ and $\eta\leq\eta_{0}$ and for all
$t\in[0,1]$ we have

$\tilde{\phi}_{2}=\phi_{2}=\sup_{q\in[0,1]}\Big{\\{}2(1-\alpha)f^{\textup{{sc}}}(\delta;2d\eta
q)+\alpha f^{\textup{{sc}}}(\delta;4d\eta q)-d\eta q^{2}\Big{\\}}.$

Hence the two-block free energy has a limit

$\underset{L^{\circlearrowleft}\to\infty}{\lim}f_{B\cup B^{\prime}}=\phi_{2}.$

This concludes the proof of Proposition 6.5.

#### Acknowledgements.

The author is highly indebted to Andrea Montanari for numerous and invaluable
discussions of the main ideas underlying this work.

## References

  * [ABA20] Emmanuel Abbe and Enric Boix-Adserà, _An information-percolation bound for spin synchronization on general graphs_ , Annals of Applied Probability 30 (2020), no. 3, 1066–1090.
  * [Abb17] Emmanuel Abbe, _Community detection and stochastic block models: recent developments_ , The Journal of Machine Learning Research 18 (2017), no. 1, 6446–6531.
  * [ABRS18] Emmanuel Abbe, Enric Boix, Peter Ralli, and Colin Sandon, _Graph powering and spectral robustness_ , arXiv:1809.04818 (2018).
  * [AK18] Ahmed El Alaoui and Florent Krzakala, _Estimation in the spiked wigner model: A short proof of the replica formula_ , 2018 IEEE International Symposium on Information Theory (ISIT), IEEE, 2018, pp. 1874–1878.
  * [AM19] Ahmed El Alaoui and Andrea Montanari, _On the computational tractability of statistical estimation on amenable graphs_ , arXiv preprint arXiv:1904.03313 (2019).
  * [AMM+18] Emmanuel Abbe, Laurent Massoulie, Andrea Montanari, Allan Sly, and Nikhil Srivastava, _Group synchronization on grids_ , Mathematical Statistics and Learning 1 (2018), no. 3, 227–256.
  * [BBS17] Afonso S Bandeira, Nicolas Boumal, and Amit Singer, _Tightness of the maximum likelihood semidefinite relaxation for angular synchronization_ , Mathematical Programming 163 (2017), no. 1-2, 145–167.
  * [BLM13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, _Concentration inequalities: A nonasymptotic theory of independence_ , Oxford university press, 2013.
  * [Bou16] Nicolas Boumal, _Nonconvex phase synchronization_ , SIAM Journal on Optimization 26 (2016), no. 4, 2355–2377.
  * [BSS13] Afonso S Bandeira, Amit Singer, and Daniel A Spielman, _A cheeger inequality for the graph connection laplacian_ , SIAM Journal on Matrix Analysis and Applications 34 (2013), no. 4, 1611–1630.
  * [CC18] Yuxin Chen and Emmanuel J Candès, _The projected power method: An efficient algorithm for joint alignment from pairwise differences_ , Communications on Pure and Applied Mathematics 71 (2018), no. 8, 1648–1714.
  * [EKPS00] William Evans, Claire Kenyon, Yuval Peres, and Leonard J Schulman, _Broadcasting on trees and the ising model_ , The Annals of Applied Probability 10 (2000), no. 2, 410–433.
  * [FV17] Sacha Friedli and Yvan Velenik, _Statistical mechanics of lattice systems: a concrete mathematical introduction_ , Cambridge University Press, 2017.
  * [GRSY15] Amir Globerson, Tim Roughgarden, David Sontag, and Cafer Yildirim, _How hard is inference for structured prediction?_ , International Conference on Machine Learning, 2015, pp. 2181–2190.
  * [GT02] Francesco Guerra and Fabio Lucio Toninelli, _The thermodynamic limit in mean field spin glass models_ , Communications in Mathematical Physics 230 (2002), no. 1, 71–79.
  * [HCMC10] Stephen D Howard, Douglas Cochran, William Moran, and Frederick R Cohen, _Estimation and registration on graphs_ , arXiv preprint arXiv:1010.2983 (2010).
  * [KN11] Brian Karrer and Mark EJ Newman, _Stochastic blockmodels and community structure in networks_ , Physical review E 83 (2011), no. 1, 016107.
  * [LKZ15] Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová, _Phase transitions in sparse pca_ , 2015 IEEE International Symposium on Information Theory (ISIT), IEEE, 2015, pp. 1635–1639.
  * [LM17] Marc Lelarge and Léo Miolane, _Fundamental limits of symmetric low-rank matrix estimation_ , Probability Theory and Related Fields (2017), 1–71.
  * [MNN03] Jean-Marie Maillard, Koji Nemoto, and Hidetoshi Nishimori, _Symmetry, complexity and multicritical point of the two-dimensional spin glass_ , Journal of Physics A: Mathematical and General 36 (2003), no. 38, 9799\.
  * [Mon08] Andrea Montanari, _Estimating random variables from random sparse observations_ , Eur. Trans. on Telecom. 19 (2008), 385–403.
  * [Nis01] Hidetoshi Nishimori, _Statistical Physics of Spin Glasses and Information Processing: An Introduction_ , Oxford University Press, 2001.
  * [Ohz09] Masayuki Ohzeki, _Locations of multicritical points for spin glasses on regular lattices_ , Physical Review E 79 (2009), no. 2, 021129.
  * [Pan13] Dmitry Panchenko, _The Sherrington-Kirkpatrick model_ , Springer Science & Business Media, 2013.
  * [Pan15] , _The free energy in a multi-species sherrington–kirkpatrick model_ , Annals of Probability 43 (2015), no. 6, 3494–3513.
  * [PW20] Yury Polyanskiy and Yihong Wu, _Application of the information-percolation method to reconstruction problems on graphs_ , Mathematical Statistics and Learning 2 (2020), no. 1, 1–24.
  * [SB18] Abishek Sankararaman and François Baccelli, _Community detection on euclidean random graphs_ , Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 2181–2200.
  * [Sin11] Amit Singer, _Angular synchronization by eigenvectors and semidefinite programming_ , Applied and computational harmonic analysis 30 (2011), no. 1, 20–36.
  * [SS11] Amit Singer and Yoel Shkolnisky, _Three-dimensional structure determination from common lines in cryo-em by eigenvectors and semidefinite programming_ , SIAM journal on imaging sciences 4 (2011), no. 2, 543–572.
  * [SW12] Amit Singer and H-T Wu, _Vector diffusion maps and the connection laplacian_ , Communications on pure and applied mathematics 65 (2012), no. 8, 1067–1144.
  * [TPV09] Francesco Parisen Toldin, Andrea Pelissetto, and Ettore Vicari, _Strong-disorder paramagnetic-ferromagnetic fixed point in the square-lattice $\pm$j ising model_, Journal of Statistical Physics 135 (2009), no. 5-6, 1039–1061.