15.1cm25.0cm

# Emergence of near-TAP free energy functional in the SK model at high
temperature

Véronique Gayrard  V. Gayrard
Aix Marseille Univ, CNRS, I2M, Marseille, France
<EMAIL_ADDRESS>
###### Abstract.

We study the SK model at inverse temperature ${\beta}>0$ and strictly positive
field $h>0$ in the region of $({\beta},h)$ where the replica-symmetric formula
is valid. An integral representation of the partition function derived from
the Hubbard-Stratonovitch transformation combined with a duality formula is
used to prove that the infinite volume free energy of the SK model can be
expressed as a variational formula on the space of magnetisations, $m$. The
resulting free energy functional differs from that of Thouless, Anderson and
Palmer (TAP) by the term
$-\frac{{\beta}^{2}}{4}\left(q-q_{\text{EA}}(m)\right)^{2}$ where
$q_{\text{EA}}(m)$ is the Edwards-Anderson parameter and $q$ is the minimiser
of the replica-symmetric formula. Thus, both functionals have the same
critical points and take the same value on the subspace of magnetisations
satisfying $q_{\text{EA}}(m)=q$. This result is based on an in-depth study of
the global maximum of this near-TAP free energy functional using Bolthausen’s
solutions of the TAP equations, Bandeira & van Handel’s bounds on the spectral
norm of non-homogeneous Wigner-type random matrices, and Gaussian comparison
techniques. It holds for $({\beta},h)$ in a large subregion of the de Almeida
and Thouless high-temperature stability region.

###### Key words and phrases:

Spin glasses, Sherrington and Kirkpatrick model, TAP free energy functional

###### 2000 Mathematics Subject Classification:

82D30,60F15

V. Gayrard would like to thank the Institute for Applied Mathematics of the
University of Bonn for its kind hospitality during the writing of this work.
Funding for her stay was provided by the Gay Lussac-Humboldt Research Award of
the Alexander von Humboldt Foundation and the Bonn Research Chair program of
the Hausdorff Center for Mathematics.

##  1\. Introduction

###  1.1. Background, motivation and main result

The Hamiltonian of the Sherrington and Kirkpatrick model (hereafter SK model)
at inverse temperature ${\beta}>0$ and external field $h\geq 0$ is the random
function defined on $\Sigma_{N}\equiv\\{-1,1\\}^{N}$ by

$H_{N,{\beta},h}({\sigma})=-{\beta}\frac{1}{2\sqrt{N}}\sum_{1\leq i,j\leq
N}J_{ij}{\sigma}_{i}{\sigma}_{j}-h\sum_{1\leq i\leq N}{\sigma}_{i}$ (1.1)

where ${\sigma}=({\sigma}_{i})_{1\leq i\leq n}\in\Sigma_{N}$ and, given a
collection $(g_{ij})_{1\leq i,j\leq N}$ of i.i.d. Gaussian random variables
with variance $1/N$, $J_{N}=(J_{ij})_{1\leq i,j\leq N}$ is the symmetric
matrix with entries

$\frac{J_{ij}}{\sqrt{N}}=\frac{1}{\sqrt{2}}\left(g_{ij}+g_{ji}\right),\quad
1\leq i,j\leq N.$ (1.2)

Although the explicit representation (1.2) comes into play only in Section 3
and 4, we introduce it now in order to avoid the confusion of having to change
the underlying probability space during the proof. We call this probability
space $({\Omega},{\mathcal{F}},{\mathbb{P}})$.

Denoting by $Z_{N,{\beta},h}$ the partition function associated to (1.1)

$Z_{N,{\beta},h}=\sum_{{\sigma}\in\Sigma_{N}}e^{-H_{N,{\beta},h}({\sigma})}$
(1.3)

the free energy, $F_{N,{\beta},h}$, is defined as111The above definitions and
terminology are not the standards of physics (in particular, $h$ should be
replaced by ${\beta}h$ and (1.4) does not define the free energy but the
pressure, the free energy being the quantity $-{\beta}^{-1}F_{N,{\beta},h}$).
However, they have become commonly used in mathematics, especially in the
publications to which we will refer extensively. Therefore, for the sake of
clarity, we stick to them. We also note that while it is customary to set the
diagonal couplings $J_{i,i}$ to zero, the contribution of these terms to
$F_{N,{\beta},h}$ vanishes as $N\rightarrow\infty$.

$F_{N,{\beta},h}=\frac{1}{N}\log Z_{N,{\beta},h}.$ (1.4)

It is known that its $N\rightarrow\infty$ limit (called the infinite volume
limit) exists and is “self-averaging” [30]

$f({\beta},h)\equiv\lim_{N\rightarrow\infty}F_{N,{\beta},h}=\lim_{N\rightarrow\infty}{\mathbb{E}}F_{N,{\beta},h}\quad{\mathbb{P}}\textstyle{-a.s.}$
(1.5)

It is also known that this limit is given by _Parisi variational formula_
[41], [47], [40]. In this paper we focus on the simplest situation where the
model is at high temperature, a regime which is defined as follows. Consider
the equation

$q=E\tanh^{2}({\beta}\sqrt{q}Z+h)$ (1.6)

where $Z$ is a standard gaussian random variable and $E$ denotes the
expectation with respect to $Z$. It is well known [47] that (1.6) has a unique
solution $q\equiv q({\beta},h)>0$ for all ${\beta}>0$ if $h\neq 0$ and that it
has for unique solution $q({\beta},0)\equiv 0$ for all ${\beta}\leq 1$ if
$h=0$. Further define the so-called _replica symmetric formula_ as the
function

$SK({\beta},h)=\log
2+\frac{{\beta}^{2}}{4}(1-q)^{2}+E\log\cosh({\beta}\sqrt{q}Z+h).$ (1.7)

Bearing in mind that (1.5) is known, we adopt Talagrand’s definition and say
that

######  Definition 1.1.

The _high-temperature region of the SK model_ is the region of $({\beta},h)$
where

$f({\beta},h)=SK({\beta},h).$ (1.8)

The identity (1.8) was originally established by Sherrington and Kirkpatrick
by means of the replica method [45]. However, it was soon realised that their
results were flawed since they yield a negative entropy at low enough
temperature. Revisiting the saddle point analysis that enters into the
derivation of (1.7) in [45], de Almeida and Thouless [27] obtained that (1.8)
should hold if

${\beta}^{2}E\frac{1}{\cosh^{4}({\beta}\sqrt{q}Z+h)}\leq 1,$ (1.9)

a condition hereafter referred to as the _AT-condition_. The region of
$({\beta},h)$ where the AT-condition is satisfied is called the _AT-region_ ,
and replacing the inequality by an equality in (1.9) defines the _AT-line_.
Mathematically, the validity of this condition was proved for $h=0$ and
${\beta}<1$ [4]. For $h>0$, only partial results are know: it was proved in
[49] that the high-temperature region is entirely located inside the AT-region
and large subregions of the high-temperature region have been identified in
[47] (see Vol. II Chap. 13, Theorem 13.6.2 for the explicit but somewhat
inextricable description of this region) and [34].

The breakdown of the replica symmetric solution at low temperature motivated
the search for alternatives to the replica method. In pursuing this aim,
Thouless, Anderson and Palmer (hereafter TAP) developed an extended mean field
approach [48]. Relying on a Bethe approximation, the fundamental self-
consistency equation underlying mean field theories – the so-called _mean
field equation_ – was derived: it consists of a system of $N$ equations in $N$
unknown thought of as local magnetisations, $m\equiv(m_{i})_{1\leq i\leq
N}\in[-1,1]^{N}$, given by

$m_{i}=\tanh\left(h+{\beta}\sum_{j=1}^{N}\frac{J_{ij}}{\sqrt{N}}m_{j}-{\beta}^{2}(1-q_{\text{EA}}(m))m_{i}\right),\quad
1\leq i\leq N.$ (1.10)

Unlike classical mean field equations, a retroactive Onsager term
${\beta}^{2}(1-q_{\text{EA}}(m))m_{i}$ is subtracted to account for the
response of site $j$ to the local magnetisation at site $i$, where

$q_{\text{EA}}(m)=\frac{1}{N}\sum_{i=1}^{N}m_{i}^{2}$ (1.11)

is the Edwards-Anderson parameter. The associated free energy functional,
$F_{N,{\beta},h}^{TAP}$, is then introduced in [48] as a “ _fait accompli_ ”
(derived from unpublished diagram expansion), and defined on
${\mathbb{R}}^{N}$ by

$\begin{split}&F_{N,{\beta},h}^{TAP}(m)\equiv\\\
&\frac{1}{N}\left\\{\frac{{\beta}}{2}\sum_{1\leq i,j\leq
N}\frac{J_{ij}}{\sqrt{N}}m_{i}m_{j}+h\sum_{1\leq i\leq
N}m_{i}+\frac{N{\beta}^{2}}{4}\left(1-q_{\text{EA}}(m)\right)^{2}-\sum_{1\leq
i\leq N}I(m_{i})\right\\}\end{split}$ (1.12)

where $I$ is Cramér’s entropy function, i.e., $I(x)=\infty$ for $|x|>1$ and

$I(x)=\frac{1+x}{2}\log\left(\frac{1+x}{2}\right)+\frac{1-x}{2}\log\left(\frac{1-x}{2}\right)\quad\text{for
$|x|\leq 1$}.$ (1.13)

Observing that the critical points of $F_{N,{\beta},h}^{TAP}(m)$ coincide, as
it must, with the solutions of the _TAP equations_ (1.10), one finally expects
the free energy in the infinite volume limit to be obtained by maximising
$F_{N,{\beta},h}^{TAP}(m)$ over the space of local magnetisations, conditional
on certain restrictions, and taking the limit $N\rightarrow\infty$. Indeed,
since (1.10) and (1.12) both rely on approximations techniques, they must be
accompanied by validity conditions and understood for large $N$, up to sub-
leading corrections.

The questions of justifying (1.12) and finding the conditions of its validity
have received much attention in the physics literature. The most influential
contribution is undoubtedly that of Plefka [42] (see also the recent
developments [43, 44]) who devised a method for deriving the free energy
functional through the perturbative expansion of a certain function of the
local magnetisations, called Gibbs potential, which, when expended to second
order, allows one to recover (1.12) under the main convergence condition

${\beta}^{2}\frac{1}{N}\sum_{i=1}^{N}\left(1-m_{i}^{2}\right)^{2}<1.$ (1.14)

This method has been examined in a number of mathematical publications but has
not been made rigorous to date [36], [32].

Another key issue raised by the extended mean field approach of [48] it that
of consistency, namely, that of proving that the thermodynamic quantities
calculated within this framework, i.e. assuming (1.12), coincide with the
predictions based on the replica method [45], [41] and rigorously established
since [47], [40]. Tightly related to the problem of finding the solutions of
the TAP equations (1.10), this question has been studied extensively in
theoretical physics in the early 2000s [20], [26], [5], [43, 44] (see also
references therein). From a mathematical viewpoint, a study of consistency for
the free energy of mixed $p$-spin models was recently initiated in [22] and
further pursued in [24], [23]. It is proved in [22] that the infinite volume
limit free energy can indeed be expressed as the supremum of the mixed
$p$-spin version of the free energy functional (1.12) constrained over
magnetisations whose Edwards-Anderson parameter, $q_{\text{EA}}(m)$, is to the
right of the support of the Parisi measure. This is done by linking the
question of finding the maxima of the free energy functional to the
mathematical theory of the Parisi solution, thus circumventing the hard
problem of explicitly solving the TAP equations.

The latter problem was first addressed in the landmark paper [9] and its
follow-up [10]. There, an iterative construction of solutions of these
equations for the SK model is introduced and is shown to converge in the whole
region of $(\beta,h)$ where the AT-condition (1.9) is satisfied.

In this paper, we revisit the extended mean field theory of TAP from a field
theory perspective via the Hubbard-Stratonovich transformation. Widely used in
physics, this transformation linearises the Hamiltonian and, in doing so,
introduces an auxiliary scalar field which, in the SK model, is complex. This
feature makes the resulting integral representation of the partition function
seem practically intractable, so that this otherwise very natural approach may
have been deemed unrealistic. We show, focusing on the high-temperature region
of the SK model in the sense of definition 1.1 and building on the properties
of the iterative construction of solutions of the TAP equations obtained in
[9], [10], that this integral representation allows us to express the free
energy in the form of a variational formula. Unexpectedly, the free energy
functional to be maximised, $F_{N,{\beta},h}^{HT}$, is not the TAP free energy
functional (1.12), but a smaller one, given by

$F_{N,{\beta},h}^{HT}(m)=F_{N,{\beta},h}^{TAP}(m)-\frac{{\beta}^{2}}{4}\left(q-q_{\text{EA}}(m)\right)^{2}.$
(1.15)

Note that when restricted to the subspace of magnetisations satisfying
$q_{\text{EA}}(m)=q$, both functionals have the same critical points and take
the same values at these points. Thus, as long as they have a common maximiser
that lies in that subspace, the difference between the two will not affect the
free energy. It can, however, lead to different _stability conditions_ , i.e.
different conditions on $({\beta},h)$ for a common critical point to be a
global maximum. We return to this question in Section 1.4.

A first, concise formulation of the main result of this article is as follows.

######  Theorem 1.2.

There exists a region ${\mathcal{D}}$ of $({\beta},h)$, $h>0$, such that in
the intersection of ${\mathcal{D}}$ and the high-temperature region of
Definition 1.1

$f({\beta},h)=\lim_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}}F_{N,{\beta},h}^{HT}\left(m\right)\quad{\mathbb{P}}\textstyle{-a.s.}$
(1.16)

The slightly cumbersome and unwieldy description of the explicit region
${\mathcal{D}}$ for which we prove Theorem 1.2 is deferred to Section 1.3.
Nevertheless, it can be said at this stage that ${\mathcal{D}}$ contains a
large subregion of the AT-region [27], in particular the high-temperature
half-plane

${\beta}<1/2,\quad\forall h>0$ (1.17)

and the low-temperature and large-field region (recall that in [27] the field
is the quantity $h/{\beta}$)

$12{\beta}e^{-\frac{1}{9}(h/{\beta})^{2}}<1.$ (1.18)

For comparison, in [27] (see Figure 2 and Eq. (23)) the corresponding regions
have the same shape but different constants, namely

${\beta}<1,\quad\forall h>0$ (1.19)

and, for large fields and low temperatures,

${\textstyle{4\over 3\sqrt{2\pi}}}{\beta}e^{-\frac{1}{2}(h/{\beta})^{2}}<1.$
(1.20)

Clearly, the region ${\mathcal{D}}$ obtained is not optimal, but reflects the
limitations of the techniques used in the analysis of $F_{N,{\beta},h}^{HT}$
(mainly random matrix techniques and Gaussian comparison techniques).
Moreover, the treatment of the high-temperature subregion is kept brief and
elementary, whereas the most difficult and interesting subregion, that of
large fields and low temperatures, is the main focus of this paper.

We stress that the proof of Theorem 1.2 is not entirely _ab initio_ since it
makes crucial use of the fact, presupposed in Definition 1.1, that the free
energy converges almost surely to $SK({\beta},h)$ in the high-temperature
region. However, in contrast to previous work, it is not presumed that the TAP
free energy formula is known.

Before presenting the strategy of the proof, we should emphasise that the
study of the TAP approach remains topical in both theoretical physics and
probability theory. Several questions, notably that of the consistency of the
two approaches, _Replicas_ versus _TAP_ , have been actively debated in
theoretical physics until recently [20], [5], [43], [44]. From a mathematical
perspective, this equivalence has recently been investigated in [22], [24],
[23]. The question of finding the solutions of the TAP equations [25], [9],
[10], reproving their derivation by Stein’s method [21] or by a dynamical
approach [2], studying their stability and their numerical solutions [31],
questioning the meaning of Plefka’s condition [32] have also been tackled
recently, and an upper bound on the TAP free energy was obtained in [8], to
mention only recent publications without claim to completeness.

###  1.2. Structure of the proof of Theorem 1.2

The major part of the proof of Theorem 1.2 is concerned with the study of the
properties of the function $F_{N,{\beta},h}^{HT}$ which are needed, in a final
section, to establish the variational formula (1.16) via the Hubbard-
Stratonovitch transformation.

The connection between this variational formula and the replica symmetric
formula (1.7) is established through a duality formula. Such a formula
transforms an initial optimisation problem into another, so that the initial
function to be optimised and its dual have the same critical points and take
the same value at those points. The case of an initial function, such as
$F_{N,{\beta},h}^{HT}$, which decomposes into the sum of a quadratic form and
a convex function, has been studied extensively (albeit in other contexts
[28]). We draw on this in Section 2.

Knowing the critical points of $F_{N,{\beta},h}^{HT}$ is key to using duality.
This is where Bolthausen’s iterative scheme [9], [10] comes in. For $h>0$, let
$q\equiv q({\beta},h)$ be the unique solution of (1.6) and consider the system
of TAP equations (1.10) with $q$ substituted for $q_{\text{EA}}$

$m_{i}=\tanh\left(h+{\beta}\sum_{j=1}^{N}\frac{J_{ij}}{\sqrt{N}}m_{j}-{\beta}^{2}(1-q)m_{i}\right),\quad
1\leq i\leq N.$ (1.21)

Note that (1.21) is nothing else but the critical point equation of the
function $F_{N,{\beta},h}^{HT}$. Let
$m^{(k)}\equiv\bigl{(}m^{(k)}_{i}\bigr{)}_{1\leq i\leq N}$,
$k\in{\mathbb{N}}$, be the sequence of random variables defined recursively by

$m^{(0)}={\bf{0}},m^{(1)}=\sqrt{q}{\bf{1}}$ (1.22)

where $\bf{0}$ and $\bf{1}$ are the vectors whose coordinates are all $0$ and
all $1$, respectively and, for all $k\geq 1$, set

$m^{(k+1)}_{i}=\tanh\left(h+{\beta}\sum_{j=1}^{N}\frac{J_{ij}}{\sqrt{N}}m^{(k)}_{j}-{\beta}^{2}(1-q)m^{(k-1)}_{i}\right),\quad
1\leq i\leq N.$ (1.23)

To simplify notation we keep the dependence of $m^{(k)}$ on $N$ implicit
throughout the paper.

It is proved in [9], [10] that under the AT-condition (1.9), and thus by [49]
in the whole high-temperature region of Definition 1.1, this iteration scheme
is convergent when taking first the limit $N\rightarrow\infty$ and then
$k\rightarrow\infty$. This is done via the explicit construction of a
representation of the sequence $m^{(k)}$ for $N$ large. Moreover, this
explicit representation of the solution makes it possible to express fairly
general functions of $m^{(k)}$ in the limit of large $N$ and large $k$.

The precise statements of these results are given in Section 3. Combined with
the duality formula, they are used in Section 4 to prove the following
statement.

######  Theorem 1.3.

For all $({\beta},h)$, $h>0$, satisfying the AT-condition,

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}F_{N,{\beta},h}^{HT}\left(m^{(k)}\right)=SK({\beta},h)\quad{\mathbb{P}}\textstyle{-a.s.}$
(1.24)

Thus, for all $({\beta},h)$, $h>0$, in the high-temperature region

$f({\beta},h)=\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}F_{N,{\beta},h}^{HT}\left(m^{(k)}\right)\quad{\mathbb{P}}\textstyle{-a.s.}$
(1.25)

Furthermore, (1.24), and hence (1.25), remain true if $F_{N,{\beta},h}^{HT}$
is replaced by $F_{N,{\beta},h}^{TAP}$.

We stress that (1.25) merely follows by identifying the right-hand side of
(1.24) with the left-hand side of (1.25) via Definition 1.1.

######  Remark.

Note that Theorem 1.3 also holds for $F_{N,{\beta},h}^{TAP}$. As will be seen
in Section 3, this reflects the fact that $q_{\text{EA}}(m^{(k)})$ is
concentrated near $q$, so that the quadratic term in (1.15) vanishes
asymptotically. A similar result was obtained in Theorem 2 of [22], which
states that $F_{N,{\beta},h}^{TAP}$ evaluated at the vector of averaged local
magnetisations
$m=\left(\langle{\sigma}_{1}\rangle,\dots,\langle{\sigma}_{N}\rangle\right)$,
where $\langle\cdot\rangle$ denotes the expectation with respect to the Gibbs
measure, converges in mean square to $SK({\beta},h)$ under the assumption,
characteristic of the high-temperature region, that the overlap is
concentrated near $q$ (see e.g. [47] Vol. II Chap. 13). Moreover, under such a
condition, it was proved in [25] using a so-called cavity iteration that the
solution of Bolthausen’s iterative scheme converges to the local
magnetizations.

Theorem 1.3 strongly suggests that the global maximum of
$F_{N,{\beta},h}^{HT}$ is reached asymptotically at $m^{(k)}$. A global
analysis of the function $F_{N,{\beta},h}^{HT}$ confirms that this is indeed
the case in a subregion ${\mathcal{D}}$ of the AT-region. This is the content
of the following theorem.

######  Theorem 1.4.

There exists a region ${\mathcal{D}}$ of $({\beta},h)$, $h>0$, such that in
the intersection of ${\mathcal{D}}$ and the AT-region

$\lim_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}}F_{N,{\beta},h}^{HT}\left(m\right)=\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}F_{N,{\beta},h}^{HT}\left(m^{(k)}\right)\quad{\mathbb{P}}\textstyle{-a.s.}$
(1.26)

Furthermore, with ${\mathbb{P}}$-probability one the supremum in (1.26) is
uniquely attained, for all large enough $N$.

Before addressing the main issues of the proof of Theorem 1.4, which occupy
Sections 5 and 6, we state the variational formula from which the function
$F_{N,{\beta},h}^{HT}$ emerges as the free energy functional of the SK model
at high temperature.

######  Theorem 1.5.

For all $({\beta},h)$, $h>0$, in the intersection of the high-temperature
region and the region ${\mathcal{D}}$ of Theorem 1.4, the free energy
$F_{N,{\beta},h}$ of the SK model obeys

$\lim_{N\rightarrow\infty}\left|F_{N,{\beta},h}-\sup_{m\in[-1,1]^{N}}F_{N,{\beta},h}^{HT}(m)\right|=0\quad{\mathbb{P}}-\text{a.s.}$
(1.27)

If ${\mathbb{P}}$-almost sure convergence in Theorem 1.4 is replaced by
convergence in ${\mathbb{P}}$-probability, then (1.27) holds in
${\mathbb{P}}$-probability.

Theorem 1.5 is proved in Section 7.

###  1.3. The region ${\mathcal{D}}$

We now come to the detailed description of the region ${\mathcal{D}}$ that
arises from the proof of Theorem 1.4. When trying to establish a result like
(1.26), one naturally first checks whether $F_{N,{\beta},h}^{HT}$ is concave
on its domain, $[-1,1]^{N}$, and, if not, whether it is locally concave in
some subset of $[-1,1]^{N}$ containing $m^{(k)}$. More precisely, one looks
for regions of $({\beta},h)$ where, with ${\mathbb{P}}$-probability one, for
all sufficiently large $N$, the Hessian of $F_{N,{\beta},h}^{HT}$ is strictly
negative definite in as large a domain containing $m^{(k)}$ as possible. Such
an analysis is carried out in Section 5. Two regions emerge that will lead to
(1.17) and (1.18), respectively. The first is the region

${\mathcal{D}}^{(1)}=\bigl{\\{}({\beta},h)\mid
h>0,{\beta}<1/(1+\sqrt{q})\bigr{\\}}.$ (1.28)

Clearly, ${\mathcal{D}}^{(1)}$ is contained in the AT-region. Introducing a
parameter $0\leq\varrho\leq 1$ and setting

$\vartheta(\varrho)\equiv
36(1-\varrho)+4(1-\varrho)^{1/2}+(1-\varrho)^{1/4}\left[4+\sqrt{12\left[|\ln(1-\varrho)|+2\right]}\right],$
(1.29)

the second region is $\varrho$-dependent and is defined by

${\mathcal{D}}^{(2)}_{\varrho}=\bigl{\\{}({\beta},h)\mid h>0,\varrho\leq
q,{\beta}\vartheta(\varrho)<1\bigr{\\}}.$ (1.30)

Based on the analysis of the Hessian, the following results are derived in
Section 5.6.

######  Theorem 1.6.

(i) For all $({\beta},h)$ in ${\mathcal{D}}^{(1)}$, ${\mathbb{P}}$-almost
surely

$\begin{split}&\lim_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}}F_{N,{\beta},h}^{HT}\left(m\right)\\\
=&\lim_{{\epsilon}\rightarrow
0}\lim_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}:|q_{\text{EA}}(m)-q|\leq
q(1-q){\epsilon}}F_{N,{\beta},h}^{HT}\left(m\right)\\\
=&\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}F_{N,{\beta},h}^{HT}\left(m^{(k)}\right).\end{split}$
(1.31)

Furthermore, with ${\mathbb{P}}$-probability one, for all but a finite number
of indices $N$, $F_{N,{\beta},h}^{HT}$ is strictly convex on $[-1,1]^{N}$.

(ii) Let $\sqrt{3/4}\leq\varrho\leq 1$ be given. For all $({\beta},h)$ in
${\mathcal{D}}^{(2)}_{\varrho}$ satisfying the AT-condition,
${\mathbb{P}}$-almost surely

$\begin{split}&\lim_{{\epsilon}\rightarrow
0}\lim_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}:q_{\text{EA}}(m)\geq\varrho-\varrho(1-\varrho){\epsilon}}F_{N,{\beta},h}^{HT}\left(m\right)\\\
=&\lim_{{\epsilon}\rightarrow
0}\lim_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}:|q_{\text{EA}}(m)-q|\leq
q(1-q){\epsilon}}F_{N,{\beta},h}^{HT}\left(m\right)\\\
=&\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}F_{N,{\beta},h}^{HT}\left(m^{(k)}\right).\end{split}$
(1.32)

The same statement is true if $0<{\epsilon}\leq 1$ is held fixed. Furthermore,
the supremum over the set
$\\{m\in[-1,1]^{N}:q_{\text{EA}}(m)\geq\varrho-\varrho(1-\varrho){\epsilon}\\}$
is uniquely attained.

Under the assumptions of Theorem 1.6, (ii), the supremum in (1.32) is not over
the entire hypercube, but over a smaller, $\varrho$-dependent set where
$\sqrt{3/4}\leq\varrho<q$. In Section 6, we complement this result by giving
conditions on $\varrho$ and $({\beta},h)$ which guarantee that the supremum of
$F_{N,{\beta},h}^{HT}$ over the set
$\\{m\in[-1,1]^{N}:q_{\text{EA}}(m)<\varrho\\}$ is strictly smaller than
$SK({\beta},h)$. Specifically, define the region

${\mathcal{D}}^{(3)}=\left\\{({\beta},h)\mid h/{\beta}>2,{\beta}^{2}(1-q)\leq
1,h\geq 4\right\\}.$ (1.33)

######  Theorem 1.7.

Let $\bar{\varrho}({\beta},h)$ be the function defined in (6.2). For all
$({\beta},h)$ in ${\mathcal{D}}^{(3)}$

$\limsup_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}:q_{\text{EA}}(m)\leq\bar{\varrho}({\beta},h)}F_{N,{\beta},h}^{HT}\left(m\right)<SK({\beta},h)\quad{\mathbb{P}}\textstyle{-a.s.}$
(1.34)

A detailed analysis of the function $\bar{\varrho}({\beta},h)$ is carried out
in Section 6.

We now come to the choice of $\varrho$. Given that
${\mathcal{D}}^{(2)}_{\varrho}$ increases as $\varrho$ increases from 0 to
$q$, and that $\bar{\varrho}({\beta},h)<q$ by definition (see (6.2)), the
choice $\varrho=\bar{\varrho}({\beta},h)$ in (1.30) is allowed and optimal.
The condition on $\rho$ of Theorem 1.6, (ii), then gives a fourth and last
region

${\mathcal{D}}^{(4)}=\left\\{({\beta},h)\mid\bar{\varrho}({\beta},h)\geq\sqrt{3/4}\right\\}.$
(1.35)

In the light of the above, we arrive at the following extended version of
Theorem 1.4. Set

${\mathcal{D}}={\mathcal{D}}^{(1)}\cup\left({\mathcal{D}}^{(2)}_{\bar{\varrho}({\beta},h)}\cap{\mathcal{D}}^{(3)}\cap{\mathcal{D}}^{(4)}\right).$
(1.36)

######  Theorem 1.8 (Theorem 1.4 redux).

Eq. (1.26) holds for all $({\beta},h)$ in the intersection of the AT-region
and the region ${\mathcal{D}}$ defined by (1.36) .

Equipped with the above result we now can state the full version of our main
result.

######  Theorem 1.9 (Theorem 1.2 redux).

Eq. (1.16) holds for all $({\beta},h)$ in the intersection of the high-
temperature region of Definition 1.1 and the region ${\mathcal{D}}$ defined by
(1.36).

The next proposition gives an explicit characterisation of the region
${\mathcal{D}}$ for sufficiently large $h/{\beta}$ and ${\beta}$, which
justifies the description given in (1.17)-(1.18). Set

$\begin{split}\widetilde{\mathcal{D}}^{(2)}&=\left\\{({\beta},h)\mid
12{\beta}e^{-\frac{1}{9}(h/{\beta})^{2}}<1,3\leq{h}/{{\beta}}\leq{\beta}q/10\right\\}.\end{split}$
(1.37)

######  Proposition 1.10.

$\widetilde{\mathcal{D}}={\mathcal{D}}^{(1)}\cup\widetilde{\mathcal{D}}^{(2)}\subset({\mathcal{D}}\cap\\{\text{AT-
region}\\}).$ (1.38)

The proof of Proposition 1.10 is given in Section 6. We stress that no attempt
was made to optimise the constants in the definitions of the sets
${\mathcal{D}}^{(2)}_{\varrho}$, $\widetilde{\mathcal{D}}^{(2)}$, and
${\mathcal{D}}^{(i)}$, $i=1,3,4$. This is because, as mentioned earlier, we do
not expect the region ${\mathcal{D}}$ defined in (1.36) to be optimal due to
technical artefacts. However, it seems difficult to significantly improve the
constant $1/9$ in (1.38) within our technical framework.

###  1.4. Comments on stability

The issue of stability within the TAP approach has been extensively addressed
in the physics literature [16], [39], [42], [43], [44], [5]. From these works,
condition (1.14) emerges as the main stability condition. It is also believed
to coincide with the AT-condition (1.9). Eq. (1.14) was originally derived in
two different ways, as a convergence condition for Plefka’s expansion [42] and
as a divergence condition for the spin glass susceptibility in [16]. Both
conditions ultimately reduce to conditions on the eigenvalues of the Hessian
matrix of $F_{N,{\beta},h}^{TAP}$, and are formulated as conditions on the
_empirical spectral measure_ of the Hessian. We will not question the validity
of these approaches and results here (see [32] for recent, partial but
rigorous results). We simply ask what would become of these results if we
replaced $F_{N,{\beta},h}^{TAP}$ by $F_{N,{\beta},h}^{HT}$.

By (1.15), the Hessians of $NF_{N,{\beta},h}^{HT}$ and
$NF_{N,{\beta},h}^{TAP}$, denoted by ${\mathcal{H}}^{HT}$ and
${\mathcal{H}}^{TAP}$ respectively, have spectral norm of order one as
$N\rightarrow\infty$. Moreover, on the subspace of magnetisations satisfying
$q_{\text{EA}}(m)=q$ (to which the iterative solution $m^{(k)}$ asymptotically
belongs if the AT-condition (1.9) is satisfied), these Hessians differ by a
rank-one projector of non-null eigenvalue $q{\beta}^{2}$. It is known that the
_extreme eigenvalues_ of certain Hermitian random matrices, such as Wigner
matrices, can be strongly influenced by rank-one deformations, i.e., they can
be detached from the spectrum for sufficiently large deformations (see, e.g.,
the survey paper [17]). Since in the present case the deformation is
proportional to $q{\beta}^{2}$, this effect is expected to be present at
sufficiently low temperatures. The case of spectral measures is completely
different. As a direct consequence of the so-called rank inequalities (see
[6], Appendix A.6, and again [17]), the limiting behaviour of the spectral
measure of a Hermitian random (or non-random) matrix is not modified by a
finite-rank deformation. Accordingly, ${\mathcal{H}}^{HT}$ and
${\mathcal{H}}^{TAP}$ have the same limiting spectral measure, and will thus
give the same condition (1.14) in the limit $N\rightarrow\infty$.

The proof of Theorem 1.4 described in Section 1.3 is also a stability
analysis. It differs from the approaches of [16] and [42] in that the
functional $F_{N,{\beta},h}^{HT}$ is not examined in a single $m$, but
globally over the whole hypercube. Indeed, as in the Laplace method for
approximating integrals, we need to establish that the solution $m^{(k)}$ of
the iterative scheme (1.22)-(1.23) is (a good ansatz for) the global maximum
of $F_{N,{\beta},h}^{HT}$. To do this, it is not enough to know the nature of
the Hessian ${\mathcal{H}}^{HT}$ at just this point. This global control is
achieved at the expense of the precision of the constants in (1.18), i.e., in
(1.38). We also note that our analysis, via Theorem 1.6, centers on the
largest eigenvalue of ${\mathcal{H}}^{HT}$, not on the spectral measure as in
[16], [42].

The remainder of this paper is organised as follows. Section 2 introduces a
key duality formula. Section 3 summarises the needed results on Bolthausen’s
iterative scheme and shows how they can be turned into ${\mathbb{P}}$-almost
sure results. Section 4 contains the proof of Theorem 1.3 and Section 5 the
proof of Theorem 1.6. Theorem 1.7 is a reformulation of Theorem 6.1, which is
stated and proved in Section 6. This section also contains the proofs of
Theorems 1.4, 1.8 and Proposition 1.10. Finally, in Section 7, the Hubbard-
Stratonovitch transformation is used to prove Theorem 1.5, and the proofs of
Theorems 1.2 and 1.9 are given.

In the rest of the paper, $h>0,{\beta}>0$ and $q\equiv q({\beta},h)$ is the
unique solution of (1.6).

##  2\. Preparatory tools: duality

The proof of Theorem 1.2 hinges on a duality formula for non-convex functions
known as the Clarke duality formula. The general formulation we use is that of
[28] (see Section 4). This duality was first used in the context of spin
glasses in the study of generalised Hopfield models to prove a so-called
transfer principle [13].

###  2.1. Duality

Let $A_{N}=(A_{ij})_{1\leq i,j\leq N}$ be the symmetric matrix with entries

$A_{ij}=\frac{J_{ij}}{\sqrt{N}}-{\beta}(1-q){\delta}_{i,j}$ (2.1)

where ${\delta}_{i,j}$ is the Kronecker delta. It follows from know results
(see, e.g., Theorem 1.2 of [50]) that there exists a subset
${\Omega}_{0}\subset{\Omega}$ with ${\mathbb{P}}\left({\Omega}_{0}\right)=1$
such that for all ${\omega}\in{\Omega}_{0}$ there exists
$N_{0}({\omega})<\infty$ such that for all $N>N_{0}({\omega})$, $A_{N}$ is
non-singular. It is henceforth assumed that $N>N_{0}({\omega})$: all results
have to be understood in this sense. Set $I^{*}(x)=\log\cosh(x)+\log 2$,
$x\in{\mathbb{R}}$, and for ${\bf{h}}=(h_{i})_{1\leq i\leq N}$ a given vector
in ${\mathbb{R}}^{N}$, define the functions
$\Psi_{N,{\beta},{\bf{h}}}:{\mathbb{R}}^{N}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$
and $\Phi_{N,{\beta},{\bf{h}}}:{\mathbb{R}}^{N}\rightarrow{\mathbb{R}}$ by

$\begin{split}\Psi_{N,{\beta},{\bf{h}}}(x)&=\frac{{\beta}}{2}(x,A_{N}x)+({\bf{h}},x)-\sum_{i=1}^{N}I(x_{i}),\\\
\Phi_{N,{\beta},{\bf{h}}}(x)&=-\frac{{\beta}}{2}(x,A_{N}x)+\sum_{i=1}^{N}I^{*}\left({\beta}(A_{N}x)_{i}+h_{i}\right).\end{split}$
(2.2)

######  Proposition 2.1 (Duality formula).

$x$ is a critical point of $\Psi_{N,{\beta},{\bf{h}}}(x)$ if and only if $x$
is a critical point of $\Phi_{N,{\beta},{\bf{h}}}(x)$. These critical points
are the solutions of the system of equations

$x_{i}=\tanh\left(h_{i}+{\beta}(A_{N}x)_{i}\right),\quad 1\leq i\leq N,$ (2.3)

and at each critical point

$\Psi_{N,{\beta},{\bf{h}}}(x)=\Phi_{N,{\beta},{\bf{h}}}(x).$ (2.4)

By (2.2), the function $F_{N,{\beta},h}^{TAP}$ and $F_{N,{\beta},h}^{HT}$
defined in (1.12) and (1.15) can be written as

$\displaystyle F_{N,{\beta},h}^{HT}(x)$ $\displaystyle=$
$\displaystyle\frac{1}{N}\left\\{\Psi_{N,{\beta},h{\bf{1}}}(x)+\frac{{\beta}^{2}N}{4}\left(1-q^{2}\right)\right\\},$
(2.5) $\displaystyle F_{N,{\beta},h}^{TAP}(x)$ $\displaystyle=$
$\displaystyle\frac{1}{N}\left\\{\Psi_{N,{\beta},h{\bf{1}}}(x)+\frac{{\beta}^{2}N}{4}\left[1-q^{2}+\left(q-q_{\text{EA}}(x)\right)^{2}\right]\right\\}.$
(2.6)

######  Corollary 2.2 (Duality formula for the free energy functional).

Taking ${\bf{h}}=h{\bf{1}}$ in (2.2) we have, for all solutions $x$ of the TAP
equations (1.10) such that $q_{\text{EA}}(x)=q$,

$F_{N,{\beta},h}^{TAP}(x)=F_{N,{\beta},h}^{HT}(x)=\frac{1}{N}\left\\{\Phi_{N,{\beta},h{\bf{1}}}(x)+\frac{{\beta}^{2}N}{4}\left[1-q^{2}\right]\right\\}.$
(2.7)

###### Proof of Proposition 2.1.

This is a direct application of Theorem 2 in Section 4, Chapter II of [28]
(hereafter referred to as Theorem 2 of [28]), whose notation and terminology
we use. First note that $A_{N}$ being ${\mathbb{P}}$-almost surely non-
singular, $\rm{Ker}A_{N}=\\{\bf{0}\\}$ ${\mathbb{P}}$-almost surely, where
$\bf{0}$ is the vector whose coordinates are all $0$. Next note that the
functions

$\textstyle{\mathcal{I}}_{N}(x)\equiv\sum_{i=1}^{N}I(x_{i}),\quad{\mathcal{I}}_{N}^{*}(x)\equiv\sum_{i=1}^{N}I^{*}\left(x_{i}\right)$
(2.8)

form a pair of Legendre-Fenchel conjugates, and that both of them are proper,
lower semicontinuous convex functions, so they are differentiable in the
interior of their domains, $\rm{int}(\rm{dom\,}{\mathcal{I}}_{N}^{*})$ and
$\rm{int}(\rm{dom\,}{\mathcal{I}}_{N})$ (the domain of a function
$f:{\mathbb{R}}^{N}\rightarrow{\mathbb{R}}\cup\\{\infty\\}$ is the set
${\rm{dom}\,}f=\left\\{x\in{\mathbb{R}}^{N}\mid f(x)<\infty\right\\}$, with
obvious modification under the global change of sign $f\mapsto-f$.) Clearly,
condition (14) of Theorem 2 of [28] is satisfied. We can now conclude: the
first claim of Proposition 2.1 follows from the first two claims of Theorem 2
of [28] combined, (2.4) is (15) therein, and differentiation of any of the
dual functions (2.2) yields (2.3). ∎

###### Proof of Corollary 2.2.

Take ${\bf{h}}=h{\bf{1}}$ in Proposition 2.1. For this choice, the system of
equations (2.3) reduces to the specialised TAP equations (1.21). The second
equality in (2.7) then follows from (2.5) and (2.4). The first identity
follows from (2.6) and the assumption that $q_{\text{EA}}(x)=q$. ∎

######  Remark (on maxima of the dual functions).

As an immediate consequence of Legendre-Fenchel conjugacy,
$\Psi_{N,{\beta},{\bf{h}}}(x)\leq\Phi_{N,{\beta},{\bf{h}}}(x)$ for all
$x\in{\mathbb{R}}^{N}$. When $A_{N}$ is strictly positive definite,
$\Phi_{N,{\beta},{\bf{h}}}$ is bounded from above and the set of critical
points of $\Psi_{N,{\beta},{\bf{h}}}$ and of $\Phi_{N,{\beta},{\bf{h}}}$ that
are local maxima are in one-to-one correspondence. (This is the case, for
example, with the Curie-Weiss model.) In the case where $A_{N}$ is not
positive definite which interests us here, this is not true. The function
$\Phi_{N,{\beta},{\bf{h}}}$ is unbounded. It has no maxima, only saddles, and
the local maxima of $\Psi_{N,{\beta},{\bf{h}}}$ are saddles of the function
$\Phi_{N,{\beta},{\bf{h}}}$.

###  2.2. Dealing with approximate solutions of the TAP equations

The duality formula for the free energy of Corollary 2.2 is of little
practical use if we only know approximate solutions of the TAP equations. To
deal with such a situation, let us first observe that equality in (2.4) can be
achieved at any given ${\bar{x}}\in{\mathbb{R}}^{N}$ by using a modified
magnetic field. Specifically, for ${\bar{x}}\in{\mathbb{R}}^{N}$ let
${\bf{\bar{h}}}\in{\mathbb{R}}^{N}$ be defined by

${\bf{\bar{h}}}={\bf{h}}-\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x}).$ (2.9)

Here $\nabla$ is the gradient operator, that is to say, for
$f:{\mathbb{R}}^{N}\rightarrow{\mathbb{R}}$, $\nabla
f:{\mathbb{R}}^{N}\rightarrow{\mathbb{R}}^{N}$ is the vector of coordinates
$\nabla
f(x)=(\frac{{\partial}}{{\partial}x_{1}}f(x),\dots\frac{{\partial}}{{\partial}x_{N}}f(x))$.

######  Lemma 2.3.

$\displaystyle\Psi_{N,{\beta},{\bf{\bar{h}}}}(\bar{x})=\Phi_{N,{\beta},{\bf{\bar{h}}}}(\bar{x}).$

###### Proof of Proposition 2.1.

It is easy to check from the definition (2.2) that the choice of
${\bf{\bar{h}}}$ in (2.9) guarantees that the function
$\Psi_{N,{\beta},{\bf{\bar{h}}}}(x)$ has a critical point at $\bar{x}$, i.e.,
$\nabla\Psi_{N,{\beta},{\bf{\bar{h}}}}(\bar{x})=0$. The lemma then follows
from an application of Proposition 2.1. ∎

The next two results play the role of the duality formulas of Proposition 2.1
and Corollary 2.2, respectively, when only approximate solutions of the TAP
equations are known.

######  Proposition 2.4.

For all $\bar{x}\in{\mathbb{R}}^{N}$ such that
$\sqrt{\frac{1}{N}\left\|\bar{x}\right\|_{2}^{2}}\leq\kappa$ for some constant
$\kappa<\infty$,

$\frac{1}{N}\left|\Psi_{N,{\beta},{\bf{h}}}(\bar{x})-\Phi_{N,{\beta},{\bf{h}}}(\bar{x})\right|\leq\frac{1+\kappa}{\sqrt{N}}\left\|\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x})\right\|_{2}.$
(2.10)

Thus clearly, if $\bar{x}$ is an approximate solution of the system of
equations (2.3) in the sense that
$\frac{1}{N}\left\|\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x})\right\|_{2}^{2}\rightarrow
0$ as $N\rightarrow\infty$, then, normalised by $1/N$, (2.4) holds at
$\bar{x}$ asymptotically, as $N\rightarrow\infty$. As an immediate corollary
we have :

######  Corollary 2.5.

Take ${\bf{h}}=h{\bf{1}}$ in (2.2). Then, under the assumptions and with the
notations of Proposition 2.4

$\begin{split}&\left|\left\\{\frac{1}{N}\Phi_{N,{\beta},h{\bf{1}}}(\bar{x})+\frac{{\beta}^{2}}{4}\left(1-q^{2}\right)\right\\}-F_{N,{\beta},h}^{TAP}(\bar{x})\right|\\\
\leq\,\,&\frac{1+\kappa}{\sqrt{N}}\left\|\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x})\right\|_{2}+\frac{{\beta}^{2}}{4}\left(q-q_{\text{EA}}(\bar{x})\right)^{2}.\end{split}$
(2.11)

The same result holds substituting $F_{N,{\beta},h}^{HT}$ for
$F_{N,{\beta},h}^{TAP}$ and suppressing the term
$\frac{{\beta}^{2}}{4}\left(q-q_{\text{EA}}(\bar{x})\right)^{2}$ on the right-
and side of (2.11).

###### Proof of Proposition 2.4.

Using Lemma 2.3, we have

$\left|\Psi_{N,{\beta},{\bf{h}}}(\bar{x})-\Phi_{N,{\beta},{\bf{h}}}(\bar{x})\right|\leq\left|\Psi_{N,{\beta},{\bf{h}}}(\bar{x})-\Psi_{N,{\beta},{\bf{\bar{h}}}}(\bar{x})\right|+\left|\Phi_{N,{\beta},{\bf{h}}}(\bar{x})-\Phi_{N,{\beta},{\bf{\bar{h}}}}(\bar{x})\right|.$
(2.12)

Consider the first term in the right-hand side of (2.12). By (2.2) and (2.9),
for all $x\in{\mathbb{R}}^{N}$

$\displaystyle\left|\Psi_{N,{\beta},{\bf{\bar{h}}}}(x)-\Psi_{N,{\beta},{\bf{h}}}(x)\right|=$
$\displaystyle\left|({\bf{\bar{h}}}-{\bf{h}},x)\right|$ $\displaystyle=$
$\displaystyle\left|(\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x}),x)\right|$
$\displaystyle\leq$ $\displaystyle\textstyle
N\sqrt{\frac{1}{N}\left\|x\right\|_{2}^{2}}\sqrt{\frac{1}{N}\left\|\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x})\right\|_{2}^{2}}.$
(2.13)

To bound the second term we write, recalling (2.8),

$\left|\Phi_{N,{\beta},{\bf{\bar{h}}}}(\bar{x})-\Phi_{N,{\beta},{\bf{h}}}(\bar{x})\right|=\left|{\mathcal{I}}_{N}^{*}({\beta}A_{N}\bar{x}+{\bf{\bar{h}}})-{\mathcal{I}}_{N}^{*}({\beta}A_{N}\bar{x}+{\bf{h}})\right|.$
(2.14)

Then, by the mean value theorem

$\displaystyle\left|{\mathcal{I}}_{N}^{*}({\beta}A_{N}\bar{x}+{\bf{\bar{h}}})-{\mathcal{I}}_{N}^{*}({\beta}A_{N}\bar{x}+{\bf{h}})\right|$
$\displaystyle\leq$ $\displaystyle\max_{0\leq{\lambda}\leq
1}\left\|\nabla{\mathcal{I}}_{N}^{*}\left({\beta}A_{N}\bar{x}+{\bf{h}}+(1-{\lambda})({\bf{\bar{h}}}-{\bf{h}})\right)\right\|_{2}\|{\bf{\bar{h}}}-{\bf{h}}\|_{2}$
$\displaystyle=$ $\displaystyle\max_{0\leq{\lambda}\leq
1}\left\\{\sum_{i=1}^{N}\left[(I^{*})^{\prime}\left({\beta}(A_{N}\bar{x})_{i}+h_{i}+(1-{\lambda})(\bar{h}_{i}-h_{i})\right)\right]^{2}\right\\}^{1/2}\|{\bf{\bar{h}}}-{\bf{h}}\|_{2}$
$\displaystyle\leq$ $\displaystyle
N\sqrt{\frac{1}{N}\left\|\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x})\right\|_{2}^{2}},$
(2.15)

where we used (2.9) and the bound $|(I^{*})^{\prime}(z)|\leq 1$ $\forall
z\in{\mathbb{R}}$ in the last line. Taking $x=\bar{x}$ in (2.13) and inserting
the resulting bound and (2.15) in (2.12) establishes (2.10) for all $\bar{x}$
such that $\sqrt{\frac{1}{N}\left\|\bar{x}\right\|_{2}^{2}}\leq C$ for some
constant $0<C<\infty$. ∎

###### Proof of Corollary 2.5.

By Proposition 2.4 and (2.6)

$\begin{split}&\left|\frac{1}{N}\left\\{\Phi_{N,{\beta},h{\bf{1}}}(\bar{x})+\frac{{\beta}^{2}N}{4}\left[1-q^{2}+\left(q-q_{\text{EA}}(\bar{x})\right)^{2}\right]\right\\}-F_{N,{\beta},h}^{TAP}(\bar{x})\right|\\\
\leq\,\,&\frac{1+\kappa}{\sqrt{N}}\left\|\nabla\Psi_{N,{\beta},{\bf{h}}}(\bar{x})\right\|_{2}.\end{split}$
(2.16)

Clearly, (2.16) implies (2.11) while using (1.15) in (2.16) yields the claim
for $F_{N,{\beta},h}^{HT}$. ∎

##  3\. Iterative solutions of the specialised TAP equations

This section recalls the results of [9], [10], which are central to this
paper. We mostly use the notation of [10]. In particular, inner products and
norms are rescaled: given two vectors $x,y\in{\mathbb{R}}^{N}$, we write

$\langle
x,y\rangle=\frac{1}{N}(x,y)\quad\text{and}\quad\|x\|_{2,N}=\frac{1}{\sqrt{N}}\|x\|_{2}.$
(3.1)

###  3.1. Convergence of the iterative scheme

The main result of [9] is the following convergence theorem.

######  Theorem 3.1 (Theorem 2.1 of [9]).

Assume that $h>0$. If ${\beta}>0$ is below the AT-line, i.e. if

${\beta}^{2}E\frac{1}{\cosh^{4}({\beta}\sqrt{q}Z+h)}\leq 1,$ (3.2)

then

$\lim_{k,k^{\prime}\rightarrow\infty}\limsup_{N\rightarrow\infty}{\mathbb{E}}\left\|m^{(k)}-m^{(k^{\prime})}\right\|_{2,N}^{2}=0.$
(3.3)

If inequality in (3.2) is strict then there exists $0<{\lambda}({\beta},h)<1$
and $C>0$ such that, for all $k$,

$\limsup_{N\rightarrow\infty}{\mathbb{E}}\left\|m^{(k+1)}-m^{(k)}\right\|_{2,N}^{2}=C{\lambda}^{k}({\beta},h).$
(3.4)

###  3.2. Approximate solution of the iterative scheme

The proof of Theorem 3.1 relies on the construction of an explicit
representation of a sequence of approximate solutions, $\bar{m}^{(k)}$, $k\geq
1$, of the iterative scheme (1.22)-(1.23). To express $\bar{m}^{(k)}$, a
number of notations and definitions have to be introduced. We stick as much as
possible to those of [10], which gives a technically simplified approach to
the proofs of [9], based on the symmetric representation (1.2). Denoting by
$g$ and $g^{t}$, respectively, the (non-symmetric) $N\times N$ matrix with
entries $g_{i,j}$ and its transpose, we write for simplicity

${J_{N}}/{\sqrt{N}}\equiv\bar{g}=(g+g^{T})/\sqrt{2}.$ (3.5)

We now construct several sequences:

  * (i)

of real numbers $\\{{\gamma}_{k}\\}_{k\geq 1}$ and $\\{\varrho_{k}\\}_{k\geq
1}$,

  * (ii)

of random $N\times N$ matrices, $g^{(k)}$ and $\rho^{(k)}$, $k\geq 1$, and

  * (iii)

of random vectors, $\phi^{(k)}$, $\xi^{(k)}$, $\eta^{(k)}$ and $\zeta^{(k)}$
in ${\mathbb{R}}^{N}$.

Below, $Z$, $Z^{\prime}$, $Z_{1}$, _etc_. are standard Gaussian random
variables, always assumed independent when appearing in the same formula. We
denote their joint expectation by $E$. Define

${\gamma}_{1}=E\tanh(h+{\beta}Z),\quad\varrho_{1}=\sqrt{q}{\gamma}_{1}$ (3.6)

and recursively,

$\varrho_{k}=\psi(\varrho_{k-1}),\quad{\gamma}_{k}=\frac{\varrho_{k}-\sum_{j=1}^{k-1}{\gamma}_{j}^{2}}{\sqrt{q-\sum_{j=1}^{k-1}{\gamma}_{j}^{2}}},$
(3.7)

where, setting ${\mathrm{Th}}(x)\equiv\tanh(h+{\beta}x)$, the function
$\psi:[0,q]\rightarrow[0,q]$ is defined by

$\psi(t)=E{\mathrm{Th}}(\sqrt{t}Z+\sqrt{q-t}Z^{\prime}){\mathrm{Th}}(\sqrt{t}Z+\sqrt{q-t}Z^{\prime\prime}).$
(3.8)

We now define recursions for $g^{(k)}$ and $\phi^{(k)}$, as well as for the
closely related vectors ${\bar{h}}^{(k)}$ and $\bar{m}^{(k)}$. For $k=1$,

$g^{(1)}=g,\,\,\,\bar{m}^{(1)}=\sqrt{q}\bf{1}$ (3.9)

where $\bf{1}$ is as in (1.22). Assume that $g^{(s)}$, $\phi^{(s)}$ and
$\bar{m}^{(s)}$ are defined for $s\leq k$ and set

$\xi^{(s)}=g^{(s)}\phi^{(s)},\,\,\,\eta^{(s)}={g^{(s)}}^{T}\phi^{(s)},\,\,\,\text{and}\,\,\,\zeta^{(s)}=\frac{\xi^{(s)}+\eta^{(s)}}{\sqrt{2}}=\overline{g^{(s)}}\phi^{(s)}.$
(3.10)

Next write ${\Gamma}^{2}_{k-1}=\sum_{j=1}^{k-1}{\gamma}_{j}^{2}$, set
${\bar{h}}^{(1)}_{i}=\tanh^{-1}(\sqrt{q})$ for all $1\leq i\leq N$ and for
$k\geq 1$ set

${\bar{h}}^{(k+1)}_{i}=h+{\beta}\sum_{s=1}^{k-1}{\gamma}_{s}\zeta^{(s)}_{i}+{\beta}\sqrt{q-{\Gamma}^{2}_{k-1}}\zeta^{(k)}_{i},\quad
1\leq i\leq N,$ (3.11)
$\bar{m}^{(k+1)}_{i}=\tanh\left({\bar{h}}^{(k+1)}_{i}\right),\quad 1\leq i\leq
N.$ (3.12)

Finally, defining the vectors $\phi^{(k)}$ as

$\phi^{(k+1)}=\frac{\bar{m}^{(k+1)}-\sum_{s=1}^{k}\langle\bar{m}^{(k+1)},\phi^{(s)}\rangle\phi^{(s)}}{\left\|\bar{m}^{(k+1)}-\sum_{s=1}^{k}\langle\bar{m}^{(k+1)},\phi^{(s)}\rangle\phi^{(s)}\right\|_{2,N}}$
(3.13)

the matrix $g^{(k)}$ is defined recursively through

$g^{(k+1)}=g^{(k)}-\rho^{(k)}$ (3.14)

where

$\rho^{(k)}=\xi^{(k)}\otimes\phi^{(k)}+\phi^{(k)}\otimes\eta^{(k)}-\langle\phi^{(k)},\xi^{(k)}\rangle\left(\phi^{(k)}\otimes\phi^{(k)}\right),$
(3.15)

and where, given two vectors $x,y\in{\mathbb{R}}^{N}$, $x\otimes y$ the
$N\times N$ denotes the matrix with entries

$(x\otimes y)_{i,j}=\frac{x_{i}y_{j}}{N}.$ (3.16)

All of the above objects are well defined and their properties are well
understood. We refer the reader to [10] for more details.

We now specify in which sense the vector $\bar{m}^{(k)}$ of coordinates
$\bar{m}^{(k)}_{i}$ defined in (3.12) is an approximation of the vector
$m^{(k)}$ of coordinates $m^{(k)}_{i}$, $1\leq i\leq N$. For this we use
additional notations.

We write $X_{N}\simeq Y_{N}$ if $X_{N}$ and $Y_{N}$ are two random variables,
possibly depending on extra parameters (such as ${\beta}$, $h$, $k$), if there
exists a constant $C>0$, possibly depending on these parameters, but not on
$N$, such that

${\mathbb{P}}\left(|X_{N}-Y_{N}|\geq t\right)\leq Ce^{-t^{2}N/C}.$ (3.17)

If $X^{N}=\left(X^{N}_{i}\right)_{i\leq N}$ and
$Y^{N}=\left(Y^{N}_{i}\right)_{i\leq N}$ are two sequences of random vectors
in ${\mathbb{R}}^{N}$ we write $X^{N}\approx Y^{N}$ if

$\frac{1}{N}\sum_{i=1}^{N}\left|X^{N}_{i}-Y^{N}_{i}\right|\simeq 0.$ (3.18)

Let ${h}^{(k+1)}$ be the vector in ${\mathbb{R}}^{N}$ defined through

$h^{(k+1)}=h+{\beta}\bar{g}m^{(k)}-{\beta}^{2}(1-q)m^{(k-1)}$ (3.19)

and denote by ${\bar{h}}^{(k+1)}$ the vector of coordinates
${\bar{h}}^{(k+1)}_{i}$, $1\leq i\leq N$ (see (3.11)).

######  Lemma 3.2.

For all ${\beta}>0$ and all $k\in{\mathbb{N}}$

${\bar{h}}^{(k+1)}\approx{h}^{(k+1)},$ (3.20) $\bar{m}^{(k)}\approx m^{(k)}.$
(3.21)

###### Proof of Lemma 3.2.

These results are proved in [9] by explicitly constructing the iterates of the
scheme (1.23). This construction uses the matrix ${J_{N}}/{\sqrt{N}}$, while
that of [10] which we have adopted, uses the matrix $g$ from the
representation (3.5). This leads to slightly different objects. In order to
prove the lemma, the iterative method of [9] must therefore be adapted to the
present setting. We will not give the simple but lengthy details of this
adaptation. Let us only point out that in [9], the analogue of the sequence
$\bar{m}^{(k)}$ is given by the right-hand side of (1.4). It is formulated
more precisely as $\hat{m}^{(k)}$, defined above (5.2) (see also
$\bar{m}^{(k)}$ above (5.10)). Then (3.21) is obtained by combining Remark 5.2
and Remark 5.4 of [9], and one checks that this statement is in substance
deduced from (3.20). By repeating the iteration of [9] using $g$ instead of
${J_{N}}/{\sqrt{N}}$, one arrives at an expression similar to (1.4) in [9].
The gain is that one now has a structurally simple expression for the matrix
$g^{(k)}$, from which the term $\sum_{j}g_{i,j}^{(k-1)}m_{j}^{(k-1)}$ in the
right-hand side of (1.4) in [9] can easily be shown to be Gaussian,
conditional on the sigma algebra
${\mathcal{G}}_{k-2}=\left\\{\xi^{(s)},\zeta^{(s)}\mid s\leq k-2\right\\}$.
Its variance can be calculated. For finite $N$ it still depends on
${\mathcal{G}}_{k-2}$ in a complicated way, but by a SLLN it is proved to be
non-random in the limit $N\rightarrow\infty$ and given by
$\sqrt{q-{\Gamma}^{2}_{k-1}}$. ∎

This section concludes with two important structural results from [9] and
[10].

######  Lemma 3.3 (Lemma 2 of [10]).

a) $\\{\varrho_{k}\\}$ is an increasing sequence.
$\lim_{k\rightarrow\infty}\varrho_{k}=q$ if and only if (3.2) is satisfied. If
inequality in (3.2) is strict, this convergence is exponentially fast.

b) ${\Gamma}^{2}_{k-1}=\sum_{j=1}^{k-1}{\gamma}_{j}^{2}<\varrho_{k}<q$ holds
for all $k$ and $\sum_{j=1}^{\infty}{\gamma}_{j}^{2}=q$ holds if and only if
(3.2) is satisfied.

The following result is stated for $\bar{m}^{(k)}$ as Proposition 6 of [10],
and for $m^{(k)}$ as Proposition 2.5 of [9]. (In [9], $\phi^{(k)}$ is defined
as in (3.13) substituting $m^{(k)}$ for $\bar{m}^{(k)}$. The sequences
${\gamma}_{j}$ and $\varrho_{j}$ are defined in the same way in both papers.)

######  Proposition 3.4 (Proposition 6 of [10] & Proposition 2.5 of [9]).

a) For any $j<k$,

$\left\langle m^{(k)},\phi^{(j)}\right\rangle\simeq{\gamma}_{j}.$ (3.22)

b) For any $k\in{\mathbb{N}}$

$\bigl{\|}m^{(k)}\bigr{\|}^{2}_{2,N}\simeq q,$ (3.23)

and for $j<k$

$\left\langle m^{(k)},m^{(j)}\right\rangle\simeq\varrho_{j}.$ (3.24)

The proposition holds unchanged if $\bar{m}^{(k)}$ is substituted for
$m^{(k)}$.

###  3.3. Almost sure convergence results

The formulations of Lemma 3.2 and Proposition 3.4 are particularly well suited
to prove convergence results in mean of order $p$. As the next lemma shows,
they can easily be reformulated as almost sure convergence results. Note,
however, that regardless of the chosen notion of convergence, the limits in
$N$ and $k$ cannot be interchanged, as can be seen from (3.28).

######  Lemma 3.5.

Let $X^{(k)}_{N}$ and $Y^{(k)}_{N}$ be two sequences of random variables
depending on a parameter $k\in{\mathbb{N}}$. Assume that $X^{(k)}_{N}\simeq
Y^{(k)}_{N}$ in the sense of (3.17), namely, with a constant $C\equiv C(k)>0$
depending a priori on $k$ but not on $N$. Then, there exists a subset
${\Omega}^{*}\subset{\Omega}$ with ${\mathbb{P}}\left({\Omega}^{*}\right)=1$,
that does not depend on $k$ and such that on ${\Omega}^{*}$, the following
holds: for all $k\geq 1$

$\lim_{N\rightarrow\infty}\left|X^{(k)}_{N}-Y^{(k)}_{N}\right|=0,$ (3.25)

and

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\left|X^{(k)}_{N}-Y^{(k)}_{N}\right|=0.$
(3.26)

The limits in (3.26) are iterated, as opposed to joint. If the constant $C(k)$
depends on other parameters (e.g., ${\beta}$, $h$), then ${\Omega}^{*}$ also
depends on these parameters. The lemma 3.5 holds in the case of sequences
$X^{(k_{1},\dots,k_{m})}_{N}$ and $Y^{(k_{1},\dots,k_{m})}_{N}$ that depend on
finitely many parameters $k_{1}<\dots<k_{m}$ in ${\mathbb{N}}$, with
$C=C(k_{1},\dots,k_{m})>0$.

###### Proof of Lemma 3.5.

Given $\varepsilon>0$, define the collections of sets

$\begin{split}{\Omega}^{(k)}_{N}(\varepsilon)&=\left\\{{\omega}\in{\Omega}\,:\,\left|X^{(k)}_{N}({\omega})-Y^{(k)}_{N}({\omega})\right|\leq\varepsilon\right\\},\quad\forall
N\geq 1,k\geq 1,\\\ {\Omega}^{(k)}(\varepsilon)&=\textstyle{\bigcup_{N^{*}\geq
1}\bigcap_{N\geq N^{*}}}{\Omega}^{(k)}_{N}(\varepsilon),\quad\forall k\geq
1,\\\
{\Omega}^{(k)}_{0}&=\cap_{\varepsilon>0}{\Omega}^{(k)}(\varepsilon).\end{split}$
(3.27)

Further introduce the quantity

${\delta}_{k,N}^{2}\equiv\frac{2C(k)}{N}\left(\log\bigl{(}k\sqrt{|\log
C(k)|}\bigr{)}+\log N\right)$ (3.28)

and note that by (3.17) (with $C\equiv C(k)$),

${\mathbb{P}}\left(\Bigl{(}{\Omega}^{(k)}_{N}({\delta}_{k,N})\Bigr{)}^{c}\right)\leq\frac{1}{N^{2}k^{2}}.$
(3.29)

Let now $k$ be fixed. Then, ${\delta}_{k,N}$ is a decreasing function of $N$
that decays to zero as $N\uparrow\infty$. Hence, for all $\varepsilon>0$,
there exists $N(k,\varepsilon)$ such that ${\delta}_{k,N}<\varepsilon$ for all
$N\geq N(k,\varepsilon)$ and, for all $N^{*}\geq N(k,\varepsilon)$,

${\mathbb{P}}\left({\textstyle\bigcup_{N\geq
N^{*}}\bigl{(}{\Omega}^{(k)}_{N}(\varepsilon)\bigr{)}^{c}}\right)\leq\sum_{N>N^{*}}\frac{1}{N^{2}k^{2}}<\frac{1}{N^{*}k^{2}}<\infty,$
(3.30)

where we used (3.29). By Borel-Cantelli lemma, for all $\varepsilon>0$

${\mathbb{P}}\left(\left({\Omega}^{(k)}(\varepsilon)\right)^{c}\right)=\lim_{{N^{*}\rightarrow\infty}\atop{N^{*}\geq
N(k,\varepsilon)}}{\mathbb{P}}\left({\textstyle\bigcup_{N\geq
N^{*}}\bigl{(}{\Omega}^{(k)}_{N}(\varepsilon)\bigr{)}^{c}}\right)=0.$ (3.31)

From this and the monotony of ${\Omega}^{(k)}(\varepsilon)$ it then follows in
a standard way that

${\mathbb{P}}\bigl{(}{\Omega}^{(k)}_{0}\bigr{)}={\mathbb{P}}\left(\lim_{N\rightarrow\infty}\left|X^{(k)}_{N}({\omega})-Y^{(k)}_{N}({\omega})\right|=0\right)=1.$
(3.32)

Since the above holds true for any given $k\geq 1$,

${\mathbb{P}}\left({\textstyle\bigcap_{k\geq
1}}{\Omega}^{(k)}_{0}\right)={\mathbb{P}}\left(\forall{k\geq
1}\lim_{N\rightarrow\infty}\left|X^{(k)}_{N}({\omega})-Y^{(k)}_{N}({\omega})\right|=0\right)=1,$
(3.33)

which proves (3.25).

In order to prove (3.26) we must take the additional limit
$k\rightarrow\infty$. Set

${\Omega}_{0}=\textstyle{\bigcup_{k^{*}\geq 1}\bigcap_{k\geq
k^{*}}}{\Omega}^{(k)}_{0}$ (3.34)

and observe that $\cap_{k\geq 1}{\Omega}^{(k)}_{0}\subseteq{\Omega}_{0}$.
Thus, by (3.33)

$1={\mathbb{P}}\left({\textstyle\bigcap_{k\geq
1}}{\Omega}^{(k)}_{0}\right)\leq{\mathbb{P}}\left({\Omega}_{0}\right)\leq 1,$
(3.35)

and so,

${\mathbb{P}}\bigl{(}{\Omega}_{0}\bigr{)}={\mathbb{P}}\left(\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\left|X^{(k)}_{N}({\omega})-Y^{(k)}_{N}({\omega})\right|=0\right)=1.$
(3.36)

This proves (3.26). (Note that alternatively, we could have taken this second
$k\rightarrow\infty$ limit by summing (3.30) over $k$ and using Borel-Cantelli
lemma.) It is clear from the proof that the limits in (3.36) cannot be
interchanged. Taking ${\Omega}^{*}=\bigl{(}\cap_{k\geq
1}{\Omega}^{(k)}_{0}\bigr{)}\textstyle{\bigcap}{\Omega}_{0}=\cap_{k\geq
1}{\Omega}^{(k)}_{0}$ completes the proof of the lemma in the case of
sequences that depend on a single parameter, $k\in{\mathbb{N}}$. The extension
of the proof to the case of sequences depending on finitely many parameters
$k_{1}<\dots<k_{m}$ is straightforward. ∎

######  Theorem 3.6 (Almost sure version of Theorem 3.1).

Under the assumptions of Theorem 3.1, there exists a subset
${\Omega}^{*}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}^{*}({\beta},h)\right)=1$ such that on
${\Omega}^{*}({\beta},h)$,

$\lim_{k,k^{\prime}\rightarrow\infty}\limsup_{N\rightarrow\infty}\left\|m^{(k)}-m^{(k^{\prime})}\right\|_{2,N}^{2}=0.$
(3.37)

###### Proof of Theorem 3.6.

This is a simple modification of the proof of Theorem 3.1. In view of Lemma
3.5, it follows from (b) of Proposition 3.4 that there exists a subset
${\Omega}^{\prime}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}^{\prime}({\beta},h)\right)=1$ such that on
${\Omega}^{\prime}({\beta},h)$, for all $k\geq 1$

$\lim_{N\rightarrow\infty}\bigl{\|}m^{(k)}\bigr{\|}^{2}_{2,N}=q.$ (3.38)

Similarly, there exists a subset
${\Omega}^{\prime\prime}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}^{\prime\prime}({\beta},h)\right)=1$ such that on
${\Omega}^{\prime\prime}({\beta},h)$, for all $k>k^{\prime}\geq 1$

$\lim_{N\rightarrow\infty}\bigl{\langle}m^{(k)},m^{(k^{\prime})}\bigr{\rangle}=\varrho_{k^{\prime}}.$
(3.39)

Set
${\Omega}^{*}({\beta},h)={\Omega}^{\prime}({\beta},h)\cap{\Omega}^{\prime\prime}({\beta},h)$
and write

$\bigl{\|}m^{(k)}-m^{(k^{\prime})}\bigr{\|}_{2,N}^{2}=\bigl{\|}m^{(k)}\bigr{\|}_{2,N}^{2}+\bigl{\|}m^{(k^{\prime})}\bigr{\|}_{2,N}^{2}-2\bigl{\langle}m^{(k)},m^{(k^{\prime})}\bigr{\rangle}.$
(3.40)

Using (3.38) and (3.39) to first take the limit $N\rightarrow\infty$ in
(3.40), and using (a) of Lemma 3.3 together with (3.26) of Lemma 3.5 to next
take the limits $k^{\prime},k\rightarrow\infty$, the theorem follows. ∎

We conclude this section by stating the almost sure versions of three
technical lemmata from [10] needed in Section 4. Making use of Lemma 3.5,
their proofs are _mutatis mutandis_ those of their original versions. They are
omitted.

######  Lemma 3.7 (Almost sure version of Lemma 13 of [10]).

Under the assumptions of Lemma 13 of [10], there exists a subset
${\Omega}^{*}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}^{*}({\beta},h)\right)=1$ such that on
${\Omega}^{*}({\beta},h)$,

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\left\|g^{(k)}\bar{m}^{(k)}\right\|^{2}_{2,N}=0.$
(3.41)

######  Lemma 3.8 (Almost sure version of Lemma 16 of [10]).

There exists a subset ${\Omega}^{*}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}^{*}({\beta},h)\right)=1$ such that on
${\Omega}^{*}({\beta},h)$, the following holds: for all $n>2$

$\textstyle\lim_{N\rightarrow\infty}\left\langle\bar{m}^{(n)},\zeta^{(n-1)}\right\rangle={\beta}(1-q)\sqrt{q-\sum_{j=1}^{n-2}{\gamma}_{j}^{2}},$
(3.42)

and for $1\leq m\leq n-2$

$\lim_{N\rightarrow\infty}\left\langle\bar{m}^{(n)},\zeta^{(m)}\right\rangle={\beta}{\gamma}_{m}(1-q).$
(3.43)

######  Lemma 3.9 (Almost sure version of Lemma 14 of [10]).

Under the assumptions of Lemma 14 of [10], there exists a subset
${\Omega}^{*}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}^{*}({\beta},h)\right)=1$ such that on
${\Omega}^{*}({\beta},h)$, for all $k\geq 2$

$\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{i=1}^{N}f\left({\bar{h}}_{i}^{(k)}\right)=Ef(h+{\beta}\sqrt{q}Z).$
(3.44)

##  4\. Proof of Theorem 1.3

###  4.1. Proof of Theorem 1.3

Theorem 1.3 is an immediate consequence of the following two lemmata. Let
$m^{(k)}$, $k\geq 1$, be defined through the iterative scheme (1.22)-(1.23).

######  Lemma 4.1.

For all $({\beta},h)$, $h>0$, satisfying the AT-condition,

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\left|\left\\{\frac{1}{N}\Phi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)+\frac{{\beta}^{2}}{4}\left(1-q^{2}\right)\right\\}-F_{N,{\beta},h}^{HT}\left(m^{(k)}\right)\right|=0\quad{\mathbb{P}}-\text{a.s.}$
(4.1)

The same result holds with $F_{N,{\beta},h}^{TAP}$ substituted for
$F_{N,{\beta},h}^{HT}$.

######  Lemma 4.2.

For all $({\beta},h)$, $h>0$, satisfying the AT-condition,

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\left\\{\frac{1}{N}\Phi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)+\frac{{\beta}^{2}}{4}\left(1-q^{2}\right)\right\\}=SK({\beta},h)\quad{\mathbb{P}}-\text{a.s.}$
(4.2)

Before proving these two lemmata, we state a well known bound on the spectral
radius $r({J_{N}}/{\sqrt{N}})$ of ${J_{N}}/{\sqrt{N}}$ (defined above (5.4)),
which will be needed repeatedly.

######  Theorem 4.3 (Geman [29]).

${\mathbb{P}}$-almost surely,
$\displaystyle\lim_{N\rightarrow\infty}r\Bigl{(}{\textstyle{J_{N}\over\sqrt{N}}}\Bigr{)}=2$.

We are now ready to prove Lemma 4.1. In the sequel, the notation (3.1) is used
without reminder.

###### Proof of Lemma 4.1.

We first prove the lemma for $F_{N,{\beta},h}^{TAP}$. For this we use
Corollary 2.5 with $\bar{x}=m^{(k)}$. By definition of $m^{(k)}$,
$q_{\text{EA}}\left(m^{(k)}\right)\leq 1$. Hence (2.11) holds with $\kappa=1$
and

$\begin{split}&\left|\left\\{\frac{1}{N}\Phi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)+\frac{{\beta}^{2}}{4}\left(1-q^{2}\right)\right\\}-F_{N,{\beta},h}^{TAP}\left(m^{(k)}\right)\right|\\\
\leq\,\,&2\sqrt{\left\|\nabla\Psi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)\right\|_{2,N}^{2}}+\frac{{\beta}}{4}\left(q-q_{\text{EA}}\left(m^{(k)}\right)\right)^{2}.\end{split}$
(4.3)

It remains to prove that in the AT-region, passing first to the limit
$N\rightarrow\infty$ and then $k\rightarrow\infty$, both terms on the right-
hand side of (4.1) vanish ${\mathbb{P}}$-almost surely.

Proceeding as in the proof of Theorem 3.6 (see (3.38)),

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\frac{{\beta}}{4}\left(q-q_{\text{EA}}\left(m^{(k)}\right)\right)^{2}=0\quad{\mathbb{P}}-{\text{a.s.}}$
(4.4)

Let us now establish that in the AT-region,

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\sqrt{\left\|\nabla\Psi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)\right\|_{2,N}^{2}}=0\quad{\mathbb{P}}-{\text{a.s.}}$
(4.5)

By (2.2),

$\frac{{\partial}}{{\partial}x_{i}}\Psi_{N,{\beta},{\bf{h}}}(x)={\beta}(A_{N}x)_{i}+h-I^{\prime}(x_{i})=0,\quad
1\leq i\leq N,$ (4.6)

where $I^{\prime}(x)=(I^{*}(x))^{-1}=\tanh^{-1}(x)$. Thus

$\left\|\nabla\Psi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)\right\|_{2,N}^{2}=\frac{1}{N}\sum_{i=1}^{N}\left[{\beta}\left(A_{N}m^{(k)}\right)_{i}+h-\tanh^{-1}\bigl{(}m^{(k)}_{i}\bigr{)}\right]^{2}$
(4.7)

Now, since $m^{(k)}$ obeys (1.23) we have, using (2.1),

$\tanh^{-1}\bigl{(}m^{(k)}_{i}\bigr{)}=h+{\beta}\left({\textstyle{J_{N}\over\sqrt{N}}}m^{(k-1)}\right)_{i}-{\beta}^{2}(1-q)m^{(k-2)}_{i}\quad
1\leq i\leq N.$ (4.8)

Inserting (4.8) in (4.7) yields

$\displaystyle\left\|\nabla\Psi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)\right\|_{2,N}^{2}$
(4.9) $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\left[{\beta}\left({\textstyle{J\over\sqrt{N}}}\left(m^{(k)}-m^{(k-1)}\right)\right)_{i}-{\beta}^{2}(1-q)\left(m^{(k)}-m^{(k-2)}\right)_{i}\right]^{2}$
$\displaystyle\leq$ $\displaystyle
2{\beta}r^{2}\bigl{(}{\textstyle{J\over\sqrt{N}}}\bigr{)}\left\|m^{(k)}-m^{(k-1)}\right\|^{2}_{2,N}+2{\beta}^{2}(1-q)\left\|m^{(k)}-m^{(k-2)}\right\|^{2}_{2,N},$

where we used the Courant-Fisher minimax principle in the last line. Eq. (4.5)
now readily follows from Theorem 4.3, Theorem 3.6 and the continuity of
$x\rightarrow\sqrt{x}$ on ${\mathbb{R}}^{+}$.

Taking the limits of both sides of (4.3), it follows from (4.4) and (4.5) that
(4.1) holds with $F_{N,{\beta},h}^{HT}$ replaced by $F_{N,{\beta},h}^{TAP}$.
That (4.1) holds for the function $F_{N,{\beta},h}^{HT}$ itself follows from
(4.5) by virtue of the last claim of Corollary 2.5. Lemma 4.1 is proven. ∎

###### Proof of Lemma 4.2.

Consider the first term in the left-hand side of (4.2). By (2.2),

$\frac{1}{N}\Phi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)=-\frac{{\beta}}{2N}\left(m^{(k)},A_{N}m^{(k)}\right)+\frac{1}{N}\sum_{i=1}^{N}I^{*}\left({\beta}\left(A_{N}m^{(k)}\right)_{i}+h\right).$
(4.10)

In view of (1.7) and (4.10), Lemma 4.2 will be proven if we can establish the
following two claims hold ${\mathbb{P}}$-almost surely:

$\displaystyle\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\frac{{\beta}}{2N}\left(m^{(k)},A_{N}m^{(k)}\right)$
$\displaystyle=$ $\displaystyle\frac{{\beta}^{2}}{2}q(1-q),$ (4.11)
$\displaystyle\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{i=1}^{N}I^{*}\left({\beta}\left(A_{N}m^{(k)}\right)_{i}+h\right)$
$\displaystyle=$ $\displaystyle\log 2+E\log\cosh({\beta}\sqrt{q}Z+h).\quad$
(4.12)

We first prove (4.11). Recall the definition of the symmetrized matrix
$\bar{g}$ from (3.5). Using the notations (3.1) and the definition (2.1), we
have

$\left\langle m^{(k)},A_{N}m^{(k)}\right\rangle=\left\langle
m^{(k)},\bar{g}m^{(k)}\right\rangle-{\beta}(1-q)\left\|m^{(k)}\right\|^{2}_{2,N}.$
(4.13)

Proceeding as in the proof of (4.4),

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}{\beta}(1-q)\left\|m^{(k)}\right\|^{2}_{2,N}={\beta}q(1-q)\quad{\mathbb{P}}-\text{a.s.}$
(4.14)

To deal with the first term on the right-hand side of (4.13), we decompose
this term into

$\left\langle
m^{(k)},\bar{g}m^{(k)}\right\rangle=T^{(k)}_{N,1}+T^{(k)}_{N,2}+T^{(k)}_{N,3}+T^{(k)}_{N,4}$
(4.15)

where

$T^{(k)}_{N,1}=\left\langle
m^{(k)}-\bar{m}^{(k)},\bar{g}\left(m^{(k)}-\bar{m}^{(k)}\right)\right\rangle,$
(4.16) $T^{(k)}_{N,2}=2\left\langle
m^{(k)}-\bar{m}^{(k)},\bar{g}m^{(k)}\right\rangle,$ (4.17)
$T^{(k)}_{N,3}=\left\langle\bar{m}^{(k)},\overline{g^{(k)}}\bar{m}^{(k)}\right\rangle,$
(4.18)
$T^{(k)}_{N,4}=\left\langle\bar{m}^{(k)},(\bar{g}-\overline{g^{(k)}})\bar{m}^{(k)}\right\rangle$
(4.19)

where $\overline{g^{(k)}}$ is the symmetrized matrix defined in (3.10). By
Cauchy-Schwarz’s inequality, the bound $\left\|m^{(k)}\right\|^{2}_{2,N}\leq
1$ and the Courant-Fisher minimax principle we have

$\displaystyle\bigl{|}T^{(k)}_{N,1}\bigr{|}$ $\displaystyle\leq$
$\displaystyle r(\bar{g})\left\|m^{(k)}-\bar{m}^{(k)}\right\|^{2}_{2,N},$
(4.20) $\displaystyle\bigl{|}T^{(k)}_{N,2}\bigr{|}$ $\displaystyle\leq$
$\displaystyle
2\left\|m^{(k)}-\bar{m}^{(k)}\right\|_{2,N}\left\|\bar{g}m^{(k)}\right\|_{2,N}\leq
2r^{2}(\bar{g})\left\|m^{(k)}-\bar{m}^{(k)}\right\|_{2,N},$ (4.21)
$\displaystyle\bigl{|}T^{(k)}_{N,3}\bigr{|}$ $\displaystyle\leq$
$\displaystyle\left\|\bar{m}^{(k)}\right\|_{2,N}\left\|\overline{g^{(k)}}\bar{m}^{(k)}\right\|_{2,N}\leq\left\|g^{(k)}\bar{m}^{(k)}\right\|_{2,N}.$
(4.22)

On the one hand, by (3.41) of Lemma 3.7,
$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}T^{(k)}_{N,3}=0$
${\mathbb{P}}$-a.s.. On the other hand, by (3.21) of Lemma 3.2 and Lemma 3.5.

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\left\|m^{(k)}-\bar{m}^{(k)}\right\|^{2}_{2,N}=0\quad{\mathbb{P}}-\text{a.s.},$
(4.23)

and by this and Theorem 4.3,
$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}T^{(k)}_{N,i}=0$
${\mathbb{P}}$-a.s. for $i=1,2$.

It remains to deal with $T^{(k)}_{N,4}$. By (3.14) and (3.15)

$\displaystyle T^{(k)}_{4}$ $\displaystyle=$
$\displaystyle\sum_{l=1}^{k-1}\left\langle\bar{m}^{(k)},\overline{\rho^{(k)}}\bar{m}^{(k)}\right\rangle$
(4.24) $\displaystyle=$
$\displaystyle\sum_{l=1}^{k-1}\left\\{2\left\langle\bar{m}^{(k)},\zeta^{(l)}\right\rangle\left\langle\bar{m}^{(k)},\phi^{(l)}\right\rangle-\left\langle\phi^{(l)},\zeta^{(l)}\right\rangle\left\langle\bar{m}^{(k)},\phi^{(l)}\right\rangle^{2}\right\\}.$
(4.25)

We treat the two terms in the brackets separately, starting with the first.
For $k\geq 2$, set

$a^{(k,l)}\equiv\begin{cases}{\beta}(1-q)\sqrt{q-{\Gamma}^{2}_{k-2}}&\mbox{if
}\,l=k-1,\\\ {\beta}(1-q){\gamma}_{l}&\mbox{if }\,1\leq l\leq k-2.\end{cases}$
(4.26)

By Lemma 3.8, there exists a subset ${\Omega}_{1}({\beta},h)\subset{\Omega}$
with ${\mathbb{P}}\left({\Omega}_{1}({\beta},h)\right)=1$ such that on
${\Omega}_{1}({\beta},h)$, for all $1\leq l\leq k-1$ and $k\geq 2$

$\lim_{N\rightarrow\infty}\left\langle\bar{m}^{(k)},\zeta^{(l)}\right\rangle=a^{(k,l)},$
(4.27)

whereas by (3.22) of Proposition 3.4 and Lemma 3.5, there exists a subset
${\Omega}_{2}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}_{2}({\beta},h)\right)=1$ such that on
${\Omega}_{2}({\beta},h)$, for all $1\leq l\leq k-1$ and $k\geq 2$

$\lim_{N\rightarrow\infty}\left\langle\bar{m}^{(k)},\phi^{(l)}\right\rangle={\gamma}_{l}.$
(4.28)

Thus, on ${\Omega}_{1}({\beta},h)\cap{\Omega}_{2}({\beta},h)$, for all $1\leq
l\leq k-1$ and $k\geq 2$

$\lim_{N\rightarrow\infty}\left\langle\bar{m}^{(k)},\zeta^{(l)}\right\rangle\left\langle\bar{m}^{(k)},\phi^{(l)}\right\rangle={\gamma}_{l}a^{(k,l)}.$
(4.29)

We now turn to the second term in the brackets in (4.25). Note that
$\left\|\phi^{(l)}\right\|^{2}_{2,N}=1$ and
$\left\|m^{(k)}\right\|^{2}_{2,N}\leq 1$ so that
$\left|\left\langle\bar{m}^{(k)},\phi^{(l)}\right\rangle\right|\leq 1$, while
by Lemma 11 of [10] $\left\langle\phi^{(l)},\zeta^{(l)}\right\rangle$ is
Gaussian with mean zero and variance $1/N$. From this it follows that there
exists a subset ${\Omega}_{3}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}_{3}({\beta},h)\right)=1$ such that on
${\Omega}_{3}({\beta},h)$, for all $1\leq l\leq k-1$ and $k\geq 2$

$\lim_{N\rightarrow\infty}\left\langle\phi^{(l)},\zeta^{(l)}\right\rangle\left\langle\bar{m}^{(k)},\phi^{(l)}\right\rangle^{2}=0.$
(4.30)

Plugging (4.29) and (4.30) in (4.25) we obtain that on
$\cap_{i=1}^{3}{\Omega}_{i}({\beta},h)$, for all $1\leq l\leq k-1$ and $k\geq
2$

$\lim_{N\rightarrow\infty}T^{(k)}_{N,4}=2\sum_{l=1}^{k-1}{\gamma}_{l}a^{(k,l)}=2{\beta}(1-q){\gamma}_{k-1}\sqrt{q-{\Gamma}^{2}_{k-2}}+2{\beta}(1-q){\Gamma}^{2}_{k-2},$
(4.31)

where ${\Gamma}^{2}_{k-2}$ is defined below (3.10). Using (b) of Lemma 3.3 and
reasoning as in the proof of (3.26) to pass to the limit $k\rightarrow\infty$,
we get that on $\cap_{i=1}^{3}{\Omega}_{i}({\beta},h)$

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}T^{(k)}_{N,4}=2{\beta}q(1-q).$
(4.32)

Inserting the above results in (4.15), we obtain that

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\left\langle
m^{(k)},\bar{g}m^{(k)}\right\rangle=2{\beta}q(1-q)\quad{\mathbb{P}}-\text{a.s.}$
(4.33)

Finally, (4.11) follows from (4.33), (4.14) and (4.13).

It remains to prove (4.12). From the definition of $I^{*}$, (2.1) and (3.19),
we have

$\frac{1}{N}\sum_{i=1}^{N}I^{*}\left({\beta}\left(A_{N}m^{(k)}\right)_{i}+h\right)=\log
2+\frac{1}{N}\sum_{i=1}^{N}\log\cosh\bigl{(}{h}^{(k+1)}_{i}\bigr{)}.$ (4.34)

Recalling the definition of ${\bar{h}}^{(k+1)}_{i}$ from (3.11), we decompose
the last term in (4.34) into

$\frac{1}{N}\sum_{i=1}^{N}\log\cosh\bigl{(}{h}^{(k+1)}_{i}\bigr{)}={\overline{T}}^{(k)}_{N,1}+{\overline{T}}^{(k)}_{N,2}+E\log\cosh({\beta}\sqrt{q}Z+h)$
(4.35)

where

$\displaystyle{\overline{T}}^{(k)}_{N,1}$ $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\left[\log\cosh\bigl{(}{h}^{(k+1)}_{i}\bigr{)}-\log\cosh\bigl{(}{\bar{h}}^{(k+1)}_{i}\bigr{)}\right],$
(4.36) $\displaystyle{\overline{T}}^{(k)}_{N,2}$ $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\log\cosh\bigl{(}{\bar{h}}^{(k+1)}_{i}\bigr{)}-E\log\cosh({\beta}\sqrt{q}Z+h).$
(4.37)

Now, by Lemma 3.9, there exists a subset
${\Omega}_{4}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}_{4}({\beta},h)\right)=1$ such that on
${\Omega}_{4}({\beta},h)$, for all $k\geq 1$

$\lim_{N\rightarrow\infty}{\overline{T}}^{(k)}_{N,2}=0.$ (4.38)

Turning to ${\overline{T}}^{(k)}_{N,1}$, observe that

$\textstyle\bigl{|}{\overline{T}}^{(k)}_{N,1}\bigr{|}\leq\frac{1}{N}\sum_{i=1}^{N}\bigl{|}{h}^{(k+1)}_{i}-{\bar{h}}^{(k+1)}_{i}\bigr{|}.$
(4.39)

It then follows from (4.39), (3.20) of Lemma 3.2 and the definition (3.18)
that

$\textstyle\bigl{|}{\overline{T}}^{(k)}_{N,1}\bigr{|}\leq\frac{1}{N}\sum_{i=1}^{N}\bigl{|}{h}^{(k+1)}_{i}-{\bar{h}}^{(k+1)}_{i}\bigr{|}\simeq
0,$ (4.40)

and so, by Lemma 3.5 there exists a subset
${\Omega}_{5}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}_{5}({\beta},h)\right)=1$ such that on
${\Omega}_{5}({\beta},h)$, for all $k\geq 1$

$\lim_{N\rightarrow\infty}{\overline{T}}^{(k)}_{N,1}=0.$ (4.41)

Inserting (4.38), and (4.41) in (4.35) and again reasoning as in the proof of
(3.26) to pass to the limit $k\rightarrow\infty$, the claim of (4.12) follows.
The proof of Lemma 4.2 is done. ∎

The proof of Theorem 1.3 is complete.

##  5\. Analysis of the Hessian of $\Psi_{N,{\beta},{\bf{h}}}$

###  5.1. Main results and strategy

Let ${\mathcal{H}}_{N}(m)\equiv{\mathcal{H}}_{N,{\beta},{\bf{h}}}(m)$ denote
the Hessian matrix of $\Psi_{N,{\beta},{\bf{h}}}$ at $m$. Given
$\sqrt{3/4}\leq\varrho\leq 1$, consider the set

${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)=\left\\{m\in[-1,1]^{N}:q_{\text{EA}}(m)\geq\varrho-\varrho(1-\varrho){\epsilon}\right\\}.$
(5.1)

The main result of this section establishes that ${\mathcal{H}}_{N}(m)$ is
strictly negative definite on ${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ for
all $({\beta},h)$ in ${\mathcal{D}}^{(1)}\cap{\mathcal{D}}^{(2)}_{\varrho}$,
where ${\mathcal{D}}^{(1)}$ and ${\mathcal{D}}^{(2)}_{\varrho}$ are defined in
(1.28) and (1.30), respectively.

######  Theorem 5.1.

(i) Let $\sqrt{3/4}\leq\varrho$ be given. For all $({\beta},h)$ in
${\mathcal{D}}^{(2)}_{\varrho}$

${\mathbb{P}}\left(\bigcup_{N_{0}}\bigcap_{N\geq
N_{0}}\left\\{\sup_{{\epsilon}\in[0,1]}\sup_{m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)}{\lambda}_{max}({\mathcal{H}}_{N}(m))<0\right\\}\right)=1,$
(5.2)

(ii) For all $({\beta},h)$ in ${\mathcal{D}}^{(1)}$

${\mathbb{P}}\left(\bigcup_{N_{0}}\bigcap_{N\geq
N_{0}}\left\\{\sup_{m\in[-1,1]^{N}}{\lambda}_{max}({\mathcal{H}}_{N}(m))<0\right\\}\right)=1.$
(5.3)

The proofs of the two items of Theorem 5.1 follow very different strategies.
Item (ii) is based on elementary arguments and is proved at the very end of
the section, while the proof of item (i) occupies most of it.

First, we set up the necessary matrix notation. Let $M_{N}$ be an $N\times N$
real symmetric matrix. We write $M_{N}<0$ (resp., $M_{N}>0$) when $M_{N}$ is
strictly negative (resp., positive) definite. The notation
$M_{N}=\textrm{diag}(\mu_{1},\dots,\mu_{N})$ indicates that $M_{N}$ is
diagonal with diagonal entries $M_{ii}=\mu_{i}$. We denote by
${\lambda}_{max}(M_{N})$ and ${\lambda}_{min}(M_{N})$ the largest and smallest
eigenvalues of $M_{N}$, and by $r(M_{N})$ its spectral radius, i.e. the
largest absolute value of its eigenvalues. The operator norm of $M_{N}$ is
denoted by $\|M_{N}\|$ and defined by

$\|M_{N}\|=\sup_{x:\|x\|_{2}=1}\|M_{N}x\|_{2}.$ (5.4)

Finally, we recall that eigenvalues, spectral radius and operator norm are
related through

$\textstyle\sup_{x:\|x\|_{2}=1}|(x,M_{N}x)|=r(M_{N})=\sqrt{r(M^{2}_{N})}=\|M_{N}\|.$
(5.5)

The central idea behind the proof of item (i) of Theorem 5.1 is to replace the
condition on the negative definiteness of the Hessian matrix
${\mathcal{H}}_{N}(m)$, which, as we will see, is of additive form, by a
condition on the spectrum of a matrix, which takes the form of a product and
is easier to study. To this end, we go back to the function
$\Psi_{N,{\beta},{\bf{h}}}$ and, taking second partial derivatives, we get

${\mathcal{H}}_{N}(m)={\beta}\frac{J_{N}}{\sqrt{N}}-B_{N}(m)$ (5.6)

where $B_{N}(m)=\textrm{diag}(b_{1}(m),\dots,b_{N}(m))$ and

$b_{i}(m)={\beta}^{2}(1-q)+\frac{1}{1-m_{i}^{2}},\quad 1\leq i\leq N.$ (5.7)

Since $b_{i}(m)>0$ for each $1\leq i\leq N$, $B_{N}(m)$ is strictly positive
definite and has rank $N$. Denoting by $B^{1/2}_{N}(m)$ its strictly unique
positive definite square root and by $B^{-1/2}_{N}(m)$ its inverse, (5.6) may
be written as

${\mathcal{H}}_{N}(m)=B^{1/2}_{N}(m)\left({\beta}C_{N}(m)-I_{N}\right)B^{1/2}_{N}(m)$
(5.8)

where $I_{N}$ is the identity matrix in ${\mathbb{R}}^{N}$ and

$C_{N}(m)\equiv B^{-1/2}_{N}(m)\frac{J_{N}}{\sqrt{N}}B^{-1/2}_{N}(m).$ (5.9)

By definition, ${\mathcal{H}}_{N}(m)$ is strictly negative definite if
$(x,{\mathcal{H}}_{N}(m)x)<0$ for all non-zero $x\in{\mathbb{R}}^{N}$, and
this is true if and only if all eigenvalues of ${\mathcal{H}}_{N}(m)$ are
strictly negative. Since $\mathop{\rm rank}\nolimits
B^{1/2}_{N}(m)=\mathop{\rm rank}\nolimits B_{N}(m)=N$, it follows from (5.8)
that ${\mathcal{H}}_{N}(m)<0$ if and only if ${\beta}C_{N}(m)-I<0$. Thus, a
necessary and sufficient condition for ${\mathcal{H}}_{N}(m)$ to be strictly
negative definite is

${\beta}{\lambda}_{max}(C_{N}(m))<1.$ (5.10)

Theorem 5.1 will then be deduced from the following proposition. Let
$\SS_{N,{\epsilon}}(\varrho)$ denote the spherical shell

$\SS_{N,{\epsilon}}(\varrho)=\left\\{m\in[-1,1]^{N}:|q_{\text{EA}}(m)-\varrho|\leq\varrho(1-\varrho){\epsilon}\right\\}\subset{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho).$
(5.11)

For $0\leq\varrho\leq q$, recalling the definition of $\vartheta(\varrho)$
from (1.29), set

$\displaystyle f_{1}(\varrho)$ $\displaystyle=$
$\displaystyle\vartheta(\varrho)$ (5.12) $\displaystyle f_{2}({\beta},q)$
$\displaystyle=$ $\displaystyle 2{\beta}-\left({\beta}^{2}(1-q)+1\right).$
(5.13)

######  Proposition 5.2.

(i) For all $({\beta},h)$, $h>0$, all $\varrho\geq\sqrt{3/4}$ and all $N$
large enough

${\mathbb{P}}\left(\sup_{{\epsilon}\in[0,1]}\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}{\lambda}_{max}(C_{N}(m))\geq
f_{1}(\varrho)+16\sqrt{{\textstyle{\log N\over\sqrt{N}}}}\right)\leq
6e^{-\sqrt{N}}.$ (5.14)

(ii) For all $({\beta},h)$, $h>0$, and all $N$ large enough

${\mathbb{P}}\left(\sup_{m\in[-1,1]^{N}}{\lambda}_{max}({\mathcal{H}}_{N}(m))\geq
f_{2}({\beta},q)+{\beta}N^{-1/4}\right)\leq 2e^{-\sqrt{N}/4}.$ (5.15)

Again, the bulk of the proof of Proposition 5.2 is devoted to proving
assertion (i), which will itself be deduced from an analogous statement for
the operator norm $\|C_{N}(m)\|$. From (5.6) and (5.9) we see, by comparing
the condition ${\mathcal{H}}_{N}(m)<0$ and (5.10), that we have turned a
condition on the spectrum of a deterministic full-rank perturbation of a
standard Gaussian Wigner random matrix, $J_{N}/\sqrt{N}$, into a condition on
the spectrum of the sole Wigner-type Gaussian random matrix $C_{N}$ whose
entries, $C_{ij}(m)$, are also independent centred Gaussians, but now have
non-identical variances. More specifically, setting

$a_{i}(m)\equiv b^{-1}_{i}(m),\quad 1\leq i\leq N,$ (5.16)

we have

$C_{ij}(m)=J_{ij}v_{ij}(m),\quad
v_{ij}(m)\equiv\sqrt{\frac{a_{i}(m)a_{j}(m)}{N}}.$ (5.17)

While there are few tools available to deal with non-finite rank perturbations
of Wigner random matrices (see [18], [19]), the question of finding bounds on
the norm or largest eigenvalue of non-homogeneous Wigner-type random matrices
such as $C_{N}(m)$ has recently witnessed significant developments [7], [37].
The proof of Proposition 5.2 is based on results of [7] which, for the
convenience of the reader, we state below in a version specialised to the
matrices (5.17).

######  Theorem 5.3 (Theorem 1.1 and Corollary 3.9 of [7]).

Given $m\in[-1,1]^{N}$ set

${\sigma}(m)=\max_{i}\sqrt{\sum_{j}v_{ij}^{2}(m)},\quad{\sigma_{\star}(m)}=\max_{ij}|v_{ij}(m)|.$
(5.18)

Then, for any $0<\varepsilon\leq 1/2$

${\mathbb{E}}\|C_{N}(m)\|\leq(1+\varepsilon)\left\\{2{\sigma}(m)+\frac{6}{\sqrt{\log(1+\varepsilon)}}{\sigma_{\star}(m)}\sqrt{\log
N}\right\\}.$ (5.19)

In addition, for any $0<\varepsilon\leq 1/2$ and $t\geq 0$

${\mathbb{P}}\left(\|C_{N}(m)\|\geq{\mathbb{E}}\|C_{N}(m)\|+t\sqrt{N}{\sigma}_{\star}(m)\right)\leq
e^{-Nt^{2}/4}.$ (5.20)

The bound (5.19) is expected to be best when the coefficients $v_{ij}(m)$ are
not too inhomogeneous (see Lemma 3.14 and its corollary in Section 3.5 of
[7]). However, since we want to bound the supremum of $\|C_{N}(m)\|$ over
$\SS_{N,{\epsilon}}(\varrho)$, we also have to deal with matrices with highly
inhomogeneous coefficients. To explain the difficulty we face, let us first
state a useful lemma. Set

$\varrho^{\pm}_{{\epsilon}}\equiv\varrho\pm\varrho(1-\varrho){\epsilon},$
(5.21)

and for $y\in[0,1]$

$c_{0}(y)\equiv\left({\beta}^{2}(1-q)+1/y\right)^{-1}.$ (5.22)

######  Lemma 5.4.

$\displaystyle(1-\varrho^{+}_{{\epsilon}})c_{0}(1)\leq$
$\displaystyle\displaystyle\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\frac{1}{N}\sum_{j}a_{j}(m)$
$\displaystyle\leq c_{0}(1-\varrho^{-}_{{\epsilon}})$ (5.23) $\displaystyle
c_{0}(1-\varrho^{-}_{{\epsilon}})\leq$
$\displaystyle\displaystyle\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\max_{i}a_{i}(m)$
$\displaystyle\leq c_{0}(1)\leq 1.$ (5.24)

If we were to apply Theorem 5.3 to bound
$\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\|C_{N}(m)\|$, we would have to replace
${\sigma}(m)$ and ${\sigma_{\star}(m)}$ by their supremum, which, according to
Lemma 5.4, gives

$\textstyle\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}{\sigma}(m)\leq\sqrt{c_{0}(1)c_{0}(1-\varrho^{-}_{{\epsilon}})},\quad\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}{\sigma_{\star}(m)}\leq
c_{0}(1)/\sqrt{N}.$ (5.25)

Thus, the deviation term that comes from Gaussian concentration in (5.20)
would outweigh the mean value of the operator norm. Since $t$ must be chosen
large enough to control the supremum over $\SS_{N,{\epsilon}}(\varrho)$, we
see that this approach cannot provide a useful bound on the operator norm.
Instead of applying Theorem 5.3 directly to $C_{N}(m)$, we will introduce
upper and lower thresholds on $a_{j}(m)$ and decompose the matrix into a sum
of three terms,
$C_{N}(m)=\underline{C}_{N}(m)+C^{\circ}_{N}(m)+\overline{C}_{N}(m)$,
depending on the size of these coefficients. Theorem 5.3 is then be applied to
a matrix $C^{\circ}_{N}(m)$ with “tamed coefficient”, that are neither too
large nor too small compared to the average $\frac{1}{N}\sum_{j}a_{j}(m)$.

###  5.2. Decomposition of the matrix $C_{N}(m)$

Given $0<\theta_{\star}<\theta\leq 1$ to be chosen later, define the sets

$\displaystyle{\Lambda}\equiv{\Lambda}(m,\theta)$ $\displaystyle=$
$\displaystyle\left\\{1\leq i\leq N\,\Big{|}\,1-m^{2}_{i}>\theta\right\\},$
(5.26)
$\displaystyle{\Lambda}_{\star}\equiv{\Lambda}_{\star}(m,\theta_{\star})$
$\displaystyle=$ $\displaystyle\\{1\leq i\leq N\mid
1-m^{2}_{i}>\theta_{\star}\\}.$ (5.27)

Note that ${\Lambda}(m,\theta)\subset{\Lambda}_{\star}(m,\theta_{\star})$.
Using $\theta_{\star}$ and ${\Lambda}_{\star}$, we define the modified
coefficients

${\tilde{a}}_{i}(m)=\begin{cases}a_{i}(m)&\text{if}\,\,\,i\in{\Lambda}_{\star},\\\
c_{0}(\theta_{\star})&\text{if}\,\,\,i\in{\Lambda}^{c}_{\star},\end{cases},\quad
1\leq i\leq N.$ (5.28)

Unlike $a_{i}(m)$, ${\tilde{a}}_{i}(m)$ is bounded from below and its
derivative is bounded on $[-1,1]$. By analogy with (5.7), (5.16) and (5.9) we
set
${\widetilde{B}}_{N}(m)=\textrm{diag}({\tilde{b}}_{1}(m),\dots,{\tilde{b}}_{N}(m))$
where ${\tilde{b}}_{i}(m)={\tilde{a}}^{-1}_{i}(m)$, $1\leq i\leq N$, and

${\widetilde{C}}_{N}(m)\equiv{\widetilde{B}}^{-1/2}_{N}(m)\frac{J_{N}}{\sqrt{N}}{\widetilde{B}}^{-1/2}_{N}(m).$
(5.29)

As usual, we denote the entries of ${\widetilde{C}}_{N}(m)$ by
$\widetilde{C}_{ij}(m)$. The set ${\Lambda}$ is then used to define the matrix
$\overline{C}_{N}(m)$ with entries

$\overline{C}_{ij}(m)\equiv\begin{cases}{\widetilde{C}}_{ij}(m)&\text{for
all}\,\,\,(i,j)\in{\Lambda}\times{\Lambda},\\\ 0&\text{else}.\end{cases}$
(5.30)

If we also set

$\displaystyle\underline{C}_{N}(m)$ $\displaystyle\equiv$ $\displaystyle
C_{N}(m)-{\widetilde{C}}_{N}(m),$ (5.31) $\displaystyle C^{\circ}_{N}(m)$
$\displaystyle\equiv$
$\displaystyle{\widetilde{C}}_{N}(m)-\overline{C}_{N}(m),$ (5.32)

we obtain the decomposition

$C_{N}(m)=\underline{C}_{N}(m)+C^{\circ}_{N}(m)+\overline{C}_{N}(m).$ (5.33)

By the triangle inequality

$\left\|C_{N}(m)\right\|\leq\left\|\underline{C}_{N}(m)\right\|+\left\|C^{\circ}_{N}(m)\right\|+\left\|\overline{C}_{N}(m)\right\|.$
(5.34)

We begin by establishing a priori bounds on the operator norm of
$\underline{C}_{N}(m)$ and $\overline{C}_{N}(m)$. To do so, we use the
following notations. Given an $N\times N$ matrix
$M_{N}\equiv\left(M_{ij}\right)_{1\leq i,j\leq N}$ and a subset $U$ of
$\\{1,\dots,N\\}$, we denote by $M_{U}$ the $N\times N$ matrix of entries
$\left(M_{U}\right)_{ij}=M_{ij}$ for all $(i,j)\in U\times U$ and
$\left(M_{U}\right)_{ij}=0$ else. In this way,

$\overline{C}_{N}(m)=\bigl{(}{\widetilde{C}}(m)\bigr{)}_{{\Lambda}}=\bigl{(}{\widetilde{B}}^{-1/2}(m)\bigr{)}_{{\Lambda}}\frac{J_{{\Lambda}}}{\sqrt{N}}\bigl{(}{\widetilde{B}}^{-1/2}(m)\bigr{)}_{{\Lambda}},$
(5.35)

and by the submultiplicativity property of matrix norms

$\left\|\overline{C}_{N}(m)\right\|\leq\left\|\bigl{(}{\widetilde{B}}^{-1/2}(m)\bigr{)}_{{\Lambda}}\right\|^{2}\left\|\frac{J_{{\Lambda}}}{\sqrt{N}}\right\|\leq
c_{0}(1)\left\|\frac{J_{{\Lambda}}}{\sqrt{N}}\right\|,$ (5.36)

where we used that by (5.28), the inclusion
${\Lambda}(m,\theta)\subset{\Lambda}_{\star}(m,\theta_{\star})$ and (5.24),

$\textstyle\bigl{\|}\bigl{(}{\widetilde{B}}^{-1/2}(m)\bigr{)}_{{\Lambda}}\bigr{\|}^{2}\leq\sup_{i\in{\Lambda}}{\tilde{a}}_{i}(m)=\sup_{i\in{\Lambda}}a_{i}(m)\leq
c_{0}(1).$ (5.37)

Turning to $\underline{C}_{N}(m)$, we set

$\displaystyle\Delta_{N}(m)$ $\displaystyle\equiv$ $\displaystyle
B^{-1/2}_{N}(m)-{\widetilde{B}}^{-1/2}_{N}(m)$ (5.38) $\displaystyle=$
$\displaystyle\textrm{diag}\left(\bigl{(}\sqrt{a_{i}(m)}-\sqrt{{\tilde{a}}_{i}(m)}\bigr{)},1\leq
i\leq N\right)=(\Delta(m))_{{\Lambda}^{c}_{\star}}$ (5.39)

where the last equality follows from (5.28). Thus, by (5.31), (5.9) and (5.29)

$\begin{split}\underline{C}_{N}(m)&=(\Delta(m))_{{\Lambda}^{c}_{\star}}\frac{J_{N}}{\sqrt{N}}{\widetilde{B}}^{-1/2}_{N}(m)+{\widetilde{B}}^{-1/2}_{N}(m)\frac{J_{N}}{\sqrt{N}}(\Delta(m))_{{\Lambda}^{c}_{\star}}\\\
&+(\Delta(m))_{{\Lambda}^{c}_{\star}}\frac{J_{N}}{\sqrt{N}}(\Delta(m))_{{\Lambda}^{c}_{\star}}.\end{split}$
(5.40)

By the triangle identity and the submultiplicativity property, bounding the
matrix $\underline{C}_{N}(m)$ reduces to bounding each of the matrices that
appear on the right-hand side of (5.40). Proceeding as in (5.37) to bound
$\bigl{\|}{\widetilde{B}}^{-1/2}_{N}(m)\|$, and observing that since
$\sqrt{a_{i}(m)}\leq\sqrt{{\tilde{a}}_{i}(m)}$ for all
$i\in{\Lambda}^{c}_{\star}$,

$\displaystyle\bigl{\|}(\Delta(m))_{{\Lambda}^{c}_{\star}}\bigr{\|}$
$\displaystyle\leq$
$\displaystyle\textstyle\sup_{i\in{\Lambda}^{c}_{\star}}\bigl{|}\sqrt{a_{i}(m)}-\sqrt{{\tilde{a}}_{i}(m)}\bigr{|}\leq\sqrt{c_{0}(\theta_{\star})},\quad$
(5.41)

we get

$\left\|\underline{C}_{N}(m)\right\|\leq
3\sqrt{c_{0}(1)c_{0}(\theta_{\star})}\left\|\frac{J_{N}}{\sqrt{N}}\right\|.$
(5.42)

Inserting (5.36) and (5.42) in (5.34) and taking the supremum over
$m\in\SS_{N,{\epsilon}}(\varrho)$, obtain

$\begin{split}&\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C_{N}(m)\right\|\\\
\leq&\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}c_{0}(1)\left\|\frac{J_{{\Lambda}}}{\sqrt{N}}\right\|+\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C^{\circ}_{N}(m)\right\|+3\sqrt{c_{0}(1)c_{0}(\theta_{\star})}\left\|\frac{J_{N}}{\sqrt{N}}\right\|.\end{split}$
(5.43)

Proposition 5.2 then follows directly from the next three propositions, which
give tail probability bounds for each operator norm in (5.43). For $0\leq
x\leq 1$, define the function

${\mathcal{J}}(x)=-\left\\{x\log x+(1-x)\log(1-x)\right\\}$ (5.44)

and set

$\textstyle\bar{L}=\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}|{\Lambda}(m,\theta)|.$
(5.45)

Note that if $\bar{L}=0$ then the first term in the right-hand side of (5.43)
drops out.

######  Proposition 5.5.

Set $x=\bar{L}/{N}$ if $1\leq\bar{L}\leq N/2$ and $x=1/2$ if $N/2<\bar{L}\leq
N$. Then, for all $N$ and all ${\lambda}>0$

${\mathbb{P}}\left(\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|\frac{J_{{\Lambda}}}{\sqrt{N}}\right\|\geq
2\sqrt{x}+2\sqrt{{\mathcal{J}}\left(x\right)+{\lambda}}\right)\leq
2e^{-N{\lambda}}.$ (5.46)

######  Proposition 5.6.

For all $N$ and all ${\lambda}>0$

${\mathbb{P}}\left(\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|\frac{J_{N}-J_{{\Lambda}}}{\sqrt{N}}\right\|\geq
4+2\sqrt{\log 2}+{\lambda}\right)\leq 4e^{-N{\lambda}^{2}/4}.$ (5.47)

Recall the notation (5.22) and for the sake of brevity set

$\varrho^{\pm}_{{\epsilon},\tilde{\varepsilon}}=\varrho\pm[\varrho(1-\varrho){\epsilon}+\varrho\tilde{\varepsilon}].$
(5.48)

######  Proposition 5.7.

For all $0<\tilde{\varepsilon}\leq 1$, ${\epsilon}\geq 0$,
$0<\theta\leq\theta_{\star}\leq 1$, ${\beta},h>0$ and all $N>80$

${\mathbb{P}}\left(\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C^{\circ}_{N}(m)\right\|\geq
c_{0}(1)r(\varrho,{\epsilon},\tilde{\varepsilon},\theta,\theta_{\star},{\beta})\right)\\\
\leq 2e^{-\sqrt{N}/4}$ (5.49)

where

$\begin{split}r(\varrho,{\epsilon},\tilde{\varepsilon},\theta,\theta_{\star},{\beta})&\equiv
2\sqrt{c_{0}(1-\varrho^{-}_{{\epsilon},\tilde{\varepsilon}})+c_{0}(\theta_{\star})}+\sqrt{2c_{0}(\theta)\log\left(2\pi
e\frac{\varrho^{+}_{{\epsilon},2\tilde{\varepsilon}}}{\varrho\tilde{\varepsilon}}\right)}\\\
&+12\left(\frac{c_{0}(\theta_{\star})}{\theta_{\star}}\right)^{3/2}\sqrt{\varrho\tilde{\varepsilon}\frac{1-\theta_{\star}}{\theta_{\star}}}+15\sqrt{\frac{\log
N}{c_{0}(1)\sqrt{N}}}.\end{split}$ (5.50)

In complement to Theorem 5.3 we state below a classical tail probability bound
on the operator norm of $\|J_{N}/\sqrt{N}\|$.

######  Proposition 5.8.

For all $t\geq 0$, ${\mathbb{P}}\bigl{(}\|J_{N}/\sqrt{N}\|\geq 2+t\bigr{)}\leq
2e^{-Nt^{2}/4}.$

###### Proof.

This follows from the one-sided concentration bound for
${\lambda}_{max}(J_{N}/\sqrt{N})$ stated below (3.5) in [38] and the fact that
by symmetry of the distribution of the spectrum of $J_{N}/\sqrt{N}$, the same
bound holds for $-{\lambda}_{min}(J_{N}/\sqrt{N})$. ∎

###  5.3. Proof of Proposition 5.5 and Proposition 5.6

###### Proof of Proposition 5.5.

Using (5.45), we break $\SS_{N,{\epsilon}}(\varrho)$ into
$\SS_{N,{\epsilon}}(\varrho)=\cup_{\underline{L}\leq\ell\leq\bar{L}}{\mathcal{E}}_{N,\ell,{\epsilon}}(\varrho)$,

${\mathcal{E}}_{N,\ell,{\epsilon}}(\varrho)=\left\\{m\in[-1,1]^{N}:|q_{\text{EA}}(m)-\varrho|\leq\varrho(1-\varrho){\epsilon}\,\,\,\text{and}\,\,\,|{\Lambda}(m,\theta)|=\ell\right\\}.$

It is worth making the construction of these sets explicit. Given
$m\in\SS_{N,{\epsilon}}(\varrho)$, we use $\theta$ to construct the set
${\Lambda}(m,\theta)$ defined in (5.26). To each $m$ corresponds a unique
${\Lambda}(m,\theta)$. We then define
${\mathcal{E}}_{N,\ell,{\epsilon}}(\varrho)$ as the set of all
$m\in\SS_{N,{\epsilon}}(\varrho)$ such that ${\Lambda}(m,\theta)$ has given
cardinality, $|{\Lambda}(m,\theta)|=\ell$, $\underline{L}\leq\ell\leq\bar{L}$.
Clearly, the sets ${\mathcal{E}}_{N,\ell,{\epsilon}}(\varrho)$ form a disjoint
covering of $\SS_{N,{\epsilon}}(\varrho)$, and so,

$\begin{split}&{\mathbb{P}}\left(\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|\frac{J_{{\Lambda}(m,\theta)}}{\sqrt{N}}\right\|\geq\sqrt{\frac{\bar{L}}{N}}(2+t)\right)\\\
\leq&\sum_{\underline{L}\leq\ell\leq\bar{L}}{\mathbb{P}}\left(\sup_{m\in{\mathcal{E}}_{N,\ell,{\epsilon}}(\varrho)}\left\|\frac{J_{{\Lambda}(m,\theta)}}{\sqrt{N}}\right\|\geq\sqrt{\frac{\bar{L}}{N}}(2+t)\right).\end{split}$
(5.51)

Since $\left\|J_{{\Lambda}(m,\theta)}\right\|$ only depends on $m$ through the
set ${\Lambda}(m,\theta)$,

$\textstyle\sup_{m\in{\mathcal{E}}_{N,\ell,{\epsilon}}(\varrho)}\left\|J_{{\Lambda}(m,\theta)}\right\|\leq\sup_{{\Lambda}\in\\{1,\dots,N\\}:|{\Lambda}|=\ell}\left\|J_{{\Lambda}}\right\|$
(5.52)

where the last $\sup$ is over non ordered sets. Thus, (5.51) is bounded above
by

$\displaystyle\sum_{\underline{L}\leq\ell\leq\bar{L}}\binom{N}{\ell}{\mathbb{P}}\left(\sqrt{\frac{\ell}{N}}\left\|\frac{J_{\ell}}{\sqrt{\ell}}\right\|\geq\sqrt{\frac{\bar{L}}{N}}(2+t)\right)\leq\sum_{\underline{L}\leq\ell\leq\bar{L}}\binom{N}{\ell}2e^{-\frac{1}{4}\bar{L}t^{2}}$
(5.53)

where we used Proposition 5.8 in the last line. We now assume that
$\underline{L}\geq 0$ is arbitrary. In that case we extend the summation range
in (5.53) to $0\leq\ell\leq\bar{L}$. Because of the symmetry of the binomial
coefficient with respect to $\ell$ and $N-\ell$, and the fact that it is
strictly increasing for $\ell\leq N/2$, we handle the resulting sum
differently if $\bar{L}\leq N/2$ or $\bar{L}>N/2$. In the first case, we use
the well known bound $\sum_{0\leq\ell\leq\bar{L}}\binom{N}{\ell}\leq
e^{N{\mathcal{J}}(\bar{L}/N)}$, valid for all $0\leq\ell\leq\bar{L}$ with
$\bar{L}/N\leq 1/2$. If on the contrary $\bar{L}>N/2$, we simply write
$\sum_{0\leq\ell\leq\bar{L}}\binom{N}{\ell}\leq
2^{N}=e^{N{\mathcal{J}}(1/2)}$. Inserting these bounds in (5.53), (5.46) is
obtained by choosing $t$ in Proposition 5.8 such that
$\frac{1}{4}({\bar{L}}/{N})t^{2}={\mathcal{J}}(x)+{\lambda}$, where
$x=\bar{L}/N$ if $1\leq\bar{L}\leq N/2$ and $x=1/2$ else. ∎

###### Proof of Proposition 5.6.

The proposition follows from the bound
$\|J_{N}-J_{{\Lambda}}\|/\sqrt{N}\leq(\|J_{N}\|+\|J_{{\Lambda}}\|)/\sqrt{N}$,
using Proposition 5.8 to bound $\|J_{N}\|/\sqrt{N}$ and proceeding as in the
proof of Proposition 5.5 to bound $\|J_{{\Lambda}}\|/\sqrt{N}$. ∎

###  5.4. Proof of Proposition 5.7

The first step is to replace the supremum over $\SS_{N,{\epsilon}}(\varrho)$
by the supremum over a discrete set,
${\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$, defined as
follows. Given $0<\tilde{\varepsilon}\leq 1$, let

${\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)=\left\\{m\in\left(\sqrt{\varrho\tilde{\varepsilon}}\,{\mathbb{Z}}\cap[-1,1]\right)^{N}:|q_{\text{EA}}(m)-\varrho|\leq\varrho(1-\varrho){\epsilon}+\varrho\tilde{\varepsilon}\right\\}.$
(5.54)

For every $m$ in $\SS_{N,{\epsilon}}(\varrho)$ there exists $m_{0}$ in
${\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$ such that
$|m_{i}-m_{0,i}|\leq\sqrt{\varrho\tilde{\varepsilon}}$ for all $1\leq i\leq N$
(this means that ${\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$
is a $\varrho\tilde{\varepsilon}$-net of $\SS_{N,{\epsilon}}(\varrho)$ for the
supremum norm).

The next lemma provides a bound on the size of
${\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$.

######  Lemma 5.9.

For large enough $N$

$\left|{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)\right|\leq\left(2\pi
e\right)^{N/2}\left(\frac{1+(1-\varrho){\epsilon}+2\tilde{\varepsilon}}{\tilde{\varepsilon}}\right)^{N/2}.$
(5.55)

###### Proof.

Denote by ${\mathcal{W}}_{N}$ the lattice of side length
$\sqrt{\varrho\tilde{\varepsilon}}$ and by
${\mathcal{B}}_{r}=\\{\|m\|^{2}_{2}\leq r\\}$ the ball of radius $\sqrt{r}$
centered at zero. Then
$\left|{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)\right|$ is
bounded above by the number of points of the lattice ${\mathcal{W}}_{N}$ that
lie in $[-1,1]^{N}\cap{\mathcal{B}}_{\varrho
N(1+(1-\varrho){\epsilon}+\tilde{\varepsilon})}$. Let us surround each point
of the lattice ${\mathcal{W}}_{N}$ by a cube of side length
$\sqrt{\varrho\tilde{\varepsilon}}$. Note that the diagonal of this cube has
length $qN\tilde{\varepsilon}$. Clearly,
$\left|{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)\right|$ is
smaller than the number of cubes which have non empty intersection with
$[-1,1]^{N}\cap{\mathcal{B}}_{\varrho
N(1+(1-\varrho){\epsilon}+\tilde{\varepsilon})}$. Thus, if ${\mathcal{V}}_{N}$
is the volume of
$[-(1+\sqrt{\varrho\tilde{\varepsilon}}),1+\sqrt{\varrho\tilde{\varepsilon}}]^{N}\cap{\mathcal{B}}_{\varrho
N(1+(1-\varrho){\epsilon}+2\tilde{\varepsilon})}$,

$\left|{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)\right|\leq{\mathcal{V}}_{N}\left(\sqrt{\varrho\tilde{\varepsilon}}\right)^{-N}.$
(5.56)

It remains to estimate ${\mathcal{V}}_{N}$. Recalling (5.48), we have

$\displaystyle{\mathcal{V}}_{N}$ $\displaystyle=$
$\displaystyle\int_{-(1+\sqrt{\varrho\tilde{\varepsilon}})}^{1+\sqrt{\varrho\tilde{\varepsilon}}}dm_{1}\dots\int_{-(1+\sqrt{\varrho\tilde{\varepsilon}})}^{1+\sqrt{\varrho\tilde{\varepsilon}}}dm_{N}\mathbbm{1}_{\left\\{\|m\|^{2}_{2}\leq\varrho^{+}_{{\epsilon},2\tilde{\varepsilon}}N\right\\}}$
(5.57) $\displaystyle\leq$ $\displaystyle
e^{\frac{N}{2}}\prod_{i=1}^{N}\left(\int_{-(1+\sqrt{\varrho\tilde{\varepsilon}})}^{1+\sqrt{\varrho\tilde{\varepsilon}}}dm_{i}e^{-m_{i}^{2}/\left(2\varrho^{+}_{{\epsilon},2\tilde{\varepsilon}}\right)}\right)\leq\left({2\pi
e}\varrho^{+}_{{\epsilon},2\tilde{\varepsilon}}\right)^{N/2}.$ (5.58)

(This bound is rough but it is hard to substantially improve it.) Inserting
(5.58) in (5.56) proves (5.55). ∎

The next lemma will enable us to replace the supremum of the operator norm
over $\SS_{N,{\epsilon}}(\varrho)$ by its supremum over
${\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$. Set

$\chi({\beta},\theta_{\star})\equiv\sqrt{\left(c_{0}(\theta_{\star})/\theta_{\star}\right)^{3}c_{0}(1)}\sqrt{\frac{1-\theta_{\star}}{\theta_{\star}}}.$
(5.59)

######  Lemma 5.10.

$\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C^{\circ}_{N}(m)\right\|\leq\sup_{m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)}\left\|C^{\circ}_{N}(m_{0})\right\|+2\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|\frac{J_{N}-J_{{\Lambda}}}{\sqrt{N}}\right\|.$
(5.60)

###### Proof of Lemma 5.10.

For simplicity of notation we write
$D_{N,{\Lambda}}\equiv(J_{N}-J_{{\Lambda}})/\sqrt{N}$ throughout the proof.
Recall that $C^{\circ}_{N}(m)$ defined in (5.32) is an $N\times N$ matrix. By
(5.5)

$\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C^{\circ}_{N}(m)\right\|=\sup_{x:\|x\|_{2}=1}\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left|\left(x,C^{\circ}_{N}(m)x\right)\right|.$
(5.61)

Given a point $x$ on the sphere $\|x\|_{2}=1$ in ${\mathbb{R}}^{N}$, let
$m\in\SS_{N,{\epsilon}}(\varrho)$ be such that

$|(x,C^{\circ}_{N}(m)x)|=\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}|(x,C^{\circ}_{N}(m)x)|$
(5.62)

and pick a point
$m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$ such that
$\sup_{1\leq i\leq N}|m_{i}-m_{0,i}|\leq\sqrt{\varrho\tilde{\varepsilon}}$.
For $1\leq 1\leq N$, set

$u_{i}(m)\equiv x_{i}\sqrt{{\tilde{a}}_{i}(m)}$ (5.63)

and denote by $u(m)$ the vector $u(m)=(u_{1}(m),\dots,u_{N}(m))$. By (5.29),
(5.32) and (5.35)

$\displaystyle(x,C^{\circ}_{N}(m)x)$ $\displaystyle=$
$\displaystyle\left(u(m),D_{N,{\Lambda}}u(m)\right)$ (5.64) $\displaystyle=$
$\displaystyle\left(u(m_{0}),D_{N,{\Lambda}}u(m_{0})\right)+Q_{1}(m,m_{0})+Q_{2}(m,m_{0})\quad$
(5.65) $\displaystyle=$
$\displaystyle(x,C^{\circ}_{N}(m_{0})x)+Q_{1}(m,m_{0})+Q_{2}(m,m_{0})$ (5.66)

where

$\begin{split}Q_{1}(m,m_{0})&=\left(u(m),D_{N,{\Lambda}}(u(m)-u(m_{0}))\right),\\\
Q_{2}(m,m_{0})&=\left((u(m)-u(m_{0})),D_{N,{\Lambda}}u(m_{0})\right).\end{split}$
(5.67)

We begin by bounding $Q_{2}(m,m_{0})$. By Cauchy-Schwarz inequality

$Q_{2}(m,m_{0})\leq\|u(m)-u(m_{0})\|_{2}\sqrt{\left(u(m_{0})D_{N,{\Lambda}}^{2}u(m_{0})\right)}.$
(5.68)

Consider the first factor in (5.68). Using that $\|x\|_{2}=1$, we have

$\displaystyle\|u(m)-u(m_{0})\|_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}x_{i}^{2}\left(\sqrt{{\tilde{a}}_{i}(m)}-\sqrt{{\tilde{a}}_{i}(m_{0})}\right)^{2}$
(5.69) $\displaystyle\leq$ $\displaystyle\sup_{1\leq i\leq
N}\left(\sqrt{{\tilde{a}}_{i}(m)}-\sqrt{{\tilde{a}}_{i}(m_{0})}\right)^{2}.$
(5.70)

The reason for the definition (5.28) of ${\tilde{a}}_{i}(m)$ now becomes
clear. Setting $g(m_{i})=\sqrt{{\tilde{a}}_{i}(m)}$, $g(m_{i})-g(m_{0,i})=0$
for all
$i\in{\Lambda}^{c}_{\star}(m,\theta_{\star})\cap{\Lambda}^{c}_{\star}(m_{0},\theta_{\star})$.
In all other cases, $g(m_{i})$ has bounded derivative on $[-1,1]$ and it
follows from the mean value theorem that

$g(m_{i})-g(m_{0,i})\leq\sup_{\hat{m}_{i}\in[0,1-\theta_{\star}]}g^{\prime}(\hat{m}_{i})|m_{i}-m_{0,i}|\leq\sqrt{\varrho\tilde{\varepsilon}/c_{0}(1)}\chi({\beta},\theta_{\star})$
(5.71)

for $\chi({\beta},\theta_{\star})$ as in (5.59). Combined with (5.70), this
yields

$\|u(m)-u(m_{0})\|_{2}\leq\sqrt{\varrho\tilde{\varepsilon}/c_{0}(1)}\chi({\beta},\theta_{\star}).$
(5.72)

It remains to bound the last factor in (5.68). Introducing the Rayleigh
quotient $Q(v)$,

$Q(v)=(v,v)^{-1}\left(vD_{N,{\Lambda}}^{2}v\right),$ (5.73)

we have

$\left(u(m_{0})D_{N,{\Lambda}}^{2}u(m_{0})\right)=\|u(m_{0})\|_{2}^{2}Q(u(m_{0})).$
(5.74)

Then, by (5.5)

$Q(u(m_{0}))\leq\sup_{v:\|v\|_{2}=1}\left(vD_{N,{\Lambda}}^{2}v\right)=r\left(D_{N,{\Lambda}}^{2}\right)=\left\|D_{N,{\Lambda}}\right\|^{2}.$
(5.75)

Proceeding as in (5.69)-(5.70) and using the rough bound
${\tilde{a}}_{i}(m_{0})\leq c_{0}(1)$ we have

$\|u(m_{0})\|_{2}^{2}\leq\max_{1\leq i\leq N}{\tilde{a}}_{i}(m_{0})\leq
c_{0}(1),$ (5.76)

and so, plugging (5.75) and (5.76) in (5.74),

$\left(u(m_{0})D_{N,{\Lambda}}^{2}u(m_{0})\right)\leq
c_{0}(1)\left\|D_{N,{\Lambda}}\right\|^{2}.$ (5.77)

Finally, inserting (5.72) and (5.77) in (5.68), we obtain

$Q_{2}(m,m_{0})\leq\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})\left\|D_{N,{\Lambda}}\right\|\leq\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|D_{N,{\Lambda}}\right\|.$
(5.78)

Bounding the term $Q_{1}(m,m_{0})$ in (5.67) in the same way, it follows from
(5.66) that

$\left|(x,C^{\circ}_{N}(m)x)\right|\leq\left|(x,C^{\circ}_{N}(m_{0})x)\right|+2\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|D_{N,{\Lambda}}\right\|.$
(5.79)

From this and our choices of $m$ and $m_{0}$ (see the paragraph above (5.63)),
we get

$\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left|(x,C^{\circ}_{N}(m)x)\right|\leq\sup_{m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)}\left|(x,C^{\circ}_{N}(m_{0})x)\right|+2\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|D_{N,{\Lambda}}\right\|.$

Since this bound holds for any given point $x$ on the sphere $\|x\|_{2}=1$,
taking the supremum over $x$ on both sides and recalling the identity (5.61),
we arrive at

$\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C^{\circ}_{N}(m)\right\|\leq\sup_{m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)}\left\|C^{\circ}_{N}(m_{0})\right\|+2\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|D_{N,{\Lambda}}\right\|.$
(5.80)

The proof of Lemma 5.10 is done. ∎

By Lemma 5.10 and Proposition 5.6 with ${\lambda}=N^{-1/4}$, we have for all
$t^{\prime}>0$ and $N>80$

$\begin{split}&{\mathbb{P}}\left(\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C^{\circ}_{N}(m)\right\|\geq
t^{\prime}\right)\\\
\leq&\sum_{m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)}{\mathbb{P}}\left(\left\|C^{\circ}_{N}(m_{0})\right\|+12\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})\geq
t^{\prime}\right)+e^{-\sqrt{N}/4}.\end{split}$ (5.81)

We are thus left with proving an upper bound on the tail probability of
$\left\|C^{\circ}_{N}(m_{0})\right\|$. Set

${\tilde{\sigma}}(m)=\sqrt{\frac{c_{0}(1)}{N}\sum_{1\leq j\leq
N}{\tilde{a}}_{j}(m)},\quad{\tilde{\sigma}_{\star}}=\sqrt{\frac{c_{0}(1)c_{0}(\theta)}{N}},\quad{\tilde{\sigma}_{0}}=\sup_{m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)}{\tilde{\sigma}}(m_{0}).$
(5.82)

######  Lemma 5.11.

For all $m\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$, all
$N$ and all $t>0$

${\mathbb{P}}\left(\left\|C^{\circ}_{N}(m)\right\|\geq
2{\tilde{\sigma}_{0}}+\sqrt{N}{\tilde{\sigma}_{\star}}t+14\sqrt{N^{-1/2}{\log
N}}\right)\leq e^{-Nt^{2}/4}.$ (5.83)

###### Proof.

Pick any $m\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$.
Setting

$\tilde{v}_{ij}(m)\equiv\sqrt{\frac{{\tilde{a}}_{i}(m){\tilde{a}}_{j}(m)}{N}},$
(5.84)

the lemma follows from an application of Theorem 5.3 to the matrix
$C^{\circ}_{N}(m)$ of entries

$C^{\circ}_{ij}(m)=\begin{cases}\tilde{v}_{ij}(m)J_{ij}&\text{if}\,\,\,(i,j)\in(\\{1,\dots,N\\}\times{\Lambda}^{c})\cup({\Lambda}^{c}\times\\{1,\dots,N\\}).\\\
0&\text{if}\,\,\,(i,j)\in{\Lambda}\times{\Lambda},\end{cases}$ (5.85)

(i.e., we replace (5.17) with (5.84)-(5.85)). To bound the quantities
${\sigma}(m)$ and ${\sigma_{\star}}(m)$ defined in (5.18), recall the bound
(5.76) on $\max_{1\leq i\leq N}{\tilde{a}}_{i}(m)$ and observe that on
${\Lambda}^{c}$

${\tilde{a}}_{j}(m)\leq\begin{cases}c_{0}(\theta)&\text{if}\,\,\,j\in{\Lambda}^{c}\cap{\Lambda}_{\star},\\\
c_{0}(\theta_{\star})&\text{if}\,\,\,j\in{\Lambda}^{c}\cap{\Lambda}^{c}_{\star},\end{cases}$
(5.86)

where $\theta_{\star}<\theta$ by assumption. Then

$\displaystyle{\sigma}^{2}(m)\leq\max\left\\{\frac{c_{0}(\theta)}{N}\sum_{1\leq
j\leq
N}{\tilde{a}}_{j}(m),\frac{c_{0}(1)}{N}\sum_{j\in{\Lambda}^{c}}{\tilde{a}}_{j}(m)\right\\}\leq{\tilde{\sigma}}^{2}(m),$
(5.87)

and

${\sigma_{\star}}^{2}(m)=\frac{1}{N}\max_{1\leq i\leq
N}{\tilde{a}}_{i}(m)\max_{j\in{\Lambda}^{c}}{\tilde{a}}_{j}(m)\leq{\tilde{\sigma}^{2}_{\star}}.$
(5.88)

Hence, by Theorem 5.3 with $\varepsilon=1/\sqrt{N}$, we have that for all
$t>0$

${\mathbb{P}}\left(\left\|C^{\circ}_{N}(m)\right\|\geq
2{\tilde{\sigma}}(m)+\sqrt{N}{\tilde{\sigma}_{\star}}t+14\sqrt{{\textstyle{\log
N\over\sqrt{N}}}}\right)\leq e^{-Nt^{2}/4}.$ (5.89)

Given the definition of ${\tilde{\sigma}_{0}}$ in (5.82), this implies the
lemma. ∎

Combining (5.81) and (5.83), and using Lemma 5.9 to bound the sum over
${\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)$ we obtain,
choosing $t^{2}=2\log\left(2\pi
e{\varrho^{+}_{{\epsilon},2\tilde{\varepsilon}}}/{(\varrho\tilde{\varepsilon})}\right)+\frac{1}{4\sqrt{N}},$

$\begin{split}{\mathbb{P}}\Biggl{(}\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}&\left\|C^{\circ}_{N}(m)\right\|\geq
2{\tilde{\sigma}_{0}}+\sqrt{N}{\tilde{\sigma}_{\star}}\sqrt{2\log\left(2\pi
e{\varrho^{+}_{{\epsilon},2\tilde{\varepsilon}}}/{(\varrho\tilde{\varepsilon})}\right)}\\\
&\quad\quad\quad+12\sqrt{\varrho\tilde{\varepsilon}}\chi({\beta},\theta_{\star})+15\sqrt{{\textstyle{\log
N\over\sqrt{N}}}}\Biggr{)}\leq\bigl{(}1+{\mathcal{O}}\bigl{(}{\textstyle{1\over\sqrt{N}}}\bigr{)}\bigr{)}e^{-\sqrt{N}/4}.\end{split}$
(5.90)

All that remains is to bound ${\tilde{\sigma}_{0}}$. Recalling the notation
(5.48), we have:

######  Lemma 5.12.

${\tilde{\sigma}_{0}}\leq\sqrt{c_{0}(1)}\sqrt{c_{0}(1-\varrho^{-}_{{\epsilon},\tilde{\varepsilon}})+c_{0}(\theta_{\star})}.$

We prove successively Lemma 5.4 and Lemma 5.12.

###### Proof of Lemma 5.4.

Note that the function $f(m)=\frac{1}{N}\sum_{j}a_{j}(m)$ is strictly concave
on $[-1,1]^{N}$. Writing

$\textstyle\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}f(m)=\sup_{\rho^{\prime}:|\rho^{\prime}-\varrho|\leq\varrho(1-\varrho){\epsilon}}\sup_{m:q_{\text{EA}}(m)=\rho^{\prime}}f(m)$
(5.91)

and using Lagrange multipliers, one readily gets that the last constrained
supremum is attained at points such that $m^{2}_{i}=\rho^{\prime}$, $1\leq
i\leq N$, yielding the upper bound of (5.23). Similarly, one proves that the
constrained infimum is attained at points of the form $m_{i}=1$ for all $i\in
I$ and $m_{i}=0$ else, where $I\subset\\{1,\dots,N\\}$ is any subset of
cardinality $|I|=\rho^{\prime}N$. This yields the lower bound. Since each
$a_{i}(m)$ is maximized at $m_{i}=0$, the upper bound of (5.24) is attained at
any point $m$ that contains at least one zero coordinate. The lower bound
follows from the choice $m^{2}_{i}=\varrho(1+{\epsilon})$, $1\leq i\leq N$. ∎

###### Proof of Lemma 5.12.

By (5.28)

$\sup_{m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)}\frac{1}{N}\sum_{1\leq
j\leq
N}{\tilde{a}}_{j}(m)\leq\sup_{m_{0}\in{\mathcal{N}}_{N,{\epsilon},\tilde{\varepsilon}}(\varrho)}\frac{1}{N}\sum_{1\leq
j\leq N}a_{j}(m)+c_{0}(\theta_{\star}).$ (5.92)

The last sum is bounded above by the upper bound of (5.23) with
$\varrho^{-}_{{\epsilon}}$ replaced by
$\varrho^{-}_{{\epsilon},\tilde{\varepsilon}}$ (see (5.48)). The lemma then
follows from the definition (5.82) of ${\tilde{\sigma}_{0}}$. ∎

Proposition 5.7 now follows from (5.90), Lemma 5.12, the definitions (5.82)
and (5.59) of ${\tilde{\sigma}_{0}}$, ${\sigma_{\star}}$ and
$\chi({\beta},\theta_{\star})$, and the bound $c_{0}(y)\leq y$.

###  5.5. Conclusion of the proof of Proposition 5.2 and proof of Theorem 5.1

###### Proof of Proposition 5.2.

We prove the two items of the proposition separately.

#### Proof of item (i).

Since ${\lambda}_{max}(C_{N}(m))\leq\left\|C_{N}(m)\right\|$, it suffices to
prove (5.14) with $\left\|C_{N}(m)\right\|$ substituted for
${\lambda}_{max}(C_{N}(m))$.

First we have to specify the parameters $\theta$, $\theta_{\star}$ and
$\tilde{\varepsilon}$ (see (5.26), (5.27) and (5.54)). A natural idea is to
choose $\theta$ and $\theta_{\star}$ such that on the sets
${\Lambda}(m,\theta)$ and ${\Lambda}^{c}_{\star}(m,\theta_{\star})$, the
coefficients $a_{i}(m)$ are respectively larger and smaller than the average
$\frac{1}{N}\sum_{j}a_{j}(m)$. In view of (5.23), this prompts us to choose

$\theta=(1-\varrho^{-}_{{\epsilon}})^{\alpha},\quad\theta_{\star}=(1-\varrho^{-}_{{\epsilon}})^{\kappa},$
(5.93)

where $0<\alpha<1$ and $\kappa\geq 1$ are constants to be chosen. Eq. (5.50)
then leads us to take

$\tilde{\varepsilon}=(1-\varrho^{-}_{{\epsilon}})^{\tilde{\kappa}}$ (5.94)

for some $\tilde{\kappa}>\kappa$. Equipped with these choices, we now use
Propositions 5.5, 5.7 and 5.8 to bound each of the three terms appearing on
the right-hand side of (5.43). The first of these terms is treated using
Proposition 5.5. By our choice of $\theta$, $\bar{L}$ in (5.45) is bounded by

$\bar{L}\leq\frac{1-\varrho^{-}_{{\epsilon}}}{\theta}N=(1-\varrho^{-}_{{\epsilon}})^{1-\alpha}N.$
(5.95)

We want to guarantee that $\bar{L}/N\leq 1/2$. For this it suffices to assume
that

$\varrho^{-}_{{\epsilon}}\geq 1-\left({\textstyle{1\over
2}}\right)^{\frac{1}{1-{\alpha}}}.$ (5.96)

It then follows from (5.46) with ${\lambda}=N^{-1/4}$ and the classical bound
${\mathcal{J}}(x)\leq 2\ln 2\sqrt{x(1-x)}$, $0\leq x\leq 1/2$, that

${\mathbb{P}}\left(\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|\frac{J_{{\Lambda}}}{\sqrt{N}}\right\|\geq
2\sqrt{(1-\varrho^{-}_{{\epsilon}})^{1-\alpha}\left(1+2\ln
2\right)}+2N^{-1/4}\right)\leq 2e^{-\sqrt{N}}.$ (5.97)

The second term on the right-hand side of (5.43) is treated using Proposition
5.7. It follows from (5.93) that the function (5.50) is bounded above by

$\begin{split}&r(\varrho,{\epsilon},\tilde{\varepsilon},\theta,\theta_{\star},{\beta})\\\
&\leq
2\sqrt{(1-\varrho^{-}_{{\epsilon}})\left[1+q(1-\varrho^{-}_{{\epsilon}})^{\tilde{\kappa}-1}+(1-\varrho^{-}_{{\epsilon}})^{\kappa-1}\right]}\\\
&+\sqrt{2(1-\varrho^{-}_{{\epsilon}})^{\alpha}\left\\{{\tilde{\kappa}}\left|\ln(1-\varrho^{-}_{{\epsilon}})\right|+\log\left(2\pi
e(1+(1-\varrho){\epsilon}+2\tilde{\varepsilon})\right)\right\\}}\\\
&+12\sqrt{\varrho(1-\varrho^{-}_{{\epsilon}})^{\tilde{\kappa}-\kappa}}+15\sqrt{{\textstyle{\log
N\over\sqrt{N}}}}.\end{split}$ (5.98)

Finally, to deal with the third and last term we use that, by Proposition 5.8
with $t=N^{-1/4}$,

${\mathbb{P}}\left(3\sqrt{\theta_{\star}}\left\|\frac{J_{N}}{\sqrt{N}}\right\|\geq
3\sqrt{(1-\varrho^{-}_{{\epsilon}})^{\kappa}}(2+N^{-1/4})\right)\leq
2e^{-\sqrt{N}}.$ (5.99)

Collecting these results yields a bound on the tail probability of
$\sup_{m\in\SS_{N,{\epsilon}}(\varrho)}\left\|C_{N}(m)\right\|$ that still
depends on ${\alpha}$, $\kappa$ and $\tilde{\kappa}$. It is clear that to
minimise the contribution of terms containing ${\alpha}$, one should choose
$\alpha=1/2$. How to optimise the choice of $\kappa$ and $\tilde{\kappa}$ is
less obvious. We take $\kappa=2$ and $\tilde{\kappa}=4$.

It remains to deal with the supremum over ${\epsilon}$ in (5.14). For this we
note that $\SS_{N,{\epsilon}}(\varrho)\subseteq\SS_{N,1}(\varrho)$ for all
${\epsilon}\in[0,1]$ and use that
$1-\varrho^{-}_{{\epsilon}}=(1-\varrho)(1+\varrho{\epsilon})\leq
1-\varrho^{2}\leq 2(1-\varrho)$ to make our bounds uniform in ${\epsilon}$.
The last inequality implies in particular that if $\varrho\geq\sqrt{3/4}$ then
(5.96) is verified for all ${\epsilon}\leq 1$ and ${\alpha}=1/2$. Item (i) of
Proposition 5.2 now readily follows.

#### Proof of item (ii).

Returning to the Hessian (5.6)-(5.7) (and remembering the matrix notation from
the paragraph above (5.6)), it follows from the Courant-Fisher minimax
principle that the largest eigenvalue ${\lambda}_{max}({\mathcal{H}}(m))$ of
${\mathcal{H}}(m)$ satisfies

${\lambda}_{max}({\mathcal{H}}_{N}(m))\leq{\beta}{\lambda}_{max}\left(\frac{J_{N}}{\sqrt{N}}\right)-{\lambda}_{min}(B_{N}(m)).$
(5.100)

On the one hand, for all $m\in[-1,1]^{N}$, $B_{N}(m)$ is strictly positive
definite and obeys

${\lambda}_{min}(B_{N}(m))\geq{\beta}^{2}(1-q)+1.$ (5.101)

On the other hand, by Proposition 5.8,
${\mathbb{P}}\left({\lambda}_{max}\bigl{(}\frac{J_{N}}{\sqrt{N}}\bigr{)}\geq
2+\frac{1}{N^{1/4}}\right)\leq 2e^{-\sqrt{N}/4}$. Combining (5.100) and
(5.101) proves (5.15).

The proof of Proposition 5.2 is now complete. ∎

###### Proof of Theorem 5.1.

#### Proof of item (i).

Since the set ${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ in (5.1) is
increasing with ${\epsilon}$, we may assume that ${\epsilon}>0$. The strategy
of the proof is to cover ${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ with a
collection of spherical shells and proceed as in the proof of item (i) of
Proposition 5.2 to deal with each of them. Set
$K=\frac{1-\varrho^{-}_{{\epsilon}}}{2\varrho(1-\varrho){\epsilon}}$,
$\rho_{k}=\varrho^{-}_{{\epsilon}}+(2k+1)\varrho(1-\varrho){\epsilon}$ and for
$0\leq k\leq K-1$

$\SS_{N,k,{\epsilon}}=\left\\{m\in[-1,1]^{N}:|q_{\text{EA}}(m)-\rho_{k}|\leq\varrho(1-\varrho){\epsilon}\right\\}.$
(5.102)

Then

${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)=\bigcup_{k=0}^{K-1}\SS_{N,k,{\epsilon}}.$
(5.103)

We now claim that for each shell $\SS_{N,k,{\epsilon}}$, $0\leq k\leq K-1$,
under the assumptions and with the notation of item (i) of Proposition 5.2,
for all $0<{\epsilon}\leq 1$ and all $N$ large enough

${\mathbb{P}}\left(\sup_{m\in\SS_{N,k,{\epsilon}}}{\lambda}_{max}(C_{N}(m))\geq
f_{1}(\varrho)+16\sqrt{{\textstyle{\log N\over\sqrt{N}}}}\right)\leq
6e^{-\sqrt{N}}.$ (5.104)

Note that for $k=0$, $\SS_{N,0,{\epsilon}}=\SS_{N,{\epsilon}}(\varrho)$ so
that (5.104) follows from (5.14). For $k>1$ the proof of (5.104) is a simple
rerun of the proof of the case $k=0$, replacing $\varrho$,
$\varrho^{\pm}_{{\epsilon}}$ and
$\varrho^{\pm}_{{\epsilon},\tilde{\varepsilon}}$ (see (5.21) and (5.48)) where
needed with $\rho_{k}$,
$\rho^{\pm}_{k,{\epsilon}}\equiv\rho_{k}\pm\varrho(1-\varrho){\epsilon}$ and
$\rho^{\pm}_{k,{\epsilon},\tilde{\varepsilon}}\equiv\rho_{k}\pm[\varrho(1-\varrho){\epsilon}+\rho_{k}\tilde{\varepsilon}]$.
In particular, Proposition 5.7 is modified as follows: replacing
$\SS_{N,{\epsilon}}(\varrho)$ with $\SS_{N,k,{\epsilon}}$ in (5.49), the
quantity
$r(\varrho,{\epsilon},\tilde{\varepsilon},\theta,\theta_{\star},{\beta})$ must
be replaced with

$\begin{split}r_{k}(\rho_{k},{\epsilon},\tilde{\varepsilon},\theta,\theta_{\star},{\beta})&\equiv
2\sqrt{1-\rho^{-}_{k,{\epsilon},\tilde{\varepsilon}}+\theta_{\star}}+\sqrt{2\theta\log\left(2\pi
e\frac{1+(1-\rho_{k}){\epsilon}+2\tilde{\varepsilon}}{\tilde{\varepsilon}}\right)}\\\
&+12\sqrt{\rho_{k}\tilde{\varepsilon}}\sqrt{\frac{1-\theta_{\star}}{\theta_{\star}}}+15\sqrt{{\textstyle{\log
N\over\sqrt{N}}}}.\end{split}$ (5.105)

We then proceeds as in the proof of item (i) of Proposition 5.2, replacing
$\varrho^{-}_{{\epsilon}}$ with $\rho^{-}_{k,{\epsilon}}$ in (5.93)-(5.94),
$r(\varrho,{\epsilon},\tilde{\varepsilon},\theta,\theta_{\star},{\beta})$ with
$r_{k}(\rho_{k},{\epsilon},\tilde{\varepsilon},\theta,\theta_{\star},{\beta})$
in (5.98), and bounding quantities of the form $\rho_{k}\tilde{\varepsilon}$
by $\tilde{\varepsilon}$. Doing this, we obtain (5.104) with $f_{1}(\varrho)$
replaced by $f_{1}(\rho_{k})$. The proof of (5.104) is now completed using the
following two facts: (1) the central radius $\rho_{k}$ of the spherical shell
$\SS_{N,k,{\epsilon}}$ increases from $\varrho$ to
$1-\varrho(1-\varrho){\epsilon}$ as $k$ increases from $0$ to $K-1$, and (2)
$f_{1}(\rho)$ is a decreasing function of $\rho$ on $[0,1]$.

By (5.103) and (5.104), we get that under the assumptions and with the
notation of item (i) of Proposition 5.2, for all $0<{\epsilon}\leq 1$ and all
$N$ large enough

${\mathbb{P}}\left(\sup_{m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)}{\lambda}_{max}(C_{N}(m))\geq
f_{1}(\varrho)+16\sqrt{{\textstyle{\log N\over\sqrt{N}}}}\right)\leq
6Ke^{-\sqrt{N}}.$ (5.106)

Thus, for all $\varrho\geq\sqrt{3/4}$ and $({\beta},h)$, $h>0$, such that
${\beta}f_{1}(\varrho)<1$, it follows from (5.106) Borel-Cantelli lemma that

${\mathbb{P}}\left(\bigcup_{N_{0}}\bigcap_{N\geq
N_{0}}\left\\{\sup_{{\epsilon}\in[0,1]}\sup_{m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)}{\beta}{\lambda}_{max}(C_{N}(m))<1\right\\}\right)=1.$
(5.107)

Now, the condition ${\beta}f_{1}(\varrho)<1$ is nothing but (1.30), and so, by
(5.10), (5.107) proves item (i) of Theorem 5.1.

#### Proof of item (ii).

If $({\beta},h)$, $h>0$, are such that (1.28) is satisfied, then the function
$f_{2}({\beta},q)$ of (5.13) obeys $f_{2}({\beta},q)<0$. Item (ii) of Theorem
5.1 in this case follows from (5.15) of Proposition 5.2 and Borel-Cantelli
lemma.

The proof of Theorem 5.1 is complete. ∎

###  5.6. Proof of Theorem 1.6

Recall from (2.5) that $F_{N,{\beta},h}^{HT}(m)$ can be written as

$F_{N,{\beta},h}^{HT}(m)=\frac{1}{N}\left\\{\Psi_{N,{\beta},h{\bf{1}}}(x)+\frac{{\beta}^{2}N}{4}\left(1-q^{2}\right)\right\\}.$
(5.108)

We first prove Theorem 1.6 for $({\beta},h)$ in the intersection of
${\mathcal{D}}^{(2)}_{\varrho}$ and the AT-region. Let
$\sqrt{3/4}\leq\varrho\leq q\leq 1$ be given. Under the assumptions and with
the notation of Theorem 5.1, (i), there exists a subset
${\Omega}_{1}({\beta},h)\subset{\Omega}$ of full measure such that on
${\Omega}_{1}({\beta},h)$, for all ${\epsilon}\in[0,1]$ and all but a finite
number of indices $N$, the Hessian of $F_{N,{\beta},h}^{HT}$ at $m$ is
strictly negative definite for all
$m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$. We claim that this implies
the following lemma.

######  Lemma 5.13.

On ${\Omega}_{1}({\beta},h)$, for all large enough $N$, $F_{N,{\beta},h}^{HT}$
has at most one critical point in ${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$,
which must be a maximum.

###### Proof.

To prove this, we first establish that given $0<{\epsilon}\leq 1$ and
$0<\varrho\leq 1$, for all sufficiently large $N$,
${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ is a closed, bounded and path-
connected subset of ${\mathbb{R}}^{N}$. Obviously, as the intersection of two
closed and bounded sets, ${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ is closed
and bounded. This leaves us to prove that it is path-connected, namely, that
given any two points
$m,m^{\prime}\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$, there exists a
continuous function ${\gamma}_{mm^{\prime}}$ from $[0,1]$ into
${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ with endpoints
${\gamma}_{mm^{\prime}}(0)=m$ and ${\gamma}_{mm^{\prime}}(1)=m^{\prime}$. We
do this in three steps.

_Step 1:_ Denote by $V_{N}=\\{-1,1\\}^{N}\ni v=(v_{1},\dots,v_{N})$ the set of
vertices of the hypercube $[-1,1]^{N}$. Under the above assumptions on
${\epsilon}$ and $\varrho$, $\varrho^{-}_{{\epsilon}}<1$ (see (5.21)), and so,
$V_{N}\subset{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$. An edge of
$[-1,1]^{N}$ is a path ${\gamma}_{vv^{\prime}}$ connecting two vertices
$v,v^{\prime}\in V_{N}$ that differ in exactly one coordinate, say the
$i{\text{th}}$ coordinate, described by the function
${\gamma}_{vv^{\prime}}:[0,1]\rightarrow[-1,1]^{N}$,
$s\mapsto{\gamma}_{vv^{\prime}}(s)=(v_{1},\dots,v_{i-1},2s-1,v_{i+1}\dots
v_{N})$. That is, all coordinates are kept fixed except the $i{\text{th}}$,
which varies linearly from $-1$ to $+1$. Along this edge,

$\textstyle
q_{\text{EA}}({\gamma}_{vv^{\prime}}(s))=\big{(}(2s-1)^{2}+N-1\bigr{)}N^{-1}\geq
1-N^{-1}.$ (5.109)

Thus ${\gamma}_{vv^{\prime}}\subset{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$
for all $N$ such that $\varrho^{-}_{{\epsilon}}\leq 1-N^{-1}$. Let an _edge
path_ ${\gamma}_{vv^{\prime}}$ be a path connecting two given vertices
$v,v^{\prime}\in V_{N}$ through a sequence of adjacent edges (i.e., any two
consecutive edges of the path share a common vertex). Since for all
sufficiently large $N$ every edge of the path maps $[0,1]$ into
${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$, so does ${\gamma}_{vv^{\prime}}$
itself.

_Step 2:_ Given any $m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$, let $v\in
V_{N}$ be the vertex of coordinates $v_{i}=1$ if $m_{i}>0$, $v_{i}=-1$ if
$m_{i}<0$ and $v_{i}=1$ otherwise, $1\leq i\leq N$. Note that $v$ minimises
the Euclidean distance from $m$ to $V_{N}$, Without loss of generality we can
assume that $m_{i}\geq 0$, so that $v_{i}=1$ for all $1\leq i\leq N$. Set
${\mathcal{C}}_{N}(m)=\times_{i=1}^{N}[m_{i},1]$ and let
${\gamma}_{mv}:[0,1]\rightarrow{\mathcal{C}}_{N}(m)$ be any path confined to
${\mathcal{C}}_{N}(m)$ that connects $m$ and $v$. Clearly,
${\mathcal{C}}_{N}(m)\subset{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ since
for each $m^{\prime}\in{\mathcal{C}}_{N}(m)$

$\textstyle
q_{\text{EA}}(m^{\prime})=N^{-1}\sum_{i=1}^{N}(m^{\prime}_{i})^{2}\geq
N^{-1}\sum_{i=1}^{N}(m_{i})^{2}\geq\varrho^{-}_{{\epsilon}}.$ (5.110)

_Step 3:_ Now consider any two points
$m,m^{\prime}\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$. Let $v$ and
$v^{\prime}$ be any vertices of $V_{N}$ that minimise the Euclidean distance
of $m$ and $m^{\prime}$ to $V_{N}$, respectively. Consider the path
${\gamma}_{m,m^{\prime}}={\gamma}_{m,v}\cup{\gamma}_{v,v^{\prime}}\cup{\gamma}_{v^{\prime},m^{\prime}}$
where ${\gamma}_{v,v^{\prime}}$ is an edge path, and
${\gamma}_{mv}:[0,1]\rightarrow{\mathcal{C}}_{N}(m)$ and
${\gamma}_{v^{\prime},m^{\prime}}:[0,1]\rightarrow{\mathcal{C}}_{N}(m^{\prime})$
are arbitrary paths confined to ${\mathcal{C}}_{N}(m)$ and
${\mathcal{C}}_{N}(m^{\prime})$, respectively. By steps 1 and 2 above,
${\gamma}_{m,m^{\prime}}\subset{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ for
all large enough $N$. This proves our claim that
${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ is path-connected for all
sufficiently large $N$.

Now let us assume that $N$ is large enough for
${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ to be path-connected. This implies
that on the set ${\Omega}_{1}({\beta},h)$ (see the paragraph below (5.108)),
$F_{N,{\beta},h}^{HT}$ has at most one maximum in
${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$. Indeed, if there are two distinct
local maxima, then along any path in
${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ connecting these two points there
must exist a point $m^{\prime\prime}$ and a vector $v$ such that the second
order directional derivative at $m^{\prime\prime}$ along $v$,
$(v,{\mathcal{H}}_{N}(m^{\prime\prime})v)$, is greater than or equal to zero,
which is a contradiction on ${\Omega}_{1}({\beta},h)$. ∎

Recall at this point that, by assumption, $({\beta},h)$ lies in the AT-region.
We know from Section 3 that in the AT-region the solution $m^{(k)}$ of
Bolthausen’s iterative scheme (1.22)-(1.23) provides an approximate solution
to the critical point equation for $F_{N,{\beta},h}^{HT}$. To use this result
we proceed as in Section 2 and compare the function $F_{N,{\beta},h}^{HT}$ to
the modified function $F_{N,{\beta},\bf{\bar{h}}}^{HT}$ whose magnetic field,
$\bf{\bar{h}}$, is chosen as in (2.9) with $\bar{x}=m^{(k)}$. This choice of
${\bf{\bar{h}}}$ ensures that $F_{N,{\beta},\bf{\bar{h}}}^{HT}$ has a critical
point at $m^{(k)}$, i.e., $\nabla
F_{N,{\beta},\bf{\bar{h}}}^{HT}\bigl{(}m^{(k)}\bigr{)}=0$. Since the modified
and original functions differ only by a linear term, they have the same
Hessian. This critical point is therefore unique and a maximum on
${\Omega}_{1}({\beta},h)$ for all $N$ large enough.

We also know from Section 3 that in the AT-region, if $0<{\epsilon}\leq 1$ and
$\varrho\leq q$, then

$m^{(k)}\in\SS_{N,{\epsilon}}(q)\subset{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$
(5.111)

for all $N$ large enough, where $\SS_{N,{\epsilon}}(q)$ is the spherical shell
(5.11). More precisely, we saw in the proof of Theorem 3.6 (see (3.38)) that
there exists a subset ${\Omega}^{\prime}({\beta},h)\subset{\Omega}$ with
${\mathbb{P}}\left({\Omega}^{\prime}({\beta},h)\right)=1$ such that on
${\Omega}^{\prime}({\beta},h)$, for all $k\geq 1$,
$\lim_{N\rightarrow\infty}\bigl{\|}m^{(k)}\bigr{\|}^{2}_{2,N}=q.$ This implies
that on ${\Omega}^{\prime}({\beta},h)$, for all $\varrho\leq q$ and all $k\geq
1$, $|q_{\text{EA}}(m^{(k)})-q|\leq q(1-q){\epsilon}_{N}$ for some
${\epsilon}_{N}$ (possibly depending on $k,{\beta},h$) with the property that
${\epsilon}_{N}\downarrow 0$ as $N\uparrow\infty$. Without loss of generality,
we can assume that $N$ is large enough so that ${\epsilon}_{N}<{\epsilon}$.

Next, reasoning as in (2.13), we have that for all $m\in[-1,1]^{N}$

$\displaystyle\left|F_{N,{\beta},h}^{HT}(m)-F_{N,{\beta},\bf{\bar{h}}}^{HT}(m)\right|\leq$
$\displaystyle\textstyle\sqrt{\left\|m\right\|_{2,N}^{2}}\sqrt{\left\|\nabla\Psi_{N,{\beta},h{\bf{1}}}\left(m^{(k)}\right)\right\|_{2,N}^{2}}.$
(5.112)

It then follows from (4.5) and the bound $\left\|m\right\|_{2,N}\leq 1$ that

$\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}\sup_{m\in[-1,1]^{N}}\left|F_{N,{\beta},h}^{HT}(m)-F_{N,{\beta},\bf{\bar{h}}}^{HT}(m)\right|=0\quad{\mathbb{P}}\textstyle{-a.s.},$
(5.113)

that is, $F_{N,{\beta},h}^{HT}$ is uniformly well approximated by
$F_{N,{\beta},\bf{\bar{h}}}^{HT}$ asymptotically, ${\mathbb{P}}$-a.s.. Thus,

$\lim_{N\rightarrow\infty}\sup_{m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)}F_{N,{\beta},h}^{HT}(m)=\lim_{k\rightarrow\infty}\lim_{N\rightarrow\infty}F_{N,{\beta},h}^{HT}\left(m^{(k)}\right)\quad{\mathbb{P}}\textstyle{-a.s.}.$
(5.114)

By (1.24) of Theorem 1.3, (5.114) implies

$\lim_{N\rightarrow\infty}\sup_{m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)}F_{N,{\beta},h}^{HT}(m)=SK({\beta},h)\quad{\mathbb{P}}\textstyle{-a.s.}.$
(5.115)

By (5.111), ${\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)$ can be replaced by
$\SS_{N,{\epsilon}}(q)$ in the above. So far, $0<{\epsilon}\leq 1$ is
arbitrary. Passing to the limit ${\epsilon}\rightarrow 0$ in (5.115), we get

$\lim_{{\epsilon}\rightarrow
0}\lim_{N\rightarrow\infty}\sup_{m\in\sup_{m\in{\mathcal{B}}^{c}_{N,{\epsilon}}(\varrho)}}F_{N,{\beta},h}^{HT}\left(m\right)=SK({\beta},h)\quad{\mathbb{P}}\textstyle{-a.s.}$
(5.116)

This concludes the proof of Theorem 1.6, (ii).

The case where $({\beta},h)$ is in ${\mathcal{D}}^{(1)}$ is simpler. Indeed,
under the assumptions and with the notation of Theorem 5.1, (ii), there exists
a subset ${\Omega}_{2}({\beta},h)\subset{\Omega}$ of full measure such that on
${\Omega}_{2}({\beta},h)$, for all but a finite number of indices $N$, the
Hessian of $F_{N,{\beta},h}^{HT}$ at $m$ is strictly negative definite in the
entire hypercube $[-1,1]^{N}$. Thus, on ${\Omega}_{2}({\beta},h)$, for all
sufficiently large $N$, the function $F_{N,{\beta},h}^{HT}$ is strictly
concave on the convex domain $[-1,1]^{N}$. From here on, the proof is a repeat
of the proof of Theorem 1.6, (ii). The proof of Theorem 1.6 is now complete.

##  6\.  Proof of Theorem 1.7

Recall that ${\mathcal{D}}^{(3)}$ is defined in (1.33). Set

$r({\beta},h)\equiv
h^{-1}\left({\beta}^{2}q\left(1-q\right)+E2|{\beta}\sqrt{q}Z+h|e^{-2|{\beta}\sqrt{q}Z+h|}\right)$
(6.1)

and let $\bar{\varrho}({\beta},h)$ be the function defined on
${\mathcal{D}}^{(3)}$ by

$\bar{\varrho}\equiv\bar{\varrho}({\beta},h)=\begin{cases}\left[1-\left(1+{\textstyle{1\over
h-1}}\right)r({\beta},h)\right]^{2}&\text{if
$\left[1-\left(1+{\textstyle{1\over
h-1}}\right)r({\beta},h)\right]^{2}<q$,}\\\
q\left[1-\left(1+{\textstyle{1\over
h-1}}\right)r({\beta},h)\right]^{2}&\text{else}.\end{cases}$ (6.2)

Clearly, $\bar{\varrho}({\beta},h)<q$ for all $({\beta},h)$ in
${\mathcal{D}}^{(3)}$. Given $\varrho>0$ set

${\mathcal{B}}_{N}(\varrho)=\left\\{m\in[-1,1]^{N}:q_{\text{EA}}(m)<\varrho\right\\}.$
(6.3)

Theorem 1.7 is a reformulation of the following result.

######  Theorem 6.1.

For all $({\beta},h)$ in ${\mathcal{D}}^{(3)}$

${\mathbb{P}}\left(\bigcup_{N_{0}}\bigcap_{N\geq
N_{0}}\left\\{\sup_{m\in{\mathcal{B}}_{N}(\bar{\varrho})}F_{N,{\beta},h}^{HT}(m)<SK({\beta},h)\right\\}\right)=1.$
(6.4)

The domain ${\mathcal{D}}^{(3)}$ is not the most general possible, but is
chosen to satisfy two conditions: it allows to easily bound $r({\beta},h)$ and
it contains a large part of ${\mathcal{D}}^{(2)}_{\bar{\varrho}}$, especially
the low temperature part. The following two lemmata, which provide bounds on
$r({\beta},h)$ and $1-q$, and their accompanying remarks, elaborate on these
observations.

######  Lemma 6.2.