# Sharp Signal Detection under Ferromagnetic Ising Models

Sohom Bhattacharya  Sohom Bhattacharya
Department of Statistics, Stanford University, CA, USA,
<EMAIL_ADDRESS>,  Rajarshi Mukherjee  Rajarshi Mukherjee
Department of Biostatistics, Harvard University, MA, USA,
<EMAIL_ADDRESS>and  Gourab Ray  Gourab Ray
Department of Mathematics and Statistics, University of Victoria, Vancouver,
BC, Canada,
<EMAIL_ADDRESS>
###### Abstract.

In this paper we study the effect of dependence on detecting a class of
structured signals in Ferromagnetic Ising models. Natural examples of our
class include Ising Models on lattices, and Mean-Field type Ising Models such
as dense Erdős-Rényi, and dense random regular graphs. Our results not only
provide sharp constants of detection in each of these cases and thereby
pinpoint the precise relationship of the detection problem with the underlying
dependence, but also demonstrate how to be agnostic over the strength of
dependence present in the respective models.

##  1\. Introduction

††2010 Mathematics Subject Classification: 62G10, 62G20, 60C20††Keywords and
phrases: Ising Model, Signal Detection, Structured Sparsity, Sharp Constants

Let $\mathbf{X}=(X_{1},\ldots,X_{n})^{\top}\in\\{\pm 1\\}^{n}$ be a random
vector with the joint distribution of $\mathbf{X}$ given by an Ising model
defined as:

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\mathbf{X}=\mathbf{x}):=\frac{1}{Z(\beta,\mathbf{Q},\mathbf{\boldsymbol{\mu}})}\exp{\left(\frac{\beta}{2}\mathbf{x}^{\top}\mathbf{Q}\mathbf{x}+\boldsymbol{\mu}^{\top}\mathbf{x}\right)},\qquad\forall\mathbf{x}\in\\{\pm
1\\}^{n},$ (1)

where $\mathbf{Q}$ is an $n\times n$ symmetric and hollow matrix,
$\boldsymbol{\mu}:=(\mu_{1},\ldots,\mu_{n})^{\top}\in\mathbb{R}^{n}$ is an
unknown parameter vector to be referred to as the external magnetization
vector, $\beta\in\mathbb{R}$ is a real number usually referred to as the
“inverse temperature”, and $Z(\beta,\mathbf{Q},\mathbf{\boldsymbol{\mu}})$ is
a normalizing constant. It is clear that the pair $(\beta,\mathbf{Q})$
characterizes the dependence among the coordinates of $\mathbf{X}$, and
$X_{i}$’s are independent if $\beta\mathbf{Q}=\mathbf{0}_{n\times n}$. The
matrix $\mathbf{Q}$ will usually be associated with a certain sequence of
simple labeled graphs $\mathbb{G}_{n}=(V_{n},E_{n})$ with vertex set
$V_{n}=\\{1,\dots,n\\}$ and edge set $E_{n}\subseteq V_{n}\times V_{n}$ and
corresponding $\mathbf{Q}=|V_{n}|G_{n}/2|E_{n}|$, where $G_{n}$ is the
adjacency matrix of $\mathbb{G}_{n}$. Note that we do not absorb $\beta$ in
the matrix $\mathbf{Q}$. This is because we want to understand the effect of
the nuisance parameter $\beta$ on the inference about $\boldsymbol{\mu}$.

We are interested in testing against a collection of alternatives defined by a
class of subsets $\mathcal{C}_{s}$ of $\mathbb{R}_{+}^{n}$ each of which is of
size $s$. More precisely, given any class of subsets
$\mathcal{C}_{s}\subset\\{S\subset\mathbb{R}_{+}^{n}:|S|=s\\}$ of
$\mathbb{R}_{+}^{n}$ having size $s$ each, we consider testing the following
hypotheses

$H_{0}:\boldsymbol{\mu}=\mathbf{0}\quad{\rm vs}\quad
H_{1}:\boldsymbol{\mu}\in\Xi(\mathcal{C}_{s},A),$ (2)

where

${\Xi}(\mathcal{C}_{s},A):=\left\\{\begin{array}[]{c}\boldsymbol{\mu}\in\mathbb{R}_{+}^{n}:\mathrm{supp}(\boldsymbol{\mu})\in\mathcal{C}_{s}{\rm\
and\ }\min\limits_{i\in{\rm supp}(\boldsymbol{\mu})}\mu_{i}\geq
A\end{array}\right\\},$

and

${\rm supp}(\boldsymbol{\mu}):=\\{i\in\\{1,\ldots,n\\}:\mu_{i}\neq 0\\}.$

Thus the class of alternatives $\Xi(\mathcal{C}_{s},A)$ puts non-zero signals
on one of candidate sets in $\mathcal{C}_{s}$ where each signal set has size
$s$. Of primary interest here is to explore the effect of $(\beta,\mathbf{Q})$
in testing (2) when $\mathcal{C}_{s}$ has low complexity in a suitable sense.

In this regard, previously, [6, 4] studied the detection of block-sparse and
thick shaped signals on lattices while [1] considered general class of signals
of combinatorial nature. However these papers crucially assume independence
between the outcomes and thereby correspond to $\beta=0$ in (1) in our
context. Following up on this line of research, several other papers have also
considered detection of signals over lattices and networks (see e.g. [26, 50,
7, 45, 49, 13, 35] and references therein). However, in overwhelming majority
of the literature, the underlying networks only describe the nature of signals
– such as rectangles or thick clusters in lattices [6]. A fundamental question
however remains – “how does dependence characterized by a network modulate the
behavior of such detection problems ?” Only recently, [26] explored the effect
of dependence 111Effect of dependence in signal detection for Gaussian
outcomes has also been explored for detecting unstructured arbitrary sparse
signals [31, 32]. on such structured detection problems for stationary
Gaussian processes – with examples including linear lattices studied through
the lens of Gaussian auto-regressive observation schemes. Dependence
structures beyond Gaussian random variables are often more challenging to
analyze (due to possible lack of closed form expressions of resulting
distributions) and allow for interesting and different behavior of such
testing problems – see e.g. [42]. One of the motivations of this paper is to
fill this gap in the literature and show how dependent binary outcomes can
substantially change the results for detecting certain classes structured
signals. One of the motivations of this paper is to pinpoint the precise
effect of dependence on the behavior of such testing problems. In particular,
[42, 18] demonstrate how dependence might have a subtle effect on the minimax
separation rate of sparse testing problems. In this paper we crystallize the
effect of such dependence by going beyond optimal rates and characterizing
sharp asymptotic constant for minimax separation while testing against
suitably structured hypotheses $\mathcal{C}_{s}$.

To describe our results in the context of the model-problem pair (1)-(2) we
adopt a standard minimax framework as follows. Let a statistical test for
$H_{0}$ versus $H_{1}$ be a measurable $\\{0,1\\}$ valued function of the data
$\mathbf{X}$, with $1$ denoting rejecting the null hypothesis $H_{0}$ and $0$
denoting not rejecting $H_{0}$. The worst case risk of a test $T:\\{\pm
1\\}^{\Lambda_{n}(d)}\to\\{0,1\\}$ for testing (2) is defined as

$\displaystyle\mathrm{Risk}(T,{\Xi}(\mathcal{C}_{s},A),\beta,\mathbf{Q})$
$\displaystyle:=\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(T(\mathbf{X})=1\right)+\sup_{\boldsymbol{\mu}\in{\Xi}(\mathcal{C}_{s},A)}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(T(\mathbf{X})=0\right).$
(3)

We say that a sequence of tests $T_{n}$ corresponding to a sequence of model-
problem pair (1) and (2), to be asymptotically powerful (respectively
asymptotically not powerful) against $\Xi(\mathcal{C}_{s},A)$ if

$\limsup\limits_{n\rightarrow\infty}\mathrm{Risk}(T_{n},\Xi(\mathcal{C}_{s},A),\beta,\mathbf{Q})=0\text{
(respectively
}\liminf\limits_{n\rightarrow\infty}\mathrm{Risk}(T_{n},\Xi(\mathcal{C}_{s},A),\beta,\mathbf{Q})>0).$
(4)

The goal of the current paper is to characterize how for some low complexity
class $\mathcal{C}_{s}$, the sparsity $s$, and strength $A$ of the signal
jointly determine if there is an asymptotically powerful test, and how the
behavior changes with $(\beta,\mathbf{Q})$.

With the above framework, our main results can be summarized as follows.

  1. (i)

For some classical mean-field type models we show that detecting low
complexity sets (see Theorem 1 for exact definition) has same constant of
detection for low and critical dependence and has a larger constant of minimax
separation (i.e. strictly more information theoretic hardness) for higher
dependence. Our examples naturally include the complete graph (Theorem 1),
dense Erdős-Rényi and dense random regular graphs(Theorem 3).

  2. (ii)

For detecting thick rectangular signals in Ising models over lattices of
general dimensions, we present the sharp minimax separation constants (Theorem
6) for low dependence and high dependence (under a “pure phase” defined in
Section 3). In contrast to dense regular graphs, the problem has a strict
monotone increasing nature of the constant as one approaches criticality from
the low dependence direction (Lemma 7). The exact monotonic nature of the
constant in the high dependence case is not clear and is left as future
research direction.

  3. (iii)

We further demonstrate how the sharp optimal tests can be obtained adaptively
over the dependence strength $\beta$ (Theorem 2 and Theorem 8).

The rest of this paper is organized as follows. In Section 2 we present our
results for detecting low complexity type signals in dense regular type
graphs. Subsequently, Section 3 considers detecting thick rectangular signals
over lattices. Finally all the proofs and associated technical lemmas are
collected in Section 6.

###  1.1. Notation

$[n]$, for $\mathbf{v}=(v_{1},\ldots,v_{d})^{T}\in\mathbb{R}^{d}$ define
$\bar{\mathbf{v}}=\frac{1}{d}\sum_{i=1}^{d}v_{i}$, for any set $A$ define
$\mathbbm{1}(\cdot\in A)$ as the indicator function for the set. For any set
$S\in\mathcal{S}$, let $\boldsymbol{\mu}_{S}(A)$ denote the vector with
$\mu_{i}=A\mathbbm{1}_{i\in S}$. Let $\mathbf{1}$ denote the vector of all
$1$s. We also let $\mathbbm{1}$ to denote generic indicator functions.

The results in this paper are mostly asymptotic (in $n$) in nature and thus
requires some standard asymptotic notations. If $a_{n}$ and $b_{n}$ are two
sequences of real numbers then $a_{n}\gg b_{n}$ (and $a_{n}\ll b_{n}$) implies
that ${a_{n}}/{b_{n}}\rightarrow\infty$ (and ${a_{n}}/{b_{n}}\rightarrow 0$)
as $n\rightarrow\infty$, respectively. Similarly $a_{n}\gtrsim b_{n}$ (and
$a_{n}\lesssim b_{n}$) implies that
$\liminf_{n\rightarrow\infty}{{a_{n}}/{b_{n}}}=C$ for some $C\in(0,\infty]$
(and $\limsup_{n\rightarrow\infty}{{a_{n}}/{b_{n}}}=C$ for some
$C\in[0,\infty)$). Alternatively, $a_{n}=o(b_{n})$ will also imply $a_{n}\ll
b_{n}$ and $a_{n}=O(b_{n})$ will imply that $\limsup_{n\rightarrow\infty}\
a_{n}/b_{n}=C$ for some $C\in[0,\infty)$). If $C>0$ then we write
$a_{n}=\Theta(b_{n})$. If $a_{n}/b_{n}\rightarrow 1$, then we say $a_{n}\sim
b_{n}$. For any $a,b\in\mathbb{Z}$, $a\leq b$, let
$[a,b]:=\\{a,a+1,\ldots,b\\}$.

##  2\. Mean-Field type Interactions

In this section, we collect our results on the testing problem (2) for some
specific examples of mean-field type models [8] such as Ising models on the
complete graph, and dense Erdős-Rényi and random regular graphs. However, for
the precise statement the upper bounds of our results we first define a class
of signals $\mathcal{C}_{s}$. This is captured by a notion of complexity
defined through the following weighted Hamming type of metric (see e.g. – [4,
6]) on $2^{[n]}$. Mathematically, for any two subsets $S_{1},S_{2}\subset[n]$
we let $\gamma(S_{1},S_{2}):=\sqrt{2}\left(1-\frac{|S_{1}\cap
S_{2}|}{\sqrt{|S_{1}||S_{2}|}}\right)$ denote their distance. Subsequently,
for any $\varepsilon>0$ we let
$|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon)|$ denote the
$\varepsilon$-covering number of $\mathcal{C}_{s}$ w.r.t. $\gamma$. Our main
result in terms of detecting signals in $\Xi(\mathcal{C}_{s},A)$ pertains to
classes of signals with suitably low complexity defined through the asymptotic
behavior of $|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon)|$. In this
regard we first provide a complete picture for all temperature regimes in the
mean-field Curie-Weiss model followed by demonstrating how similar results
might be obtained in high temperature regimes for other dense regular type
graphs.

###  2.1. Complete Graph

We begin by stating and discussing our results for the Curie-Weiss model.

######  Theorem 1.

Consider testing (2) in the model (1) with
$\mathbf{Q}_{ij}=\frac{\mathbf{1}(i\neq j)}{n}$ correspond to the complete
graph.

  1. i.

Assume that $\mathcal{C}_{s}$ satisfies the following condition w.r.t. the
metric $\gamma$ for some sequence $\varepsilon_{n}\rightarrow 0$:

$\Theta(\log n)=\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|\ll
s\ll n/\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|.$

Then the following hold.

    1. _a_)

For $\beta<1$, $s\ll\frac{n}{\log n}$, there exists a sequence of
asymptotically powerful test if

$\liminf_{n\rightarrow\infty}\sqrt{s}\tanh(A)(\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|)^{-1/2}>\sqrt{2}.$
(5)

    2. _b_)

For $\beta=1$, the same conclusion is valid for $s\ll\frac{\sqrt{n}}{\log n}$.

    3. _c_)

For $\beta>1$ and $s\ll\frac{n}{\log n}$, there exists a sequence of
asymptotically powerful test if

$\liminf_{n\rightarrow\infty}\sqrt{s}\tanh(A)(\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|)^{-1/2}>\sqrt{2}\cosh(\beta
m),$ (6)

where $m$ is the unique positive root of the equation $m=\tanh(\beta m)$.

  2. ii.

Assume that, there exists a subset
$\tilde{\mathcal{C}}_{s}\subset\mathcal{C}_{s}$ of disjoint sets such that

$\Theta(\log n)=\log|\tilde{\mathcal{C}}_{s}|\ll s\ll
n/\log|\tilde{\mathcal{C}}_{s}|.$

Then the following hold.

    1. _a_)

For $\beta<1$ and $s\ll\frac{n}{\log n}$, all tests are asymptotically
powerless if

$\liminf_{n\rightarrow\infty}\sqrt{s}\tanh(A)(\log|\tilde{\mathcal{C}}_{s}|)^{-1/2}<\sqrt{2}.$
(7)

    2. _b_)

For $\beta=1$, the same conclusion is valid for $s\ll\frac{\sqrt{n}}{\log n}$.

    3. _c_)

For $\beta>1$ and $s\ll\frac{n}{\log n}$, no tests are asymptotically powerful
if

$\liminf_{n\rightarrow\infty}\sqrt{s}\tanh(A)(\log|\tilde{\mathcal{C}}_{s}|)^{-1/2}<\sqrt{2}\cosh(\beta
m),$ (8)

A few remarks are in order regarding the conditions, involved optimal
procedures, and implications of Theorem 1. We first note that the upper and
lower bounds are sharp as long as there exists
$\tilde{C}_{s},\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ such that
$\log|\tilde{C}_{s}|\sim\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|$
for some $\varepsilon_{n}\rightarrow 0$. In particular, the sharp constants
match for testing a class of signals whose size is dominated (on log-scale) by
the size of a subclass of disjoint sets. Next we note that the conditions on
$s$ posited in the various parts of the theorem are actually optimal. Indeed,
as was discussed in [18], for $\beta=1$ and $s\gg\sqrt{n}$ the rate of
detection is much faster (requiring only $s\tanh(A)\gg n^{1/4}$) and the
problem might not offer a phase transition at the level of sharp constants.
Next we note that the optimal test above is based on a suitably calibrated
scanning procedure. However, the scanning procedure is somewhat different
depending on the regime of dependence. In high and critical dependence
($0\leq\beta\leq 1$) the procedure can be described as follows. For
$S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ we first define
$Z_{S}=\sum_{i\in S}X_{i}/\sqrt{s}$ and our scan test rejects for large values
of
$Z_{\max}:=\max\limits_{S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})}Z_{S}$.
In contrast, for the high dependence regime ($\beta>1$) we perform a somewhat
randomized scan test by first generating $W_{n}\sim
N(\bar{\mathbf{X}},1/(n\beta))$ and subsequently for $W_{n}>0$, rejecting
$H_{0}$ for large values of $Z_{\max}-m\sqrt{s}$ and when $W_{n}\leq 0$
rejecting $H_{0}$ for large values of $Z_{\max}+m\sqrt{s}$ 222$m:=m(\beta)$ is
the unique positive root of $m=\tanh(\beta m)$. The fact that these sequence
of tests are indeed sharp optimal is thereafter demonstrated by precise
analyses of the Type II errors (through a mean-variance control) and a
matching lower bound calculation obtained through a truncated second moment
approach. Both the analyses of the tests and the proofs for matching lower
bounds rely on the moderation deviation behavior of
$Z_{S},S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ – which are
obtained through Lemma 1. Finally, a direct analysis of the sharp constants of
detection, $\sqrt{2}$ for $\beta\leq 1$ and $\sqrt{2\cosh^{2}(\beta
m(\beta))}$ for $\beta>1$, reveals that the problem becomes harder as one
moves away from the critical dependence $\beta=1$. In particular, the sharp
constant of detection can be succinctly defined through by
$\sqrt{2\cosh^{2}(\beta m(\beta))}$ which we display below in Figure 1 to
demonstrate this phenomenon.

Figure 1. Behavior of $\sqrt{2}\cosh(m(\beta))$

To describe our next result, we note that the proof of the upper bound in
Theorem 1 assumes the knowledge of $\beta>0$. Our next result therefore
pertains to showing that the sharp rates obtained above can actually be
obtained adaptively over the knowledge of the inverse temperature $\beta>0$.
To this end we begin by noting that using a consistent of $\beta>0$ might seem
hopeless to begin with since consistent estimation of $\beta$ is not possible
when $\beta\in[0,1)$. However, when $\beta\leq 1$, our optimal test does not
depend on the specific knowledge of $\beta$. Therefore our idea can be
described as follows: (1) construct a consistent test to decide whether
$\beta\leq 1$ or $\beta>1$; (2) if the test rejects in favor of $\beta>1$ then
use a pseudo-likelihood estimator of $\beta$ under the working model of
$\boldsymbol{\mu}=0$ 333this is important since joint estimation of
$\beta,\boldsymbol{\mu}$ can be significantly harder information theoretically
and if the test return in favor of $\beta\leq 1$ then construct the $\beta$
independent optimal test in Theorem 1.

######  Theorem 2.

Theorem 1 holds for unknown $\beta>0$ if $\|\boldsymbol{\mu}\|_{\infty}=O(1)$.

The proof of Theorem 2, which is deferred to Section 6, requires the
assumption on $\boldsymbol{\mu}$ in terms of its maximal element. Although
this requirement can be relaxed to $\|\boldsymbol{\mu}\|_{\infty}=o(n/s)$, our
arguments were unable to get rid of it completely. We keep further
explorations in this regard for future research.

###  2.2. Dense Regular Graphs

The results in the Curie-Weiss model in the last section provides insight on
the possible behavior of this testing problem under mean-field type models
[8]. Here we demonstrate that this intuition of similar behavior to the Curie-
Weiss model with regard to this inferential problem is indeed true for some
specific examples of mean-field type models such as dense Erdős-Rényi and
random regular graphs, which is our first result in this direction. In
particular, we let $\mathbb{G}_{n}=(V_{n},E_{n})\sim\mathcal{G}_{n}(n,p)$
denote an Erdős-Rényi random graph with edges $E_{n}$ formed by joining pairs
of vertices $i,j\in V_{n}=\\{1,\ldots,n\\}$ independently with probability
$p\in(0,1)$. In a similar vein we let
$\mathbb{G}_{n}=(V_{n},E_{n})\sim\mathcal{G}_{n}(n,d)$ denote an randomly
drawn graph from the collection of all $d$-regular graphs on
$V_{n}=\\{1,\ldots,n\\}$.

######  Theorem 3.

The same conclusion of Theorem 1 hold for any $\beta\geq 0$ when either (i)
$\mathbf{Q}=\frac{G_{n}}{np}$ with $G_{n}$ being the adjacency matrix of
$\mathbb{G}_{n}\sim\mathcal{G}_{n}(n,p)$ with $p=\Theta(1)$; or (ii)
$\mathbf{Q}=\frac{G_{n}}{d}$ with $G_{n}$ being the adjacency matrix of
$\mathbb{G}_{n}\sim\mathcal{G}_{n}(n,d)$ with $d=\Theta(n)$.

A few remarks in order regarding the statement and proof of Theorem 3. First,
the result should be understood as a high probability statement w.r.t. the
randomness of the underlying Erdős-Rényi random graph. In particular, we prove
that same results as in Theorem 1 hold with probability converging  to $1$
under the Erdős-Rényi measure on $\mathbb{G}_{n}$. In this regard, the
requirement of $p=\Theta(1)$ is mostly used for the $\beta>1$ case and can be
relaxed for $\beta\leq 1$ regime. However, to keep our discussions consistent
over values of $\beta$ we only consider the $p=\Theta(1)$ case. Finally, the
proof of the theorem mainly operates through careful comparison of suitable
event probabilities and partition functions under Ising models over Erdős-
Rényi and complete graphs respectively – the proofs of which can be found in
Section 6.4. We also show that the result above can be obtain without the
knowledge of $\beta$.

######  Theorem 4.

Theorem 3 holds for unknown $\beta>0$ if $\|\boldsymbol{\mu}\|_{\infty}=O(1)$.

The requirement of $\|\boldsymbol{\mu}\|_{\infty}=O(1)$ can be relaxed to
$\|\boldsymbol{\mu}\|_{\infty}=o(n/s)$. However, at this moment we have not
been able to relax this completely.

##  3\. Short Range Interactions on Lattices

To describe the detection problem for nearest neighbor interaction type
models, it is convenient to represent the points $i=1,\dots,n$ to be vertices
of $d$-dimensional hyper-cubic lattice and the underlying graph (i.e. the
graph corresponding to $\mathbf{Q}$) to be the nearest neighbor (in sense of
Euclidean distance) graph on these vertices. More precisely, given positive
integers $n,d$, we consider a growing sequence of lattice boxes of dimension
$d$ defined as

$\\{\Lambda_{n,d}\\}_{n\geq
1}=\\{[-n^{1/d},n^{1/d}]^{d}\cap\mathbb{Z}^{d}\\}_{n\geq 1}$

where $\mathbb{Z}^{d}$ denotes the d-dimensional integer lattice.
Subsequently, we consider a family of random variables defined on the vertices
of $\Lambda_{n,d}$ as $\mathbf{X}\in\\{-1,+1\\}^{\Lambda_{n,d}}$ with the
following probability mass function (p.m.f.)

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\mathbf{X}=\mathbf{x})=\frac{1}{Z(\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{\boldsymbol{\mu}})}\exp{\left(\frac{\beta}{2}\mathbf{x}^{\top}\mathbf{Q}(\Lambda_{n,d})\mathbf{x}+\boldsymbol{\mu}^{\top}\mathbf{x}\right)},\qquad\forall\mathbf{x}\in\\{\pm
1\\}^{\Lambda_{n,d}},$ (9)

where as usual
$\mathbf{Q}(\Lambda_{n,d})=(\mathbf{Q}(\Lambda_{n,d})_{ij})_{i,j\in\Lambda_{n,d}}$
is a symmetric and hollow array (i.e. $\mathbf{Q}(\Lambda_{n,d})_{ii}=0$ for
all $i\in\Lambda_{n,d}$) with elements indexed by pairs of vertices in
$\Lambda_{n,d}$ (organized in some pre-fixed lexicographic order),
$\boldsymbol{\mu}:=(\mu_{i}:i\in\Lambda_{n,d})^{\top}\in\mathbb{R}^{\Lambda_{n,d}}$
referred to as the external magnetization vector indexed by vertices of
$\Lambda_{n,d}$ , $\beta>0$ is the “inverse temperature”, and
$Z(\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{\boldsymbol{\mu}})$ is a
normalizing constant. Note that in this notation $i,j\in\Lambda_{n,d}$ are
vertices of the $d$-dimensional integer lattice and hence correspond to
$d$-dimensional vector with integer coordinates. Therefore, using this
notation, by nearest neighbor graph will correspond to the matrix
$\mathbf{Q}_{ij}=\mathbf{Q}_{ij}(\Lambda_{n,d})=\mathbf{1}(0<\|i-j\|_{1}=1)$.

Our results in this model will be derived for any dependence other than a
critical dependence $\beta_{c}(d)$ to be defined next. The case of critical
dependence for lattices remains open even in terms of optimal rate for the
minimax separation and therefore we do not pursue the issue of optimal
constants in this regime. To describe a notion of critical temperature,
consider $\mathcal{Q}(d)$ be the sequence of matrices
$\\{\mathbf{Q}(\Lambda_{n,d})\\}_{n\geq 1}$ and define

$\displaystyle\beta_{c}(d)=\beta_{c}(\mathcal{Q}(d))=\inf\left\\{\beta>0:\lim_{h\downarrow
0}\lim_{n\rightarrow\infty}\mathbb{E}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\boldsymbol{\mu}(h)}\left(\frac{1}{n}\sum_{i\in\Lambda_{n,d}}X_{i}\right)>0\right\\},$

where we let $\boldsymbol{\mu}(h)$ denote the vector in
$\mathbb{R}^{|\Lambda_{n,d}|}$ with all coordinates equal to $h$. The
existence and equivalence of the above notions (such as ones including
uniqueness of infinite volume measure) of critical temperature in nearest
neighbor Ising Model is a topic of classical statistical physics and we refer
the interested reader to the excellent expositions in [27, 20] for more
details. This value of $\beta_{c}(d)$ (which is known to be strictly positive
for any fixed $d\geq 1$) is referred to as the critical inverse temperature in
dimension $d$ and the behavior of the system of observations $\mathbf{X}$
changes once $\beta$ exceeds this threshold. For $d=1$, it is known from the
first work in this area [34] that $\beta_{c}(1)=+\infty$ and consequently the
Ising model in 1-dimension is said to have no phase transitions. The seminal
work of [43] provides a formula for $\beta_{c}(2)$ and obtaining an analytical
formula for $\beta_{c}(d)$ for $d\geq 3$ remains open. Consequently, results
only pertain to the existence of a strictly non-zero finite $\beta_{c}(d)$
which governs the macroscopic behavior of the system of observations
$X_{i},i\in\Lambda_{n,d}$ as $n\rightarrow\infty$. In particular, the average
magnetization $n^{-1}\sum X_{i}$ converges to $0$ in probability for
$\beta<\beta_{c}(d)$ and to an equal mixture of two delta-dirac random
variables $m_{+}(\beta)$ and $m_{-}(\beta)=-m_{+}(\beta)$, for
$\beta>\beta_{c}(d)$ ([38]). This motivates defining Ising models in pure
phases as follows.

Let $\Lambda^{\mathsf{w}}_{n,d}$ denote the graph obtained by identifying the
vertices not in $\Lambda_{n,d}$ into a single vertex $\partial\Lambda_{n,d}$
and then erasing all the self loops. Let
$\mathbf{Q}(\Lambda^{\mathsf{w}}_{n,d})$ denote the adjacency matrix
corresponding to nearest neighbour interaction in this modified graph. We
denote

$\displaystyle\mathbb{P}^{+}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\boldsymbol{\mu}}(\mathbf{X}=\mathbf{x})=\mathbb{P}_{\beta,\mathbf{Q}(\Lambda^{\mathsf{w}}_{n,d}),\boldsymbol{\mu}}(\mathbf{X}=\mathbf{x}|\partial\Lambda_{n,d}=+1),$
$\displaystyle\mathbb{P}^{-}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\boldsymbol{\mu}}(\mathbf{X}=\mathbf{x})=\mathbb{P}_{\beta,\mathbf{Q}(\Lambda^{\mathsf{w}}_{n,d}),\boldsymbol{\mu}}(\mathbf{X}=\mathbf{x}|\partial\Lambda_{n,d}=-1),$

to be Ising Models (see (1)) with $+$ and $-$ boundary conditions
respectively. On the other hand
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ is referred to as the Ising
model with _free boundary condition_. It is well known [27], that for
$0\leq\beta<\beta_{c}(d)$ the asymptotic properties of the models
$\mathbb{P}^{+}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$,
$\mathbb{P}^{-}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$, and
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ are similar (i.e. they have
all the same infinite volume $n\rightarrow\infty$ weak limit). However, for
$\beta>\beta_{c}(d)$, the model
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ behaves asymptotically as the
mixture of $\mathbb{P}^{+}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ and
$\mathbb{P}^{-}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$. We only present our
result for the measure $\mathbb{P}^{+}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$ in
such cases. Although we believe that a similar result might hold for both
negative boundary condition (i.e.
$\mathbb{P}^{-}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$) as well as free boundary
condition (i.e. the original model
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}$) we do not yet have access to
a rigorous argument in this regard. In the rest of this section, we therefore
shall use the superscript “$\rm bc$” in our probability, expectation, and
variance operators (e.g. $\mathbb{P}^{\rm
bc}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\boldsymbol{\mu}}$, $\mathbb{E}^{\rm
bc}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\boldsymbol{\mu}}$, and
$\mathrm{Var}^{\rm bc}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\boldsymbol{\mu}}$)
where $\mathrm{bc}\in\\{\mathsf{f},+\\}$ and stands for “boundary condition”
referring to either the free boundary condition (when $\rm bc=\mathsf{f}$) or
plus boundary condition (when $\rm bc=+$).

To present our results in this case, we begin with describing the structure of
our alternatives. Since our model has an inherent geometry given by the
lattice structure in $d$-dimensions, it is natural to consider signals which
can be described by such geometry. Similar to one of the emblematic cases
considered in [4, 6, 49, 13, 35], here we discuss testing against block sparse
alternatives of size $s$ define by $\Xi(\mathcal{C}_{s},A)$ with

$\displaystyle\mathcal{C}_{s}=\mathcal{C}_{s,\rm
rect}:=\left\\{\prod\limits_{j=1}^{d}[a_{j}:b_{j}]\cap\Lambda_{n}(d):\
b_{j}-a_{j}=\lceil s^{1/d}\rceil\right\\}.$ (10)

Although we only present the results for sub-cube detection with equal size of
the sides , one can extend the results to detection of thick clusters (see [6]
for details) with modifications of the arguments presented here. The
development and analysis of multi-scale tests similar to those explored in [4,
49, 35] is also important. However we keep this for future research to keep
our discussions in this paper focused on understanding the main driving
principles behind the sharp constants of detection under Ising dependence.

This a class of alternatives is known to require
$\tanh(A)\asymp\sqrt{\frac{\log{n}}{s}}$ for consistent detection (see e.g.
[4, 5, 6] for independent outcomes case and [26, 18] for dependent models) and
allows a sharp transition at a level of multiplicative constants. Indeed, such
sharp constants of phase transition has been derived for either independent
outcome models [4, 5, 6] and for dependent Gaussian outcomes [26]. For our
problem, the derivation of the sharp optimal constant of detection is somewhat
subtle and we first discuss a way to formalize this asymptotic constant below.

We begin by noting that it is reasonable to believe that a sequence of optimal
test can be obtained by scanning over a suitable subclass of the potentially
signal rectangles. We define the test first to gain intuition about the sharp
constant of detection. To put ourselves in the context of notation similar to
Section 2, we use $\mathcal{C}_{s,\rm rect}$ to denote the class of all thick
rectangles of volume $s$ and for any $S\in\mathcal{C}_{s,\rm rect}$

$\displaystyle Z_{S}=\frac{1}{\sqrt{s}}\sum_{i\in
S}\left(X_{i}-\mathbb{E}^{\rm
bc}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(X_{i})\right),$

We would like to scan over a suitable subclass $\tilde{\mathcal{C}}_{s,\rm
rect}$ which captures the essential complexity of $\mathcal{C}_{s,\rm rect}$
both in terms of theoretical and computational aspects. From a theoretical
perspective, we shall require a precise understanding of the moderate
deviation behavior of $Z_{S}$ and which in turn crucially relies on
understanding the asymptotic behavior of the variance of $Z_{S}$. In
particular, it is reasonable to believe that in the “pure phase” (which is the
case for free boundary high temperature and low temperature plus boundary
case) $Z_{S}$ should asymptotically behave like a Gaussian random variable and
thus its moderate deviation exponent is characterized by its variance (See
[24, Theorem V.7.2] for a result of this nature). To justify that there is a
valid candidate for the limit of
$\mathrm{Var}^{+}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(Z_{S})$ we have
the following result which is one of the main components of this section.

######  Theorem 5.

Suppose
$\mathrm{dist}(S,\partial\Lambda_{n,d}):=\inf\limits_{j\in\partial\Lambda_{n,d},i\in
S}\|i-j\|_{1}\gg\log^{2}{n}$. Then there exists $\chi^{\mathsf{f}}(\beta)$
(for $\beta<\beta_{c}(d)$) and $\chi^{+}(\beta)$ (for $\beta>\beta_{c}(d)$)
such that

$\displaystyle\lim_{s\rightarrow\infty}\mathrm{Var}^{\mathrm{b}c}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(Z_{S})$
$\displaystyle=\chi^{\mathrm{b}c}(\beta),\quad\text{for}\quad\beta<\beta_{c}(d),\mathrm{bc}\in\\{\mathsf{f},+\\};$
(11)
$\displaystyle\lim_{s\rightarrow\infty}\mathrm{Var}^{+}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\mathbf{0}}(Z_{S})$
$\displaystyle=\chi^{+}(\beta),\quad\text{for}\quad\beta>\beta_{c}(d).$ (12)

Armed with Theorem 5 we are now ready to state the main sharp detection
threshold for detecting rectangles over lattices.

######  Theorem 6.

Suppose $\mathbf{X}\sim\mathbb{P}^{\rm
bc}_{\beta,\mathbf{Q}(\Lambda_{n,d}),\boldsymbol{\mu}}$ for $\rm
bc\in\\{\mathsf{f},+\\}$and consider testing (2) against
$\mathcal{C}_{s}=\mathcal{C}_{s,\rm rect}$. Then the following hold with $\rm
bc\in\\{\mathsf{f},+\\}$ for $\beta<\beta_{c}(d)$ and $\rm bc=+$ for
$\beta>\beta_{c}(d)$.

  1. (1)

A test based on $\max_{S\in\tilde{\mathcal{C}}_{s,\rm rect}}Z_{S}$ is
asymptotically powerful if $s\gg(\log{n})^{d}$

$\liminf\tanh(A)\sqrt{s/\log{(n/s)}}>\sqrt{2\chi^{\rm bc}(\beta)}.$

  2. (2)

All tests are asymptotically powerless if
$\limsup\tanh(A)\sqrt{s/\log{(n/s)}}<\sqrt{2\chi^{\rm bc}(\beta)}$.

A few remarks are in order regarding the results in Theorem 6. First, we have
not tried optimize the requirement $s\gg(\log{n})^{d}$ in our upper bound
above. Indeed, as noted in [18] one needs $s\gg\log{n}$ for any successful
detection and hence our results on sharp constants matches the requirement on
$s$ up to log-factors. Moreover, our next verifies that the susceptibility is
indeed an increasing function of $0\leq\beta<\beta_{c}(d)$.

######  Proposition 7.

$\chi(\beta)$ is differentiable and strictly monotonically increasing for
$\beta\in(0,\beta_{c}(d))$.

It is worth noting that this monotonicity without the strictness can be seen
as a consequence of the Edwards-Sokal coupling and the monotonicity in $p$ of
the FK-Ising model ([30]). Finally, we demonstrate that the results above can
be obained without the knowledge of $\beta\neq\beta_{c}(d)$.

######  Theorem 8.

Theorem 6 continues to hold for unknown $\beta\neq\beta_{c}(d)$ and $\rm
bc=\mathsf{f}$.

Although this completes the picture for non-critical temperature in nearest
neighbor Ising models over lattices, the behavior of the testing problem at
$\beta=\beta_{c}(d)$ remains open. At this moment we believe that the blessing
of getting a better rate and/or constant at criticality continues to hold for
lattices as well.

##  4\. Discussions

In this paper we have considered sharp constants of detecting structured
signals under Ising dependence. Although we have derived sharp phase
transitions in some popular classes of of both mean-field type Ising models
(at all temperatures) and nearest-neighbor Ising models on lattices (at all
non-critical temperatures) several related directions remain open. As an
immediate interesting question pertains to the Ising model on lattices and
figuring out the exact detection thresholds at the critical temperature to
complete the narrative of precise benefit of critical dependence in this
model. As was discussed in [41] this might require new ideas. Moreover, even
for non-critical temperatures it remains to explore the multi-scale procedures
for adaptive testing of thick clusters for Ising models over lattices (see
e.g. [4, 49, 35] and references therein). Moreover distributional
approximation for the test statistics used here is also a crucial direction
for the sake of improved practical applicability of our result. We keep these
questions as future research directions.

##  5\. Acknowledgements

GR is supported by NSERC 50311-57400.

## References

  * Addario-Berry et al. [2010] Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, Gábor Lugosi, et al.  On combinatorial testing problems.  _The Annals of Statistics_ , 38(5):3063–3092, 2010.
  * Aizenman et al. [1987] Michael Aizenman, David J Barsky, and Roberto Fernández.  The phase transition in a general class of ising-type models is sharp.  _Journal of Statistical Physics_ , 47(3-4):343–374, 1987.
  * Aizenman et al. [2015] Michael Aizenman, Hugo Duminil-Copin, and Vladas Sidoravicius.  Random currents and continuity of ising model’s spontaneous magnetization.  _Communications in Mathematical Physics_ , 334(2):719–742, 2015.
  * Arias-Castro et al. [2005] Ery Arias-Castro, David L Donoho, and Xiaoming Huo.  Near-optimal detection of geometric objects by fast multiscale methods.  _IEEE Transactions on Information Theory_ , 51(7):2402–2425, 2005.
  * Arias-Castro et al. [2008] Ery Arias-Castro, Emmanuel J Candès, Hannes Helgason, and Ofer Zeitouni.  Searching for a trail of evidence in a maze.  _The Annals of Statistics_ , pages 1726–1757, 2008.
  * Arias-Castro et al. [2011] Ery Arias-Castro, Emmanuel J Candes, and Arnaud Durand.  Detection of an anomalous cluster in a network.  _The Annals of Statistics_ , pages 278–304, 2011.
  * Arias-Castro et al. [2018] Ery Arias-Castro, Rui M Castro, Ervin Tánczos, and Meng Wang.  Distribution-free detection of structured anomalies: Permutation and rank-based scans.  _Journal of the American Statistical Association_ , 113(522):789–801, 2018.
  * Basak and Mukherjee [2015] Anirban Basak and Sumit Mukherjee.  Universality of the mean-field for the potts model.  _Probability Theory and Related Fields_ , pages 1–44, 2015.
  * Besag [1974] Julian Besag.  Spatial interaction and the statistical analysis of lattice systems.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 36(2):192–225, 1974.
  * Bhattacharya and Mukherjee [2018a] Bhaswar B Bhattacharya and Sumit Mukherjee.  Inference in ising models.  _Bernoulli_ , 24(1):493–525, 2018a.
  * Bhattacharya and Mukherjee [2018b] Bhaswar B Bhattacharya and Sumit Mukherjee.  Inference in ising models.  _Bernoulli_ , 24(1):493–525, 2018b.
  * Bodineau [2003] Thierry Bodineau.  Slab percolation for the ising model.  _arXiv preprint math/0309300_ , 2003.
  * Butucea and Ingster [2013] Cristina Butucea and Yuri I Ingster.  Detection of a sparse submatrix of a high-dimensional noisy matrix.  _Bernoulli_ , 19(5B):2652–2688, 2013.
  * Chatterjee [2007a] Sourav Chatterjee.  Estimation in spin glasses: A first step.  _The Annals of Statistics_ , pages 1931–1946, 2007a.
  * Chatterjee [2007b] Sourav Chatterjee.  Estimation in spin glasses: A first step.  _The Annals of Statistics_ , pages 1931–1946, 2007b.
  * Daskalakis et al. [2019] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.  Testing ising models.  _IEEE Transactions on Information Theory_ , 2019.
  * Deb and Mukherjee [2020] Nabarun Deb and Sumit Mukherjee.  Fluctuations in mean-field ising models.  _arXiv preprint arXiv:2005.00710_ , 2020.
  * Deb et al. [2020] Nabarun Deb, Rajarshi Mukherjee, Sumit Mukherjee, and Ming Yuan.  Detecting structured signals in ising models.  _arXiv preprint arXiv:2012.05784_ , 2020.
  * Duminil-Copin [2016] Hugo Duminil-Copin.  Random currents expansion of the ising model.  _arXiv preprint arXiv:1607.06933_ , 2016.
  * Duminil-Copin [2017] Hugo Duminil-Copin.  Lectures on the ising and potts models on the hypercubic lattice.  _arXiv preprint arXiv:1707.00520_ , 2017.
  * Duminil-Copin and Tassion [2016] Hugo Duminil-Copin and Vincent Tassion.  A new proof of the sharpness of the phase transition for bernoulli percolation and the ising model.  _Communications in Mathematical Physics_ , 343(2):725–745, 2016.
  * Duminil-Copin et al. [2017] Hugo Duminil-Copin, Aran Raoufi, and Vincent Tassion.  Sharp phase transition for the random-cluster and potts models via decision trees.  _arXiv preprint arXiv:1705.03104_ , 2017.
  * Duminil-Copin et al. [2018] Hugo Duminil-Copin, Subhajit Goswami, and Aran Raoufi.  Exponential decay of truncated correlations for the ising model in any dimension for all but the critical temperature.  _arXiv preprint arXiv:1808.00439_ , 2018.
  * Ellis [2006] Richard S Ellis.  _Entropy, large deviations, and statistical mechanics_ , volume 1431\.  Taylor & Francis, 2006.
  * Ellis and Newman [1978] Richard S. Ellis and Charles M. Newman.  The statistics of curie-weiss models.  _Journal of Statistical Physics_ , 19(2):149–161, 1978.
  * Enikeeva et al. [2020] Farida Enikeeva, Axel Munk, Markus Pohlmann, and Frank Werner.  Bump detection in the presence of dependency: Does it ease or does it load?  _Bernoulli_ , 26(4):3280–3310, 2020.
  * Friedli and Velenik [2017] Sacha Friedli and Yvan Velenik.  _Statistical mechanics of lattice systems: a concrete mathematical introduction_.  Cambridge University Press, 2017.
  * Ghosal and Mukherjee [2020] Promit Ghosal and Sumit Mukherjee.  Joint estimation of parameters in ising model.  _The Annals of Statistics_ , 48(2):785–810, 2020\.
  * Grimmett [1999] Geoffrey Grimmett.  _Percolation_ , volume 321 of _Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]_.  Springer-Verlag, Berlin, second edition, 1999.  ISBN 3-540-64902-6.  doi: 10.1007/978-3-662-03981-6.  URL https://doi.org/10.1007/978-3-662-03981-6.
  * Grimmett [2006] Geoffrey R Grimmett.  _The random-cluster model_ , volume 333.  Springer Science & Business Media, 2006.
  * Hall and Jin [2008] Peter Hall and Jiashun Jin.  Properties of higher criticism under strong dependence.  _The Annals of Statistics_ , pages 381–402, 2008.
  * Hall and Jin [2010] Peter Hall and Jiashun Jin.  Innovated higher criticism for detecting sparse signals in correlated noise.  _The Annals of Statistics_ , 38(3):1686–1732, 2010.
  * Ingster et al. [2010] Yuri I Ingster, Alexandre B Tsybakov, and Nicolas Verzelen.  Detection boundary in sparse regression.  _Electronic Journal of Statistics_ , 4:1476–1526, 2010\.
  * Ising [1925] Ernst Ising.  Beitrag zur theorie des ferromagnetismus.  _Zeitschrift für Physik A Hadrons and Nuclei_ , 31(1):253–258, 1925.
  * König et al. [2020] Claudia König, Axel Munk, and Frank Werner.  Multidimensional multiscale scanning in exponential families: Limit theory and statistical consequences.  _The Annals of Statistics_ , 48(2):655–678, 2020\.
  * Lebowitz [1972] Joel L Lebowitz.  Bounds on the correlations and analyticity properties of ferromagnetic ising spin systems.  _Communications in Mathematical Physics_ , 28(4):313–321, 1972.
  * Lebowitz [1974] Joel L Lebowitz.  Ghs and other inequalities.  _Communications in Mathematical Physics_ , 35(2):87–92, 1974.
  * Lebowitz [1977] Joel L Lebowitz.  Coexistence of phases in ising ferromagnets.  _Journal of Statistical Physics_ , 16(6):463–476, 1977.
  * Liggett et al. [1997] Thomas M Liggett, Roberto H Schonmann, and Alan M Stacey.  Domination by product measures.  _The Annals of Probability_ , 25(1):71–95, 1997\.
  * Martin-Löf [1973] Anders Martin-Löf.  Mixing properties, differentiability of the free energy and the central limit theorem for a pure phase in the ising model at low temperature.  _Communications in Mathematical Physics_ , 32(1):75–92, 1973.
  * Mukherjee and Ray [2019] Rajarshi Mukherjee and Gourab Ray.  On testing for parameters in ising models.  _arXiv preprint arXiv:1906.00456_ , 2019.
  * Mukherjee et al. [2016] Rajarshi Mukherjee, Sumit Mukherjee, and Ming Yuan.  Global testing against sparse alternatives under ising models.  _arXiv preprint arXiv:1611.08293_ , 2016.
  * Onsager [1944] Lars Onsager.  Crystal statistics. i. a two-dimensional model with an order-disorder transition.  _Physical Review_ , 65(3-4):117, 1944.
  * Pisztora [1996] Agoston Pisztora.  Surface order large deviations for Ising, Potts and percolation models.  _Probab. Theory Related Fields_ , 104(4):427–466, 1996.  ISSN 0178-8051.  doi: 10.1007/BF01198161.  URL https://doi.org/10.1007/BF01198161.
  * Sharpnack et al. [2015] James Sharpnack, Alessandro Rinaldo, and Aarti Singh.  Detecting anomalous activity on networks with the graph fourier scan statistic.  _IEEE Transactions on Signal Processing_ , 64(2):364–379, 2015.
  * Simon [1980] Barry Simon.  Correlation inequalities and the decay of correlations in ferromagnets.  _Communications in Mathematical Physics_ , 77(2):111–126, 1980.
  * Tikhomirov and Youssef [2019] Konstantin Tikhomirov and Pierre Youssef.  The spectral gap of dense random regular graphs.  _The Annals of Probability_ , 47(1):362–419, 2019\.
  * Vu [2005] Van H Vu.  Spectral norm of random matrices.  In _Proceedings of the thirty-seventh annual ACM symposium on Theory of computing_ , pages 423–430, 2005.
  * Walther [2010] Guenther Walther.  Optimal and fast detection of spatial clusters with scan statistics.  _The Annals of Statistics_ , 38(2):1010–1033, 2010.
  * Zou et al. [2017] Shaofeng Zou, Yingbin Liang, and H Vincent Poor.  Nonparametric detection of geometric structures over networks.  _IEEE Transactions on Signal Processing_ , 65(19):5034–5046, 2017.

##  6\. Proofs of Main Results

We divide the proofs our main results according to Sections 2 and 3.

###  6.1. Proof of Results in Section 2.1

####  6.1.1. Proof of Theorem 1

##### Proof of Theorem 1i.

We divide our proof according to the various parts of the theorem.

##### Proof of Theorem 1i.i._a_)

Recall from the discussion following the statement of Theorem 1 that the
claimed optimal test is given the by the scan test which can be described as
follows. For $S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ we
first define $Z_{S}=\sum_{i\in S}X_{i}/\sqrt{s}$ and our scan test rejects for
large values of
$Z_{\max}:=\max\limits_{S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})}Z_{S}$.
The cut-off for the test is decided by the moderate deviation behavior of
$Z_{S}$’s given in Lemma 1 – which implies that for any $\delta>0$, the test
given by
$T_{n}(\delta)=\mathbf{1}\left\\{Z_{\max}>\sqrt{2(1+\delta)\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}\right\\}$
has Type I error converging to $0$.

Turning to the Type II error, consider any
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\in\Xi(\mathcal{C}_{s},A)$ and
note that by monotonicity arguments (i.e. stochastic increasing nature of the
distribution of $Z_{\max}$ as a function of coordinates of $\boldsymbol{\mu}$)
it is enough to restrict to the case where
$A=\Theta(\sqrt{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}})$.
Thereafter, note that by GHS inequality(cf. 15) one has
$\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in\tilde{S}^{\star}}X_{i})\leq\mathrm{Var}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i\in\tilde{S}^{\star}}X_{i})=O(s)$
for $\beta<1$ since $s\ll\frac{n}{\log{n}}$ by appealing to [18, Lemma 9(a)].
As a result,
$\frac{\sum_{\i\in\tilde{S^{\star}}}(X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i}))}{\sqrt{s}}=O_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(1)$.
Therefore, as usual it is enough to show that there exists $\delta>0$ such
that
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)\rightarrow-\infty$.
To show this end, first let $S^{\star}\in\mathcal{C}_{s}$ be such that the
signal lies on $S^{\star}$ i.e. for all $i\in S^{\star}$ one has
$\boldsymbol{\mu}_{i}\geq A$. Note that by monotonicity arguments it is enough
to consider $\boldsymbol{\mu}_{i}=A$. By definition of covering, we can find a
$\tilde{S}^{\star}\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ such
that $\gamma\left(\tilde{S}^{\star},S^{\star}\right)\leq\varepsilon_{n}$ i.e.
$|\tilde{S}^{\star}\cap S^{\star}|\geq s(1-\varepsilon_{n}/\sqrt{2})$.

Thereafter note that by Lemma 20 we have that

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

However, by [18, Lemma 9 (a)] we have that

$\displaystyle 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})$
$\displaystyle\lesssim\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}{s}\left(\frac{|\tilde{S}^{\star}\cap
S^{\star}||S^{\star}|}{n}+|\tilde{S}^{\star}\cap S^{\star}|\right)$
$\displaystyle\leq\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|s}}{{n}}+\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}\ll
As.$

Consequently, we immediately have that there exists $\epsilon>0$ such that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)$
$\displaystyle\geq
As(1+o(1))\geq\sqrt{2(1+\epsilon)s\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$

Therefore, we can conclude that for any $\delta<\epsilon$ we have
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)\rightarrow-\infty$.
This completes the proof of the upper bound for $0<\beta<1$.

##### Proof of Theorem 1i.i._b_)

An optimal test is given the by the scan test which can be described similar
to the case $\beta<1$. For
$S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$, define
$Z_{S}=\sum_{i\in S}X_{i}/\sqrt{s}$ and reject for large values of
$Z_{\max}:=\max\limits_{S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})}Z_{S}$.
Lemma 1 implies that for any $\delta>0$, the test given by
$T_{n}(\delta)=\mathbf{1}\left\\{Z_{\max}>\sqrt{2(1+\delta)\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}\right\\}$
has Type I error converging to $0$ whenever $s\ll\sqrt{n}/\log{n}$.

Turning to the Type II error, consider any
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\in\Xi(\mathcal{C}_{s},A)$ and
note that by monotonicity arguments it is enough to restrict to the case where
$A=\Theta(\sqrt{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}})$.
Thereafter, note that by GHS inequality(cf. 15) one has
$\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in\tilde{S}^{\star}}X_{i})\leq\mathrm{Var}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i\in\tilde{S}^{\star}}X_{i})=O(s)$
even for $\beta=1$ since $s\ll\frac{\sqrt{n}}{\log{n}}$ by appealing to [18,
Lemma 9(c)]. As a result,
$\frac{\sum_{\i\in\tilde{S^{\star}}}(X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i}))}{\sqrt{s}}=O_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(1)$.
Therefore, as usual it is enough to show that there exists $\delta>0$ such
that
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)\rightarrow-\infty$.
To show this end, first let $S^{\star}\in\mathcal{C}_{s}$ be such that the
signal lies on $S^{\star}$ i.e. for all $i\in S^{\star}$ one has
$\boldsymbol{\mu}_{i}\geq A$. Note that by monotonicity arguments it is enough
to consider $\boldsymbol{\mu}_{i}=A$. By definition of covering, we can find a
$\tilde{S}^{\star}\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ such
that $\gamma\left(\tilde{S}^{\star},S^{\star}\right)\leq\varepsilon_{n}$ i.e.
$|\tilde{S}^{\star}\cap S^{\star}|\geq s(1-\varepsilon_{n}/\sqrt{2})$.

Thereafter note that by Lemma 20 we have that

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

However, by [18, Lemma 9 (c)] we have that

$\displaystyle 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})$
$\displaystyle\lesssim\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}{s}\left(\frac{|\tilde{S}^{\star}\cap
S^{\star}||S^{\star}|}{\sqrt{n}}+|\tilde{S}^{\star}\cap S^{\star}|\right)$
$\displaystyle\leq\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|s}}{\sqrt{n}}+\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}\ll
As.$

Consequently, we immediately have that there exists $\epsilon>0$ such that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)$
$\displaystyle\geq
As(1+o(1))\geq\sqrt{2(1+\epsilon)s\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$

Therefore, we can conclude that for any $\delta<\epsilon$ we have
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)\rightarrow-\infty$.
This completes the proof of the upper bound for $\beta=1$.

##### Proof of Theorem 1i.i._c_)

We use a randomized scan test here described as follows: Given data
$X_{i},i\in[n]$, generate a random variable $W_{n}\sim
N(\bar{\mathbf{X}},1/(n\beta))$. If $W_{n}>0$, we reject the null hypotheses
if
$Z_{\max}:=\max\limits_{S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})}Z_{S}>m\sqrt{s}+t_{n}(\delta)$.
If $W_{n}\leq 0$ we reject if $Z_{\max}>-m\sqrt{s}+t_{n}(\delta)$, where
$m:=m(\beta)$ is the unique positive root of $m=\tanh(\beta m)$ and
$t_{n}(\delta)=\sqrt{2(1+\delta)(1-m^{2})\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$.
It turns out that our analysis of this test works whenever
$\sum_{i=1}^{n}\mu_{i}\ll n$. This is however not an issue since the test
based on conditionally centered $\sum_{i=1}^{n}X_{i}$ works as soon as
$\sum_{i=1}^{n}\mu_{i}\gg\sqrt{n}$ [42] – and hence simple Bonferroni
correction (i.e. the test rejects when either the randomized test described
above or the the conditionally centered sum based test of [42]) yields our
desired result. Hence we focus here on the case when
$\sqrt{n}\ll\sum_{i=1}^{n}\mu_{i}\ll n^{3/4}$.

By the moderate deviation behavior of $Z_{S}$’s given in Lemma 1, the Type-I
error converges to $0$.

Turning to the Type II error, consider any
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\in\Xi(\mathcal{C}_{s},A)$.
Now, let $S^{*}$ be the rectangle with non-zero signal with the true signal
set under the alternative. We choose $\delta$ with
$\tanh(A)=\sqrt{2(1+\delta)^{2}(1-m^{2})^{-1}\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}/s}$.
By definition of covering, we can find a
$\tilde{S}^{\star}\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ such
that $\gamma\left(\tilde{S}^{\star},S^{\star}\right)\leq\varepsilon_{n}$ i.e.
$|\tilde{S}^{\star}\cap S^{\star}|\geq s(1-\varepsilon_{n}/\sqrt{2})$. We want
to control
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(A_{n,\tilde{S}^{\star}}\cup
B_{n,\tilde{S}^{\star}})$ where

$\displaystyle A_{n,S}$
$\displaystyle=\\{Z_{S}>m\sqrt{s}+t_{n}(\delta),W_{n}>0\\},$ $\displaystyle
B_{n,S}$ $\displaystyle=\\{Z_{S}>-m\sqrt{s}+t_{n}(\delta),W_{n}\leq 0\\}.$
(13)

We have to show

$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(A_{n,\tilde{S}^{\star}}\cup
B_{n,\tilde{S}^{\star}})\rightarrow 1.$ (14)

We plan to show
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(A_{n,\tilde{S}^{\star}})-\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(W_{n}>0)\rightarrow
0$ and
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(B_{n,\tilde{S}^{\star}})-\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(W_{n}\leq
0)\rightarrow 0$. We prove of the first limit and the proof of the second one
is similar.

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(A_{n,\tilde{S}^{\star}})=\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\mathbf{1}(W_{n}>0)\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left[\bar{X}_{S}>m(\beta)+t_{n}(\delta)/\sqrt{s}|W_{n}\right]\right)$
$\displaystyle\leq\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\mathbf{1}(W_{n}>0)\underbrace{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left[\frac{\sum_{i\in
S}X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum\limits_{i\in
S}X_{i}|W_{n})}{\sqrt{s}}>\sqrt{s}(m-\tanh(\beta
W_{n}+A))+t_{n}(\delta)|W_{n}\right]}_{G_{n}(W_{n})}\right)$

We claim that
$G_{n}(W_{n})\mathbf{1}(W_{n}>0)-\mathbf{1}(W_{n}>0)\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$.
This will imply
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(A_{n})-\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(W_{n}>0)\rightarrow
0$ by DCT. To show the in probability convergence of
$G_{n}(W_{n})\mathbf{1}(W_{n}>0)$ we note that for any $\epsilon>0$

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\mathbf{1}(W_{n}>0)(1-G_{n}(W_{n}))>\epsilon)$
$\displaystyle\leq\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(G_{n}(W_{n})<1-\epsilon,W_{n}>0).$

We therefore need to understand $G_{n}(W_{n})$ on the event $W_{n}>0$. By
Lemma 4,
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(|W_{n}-m|>\zeta_{n},W_{n}>0)\rightarrow
0$ for some slowly decreasing $\zeta_{n}$. More specifically, this follows
from 4 since this lemma not only implies concentration of $W_{n}$ around
$m_{n}$ in $\sqrt{n}$-scale and but also that
$m_{n}-m=\Theta(\frac{1}{n}\sum_{i=1}^{n}\mu_{i})=o(n^{-1/4})$ by the property
of $\boldsymbol{\mu}$. Next fix $\eta>0$ such that if
$W_{n}>0,|W_{n}-m|\leq\zeta_{n}$ for some decreasing
$\frac{1}{\sqrt{n}}\ll\zeta_{n}\rightarrow\ll\frac{1}{n^{1/4}}$,
$\operatorname{sech}^{2}(\beta
W_{n}+A)\leq(1+\eta)^{2}\operatorname{sech}^{2}(\beta m)$ and
$\sqrt{s}(m-\tanh(\beta W_{n}+A))\leq-(1-\eta)\operatorname{sech}^{2}(\beta
m)A\sqrt{s}$. Hence, on the event $W_{n}>0,|W_{n}-m|\leq\zeta_{n}$ we have

$\displaystyle\sqrt{\frac{s}{\operatorname{sech}^{2}(\beta
W_{n}+A)}}(m-\tanh(\beta
W_{n}+A))+\frac{t_{n}(\delta)}{\operatorname{sech}^{2}(\beta W_{n}+A)}$
$\displaystyle\leq-\sqrt{2\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}\left[\frac{(1-\eta)(1+\delta)}{1+\eta}-1\right]$

Choosing $\eta$ small enough we have the last display
$\Theta(-\sqrt{\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|})$
and the result follows by Chebyshev’s Inequality. The same proof goes through
for $W_{n}\leq 0$ by appealing to Lemma 4.

##### Proof of Theorem 1ii.

We divide our proof according to the various parts of the theorem.

##### Proof of Theorem 1ii.ii._a_)

We follow the path of truncated second moment method with respect to a
suitable prior over $\tilde{\mathcal{C}}_{s}\subset\mathcal{C}_{s}$. Owing to
the exchangeability of the Curie-Weiss model it is natural to consider the
uniform prior $\pi$ (say) over all $\boldsymbol{\mu}\in\Xi(\mathcal{C}_{s},A)$
such $\mathrm{supp}(\boldsymbol{\mu})\in\tilde{C}_{s}$ and
$\boldsymbol{\mu}_{i}=A$ for $i\in\mathrm{supp}(\boldsymbol{\mu})$. The
likelihood ratio $L_{\pi}$ (say) corresponding to this prior can be written as

$\displaystyle
L_{\pi}=\frac{1}{|\tilde{C}_{s}|}\sum_{S\in\tilde{C}_{s}}\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),$

where $\boldsymbol{\mu}_{S}(A)$ is the vector with support $S$ and entries
equal to $A$ on its support. Now recall the definition of $Z_{S}$ from the
proof of Theorem 1i.i._a_) define an event
$\Omega_{n}(S,\delta)=\\{Z_{S}\leq\tilde{t}_{n}(\delta)\\}$ – where for any
$\delta>0$ we define
$\tilde{t}_{n}(\delta)=\sqrt{2(1+\delta)\log|\tilde{C}_{s}|}$. Subsequently,
we let

$\displaystyle\tilde{L}_{\pi}(\delta):=\frac{1}{|\tilde{C}_{s}|}\sum_{S\in\tilde{C}_{s}}\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}(\mathbf{X}\in\Omega_{n}(S,\delta))$ (15)

denote a truncated likelihood ratio at level $\delta>0$. It is thereafter
enough the verify that there exists $\delta>0$ such that the following three
claims hold [33]

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(L_{\pi}\neq\tilde{L}_{\pi}(\delta))$
$\displaystyle\rightarrow 0;$ (16)
$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\tilde{L}_{\pi}(\delta))$
$\displaystyle\rightarrow 1;$ (17)
$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\tilde{L}_{\pi}^{2}(\delta))$
$\displaystyle\leq 1+o(1).$ (18)

We now show them in sequence. To show (16) note that

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(L_{\pi}\neq\tilde{L}_{\pi}(\delta))=\sum_{S\in\tilde{C}_{s}}\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(\frac{1}{\sqrt{s}}\sum_{i\in
S}X_{i}>\tilde{t}_{n}(\delta)\right)\rightarrow 0.$

The convergence to $0$ in the display above follows from Lemma 1 for any
$\delta>0$ – by the same verbatim argument that showed the Type I error
convergence to $0$ in the proof of Theorem 1i.i._a_).

Next we turn to (17). To verify this, we first note that by a simple change of
measure

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\tilde{L}_{\pi}(\delta))=\frac{1}{|\tilde{\mathcal{C}}_{s}|}\sum_{S\in\tilde{C}_{s}}\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).$

To analyze the R.H.S of the display above note 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. Also, by arguments similar to the control
of Type II error in the proof of Theorem 1i.i._a_) and the fact that
$\limsup_{n\rightarrow\infty}\sqrt{s}\tanh(A)(\log|\tilde{\mathcal{C}}_{s}|)^{-1/2}<\sqrt{2}$,
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$ for any $\delta>0$.

Finally we shall make a choice of $\delta>0$ while verifying (18). First note
that since $\tilde{\mathcal{C}}_{s}$ consists of disjoint sets we have

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}\left(\tilde{L}_{\pi}^{2}(\delta)\right)$
$\displaystyle=\frac{1}{|\tilde{\mathcal{C}}_{s}|^{2}}\sum_{S\in\tilde{\mathcal{C}}_{s}}\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)}(\Omega_{n}(S,\delta))$
$\displaystyle+\frac{1}{|\tilde{\mathcal{C}}_{s}|^{2}}\sum_{S_{1}\neq
S_{2}\in\tilde{\mathcal{C}}_{s}}\frac{Z^{2}(\beta,\mathbf{Q},\mathbf{0})Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}\cup
S_{2}}(A))}{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}}(A))Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{2}}(A))Z(\beta,\mathbf{Q},\mathbf{0})}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}\cup
S_{2}}(A)}(\Omega_{n}(S_{1},\delta)\cap\Omega_{n}(S_{2},\delta))$
$\displaystyle=T_{1}+T_{2}\quad\text{(say),}$ (19)

We will first show that $T_{2}\leq 1+o(1)$. To see this note that

$\displaystyle T_{2}\leq\frac{1}{|\tilde{\mathcal{C}}_{s}|^{2}}\sum_{S_{1}\neq
S_{2}\in\tilde{\mathcal{C}}_{s}}\frac{Z^{2}(\beta,\mathbf{Q},\mathbf{0})Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}\cup
S_{2}}(A))}{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}}(A))Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{2}}(A))Z(\beta,\mathbf{Q},\mathbf{0})}=1+o(1),$

by the proof for the control of the second term in equation (9) of [18,
Theorem 3] along with the correlation bounds presented in [18, Lemma 9(a)]. By
symmetry, the value of $T_{1}$ equals

$T_{1}=\frac{1}{|\tilde{\mathcal{C}}_{s}|}\frac{Z^{2}_{n}(\beta,0)}{Z^{2}_{n}(\beta,s,A)}\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)}(\Omega_{n}(S,\delta)).$
(20)

Let $\varepsilon>0$ small enough such that
$\sqrt{s}\tanh(A)(\log|\tilde{\mathcal{C}}_{s}|)^{-1/2}=2(1-\varepsilon)$. Set
$\lambda>0$ such that
$\tanh(2A-\lambda/\sqrt{s})=\tilde{t}_{n}(\delta)/\sqrt{s}$. Note,
$\cosh(2A)\leq(1-\frac{(t_{n}(\delta)+\lambda)^{2}}{s})^{-1/2}$. Therefore,

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A)}\Big{(}Z_{S}\leq\tilde{t}_{n}(\delta)\Big{)}$
$\displaystyle\leq
e^{\lambda\tilde{t}_{n}(\delta)}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A)}\Big{(}\exp{(-\frac{\lambda}{\sqrt{s}}\sum\limits_{i\in
S}X_{i})}\Big{)}$
$\displaystyle=(1+o(1))e^{\lambda\tilde{t}_{n}(\delta)}\Big{(}\frac{\cosh(2A-\frac{\lambda}{\sqrt{s}})}{\cosh(2A)}\Big{)}^{s}$
$\displaystyle\leq(1+o(1))e^{\lambda\tilde{t}_{n}(\delta)}e^{\frac{\tilde{t}^{2}_{n}(\delta)}{2}}\frac{1}{\cosh^{s}(2A)}$
$\displaystyle\leq(1+o(1))\exp\left(\lambda\tilde{t}_{n}(\delta)+\frac{\tilde{t}^{2}_{n}(\delta)}{2}-\frac{(\lambda+t_{n}(\delta))^{2}}{2}\right)$
(21) $\displaystyle=(1+o(1))\exp(-\frac{\lambda^{2}}{2}).$ (22)

where the first equality is by Lemma 3. Choose $\eta>0$ small enough such
that,

$2\sqrt{\frac{1-\varepsilon}{1+\delta}}(1-\eta)\frac{\tilde{t}_{n}(\delta)}{\sqrt{s}}\leq
2\sqrt{(1-\varepsilon)}(1-\eta)\tanh(A)\leq\tanh(2A)\leq\frac{\lambda+\tilde{t}_{n}(\delta)}{\sqrt{s}}.$

Hence,

$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A)}\left(Z_{S}\leq\tilde{t}_{n}(\delta)\Big{)}\leq(1+o(1))\exp\Big{(}-(2\sqrt{\frac{1-\varepsilon}{1+\delta}}(1-\eta)-1)^{2}\frac{\tilde{t}^{2}_{n}(\delta)}{2}\right).$
(23)

By (20),

$\displaystyle T_{1}$
$\displaystyle=(1+o(1))\exp\Big{(}s\\{\log\cosh(2A)-2\log\cosh(A)\\}-\log|\tilde{\mathcal{C}}_{s}|-(2\sqrt{\frac{1-\varepsilon}{1+\delta}}(1-\eta)-1)^{2}\frac{\tilde{t}^{2}_{n}(\delta)}{2}\Big{)}$
$\displaystyle\leq(1+o(1))\exp\Big{(}sA^{2}-\log|\tilde{\mathcal{C}}_{s}|-(2\sqrt{\frac{1-\varepsilon}{1+\delta}}(1-\eta)-1)^{2}\frac{\tilde{t}^{2}_{n}(\delta)}{2}\Big{)}=o(1),$
(24)

for small enough $\eta>0$. This completes the proof of (18), finishing the
proof of lower bound.

##### Proof of Theorem 1ii.ii._b_)

The proof is verbatim same as that for $\beta<1$ in part Theorem 1ii.ii._a_)
and the only change comes from applying Lemma 1 which is applicable now for
$s\ll\sqrt{n}/\log{n}$ – a condition that is part of the theorem’s assumption.

##### Proof of Theorem 1ii.ii._c_)

To prove the lower bound, fix $\varepsilon>0$ such that
$\sqrt{s}\tanh(A)(\log|\tilde{\mathcal{C}}_{s}|)^{-1/2}=2(1-\varepsilon)(1-m^{2})^{-1}$.
Defining

$L_{\pi}=\frac{1}{|\tilde{C}_{s}|}\sum_{S\in\tilde{C}_{s}}\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),$ (25)

it suffices to show $L_{\pi}\rightarrow 1$ in probability. Defining
$\Omega_{n}(S,\delta)=\\{(A_{n,S}\cup B_{n,S})^{c}\\}$ – where for any
$\delta>0$ we define
$\tilde{t}_{n}(\delta)=\sqrt{2(1+\delta)\log|\tilde{C}_{s}|}$. Subsequently,
we let

$\displaystyle\tilde{L}_{\pi}(\delta):=\frac{1}{|\tilde{C}_{s}|}\sum_{S\in\tilde{C}_{s}}\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}(\mathbf{X}\in\Omega_{n}(S,\delta)),$ (26)

and it is enough to show (16),(17),(18). The proof of type I error in Theorem
1i.i._c_) yields $\mathbb{P}(L_{\pi}\neq\tilde{L}_{\pi})\rightarrow 0$. The
proof of (17) follows similar to the Type II error of in Theorem 1i.i._c_). To
prove (18), recall that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}\left(\tilde{L}_{\pi}^{2}(\delta)\right)$
(27)
$\displaystyle=\frac{1}{|\tilde{\mathcal{C}}_{s}|^{2}}\sum_{S\in\tilde{\mathcal{C}}_{s}}\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)}(\Omega_{n}(S,\delta))$
$\displaystyle+\frac{1}{|\tilde{\mathcal{C}}_{s}|^{2}}\sum_{S_{1}\neq
S_{2}\in\tilde{\mathcal{C}}_{s}}\frac{Z^{2}(\beta,\mathbf{Q},\mathbf{0})Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}\cup
S_{2}}(A))}{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}}(A))Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{2}}(A))Z(\beta,\mathbf{Q},\mathbf{0})}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}\cup
S_{2}}(A)}(\Omega_{n}(S_{1},\delta)\cap\Omega_{n}(S_{2},\delta))$
$\displaystyle=T_{1}+T_{2},$ (28)

Here, $T_{2}\leq 2+o(1)$, because

$\frac{Z^{2}(\beta,\mathbf{Q},\mathbf{0})Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}\cup
S_{2}}(A))}{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{1}}(A))Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S_{2}}(A))Z(\beta,\mathbf{Q},\mathbf{0})}=(2+o(1))\frac{\cosh^{2s}(\beta
m+A)+\cosh^{2s}(\beta m-A)}{(\cosh^{s}(\beta m+A)+\cosh^{s}(\beta
m-A))^{2}}=2+o(1),$

where we have used $\frac{\cosh^{s}(\beta m-A)}{\cosh^{s}(\beta m+A)}=o(1)$.
To bound $T_{1}$, choose $\eta>0$ small to be specified later. Set
$\lambda=\frac{\tilde{t}_{n}(\delta)\sqrt{s}(1-\eta)}{1-m^{2}}$.

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(2A)}(Z_{S}\leq\sqrt{s}+\tilde{t}_{n}(\delta)|W_{n}>0)$
$\displaystyle\leq\exp\Big{(}{\lambda(m+\tilde{t}_{n}(\delta)/\sqrt{s})+s[\log\cosh(\beta
m+2A-\frac{\lambda}{s})-\log\cosh(\beta m+2A)]}\Big{)}$
$\displaystyle\leq\exp\Big{(}\lambda(m-\tanh(\beta
m+2A)+\frac{\tilde{t}_{n}(\delta)}{\sqrt{s}})+\frac{\lambda^{2}}{2s}\operatorname{sech}^{2}(\beta
m)+o(\log|\tilde{C}_{s}|)\Big{)}$
$\displaystyle\leq\exp\Big{(}-\frac{\lambda\tilde{t}_{n}(\delta)}{\sqrt{s}}(1-\eta)+\frac{\lambda^{2}}{2s}\operatorname{sech}^{2}(\beta
m)+o(\log|\tilde{C}_{s}|)\Big{)}$
$\displaystyle=\exp\Big{(}-(1+\varepsilon)(1-\eta)^{2}\log|\tilde{C}_{s}|+o(\log|\tilde{C}_{s}|)\Big{)},$

where the third inequality is by $\tanh(\beta m+2A)\geq
m+2A\operatorname{sech}^{2}(\beta m)$ and small $\eta>0$. Similar bound holds
for $W_{n}<0$. Therefore,

$\displaystyle T_{1}$ $\displaystyle\leq C\exp\Big{(}s[\log\cosh(\beta
m+2A)-2\log\cosh(\beta m+A)+\log\cosh(\beta
m)]-\log|\tilde{C}_{s}|-(1+\varepsilon)(1-\eta)^{2}\log|\tilde{C}_{s}|\Big{)}$
$\displaystyle\leq
C\exp\Big{(}sA^{2}-\log|\tilde{C}_{s}|-(1+\varepsilon)(1-\eta)^{2}\log|\tilde{C}_{s}|\Big{)}=o(1),$

by small $\varepsilon,\eta>0$ and since $\tanh(A)\sim A$. Therefore,
$\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(\tilde{L}^{2}_{\pi})\leq 2+o(1)$.
Hence,

$\liminf_{n\rightarrow\infty}\inf_{T}\mathrm{Risk}(T,{\Xi}(\mathcal{C}_{s},A),\beta,\mathbf{Q})\geq
1-\limsup_{n\rightarrow\infty}\frac{1}{2}\sqrt{\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}(L^{2}_{\pi})-1}>0.$

Consequently, no test is asymptotically powerful.

####  6.1.2. Proof of Theorem 2

To obtain an adaptive test, we first test the hypothesis
$H_{0,\beta}:\beta\leq 1$ vs $H_{1,\beta}:\beta>1$. This is obtained through
the test

$T_{n}^{(1)}=\mathbbm{1}\left(|\bar{\mathbf{X}}|\geq\frac{1}{\log{n}}\right).$

Subsequently, if $T_{n}^{(1)}=0$ we simply use the test

$T_{n}^{(2)}=\mathbbm{1}\left(Z_{\max}>\sqrt{2(1+\delta)\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}\right)$

for $\delta>0$ as in the proof of Theorem 1i.i._a_). In contrast, if
$T_{n}^{(1)}=1$ we estimate $\beta$ assuming the working model
“$\mathbf{X}\stackrel{{\scriptstyle\text{working}}}{{\sim}}\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}$”
using the Pseudo-likelihood method [9, 15, 10, 28] and with $\hat{\beta}_{\rm
working}$ denote this estimator we consider rejecting $H_{0}$ using

$\displaystyle T_{n}^{(3)}$
$\displaystyle=\mathbbm{1}(Z_{\max}>m(\hat{\beta}_{\rm
working})+\sqrt{2(1+\delta)(1-m^{2}(\hat{\beta}_{\rm
working}))\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|},W_{n}\geq
0)$ $\displaystyle+\mathbbm{1}(Z_{\max}>-m(\hat{\beta}_{\rm
working})+\sqrt{2(1+\delta)(1-m^{2}(\hat{\beta}_{\rm
working}))\log|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|},W_{n}<0)$

where $\delta>0$ can be chosen as in the proof of Theorem Theorem 1i.i._c_)
and $m(\beta)$ is the unique positive root of $m=\tanh(\beta m)$. Our final
$\beta$-adaptive test is thereafter given by
$T_{n}=(1-T_{n}^{(1)})T_{n}^{(2)}+T_{n}^{(1)}T_{n}^{(3)}$. We note that in
this part of the proof we do not perform the Bonferroni correction of the test
$T_{n}^{(3)}$ with a test based on conditionally centered version of
$\sum_{i=1}^{n}X_{i}$ since here $\sum_{i=1}^{n}\mu_{i}\ll s\ll n$. Therefore
as it is clear from the proof of Theorem 1i.i._c_), it suffices to only
consider the randomized scan test described through $T_{n}^{(3)}$.

We first show that uniformly over all
$\boldsymbol{\mu}\in\\{\mathbf{0}\\}\cup\Xi(\mathcal{C}_{s},A)$ one has that
$|\bar{\mathbf{X}}|=o_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(\frac{1}{\log{n}})$
for $\beta\leq 1$ and $|\bar{\mathbf{X}}|\gg\frac{1}{\log{n}}$ with
probability converging to $1$ for $\beta>1$. For the first claim, first let
$\beta\leq 1$. Then from Lemma 5 we have that
$|\bar{\mathbf{X}}|=o_{\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}}(\frac{1}{\log{n}})$
for $\beta\leq 1$. Now note that by Lemma 20 we have that there exists
constants $C_{1},C_{2}>0$ such that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}\right)\leq
C_{1}\sum_{i=1}^{n}\tanh(\mu_{i})+C_{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\tanh(\mu_{j})\left(\mathbf{Q}_{i,j}+\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\right)$

Now suppose $\beta<1$. Then we have from [18] that
$0\leq\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\lesssim
1/n$. Hence for $\beta<1$ we have

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}\right)\lesssim\sum_{i=1}^{n}\tanh(\mu_{i})\sum_{i=1}^{n}\sum_{j=1}^{n}\tanh(\mu_{j})\left(\mathbf{Q}_{i,j}+\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\right)\lesssim\sum_{j=1}^{n}\tanh(\mu_{j})\lesssim
s$

since $\|\boldsymbol{\mu}\|_{0}\leq s$. Hence under any $\boldsymbol{\mu}$ and
$\beta<1$ one has

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}^{(1)}=1)$
$\displaystyle=\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}>\frac{n}{\log{n}}\right)+\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}<-\frac{n}{\log{n}}\right)$
$\displaystyle\leq\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}>\frac{n}{\log{n}}\right)+\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(\sum_{i=1}^{n}X_{i}<-\frac{n}{\log{n}}\right)\quad\text{by
monotonicity of}\ \sum_{i=1}^{n}X_{i}$
$\displaystyle=\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\frac{\sum_{i=1}^{n}X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}{\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}>\frac{n}{\log{n}\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}-\frac{\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}{\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}\right)+o(1)$
$\displaystyle\leq\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\frac{\sum_{i=1}^{n}X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}{\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}>C_{1}\frac{\sqrt{n}}{\log{n}}-C_{2}\frac{s}{\sqrt{n}}\right)+o(1)$

where in the last line we have used the fact that by GHS inequality (Lemma 15)
and Lemma 5 we have that
$n\lesssim\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})\leq\mathrm{Var}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i=1}^{n}X_{i})\lesssim
n$ for $\beta<1$. Now note that by our assumptions
$s/\sqrt{n}\ll\sqrt{n}/\log{n}$ since $s\ll n/\log{n}$ and hence the first
term of the display above goes to $0$ uniformly in $\boldsymbol{\mu}$ for
$\beta<1$.

Turning to $\beta=1$, we have from [18] that
$0\leq\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\lesssim
1/\sqrt{n}$. Hence for $\beta=1$ we have

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})\lesssim\sum_{i=1}^{n}\tanh(\mu_{i})\sum_{i=1}^{n}\sum_{j=1}^{n}\tanh(\mu_{j})\left(\mathbf{Q}_{i,j}+\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\right)\lesssim\sum_{j=1}^{n}\tanh(\mu_{j})\lesssim
s\sqrt{n}$

since $\|\boldsymbol{\mu}\|_{0}\leq s$. Hence under any $\boldsymbol{\mu}$ and
$\beta=1$ one has

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}^{(1)}=1)$
$\displaystyle=\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}>\frac{n}{\log{n}}\right)+\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}<-\frac{n}{\log{n}}\right)$
$\displaystyle\leq\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i=1}^{n}X_{i}>\frac{n}{\log{n}}\right)+\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(\sum_{i=1}^{n}X_{i}<-\frac{n}{\log{n}}\right)\quad\text{by
monotonicity of}\ \sum_{i=1}^{n}X_{i}$
$\displaystyle=\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\frac{\sum_{i=1}^{n}X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}{\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}>\frac{n}{\log{n}\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}-\frac{\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}{\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}\right)+o(1)$
$\displaystyle\leq\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\frac{\sum_{i=1}^{n}X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}{\sqrt{\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})}}>C_{1}\frac{n^{1/4}}{\log{n}}-C_{2}\frac{s}{n^{1/4}}\right)+o(1)$

where in the last line we have used the fact that by GHS inequality (Lemma 15)
and Lemma 5 we have that
$n^{3/4}\lesssim\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i=1}^{n}X_{i})\leq\mathrm{Var}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i=1}^{n}X_{i})\lesssim
n^{3/4}$ for $\beta<1$. Now note that by our assumptions $s/n^{1/4}\ll
n^{1/4}/\log{n}$ since $s\ll\sqrt{n}/\log{n}$ and hence the first term of the
display above goes to $0$ uniformly in $\boldsymbol{\mu}$ for $\beta=1$ as
well. This shows that for any $\boldsymbol{\mu}$ one has that $T_{n}^{(1)}$
has Type I error converging to $0$ for testing $H_{0,\beta}$ vs $H_{1,\beta}$.

Next we show that uniformly over all
$\boldsymbol{\mu}\in\\{\mathbf{0}\\}\cup\Xi(\mathcal{C}_{s},A)$
$|\bar{\mathbf{X}}|\gg\frac{1}{\log{n}}$ with probability converging to $1$
for $\beta>1$. The claim is trivial for $\boldsymbol{\mu}=\mathbf{0}$ by [25].
In particular, it also follows that
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0)\leq e^{-Cn}$ for some
$C>0$ depending on $\beta>1$. Then for any $\boldsymbol{\mu}$ with
$\|\boldsymbol{\mu}\|_{\infty}\leq M$ for some $M>0$ one has

$\displaystyle\sup_{\boldsymbol{\mu}:\|\boldsymbol{\mu}\|_{\infty}\leq
M}\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0)$
$\displaystyle=\sup_{\boldsymbol{\mu}:\|\boldsymbol{\mu}\|_{\infty}\leq
M}\frac{Z(\beta,\mathbf{Q},\mathbf{0})}{Z(\beta,\mathbf{Q},\boldsymbol{\mu})}\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}\left(\mathbbm{1}(T_{n}^{(1)}=0)e^{\sum_{i=1}^{n}\mu_{i}X_{i}}\right)$
$\displaystyle=\sup_{\boldsymbol{\mu}:\|\boldsymbol{\mu}\|_{\infty}\leq
M}e^{2s\|\boldsymbol{\mu}\|_{\infty}}\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0)\leq
e^{2sM-Cn}\rightarrow 0$

since $s\ll n$. This completes the proof for $\beta>1$ for the consistency of
testing $H_{0,\beta}$ vs $H_{1,\beta}$ using $T_{n}^{(1)}$ under any
$\boldsymbol{\mu}\in\mathbb{R}_{+}^{n}$ s.t. $\|\boldsymbol{\mu}\|_{0}\leq
s\ll n$ and $\|\boldsymbol{\mu}\|_{\infty}=O(1)$. We next turn to the
consistency of the test
$T_{n}=(1-T_{n}^{(1)})T_{n}^{(2)}+T_{n}^{(1)}T_{n}^{(3)}$ for testing the
actual hypotheses (2) of interest.

First consider the case $\beta\leq 1$. Let us first consider the Type I error
of the test $T_{n}$.

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}=1)=\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0,T_{n}^{(2)}=1)+\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=1,T_{n}^{(3)}=1).$

By consistency of the test $T-n^{(1)}$ for testing $H_{0,\beta}$ vs
$H_{1,\beta}$ one has that for $\beta\leq 1$ one has
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=1)\rightarrow 0$. Hence
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=1,T_{n}^{(3)}=1)\rightarrow
0$ as well. Hence it is enough to show that
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(2)}=1)\rightarrow 0$ under
$\beta\leq 1$. However this follows by arguments verbatim to the proof of Type
I errors in Theorem 1i.i._a_) and Theorem 1i.i._b_) since the test
$T_{n}^{(2)}$ is free of $\beta$. This completes the control of Type I error
for $\beta\leq 1$. Turning to the Type II error, once again note that for any
$\boldsymbol{\mu}\in\mathcal{C}_{s}$

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}=0)=\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0,T_{n}^{(2)}=0)+\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=1,T_{n}^{(3)}=0).$

Once again by consistency of the test $T-n^{(1)}$ for testing $H_{0,\beta}$ vs
$H_{1,\beta}$ (uniformly against any $\boldsymbol{\mu}$ in our class having
$\|\boldsymbol{\mu}\|_{\infty}=O(1)$) one has that for $\beta\leq 1$ one has
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}^{(1)}=1)\rightarrow 0$
uniformly in such $\boldsymbol{\mu}$’s. Hence
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=1,T_{n}^{(3)}=1)\rightarrow
0$ uniformly as well and is enough to show that
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}^{(2)}=0)\rightarrow 0$
uniformly in $\boldsymbol{\mu}$ under $\beta\leq 1$. This once again follows
by arguments verbatim to the proof of Type II errors in Theorem 1i.i._a_) and
Theorem 1i.i._b_) since the test $T_{n}^{(2)}$ is free of $\beta$.

We next turn to the final case of analyzing the test $T_{n}$ under $\beta>1$.
Let us first consider the Type I error of the test $T_{n}$.

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}=1)=\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0,T_{n}^{(2)}=1)+\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=1,T_{n}^{(3)}=1).$

By consistency of the test $T_{n}^{(1)}$ for testing $H_{0,\beta}$ vs
$H_{1,\beta}$ one has that for $\beta>1$ one has
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0)\rightarrow 0$. Hence
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(1)}=0,T_{n}^{(2)}=1)\rightarrow
0$ as well. Hence it is enough to show that
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(T_{n}^{(3)}=1)\rightarrow 0$ under
$\beta>1$. Now note that the only dependence of the test $T_{n}^{(3)}$ on
$\hat{\beta}_{\rm working}$ is in its cutoff and the proof of the Type I error
in Theorem 1i.i._c_) shows that it is enough to show that $m(\hat{\beta}_{\rm
working})\stackrel{{\scriptstyle\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}}}{{\rightarrow}}m(\beta)$
which follows from Lemma 19. In particular, Lemma 19 is applicable since

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

using [11, (7.9)]. Hence, by Lemma 19, is applicable. Turning to the Type II
error of our test $T_{n}$ once again by consistency of the test $T_{n}^{(1)}$
for testing $H_{0,\beta}$ vs $H_{1,\beta}$ (uniformly against any
$\boldsymbol{\mu}$ in our class having $\|\boldsymbol{\mu}\|_{\infty}=O(1)$)
one has that for $\beta>1$ one has
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}^{(1)}=0)\rightarrow 0$
uniformly in such $\boldsymbol{\mu}$’s. Hence
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}^{(1)}=0,T_{n}^{(2)}=0)\rightarrow
0$ uniformly as well and is enough to show that
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(T_{n}^{(2)}=0)\rightarrow 0$
uniformly in $\boldsymbol{\mu}$ under $\beta>1$. Once again from the proof of
the Type II error in Theorem 1i.i._c_) it is enough to show that
$m(\hat{\beta}_{\rm
working})\stackrel{{\scriptstyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}}{{\rightarrow}}m(\beta)$
uniformly in $\boldsymbol{\mu}$ in our class which follows from Lemma 19.

###  6.2. Technical Lemmas for Proofs of Theorems in Section 2.1

######  Lemma 1.

Suppose $\mathbf{X}\sim\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}}$ with $\mathbf{Q}^{\rm CW}_{i,j}=\mathbf{1}(i\neq j)/n$
and 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))e^{-t^{2}_{n}(\delta)}$.

  2. (b)

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

  3. (c)

If $\beta>1,s\ll\frac{n}{\log n}$,

$P_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(Z_{S}>m\sqrt{s}+t_{n}(\delta))\leq(1+o(1))\exp\left(-\frac{t^{2}_{n}(\delta)}{2(1-m^{2})}\right)$
(30)

Further,

$P_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(Z_{S}>-m\sqrt{s}+t_{n}(\delta),W_{n}<0)\leq(1+o(1))\exp\left(-(1+o(1))\frac{t^{2}_{n}(\delta)}{2(1-m^{2})}\right)$
(31)

###### 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}^{\rm
CW}\mathbf{0}}(Z_{S}>t_{n}(\delta)$ $\displaystyle\leq 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))e^{-\lambda
t_{n}(\delta)}\cosh^{s}\left(\frac{\lambda}{\sqrt{s}}\right)\leq(1+o(1))e^{-t^{2}_{n}(\delta)},$

where 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 2 again and the $o(1)$ term does not depend on the choice
of $S$.

  3. (c)

When $\beta>1$, pick $\lambda=\frac{t_{n}(\delta)\sqrt{s}}{1-m^{2}}$. Here,
$s\tanh(\lambda/s)\ll\sqrt{n}$ and $\lambda/s\rightarrow 0$.

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(Z_{S}>m\sqrt{s}+t_{n}(\delta))$
$\displaystyle\leq\exp\left(-\frac{\lambda t}{\sqrt{s}}-\lambda
m\right)\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}\exp\left(\frac{\lambda}{s}\sum_{i\in S}X_{i}\right)$
$\displaystyle=\exp\left(-\frac{\lambda t}{\sqrt{s}}-\lambda
m\right)\frac{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(\frac{\lambda}{s}))}{Z(\beta,\mathbf{Q}^{\rm
CW},\mathbf{0})}$ $\displaystyle\leq(1+o(1))\exp\left(-\frac{\lambda
t}{\sqrt{s}}-\lambda m\right)\left(\frac{\cosh(\beta m+\lambda/s)}{\cosh(\beta
m)}\right)^{s}$ $\displaystyle=(1+o(1))\exp\left(-\frac{\lambda
t}{\sqrt{s}}-\lambda m+s\log\cosh(\beta m+\lambda/s)-s\log\cosh(\beta
m)\right)$ $\displaystyle\leq(1+o(1))\exp\left(-\frac{\lambda
t}{\sqrt{s}}\underbrace{-\lambda m(\beta)+\frac{s\lambda}{s}\tanh(\beta
m(\beta))}_{=0}+\frac{s\lambda^{2}}{2s^{2}}\operatorname{sech}^{2}(\beta
m(\beta))\right)$ $\displaystyle=(1+o(1))\exp\left(-\frac{\lambda
t}{\sqrt{s}}+\frac{\lambda^{2}}{2s}\operatorname{sech}^{2}(\beta
m(\beta))\right)$
$\displaystyle=(1+o(1))\exp\left(-\frac{t^{2}}{2(1-m^{2})}\right),$

where the second inequality is due to Lemma 2 and the third inequality occurs
since the third term of the Taylor expansion is negative.

When $W_{n}<0$, note that,

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(Z_{S}>-m\sqrt{s}+t_{n}(\delta),W_{n}<0)$
$\displaystyle\leq\exp\left(-\frac{\lambda t}{\sqrt{s}}+\lambda
m\right)\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}\exp\left(\frac{\lambda}{s}\sum_{i\in
S}X_{i}\mathbbm{1}_{W_{n}\leq 0}\right)$
$\displaystyle\leq(1+o(1))\exp\left(-\frac{\lambda
t_{n}(\delta)}{\sqrt{s}}+\lambda m\right)\left(\frac{\cosh(\beta
m-\lambda/s)}{\cosh(\beta m)}\right)^{s}$

Previously, the third term in Taylor expansion was $<0$, here we simply bound
it by $O\left(\frac{t^{3}_{n}(\delta)}{s}\right)=o(t^{2}_{n}(\delta))$.

∎

The following Lemma provides estimates for ratios of normalizing constants in
the Curie-Weiss model.

######  Lemma 2.

For $s\in[n]$ and $A,\beta>0$ let $Z_{n}(\beta,s,A)=Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))$ be the partition function of the Curie-Weiss
model $\mathbb{P}_{\beta,\mathbf{Q}^{\rm CW},\boldsymbol{\mu}_{S}(A)}$ with
$\mathbf{Q}^{\rm CW}_{i,j}=\mathbbm{1}(i\neq j)/n$ Then the following
conclusions hold for any $C>0$:

  1. (a)

If $\beta<1,s\ll\frac{n}{\log n}$ and $s\tanh(A)\ll\sqrt{n}$, then we have

$\displaystyle\frac{Z_{n}(\beta,s,A)}{Z_{n}(\beta,0,0)}=(1+o(1))\cosh(A)^{s}.$
(32)

  2. (b)

If $\beta>1,s\ll\frac{n}{\log n}$ and $s\tanh(A)\ll\sqrt{n}$ we have

$\mathbb{E}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}\left(\exp(A\sum_{i\in
S}X_{i})|W_{n}>0\right)=(1+o(1))\frac{\cosh(\beta m+A)^{s}}{\cosh(\beta
m)^{s}},$ $\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}\left(\exp(A\sum_{i\in
S}X_{i})|W_{n}<0\right)=(1+o(1))\frac{\cosh(\beta m-A)^{s}}{\cosh(\beta
m)^{s}},$

where $W_{n}$ is the auxilliary variable for the Curie-Weiss model (cf. [42,
lemma 3]). Therefore,

$\displaystyle\frac{Z_{n}(\beta,s,A)}{Z_{n}(\beta,0,0)}=(1+o(1))\frac{1}{2}\left(\frac{\cosh(\beta
m-A)^{s}}{\cosh(\beta m)^{s}}+\frac{\cosh(\beta m+A)^{s}}{\cosh(\beta
m)^{s}}\right)$ (33)

where $m$ is the unique positive root of the equation $m=\tanh(\beta m)$.

  3. (c)

If $\beta=1$ and $s\ll\frac{n}{\log n}$, then for $s\tanh(A)\ll n^{1/4}$ we
have (32) holds.

###### Proof.

We begin with the representation used in [42, lemma 3]. Define a random
variable $W_{n}$ which given $\mathbf{X}$ has a distribution
$N(\bar{\mathbf{X}},1/n)$. Then under $\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}$, given $W_{n}=w_{n}$, each $X_{i}$’s are i.i.d with

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(X_{i}=x_{i}|W_{n}=w_{n})=\frac{e^{\beta w_{n}x_{i}}}{e^{\beta
w_{n}}+e^{-\beta w_{n}}}.$

Therefore, for any $\mu_{i}\in\mathbb{R}$ one has
$\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(\exp(\mu_{i}X_{i})|W_{n})=\frac{\cosh(\mu_{i}+\beta
W_{n})}{\cosh(\beta W_{n})}$. Therefore for any
$\boldsymbol{\mu}\in\mathbb{R}^{n}$

$\displaystyle\frac{Z_{n}(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu})}{Z_{n}(\beta,\mathbf{Q}^{\rm CW},\mathbf{0})}$
$\displaystyle=\frac{\sum_{\mathbf{x}\in\\{\pm
1\\}^{n}}\exp\left(\frac{\beta}{n}\sum_{i<j}x_{i}x_{j}+\sum_{i=1}^{n}\mu_{i}x_{i}\right)}{\sum_{\mathbf{x}\in\\{\pm
1\\}^{n}}\exp\left(\frac{\beta}{n}\sum_{i<j}x_{i}x_{j}\right)}=\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}\left(\exp(\sum_{i=1}^{n}\mu_{i}X_{i})\right)$
$\displaystyle=\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}\left[\exp\left\\{\sum_{i=1}^{n}\left(\log\cosh(\mu_{i}+\beta
W_{n})-\log\cosh(\beta W_{n})\right)\right\\}\right].$ (34)

Consequently we have

$\displaystyle\frac{Z_{n}(\beta,s,A)}{Z_{n}(\beta,0,0)}=\frac{Z_{n}(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}{Z_{n}(\beta,\mathbf{Q}^{\rm
CW},\mathbf{0})}=\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(e^{T_{n}}),\quad T_{n}:=s[\log\cosh(\beta
W_{n}+A)-\log\cosh(\beta W_{n})].$ (35)

Also use [42, Lemma 3] to note that $W_{n}$ marginally has a density
proportional to $e^{-nf(w)}$, with $f(w):=\beta w^{2}/2-\log\cosh(\beta w)$.
With this we are ready to prove the lemma.

  1. (a)

To begin note that $|\log\cosh(\beta W_{n})|\leq\frac{\beta^{2}}{2}W_{n}^{2}$.
Also, a two term Taylor’s series expansion in $W_{n}$ gives

$\displaystyle\Big{|}\log\cos(\beta W_{n}+A)-\log\cosh(A)-\beta
W_{n}\tanh(A)\Big{|}\leq$ $\displaystyle\frac{\beta^{2}}{2}W_{n}^{2}.$

Combining these two and setting $B:=\tanh(A)$ we have

$|T_{n}-s\log\cosh(A)|\leq\beta|W_{n}|sB+\beta^{2}sW_{n}^{2},$

the RHS of which converges to $0$ in probability, as
$\sqrt{n}W_{n}=O_{\mathbb{P}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}}(1)$ by
part (a) of Lemma 5. Thus to prove (32), using uniform integrability it
suffices to show that

$\displaystyle\limsup_{n\rightarrow\infty}\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}e^{2T_{n}-2s\log\cosh(A)}<\infty.$ (36)

To this effect, again using the above Taylor’s expansion gives

$T_{n}-s\log\cosh(A)\leq\beta s|W_{n}|B+s\beta^{2}W_{n}^{2},$

using which the RHS (36) can be bounded as follows:

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}e^{2T_{n}-2s\log\cosh(A)}\leq\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}e^{2\beta sB|W_{n}|+2s\beta^{2}W_{n}^{2}}\leq
2\mathbb{E}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}e^{2\beta
sBW_{n}+2s\beta^{2}W_{n}^{2}}$

Setting $\lambda_{1}:=\beta(1-\beta),\lambda_{2}:=\beta$ we have

$\lambda_{1}\frac{w^{2}}{2}\leq f(w)\leq\lambda_{2}\frac{w^{2}}{2},$

which readily gives

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}e^{2\beta
sW_{n}B+s\beta^{2}W_{n}^{2}}\leq$ $\displaystyle
2\frac{\int_{\mathbb{R}}e^{2\beta
sBz+2s\beta^{2}z^{2}-n\lambda_{1}z^{2}/2}dz}{\int_{\mathbb{R}}e^{-n\lambda_{2}z^{2}/2}dz}$
$\displaystyle=$
$\displaystyle\sqrt{\frac{n\lambda_{2}}{n\lambda_{1}-4\beta^{2}s}}\text{exp}\Big{\\{}\frac{2\beta^{2}s^{2}B^{2}}{n\lambda_{1}-4\beta^{2}s}\Big{\\}},$

the RHS of which converges to $1$. Thus (36) holds, and so the proof is
complete.

  2. (b)

To begin, setting $C_{n}:=\int_{\mathbb{R}}e^{-nf(w)}dw$ we have

$\displaystyle C_{n}\mathbb{E}e^{T_{n}}=$
$\displaystyle\int_{-\infty}^{0}\prod_{i=1}^{n}e^{\log\cosh(\beta
w+\mu_{i})-\log\cosh(\beta
w)}e^{-nf(w)}dw+\int_{0}^{\infty}\prod_{i=1}^{n}e^{\log\cosh(\beta
w+\mu_{i})-\log\cosh(\beta w)}e^{-nf(w)}dw$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\prod_{i=1}^{n}e^{\log\cosh(-\beta
w+\mu_{i})-\log\cosh(-\beta
w)}e^{-nf(w)}dw+\int_{0}^{\infty}\prod_{i=1}^{n}e^{\log\cosh(\beta
w+\mu_{i})-\log\cosh(\beta w)}e^{-nf(w)}dw$ $\displaystyle\leq$ $\displaystyle
2\int_{0}^{\infty}\prod_{i=1}^{n}e^{\log\cosh(\beta w+\mu_{i})-\log\cosh(\beta
w)}e^{-nf(w)}dw,$

where the last inequality uses the fact that

$\displaystyle\log\cosh(\beta w+\mu_{i})-\log\cosh(\beta w)=$
$\displaystyle\int_{0}^{\mu_{i}}\tanh(\beta w+z)dz$ $\displaystyle\leq$
$\displaystyle\int_{0}^{\mu_{i}}\tanh(-\beta w+z)dz=\log\cosh(-\beta
w+\mu_{i})-\log\cosh(-\beta w),$

as $\tanh$ is monotone increasing. This shows that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}e^{T_{n}}$
$\displaystyle=\frac{1}{2}\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(e^{T_{n}}|W_{n}>0)+\frac{1}{2}\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(e^{T_{n}}|W_{n}<0).$

We will now show that,

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(e^{T_{n}}|W_{n}>0)=(1+o(1))\frac{\cosh(\beta
m+A)^{s}}{\cosh(\beta m)^{s}}.$ (37)

A similar argument takes care of the second term. For this, use part (b) of
Lemma 5 to note that $\Big{(}\sqrt{n}(W_{n}-m)|W_{n}>0\Big{)}=O_{p}(1)$. For
$W_{n}>0$, a Taylor’s series expansion gives

$\displaystyle\Big{|}\log\cosh(\beta W_{n}+A)-\log\cosh(\beta
m+A)-\beta(W_{n}-m)\tanh(\beta m+A)\Big{|}$ $\displaystyle\leq$
$\displaystyle\frac{\beta^{2}}{2}(W_{n}-m)^{2}$
$\displaystyle\Big{|}\log\cosh(\beta W_{n})-\log\cosh(\beta
m)-\beta(W_{n}-m)\tanh(\beta m)\Big{|}$ $\displaystyle\leq$
$\displaystyle\frac{\beta^{2}}{2}(W_{n}-m)^{2},$

which on taking a difference gives

$\Big{|}T_{n}-s(\log\cosh(\beta m+A)-\log\cosh(\beta m))\Big{|}\leq
s\tilde{B}|W_{n}-m|+\beta^{2}s(W_{n}-m)^{2},$

where $\tilde{B}:=|\tanh(\beta m+A)-\tanh(\beta m)|$. The RHS in the display
above converges to $0$ in probability, conditioned on the event $T_{n}>0$. As
before, (37) will follow from this via uniform integrability if we can show
that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}e^{2T_{n}-2s\log\cosh(\beta m+A)+2s\log\cosh(\beta m)}<\infty.$
(38)

For showing (38), again use the above Taylor’s expansion to note that

$T_{n}-s\log\cosh(\beta m+A)+s\log\cosh(\beta m)\leq
s\tilde{B}|W_{n}-m|+\beta^{2}s(W_{n}-m)^{2}.$

We now claim that on $[0,\infty)$ the function $f(w)$ satisfies

$\displaystyle\frac{\lambda_{2}}{2}(w-m)^{2}\leq
f(w)-f(m)\leq\frac{\lambda_{1}}{2}(w-m)^{2}$ (39)

for some positive constants $\lambda_{1}>\lambda_{2}$. Given the claim, a
similar calculation as in part (a) shows that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(e^{T_{n}}|W_{n}>0)\leq$ $\displaystyle
2\frac{\int_{\mathbb{R}}e^{2\beta
s\tilde{B}z+2s\beta^{2}z^{2}-n\lambda_{1}z^{2}/2}dz}{\int_{-m}^{\infty}e^{-n\lambda_{2}z^{2}/2}dz}$
$\displaystyle=$
$\displaystyle(1+o(1))\sqrt{\frac{n\lambda_{2}}{n\lambda_{1}-4\beta^{2}s}}\text{exp}\Big{\\{}\frac{2\beta^{2}s^{2}\tilde{B}^{2}}{n\lambda_{1}-4\beta^{2}s}\Big{\\}},$

which converges to $1$ as before, thus verifying (38) and hence completing the
proof of the Lemma.

It thus remains to prove (39). To this effect, note that the function $f(.)$
on $[0,\infty)$ has a unique global minima at $z=m$, and
$f^{\prime\prime}(m)>0$. Thus the function $F:[0,\infty)\mapsto\mathbb{R}$
defined by

$F(w)=\frac{f(w)-f(m)}{2(w-m)^{2}},z\neq m,\quad F(m):=f^{\prime\prime}(m)$

is continuous and strictly positive on $[0,\infty)$, and
$\lim_{t\rightarrow\infty}F(t)=\beta_{2}>0$. Thus setting
$\lambda_{2}:=\inf_{t\in[0,\infty)}F(t)$,
$\lambda_{1}:=\sup_{t\in[0,\infty)}F(t)$, it follows that $\lambda_{2}>0$ and
$\lambda_{1}<\infty$, and so the proof of (39) is complete.

  3. (c)

We now use a four term Taylor expansion to get

$\displaystyle\Big{|}\log\cosh(W_{n}+A)-\log\cosh(A)-\frac{W_{n}^{2}}{2}\text{sech}^{2}(A)|$
$\displaystyle\leq$ $\displaystyle
B|W_{n}|+\frac{1}{2}B|W_{n}|^{3}+\frac{1}{4}|W_{n}|^{4}$
$\displaystyle\Big{|}\log\cosh(W_{n})-\frac{W_{n}^{2}}{2}\Big{|}$
$\displaystyle\leq$ $\displaystyle\frac{1}{4}|W_{n}|^{4}$

This gives

$|T_{n}-s\log\cosh(A)|\leq
sB|W_{n}|+sB^{2}\frac{W_{n}^{2}}{2}+\frac{1}{2}sB|W_{n}|^{3}+\frac{1}{2}sW_{n}^{4}$

The RHS above converges to $0$ on noting that $sB\ll n^{1/4}$, and
$W_{n}=O_{p}(n^{-1/4})$ (which follows by part (c) of Lemma 5).

As before, using uniform integrability it suffices to show that

$\displaystyle\limsup_{n\rightarrow\infty}\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}e^{2T_{n}-2s\log\cosh(A)}<\infty.$ (40)

To this end, use the bound $x-\log 2\leq\log\cosh(x)\leq x$ for $x\geq 0$ to
conclude

$T_{n}-s\log\cosh(A)\leq 2s\log 2.$

Also, since

$\lim_{z\rightarrow 0}\frac{f(z)}{z^{4}}=\frac{1}{12},$

there exists $\delta\in(0,1)$ and $0<\lambda_{2}\leq\lambda_{1}<\infty$ such
that for $|z|\leq\delta$ we have

$\lambda_{1}z^{4}\leq f(z)\leq\lambda_{2}z^{4},$

which gives

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}e^{2W_{n}-2s\log\cosh(A)}\leq$ $\displaystyle e^{2s\log
2}\mathbb{P}(|T_{n}|>\delta)+\frac{\int_{-\delta}^{\delta}e^{5sB|z|-n\lambda_{1}z^{4}}dz}{\int_{-\delta}^{\delta}e^{-n\lambda_{2}z^{4}}dz},$
(41)

where the last line uses the bound

$\max\Big{(}sB^{2}z^{2},sB|z|^{3}+sz^{4}\Big{)}\leq sB|z|$

for all $|z|\leq\delta$. We now bound each of the terms in the RHS of (41).
The denominator in the RHS of (41) by a change of variable equals

$n^{-1/4}\int_{-\delta n^{1/4}}^{\delta
n^{1/4}}e^{-\lambda_{2}t^{4}}dt=(1+o(1))n^{-1/4}\int_{-\infty}^{\infty}e^{-\lambda_{2}t^{4}}dt.$

For estimating the numerator of RHS, set
$t_{n}:=\Big{(}\frac{10sB}{n\lambda_{1}}\Big{)}^{1/3}$ and note that for
$t>t_{n}$ we have $5sB|z|\leq\frac{1}{2}n\lambda_{1}z^{4}$. This gives

$\displaystyle\int_{-\delta}^{\delta}e^{5sB|z|-n\lambda_{1}z^{4}}dz\leq$
$\displaystyle
2\int_{0}^{t_{n}}e^{5sBz}dz+2\int_{t_{n}}^{\delta}e^{-\frac{n\lambda_{1}}{2}t^{4}}dt$
$\displaystyle\leq$ $\displaystyle
2t_{n}e^{5sBt_{n}}+2\int_{0}^{\infty}e^{-\frac{n\lambda_{1}}{2}t^{4}}dt$
$\displaystyle=$ $\displaystyle
2t_{n}e^{5sBt_{n}}+2n^{-1/4}\int_{0}^{\infty}e^{-\lambda_{1}t^{4}/2}dt.$

The first term above is asymptotically $2t_{n}\ll n^{-1/4}$, where we use the
bound $sB\ll n^{1/4}$. Thus the numerator in the second term in the RHS of
(41) is $O(n^{-1/4})$. Proceeding to estimate the first term, use Lemma 5 to
note that $\mathbb{P}(|W_{n}|>\delta)$ decays exponentially in $n$, whereas
$e^{2s\log 2}\leq e^{\frac{2n\log 2}{\log n}}$ is sub exponential. It thus
follows that the RHS of (41) is bounded, and so the proof of part (c) is
complete.

∎

######  Lemma 3.

Suppose $\mathbf{X}\sim\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}$ with $\mathbf{Q}^{\rm CW}_{i,j}=\mathbf{1}(i\neq
j)/n$. If $\lambda\in\mathbb{R}$, $\beta<1$, $s\ll n/\log n$,
$B:=s\max\\{\tanh(\lambda+A),\tanh(A)\\}\ll\sqrt{n}$, then

$\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}\big{(}\exp{(\lambda\sum\limits_{i\in
S}X_{i})}\big{)}=(1+o(1))\Big{(}\frac{\cosh(A+\lambda)}{\cosh(A)}\Big{)}^{s}.$
(42)

###### Proof.

Observe that,

$\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}\big{(}\exp{(\lambda\sum\limits_{i\in
S}X_{i})}\big{)}=\frac{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A+\lambda))}{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}=\frac{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A+\lambda))/Z(\beta,\mathbf{Q},\mathbf{0})}{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))/Z(\beta,\mathbf{Q},\mathbf{0})}.$

Now, Lemma 2 completes the proof. ∎

######  Lemma 4.

Suppose $\mathbf{X}\sim\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}}$ with $\mathbf{Q}^{\rm CW}_{i,j}=\mathbf{1}(i\neq j)/n$.
When $\beta>1$, let $m$ be the unique positive root of $m=\tanh(\beta m)$. Fix
$\boldsymbol{\mu}\in\Xi(s,A)$. Then the following hold uniformly in
$\boldsymbol{\mu}\in\mathbb{R}_{+}^{n}$ such that
$\sum_{\i=1}^{n}\boldsymbol{\mu}_{i}\ll n$.

  1. (a)

Fix any sequence $\kappa_{n}\rightarrow 0$. Then then there exists a sequence
$\zeta_{n}\rightarrow 0$ (depending only on the pre-fixed sequence
$\kappa_{n}$) such that,

$\sup_{\boldsymbol{\mu}:\sum_{i=1}^{n}\mu_{i}\leq\kappa_{n}n}\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}}\left(|W_{n}-m|>\zeta_{n},W_{n}\geq 0\right)\rightarrow
0$

  2. (b)

Fix any sequence $\kappa_{n}\rightarrow 0$. Then  then there exists a sequence
$\zeta_{n}\rightarrow 0$ (depending only on the pre-fixed sequence
$\kappa_{n}$) such that,

$\sup_{\boldsymbol{\mu}:\sum_{i=1}^{n}\mu_{i}\leq\kappa_{n}n}\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}}\left(|W_{n}+m|>\zeta_{n},W_{n}\leq 0\right)\rightarrow
0$

###### Proof.

For the proof of the case $W_{n}\geq 0$ we first note that by [24] there
exists $C>0$
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(|W_{n}-m|>{\zeta_{n}},W_{n}\geq
0\right)\leq\exp\left(-Cn\zeta_{n}^{2}\right)$ and hence for
$\sum_{i=1}^{n}\mu_{i}\ll n$ we have with
$\mathcal{E}_{n}=\\{|W_{n}-m|>\frac{\zeta_{n}}{\sqrt{n}},W_{n}\geq 0\\}$ and
any sequence $\kappa_{n}\rightarrow 0$ that

$\displaystyle\sup_{\boldsymbol{\mu}:\sum_{i=1}^{n}\mu_{i}\leq\kappa_{n}n}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\mathcal{E}_{n}\right)$
$\displaystyle=\sup_{\boldsymbol{\mu}:\sum_{i=1}^{n}\mu_{i}\leq\kappa_{n}n}\frac{Z(\beta,\mathbf{Q},\mathbf{0})}{Z(\beta,\mathbf{Q},\boldsymbol{\mu})}\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}\left(\mathbbm{1}(\mathcal{E}_{n})e^{\sum_{i=1}^{n}\mu_{i}X_{i}}\right)$
$\displaystyle=\sup_{\boldsymbol{\mu}:\sum_{i=1}^{n}\mu_{i}\leq\kappa_{n}n}e^{2\sum_{i=1}^{n}\mu_{i}}\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(\mathcal{E}_{n})\leq
e^{2\sum_{i=1}^{n}\boldsymbol{\mu}_{i}-Cn\zeta_{n}^{2}}\rightarrow 0$

whenever $n\zeta_{n}^{2}\gg\kappa_{n}n$. This completes the proof of the
lemma. For the case $W_{n}\leq 0$ [24] there exists $C>0$
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}\left(|W_{n}+m|>{\zeta_{n}},W_{n}\geq
0\right)\leq\exp\left(-Cn\zeta_{n}^{2}\right)$ and the rest of the proof is
similar.

∎

The next lemma follows from [25, Theorems 1-3].

######  Lemma 5.

Suppose $\mathbf{X}\sim\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}}$ with $\mathbf{Q}^{\rm CW}_{i,j}=\mathbbm{1}(i\neq
j)/n$.

  1. (a)

If $\beta\in(0,1)$ then under $\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}$ we have

$\sqrt{n}\bar{\mathbf{X}}\stackrel{{\scriptstyle
d}}{{\rightarrow}}N\left(0,\frac{1}{1-\beta}\right).$

  2. (b)

If $\beta>1$ then under $\mathbb{P}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}$ we
have

$\sqrt{n}(\bar{\mathbf{X}}-m|\bar{\mathbf{X}}>0)\stackrel{{\scriptstyle
d}}{{\rightarrow}}N\left(0,\frac{1-m^{2}}{1-\beta(1-m^{2})}\right),$

where $m$ is the unique positive root of the equation $t=\tanh(\beta t)$.

  3. (c)

If $\beta=1$ then under $\mathbb{P}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}$ we
have

$n^{1/4}\bar{\mathbf{X}}\stackrel{{\scriptstyle d}}{{\rightarrow}}Y,$

where $Y$ is a random variable with density proportional to $e^{-y^{4}/12}$.

###  6.3. Proof of Results in Section 2.2

####  6.3.1. Proof of Theorem 3

We will divide the proof into three parts based on high $(\beta<1)$, critical
$(\beta=1)$, and low $(\beta>1)$ temperature. Throughout we will use
$\mathbf{Q}$ for either scaled adjacency 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)$.

##### Proof for upper bound in High Temperature $(0\leq\beta<1)$ Regime:

We first focus on the upper bound. As before, the optimal test is given the by
the scan test which rejects for large values of $Z_{\max}:=\max\limits_{S\in
S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})}Z_{S}$ (recall that
for $S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ we defined
$Z_{S}=\sum_{i\in S}X_{i}/\sqrt{s}$). The cut-off for the test is decided by
the moderate deviation behavior of $Z_{S}$’s given in Lemma 10 – which implies
that for any $\delta>0$, the test given by
$T_{n}(\delta)=\mathbf{1}\left\\{Z_{\max}>\sqrt{2(1+\delta)\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}\right\\}$
has Type I error converging to $0$.

Turning to the Type II error, consider any
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\in\Xi(\mathcal{C}_{s},A)$.
First note that by GHS inequality
$\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in\tilde{S}^{\star}}X_{i})\leq\mathrm{Var}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i\in\tilde{S}^{\star}}X_{i})=O(s)$.
As a result,
$\frac{\sum_{i\in\tilde{S^{\star}}}(X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i}))}{\sqrt{s}}=O_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(1)$.
Therefore, as usual it is enough to show that there exists $\delta>0$ such
that
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)\rightarrow-\infty$.
To show this end, first let $S^{\star}\in\mathcal{C}_{s}$ be such that the
signal lies on $S^{\star}$ i.e. for all $i\in S^{\star}$ one has
$\boldsymbol{\mu}_{i}\geq A$. Note that by monotonicity arguments it is enough
to consider $\boldsymbol{\mu}_{i}=A$. By definition of covering, we can find a
$\tilde{S}^{\star}\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ such
that $\gamma\left(\tilde{S}^{\star},S^{\star}\right)\leq\varepsilon_{n}$ i.e.
$|\tilde{S}^{\star}\cap S^{\star}|\geq s(1-\varepsilon_{n}/\sqrt{2})$.
Thereafter note that by Lemma 20 we have that

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

However, by [18, Lemma 9 (a) and Theorem 7] we have that

$\displaystyle 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})$
$\displaystyle\lesssim\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}{s}\left(\frac{|\tilde{S}^{\star}\cap
S^{\star}||S^{\star}|}{n}+|\tilde{S}^{\star}\cap S^{\star}|\right)$
$\displaystyle\leq\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|s}}{{n}}+\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}\ll
As,$

since $\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}\ll s\ll
n/\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}$. Consequently,
we immediately have that there exists $\epsilon>0$ such that

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)$
$\displaystyle\geq
As(1+o(1))\geq\sqrt{2(1+\epsilon)s\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$

Therefore, we can conclude that for any $\delta<\epsilon$ we have
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)\rightarrow-\infty$.
This completes the proof of the upper bound for $0<\beta<1$.

##### Proof for upper bound at Critical Temperature $(\beta=1)$ Regime:

Similar to $\beta<1$ regime, the optimal test is given the by the scan test
which rejects for large values of $Z_{\max}:=\max\limits_{S\in
S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})}Z_{S}$ (recall that
for $S\in\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})$ we defined
$Z_{S}=\sum_{i\in S}X_{i}/\sqrt{s}$). The cut-off for the test is decided by
the moderate deviation behavior of $Z_{S}$’s given in Lemma 10 – which implies
that for any $\delta>0$, the test given by
$T_{n}(\delta)=\mathbf{1}\left\\{Z_{\max}>\sqrt{2(1+\delta)\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}\right\\}$
has Type I error converging to $0$.

Turning to the Type II error, we again consider any
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\in\Xi(\mathcal{C}_{s},A)$.
First note that by GHS inequality
$\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in\tilde{S}^{\star}}X_{i})\leq\mathrm{Var}_{\beta,\mathbf{Q},\mathbf{0}}(\sum_{i\in\tilde{S}^{\star}}X_{i})=O(s)$
even for $\beta=1$ since $s\ll\frac{\sqrt{n}}{\log{n}}$ by appealing to [18,
Lemma 9(c)]. Hence, it is enough to show that there exists $\delta>0$ such
that
$t_{n}(\delta)-\frac{1}{\sqrt{s}}\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\left(\sum_{i\in\tilde{S}^{\star}}X_{i}\right)\rightarrow-\infty$.
As before, let $S^{\star}\in\mathcal{C}_{s}$ be such that the signal lies on
$S^{\star}$ i.e. for all $i\in S^{\star}$ one has $\boldsymbol{\mu}_{i}\geq
A$. By monotonicity arguments it is enough to consider
$\boldsymbol{\mu}_{i}=A\mathbbm{1}_{i\in S^{\star}}$. Following (43), it is
enough to lower bound $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})$.
By [18, Lemma 9 (c) and Theorem 7], we have that

$\displaystyle 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})$
$\displaystyle\lesssim\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}{s}\left(\frac{|\tilde{S}^{\star}\cap
S^{\star}||S^{\star}|}{\sqrt{n}}+|\tilde{S}^{\star}\cap S^{\star}|\right)$
$\displaystyle\leq\frac{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|s}}{\sqrt{n}}+\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}\ll
As,$

since $\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}\ll
s\ll\frac{n}{\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$.
This completes the proof of the upper bound for $\beta=1$.

##### Proof for upper bound in Low Temperature $(\beta>1)$ Regime:

To prove the upper bound on detection threshold, we will use the same
randomized test as described in Theorem 1i.i._c_). Let the rejection region of
the test be denoted by $\Omega_{n}$. Using [17, Theorem 1.6], we obtain

$\log\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(\Omega_{n})\leq
C_{\delta}\Big{(}\log\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(\Omega_{n})+\|\mathbf{Q}\|^{2}_{F}+\sum_{i=1}^{n}(R_{i}-1)^{2}\Big{)}.$

Now, $\mathbb{P}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}(\Omega_{n})=o(1)$ by
Theorem 1i.i._c_). The error term in RHS is $O(1)$ by [17, Section 1.2].
Hence, type-I error of the proposed test converges to $0$.

For the type-II error, fix $\eta>0$ and
$\tanh(A)=\sqrt{2(1+\delta)^{2}(1-m^{2})^{-1}\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}/s}$.
To get the desired cut-off of the test, take $\delta>0$ to be chosen later and
set
$t_{n}(\delta)=\sqrt{2(1+\delta)(1-m^{2})\log{|\mathcal{N}(\mathcal{C}_{s},\gamma,\varepsilon_{n})|}}$.
Assume $\boldsymbol{\mu}$ be the true signal with support $S^{\star}$ and we
scan over $S$ such that $\gamma(S,S^{\star})\leq\varepsilon_{n}=o(1)$. We will
show that $\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in
S}X_{i}>ms+t\sqrt{s}|\bar{\mathbf{X}}\geq 0)\rightarrow 1$. Note that,

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in
S}X_{i}>ms+t\sqrt{s}|\bar{\mathbf{X}}\geq 0)$
$\displaystyle=\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\frac{\sum_{i\in
S}X_{i}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in
S}X_{i}|\bar{\mathbf{X}}>0)}{\sqrt{Var_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in
S}X_{i}|\bar{\mathbf{X}}>0)}}>\frac{ms+t\sqrt{s}-\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in
S}X_{i}|\bar{\mathbf{X}}>0)}{\sqrt{Var_{\beta,\mathbf{Q},\boldsymbol{\mu}}(\sum_{i\in
S}X_{i}|\bar{X}>0)}}|\bar{\mathbf{X}}\geq 0)$

Since LHS is $O_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(1)$, it is
enough to show the RHS (henceforth denoted by $T_{n}$) converges to $-\infty$.
Defining $\alpha_{n}=\sqrt{\frac{\log n}{n}}$, we obtain the following
estimates from [18, Lemma 9] for some absolute constants $c_{i}>0$, $i\in[3]$:

$\displaystyle\max_{i,j}\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j}|\bar{\mathbf{X}}\geq
0)\leq\frac{c_{1}}{n}$ (44)
$\displaystyle\max_{i}|\mathrm{Var}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i}|\bar{X}\geq
0)-\operatorname{sech}^{2}(\beta m+\mu_{i})|\leq c_{2}\alpha_{n}$ (45)
$\displaystyle\max_{i}|\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i}|\bar{X}\geq
0)-\tanh(\beta m+\mu_{i})|\leq c_{3}\alpha_{n}.$ (46)

All the above statements hold with high probability with respect to the
randomness of $\mathbb{G}_{n}$.

Using the bounds, we obtain

$\displaystyle T_{n}$ $\displaystyle\leq\frac{ms-
t_{n}(\delta)\sqrt{s}-\sum_{i\in S}\tanh(\beta
m+\mu_{i})+sc_{3}\alpha_{n}}{\sqrt{\sum_{i\in S}\operatorname{sech}^{2}(\beta
m+\mu_{i})+sc_{2}\alpha_{n}-\frac{cs^{2}}{n}}}\leq\frac{ms-
t_{n}(\delta)\sqrt{s}-s\tanh(\beta
m+A)+sc_{3}\alpha_{n}}{\sqrt{s\operatorname{sech}^{2}(\beta
m+A)+sc_{2}\alpha_{n}-\frac{cs^{2}}{n}}}$
$\displaystyle\leq\frac{1}{C\sqrt{s}}\left(ms-
t_{n}(\delta)\sqrt{s}-s\big{(}m-(1+o(1)A\operatorname{sech}^{2}(\beta
m)\big{)}+sc_{3}\alpha_{n}\right)$
$\displaystyle\leq\frac{1}{C}\left(-t_{n}(\delta)+As(1+o(1))(1-m^{2})+o(As)\right),$

since $\alpha_{n}=o(A)$. By choosing $\delta$ based on $\eta$, the final bound
converges to $\infty$.  The same calculation holds for
$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}\big{(}\sum_{i\in
S}X_{i}>-ms+t\sqrt{s}|\bar{\mathbf{X}}<0\big{)}$ yielding Type-II error
converging to $0$.

##### Proof for lower bound in $\beta>0$ Regime:

To prove the lower bound, fix $\beta>$ and $\varepsilon>0$ such that
$\sqrt{s}\tanh(A)(\log|\tilde{\mathcal{C}}_{s}|)^{-1/2}=2(1-\varepsilon)c_{\beta}$
where $c_{\beta}=1$ if $\beta\leq 1$, and $(1-m^{2})^{-1}$ otherwise. Suppose
there exists a test with rejection region $\Omega_{n}$ which can test $H_{0}$
vs $H_{1}$. Hence,
$\mathbb{P}_{\beta,\mathbf{Q},\mathbf{0}}(\Omega_{n})\rightarrow 0$. Using
Lemma 6, we have $\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(\Omega_{n})\rightarrow 0$. However, since every test not
asymptotically powerful for Curie-Weiss model in this regime of signal,
implying that, $\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(\Omega^{c}_{n})\geq\eta$, for some $\eta>0$ for
all large enough $n$. This implies, using Lemma 6, there exists $\nu>0$ such
that $\mathbb{P}_{\beta,\mathbf{Q},\mu_{S}(A)}(\Omega_{n})\geq\nu$. Hence, the
type-I and type-II errors cannot converge to $0$ simultaneously completing the
proof of the lower bound.

####  6.3.2. Proof of Theorem 4

To obtain an adaptive test, we apply the same procedure as described by the
proof of Theorem 2. The proof of type-I error convergence when
$\boldsymbol{\mu}=0$ follows from concentration of $\bar{\mathbf{X}}$ which is
immediate by [17, Theorem 1.1, Theorem 1.2]. For general $\boldsymbol{\mu}$,
we only require the fact
$\mathrm{Cov}_{\beta,\mathbf{Q},\boldsymbol{\mu}}(X_{i},X_{j})\lesssim 1/n$
which follows from [18, Lemma 9]. Finally we also can obtain consistent
estimator of $\beta$ thanks to [11, Corollary 3.1, Corollary 3.2] and Lemma
19. This completes our proof exactly as Theorem 2.

###  6.4. Technical Lemmas for Proofs of Theorems in Section 2.2

######  Lemma 6.

Fix $\beta>0$. Let $\mathbf{Q}^{\rm CW}$ be the scaled adjacency matrix of the
complete graph and $\mathbf{Q}$ is 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)$. Fix any $\delta>0$. For any event
$\mathcal{E}_{n}$: the following holds with probability $\geq 1-\delta$: If
$\exists\eta>0$ such that $\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mu_{S}(A)}(\mathcal{E}_{n})\geq\eta$, then $\exists\nu>0$ such that
$\mathbb{P}_{\beta,\mathbf{Q},\mu_{S}(A)}(\mathcal{E}_{n})>\nu$.

###### Proof.

Defining $\mathcal{A}_{n}:=G_{n}-11^{T}/n+I/n$, note that

$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}(\mathcal{E}_{n})=\frac{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))}\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\frac{\beta}{2}\sigma^{\top}\mathcal{A}_{n}\sigma}\mathbbm{1}_{\sigma\in\mathcal{E}_{n}}.$

For the auxiliary variable $W_{n}$, define a vector
$\tilde{T}_{n}=\tilde{T}_{n}(W_{n})$ such that $\tilde{T}_{n,i}=\tanh(\beta
W_{n}+A\mathbbm{1}_{i\in S})$. Observe that,

$\sigma^{\top}\mathcal{A}_{n}\sigma=(\sigma^{\top}-\tilde{T}_{n})\mathcal{A}_{n}(\sigma-\tilde{T}_{n})+2\tilde{T}^{\top}_{n}\mathcal{A}_{n}(\sigma-\tilde{T}_{n})+\tilde{T}^{\top}_{n}\mathcal{A}\tilde{T}_{n}=:Y_{n}+\tilde{T}^{\top}_{n}\mathcal{A}\tilde{T}_{n}.$

Define the good set $J_{n,\varepsilon}:=\\{m-\varepsilon\leq|W_{n}|\leq
m+\varepsilon\\}$. Then,

$\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}(\mathcal{E}_{n})\geq\frac{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))}\left(\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\sigma^{\top}\mathcal{A}_{n}\sigma}\mathbbm{1}_{J_{n,\varepsilon}}\right)$
(47)

The ratio of partition function is $\geq 1/C_{u}$ for some $C_{u}>0$, w.p.
$\geq 1-\delta$ by Lemma 8.

To analyse the expectation above, define $A_{M}=\\{\sigma:|Y_{n}|\leq M\\}$
for some $M>0$ and observe that,

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\frac{\beta}{2}\sigma^{\top}\mathcal{A}_{n}\sigma}\mathbbm{1}_{J_{n,\varepsilon}}\mathbbm{1}_{\sigma\in\mathcal{E}_{n}}$
$\displaystyle\geq\mathbb{E}\left(\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}\Big{(}e^{\frac{\beta}{2}\sigma^{\top}\mathcal{A}_{n}\sigma}\mathbbm{1}_{J_{n,\varepsilon}}\mathbbm{1}_{\sigma\in\mathcal{E}_{n}}\mathbbm{1}_{A_{M}}|W_{n}\Big{)}\right)$
$\displaystyle\geq
e^{-\frac{\beta}{2}M}\mathbb{E}\left(e^{\frac{\beta}{2}\tilde{T}^{\top}_{n}\mathcal{A}\tilde{T}_{n}}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}(J_{n,\varepsilon}\cap\mathcal{E}_{n}\cap
A_{M}|W_{n})\right)$

The proof of Lemma 8 yields $\exists\theta>0$ and $\delta>0$ small enough such
that
$\inf_{W_{n}}\exp(\frac{\beta}{2}\tilde{T}_{n}(W_{n})^{T}\mathcal{A}_{n}\tilde{T}_{n}(W_{n}))\geq
e^{-\theta}$ with probability $\geq 1-\delta$. Therefore,

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\frac{\beta}{2}\sigma^{\top}\mathcal{A}_{n}\sigma}\mathbbm{1}_{J_{n,\varepsilon}}\mathbbm{1}_{\sigma\in\mathcal{E}_{n}}\geq
e^{-\frac{\beta}{2}M-\theta}\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}(J_{n,\varepsilon}\cap\mathcal{E}_{n}\cap
A_{M}).$

By Hanson-Wright inequality(cf. Lemma 21), pick $M$ large enough such that
$\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(A_{M}|W_{n})\geq 1-\eta/4$. Hence,
$\mathbb{P}_{\beta,\mathbf{Q}^{\rm CW},\boldsymbol{\mu}_{S}(A)}(A_{M})\geq
1-\eta/4$ By picking $\varepsilon>0$ small enough, we can also get
$\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(J_{n,\varepsilon})\geq 1-\eta/4$. Hence,

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\frac{\beta}{2}\sigma^{\top}\mathcal{A}_{n}\sigma}\mathbbm{1}_{J_{n,\varepsilon}}\geq\frac{\eta}{2}e^{-\frac{\beta}{2}M-\theta}=:\nu>0.$

This concludes the proof of this lemma. ∎

######  Lemma 7.

There exists a constant $C_{\varepsilon}>0$ such that

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(J^{c}_{n,\varepsilon})\leq e^{-Cn},$

where $\mathbf{Q}^{\rm CW}$ corresponds to the coupling matrix of a Curie-
Weiss model on $n$ vertices.

###### Proof.

$\displaystyle\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(J^{c}_{n,\varepsilon})$
$\displaystyle=\frac{Z(\beta,\mathbf{Q}^{\rm
CW},\mathbf{0})}{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}\mathbb{E}_{\beta,\mathbf{Q},\mathbf{0}}\left(e^{A\sum_{i\in
S}{X_{i}}}\mathbbm{1}_{J^{c}_{n,\varepsilon}}\right)$ $\displaystyle\leq
e^{As}\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\mathbf{0}}(J^{c}_{n,\varepsilon})\leq e^{As-Cn},$

for some $C>0$ depending on $\varepsilon>0$ (where the proof of
$\mathbb{P}_{\beta,\mathbf{Q}^{\rm CW},\mathbf{0}}(J^{c}_{n,\varepsilon})\leq
e^{-Cn}$ follows from [24]). The proof follows from the assumption that $As\ll
n$. ∎

######  Lemma 8.

Let $\mathbf{Q}^{\rm CW}_{i,j}$ denote the coupling matrix of Curie-Weiss
model and $\mathbf{Q}$ be the scaled 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)$. Then for any $\delta>0$ the following holds with
probability $\geq 1-\delta$: for any $\beta>0,\boldsymbol{\mu}_{S}(A)$:

$\displaystyle
C_{l}\leq\frac{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))}{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}\leq C_{u}\quad,$

for constants $C_{l},C_{u}$ depending on $\beta,\delta$.

###### Proof.

Define $\mathcal{A}_{n}:=G-\mathbf{1}\mathbf{1}^{T}+I/n$. For the auxiliary
variable $W_{n}$, define a vector $\tilde{T}_{n}=\tilde{T}_{n}(W_{n})$ such
that $\tilde{T}_{n,i}=\tanh(\beta W_{n}+A\mathbbm{1}_{i\in S})$. Observe that,

$\mathbf{X}^{\top}\mathcal{A}_{n}\mathbf{X}=(\mathbf{X}-\tilde{T}_{n})^{\top}\mathcal{A}_{n}(\mathbf{X}-\tilde{T}_{n})+2\tilde{T}^{\top}_{n}\mathcal{A}_{n}(\mathbf{X}-\tilde{W}_{n})+\tilde{T}^{\top}_{n}\mathcal{A}\tilde{T}_{n}=:Y_{n}+\tilde{T}^{\top}_{n}\mathcal{A}\tilde{T}_{n}.$

Define the good set $J_{n,\varepsilon}:=\\{m-\varepsilon\leq|W_{n}|\leq
m+\varepsilon\\}$, where $m$ is the unique positive root of $m=\tanh(\beta
m)$. For the upper bound, note that,

$\displaystyle\frac{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))}{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}$
$\displaystyle=\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}\Big{(}e^{\frac{\beta}{2}\mathbf{X}^{T}\mathcal{A}_{n}\mathbf{X}}\Big{)}$
$\displaystyle=\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\mathbf{X}^{\top}\mathcal{A}_{n}\mathbf{X}}\mathbbm{1}_{J^{c}_{n,\varepsilon}}+\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\mathbf{X}^{\top}\mathcal{A}_{n}\mathbf{X}}\mathbbm{1}_{J_{n,\varepsilon}},$

To bound the first summand, note that for any $\delta>0$ one has that there
exists a sequence $\epsilon_{n}(\delta)\rightarrow 0$ such that with
probability $1-\epsilon_{n}(\delta)$ one has that $\|\mathcal{A}_{n}\|_{\rm
op}\leq n^{-1/2+\delta}$ for either $G(n,p)$ [48, Theorem 1.1] or for random
regular graph [47, Theorem A]. As a result, for any $\delta>0$ one has that
with probability with probability $1-\epsilon_{n}(\delta)$,
$\sup\limits_{\sigma\in\\{\pm\\}^{n}}e^{\mathbf{X}^{T}\mathcal{A}_{n}\mathbf{X}}\leq
e^{n^{1/2+\delta}}$. Subsequently, with probability larger than
$1-\epsilon_{n}(\delta)$ the following hold

$\displaystyle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\sigma^{\top}\mathcal{A}_{n}\sigma}\mathbbm{1}_{J^{c}_{n,\varepsilon}}\leq
e^{n^{1/2+\delta}}\mathbb{P}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(J^{c}_{n,\varepsilon}).$

This inequality and Lemma 7 yields that the first summand is $o(1)$. To
analyze $\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}e^{\mathbf{X}^{\top}\mathcal{A}_{n}\mathbf{X}}\mathbbm{1}_{J_{n,\varepsilon}}$
we plan to invoke Hanson-Wright inequality (cf. Lemma 21). To this end, we
choose $\varepsilon>0$ small enough such that

$\lim\sup\max_{i}s_{\tilde{T}_{n,i}}\lambda_{1}(\beta\mathcal{A}_{n})<1,$

where $s$ in Lemma 21. The choice of $\varepsilon$ is possible since $A=o(1)$.
Now, we apply 21 on $\mathbb{E}(e^{\frac{\beta}{2}Y_{n}}|W_{n})$ and the error
term in Lemma 21 is $O(1)$ as shown in [17, Section 1.2]. Hence, the proof
concludes once we observe that $\log\mathbb{E}^{\rm
CW}e^{\tilde{T}^{\top}_{n}\mathcal{A}\tilde{T}_{n}}=O(1)$ uniformly over $S$.
To see this, note that it is enough to show that for any $\delta>0$ there
exists a $C_{\delta}>0$ such that
$\sup_{W_{n}}\exp(\tilde{T}_{n}(W_{n})^{T}\mathcal{A}_{n}\tilde{T}_{n}(W_{n}))\leq
C_{\delta}$ with probability $\geq 1-\delta$ under either Erdős-Rényi
randomness or random regular graph. To that end, note that with $S(\mu)$
denoting the support of $\boldsymbol{\mu}$ one has

$\displaystyle\tilde{T}_{n}(W_{n})^{T}\mathcal{A}_{n}\tilde{T}_{n}(W_{n})$
$\displaystyle=T_{1}+2T_{2}+T_{3}$

where

$\displaystyle T_{1}$ $\displaystyle=\frac{1}{\tilde{d}}\sum_{(i,j)\in
S(\boldsymbol{\mu})^{c}\times S(\boldsymbol{\mu})^{c}}\tanh^{2}(\beta
W_{n})\left(G_{i,j}-\frac{\tilde{d}}{n}\right);$ $\displaystyle T_{2}$
$\displaystyle=\frac{1}{\tilde{d}}\sum_{(i,j)\in S(\boldsymbol{\mu})\times
S(\boldsymbol{\mu})^{c}}\tanh(\beta W_{n}+\mu_{i})\tanh(\beta
W_{n})\left(G_{i,j}-\frac{\tilde{d}}{n}\right);$ $\displaystyle T_{3}$
$\displaystyle=\frac{1}{\tilde{d}}\sum_{(i,j)\in S(\boldsymbol{\mu})\times
S(\boldsymbol{\mu})}\tanh(\beta W_{n}+\mu_{i})\tanh(\beta
W_{n}+\mu_{j})\left(G_{i,j}-\frac{\tilde{d}}{n}\right).$

Above $\tilde{d}=np$ when $\mathbb{G}_{n}\sim\mathcal{G}_{n}(n,p)$ and
$\tilde{d}=d$ when $\mathbb{G}_{n}\sim\mathcal{G}_{n}(n,d)$. In particular, in
that case

$\displaystyle T_{1}$ $\displaystyle=\tanh^{2}(\beta
W_{n})\frac{1}{\tilde{d}}\sum_{(i,j)\in S(\boldsymbol{\mu})^{c}\times
S(\boldsymbol{\mu})^{c}}\left(G_{i,j}-\frac{\tilde{d}}{n}\right)$
$\displaystyle=O_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(1)O_{\mathbb{P}_{G_{n}}}\left(\frac{(n-s)}{\tilde{d}}\right)\quad\text{by
Lemma \ref{lem:random_regular_covariance}}.$

Similarly,

$\displaystyle T_{2}$ $\displaystyle=\tanh(\beta W_{n})\tanh(\beta
W_{n}+A)\frac{1}{\tilde{d}}\sum_{(i,j)\in S(\boldsymbol{\mu})\times
s(\boldsymbol{\mu})^{c}}\left(G_{i,j}-\frac{\tilde{d}}{n}\right)$
$\displaystyle=O_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(1)O_{\mathbb{P}_{G_{n}}}\left(\frac{\sqrt{(n-s)s}}{\tilde{d}}\right)\quad\text{by
Lemma \ref{lem:random_regular_covariance}},$

and

$\displaystyle T_{3}$ $\displaystyle=\tanh^{2}(\beta
W_{n}+A)\frac{1}{\tilde{d}}\sum_{(i,j)\in S(\boldsymbol{\mu})\times
s(\boldsymbol{\mu})}\left(G_{i,j}-\frac{\tilde{d}}{n}\right)$
$\displaystyle=O_{\mathbb{P}_{\beta,\mathbf{Q},\boldsymbol{\mu}}}(1)O_{\mathbb{P}_{G_{n}}}\left(\frac{\sqrt{(n-s)s}}{\tilde{d}}\right)\quad\text{by
Lemma \ref{lem:random_regular_covariance}},$

These estimates immediately verifies claim that $T_{j}$’s $O_{\mathbb{P}}(1)$
whenever $\tilde{d}=\Theta(n)$ – which is guaranteed by either $p=\Theta(1)$
when $\mathbb{G}_{n}\sim\mathcal{G}_{n}(n,p)$ or $d=\Theta(n)$ when
$\mathbb{G}_{n}\sim\mathcal{G}_{n}(n,d)$.

For the lower bound on ratio of partition functions we begin by noting that by
convexity of $\mathbf{Q}\rightarrow\log{Z(\beta,\mathbf{Q},\boldsymbol{\mu})}$
for every $\boldsymbol{\mu}$,444for any differentiable convex function
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ one has $f(y)-f(x)\geq\langle\nabla
f(x),y-x\rangle$

$\displaystyle\exp\left(\beta\langle\mathbb{E}_{\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A)}(\hat{\Sigma}),-\Delta_{\mathbf{Q}}\rangle_{\rm
TR}\right)\leq\frac{Z(\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A))}{Z(\beta,\mathbf{Q}^{\rm
CW},\boldsymbol{\mu}_{S}(A))}\leq\exp\left(-\beta\langle\mathbb{E}_{\beta,\mathbf{Q},\boldsymbol{\mu}_{S}(A)}(\hat{\Sigma}),\Delta_{\mathbf{Q}}\rangle_{\rm
TR}\right)$

where $\hat{\Sigma}_{i,j}=X_{i}X_{j}$,