# Efficient $\mathbb{Z}_{2}$ synchronization on $\mathbb{Z}^{d}$ under
symmetry-preserving side information

Ahmed El Alaoui Department of Statistics and Data Science, Cornell university.

###### Abstract

We consider $\mathbb{Z}_{2}$-synchronization on the Euclidean lattice. Every
vertex of $\mathbb{Z}^{d}$ is assigned an independent symmetric random sign
$\theta_{u}$, and for every edge $(u,v)$ of the lattice, one observes the
product $\theta_{u}\theta_{v}$ flipped independently with probability $p$. The
task is to reconstruct products $\theta_{u}\theta_{v}$ for pairs of vertices
$u$ and $v$ which are arbitrarily far apart. Abbé, Massoulié, Montanari, Sly
and Srivastava (2018) showed that synchronization is possible if and only if
$p$ is below a critical threshold $\tilde{p}_{c}(d)$, and efficiently so for
$p$ small enough. We augment this synchronization setting with a model of side
information preserving the sign symmetry of $\theta$, and propose an
_efficient_ algorithm which synchronizes a randomly chosen pair of far away
vertices on average, up to a differently defined critical threshold
$p_{c}(d)$. We conjecture that $p_{c}(d)=\tilde{p}_{c}(d)$ for all $d\geq 2$.
Our strategy is to _renormalize_ the synchronization model in order to reduce
the effective noise parameter, and then apply a variant of the multiscale
algorithm of AMMSS. The success of the renormalization procedure is
conditional on a plausible but unproved assumption about the regularity of the
free energy of an Ising spin glass model on $\mathbb{Z}^{d}$.

##  1 Introduction and main results

In this paper we study a _group synchronization_ problem. Formulated
generally, this is the task of estimating a sequence of group–valued random
variables up to a global shift from noisy measurements of their differences.
This problem arises in several applications such as community detection, where
individuals belong to well-defined communities and observations come in the
form of pairwise affinities between individuals [KN11], time synchronization
in sensor networks where the goal is to adjust the local clock of each sensor
given noisy clock differences [HCMC10], computer vision and microscopy, where
the task is to estimate the shape of a moving object from multiple noisy
snapshots of it [SS11].

This problem has mostly been studied in settings where the set of compared
pairs forms a “unstructured” graph such as the complete graph or a random
graph from the Erdös-Rényi model. The analysis and the algorithms proposed in
such cases rely on the high degree of exchangeability of the variables
involved in the problem. A prime example being $\mathbb{Z}_{2}$
synchronization on the complete graph, where the observations can be put
together in a matrix having the form of a rank-one-perturbed Wigner matrix; a
well studied object for which powerful tools from random matrix theory and
mean-field methods originating in statistical physics are readily available.
These methods will typically fail on more structured graphs having geometric
features such as finite-dimensional lattices. Furthermore, studying signal
recovery problems on structured graphs can potentially be relevant to
applications such as the ones mentioned above where, due to resource
constraints or simply the problem’s nature, only a limited number of
comparisons can be measured.

To our knowledge, Abbé, Massoulié, Montanari, Sly and Srivastava [AMM+18] were
the first to consider the synchronization problem on the Euclidean lattice
$\mathbb{Z}^{d}$ for compact groups. They proved for $d\geq 3$ that
synchronization is possible with an efficient algorithm if the noise is weak
enough and impossible in the opposite regime where the noise is strong. (They
also treat the case $d=2$ in their paper, however this case is special, as the
structure of the group plays an important role in the results.) By
monotonicity with respect to the value of the noise, this establishes the
existence of a critical value where recovery is possible below it and
impossible above. We call this threshold the _information-theoretic_
threshold, or limit, of synchronization. In this paper we ask the question

> Is group synchronization on $\mathbb{Z}^{d}$ possible with an _efficient_
> algorithm up the information-theoretic limit?

We answer this question in the affirmative in the case of the simplest non
trivial group $\mathbb{Z}_{2}=\\{-1,+1\\}$, for all dimensions $d\geq 2$,
assuming one has access to a vanishing amount of ‘side information’ providing
extra help in the synchronization task. We should mention that contrary to
‘mean-field models’ as discussed above, no ‘explicit’ characterization of this
information-theoretic threshold is known on $\mathbb{Z}^{d}$. Therefore
whatever strategy aiming to answer the above question has to be content with
the implicit definition of the threshold, as we do in this paper, and build an
algorithm based on it.

We now set up the mathematical problem. Let
$\theta=(\theta_{u})_{u\in\mathbb{Z}^{d}}$ be i.i.d. symmetric $\pm 1$ random
variables assigned to the vertices of $\mathbb{Z}^{d}$. The edges of the
lattice
$\mathbb{E}^{d}=\\{(u,v)\in\mathbb{Z}^{d}\times\mathbb{Z}^{d}:|u-v|=1\\}$
($|\cdot|$ is the $\ell_{2}$ distance in $\mathbb{R}^{d}$) are assigned random
variables

$\displaystyle Y^{\delta}_{uv}=\begin{cases}+\theta_{u}\theta_{v}&\mbox{with
probability }1-p,\\\ -\theta_{u}\theta_{v}&\mbox{with probability
}p,\end{cases}$ (1.1)

independently for every $(u,v)\in\mathbb{E}^{d}$ conditional on $\theta$,
where $p\in(0,\frac{1}{2})$ is a fixed parameter. We let $\delta=1-2p$ so that
$\operatorname{\mathbb{E}}[Y_{uv}^{\delta}|\theta_{u},\theta_{v}]=\operatorname{\mathbb{E}}[Y_{uv}^{\delta}|\theta_{u}\theta_{v}]=\delta\theta_{u}\theta_{v}$.

Let $\Lambda_{n}=[-n,n]^{d}\cap\mathbb{Z}^{d}$ be a finite box of side length
$2n+1$ and let $E_{n}=\mathbb{E}^{d}\cap\Lambda_{n}^{2}$ be its set of edges.
We will informally denote the graph $(\Lambda_{n},E_{n})$ by its vertex set
$\Lambda_{n}$. Let us also denote the set of observations in the box
$\Lambda_{n}$ by
$Y_{\Lambda_{n}}^{\delta}=\\{Y_{uv}^{\delta}\,:\,u,v\in\Lambda_{n}\\}$.

Due to sign symmetry, it is not possible to distinguish $\theta$ from
$-\theta$ from the knowledge of the edge observations
$Y_{\Lambda_{n}}^{\delta}$. The _synchronization problem_ is as follows: given
$Y_{\Lambda_{n}}^{\delta}$ and possibly a small amount of side information as
clarified below, we want to produce estimates $T_{uv}$ that approximate the
product $\theta_{u}\theta_{v}$ with non-trivial error for ‘most’ pairs of
vertices $u,v\in\Lambda_{n}$.

We assume that side information comes in the form of pairwise measurements
according to the _‘spiked GOE’_ model111The terminology is meant to evoke the
random matrix model $\theta\theta^{\top}+W$ where $W$ is from the Gaussian
Orthogonal Ensemble, although due to the finite interaction range $L$, this
analogy is only superficial. with signal-to-noise ratio (SNR) $\eta$ and
interaction range $L$:

$Y^{\eta,L}_{uv}=\sqrt{\frac{\eta}{L^{d}}}\theta_{u}\theta_{v}+Z_{uv},\qquad\forall
u,v\in\Lambda_{n}~{}\mbox{s.t.}~{}|u-v|_{\infty}\leq L,$ (1.2)

where $Z_{uv}\sim N(0,1)$ are independent for all unordered pairs $(u,v)$,
$|\cdot|_{\infty}$ denotes the $\ell_{\infty}$ distance in $\mathbb{R}^{d}$.
The range of the interaction $L$ is a large but fixed constant independent of
$n$, and $\eta$ is an arbitrarily small constant.

We denote by
$Y_{\Lambda_{n}}^{\delta,\eta,L}=\\{Y_{\Lambda_{n}}^{\delta},Y_{\Lambda_{n}}^{\eta,L}\\}$
the union of the measurements (1.1) and (1.2). We are interested in maximizing
the criterion

$\mathcal{R}_{\Lambda_{n}}(T):=\frac{1}{|\Lambda_{n}|^{2}}\sum_{u,v\in\Lambda_{n}}\operatorname{\mathbb{E}}\Big{[}T_{uv}(Y_{\Lambda_{n}}^{\delta,\eta,L})\theta_{u}\theta_{v}\Big{]},$
(1.3)

which measures the average correlation between the estimate $T_{uv}$ and
$\theta_{u}\theta_{v}$, among all estimators $T=(T_{uv})_{u,v\in\Lambda_{n}}$
where
$T_{uv}:\\{-1,+1\\}^{E_{n}}\times\mathbb{R}^{\Lambda_{n}^{2}}\to\\{-1,+1\\}$
are measurable functions.

The presence of side information (1.2) is a technical device enabling the
analysis of the posterior distribution of
$\theta_{\Lambda_{n}}=(\theta_{u})_{u\in\Lambda_{n}}$. Our results will be
stated in the regime $L\to\infty$ and $\eta\to 0$ (after $n\to\infty$). The
use of this device is well established in information theory, spin glass
theory, and models of high-dimensional statistical inference [Mon08, Pan13,
LM17], although a different model of side information, or perturbation, is
typically used in the literature. The specific form of the side information
(1.2) does not break the sign symmetry of $\theta_{\Lambda_{n}}$ and as we
explain in Section 2 the problem of synchronization is still non trivial.

Before considering the algorithmic question, we first define the information-
theoretic limits of synchronization. For the purpose of establishing some key
definitions, we consider the situation where side information of the form
(1.2) is available for every pair $u,v\in\Lambda_{n}$; this is equivalent to
$L=L_{n}=2n+1$. We now define the average pair correlations

$\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,\eta,L_{n}}\big{]}^{2}\Big{]}.$
(1.4)

Note that $\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny
e}}=\mathcal{R}_{\Lambda_{n}}(T^{\mbox{\rm\tiny Bayes}})$ where
$T^{\mbox{\rm\tiny
Bayes}}_{uv}=\operatorname{\mathbb{E}}\big{[}\theta_{u}\theta_{v}|Y_{\Lambda_{n}}^{\delta,\eta,L_{n}}\big{]}$
is the Bayes-optimal estimator.

######  Proposition 1.1.

The sequence $(\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny e}})_{n\geq 1}$ has a
limit $q_{\star}^{2}(\delta,\eta)$ for all $\delta\in[0,1]$ and all except
countably many $\eta\geq 0$. Moreover, the maps $\delta\mapsto
q_{\star}(\delta,\eta)$ and $\eta\mapsto q_{\star}(\delta,\eta)$ are non-
decreasing.

The proof of Proposition 1.1 can be found in Section 6.2. Let us denote by
$\mathcal{D}_{\delta}$ the countable set of $\eta$ (for a given $\delta$)
where $(\varphi_{\Lambda_{n}}^{\mbox{\rm\tiny e}})_{n}$ fails to converge, as
per Proposition 1.1. Then the following limit exists for all $\delta\in[0,1]$
and is non-decreasing in $\delta$:

$q_{\star\star}(\delta):=\lim_{\underset{\eta\notin\mathcal{D}_{\delta}}{\eta\to
0^{+}}}q_{\star}(\delta,\eta).$ (1.5)

We now define _the synchronization threshold_

$\delta_{c}=\inf\\{\delta>0~{}:~{}q_{\star\star}(\delta)>0\\}.$ (1.6)

The next two results show that synchronization is efficiently possible above
$\delta_{c}$ and impossible below (efficiently or otherwise). The
synchronization result is conditional on an unproved but highly plausible
assumption which we state in Section 6, Assumption 1.

######  Theorem 1.2.

Conditional on Assumption 1, for all $d\geq 2$ and all $\delta>\delta_{c}$
there exists $\eta_{0}=\eta_{0}(d,\delta)>0$ such that for almost all
$\eta\leq\eta_{0}$, there exists $L_{0}=L_{0}(\delta,d,\eta)\geq 1$ and
$n_{0}=n_{0}(\delta,d,\eta)$ such that the following holds. For all $n$ there
exists a randomized estimator $T^{(n)}=(T^{(n)}_{uv})_{u,v\in\Lambda_{n}}$
where
$T^{(n)}_{uv}=T^{(n)}_{uv}(Y_{\Lambda_{n}}^{\delta,\eta,L})\in\\{-1,+1\\}$
with runtime $\mathcal{O}(n^{2d})$ such that for all $n\geq n_{0}$ and all
$L\geq L_{0}$,

$\mathcal{R}_{\Lambda_{n}}\big{(}T^{(n)}\big{)}\geq\frac{9}{10}q_{\star\star}^{2}(\delta).$

The above result establishes the existence of an algorithm whose running time
is quadratic in the size of the problem and which succeeds at synchronizing a
randomly chosen pair of variables on average, immediately above the
synchronization threshold $\delta_{c}$, when given an arbitrarily small amount
of side information as per Eq. (1.2). (Note that the interaction range $L$ in
the side information does not depend on $n$.) Moreover the synchronization
accuracy is near optimal (the constant $\frac{9}{10}$ is arbitrary and can be
replaced by any other constant $c_{0}<1$.) We next answer the natural question
of whether synchronization is possible below $\delta_{c}$. We show that this
is not the case in the following sense.

######  Theorem 1.3.

Let $\delta<\delta_{c}$ and $L=L_{n}\geq 1$ be any sequence of integers
depending on $n$. There exists a set $\mathcal{A}\subset\mathbb{R}_{+}$ of
full Lebesgue measure such that the following holds. For any sequence of
estimators $T^{(n)}=(T^{(n)}_{uv})_{u,v\in\Lambda_{n}}$ where
$T^{(n)}_{uv}=T^{(n)}_{uv}(Y_{\Lambda_{n}}^{\delta,\eta,L_{n}})\in\\{-1,+1\\}$,
we have

$\lim_{\underset{\eta\in\mathcal{A}}{\eta\to
0^{+}}}\liminf_{n\to\infty}\big{|}\mathcal{R}_{\Lambda_{n}}\big{(}T^{(n)}\big{)}\big{|}=0.$

Theorem 1.2 is proved in Section 4.2, and Theorem 1.3 is proved in Section
7.4.

##  2 Discussion and related work

As mentioned earlier, there is a wealth of results for reconstruction problems
on the complete graph, sparse and dense regular and Erdös-Rényi random graphs
and trees. See for instance [Sin11, SW12, Bou16, BSS13, BBS17, CC18, Abb17]
and references therein for work using various methods for group
synchronization and its applications. However, the study of reconstruction on
structured graph models with a lesser degree of exchangeability is fairly
limited. A few pointers to the latter category are [GRSY15, AMM+18, SB18,
ABRS18, ABA20, PW20]. The former class of models, in addition to being
analytically tractable, is also known to exhibit an information-computation
gap where in a certain regime of parameters, reconstruction (in our case,
synchronization) is information-theoretically possible but all known efficient
(polynomial-time) algorithms fail at it.

Local algorithm with BEC. In contrast, Montanari and the author showed in
[AM19] that on amenable graphs, and under a stronger model of side information
where one receives the value of $\theta_{u}$ with small probability
independently for each vertex $u$—this is called the binary erasure channel
(BEC)—optimal reconstruction is possible in a certain asymptotic sense by
means of an efficient local algorithm. Therefore, reconstruction on amenable
graphs with BEC side information does not exhibit a statistical-computational
gap. The local algorithm uses the side information from the BEC in a crucial
way to induce, asymptotically, a decoupling among the variables $\theta_{u}$.
Amenability then implies that observations beyond a receding boundary around a
given vertex $u$ carries vanishing information about its spin $\theta_{u}$.
Therefore, under BEC, it is possible to estimate each $\theta_{u}$ by only
using information in a ball of bounded radius around $u$. (Synchronization is
then trivial as one can return an estimate for $\theta_{u}\theta_{v}$ by
multiplying the estimates corresponding to $\theta_{u}$ and $\theta_{v}$
respectively.) The present model of side information (1.2) is weaker than BEC.
In particular the sign symmetry of the variables $\theta_{u}$ is not broken
given the observations $Y^{\delta,\eta,L}_{\Lambda_{n}}$, so one cannot
estimate individual spins better than random and the strategy employed in
[AM19] fails. One can instead focus on the task of synchronizing two faraway
vertices.

Synchronization via a multiscale algorithm. Our algorithm is based on a
multiscale procedure similar to the one used in [AMM+18]. Our main innovation
concerns the base layer of the multiscale hierarchy: we partition the lattice
into overlapping patches of constant size (see Figure 1) and construct a
_renormalized_ instance of the synchronization problem where patches play the
role of vertices, i.e., we assign a global spin to each patch and construct a
new synchronization variables between every two neighboring patches. We
exploit properties of the posterior measure of $\theta$ when augmented with
the side information to show that the effective noise parameter for the
renormalized instance can be made as small as one desires by making the
patches large enough. We then adapt the multiscale algorithm of [AMM+18] and
apply it to this renormalized instance, therefore synchronizing any two
vertices by traveling the path connecting them in tree encoding the multiscale
hierarchy. The analysis of this second stage also requires significant effort
as the renormalized instance is a more complicated graphical model than the
original synchronization instance.

The synchronization threshold. The authors of [AMM+18] consider a definition
of synchronization slightly different from ours. The latter is considered
possible if one can synchronize an _arbitrary_ pair of far away vertices, and
the synchronization threshold is defined as

$\tilde{\delta}_{c}:=\inf\Big{\\{}\delta>0~{}:~{}\liminf_{|u-v|\to\infty}\,\sup_{T_{uv}}\,d_{\mbox{\rm\tiny
TV}}\Big{(}\text{Law}\big{(}T_{uv}(Y^{\delta}_{\mathbb{Z}^{d}})\theta_{u}\theta_{v}\big{)},\bar{\nu}\Big{)}>0\Big{\\}},$

where
$Y^{\delta}_{\mathbb{Z}^{d}}=\\{Y^{\delta}_{uv}:(u,v)\in\mathbb{E}^{d}\\}$,
$T_{uv}:\\{-1,+1\\}^{\mathbb{E}^{d}}\to\\{-1,+1\\}$ measurable, $\bar{\nu}$ is
the uniform distribution over $\\{-1,+1\\}$, and $d_{\mbox{\rm\tiny TV}}$ is
the total variation distance. This definition relies only on the lattice
observations $Y^{\delta}_{uv},(u,v)\in\operatorname{\mathbb{E}}^{d}$ and not
on any side information. We find it more convenient to work with our
definition of $\delta_{c}$, Eq. (1.6), which is more suitable to algorithmic
reasoning. Nevertheless, in light of Theorem 1.2 and Theorem 1.3 we find it
plausible to conjecture that the equality $\tilde{\delta}_{c}=\delta_{c}$
holds for all $d\geq 2$.

The Ising spin glass. In the absence of measurements on the edges of
$\mathbb{Z}^{d}$, i.e., $\delta=0$, the quantity $q_{\star}(0,\eta)$ in
Proposition 1.1 has a well understood, rather explicit expression [LKZ15,
LM17]. In particular it is known that $q_{\star}(0,\eta)=0$ for all $\eta\leq
1$ (therefore $q_{\star\star}(0)=0$) and $q_{\star}(0,\eta)>0$ for $\eta>1$.
When $\delta>0$, little is known about $q_{\star}(\delta,\eta)$. For instance,
the pure lattice case $\eta=0$ is of interest to statistical physics, since
the posterior measure of $\theta$ is equivalent to the Ising spin glass
measure on $\mathbb{Z}^{d}$, on the so-called Nishimori line: A simple
application of the Bayes rule reveals

$\operatorname{\mathbb{P}}(\theta|Y^{\delta}_{\Lambda_{n}})\propto
e^{\beta\sum_{(u,v)\in
E_{n}}Y^{\delta}_{uv}\theta_{u}\theta_{v}},~{}~{}~{}\beta=\frac{1}{2}\log\big{(}\frac{1-p}{p}\big{)}.$

Let us write $Y^{\delta}_{uv}=Z_{uv}\theta_{0u}\theta_{0v}$ where
$\operatorname{\mathbb{P}}(Z_{uv}=+1)=1-p=1-\operatorname{\mathbb{P}}(Z_{uv}=-1)$
as per Eq. (1.1) (the added subscript in $\theta_{0}$ is to distinguish it
from a generic vector $\theta$ in the above formula). Let us also define
$\sigma_{u}=\theta_{u}\theta_{0u}$ for all $u\in\Lambda_{n}$. Then the push-
forward of $\operatorname{\mathbb{P}}(\cdot|Y^{\delta}_{\Lambda_{n}})$ by
$\theta\to\sigma$ is of the form

$\mu_{\Lambda_{n}}(\sigma)\propto e^{\beta\sum_{(u,v)\in
E_{n}}Z_{uv}\sigma_{u}\sigma_{v}}.$

The relation $\beta=\frac{1}{2}\log\big{(}\frac{1-p}{p}\big{)}$ between the
inverse temperature and the bias of the disorder variables $Z_{uv}$ defines a
curve in the plane $(p,\beta)$ called the Nishimori line; see also [Nis01,
Chapter 4]. Furthermore, $\delta_{c}=1-2p_{c}$ as defined in (1.6) corresponds
to _the tri-critical point_ $(p_{c},\beta_{c})$ conjecturally separating three
distinct phases of the model. A few predictions are available for its location
in $d=2$: Nonrigorous analytical considerations based on the replica method
and special symmetries of the model have lead the authors of [MNN03] to put
forward the conjecture that $p_{c}$ solves the equation $-p\log
p-(1-p)\log(1-p)=\frac{\log 2}{2}$ with $p<\frac{1}{2}$, which leads to
$p_{c}\simeq 0.110028$, i.e., $\delta_{c}^{2}\simeq 0.608312$. However Ohzeki
[Ohz09] suggests that this is only an approximation which can be further
improved via a renormalization group analysis, and they advance the value
$p_{c}\simeq 0.109168$ ($\delta_{c}^{2}\simeq 0.610939$). On the other hand,
Monte-Carlo simulations for $d=2$ made by Toldin, Pelissetto and Vicari
[TPV09] seem to agree with the theoretical predictions to a good extent and
indicate that $p_{c}\simeq 0.10917$ ($\delta_{c}^{2}\simeq 0.61099$.)

On the rigorous mathematical side, explicit bounds on $\tilde{\delta}_{c}$ are
known in the recent literature: It was shown in [AMM+18] that
$p_{\mbox{\rm\tiny perc}}(d)\leq\tilde{\delta}_{c}<1$, where
$p_{\mbox{\rm\tiny perc}}(d)$ be the critical threshold of Bernoulli bond
percolation on $\mathbb{Z}^{d}$. Abbé and Boix [ABA20], and Polyanskiy and Wu
[PW20] independently introduced a more refined _information–percolation_
argument implying that synchronization is impossible if $\delta^{2}\leq
p_{\mbox{\rm\tiny perc}}(d)$, i.e., $\tilde{\delta}_{c}^{2}\geq
p_{\mbox{\rm\tiny perc}}(d)$. The iquadratic mprovement comes from a
comparison with a more accurate, potentially inhomogeneous, percolation model
where an edge $(u,v)\in\operatorname{\mathbb{E}}^{d}$ is open with probability
$I_{2}(Y^{\delta}_{uv};\theta_{u},\theta_{v})$, $I_{2}$ being the mutual
information in $\chi^{2}$ divergence. In the two-dimensional case $d=2$, this
latter bound reads $\tilde{\delta}_{c}^{2}\geq\frac{1}{2}$, to be compared
with the above-mentioned predictions.

At the opposite end of the spectrum, one would expect mean-field behavior when
$d$ is large, and the critical point of the model should approach its analogue
on the infinite regular tree of the same degree, which this given by the
Kesten-Stigum threshold for reconstruction on the $2d$-regular tree with
binary alphabet [EKPS00]. This leads to a natural conjecture:
$\tilde{\delta}_{c}^{2}\sim 1/(2d)$ as $d\to\infty$.

#### Organization.

We present the renormalization procedure, which is the first step of the
multiscale algorithm in Section 3. Section 4 is devoted to statements of the
key theorems enabling the analysis. The rest of multiscale construction is
presented and analyzed in Section 5. Sections 6, 7 and 8 are devoted to the
technical results and proofs underlying the key theorems of Section 4.

#### Notation.

We will frequently take limits of numerical quantities which are only defined
almost everywhere or everywhere except on a countable number of points with
respect to a real-valued parameter, see e.g., the definition of
$q_{\star\star}$, Eq. (1.5). It will be implicitly understood and with no
further precision that the limits are taken along sequences avoiding the
exceptional problematic set. We use the asymptotic notation
$\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{\scalebox{0.7}{$\scriptscriptstyle\mathcal{O}$}}_{L,\eta}(1)$
for a quantity tending to zero when $L\to\infty$ followed by $\eta\to 0$ (in
this order).

Figure 1: Left: A block bound by black solid lines. The dashed inner
boundaries define the surrounding square joints. Right: The core of a block,
i.e., a block deprived of its joints.

##  3 The synchronization algorithm

In this section we describe the synchronization algorithm which underlies
Theorem 1.2.

#### 1\. Partitioning.

We first cover the lattice $\Lambda_{n}$ with pairwise interlocking blocks: We
consider a tiling of $\mathbb{R}^{d}$ with translates of the cube
$C=[-\frac{1}{2},\frac{1}{2}]^{d}$ along the coordinate directions. We put
translates of the cube $\frac{1}{3}C$ at the midpoint of every edge of the
integer lattice: these are all sets $\frac{1}{3}C+(k+\frac{1}{2})e_{i}$ where
$k\in\mathbb{Z}$ and $(e_{1},\cdots,e_{d})$ is the standard unit basis of
$\mathbb{R}^{d}$. We call these translates _joints_. Note that each joint
overlaps with two adjacent elements of the tiling. We define a _block_ to be
the union of an element of the tiling with its $2d$ surrounding joints; see
Figure 1 (left). Hence two adjacent blocks have a non empty intersection which
is precisely the joint between them; see Figure 2. We also define the _core_
of a block $A$ as $A^{\bullet}=A\setminus\cup J$ where the union is over all
joints surrounding $A$; see Figure 1 (right). Now we dilate all distances by a
factor $L^{\circlearrowleft}$ and then intersect the dilated sets with
$\mathbb{Z}^{d}$:

$\mathbb{B}=\Big{\\{}(L^{\circlearrowleft}\cdot
A)\cap\mathbb{Z}^{d}~{}:~{}A\mbox{ is a
block}\Big{\\}},\quad\mathbb{J}=\Big{\\{}(L^{\circlearrowleft}\cdot
J)\cap\mathbb{Z}^{d}~{}:~{}J\mbox{ is a joint}\Big{\\}}.$

The parameter $L^{\circlearrowleft}\geq 1$ is an integer representing the
scale of the renormalization. We retain the terminology of blocks, joints and
cores for the elements of $\mathbb{B}$, the elements of $\mathbb{J}$ and
blocks deprived of their surrounding joints, respectively. We define the
_intersection graph_ $\mathbb{L}=(\mathbb{B},\mathbb{J})$ to have blocks as
its vertices and joints as its edges; $\mathbb{L}$ is clearly isomorphic to
the integer lattice. We write $B\sim B^{\prime}$ for adjacency in
$\mathbb{L}$. Finally, we let
$\mathbb{B}_{n}=\\{B\in\mathbb{B}:B\cap\Lambda_{n}\neq\emptyset\\}$. For
convenience we ignore the blocks $B$ that fall on the boundary of
$\Lambda_{n}$, as their contribution to $\mathcal{R}_{\Lambda_{n}}$, Eq.
(1.3), is negligible.

We set the range of the GOE interaction (1.2) to be $L=2L^{\circlearrowleft}$.
This insures that an observation $Y^{\eta,L}_{xy}$ is available for every two
vertices $x,y\in B$ for every block $B\in\mathbb{B}_{n}$.

Figure 2: Interlocking blocks in $d=2$. Cores are in white and bound by solid
lines. Joints are in gray.

#### 2\. Processing side information.

Without loss of generality we can assume we have access to an arbitrary finite
number of independent copies of the GOE side information
$Y_{\Lambda_{n}}^{\eta,L}$, Eq.(1.2) with arbitrary SNR $\eta$. Indeed, given
observations of the form (1.2) we can artificially create two independent
copies with any SNR smaller than $\eta$ by adding and subtracting an
independent normal r.v. with appropriate variance to/from $Y^{\eta,L}_{xy}$
for each pair $x,y$. Recursing this operation $\ell$ times, we get $2^{\ell}$
copies of (1.2) with any desired SNR (smaller than $\eta$).

Now we associate to the blocks $B\in\mathbb{B}_{n}$ independent (conditionally
on $\theta$) sets of side information produced as follows. Let $t\in[0,1]$ be
chosen, for instance, uniformly at random. This parameter is shared across all
blocks $B\in\mathbb{B}_{n}$. Now we fix a block $B$ and do the following: For
every $B^{\prime}=B+L^{\circlearrowleft}a$ where $a\in\\{\pm e_{1},\cdots,\pm
e_{d}\\}$ (so that $B^{\prime}\sim B$), let

$\displaystyle Y^{\eta,(a,\bullet)}_{uv}$
$\displaystyle=\sqrt{\frac{t\eta}{|B|}}\theta_{u}\theta_{v}+Z^{(a,\bullet)}_{uv}~{}\mbox{for
all}~{}x,y\in B,$ $\displaystyle Y^{\eta,(a,\cap)}_{uv}$
$\displaystyle=\sqrt{\frac{(1-t)\eta}{|B\cap
B^{\prime}|}}\theta_{u}\theta_{v}+Z^{(a,\cap)}_{uv}~{}\mbox{for all}~{}x,y\in
B\cap B^{\prime},$ $\displaystyle Y^{\eta,(a,\setminus)}_{uv}$
$\displaystyle=\sqrt{\frac{(1-t)\eta}{|B\setminus
B^{\prime}|}}\theta_{u}\theta_{v}+Z^{(a,\setminus)}_{uv}~{}\mbox{for
all}~{}x,y\in B\setminus B^{\prime},$

where $\big{\\{}(Z^{(a,\bullet)}_{uv})_{u,v\in B},(Z^{(a,\cap)}_{uv})_{u,v\in
B\cap B^{\prime}},(Z^{(a,\setminus)}_{uv})_{u,v\in B\setminus
B^{\prime}}\big{\\}}$ are all mutually independent standard normal random
variables which are also independent from everything else. Importantly, these
noise r.v.’s are independent from those used in the construction of side
information on a different block. The fact that these observations are
available is due the relation $L=2L^{\circlearrowleft}$. We concatenate this
side information in a convenient notation:

$\displaystyle Y^{\eta}_{B}$
$\displaystyle:=\bigcup_{\underset{B^{\prime}=B+L^{\circlearrowleft}a}{a\in\\{\pm
e_{1},\cdots,\pm e_{d}\\}}}\Big{(}\\{Y^{\eta,(a,\bullet)}_{xy}:(x,y)\in
B^{2}\\}\cup\\{Y^{\eta,(a,\cap)}_{xy}:(x,y)\in(B\cap B^{\prime})^{2}\\}$ (3.1)
$\displaystyle\hskip
113.81102pt\cup\\{Y^{\eta,(a,\setminus)}_{xy}:(x,y)\in(B\setminus
B^{\prime})^{2}\\}\Big{)}.$

With this notation let us reiterate that $Y^{\eta}_{B}$ and
$Y^{\eta}_{B^{\prime}}$ are independent conditionally on $\theta$ for $B\neq
B^{\prime}$. This construction is designed to ‘lock’ certain overlaps
pertaining to the core and the joints of the block $B$ together. This locking
property will be explained in greater detail in Section 4.1.

#### 3\. Sampling.

For each block $B\in\mathbb{B}_{n}$, we independently generate a sample
$\big{(}\theta^{B}_{x}\big{)}_{x\in B}$ from the posterior distribution of
$(\theta_{x})_{x\in B}$ given the lattice observations
$Y^{\delta}_{B}=\\{Y^{\delta}_{uv}:u,v\in B,|u-v|=1\\}$ and the side
information $Y^{\eta}_{B}$ as defined above:

$\big{(}\theta^{B}_{x}\big{)}_{x\in
B}\sim\operatorname{\mathbb{P}}\big{(}\cdot|Y^{\delta}_{B},Y^{\eta}_{B}\big{)}.$
(3.2)

#### 4\. New synchronization variables.

For every two adjacent blocks $B\sim B^{\prime}\in\mathbb{B}_{n}$, we
construct a new synchronization variable $\widetilde{Y}_{B,B^{\prime}}$ by
taking the sign of the inner product of $(\theta^{B}_{x})_{x\in B\cap
B^{\prime}}$ and $(\theta^{B^{\prime}}_{x})_{x\in B\cap B^{\prime}}$:

$\widetilde{Y}_{B,B^{\prime}}=\operatorname{sign}\Big{(}\sum_{x\in B\cap
B^{\prime}}\theta^{B}_{x}\theta^{B^{\prime}}_{x}\Big{)}.$ (3.3)

#### 5\. Multiscale scheme.

We apply the multiscale scheme presented in Section 5 on the new observations
$(\widetilde{Y}_{B,B^{\prime}})_{B\sim B^{\prime}}$ to synchronize the blocks
and produce estimates $\hat{\sigma}_{B}$ for every block $B\in\mathbb{B}_{n}$.

#### 6\. Final estimates.

We output final estimates for every vertex $x$ in the original lattice
$\Lambda_{n}$: $\hat{\theta}_{x}=\hat{\sigma}_{B}\theta^{B}_{x}$ where
$B\in\mathbb{B}_{n}$ is such that $x\in B$. (If $x$ belongs to the
intersection of two adjacent blocks then we choose one of the blocks
containing it arbitrarily.) We then let
$T_{xy}=\hat{\theta}_{x}\hat{\theta}_{y}$ for all pairs $x,y\in\Lambda_{n}$.

##  4 Renormalization

The above algorithm builds a bigger lattice consisting of blocks and
constructs new pairwise measurements between blocks (Step 4). We explain here
the purpose of this operation. Let us assign a spin
$\tilde{\theta}_{B}\in\\{\pm 1\\}$ to every block $B\in\mathbb{B}_{n}$ based
on the inner product of $(\theta^{B}_{x})_{x\in B}$ as constructed in Step 3,
and the hidden assignment $\theta$:

$\tilde{\theta}_{B}=\operatorname{sign}\Big{(}\sum_{x\in
B}\theta^{B}_{x}\theta_{x}\Big{)}.$ (4.1)

These variables are of course hidden from the observer as they depend on
$\theta$. This provides us with a new synchronization instance
$\\{(\tilde{\theta}_{B})_{B\in\mathbb{B}_{n}},(\widetilde{Y}_{B,B^{\prime}})_{B\sim
B^{\prime}}\\}$ on the rescaled lattice $\mathbb{L}$. So we mapped the
original synchronization instance
$\\{(\theta_{u})_{u\in\Lambda_{n}},(Y_{uv}^{\delta})_{(u,v)\in E_{n}}\\}$ on
$(\Lambda_{n},E_{n})$ to a new, _renormalized_ synchronization instance
$\\{(\tilde{\theta}_{B})_{B\in\mathbb{B}_{n}},(\widetilde{Y}_{B,B^{\prime}})_{B\sim
B^{\prime}}\\}$ on $\mathbb{L}$ where the role of vertices is now played by
blocks222Observe however that this new synchronization instance is a more
complicated graphical model since it does not have the same conditional
independence structure as the model as defined by (1.1). The observations
$\widetilde{Y}_{B,B^{\prime}}$ are meant to be noisy versions of the products
$\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}$, the same way $Y_{uv}$ is a
noisy version of the product $\theta_{u}\theta_{v}$. Moreover, the outputs
$(\hat{\sigma}_{B})_{B\in\mathbb{B}_{n}}$ produced in Step 5 of the algorithm
are meant to be such that $\hat{\sigma}_{B}\hat{\sigma}_{B^{\prime}}$ is a
good estimate of $\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}$ for all pairs
$B,B^{\prime}$.

The main point of this mapping is to increase the signal strength: whereas
$\operatorname{\mathbb{P}}(Y^{\delta}_{uv}=-\theta_{u}\theta_{v})=p$ is a
constant of the problem, we will show that the _effective noise parameter_ of
the renormalized model

$p^{\circlearrowleft}:=\operatorname{\mathbb{P}}\left(\widetilde{Y}_{B,B^{\prime}}=-\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}\right),$
(4.2)

tends to zero as the renormalization rescale $L^{\circlearrowleft}$ becomes
large.

######  Theorem 4.1.

Under Assumption 1, for $\delta>\delta_{c}$ and almost every $t\in[0,1]$,

$\lim_{\eta\to
0^{+}}\lim_{L^{\circlearrowleft}\to\infty}p^{\circlearrowleft}=0.$

Therefore, for $L^{\circlearrowleft}$ large (and $\eta$ small), it is easier
to solve the synchronization problem on the rescaled lattice $\mathbb{L}$
since this problem is less noisy: we cary out in Section 5 a multiscale
analysis to synchronize the blocks $B\in\mathbb{B}_{n}$ given the new
synchronization variables $(\widetilde{Y}_{B,B^{\prime}})_{B\sim B^{\prime}}$,
Eq. (3.3) and show the following result.

######  Theorem 4.2.

Under Assumption 1, for $\delta>\delta_{c}$, there exists $\eta_{0}>0$ such
that for almost all $\eta\leq\eta_{0}$, there exists $L_{0}\geq 1$ such that
for all $L^{\circlearrowleft}\geq L_{0}$ and almost every $t\in[0,1]$, the
following holds. For every pair of blocks $B_{1},B_{2}\in\mathbb{B}_{n}$,
there exists an estimator
$\widetilde{T}_{B_{1},B_{2}}=\hat{\sigma}_{B_{1}}\hat{\sigma}_{B_{2}}\in\\{\pm
1\\}$ which takes as input the new observations
$(\widetilde{Y}_{B,B^{\prime}})_{B\sim B^{\prime}}$ and satisfies

$\operatorname{\mathbb{P}}\Big{(}\widetilde{T}_{B_{1},B_{2}}\neq\tilde{\theta}_{B_{1}}\tilde{\theta}_{B_{2}}\Big{)}\leq\frac{1}{21}.$

Moreover, the estimators
$(\widetilde{T}_{B_{1},B_{2}})_{B_{1},B_{2}\in\mathbb{B}_{n}}$ can be computed
in time $\mathcal{O}(n^{2d})$.

The proof of Theorem 4.2 relies on an adaptation of an approach already used
in [AMM+18], augmented with the result of Theorem 4.1. The latter theorem is a
consequence of a set of several asymptotic statements concerning intra- and
inter-block overlaps which we collect in the next theorem.

For $\big{(}\theta^{B}_{x}\big{)}_{x\in
B}\sim\operatorname{\mathbb{P}}\big{(}\cdot|Y^{\delta}_{B},Y^{\eta}_{B}\big{)}$
and $\big{(}\theta^{B^{\prime}}_{x}\big{)}_{x\in
B^{\prime}}\sim\operatorname{\mathbb{P}}\big{(}\cdot|Y^{\delta}_{B^{\prime}},Y^{\eta}_{B^{\prime}}\big{)}$,
we define the correlation between samples on adjacent blocks $B\sim
B^{\prime}$:

$W_{B,B^{\prime}}:=\frac{1}{|B\cap B^{\prime}|}\sum_{x\in B\cap
B^{\prime}}\theta^{B}_{x}\theta^{B^{\prime}}_{x},$ (4.3)

and between samples and the ground truth within a block $B\in\mathbb{B}_{n}$:

$M_{B}:=\frac{1}{|B|}\sum_{x\in
B}\theta^{B}_{x}\theta_{x},\quad\mbox{and}\quad
M_{B^{\bullet}}:=\frac{1}{|B^{\bullet}|}\sum_{x\in
B^{\bullet}}\theta^{B}_{x}\theta_{x},$ (4.4)

where $B^{\bullet}$ is the core of the block $B$.

######  Theorem 4.3.

Under Assumption 1, for all $\delta>\delta_{c}$ and almost every $t\in[0,1]$,
the following holds in the limit $L^{\circlearrowleft}\to\infty$ followed by
$\eta\to 0^{+}$:

  1. 1.

For every block $B\in\mathbb{B}_{n}$,

$\operatorname{\mathbb{E}}[M_{B}^{2}]\longrightarrow
q_{\star\star}^{2}(\delta),~{}~{}\operatorname{\mathbb{E}}\big{[}(M_{B}-M_{B^{\bullet}})^{2}\big{]}\longrightarrow
0,~{}~{}\mbox{and}~{}~{}\operatorname{var}(M_{B}^{2})\longrightarrow 0.$

  2. 2.

For every pair of adjacent blocks $B\sim B^{\prime}$,

$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{2}]\longrightarrow
q_{\star\star}^{2}(\delta),~{}~{}\mbox{and}~{}~{}\operatorname{var}(W_{B,B^{\prime}}^{2})\longrightarrow
0.$

  3. 3.

For every pair of adjacent blocks $B\sim B^{\prime}$,

$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]\longrightarrow
q_{\star\star}^{3}(\delta).$

###  4.1 An overview of the main ideas of the proof

The proof of Theorem 4.3 is where the side information (3.1) is crucially
used. We will give here a view of the main ideas. The full proof is presented
in Section 7. The statements of the theorem follow from the study of the
analytic properties (with respect to the parameters $t$ and $\eta$) of the
_free energies_ associated to a block $B$ and to the union of two adjacent
blocks $B\cup B^{\prime}$, in the limit where the volume of $B$ and
$B^{\prime}$ tends to infinity. These free energies are the (properly
normalized) expected logarithms of the partition functions of the posterior
measures of $(\theta_{u})_{u\in B}$ given $Y^{\delta,\eta}_{B}$, and
$(\theta_{u})_{u\in B\cup B^{\prime}}$ given $Y^{\delta,\eta}_{B\cup
B^{\prime}}$ respectively, see e.g., Eq. (4.5). We will show that these free
energies converge to certain variational formulas involving the limiting free
energy of the posterior measure of $\theta_{\Lambda_{n}}$ given the lattice
measurements $Y^{\delta}_{\Lambda_{n}}$ together with a side information where
one observes the spin $\theta_{u}$ of every vertex $u$ corrupted by an
_independent_ Gaussian noise $z_{u}$. These results are stated and discussed
in Section 6, and proved in Section 8. The convexity of the free energies with
respect to $\eta$ allows to deduce convergence and concentration of the
overlap $M_{B}$ in (4.4).

As for $M_{B^{\bullet}}$ and $W_{B,B^{\prime}}$, these overlaps involve only a
subset of the vertices of the block, so it is not immediately clear that they
should also converge. This is where we show a _overlap locking property_ by
varying the parameter $t$. For the sake of this discussion, suppose we have a
sequence of graphs $G_{n}=(V_{n},E_{n})$ of growing size, and let
$(A_{n},B_{n})$ be a partition of $V_{n}$ into two subsets such that
$|A_{n}|/|V_{n}|=\alpha_{n}\to\alpha$ and $|B_{n}|/|V_{n}|\to 1-\alpha$,
$\alpha\in(0,1)$. Each vertex $u$ is endowed with random variable $\theta_{u}$
drawn independently at random form a distribution $p_{0}$, and we receive an
observation $Y_{uv}\sim Q(\cdot|\theta_{u},\theta_{v})$ independently on every
edge $(u,v)\in E$, $Q$ being a probability kernel. Additionally, in the spirit
of the Guerra-Toninelli interpolation [GT02], we receive side information of
the form

$\displaystyle\tilde{Y}_{uv}$
$\displaystyle=\sqrt{\frac{t\lambda}{|V_{n}|}}\theta_{u}\theta_{v}+Z_{uv}~{}~{}~{}\mbox{for
all}~{}u,v\in V_{n},$ $\displaystyle\tilde{Y}_{uv}^{\prime}$
$\displaystyle=\sqrt{\frac{(1-t)\lambda}{|A_{n}|}}\theta_{u}\theta_{v}+Z_{uv}^{\prime}~{}~{}~{}\mbox{for
all}~{}u,v\in A_{n},$ $\displaystyle\tilde{Y}_{uv}^{\prime\prime}$
$\displaystyle=\sqrt{\frac{(1-t)\lambda}{|B_{n}|}}\theta_{u}\theta_{v}+Z_{uv}^{\prime\prime}~{}~{}~{}\mbox{for
all}~{}u,v\in B_{n},$

where $Z_{uv},Z_{uv}^{\prime},Z_{uv}^{\prime\prime}$ are mutually independent
standard normal random variables. We define the free energy
$\phi_{n}(\lambda,t)$ as the expected logarithm of the normalizing constant of
the posterior measure $\operatorname{\mathbb{P}}(\cdot|Y,\tilde{Y})$:

$\phi_{n}(\lambda,t)=\frac{1}{|V_{n}|}\operatorname{\mathbb{E}}\log\int\prod_{(u,v)\in
E_{n}}Q(Y_{uv}|\theta_{u},\theta_{v})\cdot e^{H_{n}(\theta)}\prod_{u\in
V_{n}}\mathrm{d}p_{0}(\theta_{u}),$ (4.5)

where $H_{n}=H_{V_{n}}+H_{A_{n}}+H_{B_{n}}$ and

$\displaystyle H_{V_{n}}(\theta)$ $\displaystyle=\sum_{u,v\in
V_{n}}\sqrt{\frac{t\lambda}{|V_{n}|}}\tilde{Y}_{uv}\theta_{u}\theta_{v}-\frac{t\lambda}{2|V_{n}|}\theta_{u}^{2}\theta_{v}^{2},$
$\displaystyle H_{A_{n}}(\theta)$ $\displaystyle=\sum_{u,v\in
A_{n}}\sqrt{\frac{(1-t)\lambda}{|A_{n}|}}\tilde{Y}_{uv}^{\prime}\theta_{u}\theta_{v}-\frac{(1-t)\lambda}{2|A_{n}|}\theta_{u}^{2}\theta_{v}^{2},$
$\displaystyle H_{B_{n}}(\theta)$ $\displaystyle=\sum_{u,v\in
B_{n}}\sqrt{\frac{(1-t)\lambda}{|B_{n}|}}\tilde{Y}_{uv}^{\prime\prime}\theta_{u}\theta_{v}-\frac{(1-t)\lambda}{2|B_{n}|}\theta_{u}^{2}\theta_{v}^{2}.$

Let us assume that $\phi_{n}(\lambda,t)$ converges pointwise to a limit
$\phi(\lambda,t)$ as $|V_{n}|\to\infty$. Since $\phi_{n}$ is convex with
respect to $t$, so is $\phi$, and we have
$\frac{\mathrm{d}}{\mathrm{d}t}\phi_{n}\to\frac{\mathrm{d}}{\mathrm{d}t}\phi$
for all $\lambda\geq 0$ and almost all $t\in[0,1]$. For a subset $S\subseteq
V_{n}$, we let $R_{1,2}(S)=\frac{1}{|S|}\sum_{u\in
S}\theta_{u}^{1}\theta_{u}^{2}$ where $\theta^{1},\theta^{2}$ are drawn
independently from $\operatorname{\mathbb{P}}(\cdot|Y,\tilde{Y})$. A
computation using Gaussian integration by parts yields

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\phi_{n}$
$\displaystyle=\frac{\lambda}{2|V_{n}|}\operatorname{\mathbb{E}}\Big{\langle}|V_{n}|R_{1,2}(V_{n})^{2}-|A_{n}|R_{1,2}(A_{n})^{2}-|B_{n}|R_{1,2}(B_{n})^{2}\Big{\rangle}$
$\displaystyle=-\frac{\lambda}{2}\alpha_{n}(1-\alpha_{n})\operatorname{\mathbb{E}}\Big{\langle}\Big{(}R_{1,2}(A_{n})-R_{1,2}(B_{n})\Big{)}^{2}\Big{\rangle}.$

The bracket angles $\langle\cdot\rangle$ denote the average with respect to
the posterior measure $\operatorname{\mathbb{P}}(\cdot|Y,\tilde{Y})$. Now if
we are able to show that the limit $\phi$ does not depend on $t$, then we
obtain $R_{1,2}(V_{n})\simeq R_{1,2}(A_{n})\simeq R_{1,2}(B_{n})$
“asymptotically almost surely” for almost all values of $t$. We say in this
case that $R_{1,2}(A_{n})$ and $R_{1,2}(B_{n})$ are _locked_ together. This is
essentially the strategy for treating $M_{B^{\bullet}}$ and
$W_{B,B^{\prime}}$: we show that they are locked to $M_{B}$ and $M_{B\cup
B^{\prime}}$ respectively. The unproven Assumption 1 is required in the
process of proving the convergence of $\phi_{n}\to\phi$, (and in particular
for showing that $\phi$ it does not depend on $t$; see Proposition 6.5 and
Section 8.3.

We observe that a similar property was discovered by Panchenko in the context
of spin glasses for the multi-species Sherrington-Kirkpatrick model [Pan15],
but the underlying mechanism is quite different, although it also relies on a
perturbation of the Hamiltonian. Panchenko names this property
_synchronization_ , but this word has a different meaning in our context.

Next, showing
$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]\longrightarrow
q_{\star\star}^{3}(\delta)$ requires one more ingredient, of an operator-
theoretic flavor. Let us first expand the expression at hand:

$\displaystyle\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]$
$\displaystyle=\frac{1}{|B\cap B^{\prime}||B||B^{\prime}|}\sum_{x\in B\cap
B^{\prime},y\in B,z\in
B^{\prime}}\operatorname{\mathbb{E}}\big{[}\theta_{x}^{B}\theta_{x}^{B^{\prime}}\theta_{y}^{B}\theta_{y}\theta_{z}^{B^{\prime}}\theta_{z}\big{]}$
$\displaystyle=\frac{1}{|B\cap B^{\prime}||B||B^{\prime}|}$
$\displaystyle\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}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{z}|Y_{B^{\prime}}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{y}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}\Big{]}.$

We use the locking property to show that the above expression can be
approximated by

$\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_{y}|Y_{B\cup
B^{\prime}}\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{]}\Big{]}.$

We observe that this is equal to
$\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{3})$, where $\chi$ is the
$|B\cup B^{\prime}|\times|B\cup B^{\prime}|$ matrix with entries

$\chi_{xy}=\frac{1}{|B\cup
B^{\prime}|}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}.$

On the other hand we know that, say, from Proposition 1.1, that the expected
trace of the square of $\chi$ converges to $q_{\star\star}^{2}(\delta)$:

$\operatorname{\mathbb{E}}\operatorname{trace}(\chi^{2})=\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_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}\longrightarrow q_{\star\star}^{2}(\delta).$

Therefore showing that the expected trace of the cube of $\chi$ converges to
$q_{\star\star}^{3}(\delta)$ amounts to showing that $\chi$ is approximately
rank one. Concretely we will how that
$\operatorname{\mathbb{E}}\|\chi\|_{\textup{op}}\to q_{\star\star}(\delta)$,
then use the sandwiching
$\|\chi\|_{\textup{op}}\leq\operatorname{trace}(\chi^{3})^{1/3}\leq\operatorname{trace}(\chi^{2})^{1/2}$
(valid since $\chi$ is a positive semidefinite matrix) together with a
concentration argument. Now it suffices to exhibit a vector
$v\in\mathbb{R}^{|B\cup B^{\prime}|}$ maximizing the quadratic form
$v^{\top}\chi\,v$. We let

$v_{x}=\frac{1}{\sqrt{|B\cup
B^{\prime}|}}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y_{B\cup
B^{\prime}},\tilde{y}\big{]},~{}~{}~{}~{}x\in B\cup B^{\prime},$

where $\tilde{y}\in\mathbb{R}^{|B\cup B^{\prime}|}$ is a random vector with
i.i.d. coordinates $\tilde{y}_{x}=\sqrt{\varepsilon}\theta_{x}+z_{x}$, where
$z_{x}\sim N(0,1)$. (Note that by symmetry, $v=0$ if $\varepsilon=0$,
therefore the necessity of introducing a small bias.) We will show that as
$\varepsilon\to 0$, we have $\operatorname{\mathbb{E}}|v|^{2}\to
q_{\star\star}(\delta)$, and
$\operatorname{\mathbb{E}}\big{[}v^{\top}\chi\,v\big{]}\to
q_{\star\star}^{2}(\delta)$, and then finish the proof by a concentration
argument. These concentrations statements are collectively called _decoupling
bounds_ and are presented in Section 6.4.

###  4.2 Proof of Theorem 4.1 and Theorem 1.2

We prove Theorem 4.1 as a consequence of Theorem 4.3:

###### Proof of Theorem 4.1.

For two adjacent block $B\sim B^{\prime}$, let
$\varepsilon_{B,B^{\prime}}=\operatorname{sign}(W_{B,B^{\prime}}M_{B}M_{B^{\prime}})$.
Then

$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]=\operatorname{\mathbb{E}}[\varepsilon_{B,B^{\prime}}|W_{B,B^{\prime}}||M_{B}||M_{B^{\prime}}|].$

Since for any non-negative random variable we have
$\operatorname{var}(X)^{2}\leq\frac{1}{2}\operatorname{var}(X^{2})$, the
variance statements in items 1 and 2 of Theorem 4.3 imply that
$|W_{B,B^{\prime}}|$, $|M_{B}|$ and $|M_{B^{\prime}}|$ have vanishing
variances. Combined with convergence of the expectations, this implies that
$\operatorname{\mathbb{E}}[|M_{B}|]$,
$\operatorname{\mathbb{E}}[|M_{B^{\prime}}|]$ and
$\operatorname{\mathbb{E}}[|W_{B,B^{\prime}}|]$ converge to
$q_{\star\star}(\delta)$. Therefore

$\operatorname{\mathbb{E}}[\varepsilon_{B,B^{\prime}}|W_{B,B^{\prime}}||M_{B}||M_{B^{\prime}}|]=\operatorname{\mathbb{E}}[\varepsilon_{B,B^{\prime}}]q_{\star\star}^{3}(\delta)+o_{L^{\circlearrowleft},\eta}(1),$

where $o_{L^{\circlearrowleft},\eta}(1)\to 0$ for a.e. $t\in[0,1]$ as
$L^{\circlearrowleft}\to\infty$ then $\eta\to 0$. Given item 3, this implies
that when $\delta>\delta_{c}$, $q_{\star\star}(\delta)>0$ and

$1-2p^{\circlearrowleft}=\operatorname{\mathbb{E}}[\varepsilon_{B,B^{\prime}}]\longrightarrow
1.$

$\blacksquare$

Next, we use Theorem 4.2 to prove our main reconstruction result: Theorem 1.2.

###### Proof of Theorem 1.2.

Recall that our final estimate of $\theta_{u}\theta_{v}$ is
$T_{uv}=\widetilde{T}_{B_{u},B_{v}}\theta^{B_{u}}_{u}\theta^{B_{v}}_{v}$,
where $B_{u}$ and $B_{v}$ are blocks to which vertices $u$ and $v$
respectively belong (if a vertex happens to belong to a joint then its parent
block is chosen arbitrarily) and $\theta^{B_{u}}_{u}$ is given in (3.2). We
compute the performance of this estimator. Since the graph $\mathbb{L}$ is
bipartite, $\Lambda_{n}$ can be partitioned into an alternating succession of
blocks and cores of blocks: start with the block at the origin then take the
cores of all the $3^{d}-1$ blocks surrounding it, and recurse. This forms a
disjoint union. We color white (w) the blocks $B\in\mathbb{B}_{n}$ appearing
in full in this decomposition and gray (g) those whose cores appear instead.
Below, we use the notation $B\texttt{w}$ or $B\texttt{g}$ to indicate the
color of the block $B$. We write

$\mathcal{R}_{\Lambda_{n}}(T)=\frac{1}{|\Lambda_{n}|^{2}}\sum_{u,v\in\Lambda_{n}}\operatorname{\mathbb{E}}\Big{[}T_{uv}\theta_{u}\theta_{v}\Big{]}=\texttt{ww}+2\texttt{wg}+\texttt{gg},$

where

$\displaystyle\texttt{ww}=\sum_{B\texttt{w},B^{\prime}\texttt{w}\in\mathbb{B}_{n}}$
$\displaystyle\sum_{u\in B,v\in
B^{\prime}}A_{uv}^{BB^{\prime}},~{}~{}~{}\texttt{wg}=\sum_{B\texttt{w},B^{\prime}\texttt{g}\in\mathbb{B}_{n}}\sum_{u\in
B,v\in B^{\prime\bullet}}A_{uv}^{BB^{\prime}},$ gg
$\displaystyle=\sum_{B\texttt{g},B^{\prime}\texttt{g}\in\mathbb{B}_{n}}\sum_{u\in
B^{\bullet},v\in B^{\prime\bullet}}A_{uv}^{BB^{\prime}},$

and

$A_{uv}^{BB^{\prime}}=\frac{1}{|\Lambda_{n}|^{2}}\operatorname{\mathbb{E}}\Big{[}\widetilde{T}_{B,B^{\prime}}\theta^{B}_{u}\theta^{B^{\prime}}_{v}\theta_{u}\theta_{v}\Big{]}.$

We analyze each one the three expressions separately. For the last two
expressions, we have

$\displaystyle\sum_{u\in B,v\in B^{\prime\bullet}}A_{uv}^{BB^{\prime}}$
$\displaystyle=\frac{|B|\cdot|B^{\prime\bullet}|}{|\Lambda_{n}|^{2}}\operatorname{\mathbb{E}}\Big{[}\widetilde{T}_{B,B^{\prime}}M_{B}M_{B^{\prime\bullet}}\Big{]}=\frac{|B|\cdot|B^{\prime\bullet}|}{|\Lambda_{n}|^{2}}\Big{(}\operatorname{\mathbb{E}}\Big{[}\big{(}\widetilde{T}_{B,B^{\prime}}M_{B}M_{B^{\prime}}\Big{]}+\mbox{error}\Big{)},$
$\displaystyle\sum_{u\in B^{\bullet},v\in
B^{\prime\bullet}}A_{uv}^{BB^{\prime}}$
$\displaystyle=\frac{|B^{\bullet}|\cdot|B^{\prime\bullet}|}{|\Lambda_{n}|^{2}}\operatorname{\mathbb{E}}\Big{[}\widetilde{T}_{B,B^{\prime}}M_{B^{\bullet}}M_{B^{\prime\bullet}}\Big{]}=\frac{|B^{\bullet}|\cdot|B^{\prime\bullet}|}{|\Lambda_{n}|^{2}}\Big{(}\operatorname{\mathbb{E}}\Big{[}\widetilde{T}_{B,B^{\prime}}M_{B}M_{B^{\prime}}\Big{]}+\mbox{error}\Big{)},$

where $|\mbox{error}|\leq
2\operatorname{\mathbb{E}}\big{[}|M_{B^{\prime}}-M_{B^{\prime\bullet}}|\big{]}$.
Moreover,

$\displaystyle\sum_{u\in B,v\in B^{\prime}}A_{uv}^{BB^{\prime}}$
$\displaystyle=\frac{|B|\cdot|B^{\prime}|}{|\Lambda_{n}|^{2}}\operatorname{\mathbb{E}}\Big{[}\widetilde{T}_{B,B^{\prime}}M_{B}M_{B^{\prime}}\Big{]},$
$\displaystyle=\frac{|B|^{2}}{|\Lambda_{n}|^{2}}\operatorname{\mathbb{E}}\Big{[}\big{(}\widetilde{T}_{B,B^{\prime}}\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}\big{)}|M_{B}||M_{B^{\prime}}|\Big{]}.$

Now we apply item 1 of Theorem 4.3:
$\operatorname{var}(|M_{B}|)=o_{L^{\circlearrowleft},\eta}(1)$,
$\operatorname{\mathbb{E}}[|M_{B}|]=q_{\star\star}+o_{L^{\circlearrowleft},\eta}(1)$
and $\mbox{error}=o_{L^{\circlearrowleft},\eta}(1)$, and Theorem 4.2:
$\operatorname{\mathbb{E}}\big{[}\widetilde{T}_{B,B^{\prime}}\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}\big{]}\geq\frac{19}{21}$.
Here, $o_{L^{\circlearrowleft},\eta}(1)\to 0$ as
$L^{\circlearrowleft}\to\infty$ then $\eta\to 0$. Whence

ww
$\displaystyle\geq\frac{1}{|\Lambda_{n}|^{2}}\sum_{B\texttt{w},B^{\prime}\texttt{w}\in\mathbb{B}_{n}}|B|\cdot|B^{\prime}|\Big{(}\frac{19}{21}q_{\star\star}^{2}(\delta)+o_{L^{\circlearrowleft},\eta}(1)\Big{)},$
wg
$\displaystyle\geq\frac{1}{|\Lambda_{n}|^{2}}\sum_{B\texttt{w},B^{\prime}\texttt{g}\in\mathbb{B}_{n}}|B|\cdot|B^{\prime\bullet}|\Big{(}\frac{19}{21}q_{\star\star}^{2}(\delta)+o_{L^{\circlearrowleft},\eta}(1)\Big{)},$
gg
$\displaystyle\geq\frac{1}{|\Lambda_{n}|^{2}}\sum_{B\texttt{g},B^{\prime}\texttt{g}\in\mathbb{B}_{n}}|B^{\bullet}|\cdot|B^{\prime\bullet}|\Big{(}\frac{19}{21}q_{\star\star}^{2}(\delta)+o_{L^{\circlearrowleft},\eta}(1)\Big{)}.$

Consequently,
$\mathcal{R}_{\Lambda_{n}}(T)\geq\frac{19}{21}q_{\star\star}^{2}(\delta)+o_{L^{\circlearrowleft},\eta}(1)$,
Now we let $\eta$ be sufficiently small and $L^{\circlearrowleft}$ be
sufficiently large (possibly depending on $\eta$) such that the above is, say,
larger than $\frac{9}{10}q_{\star\star}^{2}(\delta)$. Finally, the full
running time of this algorithm is $\mathcal{O}(n^{2d})$ since the construction
of the estimators $\widetilde{T}_{B,B^{\prime}}$ and the sampling operation
(step 3) both take constant time in $n$. $\blacksquare$

##  5 The multiscale scheme

We now present the multiscale algorithm and prove Theorem 4.2.

###  5.1 The algorithm

#### 1\. Hierarchical partioning.

We construct a hierarchy of partitions $(\mathcal{B}^{(k)})_{k\geq 0}$ of the
rescaled lattice $\mathbb{L}$ which we define recursively. Let
$\mathcal{B}^{(0)}=\mathbb{B}$ and $\mathbb{L}^{(0)}=\mathbb{L}$. Let
$\mathbf{0}^{(0)}\in\mathbb{B}$ is the block centered at the origin. Given
$\mathbb{L}^{(k)}$ which we assume is isomorphic to
$(\mathbb{Z}^{d},\operatorname{\mathbb{E}}^{d})$ (this is already the case at
level $k=0$), we construct $\mathbb{L}^{(k+1)}$ satisfying the same property.
Let $d_{k}$ be the $\ell_{\infty}$ distance in $\mathbb{L}^{(k)}$, which is
well defined by isomorphism to
$(\mathbb{Z}^{d},\operatorname{\mathbb{E}}^{d})$. Now we fix a integer
constant $\kappa\geq 1$ and define the origin of $\mathcal{B}^{(k+1)}$ as

$\mathbf{0}^{(k+1)}=\Big{\\{}B\in\mathcal{B}^{(k)}:d_{k}\big{(}B^{(k)},\mathbf{0}^{(k)}\big{)}\leq\kappa(k+1)^{2}\Big{\\}},$

and let

$\mathcal{B}^{(k+1)}=\Big{\\{}\mathbf{0}^{(k+1)}+m\ell_{k}e_{i}~{}:~{}m\in\mathbb{Z},~{}i=1,\cdots,d\Big{\\}},$

where $e_{i}$ are the coordinate directions of unit length in
$\mathbb{L}^{(k)}$. Two elements $B_{1}$ and $B_{2}$ of $\mathcal{B}^{(k+1)}$
are adjacent, and we write $B_{1}\sim B_{2}$, if one is a translate of the
other by $\ell_{k}e_{i}$ for some $i$. This completely defines
$\mathbb{L}^{(k+1)}$. We refer to the elements of $\mathcal{B}^{(k)}$ as the
level-$k$ blocks. The original lattice $\mathbb{Z}^{d}$ can be thought of as
being at level $k=-1$. We also define $\ell_{k}=2\kappa(k+1)^{2}+1$ be the
side length of a block in $\mathcal{B}^{(k+1)}$. We require the following
three conditions on the sequence of scales:

$\begin{split}\mathbf{A1}:~{}~{}~{}\sup_{k\geq
0}\Big{\\{}k^{2d}\ell_{k}^{2d}&(2\kappa)^{-(d-1)(k+5)}\Big{\\}}\leq\frac{1}{2},\qquad\mathbf{A2}:~{}~{}~{}\sum_{k=0}^{\infty}\frac{1+3^{d-1}}{\ell_{k}^{d-1}}\leq\frac{1}{20},\\\
\mathbf{A3}:&~{}~{}~{}(1+3^{d})\sum_{k=0}^{\infty}k^{2d}(2\kappa)^{-(d-1)(k+6)}\leq\frac{1}{42}.\end{split}$
(5.1)

All three conditions can be satisfied simultaneously if $\kappa=\kappa_{0}(d)$
is a sufficiently large constant depending on $d$. Indeed, since
$\ell_{k}\sim(2\kappa)(k+1)^{2}$ for $k$ or $\kappa$ large, the supremum in
$\mathbf{A1}$ is finite and can be made arbitrarily small if $\kappa$ is large
enough. Next, the two series in $\mathbf{A2}$ and $\mathbf{A3}$ are convergent
for all $\kappa>\frac{1}{2}$ and all $d\geq 2$, and their values are
decreasing to zero as a function of $\kappa$. We fix $\kappa$ such that
$\mathbf{A1,A2,A3}$ are satisfied.

#### 2\. Block variables 1.

We assign recursively to every level-$k$ block $B\in\mathcal{B}^{(k)}$ a
random variable $W^{(k)}_{B}\in\\{-1,+1\\}$ which is measurable with respect
to the new synchronization variables $\\{\widetilde{Y}_{B_{1},B_{2}}:B_{1}\sim
B_{2}\in\mathbb{B}\\}$ defined in (3.3). Our estimates
$\widetilde{T}_{B_{1},B_{2}}$ for two level-0 blocks $B_{1},B_{2}$ are defined
as

$\widetilde{T}_{B_{1},B_{2}}=\prod_{k\geq
0}W^{(k)}_{B_{1,k}}W^{(k)}_{B_{2,k}},$ (5.2)

where $B_{1,k}$ is the unique level-$k$ block containing $B_{2}$, and
similarly for $B_{2,k}$. Note that the above product is finite and extends up
to the most recent ancestor of $B_{1}$ and $B_{2}$, that is the lowest level
block which contains both $B_{1}$ and $B_{2}$. It will be convenient to define
the product of the variables $W^{(k)}_{B}$ up to a given high in the
hierarchy: For a level-$0$ block $B$ we let

$\widetilde{W}^{(k)}_{B}=\prod_{j=0}^{k}W^{(j)}_{B_{j}},$

were $B_{j}$ is the unique level-$j$ block containing $B$. (In this case
$\widetilde{T}_{B_{1},B_{2}}=\widetilde{W}^{(k)}_{B_{1}}\widetilde{W}^{(k)}_{B_{2}}$
where $k$ is the level of the lowest common ancestor of $B_{1}$ and $B_{2}$.)

#### 3\. Synchronization variables.

We recursively compute synchronization variables $Y^{(k)}_{B,B^{\prime}}$ for
every pair of adjacent level-$k$ blocks. For $k=0$ we let
$Y^{(0)}_{B,B^{\prime}}=\widetilde{Y}_{B,B^{\prime}}$. For general $k$ we
proceed as follows. For two adjacent level-$k$ blocks $B_{1},B_{2}$, we define
$\partial^{(0)}(B_{1},B_{2})$ to be the set of pairs of level-$0$ adjacent
blocks $B\sim B^{\prime}$ such that $B\in B_{1}$ and $B^{\prime}\in B_{2}$.
The set $\partial^{(0)}(B_{1})$ of level-$0$ blocks $B\in B_{1}$ which have an
adjacent block $B^{\prime}\in B_{2}$, seen as graph, is isomorphic to a box in
$\mathbb{Z}^{d-1}$, and is thus bipartite, therefore 2-colorable. Let
$\mathsf{col}:\partial^{(0)}(B_{1})\mapsto\\{0,1\\}$ be such a coloring (which
can be found in linear time in a recursive way). We now define the subset of
$\partial^{(0)}(B_{1},B_{2})$ consisting of those edges whose end in $B_{1}$
are colored $1$:

$\Xi(B_{1},B_{2})=\big{\\{}(B,B^{\prime})\in\partial^{(0)}(B_{1},B_{2})~{}:~{}\mathsf{col}(B)=1\big{\\}}.$
(5.3)

Importantly, two edges in $\Xi$ have their endpoints non-adjacent. This
property will be important in the analysis due to the fact that two non-
adjacent level-$0$ blocks do _not_ overlap. Finally, we define

$Y^{(k)}_{B_{1},B_{2}}=\operatorname{sign}\Big{(}\sum_{(B,B^{\prime})\in\Xi(B_{1},B_{2})}\widetilde{Y}_{B,B^{\prime}}\widetilde{W}^{(k-1)}_{B}\widetilde{W}^{(k-1)}_{B^{\prime}}\Big{)}.$
(5.4)

#### 4\. Block variables 2.

It remains to describe how $W^{(k)}_{B}$ is constructed from the knowledge of
the level-$k$ synchronization variables
$\big{\\{}Y^{(k)}_{B_{1},B_{2}}:B_{1}\sim B_{2}\in\mathcal{B}^{(k)}\big{\\}}$.
Let $B^{*}$ a level-$(k+1)$ block. We call a _quartet_ a collection of 4
level-$k$ blocks $B_{1}\sim B_{2}\sim B_{3}\sim B_{4}\sim B_{5}=B_{1}$ which
form a square inside $B^{*}$. We say that a quartet is _incoherent_ if
$\prod_{i=1}^{4}Y^{(k)}_{B_{i},B_{i+1}}=-1$, and coherent otherwise. Let
$\mathcal{I}_{B^{*}}$ be the largest connected component of level-$k$ sub-
blocks $B\in B^{*}$ which belong to no incoherent quartet. Now we assign,
whenever possible, a random variable $W^{(k)}_{B}$ to every $B\in B^{*}$ such
that

$Y^{(k)}_{B_{1},B_{2}}=W^{(k)}_{B_{1}}W^{(k)}_{B_{2}}~{}~{}\mbox{for
all}~{}~{}B_{1},B_{2}\in\mathcal{I}_{B^{*}}~{}\mbox{with}~{}B_{1}\sim B_{2}.$
(5.5)

If this is not possible then all blocks are assigned the value $+1$. Next, the
blocks which do not belong to $\mathcal{I}_{B^{*}}$ are all assigned the value
$+1$. This completes the description of the multiscale algorithm.

###  5.2 Proof of Theorem 4.2

We claim that for an appropriate choice of the renormalization length
$L^{\circlearrowleft}$, the construction satisfies the conclusion of Theorem
4.2. We follow the argument in [AMM+18] which used a similar construction
directly on the original lattice $\mathbb{Z}^{d}$ for $d=2$. There are two
novel aspects in our setting: the construction is generalized to all
dimensions, and the initial renormalization step, in particular the fact that
$p^{\circlearrowleft}\to 0$ as $L^{\circlearrowleft}\to\infty$ is used to
‘jump-start’ the argument.

Let $\delta^{\circlearrowleft}=1-2p^{\circlearrowleft}$. Let us call an edge
$B_{1}\sim B_{2}$ for two level-$k$ blocks $B_{1},B_{2}\in\mathcal{B}^{(k)}$
_honest_ if

$\sum_{(B,B^{\prime})\in\Xi(B_{1},B_{2})}\widetilde{Y}_{B,B^{\prime}}\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}\geq\frac{9}{10}\delta^{\circlearrowleft}\big{|}\Xi(B_{1},B_{2})\big{|}.$
(5.6)

Recall $\Xi(B_{1},B_{2})$ was defined in Eq. (5.3). Now we recursively define
the notion of a _good_ block. Level-$0$ blocks are good. A level-$k\geq 1$
block $B$ is good if two conditions are satisfied:

  * •

All adjacent level-$(k-1)$ sub-blocks of $B$ form honest edges.

  * •

$B$ contains at most one _bad_ (i.e., not good) level-$(k-1)$ sub-block.

######  Lemma 5.1.

There exists $p_{0}=p_{0}(d,\kappa)\in(0,\frac{1}{2})$ such that if
$p^{\circlearrowleft}\leq p_{0}$ then for all $k\geq 0$ and all
$B\in\mathcal{B}^{(k)}$,

$\operatorname{\mathbb{P}}(B~{}\mbox{is bad})\leq
k^{2d}(2\kappa)^{-(d-1)(k+6)}.$

###### Proof.

We proceed by induction. The base case $k=0$ being true, let us assume that
for some $k\geq 0$ each level-$k$ block is good with probability at least
$1-\epsilon_{k}$. Fix a level-$(k+1)$ block $B^{*}$, and two of its level-$k$
sub-blocks $B_{1},B_{2}$ which are adjacent. We evaluate the probability that
this edge is honest. We let
$Z_{B,B^{\prime}}=\widetilde{Y}_{B,B^{\prime}}\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}$
for two level-$0$ blocks $B$ and $B^{\prime}$. By construction,
$\Xi(B_{1},B_{2})$ contains edges which are far away by a distance of at least
two. If $(B,B^{\prime})$ and $(B^{\prime\prime},B^{\prime\prime\prime})$ are
two such edges then $B$ and $B^{\prime\prime}$ do not overlap, and ditto for
$B^{\prime}$ and $B^{\prime\prime\prime}$. This crucially implies that the
random variables $(Z_{B,B^{\prime}})_{(B,B^{\prime})\in\Xi(B_{1},B_{2})}$ are
_mutually independent_. Thus the sum on the left-hand side of (5.6) is a sum
of i.i.d. signs with common mean $\delta^{\circlearrowleft}$. An application
of Bennett’s inequality reveals that the probability that this edge is not
honest is bounded by

$\exp\big{(}-c_{0}(p^{\circlearrowleft})|\Xi(B_{1},B_{2})|\big{)},$

where
$c_{0}(p^{\circlearrowleft})=4p^{\circlearrowleft}(1-p^{\circlearrowleft})h\big{(}\frac{\delta^{\circlearrowleft}}{40p^{\circlearrowleft}(1-p^{\circlearrowleft})}\big{)}$
and $h(u)=(1+u)\log(1+u)-u$, $u\geq 0$. Further, $B^{*}$ has $\ell_{k}^{d}$
level-$k$ sub-blocks and $d\ell_{k}^{d}$ edges, therefore a union bound
implies

$\operatorname{\mathbb{P}}(B^{*}~{}\mbox{is bad})\leq
d\ell_{k}^{d}e^{-c_{0}(p^{\circlearrowleft})|\Xi(B_{1},B_{2})|}+\operatorname{\mathbb{P}}(B^{*}\mbox{
has at least two bad sub-blocks}).$

Since the events that two different (sub-)blocks are bad are independent, the
induction hypothesis implies that the probability on the right-hand side in
the above display is bounded by ${\ell_{k}^{d}\choose 2}\epsilon_{k}^{2}$.
Moreover, have
$|\Xi(B_{1},B_{2})|\geq\lfloor|\partial^{(0)}(B_{1},B_{2})|/2\rfloor$ and

$|\partial^{(0)}(B_{1},B_{2})|=\prod_{j=0}^{k-1}\ell_{j}^{d-1}\geq\big{(}3(2\kappa)^{k}k!^{2}\big{)}^{d-1}~{}~{}~{}\mbox{if}~{}~{}k\geq
1,$

and $|\partial^{(0)}(B_{1},B_{2})|=1$ if $k=0$. We use the crude bound
$|\Xi(B_{1},B_{2})|\geq(2\kappa)^{(d-1)k}$ and obtain

$\displaystyle\operatorname{\mathbb{P}}(B^{*}~{}\mbox{is bad})$
$\displaystyle\leq
d\ell_{k}^{d}\,\exp\big{(}-c_{0}(p^{\circlearrowleft})(2\kappa)^{(d-1)k}\big{)}+\ell_{k}^{2d}\epsilon_{k}^{2}$
$\displaystyle\leq
d\ell_{k}^{d}\,c_{0}(p^{\circlearrowleft})^{-1}(2\kappa)^{-(d-1)k}+\ell_{k}^{2d}\epsilon_{k}^{2}~{}=:\epsilon_{k+1}.$

The problem now reduces to studying the above iteration, starting from
$\epsilon_{0}=0$. We consider the auxiliary sequence

$u_{k}=k^{-2d}(2\kappa)^{(d-1)(k+6)}\epsilon_{k},$

and show that $\sup_{k}u_{k}\leq 1$ when $p^{\circlearrowleft}$ is small
enough. This sequence satisfies

$\displaystyle u_{k+1}$
$\displaystyle=\frac{k^{4d}\ell_{k}^{2d}}{(k+1)^{2d}}(2\kappa)^{-(d-1)(k+5)}u_{k}^{2}+d\frac{\ell_{k}^{d}}{(k+1)^{2d}}\,c_{0}(p^{\circlearrowleft})^{-1}(2\kappa)^{7(d-1)}.$
$\displaystyle\leq
k^{2d}\ell_{k}^{2d}(2\kappa)^{-(d-1)(k+5)}u_{k}^{2}+\frac{2d(2\kappa+1)^{d}(2\kappa)^{7(d-1)}}{c_{0}(p^{\circlearrowleft})}$
$\displaystyle=:A(k)u_{k}^{2}+B.$

By condition $\mathbf{A1}$ in Eq. (5.1) we have $A(k)\leq\frac{1}{2}$ for all
$k\geq 0$. Moreover, it is easy to see that
$c_{0}(p^{\circlearrowleft})\to+\infty$ as $p^{\circlearrowleft}\to 0$, so
there exists $p_{0}=p_{0}(d,\kappa)<1$ such that if $p^{\circlearrowleft}\leq
p_{0}$ then $B\leq\frac{1}{2}$, and we are lead to consider the iteration

$u_{k+1}\leq\frac{1}{2}u_{k}^{2}+\frac{1}{2},~{}~{}\mbox{with}~{}~{}u_{0}=0.$

It is clear that if $u_{k}\leq 1$ then $u_{k+1}\leq 1$, and therefore
$\sup_{k\geq 0}u_{k}\leq 1$, whence $\epsilon_{k}\leq
k^{2d}(2\kappa)^{-(d-1)(k+6)}$ for all $k\geq 0$. $\blacksquare$

For $B^{*}\in\mathcal{B}^{(k+1)}$, we denote by $\mathcal{H}^{(k+1)}_{B^{*}}$
the event that the equation (5.5) is satisfied for some choice of variables
$(W_{B},B\in\mathcal{I}_{B^{*}})$, and call a block $B$ _agreeable_ if it
belongs to no incoherent quartet, i.e., $B\in\mathcal{I}_{B^{*}}$ (where
$B^{*}$ is the upper-level block containing it.)

######  Lemma 5.2.

For all $k\geq 0$, if the $k$-level block $B_{1}$ is good then the following
holds:

  1. 1.

If $k\geq 1$ then all quartets of level-$(k-1)$ good sub-blocks of $B_{1}$ are
coherent.

  2. 2.

The event $\mathcal{H}_{B_{1}}^{(k)}$ holds.

  3. 3.

There exists random a variable $S_{B_{1}}^{(k)}\in\\{\pm 1\\}$ such that if
$B$ is a level-$0$ block in $B_{1}$ whose ancestors up to $B_{1}$ are good and
agreeable, then

$\tilde{\theta}_{B}=S_{B_{1}}^{(k)}\widetilde{W}^{(k-1)}_{B}.$

(By convention, $\widetilde{W}^{(-1)}_{B}=1$.)

  4. 4.

For any good level-$k$ block $B_{2}\sim B_{1}$, we have

$\sum_{\underset{\mathsf{col}(B)=1}{B\in B_{1}\cap\partial
B_{2}}}\tilde{\theta}_{B}S_{B_{1}}^{(k)}\widetilde{W}^{(k-1)}_{B}\geq(1-\epsilon_{k})|\Xi(B_{1},B_{2})|,$

where $\epsilon_{0}=0$ and
$\epsilon_{k+1}=\epsilon_{k}+\frac{2(3^{d-1}+1)}{\ell_{k}^{d-1}}$ for all
$k\geq 0$. In particular, due to condition $\mathbf{A2}$ in Eq. (5.1), we have

$\epsilon_{k}=\sum_{j\leq
k}\frac{2(3^{d-1}+1)}{\ell_{j}^{d-1}}\leq\frac{1}{10}~{}~{}~{}\mbox{for
all}~{}k\geq 0.$

###### Proof.

We proceed by induction. The base case $k=0$ is clear: we can take
$S_{B}^{(0)}=\tilde{\theta}_{B}$ for all level-$0$ blocks $B$ (which are all
good by definition). Now assume the above statements for some $k\geq 0$. Let
$B_{1}^{*}$ be a level-$(k+1)$ good block and $B_{1}\sim B_{2}$ two good and
adjacent level-$k$ sub-blocks of $B_{1}^{*}$. We have

$\displaystyle Y^{(k)}_{B_{1},B_{2}}$
$\displaystyle=\operatorname{sign}\Big{(}\sum_{(B,B^{\prime})\in\Xi(B_{1},B_{2})}\widetilde{Y}_{B,B^{\prime}}\widetilde{W}^{(k-1)}_{B}\widetilde{W}^{(k-1)}_{B^{\prime}}\Big{)}$
$\displaystyle=S_{B_{1}}^{(k)}S_{B_{2}}^{(k)}\cdot\operatorname{sign}\Big{(}\sum_{(B,B^{\prime})\in\Xi(B_{1},B_{2})}\widetilde{Y}_{B,B^{\prime}}\big{(}\widetilde{W}^{(k-1)}_{B}S_{B_{1}}^{(k)}\big{)}\big{(}\widetilde{W}^{(k-1)}_{B^{\prime}}S_{B_{2}}^{(k)}\big{)}\Big{)}.$

We want to show that the sum in the above display is positive. Item 4 in the
induction hypothesis implies

$\sum_{(B,B^{\prime})\in\Xi(B_{1},B_{2})}\widetilde{Y}_{B,B^{\prime}}\big{(}\widetilde{W}^{(k-1)}_{B}S_{B_{1}}^{(k)}\big{)}\big{(}\widetilde{W}^{(k-1)}_{B^{\prime}}S_{B_{2}}^{(k)}\big{)}\geq\sum_{(B,B^{\prime})\in\Xi(B_{1},B_{2})}\widetilde{Y}_{B,B^{\prime}}\tilde{\theta}_{B}\tilde{\theta}_{B^{\prime}}-2\epsilon_{k}|\Xi(B_{1},B_{2})|.$

Now since $B_{1}^{*}$ is good the edge $(B_{1},B_{2})$ is honest and the above
is further lower-bounded by

$\big{(}\frac{9}{10}\delta^{\circlearrowleft}-2\epsilon_{k}\big{)}|\Xi(B_{1},B_{2})|\geq\frac{3}{5}|\Xi(B_{1},B_{2})|>0,$

for $\delta^{\circlearrowleft}>\frac{9}{10}$ (i.e.,
$p^{\circlearrowleft}<\frac{1}{20}$.) Therefore

$Y^{(k)}_{B_{1},B_{2}}=S_{B_{1}}^{(k)}S_{B_{2}}^{(k)},$

for all $B_{1}\sim B_{2}$ good sub-blocks. This means that quartets of good
sub-blocks in a good block are necessarily coherent, proving item 1. The set
$\mathcal{I}_{B_{1}^{*}}$ being connected, it follows that there exists
$S_{B_{1}^{*}}^{(k+1)}\in\\{\pm 1\\}$ such that for all level-$k$ good sub-
blocks $B_{1}\in\mathcal{I}_{B_{1}^{*}}$,

$W_{B_{1}}^{(k)}=S_{B_{1}}^{(k)}S_{B_{1}^{*}}^{(k+1)},$ (5.7)

hence the event $\mathcal{H}_{B_{1}^{*}}^{(k+1)}$ holds. Moreover, for such a
good $B_{1}\in\mathcal{I}_{B_{1}^{*}}$ we have

$S_{B_{1}^{*}}^{(k+1)}\widetilde{W}^{(k)}_{B}=S_{B_{1}^{*}}^{(k+1)}W^{(k)}_{B_{1}}\widetilde{W}^{(k-1)}_{B}=S_{B_{1}}^{(k)}\widetilde{W}^{(k-1)}_{B}=\tilde{\theta}_{B},$

for all level-$0$ blocks $B$ whose ancestors are good and agreeable. Hence
item 3 holds at level $k+1$. It remains to verify item 4 at level $k+1$. Let
$B_{2}^{*}$ be a good level-$(k+1)$ block adjacent to $B_{1}^{*}$. We have

$\displaystyle\sum_{\underset{\mathsf{col}(B)=1}{B\in B_{1}^{*}\cap\partial
B_{2}^{*}}}\tilde{\theta}_{B}S_{B_{1}^{*}}^{(k+1)}\widetilde{W}^{(k)}_{B}=\sum_{B_{1}^{*}\ni\bar{B}_{1}\sim\bar{B}_{2}\in
B_{2}^{*}}\Big{(}\sum_{\underset{\mathsf{col}(B)=1}{\bar{B}_{1}\ni B\sim
B^{\prime}\in\bar{B}_{2}}}\tilde{\theta}_{B}\widetilde{W}^{(k-1)}_{B}\Big{)}S_{B_{1}^{*}}^{(k+1)}W_{\bar{B}_{1}}^{(k)},$

where the outer sum is on level-$k$ sub-blocks $\bar{B}_{1}$ and
$\bar{B}_{2}$. Let $\mathcal{A}$ be the subset of those $\bar{B}_{1}$,
level-$k$ sub-blocks of $B_{1}^{*}$ which are good, are in
$\mathcal{I}_{B_{1}^{*}}$, and are adjacent to a good sub-block
$\bar{B}_{2}\in B_{2}^{*}$. Since there is only one bad sub-block in
$B_{1}^{*}$, there are at most $3^{d-1}$ positions on the boundary of
$B_{1}^{*}$ which could possibly belong to an incoherent quartet because this
quartet must necessarily contain that single bad sub-block. Moreover,
$B_{2}^{*}$ being good, it has only one bad sub-block. Therefore the above sum
is lower-bounded by

$\displaystyle\sum_{\bar{B}_{1}\in\mathcal{A}}\Big{(}\sum_{\underset{\mathsf{col}(B)=1}{\bar{B}_{1}\ni
B\sim
B^{\prime}\in\bar{B}_{2}}}\tilde{\theta}_{B}\widetilde{W}^{(k-1)}_{B}\Big{)}S_{B_{1}^{*}}^{(k+1)}W_{\bar{B}_{1}}^{(k)}-(1+3^{d-1})|\Xi(\bar{B}_{1},\bar{B}_{2})|$
$\displaystyle=\sum_{\bar{B}_{1}\in\mathcal{A}}\Big{(}\sum_{\underset{\mathsf{col}(B)=1}{\bar{B}_{1}\ni
B\sim
B^{\prime}\in\bar{B}_{2}}}\tilde{\theta}_{B}\widetilde{W}^{(k-1)}_{B}S^{(k)}_{\bar{B}_{1}}\Big{)}-(1+3^{d-1})|\Xi(\bar{B}_{1},\bar{B}_{2})|.$

We use item 4 of the induction hypothesis:
$\underset{\underset{\mathsf{col}(B)=1}{\bar{B}_{1}\ni B\sim
B^{\prime}\in\bar{B}_{2}}}{\sum}\tilde{\theta}_{B}\widetilde{W}^{(k-1)}_{B}S^{(k)}_{\bar{B}_{1}}\geq(1-\epsilon_{k})|\Xi(\bar{B}_{1},\bar{B}_{2})|$,
whence the above is lower bounded by

$\displaystyle\sum_{\bar{B}_{1}\in\mathcal{A}}(1-\epsilon_{k})|\Xi(\bar{B}_{1},\bar{B}_{2})|-(1+3^{d-1})|\Xi(\bar{B}_{1},\bar{B}_{2})|$
$\displaystyle\geq\sum_{\underset{\mathsf{col}(B)=1}{B_{1}^{*}\ni\bar{B}_{1}\sim\bar{B}_{2}\in
B_{2}^{*}}}(1-\epsilon_{k})|\Xi(\bar{B}_{1},\bar{B}_{2})|-(2-\epsilon_{k})(1+3^{d-1})|\Xi(\bar{B}_{1},\bar{B}_{2})|$
$\displaystyle=(1-\epsilon_{k})|\Xi(B_{1}^{*},B_{2}^{*})|-(2-\epsilon_{k})(1+3^{d-1})|\Xi(\bar{B}_{1},\bar{B}_{2})|.$

Since
$|\Xi(B_{1}^{*},B_{2}^{*})|/|\Xi(\bar{B}_{1},\bar{B}_{2})|=\ell_{k}^{d-1}$ we
obtain

$\displaystyle\sum_{\underset{\mathsf{col}(B)=1}{B\in B_{1}^{*}\cap\partial
B_{2}^{*}}}\tilde{\theta}_{B}S_{B_{1}^{*}}^{(k+1)}\widetilde{W}^{(k)}_{B}$
$\displaystyle\geq\Big{(}1-\epsilon_{k}-\frac{2(1+3^{d-1})}{\ell_{k}^{d-1}}\Big{)}|\Xi(B_{1}^{*},B_{2}^{*})|$
$\displaystyle=(1-\epsilon_{k+1})|\Xi(B_{1}^{*},B_{2}^{*})|.$

This concludes the inductive argument. $\blacksquare$

We now finish the proof of Theorem 4.2. Let $B_{1}$ and $B_{2}$ be two
level-$0$ blocks and let $B^{*}$ be their most recent common ancestor in the
hierarchical partitioning; we let $k$ be its level. Item 2 in Lemma 5.2
implies that a sufficient condition for accurately synchronizing $B_{1}$ and
$B_{2}$, i.e.,
$\widetilde{T}_{B_{1},B_{2}}=\tilde{\theta}_{B_{1}}\tilde{\theta}_{B_{2}}$, is
that $B_{1}$ and $B_{2}$ along with their ancestors $B^{(j)}_{1}$ and
$B^{(j)}_{2}$ for $j=0,\cdots,k$ up to $B^{*}$ are all good and agreeable.
(Here we have $B^{(0)}_{1}=B_{1}$ and $B^{(k)}_{1}=B^{*}$ and similarly for
$B_{2}$.) Let us call this event $J_{B_{1},B_{2}}^{(k)}$. By a union bound we
obtain

$1-\operatorname{\mathbb{P}}\big{(}J_{B_{1},B_{2}}^{(k)}\big{)}\leq\sum_{j=0}^{k-1}\sum_{a=1}^{2}\operatorname{\mathbb{P}}\big{(}B^{(j)}_{a}~{}\mbox{is
bad or non-agreeable}\big{)}+\operatorname{\mathbb{P}}\big{(}B^{*}~{}\mbox{is
bad}\big{)}.$

A non-agreeable block must belong to at least one incoherent quartet. Since a
quartet of good sub-blocks belonging to a good block is necessarily coherent,
a non-agreeable block inside a good block is the center of a cube of side-
length 3 in which at least one block is bad. Hence for $0\leq j\leq k-1$ and
$a=1,2$,

$\displaystyle\operatorname{\mathbb{P}}\big{(}B^{(j)}_{a}~{}\mbox{is bad or
non-agreeable}\big{)}$
$\displaystyle\leq\operatorname{\mathbb{P}}\big{(}B^{(j)}_{a}~{}\mbox{is bad
or non-agreeable}~{}\big{|}B^{(j+1)}_{a}~{}\mbox{is good}\big{)}$
$\displaystyle~{}~{}~{}+\operatorname{\mathbb{P}}\big{(}B^{(j+1)}_{a}~{}\mbox{is
bad}\big{)}$ $\displaystyle\leq
3^{d}\operatorname{\mathbb{P}}\big{(}B^{(j)}_{a}~{}\mbox{is
bad}\big{)}+\operatorname{\mathbb{P}}\big{(}B^{(j+1)}_{a}~{}\mbox{is
bad}\big{)}.$

Therefore,

$\displaystyle 1-\operatorname{\mathbb{P}}\big{(}J_{B_{1},B_{2}}^{(k)}\big{)}$
$\displaystyle\leq 2\cdot
3^{d}\sum_{j=0}^{k-1}\operatorname{\mathbb{P}}\big{(}B^{(j)}_{1}~{}\mbox{is
bad}\big{)}+2\sum_{j=1}^{k}\operatorname{\mathbb{P}}\big{(}B^{(j)}_{1}~{}\mbox{is
bad}\big{)}+\operatorname{\mathbb{P}}\big{(}B^{*}~{}\mbox{is bad}\big{)}$
$\displaystyle\leq
2(1+3^{d})\sum_{j=1}^{k}\operatorname{\mathbb{P}}\big{(}B^{(j)}_{1}~{}\mbox{is
bad}\big{)}$ $\displaystyle\leq
2(1+3^{d})\sum_{j=0}^{\infty}j^{2d}(2\kappa)^{-(d-1)(j+6)}\leq\frac{1}{21}.$

The third inequality follows from Lemma 5.1, which requires
$p^{\circlearrowleft}\leq p_{0}$, and this can be satisfied if
$L^{\circlearrowleft}$ is large enough and $\eta$ small enough, as already
proved in Theorem 4.1. The last inequality is condition $\mathbf{A3}$ in Eq.
(5.1).

Finally, concerning the running time of the algorithm, $B_{1}$ and $B_{2}$ are
separated by distance at most $\frac{2n}{L^{\circlearrowleft}}$. Further, the
side length of a block of level $j$, $\ell_{j}$, grows super-exponentially,
hence $B^{*}$ is of level $k=\mathcal{O}(\log n)$. At every level $j$, the
random variables $(W^{(j)}_{B^{(j)}})$ and $(Y_{B_{1},B_{2}}^{(j)})$ are
constructed in time $c_{0}\ell_{j}^{d}$ for some absolute constant $c_{0}$,
and there are
$n_{j}=\big{(}2n\big{/}L^{\circlearrowleft}\cdot\prod_{j^{\prime}\leq
j-1}\ell_{j^{\prime}}\big{)}^{d}$ many blocks of level $j$. Therefore the
variables $(\tilde{W}^{(k)}_{B})_{B\in\mathbb{B}_{n}}$ are constructed in time

$\displaystyle\sum_{j=0}^{k}(\ell_{j}n_{j})^{d}$
$\displaystyle=\Big{(}\frac{2n}{L^{\circlearrowleft}}\Big{)}^{d}\Big{(}1+\sum_{j=1}^{k}\prod_{j^{\prime}=0}^{j-1}\ell_{j^{\prime}}^{-d}\Big{)}$
$\displaystyle\leq c_{0}(d)\Big{(}\frac{2n}{L^{\circlearrowleft}}\Big{)}^{d}.$

The final step of the algorithm is to take pairwise products
$\widetilde{T}_{B_{1},B_{2}}=\tilde{W}^{(k)}_{B_{1}}\tilde{W}^{(k)}_{B_{2}}$
which takes $\mathcal{O}(\big{(}\frac{2n}{L^{\circlearrowleft}}\big{)}^{2d})$
steps. Since $L^{\circlearrowleft}$ doesn’t depend on $n$, the runtime of the
whole algorithm is $\mathcal{O}(n^{2d})$.

##  6 Posterior measures

The analysis of the renormalization procedure relies on understanding the
concentration properties of the posterior measure of
$\theta_{A}=(\theta_{x})_{x\in A}$ given information associated to
$A\subset\mathbb{Z}^{d}$, for various subsets $A$. Concretely we will
investigate the asymptotic properties of the ‘free energies’ which are the
normalized log-partition functions of the posterior measures and then extract
convergence and concentration properties of certain overlaps. These free
energies will converge to variational formulas given in terms of a simpler
system where the side information is decoupled across vertices. We begin by
describing this setting.

###  6.1 Scalar side information

Let $(B_{n})_{n\geq 1}$ be a sequence of finite connected subsets of
$\mathbb{Z}^{d}$ which is increasing: $B_{n}\subseteq B_{n+1}$, invades the
entire lattice: $\bigcup_{n\geq 1}B_{n}=\mathbb{Z}^{d}$, and has vanishing
isoperimetry: $\underset{n\to\infty}{\lim}|\partial B_{n}|/|B_{n}|=0$. We call
such a sequence a _van Hove_ sequence [FV17]. Consider the scalar additive
Gaussian noise channel with SNR $\lambda\geq 0$ on $B_{n}$:

$y_{u}=\sqrt{\lambda}\theta_{u}+z_{u},~{}~{}~{}\forall u\in B_{n},$ (6.1)

where $(z_{u})_{u\in B_{n}}$ are i.i.d. Gaussian random variables independent
of everything else. Consider the posterior measure of $\theta_{B_{n}}$ given
the lattice information $Y^{\delta}_{B_{n}}=\\{Y^{\delta}_{uv}:(u,v)\in
B_{n}^{2}\cap\mathbb{E}^{d}\\}$ and $Y^{\lambda}_{B_{n}}=\\{y_{u}:u\in
B_{n}\\}$:

$\operatorname{\mathbb{P}}\Big{(}\big{(}\theta_{x}\big{)}_{x\in
B_{n}}\big{|}Y^{\delta}_{B_{n}},Y^{\lambda}_{B_{n}}\Big{)}=\frac{1}{Z_{B_{n}}}e^{H_{B_{n}}^{\delta}(\theta)+H_{B_{n}}^{\lambda}(\theta)},$
(6.2)

where

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

with $\beta=\frac{1}{2}\log(\frac{1-p}{p})$ is the Hamiltonian encoding the
lattice interaction and

$H_{B_{n}}^{\lambda}(\theta)=\sum_{u\in
B_{n}}\big{(}\sqrt{\lambda}y_{u}\theta_{u}-\frac{\lambda}{2}\big{)},$ (6.4)

encodes the side information $Y^{\lambda}_{B_{n}}$. We define the free energy
associated to this posterior by

$f^{\textup{{sc}}}_{B_{n}}(\delta,\lambda):=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{H_{B_{n}}^{\delta}(\theta)+H_{B_{n}}^{\lambda}(\theta)}\Big{\\}},$
(6.5)

where the expectation is with respect to $Y^{\delta}_{B_{n}}$ and
$Y^{\lambda}_{B_{n}}$. We also define a more general function with two
parameters $s\in\mathbb{R}$ and $r\geq 0$:

$\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,s,r):=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{H_{B_{n}}^{\delta}(\theta)+{\widetilde{H}}^{r,s}_{B_{n}}(\theta)}\Big{\\}},$
(6.6)

where

${\widetilde{H}_{B_{n}}}^{r,s}(\theta):=\sum_{u\in
B_{n}}\big{(}\sqrt{r}z_{u}\theta_{u}+s\theta_{u}\theta_{0u}-\frac{r}{2}\big{)},$

where $(z_{u})_{u\in B_{n}}$ are i.i.d. $N(0,1)$ r.v.’s and
$(\theta_{0u})_{u\in B_{n}}$ are independent symmetric signs. Note that
$\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,r,r)=f^{\textup{{sc}}}_{B_{n}}(\delta,r)$
for all $r\geq 0$333When $s\neq r$, the Gibbs measure proportional to
$e^{H_{B_{n}}^{\delta}(\theta)+{\widetilde{H}}^{r,s}_{B_{n}}(\theta)}$ doe not
have a Bayesian interpretation as the posterior distribution of a set of
random variables given some sort of observations..

######  Proposition 6.1.

For all $\delta\in[0,1]$, $s\in\mathbb{R}$ and $r\geq 0$,
$\widetilde{f^{\textup{{sc}}}_{B_{n}}}(\delta,s,r)$ has a limit
$\widetilde{f^{\textup{{sc}}}}(\delta,s,r)$ as $n\to\infty$ which does not
depend on the van Hove sequence $(B_{n})$. Moreover the convergence is uniform
on any compact set $[0,\delta_{0}]\times[-s_{0},s_{0}]\times[0,r_{0}]$ with
$s_{0},r_{0}>0$ and $\delta_{0}<1$.

We let
$f^{\textup{{sc}}}(\delta,\lambda):=\widetilde{f^{\textup{{sc}}}}(\delta,\lambda,\lambda)$
be the limit of $f^{\textup{{sc}}}_{B_{n}}(\delta,\lambda)$. We do not know of
an ‘explicit’ expression for either $\widetilde{f^{\textup{{sc}}}}$ or
$f^{\textup{{sc}}}$, but some of their properties are revealed through the
sequence $\widetilde{f^{\textup{{sc}}}_{B_{n}}}$. For instance, convexity and
monotonicity are inherited by passage to the limit:

######  Lemma 6.2.

For all $\delta\in[0,1]$ and $r\geq 0$, the map
$s\mapsto\widetilde{f^{\textup{{sc}}}}(\delta,s,r)$ is even and convex, and
the map $\lambda\mapsto f^{\textup{{sc}}}(\delta,\lambda)$ is nondecreasing
and convex.

Hence the map $\lambda\mapsto f^{\textup{{sc}}}(\delta,\lambda)$ is
differentiable everywhere expect on a countable set of points $\mathcal{D}$
possibly depending on $\delta$. Lemma 6.2 implies that the derivatives
$\frac{\mathrm{d}}{\mathrm{d}\lambda}f^{\textup{{sc}}}_{B_{n}}$ converges to
$\frac{\mathrm{d}}{\mathrm{d}\lambda}f^{\textup{{sc}}}$ on
$\mathbb{R}_{+}\setminus\mathcal{D}$. An easy computation of the derivative of
$f_{B_{n}}$ reveals that for all $\delta\in[0,1]$ and
$\lambda\in\mathbb{R}_{+}\setminus\mathcal{D}$,

$\frac{1}{2}\varphi^{\mbox{\rm\tiny v}}_{B_{n}}:=\frac{1}{2|B_{n}|}\sum_{x\in
B_{n}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta}_{B_{n}},Y^{\lambda}_{B_{n}}\big{]}^{2}\Big{]}\xrightarrow[n\to\infty]{}\frac{\mathrm{d}}{\mathrm{d}\lambda}f^{\textup{{sc}}}.$
(6.7)

Lemma 6.2 also implies that
$s\mapsto\widetilde{f^{\textup{{sc}}}}(\delta,s,r)$ is differentiable on
$\mathbb{R}\setminus\mathcal{D}^{\prime}$ where $\mathcal{D}^{\prime}$ is
countable and depends on $\delta$ and $r$. For technical reasons we will need
the following regularity condition on $f^{\textup{{sc}}}$:

######  Assumption 1.

We assume the following.

  * A1.

For all $\delta>\delta_{c}$, the map
$\lambda\mapsto\frac{\mathrm{d}}{\mathrm{d}\lambda}f^{\textup{{sc}}}(\delta,\lambda)$
is Lipschitz on $\mathbb{R}_{+}\setminus\mathcal{D}$ with Lipschitz constant
$L=L(\delta)<\infty$.

  * A2.

For all $\delta>\delta_{c}$ and all $r\geq 0$, the map
$s\mapsto\frac{\mathrm{d}}{\mathrm{d}s}\widetilde{f^{\textup{{sc}}}}(\delta,s,r)$
is Lipschitz on $\mathbb{R}\setminus\mathcal{D}^{\prime}$ uniformly in $r$
with Lipschitz constant $L^{\prime}=L^{\prime}(\delta)<\infty$.

These assumptions are highly plausible and are supported by physical
intuition: we do not expect these model to have a phase transition in the
strength $s$ of the magnetic field for $\delta>\delta_{c}$. For instance when
$r=s=\lambda$, the scalar side information has the effect of destroying long
range correlation, see e.g., [Mon08], and every spin $\theta_{x}$ gains a
small and independent bias towards the ground truth assignment when
$\lambda>0$. This bias must increase in a smooth way as $\lambda$ increases,
and the free energy should be analytic in $\lambda$. This assumption will be
explicitly mentioned whenever needed, and not required if not invoked.

###  6.2 GOE side information

The side information we are ultimately interested in is the spiked GOE
$Y^{\eta}_{B_{n}}=\\{Y^{\eta}_{uv}:u,v\in B_{n}\\}$ where
$Y^{\eta}_{uv}=\sqrt{\frac{\eta}{|B_{n}|}}\theta_{u}\theta_{v}+Z_{uv}$,
$Z_{uv}\sim N(0,1)$ independent of everything else. The posterior measure is

$\operatorname{\mathbb{P}}\Big{(}\big{(}\theta_{x}\big{)}_{x\in
B_{n}}\big{|}Y^{\delta}_{B_{n}},Y^{\eta}_{B_{n}}\Big{)}=\frac{1}{Z_{B_{n}}}e^{H_{B_{n}}^{\delta}(\theta)+H_{B_{n}}^{\eta}(\theta)},$
(6.8)

where

$H_{B_{n}}^{\eta}(\theta):=\sum_{u,v\in
B_{n}}\Big{(}\sqrt{\frac{\eta}{|B_{n}|}}Y_{uv}^{\eta}\theta_{u}\theta_{v}-\frac{\eta}{2|B_{n}|}\Big{)}.$
(6.9)

We similarly define the free energy

$f_{B_{n}}(\delta,\eta):=\frac{1}{|B_{n}|}\operatorname{\mathbb{E}}\log\Big{\\{}2^{-|B_{n}|}\sum_{\theta\in\\{\pm
1\\}^{B_{n}}}e^{H_{B_{n}}^{\delta}(\theta)+H_{B_{n}}^{\eta}(\theta)}\Big{\\}}.$
(6.10)

######  Proposition 6.3.

For all $\delta\in[0,1]$, $\eta\geq 0$, $f_{B_{n}}(\delta,\eta)$ has a limit
$\phi(\delta,\eta)$ as $n\to\infty$ which does not depends on the van Hove
sequence $(B_{n})$, and we have the relation

$\phi(\delta,\eta)=\sup_{q\geq 0}\Big{\\{}f^{\textup{{sc}}}(\delta,\eta
q)-\frac{\eta q^{2}}{4}\Big{\\}}.$ (6.11)

Similarly to the scalar side information case,
$\frac{\mathrm{d}}{\mathrm{d}\eta}f_{B_{n}}$ converges to
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi$ everywhere except on countably many
points. On the one hand, the derivative of $f_{B_{n}}$ is

$\frac{\mathrm{d}}{\mathrm{d}\eta}f_{B_{n}}=\frac{1}{4|B_{n}|^{2}}\sum_{x,y\in
B_{n}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta}_{B_{n}},Y^{\eta}_{B_{n}}\big{]}^{2}\Big{]}=\frac{1}{4}\varphi^{\mbox{\rm\tiny
e}}_{B_{n}}.$ (6.12)

On the other hand, the derivative of $\phi$ can be linked to the maximizer in
the variational formula (6.11). This proves Proposition 1.1 and provides a
another characterization of $q_{\star}$:

######  Lemma 6.4.

For all $\delta\in[0,1]$ and all $\eta$ where $\phi(\delta,\cdot)$ is
differentiable, the above maximization problem has a unique maximizer
$q_{\star}\in[0,1]$, and
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi(\delta,\lambda)=q_{\star}^{2}/4$.
Therefore, for all $\delta$ and all except countably many $\eta$, we obtain
the relation $\varphi^{\mbox{\rm\tiny e}}_{B_{n}}\to q_{\star}^{2}$ as
$n\to\infty$.

###### Proof.

This argument appears in [LM17] but we reproduce it here for the sake of
completeness. First, it is easy to see that the supremum in (6.11) is
achieved. Indeed $f^{\textup{{sc}}}$ being convex, it is also continuous, and
one has the elementary bound $f^{\textup{{sc}}}(\delta,\lambda)\leq 2\beta
d+\lambda$. Therefore, large values of $q$ cannot achieve the supremum. Next,
we reparametrize the variational formula as
$\phi(\delta,\eta)=\sup_{\bar{q}\geq
0}\\{f^{\textup{{sc}}}(\delta,\bar{q})-\frac{\bar{q}^{2}}{4\eta}\\}$ with
$\bar{q}=\eta q$. The envelope theorem implies that on points of
differentiability of $\phi$, we have
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi=\bar{q}^{2}/4\eta^{2}$ where $\bar{q}$
is any point achieving the maximum. Therefore the maximum is achieved at a
unique point $q_{\star}$ and we have
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi(\delta,\lambda)=q_{\star}^{2}/4$.
Moreover from (6.12), the fact that
$\frac{\mathrm{d}}{\mathrm{d}\eta}f_{B_{n}}$ converges to
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi$ whenever the derivative is defined
implies the last claim $\varphi^{\mbox{\rm\tiny e}}_{B_{n}}\to q_{\star}^{2}$.
$\blacksquare$

###  6.3 One-block and two-block posteriors

In this subsection we analyze the _one-block_ and _two-block_ posteriors:
these are the posterior measures of $(\theta_{x})_{x\in B}$ and
$(\theta_{x})_{x\in B\cup B^{\prime}}$ for $B\sim B^{\prime}$ respectively,
where the blocks and the associated side information were constructed in
Section 3. Since the strength of the GOE side information is inhomogeneous
within a given block, the posteriors and their free energies are not special
cases of the setting discussed above. Nevertheless the results and arguments
will have a similar flavor.

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)},$ (6.13)

where as before, $H^{\delta}_{B}$ is the Hamiltonian encoding the lattice
interaction on $B$, and

$\omega^{\mbox{\rm\tiny SK}}_{B}(\theta):=\prod_{B^{\prime}\sim
B}e^{H^{\eta}_{B^{\prime}}(\theta)}.$ (6.14)

is the Boltzmann weight encoding the heterogeneous GOE side information (3.1):
For $B^{\prime}=B+L^{\circlearrowleft}a$, $a\in\\{\pm e_{1},\cdots,\pm
e_{d}\\}$, and for $\theta\in\\{\pm 1\\}^{B}$,

$\displaystyle H^{\eta}_{B^{\prime}}(\theta)$ $\displaystyle:=\sum_{u,v\in
B}\Big{(}\sqrt{\frac{t\eta}{|B|}}Y_{uv}^{\eta,(a)}\theta_{u}\theta_{v}-\frac{t\eta}{2|B|}\Big{)}$
(6.15) $\displaystyle~{}+\sum_{u,v\in B\cap
B^{\prime}}\Big{(}\sqrt{\frac{(1-t)\eta}{|B\cap
B^{\prime}|}}Y_{uv}^{\eta,(a,\cap)}\theta_{u}\theta_{v}-\frac{(1-t)\eta}{2|B\cap
B^{\prime}|}\Big{)}$ $\displaystyle~{}+\sum_{u,v\in B\setminus
B^{\prime}}\Big{(}\sqrt{\frac{(1-t)\eta}{|B\setminus
B^{\prime}|}}Y_{uv}^{\eta,(a,\setminus)}\theta_{u}\theta_{v}-\frac{(1-t)\eta}{2|B\setminus
B^{\prime}|}\Big{)}.$

Similarly, for two adjacent blocks $B\sim 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)},$ (6.16)

where for $\theta\in\\{\pm 1\\}^{B\cup B^{\prime}}$, denoting by $\theta_{B}$
and $\theta_{B^{\prime}}$ the restrictions of $\theta$ to $B$ and $B^{\prime}$
respectively,

$\omega_{B\cup B^{\prime}}^{\mbox{\rm\tiny
SK}}(\theta):=\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}})}.$ (6.17)

We define the free energies of the above posteriors as

$f_{B}(\delta,\eta,t):=\frac{1}{|B|}\operatorname{\mathbb{E}}\log
Z_{B},\quad\mbox{and}\quad f_{B\cup
B^{\prime}}(\delta,\eta,t):=\frac{1}{|B|}\operatorname{\mathbb{E}}\log
Z_{B\cup B^{\prime}},$ (6.18)

where $Z_{B}$ and $Z_{B\cup B^{\prime}}$ are the normalizing constant of the
one-block and two-block posteriors, respectively. Let
$\alpha:=\underset{L^{\circlearrowleft}\to\infty}{\lim}\frac{|B\cap
B^{\prime}|}{|B|}=\frac{1}{3^{d}+d}$.

######  Proposition 6.5.

Under Assumption 1, there exists $\eta_{0}=\eta_{0}(d,\delta)>0$ such that if
$\eta\in\mathbb{R}_{+}\setminus\mathcal{D}$ and $\eta\leq\eta_{0}$ then the
following holds. For all $B,B^{\prime}\in\mathbb{B}$, with $B\sim B^{\prime}$,
and all $\delta>\delta_{c}$, and $t\in[0,1]$, the free energies $f_{B}$ and
$f_{B\cup B^{\prime}}$ converge to limits $\phi_{1}$ and $\phi_{2}$,
respectively, as $L^{\circlearrowleft}\to\infty$. Moreover, $\phi_{1}$ and
$\phi_{2}$ admit the following variational representations

$\displaystyle\phi_{1}$ $\displaystyle=\sup_{q\geq
0}\Big{\\{}f^{\textup{{sc}}}(\delta;2d\eta q)-\frac{d}{2}\eta
q^{2}\Big{\\}}=\phi(\delta,2d\eta),$ (6.19) $\displaystyle\phi_{2}$
$\displaystyle=\sup_{q\geq
0}\Big{\\{}2(1-\alpha)f^{\textup{{sc}}}(\delta;2d\eta q)+\alpha
f^{\textup{{sc}}}(\delta;4d\eta q)-d\eta q^{2}\Big{\\}}.$ (6.20)

In particular $\phi_{1}$ and $\phi_{2}$ do not depend on the time parameter
$t$ when $\eta\leq\eta_{0}$.

Independence with respect to $t$ implies a fundamental _locking_ property of
the overlaps: under either the one-block or the two-block posterior measures,
overlaps of two independent samples on different subsets of vertices of the
whole system are almost equal. To state this property, we adopt the following
the notation. For $A\in\\{B,B\cup B^{\prime}\\}$ define

$V_{A}(B;B^{\prime}):=\alpha\operatorname{\mathbb{E}}\left\langle\big{(}R_{1,2}(B\cap
B^{\prime})-R_{1,2}(B)\big{)}^{2}\right\rangle_{A}+(1-\alpha)\operatorname{\mathbb{E}}\left\langle\big{(}R_{1,2}(B\setminus
B^{\prime})-R_{1,2}(B)\big{)}^{2}\right\rangle_{A},$

where the Gibbs average $\langle\cdot\rangle_{A}$ is a short-hand for the
average w.r.t the one-block posterior in the case $A=B$ or the two-block
posterior in the case $A=B\cup B^{\prime}$, and
$R_{1,2}(A)=\frac{1}{|A|}\sum_{x\in A}\theta^{1}_{x}\theta^{2}_{x}$ where
$\theta^{1},\theta^{2}$ is a pair of independently drawn samples from the
one/two-block posterior measure.

######  Proposition 6.6.

Under Assumption 1, there exists $\eta_{0}=\eta_{0}(d,\delta)>0$ such that for
$\eta\leq\eta_{0}$ almost all $t\in[0,1]$, we have $V_{B}(B,B^{\prime})\to 0$
for all $B^{\prime}\sim B$, $V_{B\cup B^{\prime}}(B,B^{\prime\prime})\to 0$
for all $B^{\prime\prime}\sim B$, and $V_{B\cup
B^{\prime}}(B^{\prime},B^{\prime\prime})\to 0$ for all $B^{\prime\prime}\sim
B^{\prime}$ as $L^{\circlearrowleft}\to\infty$.

###### Proof.

Convexity of $f_{B}$ and $f_{B\cup B^{\prime}}$ w.r.t. $t$ implies that their
derivatives converge to the derivatives of the limits $\phi_{1}$ and
$\phi_{2}$ everywhere except on countably many points. A short computation of
the finite-volume derivatives reveals

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}f_{B}$
$\displaystyle=-\frac{\eta}{2}\sum_{B^{\prime}\sim
B}V_{B}(B;B^{\prime}),\qquad\mbox{and}$
$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}f_{B\cup B^{\prime}}$
$\displaystyle=-\frac{\eta}{2}\sum_{B^{\prime\prime}\sim B}V_{B\cup
B^{\prime}}(B,B^{\prime\prime})-\frac{\eta}{2}\sum_{B^{\prime\prime}\sim
B^{\prime}}V_{B\cup B^{\prime}}(B^{\prime};B^{\prime\prime}).$

Since by Proposition 6.5, the limits do not depend on $t$ for
$\eta\leq\eta_{0}$, the above right-hand sides converge to zero.
$\blacksquare$

Now that overlaps of sub-blocks of a given block are locked together, they are
all asymptotically equal to the overlap on the entire block ($B$ in the case
of the one-block posterior and $B\cup B^{\prime}$ in the case of the two-block
posterior). The limits of these global overlaps are again available by
differentiating w.r.t. $\eta$. Similarly to $V_{A}(B;B^{\prime})$, we define

$W_{A}(B;B^{\prime}):=t\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B)^{2}\right\rangle_{A}+(1-t)\Big{(}\alpha\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B\cap
B^{\prime})^{2}\right\rangle_{A}+(1-\alpha)\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B\setminus B^{\prime})^{2}\right\rangle_{A}\Big{)}.$

Thus we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\eta}f_{B}$
$\displaystyle=\frac{1}{4}\sum_{B^{\prime}\sim
B}W_{B}(B;B^{\prime}),\qquad\mbox{and}$
$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\eta}f_{B\cup B^{\prime}}$
$\displaystyle=\frac{1}{4}\sum_{B^{\prime\prime}\sim B}W_{B\cup
B^{\prime}}(B;B^{\prime\prime})+\frac{1}{4}\sum_{B^{\prime\prime}\sim
B^{\prime}}W_{B\cup B^{\prime}}(B^{\prime};B^{\prime\prime}).$

We deduce from Proposition 6.6 that

$\frac{\mathrm{d}}{\mathrm{d}\eta}f_{B}=\frac{d}{2}\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B)^{2}\right\rangle_{B}+o_{L^{\circlearrowleft}}(1),~{}~{}\mbox{and}~{}~{}\frac{\mathrm{d}}{\mathrm{d}\eta}f_{B\cup
B^{\prime}}=d\operatorname{\mathbb{E}}\left\langle R_{1,2}(B\cup
B^{\prime})^{2}\right\rangle_{B\cup B^{\prime}}+o_{L^{\circlearrowleft}}(1),$

where $o_{L^{\circlearrowleft}}(1)\to 0$ for almost all $t$ and all
$\eta\leq\eta_{0}$. Hence the following

######  Corollary 6.7.

Under Assumption 1, let $q^{\bullet}_{1}$ and $q^{\bullet}_{2}$ be the unique
maximizers in the variational problems (6.19) and (6.20) respectively. For
almost all $t\in[0,1]$ and all except countably many $\eta\in[0,\eta_{0}]$, we
have $\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B)^{2}\right\rangle_{B}\to{q^{\bullet}_{1}}^{2}$ and
$\operatorname{\mathbb{E}}\left\langle R_{1,2}(B\cup
B^{\prime})^{2}\right\rangle_{B\cup B^{\prime}}\to{q^{\bullet}_{2}}^{2}$ as
$L^{\circlearrowleft}\to\infty$.

###### Proof.

From (6.19) and Lemma 6.4 we have
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi_{1}=d{q^{\bullet}_{1}}^{2}/2$. Second,
note that the same argument used to obtain Lemma 6.4 applies to the formula
(6.20), hence the existence and uniqueness of the maximizer $q^{\bullet}_{2}$,
and $\frac{\mathrm{d}}{\mathrm{d}\lambda}\phi_{2}=d{q^{\bullet}_{2}}^{2}$.
Now, given formulas above for the derivatives of $f_{B}$ and $f_{B\cup
B^{\prime}}$, and since these derivatives converge to
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi_{1}$ and
$\frac{\mathrm{d}}{\mathrm{d}\eta}\phi_{2}$ respectively as
$L^{\circlearrowleft}\to\infty$ for all except countably many $\eta>0$, we
obtain the desired result. $\blacksquare$

Next, we show that the maximizers $q_{\star}$, $q^{\bullet}_{1}$ and
$q^{\bullet}_{2}$ of the variational formulas (6.11), (6.19) and (6.20)
respectively are close together when $\eta$ is small.

######  Lemma 6.8.

Under Assumption 1, and for $\delta>\delta_{c}$, there exist a constant
$c_{0}=c_{0}(d,L,\eta_{0})>0$ such that for all except countably many
$\eta\in[0,\eta_{0}]$,
$|q^{\bullet}_{2}-q^{\bullet}_{1}|\vee|q^{\bullet}_{1}-q_{\star}|\leq
c_{0}\eta$.

###### Proof.

Since $\delta>\delta_{c}$ all the maximizers are strictly positive and must
satisfy first order optimality conditions:

${f^{\textup{{sc}}}}^{\prime}(\delta;\eta
q_{\star})=\frac{q_{\star}}{2},~{}~{}{f^{\textup{{sc}}}}^{\prime}(\delta,2d\eta
q^{\bullet}_{1})=\frac{q^{\bullet}_{1}}{2},~{}~{}(1-\alpha){f^{\textup{{sc}}}}^{\prime}(\delta,2d\eta
q^{\bullet}_{2})+\alpha{f^{\textup{{sc}}}}^{\prime}(\delta,4d\eta
q^{\bullet}_{2})=\frac{q^{\bullet}_{2}}{2}.$

We take the difference of the first two equations and use the assumed
Lipschitz property of ${f^{\textup{{sc}}}}^{\prime}$ to obtain
$|q^{\bullet}_{1}-q_{\star}|\leq 2L\eta|2dq^{\bullet}_{1}-q_{\star}|$, or
$|q^{\bullet}_{1}-q_{\star}|\leq\frac{2L\eta}{1-2L\eta}(2d-1)q_{\star}$. And
we use the trivial bound $q_{\star}\leq 1$ (this is because
${f^{\textup{{sc}}}}^{\prime}(\delta,\lambda)\leq 1$). Similarly, taking the
difference of the last two equations we obtain
$|q^{\bullet}_{2}-q^{\bullet}_{1}|\leq\frac{4L\alpha\eta}{1-4L\eta}q^{\bullet}_{2}$.
$\blacksquare$

Corollary 6.7 and Lemma 6.8 show that the squared global overlaps
$\operatorname{\mathbb{E}}\left\langle R_{1,2}(B)^{2}\right\rangle_{B}$ and
$\operatorname{\mathbb{E}}\left\langle R_{1,2}(B\cup
B^{\prime})^{2}\right\rangle_{B\cup B^{\prime}}$ converge to the same value
$q_{\star\star}^{2}(\delta)$ as $\eta\to 0$.

###  6.4 Decoupling bounds

It will be useful for technical reasons to consider a model where one receives
side information from the scalar additive Gaussian noise channel (6.1) in
addition to the GOE side information. Let us consider the one-block and two-
block posteriors, similarly to (6.13) and (6.16), with this additional scalar
side information. These probabilities are respectively proportional to

$\displaystyle\omega^{\mbox{\rm\tiny SK}}_{B}(\theta)\cdot
e^{H_{B}^{\delta}(\theta)+H_{B}^{\lambda}(\theta)},\mbox{ for }\theta\in
B~{}\mbox{ and }~{}\omega^{\mbox{\rm\tiny SK}}_{B\cup B^{\prime}}(\theta)\cdot
e^{H_{B\cup B^{\prime}}^{\delta}(\theta)+H_{B\cup
B^{\prime}}^{\lambda}(\theta)},\mbox{ for }\theta\in B\cup B^{\prime},$

where $\omega^{\mbox{\rm\tiny SK}}_{B}$ is defined in (6.14) and
$\omega^{\mbox{\rm\tiny SK}}_{B\cup B^{\prime}}$ in (6.17), and
$H_{B}^{\lambda}(\theta)$ and $H_{B\cup B^{\prime}}^{\lambda}(\theta)$ are
defined in (6.4). We state and prove a sequence of technical lemmas which will
be extensively used in the rest of the paper. The starting point is the
following extension of Proposition 6.5:

######  Proposition 6.9.

Let $f_{B}(\delta,\eta,t,\lambda)$ and $f_{B\cup
B^{\prime}}(\delta,\eta,t,\lambda)$ be the free energies of the above
posterior measures (defined similarly to (6.18)). Then for all
$\delta\in[0,1]$, $\eta\geq 0$, $t\in[0,1]$ and $\lambda\geq 0$, $f_{B}$ and
$f_{B\cup B^{\prime}}$ converge to $\phi_{1}$ and $\phi_{2}$, respectively, as
$L^{\circlearrowleft}\to\infty$. Moreover, under Assumption 1, there exists
$\eta_{0}=\eta_{0}(d,\delta)>0$ such that if $\eta\leq\eta_{0}$ then
$\phi_{1}$ and $\phi_{2}$ admit the following variational representations

$\displaystyle\phi_{1}$ $\displaystyle=\sup_{q\geq
0}\Big{\\{}f^{\textup{{sc}}}(\delta;2d\eta q+\lambda)-\frac{d}{2}\eta
q^{2}\Big{\\}},$ (6.21) $\displaystyle\phi_{2}$ $\displaystyle=\sup_{q\geq
0}\Big{\\{}2(1-\alpha)f^{\textup{{sc}}}(\delta;2d\eta q+\lambda)+\alpha
f^{\textup{{sc}}}(\delta;4d\eta q+\lambda)-d\eta q^{2}\Big{\\}}.$ (6.22)

Similarly to previous computations, the vertex- and pair-correlations defined
respectively as

$\varphi_{A}^{\mbox{\rm\tiny v}}:=\frac{1}{|A|}\sum_{x\in
A}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{A}\big{]}^{2}\Big{]}~{}~{}\mbox{and}~{}~{}\varphi_{A}^{\mbox{\rm\tiny
e}}:=\frac{1}{|A|^{2}}\sum_{x,y\in
A}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}^{2}\Big{]},$
(6.23)

where
$Y^{\delta,\eta,\lambda}_{A}=\\{Y^{\delta}_{A},Y^{\eta}_{A},Y^{\lambda}_{A}\\}$
and $A$ is either $B$ or $B\cup B^{\prime}$, have well-defined limits as
$L^{\circlearrowleft}\to\infty$ for all except countably many values of $\eta$
and $\lambda$. Note that the introduction of the scalar side information
breaks the sign symmetry of the random variables $\theta_{x}$ under the
posterior, and the value of the one-point correlation function
$\varphi_{A}^{\mbox{\rm\tiny v}}$ is no longer trivially zero. Furthermore,
these two quantities are related in a simple way in the limit.

######  Lemma 6.10.

Let $A$ be either $B$ or $B\cup B^{\prime}$. Under Assumption 1, for all
$\delta>\delta_{c}$, all except countably many $\eta\geq 0$ and $\lambda\geq
0$, $\varphi_{A}^{\mbox{\rm\tiny v}}$ and $\varphi_{A}^{\mbox{\rm\tiny e}}$
have limits and
$\underset{L^{\circlearrowleft}\to\infty}{\lim}(\varphi_{A}^{\mbox{\rm\tiny
v}})^{2}=\underset{L^{\circlearrowleft}\to\infty}{\lim}\varphi_{A}^{\mbox{\rm\tiny
e}}$.

###### Proof.

We only consider the case $A=B$. The case $A=B\cup B^{\prime}$ can be treated
similarly. Let $\bar{q}^{\bullet}$ be the unique maximizer in (6.21) (see
Lemma 6.4). Convexity in $\lambda$ and $\eta$ imply that
$\varphi_{A}^{\mbox{\rm\tiny v}}$ and $\varphi_{A}^{\mbox{\rm\tiny e}}$
converge to
$2\frac{\mathrm{d}}{\mathrm{d}x_{2}}f^{\textup{{sc}}}(\delta,2d\eta\bar{q}^{\bullet}+\lambda)$,
and $\bar{q}^{\bullet 2}$ respectively (denoting by $x_{2}$ the second
variable of $f^{\textup{{sc}}}$). When $\delta>\delta_{c}$,
$\bar{q}^{\bullet}\geq q_{\star\star}(\delta)>0$. Therefore, by optimality of
$\bar{q}^{\bullet}$ we have

$\frac{\mathrm{d}}{\mathrm{d}x_{2}}f^{\textup{{sc}}}(\delta,2d\eta\bar{q}^{\bullet}+\lambda)=\frac{\bar{q}^{\bullet}}{2},$

and this proves the claim. $\blacksquare$

Next, we exploit information contained in the second derivatives of the free
energies.

######  Lemma 6.11.

Let $A$ be $B$ or $B\cup B^{\prime}$. For almost all $\lambda\geq 0$,

$\lim_{L^{\circlearrowleft}\to\infty}\frac{1}{|A|^{2}}\sum_{x,y\in
A}\operatorname{\mathbb{E}}\Big{[}\Big{(}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{A}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}\Big{)}^{2}\Big{]}=0.$

###### Proof.

Call the quantity in the above display $R$. Taking two derivatives of the free
energy $f_{A}$ with respect to $\lambda$, we obtain

$\frac{\mathrm{d}^{2}}{\mathrm{d}\lambda^{2}}f_{A}=\frac{1}{4|A|}\sum_{x,y\in
A}\operatorname{\mathbb{E}}\Big{[}\Big{(}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{A}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}\Big{)}^{2}\Big{]}=\frac{|A|}{4}R.$

Moreover, the first derivative is uniformly bounded:
$\frac{\mathrm{d}}{\mathrm{d}\lambda}f_{A}\leq\frac{1}{2}$, so
$\int_{0}^{\lambda}\big{(}\frac{\mathrm{d}^{2}}{\mathrm{d}\lambda^{2}}f_{A}\big{)}\mathrm{d}\lambda^{\prime}\leq\frac{\lambda}{2}$.
Therefore $\int_{0}^{\lambda}R\mathrm{d}\lambda^{\prime}\leq 2/|A|\to 0$ as
$L^{\circlearrowleft}\to\infty$. Since $R$ is non-negative, it must converge
to $0$ for almost all values of $\lambda$. $\blacksquare$

Lemmas 6.10 and 6.11 provide averaged forms of decoupling of the variables at
different vertices. Next, we show a form of continuity in $\lambda$ at zero
for the pair correlations:

######  Lemma 6.12.

Let $A$ be $B$ or $B\cup B^{\prime}$. For almost all $\eta\geq 0$,

$\lim_{\lambda\to
0}\lim_{L^{\circlearrowleft}\to\infty}\frac{1}{|A|^{2}}\sum_{x,y\in
A}\operatorname{\mathbb{E}}\Big{[}\Big{(}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{A}\big{]}\Big{)}^{2}\Big{]}=0.$

###### Proof.

Call $R$ the quantity whose double limit is taken in the above display. Since
$Y_{A}^{\delta,\eta,\lambda}$ contains more information than
$Y_{A}^{\delta,\eta}$, we have

$\displaystyle R$ $\displaystyle=\frac{1}{|A|^{2}}\sum_{x,y\in
A}\Big{\\{}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}^{2}\Big{]}-\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{A}\big{]}^{2}\Big{]}\Big{\\}}$
$\displaystyle=\varphi_{A}^{\mbox{\rm\tiny
e}}(\delta,\eta,\lambda)-\varphi_{A}^{\mbox{\rm\tiny e}}(\delta,\eta,0).$

Since $\varphi_{A}^{\mbox{\rm\tiny
e}}=4\frac{\mathrm{d}}{\mathrm{d}\eta}f_{A}$, we have

$\int_{0}^{\eta}R\mathrm{d}\eta^{\prime}\leq
4\big{|}f_{A}(\delta,\eta,t,\lambda)-f_{A}(\delta,\eta,t,0)\big{|}+4\big{|}f_{A}(\delta,0,t,\lambda)-f_{A}(\delta,0,t,0)\big{|}.$

Since $\lambda\mapsto f_{A}(\delta,\eta,t,\lambda)$ is $L$-Lipschitz with
$L=\frac{1}{2}$ uniformly in the other variables (recall that the derivative
is uniformly bounded by $\frac{1}{2}$), we arrive at
$\int_{0}^{\eta}R\mathrm{d}\eta^{\prime}\leq 4\lambda$. Since $R$ is non-
negative and has a limit as $L^{\circlearrowleft}\to\infty$, Fatou’s lemma
implies

$\int_{0}^{\eta}\lim_{L^{\circlearrowleft}\to\infty}R~{}\mathrm{d}\eta^{\prime}\leq
4\lambda.$

Sending $\lambda$ to zero finishes the proof. $\blacksquare$

Finally, we prove another form of decoupling which allows to split
correlations of quadruples of vertices into the product of pair correlations:

######  Lemma 6.13.

Let $A$ be $B$ or $B\cup B^{\prime}$. For all $\lambda\geq 0$ and almost all
$\eta\geq 0$,

$\lim_{L^{\circlearrowleft}\to\infty}\frac{1}{|A|^{4}}\sum_{x,y,w,z\in
A}\operatorname{\mathbb{E}}\Big{[}\Big{(}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}\theta_{w}\theta_{z}|Y^{\delta,\eta,\lambda}_{A}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{w}\theta_{z}|Y^{\delta,\eta,\lambda}_{A}\big{]}\Big{)}^{2}\Big{]}=0.$

###### Proof.

This time we compute the second derivative of $f_{A}$ with respect to $\eta$:

$\frac{\mathrm{d}^{2}}{\mathrm{d}\eta^{2}}f_{A}=\frac{1}{8|A|}\sum_{x,y,w,z\in
A}\operatorname{\mathbb{E}}\Big{[}\Big{(}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}\theta_{w}\theta_{z}|Y^{\delta,\eta,\lambda}_{A}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{A}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{w}\theta_{z}|Y^{\delta,\eta,\lambda}_{A}\big{]}\Big{)}^{2}\Big{]}.$

We conclude in the same way as Lemma 6.11, by noting that the first derivative
$\frac{\mathrm{d}}{\mathrm{d}\eta}f_{A}$ is also uniformly bounded (by
$\frac{1}{4}$). $\blacksquare$

##  7 Analysis of correlations: proof of Theorems 4.3 and 1.3

In this section we prove Theorem 4.3. We first prove items 1. and 2., then we
turn to item 3.

###  7.1 Proof of item 1: analysis of $M_{B}$ and $M_{B^{\bullet}}$

We first show convergence of the expectation of $M_{B}^{2}$. Recall that

$M_{B}=\frac{1}{|B|}\sum_{x\in B}\theta^{B}_{x}\theta_{x},$

where $\big{(}\theta^{B}_{x}\big{)}_{x\in
B}\sim\operatorname{\mathbb{P}}(\cdot|Y_{B})$ is sampled from the one-block
posterior on $B$, with $Y_{B}=\\{Y^{\delta}_{B},Y^{\eta}_{B}\\}$.
($M_{B^{\bullet}}$ is defined similarly.) Then

$\displaystyle\operatorname{\mathbb{E}}[M_{B}^{2}]$
$\displaystyle=\frac{1}{|B|^{2}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\Big{[}\Big{(}\sum_{x\in
B}\theta^{B}_{x}\theta_{x}\Big{)}^{2}\Big{|}Y_{B}\Big{]}\Big{]}$
$\displaystyle=\frac{1}{|B|^{2}}\sum_{x,y\in
B}\operatorname{\mathbb{E}}\big{[}\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B}]^{2}\big{]}$
$\displaystyle=\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B)^{2}\right\rangle_{B}.$

Form Corollary 6.7 and Lemma 6.8 the above converges to
$q_{\star\star}^{2}(\delta)$ for almost all $t\in[0,1]$ as
$L^{\circlearrowleft}\to\infty$ followed by $\eta\to 0$.

Next we show that
$\operatorname{\mathbb{E}}\big{[}(M_{B}-M_{B^{\bullet}})^{2}\big{]}\to 0$.
Recall that $\alpha=\frac{|J|}{|B|}$ where $J$ is a joint, and let
$M_{B\setminus B^{\prime}}:=\frac{1}{|B\setminus B^{\prime}|}\sum_{x\in
B\setminus B^{\prime}}\theta^{B}_{x}\theta_{x}$. We have the two relations

$\displaystyle M_{B}$ $\displaystyle=(1-2\alpha
d)M_{B^{\bullet}}+\alpha\sum_{B^{\prime}\sim B}M_{B\cap B^{\prime}},$
$\displaystyle M_{B\setminus B^{\prime}}$ $\displaystyle=\frac{1-2\alpha
d}{1-\alpha}M_{B^{\bullet}}+\frac{\alpha}{1-\alpha}\sum_{\underset{B^{\prime\prime}\neq
B^{\prime}}{B^{\prime\prime}\sim B}}M_{B\cap B^{\prime\prime}}.$

So

$\displaystyle M_{B}-M_{B^{\bullet}}$
$\displaystyle=\alpha\sum_{B^{\prime}\sim B}(M_{B\cap
B^{\prime}}-M_{B^{\bullet}}),$ $\displaystyle
M_{B}-\frac{1}{2d}\sum_{B^{\prime}\sim B}M_{B\setminus B^{\prime}}$
$\displaystyle=\frac{\alpha(1-2\alpha d)}{2d(1-\alpha)}\sum_{B^{\prime}\sim
B}(M_{B}-M_{B\cap B^{\prime}}).$

Therefore

$\displaystyle\operatorname{\mathbb{E}}\big{[}(M_{B}-M_{B^{\bullet}})^{2}\big{]}$
$\displaystyle=\alpha^{2}\operatorname{\mathbb{E}}\Big{[}\big{(}\sum_{B^{\prime}\sim
B}(M_{B\cap B^{\prime}}-M_{B^{\bullet}}\big{)}^{2}\Big{]}$
$\displaystyle=c(d,\alpha)\operatorname{\mathbb{E}}\Big{[}\big{(}M_{B}-\frac{1}{2d}\sum_{B^{\prime}\sim
B}M_{B\setminus B^{\prime}}\big{)}^{2}\Big{]}$
$\displaystyle\leq\frac{c(d,\alpha)}{2d}\sum_{B^{\prime}\sim
B}\operatorname{\mathbb{E}}\big{[}(M_{B}-M_{B\setminus
B^{\prime}})^{2}\big{]}.$

Proposition 6.6 implies that the above converges to zero for almost all
$t\in[0,1]$ and all $\eta<\eta_{0}$.

Next, we show that $M_{B}^{2}$ has vanishing variance.We have

$\displaystyle\operatorname{var}(M_{B}^{2})$
$\displaystyle=\operatorname{\mathbb{E}}[M_{B}^{4}]-\operatorname{\mathbb{E}}[M_{B}^{2}]^{2}$
$\displaystyle=\frac{1}{|B|^{4}}\sum_{x,y,z,w\in
B}\operatorname{\mathbb{E}}\big{[}\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}\theta_{z}\theta_{w}|Y_{B}]^{2}\big{]}-\operatorname{\mathbb{E}}[M_{B}^{2}]^{2}.$

The second term in the above display converges to
$q_{\star\star}^{4}(\delta)$. It remains to study the fourth moment
$\operatorname{\mathbb{E}}[M_{B}^{4}]$. Using the decoupling Lemma 6.13, we
have

$\frac{1}{|B|^{4}}\sum_{x,y,z,w\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}\theta_{z}\theta_{w}|Y^{\delta,\eta}_{B}]^{2}\big{]}=\frac{1}{|B|^{4}}\sum_{x,y,z,w\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{B}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{z}\theta_{w}|Y^{\delta,\eta}_{B}\big{]}^{2}\Big{]}+o_{L^{\circlearrowleft}}(1),$

where $o_{L^{\circlearrowleft}}(1)\to 0$ for almost every $\eta>0$ as
$L^{\circlearrowleft}\to\infty$. Now we introduce side information from the
scalar additive Gaussian noise channel (6.1) using Lemma 6.12 (with $A=B$):

$\displaystyle\frac{1}{|B|^{4}}$ $\displaystyle\sum_{x,y,z,w\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{B}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{z}\theta_{w}|Y^{\delta,\eta}_{B}\big{]}^{2}\Big{]}$
$\displaystyle=\frac{1}{|B|^{4}}\sum_{x,y,z,w\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{z}\theta_{w}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}+\mbox{error},$

where $\mbox{error}\to 0$ for almost every $\eta>0$ as
$L^{\circlearrowleft}\to\infty$ then $\lambda\to 0$. Using Lemma 6.11, we have

$\displaystyle\frac{1}{|B|^{4}}\sum_{x,y,z,w\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{B}]^{2}\operatorname{\mathbb{E}}[\theta_{z}\theta_{w}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}$
$\displaystyle=\frac{1}{|B|^{4}}\sum_{x,y,z,w\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{y}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{z}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{w}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}+\mbox{error}$
$\displaystyle=\operatorname{\mathbb{E}}\left[\Big{(}\frac{1}{|B|}\sum_{x\in
B}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{)}^{4}\right]+\mbox{error},$

where $\mbox{error}\to 0$ for almost every $\lambda>0$ as
$L^{\circlearrowleft}\to\infty$. Let $X:=\frac{1}{|B|}\sum_{x\in
B}\operatorname{\mathbb{E}}[\theta_{x}|Y^{\delta,\eta,\lambda}_{B}]^{2}$. The
main term in the above display is $\operatorname{\mathbb{E}}[X^{4}]$. We will
compare it to $\operatorname{\mathbb{E}}[X^{2}]^{2}$: since $X\in[0,1]$ almost
surely, we have

$\operatorname{var}(X^{2})=\frac{1}{2}\operatorname{\mathbb{E}}[(X^{2}-X^{\prime
2})^{2}]\leq
2\operatorname{\mathbb{E}}[(X-X^{\prime})^{2}]=4\operatorname{var}(X).$

(Here, $X^{\prime}$ is an independent copy of $X$.) Moreover,

$\displaystyle\operatorname{var}(X)$
$\displaystyle=\frac{1}{|B|^{2}}\sum_{x,y\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{y}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}-\operatorname{\mathbb{E}}\Big{[}\frac{1}{|B|}\sum_{x\in
B}\operatorname{\mathbb{E}}\Big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}^{2}$
$\displaystyle=\frac{1}{|B|^{2}}\sum_{x,y\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}-\operatorname{\mathbb{E}}\Big{[}\frac{1}{|B|}\sum_{x\in
B}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}^{2}+\mbox{error}$
$\displaystyle=\varphi_{B}^{\mbox{\rm\tiny
e}}(\delta,\eta,\lambda)-\varphi_{B}^{\mbox{\rm\tiny
v}}(\delta,\eta,\lambda)^{2}+\mbox{error}.$

Lemma 6.12 implies $\mbox{error}\to 0$ for almost every $\eta>0$ as
$L^{\circlearrowleft}\to\infty$ then $\lambda\to 0$. Moreover, from Lemma
6.10, we have $\varphi_{B}^{\mbox{\rm\tiny
e}}(\delta,\eta,\lambda)-\varphi_{B}^{\mbox{\rm\tiny
v}}(\delta,\eta,\lambda)^{2}\to 0$ as $L^{\circlearrowleft}\to\infty$. Thus,
we have shown that for almost every $\eta>0$,

$\lim_{\lambda\to
0}\lim_{L^{\circlearrowleft}\to\infty}\operatorname{var}(X^{2})=0.$

Now, since Lemma 6.11 implies

$\operatorname{\mathbb{E}}[X^{2}]=\operatorname{\mathbb{E}}\Big{[}\Big{(}\frac{1}{|B|}\sum_{x\in
B}\operatorname{\mathbb{E}}\big{[}\theta_{x}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{)}^{2}\Big{]}=\frac{1}{|B|^{2}}\sum_{x,y\in
B}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta,\lambda}_{B}\big{]}^{2}\Big{]}+\mbox{error},$

the above tends to $q_{\star\star}^{2}(\delta)$ as
$L^{\circlearrowleft}\to\infty$ then $\lambda\to 0$, and then $\eta\to 0$. We
conclude that $\lim_{\eta\to
0}\lim_{L^{\circlearrowleft}\to\infty}\operatorname{var}(M_{B}^{2})=0$.

###  7.2 Proof of item 2: analysis of $W_{B,B^{\prime}}$

We proceed analogously. Recall that

$W_{B,B^{\prime}}=\frac{1}{|B\cap B^{\prime}|}\sum_{x\in B\cap
B^{\prime}}\theta^{B}_{x}\theta^{B^{\prime}}_{x},$

where $\big{(}\theta^{B}_{x}\big{)}_{x\in
B}\sim\operatorname{\mathbb{P}}(\cdot|Y_{B})$ and
$\big{(}\theta^{B^{\prime}}_{x}\big{)}_{x\in
B^{\prime}}\sim\operatorname{\mathbb{P}}(\cdot|Y_{B^{\prime}})$ independently.
Therefore

$\displaystyle\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{2}]$
$\displaystyle=\frac{1}{|B\cap
B^{\prime}|^{2}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\Big{[}\Big{(}\sum_{x\in
B\cap
B^{\prime}}\theta^{B}_{x}\theta^{B^{\prime}}_{x}\Big{)}^{2}\Big{|}Y_{B},Y_{B^{\prime}}\Big{]}\Big{]}$
$\displaystyle=\frac{1}{|B\cap B^{\prime}|^{2}}\sum_{x,y\in B\cap
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B^{\prime}}\big{]}\Big{]}.$

We will use overlap locking (Proposition 6.6) to replace the conditional
expectations $\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B}]$ and
$\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B^{\prime}}]$ in the above
expression by $\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}]$ where $Y_{B\cup B^{\prime}}=\\{Y_{B},Y_{B^{\prime}}\\}$ is the
union of $Y_{B}$ and $Y_{B^{\prime}}$. Now, let $(\theta^{B\cup
B^{\prime}}_{x})_{x\in B\cup
B^{\prime}}\sim\operatorname{\mathbb{P}}(\cdot|Y_{B\cup B^{\prime}})$ be drawn
from the two-block posterior conditionally independently from everything else,
and let

$\tilde{M}_{B\cap B^{\prime}}:=\frac{1}{|B\cap B^{\prime}|}\sum_{x\in B\cap
B^{\prime}}\theta_{x}^{B\cup B^{\prime}}\theta_{x}.$

First we have

$\operatorname{\mathbb{E}}[\tilde{M}_{B\cap B^{\prime}}^{2}]=\frac{1}{|B\cap
B^{\prime}|^{2}}\sum_{x,y\in B\cap
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}=\operatorname{\mathbb{E}}\left\langle
R_{1,2}(B\cap B^{\prime})^{2}\right\rangle_{B\cup B^{\prime}}.$ (7.1)

Second, we since all variables are bounded, a simple triangle inequality
implies

$\displaystyle\Big{|}\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{2}]-\operatorname{\mathbb{E}}[\tilde{M}_{B\cap
B^{\prime}}^{2}]\Big{|}$ $\displaystyle\leq\frac{1}{|B\cap
B^{\prime}|^{2}}\sum_{x,y\in B\cap
B^{\prime}}\Big{\\{}\operatorname{\mathbb{E}}\Big{[}\Big{|}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}\Big{|}\Big{]}$ $\displaystyle\hskip
99.58464pt+\operatorname{\mathbb{E}}\Big{[}\Big{|}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B^{\prime}}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}\Big{|}\Big{]}\Big{\\}}.$

We use Jensen’s inequality and the fact that $B$ and $B^{\prime}$ play
symmetric roles to write

$\displaystyle\leq\frac{2}{|B\cap B^{\prime}|^{2}}\sum_{x,y\in B\cap
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\Big{(}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B}\big{]}-\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}\Big{)}^{2}\Big{]}^{1/2}$
$\displaystyle\leq\Big{(}\frac{4}{|B\cap B^{\prime}|^{2}}\sum_{x,y\in B\cap
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\Big{(}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B}\big{]}-\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}\Big{)}^{2}\Big{]}\Big{)}^{1/2}.$

Since $Y_{B}\subset Y_{B\cup B^{\prime}}$, using iterated expectations, we see
that

$\operatorname{\mathbb{E}}\big{[}\big{(}\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B}]-\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}]\big{)}^{2}\big{]}=\operatorname{\mathbb{E}}\big{[}\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}]^{2}\big{]}-\operatorname{\mathbb{E}}\big{[}\operatorname{\mathbb{E}}[\theta_{x}\theta_{y}|Y_{B}]^{2}\big{]}.$

It follows that

$\Big{|}\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{2}]-\operatorname{\mathbb{E}}[\tilde{M}_{B\cap
B^{\prime}}^{2}]\Big{|}\leq
2\Big{(}\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cap
B^{\prime})^{2}\big{\rangle}_{B\cup
B^{\prime}}-\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cap
B^{\prime})^{2}\big{\rangle}_{B}\Big{)}^{1/2}.$ (7.2)

By virtue of Proposition 6.6, we have on the one hand, $R_{1,2}(B\cap
B^{\prime})$ and $R_{1,2}(B)$ lock together under the one-block posterior on
$B$, and on the other hand, $R_{1,2}(B\cap B^{\prime})$ and $R_{1,2}(B\cup
B^{\prime})$ lock together under the two-block posterior. More precisely, for
almost all $t\in[0,1]$ and all $\eta\in[0,\eta_{0}]$, it holds

$\displaystyle\Big{|}\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cap
B^{\prime})^{2}\big{\rangle}_{B}-\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B)^{2}\big{\rangle}_{B}\Big{|}\xrightarrow[L^{\circlearrowleft}\to\infty]{}0,~{}~{}~{}~{}\mbox{and}~{}~{}$
$\displaystyle\Big{|}\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cap
B^{\prime})^{2}\big{\rangle}_{B\cup
B^{\prime}}-\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cup
B^{\prime})^{2}\big{\rangle}_{B\cup
B^{\prime}}\Big{|}\xrightarrow[L^{\circlearrowleft}\to\infty]{}0.$

Furthermore, we know that
$\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B)^{2}\big{\rangle}_{B}\to{q^{\bullet}_{1}}^{2}(\delta,\eta)$
and $\operatorname{\mathbb{E}}\big{\langle}R_{1,2}(B\cup
B^{\prime})^{2}\big{\rangle}_{B\cup
B^{\prime}}\to{q^{\bullet}_{2}}^{2}(\delta,\eta)$ from Corollary 6.7 for all
except countably many $\eta\in[0,\eta_{0}]$. Now from Lemma 6.8,
$q^{\bullet}_{1}-q^{\bullet}_{2}\to 0$ as $\eta\to 0$. We deduce from this and
the bound (7.2) that for almost every $t\in[0,1]$,

$\lim_{\eta\to
0}\lim_{L^{\circlearrowleft}\to\infty}\Big{|}\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{2}]-\operatorname{\mathbb{E}}[\tilde{M}_{B\cap
B^{\prime}}^{2}]\Big{|}=0,$

and Eq.(7.1) implies

$\lim_{\eta\to
0}\lim_{L^{\circlearrowleft}\to\infty}\operatorname{\mathbb{E}}[\tilde{M}_{B\cap
B^{\prime}}^{2}]=\lim_{\eta\to
0}{q^{\bullet}_{2}}^{2}(\delta,\eta)=q_{\star\star}^{2}(\delta).$

This establishes the first claim of item 2.

As for the variance, it suffices to consider the fourth moment of
$W_{B,B^{\prime}}$. We proceed similarly to the case of $M_{B}$:

$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{4}]=\frac{1}{|B\cap
B^{\prime}|^{4}}\sum_{x,y,z,w\in B\cap
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\big{[}\theta_{x}\theta_{y}\theta_{z}\theta_{w}|Y^{\delta,\eta}_{B}\big{]}\cdot\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}\theta_{z}\theta_{w}|Y^{\delta,\eta}_{B^{\prime}}\big{]}\Big{]}.$

We use Lemma 6.13 (applied with $A=B$ then $A=B^{\prime}$) to decouple the
pairs $x,y$ and $w,z$:

$\displaystyle\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{4}]=$
$\displaystyle\frac{1}{|B\cap B^{\prime}|^{4}}\sum_{x,y,z,w\in B\cap
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{B}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y^{\delta,\eta}_{B^{\prime}}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{z}\theta_{w}|Y^{\delta,\eta}_{B}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{z}\theta_{w}|Y^{\delta,\eta}_{B^{\prime}}\big{]}\Big{]}+o_{L^{\circlearrowleft}}(1),$

where $o_{L^{\circlearrowleft}}(1)\to 0$ as $L^{\circlearrowleft}\to\infty$
for almost every $\eta$. Now we repeat the argument used in the analysis of
$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}^{2}]$ to argue that the above is

$\frac{1}{|B\cup B^{\prime}|^{4}}\sum_{x,y,z,w\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}^{2}\operatorname{\mathbb{E}}\big{[}\theta_{z}\theta_{w}|Y_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}+\mbox{error},$

where $\mbox{error}\to 0$ as $L^{\circlearrowleft}\to\infty$ then $\eta\to 0$,
and $Y_{B\cup B^{\prime}}=\\{Y_{B},Y_{B^{\prime}}\\}$ is as defined above. We
use Proposition 6.13 to merge the pairs $x,y$ and $w,z$. The above becomes

$\frac{1}{|B\cup B^{\prime}|^{4}}\sum_{x,y,z,w\in B\cup
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}\theta_{z}\theta_{w}|Y_{B\cup
B^{\prime}}\big{]}^{2}\Big{]}+\mbox{error}.$

The main term in the above display is equal to
$\operatorname{\mathbb{E}}[M_{B\cup B^{\prime}}^{4}]$. Here the same analysis
used for $\operatorname{\mathbb{E}}[M_{B}^{4}]$ in the previous subsection
applies as well. Therefore $\operatorname{\mathbb{E}}[M_{B\cup
B^{\prime}}^{4}]$ converges to $q_{\star\star}^{4}(\delta)$. We conclude that
$\operatorname{var}(W_{B,B^{\prime}}^{2})\to 0$.

###  7.3 Proof of item 3: analysis of $W_{B,B^{\prime}}M_{B}M_{B^{\prime}}$

We first perform a preliminary computation and then sketch the argument, which
we then execute in three steps. Let $Y_{B\cup
B^{\prime}}=\\{Y_{B},Y_{B^{\prime}}\\}$ where as in the analysis of
$\operatorname{\mathbb{E}}[M_{B}^{2}]$, we use the short-hand
$Y_{B}=\\{Y^{\delta}_{B},Y^{\eta}_{B}\\}$. Then

$\displaystyle{|B|\cdot|B^{\prime}|\cdot|B\cap B^{\prime}|}$
$\displaystyle\cdot\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]$
$\displaystyle=\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\Big{[}\Big{(}\sum_{x\in
B\cap
B^{\prime}}\theta^{B}_{x}\theta^{B^{\prime}}_{x}\Big{)}\cdot\Big{(}\sum_{y\in
B}\theta^{B}_{y}\theta_{y}\Big{)}\cdot\Big{(}\sum_{z\in
B^{\prime}}\theta^{B^{\prime}}_{z}\theta_{z}\Big{)}~{}\Big{|}~{}Y_{B\cup
B^{\prime}}\Big{]}\Big{]}$ $\displaystyle=\sum_{x\in B\cap
B^{\prime}}\sum_{y\in B}\sum_{z\in
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta^{B}_{x}\theta^{B^{\prime}}_{x}\theta^{B}_{y}\theta_{y}\theta^{B^{\prime}}_{z}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}\Big{]}$ $\displaystyle=\sum_{x\in B\cap
B^{\prime}}\sum_{y\in B}\sum_{z\in
B^{\prime}}\operatorname{\mathbb{E}}\Big{[}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{z}|Y_{B^{\prime}}\big{]}\operatorname{\mathbb{E}}\big{[}\theta_{y}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}\Big{]}.$ (7.3)

In this case the strategy is to replace the conditional expectations
$\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B}\big{]}$ and
$\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{z}|Y_{B^{\prime}}\big{]}$
in the right-hand side with
$\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]}$ and
$\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{z}|Y_{B\cup
B^{\prime}}\big{]}$ respectively. Once we succeed at this operation,
$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]$ is
approximated by the quantity

$\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{]}.$

Notice that the above sum is over different subsets of $B\cup B^{\prime}$. We
then exploit the fact that local overlaps lock under the two-block posterior
to replace the above with a homogenous sum over all vertices of $B\cup
B^{\prime}$:

$\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{]}.$

We remark that this is the trace of the third power of a certain matrix
$\chi$, which we call _susceptibility matrix_ of the block $B\cup B^{\prime}$,
defined by

$\chi_{x,y}:=\frac{1}{|B\cup
B^{\prime}|}\operatorname{\mathbb{E}}\big{[}\theta_{x}\theta_{y}|Y_{B\cup
B^{\prime}}\big{]},~{}~{}~{}x,y\in B\cup B^{\prime}.$ (7.4)

We will then argue that $\chi$ is approximately a _rank-one_ matrix, in the
sense that its Frobenius and operator norms are equal in the limit
$L^{\circlearrowleft}\to\infty$ then $\eta\to 0$, with common asymptotic value
$q_{\star\star}(\delta)$. Since $\operatorname{trace}(\chi^{3})^{1/3}$ is
sandwiched between the operator and Frobenius norms, a concentration argument
finally yields that
$\operatorname{\mathbb{E}}[W_{B,B^{\prime}}M_{B}M_{B^{\prime}}]$ converges to
$q_{\star\star}^{3}(\delta)$.

#### Step 1: replacing the conditional expectations.

The first step is to replace $Y_{B}$ and $Y_{B^{\prime}}$ by $Y_{B\cup
B^{\prime}}$ in the conditional expectations in (7.3). Since $Y_{B}\subset
Y_{B\cup B^{\prime}}$, we have

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

Overlap locking under both the one-block and two-block posteriors, as given in
Proposition 6.6, implies that the above is equal to

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