$\Delta_{\mathbf{Q}}=\mathbf{Q}-\mathbf{Q}^{\rm CW}$, and
$\langle\cdot,\cdot\rangle_{\rm TR}$ denote the matrix trace norm.

Thereafter it is enough to show that

$\exp\left(-\beta\langle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(\hat{\Sigma}),\mathbf{Q}^{\rm CW}-\mathbf{Q}^{\rm
ER}\rangle_{\rm TR}\right)=O(1)$

with high probability. This part is similar to above and is only easier since
one can simply compute mean and variance of
$\langle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(\hat{\Sigma}),\mathbf{Q}^{\rm CW}-\mathbf{Q}^{\rm
ER}\rangle_{\rm TR}$ to conclude by Chebyshev’s Inequality. In particular,

$\displaystyle\langle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(\hat{\Sigma}),\mathbf{Q}^{\rm CW}-\mathbf{Q}^{\rm
ER}\rangle_{\rm TR}$ $\displaystyle=\xi(S,S)\sum_{(i,j)\in S\times
S}\Delta_{i,j}+2\xi(S,S^{c})\sum_{(i,j)\in S\times
S^{c}}\Delta_{i,j}+\xi(S^{c},S^{c})\sum_{(i,j)\in S^{c}\times
S^{c}}\Delta_{i,j}$

where
$\Delta_{i,j}=\frac{1}{\tilde{d}}\left(G_{i,j}-\frac{\tilde{d}}{n}\right)$ and
$\xi(S,S),\xi(S,S^{c}),\xi(S^{c},S^{c})$ stand for the common values (by the
exchangeability in the Curie-Weiss Model) of
$\\{\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(X_{i}X_{j})$, for $(i,j)\in S\times S\\}$,
$(i,j)\in S\times S^{c}\\}$ and $(i,j)\in S^{c}\times S^{c}\\}$ respectively.
Since the $\xi^{\prime}s$ are bounded by $1$ in absolute value, the proof of
the fact that $\langle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(\hat{\Sigma}),\mathbf{Q}^{\rm CW}-\mathbf{Q}^{\rm
ER}\rangle_{\rm TR}$ has bounded variance then follows from Lemma 9. This
concludes the proof of this lemma. ∎

######  Lemma 9.

Let $G$ be the adjacency matrix of either the graph $G(n,p)$ (with
$p=\Theta(1)$) or random regular graph on $n$ vertices each having degree
$d=\Theta(n)$. For any two subsets $S_{1},S_{2}\subset\\{1,\ldots,n\\}$, with
$\min\\{|S_{1}|,|S_{2}|\\}\rightarrow\infty$,
$\Psi=\Psi(S_{1},S_{2}):=\frac{1}{\sqrt{|S_{1}||S_{2}|}}\sum_{i,j\in
S_{1}\times S_{2}}(G_{ij}-\mathbb{E}(G_{ij}))=O_{\mathbb{P}}(1)$, where
$\mathbb{E}(G_{ij})$ is $p$ or $d/n$ respectively.

###### Proof.

If $G$ is the adjacency matrix of either the graph $G(n,p)$, $G_{ij}$, $i\leq
j$ are independent and the conclusion is immediate using Chebyshev’s
inequality.

When $G$ is the adjacency matrix of random regular graph, for any
$i,j,j^{\prime}\in[n]$, $Cov(G_{ij},G_{ij^{\prime}})$ are same by symmetry and
will be denoted by $c_{1}$. Similarly, for $i\neq i^{\prime}$,
$Cov(G_{ij},G_{i^{\prime}j^{\prime}})$ will be same and will denote by
$c_{2}$. For any $i\in[n]$, $\sum_{j}G_{ij}=d$. Hence,
$Var(\sum_{j}G_{ij})=0$. So,

$n^{2}c_{1}\geq 0=\sum_{j}\mathrm{Var}(G_{ij})+2\sum_{j\neq
j^{\prime}}\mathrm{Cov}(G_{ij},G_{ij^{\prime}})\leq n+n^{2}c_{1},$

implying $c_{1}=O(1/n)$. Similarly, $\mathrm{Var}(\sum_{i,j}G_{ij})=0$ and
number of tuples ${(i,j),(i^{\prime},j^{\prime})}$, $i\neq i^{\prime}$ are
$\Theta(n^{4})$ and $i=i^{\prime}$ are $\Theta(n^{3})$. So,

$0=\sum_{i,j}\mathrm{Var}(G_{ij})+\Theta(n^{3})c_{1}+\Theta(n^{4})c_{2},$

implying $c_{2}=O(1/n^{2})$. Next, we use the covariance estimates to prove
the Lemma.

To this end, note that $\mathbb{E}(\Psi)=0$. Also,

$\displaystyle\mathrm{Var}(\Psi)=\frac{1}{|S_{1}||S_{2}|}\Big{(}\sum_{i,j\in
S_{1}\times
S_{2}}\mathrm{Var}(G_{ij})+(|S_{1}||S_{2}|^{2}+|S_{2}||S_{1}|^{2})c_{1}+|S_{1}|^{2}|S_{2}|^{2}c_{2}\Big{)}=O(1),$

proving $\Psi=O_{\mathbb{P}}(1)$, as desired. ∎

######  Lemma 10.

Suppose $\mathbf{X}\sim\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ with
$\mathbf{Q}$ be either scaled adjecency matrix of of the graph $G(n,p)$ (with
$p=\Theta(1)$) or random regular graph on $n$ vertices each having degree
$d=\Theta(n)$. Let $Z_{S}=\sum_{i\in S}X_{i}/\sqrt{s}$. Define
$t_{n}(\delta):=\sqrt{2(1+\delta)(1-m^{2})\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$
for some $\delta>0$, where $m:=m(\beta)$ is the unique positive root of
$m=\tanh(\beta m)$.

  1. (a)

If $\beta<1,s\ll\frac{n}{\log n}$, $\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(Z_{S}>t_{n}(\delta))\leq(1+o(1))\frac{C_{u}}{C_{l}}e^{-t^{2}_{n}(\delta)}$,
w.h.p. where $C_{u},C_{l}$ are defined as Lemma 8.

  2. (b)

If $\beta=1,s\ll\frac{\sqrt{n}}{\log n}$, then same conclusion as (a) holds.

###### Proof.

  1. (a)

Pick $\lambda>0$ such that
$\tanh\left(\frac{\lambda}{\sqrt{s}}\right)=\frac{t_{n}(\delta)}{\sqrt{s}}$.
So, $\lambda\geq t_{n}(\delta)$, and
$\cosh\left(\frac{\lambda}{\sqrt{s}}\right)=\left(1-\frac{t^{2}_{n}(\delta)}{s}\right)^{-1/2}.$
Also,
$s\tanh\left(\frac{\lambda}{\sqrt{s}}\right)=\sqrt{st_{n}(\delta)}=O(\sqrt{s\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|})\ll\sqrt{n}$.
Hence,

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(Z_{S}>t_{n}(\delta)$
$\displaystyle\leq e^{-\lambda
t_{n}(\delta)}\frac{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(\frac{\lambda}{\sqrt{s}}))}{Z(\beta,\mathbf{Q},\mathbf{0})}\leq\frac{C_{u}}{C_{l}}e^{-\lambda
t_{n}(\delta)}\frac{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(\frac{\lambda}{\sqrt{s}}))}{Z(\beta,\mathbf{Q}^{\rm
CW},\mathbf{0})}$ $\displaystyle=(1+o(1))\frac{C_{u}}{C_{l}}e^{-\lambda
t_{n}(\delta)}\cosh^{s}\left(\frac{\lambda}{\sqrt{s}}\right)\leq(1+o(1))\frac{C_{u}}{C_{l}}e^{-t^{2}_{n}(\delta)}$

w.h.p., where the second inequality is due to Lemma 8 and the equality is due
to Lemma 2.

  2. (b)

When $\beta=1$, we pick same $\lambda$. Now,
$s\tanh\left(\frac{\lambda}{\sqrt{s}}\right)\ll n^{1/4}$ and the bound is
obtained using Lemma 8 and Lemma 2 again and the $o(1)$ term does not depend
on the choice of $S$.

∎

###  6.5. Proofs in Section 3

We shall prove Theorems 5 and 6 here. However, to do so we will need some
technical preparations.

####  6.5.1. Technical Preparations

We begin with the general idea behind the proof of Theorem 5. The crux of the
proof of Theorem 5 is a coupling argument between the finite volume and
infinite volume measures and then exploiting the various correlation decay
results of the infinite volume limit which is already known. Let us denote by
$\mathbb{P}^{\rm{bc}}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}$, the
infinite volume limit of $\mathbb{P}^{\rm
bc}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}$ for
$\rm{bc}\in\\{\mathsf{f},+\\}$. It is known that these limits exist and in
fact it is also known that there exists a constant $c=c(\beta,d)$ such that
for all $j\in\mathbb{Z}^{d}$,

$0\leq\mathrm{Cov}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}(X_{0},X_{j})\leq
e^{-c\|j\|}$ (48)

where $\rm bc\in\\{\mathsf{f},+\\}$ if $\beta<\beta_{c}$ and $\rm bc=+$ if
$\beta>\beta_{c}$ and $\|\cdot\|$ is the $L^{1}$ norm in $\mathbb{Z}^{d}$. The
first inequality is known as the GKS inequality (see the lecture notes [27])
and the second inequality is proved in [2, 21] for $\beta<\beta_{c}$ and in
[23] for $\beta>\beta_{c}$. From now on, we assume that

$\text{if }\beta<\beta_{c},\rm bc\in\\{\mathsf{f},+\\}\text{ and if
}\beta>\beta_{c},\rm bc=+.$

Note that (48) justifies the existence of the following constant for all
$\beta\neq\beta_{c}$:

$\chi^{\rm bc}=\chi^{\rm
bc}(\beta,d):=\sum_{j\in\mathbb{Z}^{d}}\mathrm{Cov}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}(X_{0},X_{j})\in(0,\infty)$
(49)

In fact for $\beta<\beta_{c}$, since the infinite volume limits for $+$ and
$\mathsf{f}$ coincide,
$\chi^{\mathsf{f}}(\beta,d)=\chi^{\mathsf{+}}(\beta,d)$. From now on, we will
drop the superscript $\rm bc$ from $\chi^{\rm bc}$ and the boundary condition
should be clear from context from the temperature of the model.

The constant $\chi(\beta,d)$ is known as the _susceptibility_ of the Ising
model. We quickly mention here that $\chi(\beta_{c}(d),d)=\infty$ ([46, 3]).
We first state an easy consequence of (49).

######  Lemma 11.

Pick $S\in\mathcal{C}_{s,\rm rect}$ with volume $s$. Fix $\beta\neq\beta_{c}$
and $\text{if }\beta<\beta_{c},\rm bc\in\\{\mathsf{f},+\\}\text{ and if
}\beta>\beta_{c},\rm bc=+.$ Then

$\lim_{s\to\infty}\frac{1}{s}{\mathrm{Var}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}}\left(\sum_{i\in
S}X_{i}\right)=\chi$

###### Proof.

Exponential decay of covariance implies that for any vertex $i\in S$ which is
at $L^{1}$ distance at least $k$ from the boundary of $S$,

$|\sum_{j\in S}{\mathrm{Cov}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}}(X_{i},X_{j})-\chi|\leq
e^{-ck}.$

for some constant $c=c(d)$. Let $S^{\prime}\subset S$ denote the set of
vertices at a distance at least $m$ from the boundary of $S$ where $1\ll m\ll
s^{1/d}$ and let $s^{\prime}$ denote the number of vertices in $S^{\prime}$.
Note that for this choice of $m$, $(s-s^{\prime})/s\to 0$. Thus summing the
above estimate over all vertices $i\in S^{\prime}$, we find that

$|\sum_{i\in S^{\prime}}\sum_{j\in S}{\mathrm{Cov}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}}(X_{i},X_{j})-s^{\prime}\chi|=s^{\prime}e^{-cm}$
(50)

We trivially bound the remaining term,

$\sum_{i\in S\setminus S^{\prime}}\sum_{j\in S}{\mathrm{Cov}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}}(X_{i},X_{j})\leq\chi(s-s^{\prime})$
(51)

simply using the fact that the covariance is always nonnegative (first
inequality of (48)). Combining (50) and (51), we get

$\displaystyle\left|\frac{1}{s}{\mathrm{Var}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}}\left(\sum_{i\in
S}X_{i}\right)-\chi\right|$ $\displaystyle\leq\left|\frac{1}{s}\sum_{i\in
S^{\prime}}\sum_{j\in S}{\mathrm{Cov}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}}(X_{i},X_{j})-\frac{s^{\prime}}{s}\chi\right|$
$\displaystyle+\frac{1}{s}\left|\sum_{i\in S\setminus S^{\prime}}\sum_{j\in
S}{\mathrm{Cov}^{\rm
bc}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}}(X_{i},X_{j})\right|+\chi\left|\frac{s^{\prime}}{s}-1\right|$
$\displaystyle\leq\frac{s^{\prime}}{s}e^{-cm}+\frac{2}{s}(s-s^{\prime})\chi$

By the choice of $m$, both terms above converge to 0, thereby completing the
proof. ∎

To prove Theorem 5, we need a finite volume version of Lemma 11. The key idea
we use here is a coupling argument. To that end, let us define the FK-Ising
model on $\mathbb{Z}^{d}$ and the celebrated _Edward-Sokal coupling_ between
the Ising model and the FK-Ising model.

Let $G=(V,E)$ be a finite graph. The FK-Ising measure is a probability measure
on $\\{0,1\\}^{E}$ defined as follows

$\phi_{G,p}(\omega)=p^{|\\{e:\omega_{e}=1\\}|}(1-p)^{|\\{e:\omega_{e}=0\\}|}2^{k(\omega)}\qquad\omega\in\\{0,1\\}^{E}.$
(52)

where $k(\omega)$ denotes the number of connected components of $\omega$
(where we think of $\omega$ as the graph $(V,\\{e:\omega_{e}=1\\})$). Similar
to Ising, it is well known (see e.g. [30]) that $\phi_{\Lambda_{n,d},p}$
converges to an infinite volume limit which is called the _free_ FK-Ising
measure and we denote it by $\phi^{\mathsf{f}}_{\mathbb{Z}^{d},p}$. We also
need to consider a _wired_ FK-Ising which corresponds to taking a limit of
$\phi_{\Lambda^{\mathsf{w}}_{n,d},p}$ where $\Lambda^{\mathsf{w}}_{n,d}$
formed by identifying all the vertices in
$\mathbb{Z}^{d}\setminus\Lambda_{n,d}$ into a single vertex and erasing all
the self loops. It is also well known (cf. [30]) that this limit exists. We
denote the infinite volume wired FK-Ising model by
$\phi^{\mathsf{w}}_{\mathbb{Z}^{d},p}$. We mention that for $p\neq
p_{c}=1-e^{-2\beta_{c}}$,
$\phi^{\mathsf{w}}_{\mathbb{Z}^{d},p}=\phi^{\mathsf{f}}_{\mathbb{Z}^{d},p}$
and furthermore for $p>p_{c}$, there exists a unique connected component
almost surely in a sample from FK-Ising (free or wired).

Let $E^{\prime}$ be a subset of the edges of $G$ and let $H$ be the subgraph
of $G$ formed by the edges not in $E^{\prime}$ and the vertices incident to
them. For any element $\xi\in\\{0,1\\}^{E^{\prime}}$, let $\phi^{\xi}_{H,p}$
denote the FK-Ising measure on $H$ conditioned on $\xi$. We say
$\xi\preceq\xi^{\prime}$ if $\xi(e)\leq\xi^{\prime}(e)$ for all $e\in
E^{\prime}$. There is another way to view boundary conditions when the edge
set we are conditioning on is the complement of a box. For $k<n$, let
$\Lambda_{k,n,d}:=\Lambda_{n,d}\setminus\Lambda_{k,d}$ and let
$E(\Lambda_{k,n,d})$ denote the edge set induced by its vertices. Given
$\xi\in\\{0,1\\}^{E(\Lambda_{k,n,d})}$ we can consider a partition $[\xi]$ of
$\partial\Lambda_{k,d}$ with $i,j$ being in the same partition class if they
belong in the same component of $\xi$. It is easy to see that the conditional
law $\phi^{\xi}_{\Lambda_{k,d},p}$ is completely described by $[\xi]$, and
this property is known as the _domain Markov property_ of the FK-Ising.
Observe that the free boundary condition corresponds to the partition where
every vertex is in its own class, while the wired boundary condition
corresponds to the partition where every boundary vertex is in the same class.

We now state a crucial monotonicity property of FK-Ising.

######  Lemma 12 (Monotonicity, [20]).

Consider any subgraph $H=(V(H),E(H))$ of a finite graph $G$ and consider
$\phi_{H,p}^{\xi}$ on $H$ with boundary condition
$\xi\in\\{0,1\\}^{E(G)\setminus E(H)}$ and parameter $p\in[0,1]$. Let
$\\{i\stackrel{{\scriptstyle H}}{{\leftrightarrow}}j\\}$ denotes the event
that $i,j$ are connected with edges in the random subgraph of $H$ obtained
from the open edges in $\phi_{H,p}^{\xi}$. Fix $i,j\in V(H)$ and suppose
$\xi_{1}\preceq\xi_{2}$ be any two boundary conditions. Then

$\phi_{H,p}^{\xi_{1}}(i\stackrel{{\scriptstyle
H}}{{\leftrightarrow}}j)\leq\phi_{H,p}^{\xi_{2}}(i\stackrel{{\scriptstyle
H}}{{\leftrightarrow}}j).$ (53)

A simple consequence of Lemma 12 is the existence of free and wired limits of
FK-Ising as asserted earlier.

A crucial connection between the the Ising model and the FK-Ising model is
given by the so called Edwards-Sokal coupling which we now describe. We refer
to [30, Theorem 4.91] for a proof.

######  Theorem 9 (Edwards-Sokal coupling).

Let $G$ be a finite graph and let $p=1-e^{-2\beta}$. Then there exists a
coupling between $\mathbb{P}_{\beta,G,\mathbf{0}}$ and $\phi_{G,p}$ such that
the following holds. Suppose $(\omega,\sigma)$ is sampled from the coupling
where $\omega\sim\phi_{G,p}$ and $\sigma\sim\mathbb{P}_{\beta,G,\mathbf{0}}$.
Then $\sigma$ can be sampled by first sampling $\omega$, and then for each
connected component of $\omega$ assign the same value in $\\{+1,-1\\}$ on all
its vertices by tossing independent, unbiased coins. The same coupling holds
between $\phi^{\mathsf{f}}_{\mathbb{Z}^{d},p}$ and
$\mathbb{P}^{\mathsf{f}}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}$.

Finally, the same coupling holds between $\phi_{\Lambda^{\mathsf{w}}_{n,d},p}$
(resp. $\phi^{\mathsf{w}}_{\mathbb{Z}^{d},p}$) and
$\mathbb{P}^{+}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\bm{0}}$ (resp.
$\mathbb{P}^{+}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\bm{0}}$) with only one
modification: the component containing the boundary vertex (resp. the a.s.
unique infinite component) is assigned a value $+1$ deterministically.

We now write a lemma which establishes a strong mixing property of FK-Ising at
all but critical temperature.

######  Lemma 13.

Fix $n,d,p$ and suppose $S$ is a rectangle of volume $s$ which is at least at
$L^{1}$ distance $m$ from the boundary of $\Lambda_{n,d}$.

Fix $p<p_{c}$ and ${\rm bc}\in\\{\mathsf{f},\mathsf{w}\\}$. There exists a
coupling $\Phi^{\rm bc}_{n,d,p}$ between $\phi^{\rm bc}_{\Lambda_{n,d},p}$ and
$\phi^{\rm bc}_{\mathbb{Z}^{d},p}$ such that the following holds with
probability at least $1-{n^{d}}\exp(-cm)$. Let $(\omega^{\rm
bc}_{n},\omega^{\rm bc})$ be sampled from this coupling with $\omega^{\rm
bc}_{n}\sim\phi^{\rm bc}_{\Lambda_{n,d},p}$ and $\omega^{\rm bc}\sim\phi^{\rm
bc}_{\mathbb{Z}^{d},p}$. Then

  * •

$\omega^{\rm bc}$ restricted to edges of $S$ is the same as that of
$\omega^{\rm bc}_{n}$ restricted to $S$

  * •

If $i$ and $j$ in $S$ are connected in $\omega^{\rm bc}$ if and only if they
are connected in $\omega^{\rm bc}_{n}$.

For $p>p_{c}$, a coupling $\Phi^{\mathsf{w}}_{n,d,p}$ holds between
$\phi_{\Lambda^{\mathsf{w}}_{n,d},p}$ and
$\phi^{\mathsf{w}}_{\mathbb{Z}^{d},p}$ where with probability at least
$1-{n^{d}}\exp(-cm)$ in addition to the above two items, the following item
holds. Let $(\omega^{\mathsf{w}}_{n},\omega^{\mathsf{w}})$ be sampled from
this coupling with
$\omega^{\mathsf{w}}_{n}\sim\phi_{\Lambda^{\mathsf{w}}_{n,d},p}$ and
$\omega^{\mathsf{w}}\sim\phi^{\mathsf{w}}_{\mathbb{Z}^{d},p}$

  * •

$i\in S$ is in the infinite cluster of $\omega^{\mathsf{w}}$ if and only if
$i$ is in the boundary cluster of $\omega^{\mathsf{w}}_{n}$.

###### Proof.

Free case. Let us first consider the free case. We will show that we can
couple $\omega_{n}^{\mathsf{f}}\sim\phi^{\mathsf{f}}_{\Lambda_{n,d},p}$ and
$\omega_{n}^{\mathsf{w}}\sim\phi^{\mathsf{w}}_{\Lambda_{n,d},p}$ with the
required properties. We claim that this is enough to prove the lemma. Indeed
by the domain Markov property and the monotonicity of FK-Ising, for any
boundary condition described by the partitioning $[\xi]$, the conditional law
of $\omega^{\xi}\sim\phi^{\xi}_{\Lambda_{n,d},p}$ on $\Lambda_{n,d}$ is
sandwiched between that of the wired and the free measures. Therefore if the
coupling between $\omega_{n}^{\mathsf{f}},\omega_{n}^{\mathsf{w}}$ satisfy
both items, then both pairs $(\omega^{\xi},\omega_{n}^{\mathsf{w}})$ and
$(\omega^{\xi},\omega_{n}^{\mathsf{f}})$ satisfy both the items.

The coupling is done in a Markovian way which exposes the ‘boundary cluster’.
Initially all the edges of the box is ‘unexplored’ and the set of ‘explored’
edges $E_{0}=\emptyset$. Let
$\xi^{\mathsf{w}}_{k},\xi^{\mathsf{f}}_{k}\in\\{0,1\\}^{E_{k}}$ be the
configurations revealed at step $k$ and assume
$\xi^{\mathsf{f}}_{k}\preceq\xi^{\mathsf{w}}_{k}$. In step $k+1$ we find an
unexplored edge $e$ incident to either a boundary vertex or a vertex connected
to the boundary vertex through a path in $E_{k}$ all of whose edges are open
in $\xi^{\mathsf{w}}_{k}$. We stop if there is no such edge $e$. Otherwise, we
reveal the status of $e$ according to the conditional law of
$\omega_{n}^{\mathsf{f}}$ and $\omega_{n}^{\mathsf{w}}$ given
$\xi^{\mathsf{f}}_{k},\xi^{\mathsf{w}}_{k}$ respectively. Furthermore we do so
in such a way that $\xi^{\mathsf{f}}_{k+1}\preceq\xi^{\mathsf{w}}_{k+1}$.
Indeed this is possible because of the monotonicity (Lemma 12). Suppose the
exploration stops at a (random) step $T$. Notice that by description of the
coupling, when we stop, all the explored edges incident to the boundary
vertices of every component of unexplored edges have $\xi^{\mathsf{w}}$ value
0. By monotonicity of the coupling, all these edges have $\xi^{\mathsf{f}}$
value 0 as well. In other words, the boundary condition of the unexplored
region is the same for the conditional law of
$\omega_{n}^{\mathsf{f}},\omega_{n}^{\mathsf{w}}$ given $\xi^{\mathsf{f}}_{T}$
and $\xi^{\mathsf{w}}_{T}$ respectively (in particular, it is a free boundary
FK-Ising in the respective regions). We thus can and will sample both
$\omega_{n}^{\mathsf{f}},\omega_{n}^{\mathsf{w}}$ in the unexplored region to
be the same according to this common conditional law.

Clearly from the description of the coupling it is enough to show that we stop
before reaching any edge incident to a vertex in $S$ with probability at least
$1-{n^{d}}\exp(-cm)$. This follows from [22, Theorem 1.2] since on the
complement of this event, one of the vertices between distance $m/4$ and $m/2$
from the boundary of $\partial\Lambda_{n}$ must be connected to the boundary
of $\partial\Lambda_{n}$ in $\omega_{n}^{\mathsf{w}}$. There is a small
subtlety here regarding the location of this vertex being not at the center of
the box. We skip the details here see [41, Section 5.5.1] for more details on
how this technicality can be handled. Overall, this event has probability at
most $V_{m}\exp(-cm)$ by a union bound, where $V_{m}$ is the number of
vertices in the said distance range from the boundary. Trivially upper
bounding $V_{m}$ by $n^{d}$, we are done.

Wired case. Let us now prove the wired case. The idea is similar to the free
case, except we need to do one step of renormalization using Pisztora’s coarse
graining approach and then crucially use the result of [23]. Again we argue
that it is enough to show the coupling between
$\omega_{n}^{\mathsf{w}}\sim\phi_{\Lambda^{\mathsf{w}}_{n,d},p}$ and
$\omega_{n}^{\mathsf{f}}\sim\phi_{\Lambda_{n,d},p}$ satisfying the first two
items. Observe that by domination, the only way a vertex $i\in S$ is a
boundary cluster for $\omega_{n}^{\mathsf{w}}$ but is not in an infinite
cluster of $\omega^{\mathsf{w}}$ is if it is in a finite cluster of diameter
at least $m$. The probability of this happening for any $i\in S$ is
$O(|S|e^{-cm})$ by [30, Theorem (5.104)] when combined with the result of
[12]. Thus the third item is satisfied so we concentrate on the first two.

For $x\in k\mathbb{Z}^{d}$ define $\Lambda_{k,d}(x)$ to be the box
$\Lambda_{k,d}+x$, and let $\mathcal{B}_{k}$ denote the set of boxes of this
form. For $\omega\in\\{0,1\\}^{E(\Lambda_{n,d})}$ we say a box
$\Lambda_{k}(x)\subset\Lambda_{n,d}$ is good if

  * •

there exists a cluster in $\omega$ restricted to $\Lambda_{k}(x)$ touching all
its sides (this is called the _crossing cluster_ of the box), and,

  * •

every path of length at least $k/2$ intersects the above cluster.

We use the following result from [44, 12]: there exists a $c>0$ such that for
all $k\geq 1$,

$\sup_{\xi}\phi^{\xi}_{\Lambda_{2k,d},p}(\Lambda_{k}\text{ is good})\geq
1-e^{-ck}.$ (54)

It also follows from [23, Proposition 1.4] that for all $\varepsilon>0$ we can
choose $k_{0}$ large so that for all $k>k_{0}$

$\sum_{e\in
E(\Lambda_{k})}(\phi^{\mathsf{w}}_{\Lambda_{2k,d},p}(\omega_{e}=1)-\phi^{\mathsf{f}}_{\Lambda_{2k,d},p}(\omega_{e}=0))<\varepsilon.$
(55)

An immediate consequence of (54) and (55) and Holley’s criterion (see [30,
Theorems 2.1 and 2.3]) is that for any coupling between
$\omega_{n}^{\mathsf{w}}$ and $\omega^{\mathsf{f}}$ the set of blocks $B$ for
which $\omega_{n}^{\mathsf{w}}|_{B}=\omega_{n}^{\mathsf{f}}|_{B}$ and $B$ is
good dominates a 5-dependant Bernoulli site percolation $\eta$ on the lattice
$k\mathbb{Z}^{d}$ the with parameter $1-2\varepsilon$ for large enough $k$.
Using the main theorem of [39], we know that $\eta$ dominates an i.i.d.
Bernoulli percolation with parameter $\tilde{\varepsilon}(\varepsilon)$ which
tends to 0 as $\varepsilon\to 0$.

We now use the Markovian coupling similar to [23, Lemma 3.3] or [41, Lemma
5.2], we provide a brief sketch here. We assume $k$ is fixed but large as
described in the previous paragraph and divides $n$ without loss of
generality. We start with a set of explored boxes which are all the elements
of $\mathcal{B}_{k}$ with centers in the boundary of $\Lambda_{n+k}$ and a set
of unexplored boxes which consist of all the elements of $\mathcal{B}_{k}$
intersecting them. In each step $t$ we pick an unexplored box $B$ and sample
$\omega_{n}^{\mathsf{w}}|_{B\setminus
C_{t}},\omega_{n}^{\mathsf{f}}|_{B\setminus C_{t}}$ where $C_{t}$ is the set
of explored boxes at step $t$. We also maintain
$\omega_{n}^{\mathsf{w}}|_{B\setminus
C_{t}}\preceq\omega_{n}^{\xi}|_{B\setminus C_{t}}$ in this sampling which is
possible by monotonicity (Lemma 12). If actually
$\omega_{n}^{\mathsf{w}}|_{B\setminus
C_{t}}=\omega_{n}^{\mathsf{f}}|_{B\setminus C_{t}}$ and $B$ is good, then we
declare the box explored and add nothing to the set of unexplored boxes.
Otherwise, we add the set of boxes in $\mathcal{B}_{k}$ intersecting $B$ to
the set of unexplored boxes.

Let $T$ be the (stopping) time when the set of unexplored boxes is empty. It
can be easily checked that if at step $T$ the set of unexplored boxes is
empty, the conditional law of $\omega_{n}^{\mathsf{w}}|_{\Lambda_{n}\setminus
C_{T}}$ is the same as that of $\omega_{n}^{\mathsf{f}}|_{\Lambda_{n}\setminus
C_{T}}$. This follows from the definition of good boxes: if two vertices on
the boundary of ${\Lambda_{n}\setminus C_{T}}$ belong to different clusters
$K,K^{\prime}$ in one and in the same cluster of the other, the clusters
$K,K^{\prime}$ must exit their respective boxes in $C_{T}$. However by
definition of a good box, this means that the clusters must be the same as the
crossing clusters in the good boxes. On the other hand, it is easy to see that
the crossing clusters in adjacent boxes actually belong to the same cluster.
Inducting this argument, we can conclude that $K,K^{\prime}$ are actually the
same cluster leading to a contradiction. We refer to [23, Lemma 3.3] for
details of this fact. Overall, this allows us to sample
$\omega_{n}^{\mathsf{w}}|_{\Lambda_{n}\setminus
C_{T}}=\omega_{n}^{\xi}|_{\Lambda_{n}\setminus C_{T}}$. Furthermore if $C_{T}$
comes within distance $m/2$ of $S$, then the Bernoulli
$(1-\tilde{\varepsilon})$ site percolation it dominates must also have a path
of 0 of length at least $\frac{m}{2k}$ from the boundary. This has probability
at most $n^{d-1}\exp(-cm)$ by a union bound and standard properties of
Bernoulli percolation (see [29]).

It remains to show that this coupling satisfies the three items on the event
$C_{T}$ does not intersect $S$. Indeed the first item is clearly satisfied.
The second item is also satisfied again because of the definition of good
boxes. Recall that we already argued how to handle the final item, thereby
finishing the proof. ∎

######  Corollary 1.

Fix $n,d,p$ and suppose $S$ is a rectangle of volume $s$ which is at least at
$L^{1}$ distance $m$ from the boundary of $\Lambda_{n,d}$. For any
$\beta<\beta_{c}$, there exists a coupling $\Psi$ between
$\mathbb{P}^{\rm{f}}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\bf 0}$ and
$\mathbb{P}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\bf 0}$ such that if
$(X_{i},Y_{j})_{i\in\Lambda_{n,d},j\in\mathbb{Z}^{d}}$ be a sample from this
coupling with
$(X_{i})_{i\in\Lambda_{n,d}}\sim\mathbb{P}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\bf
0}$ and
$(Y_{i})_{i\in\mathbb{Z}^{d}}\sim\mathbb{P}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\bf
0}$ then with probability at least $1-n^{d}e^{-cm}$, $X_{i}=Y_{i}$ for all
$i\in S$. A coupling with the same properties holds between
$\mathbb{P}^{+}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\bf 0}$ and
$\mathbb{P}^{+}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\bf 0}$

For $\beta>\beta_{c}$, a coupling with the same properties holds between
$\mathbb{P}^{+}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\bf 0}$ and
$\mathbb{P}^{+}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\bf 0}$

###### Proof.

This follows by combining Lemma 13 and Theorem 9. Let us first consider the
free case. Suppose $(\omega_{n},\omega)$ is sampled from the coupling
described in Lemma 13 for the free case. Suppose we are on the event that the
two items described in Lemma 13 are satisfied. Now for every $i\in S$ we
sample the sign of the cluster containing $i$ in $\omega_{n}$ and $\omega$ by
tossing the same unbiased coin. Note that this is well defined since by the
property of the coupling, $i,j$ are connected in $\omega_{n}$ if and only if
it is connected in $\omega$. In the complement of the event described in Lemma
13 sample the signs independently. This completes the description of the
coupling which clearly satisfies the required claim.

The proof for the wired case is exactly the same except the boundary cluster
of $\omega_{n}$ and the infinite cluster of $\omega$ are always assigned $+1$
in the coupling. ∎

With this we are now finally ready to prove Theorem 5.

####  6.5.2. Proof of Theorem 5

We prove the free case only as the proof of the wired case is exactly the same
and for notational simplicity we also drop the superscript $\mathsf{f}$ from
the proof.

Let
$(X_{i})_{i\in\Lambda_{n,d}}\sim\mathbb{P}^{\rm{f}}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\bf
0}$ and
$(Y_{i})_{i\in\mathbb{Z}^{d}}\sim\mathbb{P}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\bf
0}$ coupled together as in Corollary 1. We write $\mathrm{Var},\mathrm{Cov}$
to denote the variance and covariance under this coupling measure. Let
$\mathcal{G}$ be the event that $X_{i}=Y_{i}$ for all $i\in S$ and recall that
by the coupling, $\mathcal{G}$ has probability at least $1-n^{d}\exp(-cm)$
which converges to 1 super polynomially fast by the choice of $m$. We break up
the variance as follows

$\displaystyle{\mathrm{Var}}\left(\sum_{i\in S}Y_{i}\right)$
$\displaystyle={\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}(1_{\mathcal{G}}+1_{\mathcal{G}^{c}})\right)$ (56)
$\displaystyle=\left({\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}}\right)+{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}^{c}}\right)+2{\mathrm{Cov}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}},\sum_{i\in S}Y_{i}1_{\mathcal{G}^{c}}\right)\right)$
(57)

By definition of $\mathcal{G}$,

${\mathrm{Var}}\left(\sum_{i\in
S}X_{i}1_{\mathcal{G}}\right)={\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}}\right).$ (58)

Now notice

$\displaystyle\left|{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}\right)-{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}}\right)\right|\leq{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}^{c}}\right)+2\left|{\mathrm{Cov}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}},\sum_{i\in S}Y_{i}1_{\mathcal{G}^{c}}\right)\right|$
(59)

and observe,

${\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}^{c}}\right)\leq\mathbb{E}\left(\left(\sum_{i\in
S}Y_{i}\right)^{2}1_{\mathcal{G}^{c}}\right)\leq
s^{2}n^{d}e^{-cm};\quad{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}}\right)\leq\mathbb{E}\left(\left(\sum_{i\in
S}Y_{i}\right)^{2}1_{\mathcal{G}}\right)\leq s^{2}.$ (60)

where we used the exponential bound on the probability of $\mathcal{G}^{c}$
and the trivial pointwise bound $|\sum_{i\in S}Y_{i}|\leq s$. Using
Cauchy–Schwarz inequality to bound the covariance term in (59), we obtain

$\left|{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}\right)-{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}1_{\mathcal{G}}\right)\right|\leq
s^{2}n^{d}e^{-cm}+2s^{2}n^{d/2}e^{-cm/2}$ (61)

Clearly, both inequalities of (60) is also true if we replace $Y$ by $X$.
Using this and (58), we can conclude

$\left|{\mathrm{Var}}\left(\sum_{i\in
S}X_{i}\right)-{\mathrm{Var}}\left(\sum_{i\in
S}X_{i}1_{\mathcal{G}}\right)\right|\leq
s^{2}n^{d}e^{-cm}+2s^{2}n^{d/2}e^{-cm/2}$

Combining this with (58) and (61) and using the triangle inequality, we obtain

$\left|\frac{1}{s}{\mathrm{Var}}\left(\sum_{i\in
S}X_{i}\right)-\frac{1}{s}{\mathrm{Var}}\left(\sum_{i\in
S}Y_{i}\right)\right|\leq 2sn^{d}e^{-cm}+4sn^{d/2}e^{-cm/2}.$

The right hand side converges to 0 by the choice of $m$. Combining the above
with Lemma 11, the proof is complete

####  6.5.3. Proof of Theorem 6

We prove the upper bound first. The proof is the same for both $\rm bc=+$ or
$\rm bc=\mathsf{f}$ so we drop it from the superscript and also write
$\chi=\chi(\beta)$ to simplify notations. Also, throughout the proof, we will
use $\mathbf{Q}$ instead of $\mathbf{Q}(\Lambda_{n,d})$ to simplify notations.

For two vectors $\mathbf{a}=(a_{1},\ldots,a_{d})$ and
$\mathbf{b}=(b_{1},\ldots,b_{d})$ in $\mathbb{R}^{d}$, we say
$\mathbf{b}\succeq\mathbf{a}$ if $b_{j}\geq a_{j}$, $j\in[d]$. For two such
vectors, we also denote by
$\text{Rect}(\mathbf{a},\mathbf{b})=\prod_{j=1}^{d}[a_{j},b_{j}]$ the
rectangle with endpoints $\mathbf{a}$ and $\mathbf{b}$ and by
$\text{Vol}(\text{Rect}(\mathbf{a},\mathbf{b}))=\prod_{j=1}^{d}(b_{j}-a_{j})$
its volume. Let $\text{Rect}(\mathbf{a})$ denote
$\text{Rect}(\mathbf{a},\mathbf{b})$ when $b_{j}-a_{j}=\lceil s^{1/d}\rceil$,
$\forall j\in[d]$. Now, define a sequence $\eta_{n}>0$ such that,

  1. (1)

$\eta_{n}\rightarrow 0$,

  2. (2)

$s^{1/d}\eta_{n}\rightarrow\infty$,

  3. (3)

$|\log(\eta_{n})|=o(\log(n/s))$.

Define $t_{0}=t_{0}(\eta_{n}):=\\{-n^{1/d}+(j-1)\eta_{n}s^{1/d},1\leq
j\leq(2n/s)^{1/d}\\}$. Finally, set
$\mathcal{C}_{s}=\mathcal{C}_{s}(\eta_{n}):=\\{\text{Rect}(\mathbf{a}):a_{i}\in
t_{0},i\in[d]\\}$. Note that $|\mathcal{C}_{s}|=(1+o(1))(2n/s)\eta^{d}_{n}$.

Recall that for a set $S$, $Z_{S}=\frac{1}{\sqrt{s}}\sum_{i\in S}X_{i}$ and
$Z_{\max}=\max_{S\in\mathcal{C}_{s}}Z_{S}$. Take $\delta>0$, our test is given
by $T_{n}(\delta)=\mathbf{1}\\{Z_{\max}>t_{n}(\delta)\\}$ where
$t_{n}(\delta):=\sqrt{2(1+\delta)\chi\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$.
Choose $\lambda=t_{n}(\delta)/\chi$. Then,

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(Z_{S}\geq
t_{n}(\delta)\right)$ $\displaystyle\leq e^{-\lambda
t_{n}(\delta)}\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}\left(\exp(\frac{\lambda}{\sqrt{s}}\sum_{i\in
S}X_{i})\right)$ $\displaystyle=\exp\left(-\lambda
t_{n}(\delta)+\frac{\lambda^{2}}{2s}\mathrm{Var}\Big{(}\sum_{i\in
S}X_{i}\Big{)}+O\Big{(}\frac{\lambda^{3}}{s}\Big{)}\right)$
$\displaystyle=\exp\left(-(1+o(1)+\delta)\log(n/s)\right),$

where the equalities are due to [40, Equation 25] and Theorem 5. By our
assumption of $\eta_{n}$,

$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}(\delta))\leq|\mathcal{C}_{s}|\max_{S\in\mathcal{C}_{s}}\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(Z_{S}\geq
t\right)=o(1),$

implying that the type 1 error of our test converges to $0$.

For the type II error, consider $S^{\star}$ be the subset with signal $A$ with
$\tanh(A)=\sqrt{\frac{2}{\chi}(1+\varepsilon)\frac{\log(n/s)}{s}}$ for some
small $\varepsilon>0$. Since $s\gg(\log n)^{d}$ and $\eta_{n}\rightarrow 0$,
we can obtain a set $S\in\mathcal{C}_{s}$ such that $|S\cap
S^{\star}|=(1+o(1))s$. It is enough to show

$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(A)}(Z_{S}\leq
t_{n}(\delta))\rightarrow 0.$

Since
$(Z_{S}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(A)}(Z_{S}))=O_{p}(1)$,
it is enough to show
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(A)}(\sum_{i\in
S}X_{i})\rightarrow-\infty$.

######  Lemma 14.

$\mathbb{E}_{S^{*}}(\sum_{i\in{S^{\star}}}X_{i})=sA\chi(1+o(1)).$ (62)

###### Proof.

Define $f(\nu):=\log
Z_{n}(\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(\nu))$.

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(A)}(\sum_{i\in{S^{\star}}}X_{i})$
$\displaystyle=\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(A)}(\sum_{i\in{S^{\star}}}X_{i})-\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i\in{S^{\star}}}X_{i})$
$\displaystyle=\frac{\partial}{\partial\eta}f(\nu)|_{\nu=A}-\frac{\partial}{\partial\eta}f(\nu)|_{\nu=0}$
$\displaystyle=Af^{{}^{\prime\prime}}(0)+O(A^{2}f^{{}^{\prime\prime\prime}}(\tilde{\nu})).$

Since $f^{{}^{\prime\prime}}(0)=s\chi$ and
$f^{{}^{\prime\prime\prime}}(\tilde{\nu})=O(s)$ (by [40, Lemma 5]), we have
$A^{2}f^{{}^{\prime\prime\prime}}(\tilde{\nu})=o(As)$ obtaining the result. ∎

Finally recall that
$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(A)}(X_{i})=O(A)$.
This, along with Lemma 14 yields
$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S^{\star}}(A)}(X_{S})=sA\chi(1+o(1))$
concluding the proof for small $\varepsilon>0$. To prove the lower bound, we
define a sub-collection $\tilde{\mathcal{C}}$ of rectangles as follows:
Throughout we assume that $s^{1/d}$ and $n^{1/d}$ are integers for notational
convenience, otherwise we work with corresponding ceiling functions. We will
assume without loss of generality that $3s^{1/d}$ divides $n^{1/d}$. First,
let $\widehat{C_{n}}$ be the class of disjoint sub-cubes of $\Lambda_{n,d}$
obtained by translating along each axis (by $3s^{1/d}$ in each direction each
time) the cube of side lengths $3s^{1/d}$ from the bottom left corner of
$\Lambda_{n,d}$. Consequently, subdivide each cube in $\widehat{C_{n}}$ into
$3^{d}$ cubes of side length $s^{1/d}$ each and take the center sub-cube of
each cube in $\widehat{C_{n}}$ to be elements of our class
$\tilde{\mathcal{C}}$. It is easy to see that
$|\tilde{\mathcal{C}}|=|\widehat{C_{n}}|=(2/3)^{d}\frac{n}{s}$. Further,
$\min_{i\in S_{1},j\in S_{2},S_{1}\neq
S_{2}\in\tilde{\mathcal{C}}}\|i-j\|_{1}\geq 4s^{1/d}$. We choose a prior $\pi$
as uniform distribution over $\mu_{S}(A)$, $S\in\tilde{\mathcal{C}}$.

Fix $\varepsilon>0$ small and set
$\tanh(A)=\sqrt{\frac{2}{\chi}(1-\varepsilon)\frac{\log(n/s)}{s}}$. Using the
prior $\pi$, we obtain the likelihood ratio:

$\displaystyle
L_{\pi}=\frac{1}{|\tilde{\mathcal{C}}|}\sum_{S\in\tilde{\mathcal{C}}}\frac{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))}{Z(\beta,\mathbf{Q},\mathbf{0})}\exp\left(A\sum_{i\in
S}X_{i}\right).$

Define $\tilde{t}_{n}(\delta)=\sqrt{2(1+\delta)\log|\\\
\tilde{\mathcal{C}}|}$. Subsequently, we let

$\displaystyle\tilde{L}_{\pi}(\delta):=\frac{1}{|\tilde{\mathcal{C}}|}\sum_{S\in\tilde{\mathcal{C}}}\frac{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))}{Z(\beta,\mathbf{Q},\mathbf{0})}\exp\left(A\sum_{i\in
S}X_{i}\right)\mathbf{1}(Z_{S}\leq\tilde{t}_{n}(\delta)).$ (63)

Since
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(L_{\pi}\neq\tilde{L}_{\pi}(\delta))\rightarrow
0$ similar to the proof of type-I error convergence in the upper bound, it is
enough to show $\tilde{L}_{\pi}(\delta)\rightarrow 1$ in probability. To this
end, note that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\tilde{L}_{\pi}(\delta))=\frac{1}{|\tilde{\mathcal{C}}|}\sum_{S\in\tilde{\mathcal{C}}}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}\left(\frac{1}{\sqrt{s}}\sum_{i\in
S}X_{i}\leq\tilde{t}_{n}(\delta)\right).$

Observe that, $\frac{1}{\sqrt{s}}\sum_{i\in
S}(X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)})$ is tight
since $\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}(\sum_{i\in
S}X_{i})\leq\mathrm{Var}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i\in
S}X_{i})=O(s)$ by G.H.S inequality and Theorem 5. Also, by arguments similar
to the control of Type II error in the proof of upper bound, we have that for
any $\delta>0$ that
$\tilde{t}_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}(\sum_{i\in
S}X_{i})\rightarrow\infty$ uniformly in $S\in\tilde{\mathcal{C}}_{s}$.
Therefore by Chebyshev’s Inequality we conclude that
$1-\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\tilde{L}_{\pi}(\delta))\rightarrow
0$.

To upper bound second moment $\tilde{L}_{\pi}$, we split
$\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\tilde{L}^{2}_{\pi}(\delta))$ into
sum of $T_{1}$ and $T_{2}$ as (19). Note that, $T_{2}\leq 1+o(1)$ using [18,
Equation 11]. Recall that,

$T_{1}=\frac{1}{|\tilde{\mathcal{C}}|}\frac{Z^{2}(\beta,\mathbf{Q},\mathbf{0})Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A))}{Z^{2}(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))Z(\beta,\mathbf{Q},\mathbf{0})}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A)}(Z_{S}\leq\tilde{t}_{n}(\delta)).$
(64)

For $k>0$,

$\displaystyle\frac{Z_{n}(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(kA))}{Z_{n}(\beta,\mathbf{Q},\mathbf{0})}$
$\displaystyle=\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\exp(kA\sum_{i\in
S}X_{i}))$
$\displaystyle=\exp(\frac{k^{2}A^{2}}{2}s\chi(1+o(1))+o(\log(n/s)))$
$\displaystyle=\exp(k^{2}(1-\varepsilon+o(1))\log(n/s)).$

Also,

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A)}\left(Z_{S}\leq\tilde{t}_{n}(\delta)\right)$
$\displaystyle\leq
e^{\lambda\tilde{t}_{n}(\delta)}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A)}(\exp(-\lambda
Z_{S}))=e^{\lambda\tilde{t}_{n}(\delta)}\frac{Z_{n}(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A-\frac{\lambda}{\sqrt{s}}))}{Z_{n}(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A))}.$
(65)

and hence the probability is upper bounded by $\exp(-(1+\tau)\log(n/s))$ for
some small $\tau>0$. Hence,

$T_{1}\leq\exp(\\{-(1+o(1))+(2-2\varepsilon)-(1+\tau)\\}\log(n/s)),$

where the first summand is obtained from count of rectangle, second summand
from three ratio of two partition functions, third from (65). Hence,
$T_{1}\rightarrow 0$ and we obtain the desired conclusion.

###  6.6. Proof of Theorem 8

Following Lemma 19, we will use maximum pseudo-likelihood estimator for
$\mathbf{0}$ magnetization and it is still consistent as long as the set of
positive magnetization $S$ satisfies $|S|=o(n)$, since

$\liminf_{n\rightarrow\infty}\frac{1}{n}\log\frac{1}{2^{n}}Z(\beta,\mathbf{Q},\mathbf{0})>0,$
(66)

using [11, equation (7.9)] for any $\beta>0$. When $\rm bc=\mathsf{f}$, we set
$O(s^{1/d})=o(n)$ many vertices as $+1$ and still the conclusion of Lemma 19
holds. Once we obtain such an estimator $\hat{\beta}_{n}$ of $\beta$, we can
consistently estimate the cutoff of our scan test since susceptibility of the
Ising model is a continuous function of $\beta$ away from criticality.

####  6.6.1. Proof of Proposition 7

Define

$\chi_{n}(\beta):=\sum_{j\in\Lambda_{n,d}}\mathrm{Cov}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0},X_{j})=\sum_{j\in\Lambda_{n,d}}\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0}X_{j})$
(67)

A consequence of Lemma 12 and Theorem 9 is that
$\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0}X_{j})$ is non-
decreasing in $\beta$ for $\beta\geq 0$. We obtain the following by
straightforward calculation:

$\frac{d}{d\beta}\chi_{n}(\beta)=\sum_{j,k,l\in\Lambda_{n,d}}\big{(}\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0}X_{j}X_{k}X_{l})-\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0}X_{j})\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{k}X_{l})\big{)}$

To show that the quantity on the right hand side above is strictly positive
for $\beta\in(0,\beta_{c})$ 555It is easy to come up with examples where the
quantity is 0 but the system is not something trivial like i.i.d. we invoke
the following identity (see [19, Section 3])

$\big{(}\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0}X_{j}X_{k}X_{l})-\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0}X_{j})\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{k}X_{l})\big{)}\\\
=\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{0}X_{j}X_{k}X_{l})\mathbf{P}_{\beta,n,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}(k\not\leftrightarrow
l).$ (68)

Here $\mathbf{P}_{\beta,n,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}$
denotes the _double random current probability measure_ where one current has
no source and one current has sources $\\{0,j\\}\Delta\\{k,l\\}$. We refer to
[19] for details on this model.

It remains to take a limit as $n\to\infty$. It is a consequence of the
existence of the limit of correlations of the free Ising model that the
infinite volume limit of
$P_{\beta,n,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}$ exists ([19]). Call
this limit $P_{\beta,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}$. To
justify that the limit can be inserted inside the sum, we invoke a result of
[36] and sharpness of phase transition ([22, 2]) and obtain that for all
$\beta<\beta_{c}$, $\chi(\beta)$ is differentiable and

$\frac{d}{d\beta}\chi(\beta)=\lim_{n\to\infty}\frac{d}{d\beta}(\chi_{n}(\beta))=\sum_{j,k,l\in\mathbb{Z}^{d}}\mathbb{E}_{\beta,\mathbf{Q}(\mathbb{Z}^{d}),\mathbf{0}}(X_{0}X_{j}X_{k}X_{l})\mathbf{P}_{\beta,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}(k\not\leftrightarrow
l)$ (69)

Therefore all we need to show is that the sum in the right hand side is
strictly positive. To prove this we assume familiarity with the random current
model for which we refer the reader to [19]. Take $0,j,k,l$ to be the
consecutive corners of a square (or a plaquette) in $\mathbb{Z}^{d}$. We need
the following property of the random current model which is a version of the
finite energy property. Take any event $\mathcal{A}$ with
$P_{\beta,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}(\mathcal{A})>0$.
Introduce a map $\psi$ which takes an element of $\mathcal{A}$ and adds and
removes a finite number of some odd or even edges, keeping the source set to
be the same. There exists a constant $c>0$ such that
$P_{\beta,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}(\psi(\mathcal{A}))\geq
cP_{\beta,d}^{\emptyset\otimes\\{0,j\\}\Delta\\{k,l\\}}(\mathcal{A})$. Now
take $\mathcal{A}$ to be $k\leftrightarrow l$. Remove both odd or even edges
so that all the edges incident to $0,j,k,l$ are closed in both the currents.
This operation possibly introduces some sources in
$\mathbb{Z}^{d}\setminus\\{0,j,k,l\\}$. Next we add some odd edges none of
which intersect $\\{0,j,k,l\\}$ so that there are no sources in each current
(for example, one can add odd paths between the sources). Next we add an odd
edge between $\\{0,l\\}$ and between $\\{k,j\\}$. This finishes the mapping,
which clearly maps to a subset of $\\{k\not\leftrightarrow l\\}$. The proof is
complete by the finite energy property mentioned above.

###  6.7. General Technical Lemmas

In this section we collect the lemmas which have been used in the proofs of
results in both Sections 2 and 3.

######  Lemma 15 (GHS Inequality [37]).

Suppose $X\sim\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ with $\beta>0$,
$\mathbf{Q}_{ij}\geq 0$ for all $i,j\in[n]$ and
$\boldsymbol{\mu}\in\left(\mathbb{R}^{+}\right)^{n}$. Then for any
$(i_{1},i_{2},i_{3})\in[n]^{\otimes 3}$ one has

$\displaystyle\frac{\partial^{3}\log{Z_{n}(\beta,\mathbf{Q},\boldsymbol{\mu})}}{\partial\mu_{i_{1}}\partial\mu_{i_{2}}\partial\mu_{i_{3}}}\leq
0.$

Consequently, for any
$\boldsymbol{\mu}_{1}\succcurlyeq\boldsymbol{\mu}_{2}\succcurlyeq\mathbf{0}$
(i.e. coordinate-wise inequality) one has

$\displaystyle\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{1}}(X_{i},X_{j})$
$\displaystyle\leq\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{2}}(X_{i},X_{j}),$
(70)

whenever $\beta\mathbf{Q}_{ij}\geq 0$ for all $i,j\in[n]$.

######  Lemma 16 (GKS Inequality [27]).

Suppose $X\sim\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ with $\beta>0$,
$\mathbf{Q}_{ij}\geq 0$ for all $i,j\in[n]$ and
$\boldsymbol{\mu}\in\left(\mathbb{R}^{+}\right)^{n}$. Then the following hold
for any $i,j\in[n]$

$\displaystyle\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\geq
0;\quad\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i})\geq 0.$

######  Lemma 17 (Lemma 8 of [16]).

Suppose $X^{(k)}\sim\mathbb{P}_{\beta^{(k)},\mathbf{Q}^{(k)},\mathbf{0}}$ for
$k=1,2$ with
$\beta^{(1)}\mathbf{Q}^{(1)}_{ij}\geq\beta^{(2)}\mathbf{Q}^{(2)}_{ij}\geq 0$
for all $i,j$. Then

$\displaystyle\mathrm{Cov}_{\beta^{(1)},\mathbf{Q}^{(1)},\mathbf{0}}(X_{i},X_{j})\geq\mathrm{Cov}_{\beta^{(2)},\mathbf{Q}^{(2)},\mathbf{0}}(X_{i},X_{j}),\quad\forall
i,j.$

######  Lemma 18.

Suppose $X\sim\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ with
$\boldsymbol{\mu}\in(\mathbb{R}^{+})^{n}$, and $\beta\mathbf{Q}_{i,j}\geq 0$
for all $i\neq j$.

  1. (a)

Setting $c=(1-\tanh(\beta\|\mathbf{Q}\|_{\infty\rightarrow\infty})$ we have
$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i})\geq c\tanh(\mu_{i})$.

  2. (b)

With $C:=\frac{1}{\tanh(1)}$ we have

$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i})\leq
C\left\\{\tanh(\mu_{i})+\sum_{j}\tanh(\mu_{j})\Big{[}\mathbf{Q}_{ij}+\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\Big{]}\right\\}.$

###### Proof.

  1. (a)

Note that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i})=$
$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\tanh(\beta\sum_{j\in\Lambda_{n}(d)}\mathbf{Q}_{ij}X_{j}+\mu_{i})$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\tanh(\beta\sum_{j\in\Lambda_{n}(d)}\mathbf{Q}_{ij}X_{j})+(1-\tanh(\beta\|\mathbf{Q}\|_{\infty\rightarrow\infty})\tanh(\mu_{i}),$

from which the result follows on noting that

$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\tanh(\beta\sum_{j\in\Lambda_{n}(d)}\mathbf{Q}_{ij}X_{j})\geq\mathbb{E}_{\beta,\mathbf{Q},{\bf
0}}\tanh(\beta\sum_{j\in\Lambda_{n}(d)}\mathbf{Q}_{ij}X_{j})=0.$

In the above display, the first inequality follows the fact that the Ising
model is stochastically non decreasing in $\boldsymbol{\mu}$, along with the
observation that the function
$(x_{j},j\in\Lambda_{n}(d))\mapsto\tanh(\beta\sum_{j\in\Lambda_{n}(d)}\mathbf{Q}_{ij}x_{j})$
is non decreasing, and the second equality follows by symmetry of the Ising
model when $\boldsymbol{\mu}={\bf 0}$.

  2. (b)

A straightforward calculus gives the existence of $C_{1},C_{2}<\infty$ such
that for all $x\in[-c,c]$ and $y>0$ we have

$\displaystyle C_{1}\tanh(y)\leq\tanh(x+y)-\tanh(x)\leq C_{2}\tanh(y).$ (71)

Note that if $\mu_{i}>1$ then we have

$\mathbb{E}_{\beta,\boldsymbol{\mu},\mathbf{Q}}(X_{i})\leq 1\leq
C\tanh(\mu_{i}),$

where $C:=\frac{1}{\tanh(1)}$, and so we are done.

Setting $\mathcal{J}:=\\{j\in\Lambda_{n}(d):\mu_{j}\leq 1\\}$ define a vector
$\tilde{\boldsymbol{\mu}}$ by setting

$\displaystyle\tilde{\mu}_{i}:=$
$\displaystyle\mu_{i}+\sum_{j\notin\mathcal{J}}\mathbf{Q}_{ij},$
$\displaystyle\tilde{\mu}_{j}:=$ $\displaystyle\mu_{j}\text{ if }j\neq
i,j\in\mathcal{J},$ $\displaystyle:=$ $\displaystyle 0\text{ if
}j\notin\mathcal{J}.$

Also define an $n\times n$ matrix $\tilde{\mathbf{Q}}$ by setting

$\displaystyle\tilde{\mathbf{Q}}_{j,k}:=$ $\displaystyle\mathbf{Q}_{j,k}\text{
if both }j,k\in\mathcal{J},$ $\displaystyle:=$ $\displaystyle 0\text{ if
either }j,k\notin\mathcal{J}.$

Then invoking Lemma 16 in the first and the last line of the display below, we
have

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i})\leq\lim_{\mu_{j}\rightarrow\infty,j\notin\mathcal{J}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i})=$
$\displaystyle\mathbb{E}_{\beta,\tilde{\mathbf{Q}},\tilde{\boldsymbol{\mu}}}(X_{i})$
$\displaystyle=$
$\displaystyle\sum_{j\in\mathcal{J}}\tilde{\mu}_{j}\mathrm{Cov}_{\beta,\tilde{\mathbf{Q}},\tilde{\boldsymbol{\mu}}}(X_{i},X_{j})$
$\displaystyle=$
$\displaystyle\sum_{j\in\mathcal{J}}\tilde{\mu}_{j}\lim_{\mu_{j}\rightarrow\infty,j\notin\mathcal{J}}\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})$
$\displaystyle\leq$
$\displaystyle\sum_{j\in\mathcal{J}}\tilde{\mu}_{j}\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j}).$

Finally with $C=\frac{1}{\tanh(1)}$ the RHS above can be bounded as

$\displaystyle\sum_{j\in\mathcal{J}}\tilde{\mu}_{j}\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})=$
$\displaystyle\mu_{i}+\sum_{j\notin\mathcal{J}}\mathbf{Q}_{ij}+\sum_{j\in\mathcal{J},j\neq
i}\mu_{j}\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})$
$\displaystyle\leq$ $\displaystyle
C\tanh(\mu_{i})+C\sum_{j\notin\mathcal{J}}\mathbf{Q}_{ij}\tanh(\mu_{j})+C\sum_{j\in\mathcal{J}}\tanh(\mu_{j})\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})$

from which the desired conclusion follows on noting that
$\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\geq 0$ for all
$i,j$.

∎

######  Lemma 19.

If $\sup_{n}\|\mathbf{Q}\|<\infty$ and

$\liminf_{n\rightarrow\infty}\frac{1}{n}\log\frac{1}{2^{n}}Z(\beta,\mathbf{Q},\mathbf{0})>0,$
(72)

then maximum pseudo-likelihood estimator of $\beta$ under $\boldsymbol{\mu}=0$
based on our data is consistent for $\beta$ even under arbitrary magnetization
$\boldsymbol{\mu}\in\mathbb{R}^{n}_{+}$ when
$S:=\mathrm{supp}(\boldsymbol{\mu})$ with $|S|=o(n)$ uniformly over
$\boldsymbol{\mu}$. The same conclusion holds true if we further assume there
a subset $S_{1}$ with $|S_{1}|=o(n)$ and we set the vertices of $S_{1}$ being
set to $+1$.

###### Proof.

By assumption (72),

$\liminf_{n\rightarrow\infty}\frac{1}{n}\log\frac{1}{2^{n}}Z(\beta,\mathbf{Q},\boldsymbol{\mu})\geq\liminf_{n\rightarrow\infty}\frac{1}{n}\log\frac{1}{2^{n}}Z(\beta,\mathbf{Q},\mathbf{0})>0$

Our maximum pseudolikelihood estimator $\hat{\beta}_{n}$ satisfies the
equation $\tilde{S}_{\bm{\sigma}}(\beta)=0$, where
$\tilde{S}_{\bm{\sigma}}(\beta)$ is defined by

$\tilde{S}_{\bm{\sigma}}(\beta):=\frac{1}{n}\sum_{i}m_{i}({\bm{\sigma}})(\sigma_{i}-\tanh(\beta
m_{i}({\bm{\sigma}})+\boldsymbol{\mu}_{i})),$

and $m_{i}({\bm{\sigma}}):=\sum_{j}\mathbf{Q}_{ij}\sigma_{j}$. Define,

$S_{\bm{\sigma}}(\beta)=\frac{1}{n}\sum_{i}m_{i}({\bm{\sigma}})(\sigma_{i}-\tanh(\beta
m_{i}({\bm{\sigma}}))).$

Following the proof techniques of [11], we want a lower bound on
$\frac{1}{n}\sum_{i}m^{2}_{i}({\bm{\sigma}})$ and an upper bound on
$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(S^{2}_{\bm{\sigma}}(\beta))$.
For the upper bound, one can redo [14, Lemma 1.2] for $\boldsymbol{\mu}$
yielding
$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\tilde{S}^{2}_{\bm{\sigma}}(\beta))\leq
c/n$, for some $c>0$. Also

$|S_{\bm{\sigma}}(\beta)-\tilde{S}_{\bm{\sigma}}(\beta)|\leq\frac{1}{n}\sum_{i\in
S}2|m_{i}(\bm{\sigma})|=O\Big{(}\frac{s}{n}\Big{)}.$

Hence,

$\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(S^{2}_{\bm{\sigma}}(\beta))\leq
2(\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\tilde{S}^{2}_{\bm{\sigma}}(\beta))+o(1/n))=O(\max\\{\frac{s^{2}}{n^{2}},\frac{1}{n}\\})=o(a_{n}),$

for some $a_{n}=o(1)$. Therefore,
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(|S_{\bm{\sigma}}(\beta)|>K\sqrt{a_{n}})\leq
C/K^{2}$.

To obtain a lower bound on $\frac{1}{n}\sum_{i}m^{2}_{i}(\bm{\sigma})$, one
needs to lower bound
$H(\bm{\sigma})=\sum_{i,j}\mathbf{Q}_{ij}\sigma_{i}\sigma_{j}$. (72) and [11,
Lemma 5.1] yields

$\lim\limits_{\varepsilon\rightarrow
0}\limsup_{n\rightarrow\infty}\sup_{\boldsymbol{\mu}}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(H(\bm{\sigma})<\varepsilon
n)=0.$ (73)

Fixing $\delta>C/K^{2}$. $\exists\varepsilon>0$ such that

$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(H(\bm{\sigma})<\varepsilon
n)\leq\delta,$ (74)

Consider the set $\mathcal{A}=\\{|S_{\bm{\sigma}}(\beta)|\leq
K\sqrt{a_{n}},H(\bm{\sigma})\geq\varepsilon n\\}$.
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\mathcal{A})\geq 1-2\delta$.
On $\mathcal{A}$,

$\displaystyle\sum\beta m^{2}_{i}({\bm{\sigma}})$ $\displaystyle\geq\sum
m_{i}(\bm{\sigma})\tanh(m_{i}({\bm{\sigma}}))=H({\bm{\sigma}})-nS_{\bm{\sigma}}(\beta)\geq\eta
n,$

for some small $\eta>0$. So,
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\frac{1}{n}\sum_{i}m^{2}_{i}({\bm{\sigma}})\geq\eta)\geq
1-2\delta$. Also on $\mathcal{A}$,

$\displaystyle|S^{\prime}_{\bm{\sigma}}(\beta)|$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}m^{2}_{i}({\bm{\sigma}})\operatorname{sech}^{2}(\beta
m_{i}({\bm{\sigma}}))\geq\eta\operatorname{sech}^{2}(\beta).$

Therefore,

$K\sqrt{a_{n}}\geq|S_{\bm{\sigma}}(\beta)|=|S_{\bm{\sigma}}(\beta)-S_{\bm{\sigma}}(\hat{\beta}_{n})|=\int_{\beta\vee\hat{\beta}_{n}}^{\beta\wedge\hat{\beta}_{n}}|S^{\prime}_{\bm{\sigma}}(x)|dx\geq\eta|\tanh(\beta)-\tanh(\hat{\beta}_{n})|$

This proves $\hat{\beta}_{n}$ is consistent estimator of $\beta$.

If we set $S_{1}$ many vertices to be $+1$ with $|S_{1}|=o(n)$, then we have
non-zero magnetization on the set $S\cup S_{1}$ with $|S\cup S_{1}|=o(n)$.
Hence the previous argument still holds yielding the same conclusion. ∎

######  Lemma 20.

Suppose $\mathbf{X}\sim\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ with
$\boldsymbol{\mu}\in\Xi(\mathcal{C}_{s},A)$. Then for any set
$\tilde{S}^{\star}\subset[n]$ one has

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in\tilde{S}^{\star}}X_{i})\geq
A|\tilde{S}^{\star}\cap S^{\star}|-A^{2}\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}\sum_{j\in
S}\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\mathbf{\eta}}_{S^{\star}}(A)}(X_{i},X_{j}),$

where $S^{\star}$ denotes the support of $\boldsymbol{\mu}$ and
$\tilde{\mathbf{\eta}}_{S^{\star}}(A)$ is any point on the line segment
joining $\boldsymbol{\mu}_{S^{\star}}(A)$ and $\mathbf{0}$.

###### Proof.

We begin by noting that by G.K.S. Inequality (cf. Lemma 16), we have

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)$
$\displaystyle\geq\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}^{\star}(A)}\left(\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}X_{i}\right)$ $\displaystyle=\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}\left\\{\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(X_{i})+\sum_{j=1}^{n}\boldsymbol{\mu}_{j,S^{*}}(A)\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i},X_{j})\right\\}$
$\displaystyle=\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}\sum_{j=1}^{n}\boldsymbol{\mu}_{j,S^{*}}(A)\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i},X_{j}),$
(75)

for some $\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)$ lying on the line joining
$\mathbf{0}$ and $\boldsymbol{\mu}_{S}^{\star}(A)$. Now

$\displaystyle\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}\sum_{j=1}^{n}\boldsymbol{\mu}_{j,S^{\star}}(A)\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i},X_{j})$
$\displaystyle=A\sum_{i\in\tilde{S}^{\star}\cap S^{\star}}\sum_{j\in
S^{\star}}\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i},X_{j})$
$\displaystyle=A\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}\mathrm{Var}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i})+\tilde{R}_{n}$
$\displaystyle\geq A\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}\mathrm{Var}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i})$
(76)

since $\tilde{R}_{n}=A\sum_{i\in\tilde{S}^{\star}\cap S^{\star}}\sum_{j\neq
i\in
S^{\star}}\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i},X_{j})\geq
0$ by by G.K.S. Inequality (cf. Lemma 16). Thereafter note that

$\displaystyle\mathrm{Var}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i})=1-\mathbb{E}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}^{2}(X_{i}).$

Now, by repeating the argument above we have that for some
$\tilde{\bm{\eta}}_{S}^{\star}(A)$ on the line joining $\mathbf{0}$ and
$\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)$, and hence on on the line joining
$\mathbf{0}$ and $\boldsymbol{\mu}_{S}^{\star}(A)$, one has

$\displaystyle\mathbb{E}^{2}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i})\leq\mathbb{E}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i})=\sum_{j=1}^{n}\tilde{\boldsymbol{\mu}}_{j,S}^{\star}(A)\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\bm{\eta}}_{S}^{\star}(A)}(X_{i},X_{j})\leq
A\sum_{j\in
S^{*}}\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\bm{\eta}}_{S}^{\star}(A)}(X_{i},X_{j}),$

where the last inequality follows by noting that
$\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)$ lies on the line joining
$\mathbf{0}$ and ${\boldsymbol{\mu}}_{S}^{\star}(A)$. Therefore

$\displaystyle A\sum_{i\in\tilde{S}^{\star}\cap
S^{\star}}\mathrm{Var}_{\beta,\mathbf{Q},\tilde{\boldsymbol{\mu}}_{S}^{\star}(A)}(X_{i})\geq
A|\tilde{S}^{\star}\cap S^{\star}|-A^{2}\sum_{i\in\tilde{S}^{\star}\cap
S^{*}}\sum_{j\in
S^{*}}\mathrm{Cov}_{\beta,\mathbf{Q},\tilde{\bm{\eta}}_{S}^{\star}(A)}(X_{i},X_{j}).$

The proof of the lemma follows. ∎

######  Lemma 21.

Suppose $X_{i}$ are independent $\pm 1$ valued random variables such that
$\mathbb{E}(X_{i})=\mu_{i}$. Define $\tilde{X}_{i}=X_{i}-\mu_{i}$. For
$\theta\in(-1,1)\setminus\\{0\\}$, define
$s_{\theta}:=\frac{2\theta}{\log(1+\theta)-\log(1-\theta)}$. Set $s_{0}=1$.
Let $D_{n}$ be an $n\times n$ symmetric matrix with $D_{n,ii}=0$ $\forall
i\in[n]$. Let $\lambda_{1}$ denote the largest eigenvalue of $D_{n}$. For any
vector $\mathbf{c}=(c_{1},\ldots,c_{n})^{\top}$, if $\lambda_{1}\max_{i\leq
n}s_{\mu_{i}}<1$, then

$\log\left(\mathbb{E}\Big{(}\frac{1}{2}\sum_{i,j=1}^{n}D_{n,ij}\tilde{X}_{i}\tilde{X}_{j}+\sum_{i}c_{i}\tilde{X}_{i}\Big{)}\right)\lesssim\|D_{n}\|^{2}_{F}+\sum_{i=1}^{n}c^{2}_{i}.$
(77)

As an immediate consequence, we obtain
$\frac{1}{2}\sum_{i,j=1}^{n}D_{n,ij}\tilde{X}_{i}\tilde{X}_{j}+\sum_{i}c_{i}\tilde{X}_{i}$
is tight.

###### Proof.

Define $s^{\star}:=\max_{i}s_{\mu_{i}}$. The proof follows same steps as [17,
Lemma 3.1] with the change that we replace $\tilde{X}_{i}$ by
$\sqrt{s^{\star}}Z_{i}$ in [17, Equation 5.1]. ∎