Phase transition in the spiked random tensor with Rademacher prior
Wei-Kuo Chen∗

arXiv:1712.01777v2 [math.PR] 11 Dec 2017

December 12, 2017

Abstract
We consider the problem of detecting a deformation from a symmetric Gaussian random ptensor (p ≥ 3) with a rank-one spike sampled from the Rademacher prior. Recently in Lesieur et
al. [30], it was proved that there exists a critical threshold βp so that when the signal-to-noise
ratio exceeds βp , one can distinguish the spiked and unspiked tensors and weakly recover the prior
via the minimal mean-square-error method. On the other side, Perry, Wein, and Bandeira [44]
proved that there exists a βp0 < βp such that any statistical hypothesis test can not distinguish
these two tensors, in the sense that their total variation distance asymptotically vanishes, when
the signa-to-noise ratio is less than βp0 . In this work, we show that βp is indeed the critical
threshold that strictly separates the distinguishability and indistinguishability between the two
tensors under the total variation distance. Our approach is based on a subtle analysis of the high
temperature behavior of the pure p-spin model with Ising spin, arising initially from the field of
spin glasses. In particular, we identify the signal-to-noise criticality βp as the critical temperature,
distinguishing the high and low temperature behavior, of the Ising pure p-spin mean-field spin
glass model.

Contents
1 Introduction

2

2 Main results

4

3 Proof of Theorem 1
3.1 Total variation distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Proof of Theorem 1(i) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Proof of Theorem 1(ii) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7
9
12

4 The
4.1
4.2
4.3

14
14
16
18
19
25
26
27

4.4
4.5

pure p-spin model
High temperature behavior
Proof of Theorem 2 . . . . .
Proof of Theorems 3 and 4
4.3.1 Even p case . . . . .
4.3.2 Odd p case . . . . .
Proof of Proposition 1 . . .
Proof of Proposition 2 . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

Appendix
∗

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

36

School of Mathematics, University of Minnesota. Email: wkchen@umn.edu

1

1

Introduction

The problem of detecting a deformation in a symmetric Gaussian random tensor is concerned about
whether there exists a statistical hypothesis test that can reliably distinguish the deformation from
the noise. In the matrix case, if W is a Gaussian Wigner ensemble and u is a unit vector, the goal
is to distinguish the unspiked matrix W and the spiked matrix W + βuuT for a given signal-tonoise ratio β. It is well-known that in this case the top eigenvalue of the spiked matrix exhibits the
so-called BBP (Baik, Ben Arous, and Péché) transition [5, 15, 17, 43]. Namely, the top eigenvalue
successfully detects the signal if the strength of β exceeds the critical threshold 1, while it fails to
provide indicative information if β < 1. It was further proved in [34, 37, 45] that for any β < 1,
every statistical hypothesis test can not distinguish the spiked and unspiked matrices.
In recent years, the above phenomena were also studied in the spiked symmetric Gaussian random
p-tensor model of the form, W + βu⊗p . Earlier results were obtained by Montanari and Richard [35]
and Montanari, Reichman, and Zeitouni [34] in the setting of spherical prior, where they showed that
there exist βp− and βp+ with βp− < βp+ such that if the signal-to-noise ratio exceeds βp+ , it is possible to
distinguish the spiked and unspiked tensors and weakly recover the signal, but these are impossible
if the signal-to-noise ratio is less than βp− . More recently, Lesieur et al. [30] studied this detection
problem for any prior by means of the minimal mean-square-error (MMSE). They discovered that
there exists a critical threshold βp (depending on the prior) such that when the signal-to-noise ratio
exceeds the critical value βp , one can distinguish the two tensors by the MMSE and weakly recover
the signal by the MMSE estimator. In contrast, when β < βp , MMSE fails to distinguish the two
tensors and weakly recovery of the signal is not possible. On the other side, Perry, Wein, and
Bandeira [44] studied the detection problem with spherical, Rademacher, and sparse Rademacher
priors and they provided an improvement on the bounds in [34, 35]. Moreover, their results showed
that in each of these three cases, there exists a βp0 < βp such that for any β < βp0 , it is impossible
to distinguish the two tensors in the sense that the total variation distance between the spiked and
unspiked tensors asymptotically vanishes. As a consequence, every statistical hypothesis test fails
to distinguish the two tensors. The paper [44] then left with a conjecture that indistinguishability
between the two tensors should be valid up to the critical threshold βp .
The aim of this paper is to study the symmetric Gaussian random p-tensor (p ≥ 3) with
Rademacher prior as in the setting of [44]. We show that the threshold βp , suggested by the MMSE
method in [30], is indeed the critical value that strictly separates the distinguishability and indistinguishability between the spiked and unspiked tensors under the total variation distance. More
precisely, it is established that when the signal-to-noise ratio is less than the critical value βp , the
total variation distance between the spiked and unspiked tensors converges to zero. This establishes
the aforementioned prediction in [44]. In particular, we identify the critical value βp as the critical temperature, distinguishing the high and low temperature behavior, of the Ising pure p-spin
mean-field spin glass model.
Our approach is based on the methodologies originated from the study of mean-field spin glasses,
especially those for the Sherrington-Kirkpatrick model and the mixed p-spin models, see [39, 49, 50].
Roughly speaking, spin glass models are disordered spin systems initially invented by theoretical
physicists in order to explain the strange magnetic behavior of certain alloys, such as CuMn. Mathematically, they are usually formulated as stochastic processes with high complexity and present
several crucial features, e.g., quenched disorder and frustration, that are commonly shared in many
real world problems, involving combinatorial random optimizations. Over the past decades, the
study of spin glasses has received a lot of attention in both physics and mathematics communities,
see [32] for physics overview and [39, 49, 50] for mathematical development.
One way to investigate the detection problem in the symmetric Gaussian random tensor is
through the total variation distance between the spiked and unspiked tensors. While in the detection

2

problem β represents the signal-to-noise ratio, we regard β as a (inverse) temperature parameter in
the pure p-spin model. Notably, under this setting, the ratio of the densities between the two tensors
can be computed as the partition function of the pure p-spin model with temperature β. In [34, 44],
the authors controlled the total variation distance by the second moment of the partition function.
Different than their consideration, we relate this distance to the free energy of the pure p-spin model
with Ising spin, see Lemma 2. This relation allows us to show that the critical threshold βp can be
determined by the critical temperature of the pure p-spin model. In bounding the total variation
distance, the most critical ingredient is played by a sharp upper bound concerning the fluctuation of
the free energy up to the critical temperature for all p ≥ 3. In the case p = 2, the pure p-spin model
is famously known as the Sherrington-Kirkpatrick model and its free energy was shown to possess a
Gaussian central limit theorem in the weak limit up to the critical temperature βp = 1 by Aizenman,
Lebowitz, and Ruelle [1]. As for even p ≥ 4, Bovier, Kurkova, and Löwe [16] showed that the same
result also holds (with different scaling than that in the Sherrington-Kirkpatrick model), but not
up to the critical temperature. Our main contribution is that we obtain a sharp upper bound for
the fluctuation of the free energy, which is comparable to the one in [16] and more importantly it is
valid up to the critical temperature for all p ≥ 3 including odd p. This allows us to extract a sharp
upper bound for the total variation distance and deduce the desired result.
Besides the consideration of the detection problem, we also present some new results and arguments for the pure p-spin models that are of independent interest in spin glasses. First, we show
that if the temperature is below the critical value βp , the model presents the high temperature or
replica symmetric solution in the sense that any two independently sampled spin configurations from
the Gibbs measure are essentially orthogonal to each other by providing exponential tail probability
and moment controls. While these results can also be established at very high temperature by some
well-known techniques in spin glasses, such as the cavity method, the second moment method, and
Latala’s argument (see [49, Chapter 1]), it is relatively a more challenging task to obtain the same
behavior throughout the entire high temperature regime. We show that this is achievable in the pure
p-spin model (see Theorem 3 and 4) and indeed, our method can also be applied to more general
situations, the mixed p-spin models (see Remark 3). Next, in terms of technicality, our argument
for the above result is based on the Guerra-Talagrand replica symmetry breaking bound for the
coupled free energy for two systems. This bound has been playing a critical role in the study of the
mixed even p-spin models, see Talagrand [50]. Its validity for the model involving odd p mixture is
however generally unknown as it is unclear whether the error term along Guerra’s replica symmetry
breaking interpolation possesses a nonnegative sign or not. To tackle this obstacle, we adopt the
synchronization property, introduced by Panchenko [41, 42], that the overlap matrix is asymptotically symmetric and positive semi-definite under the Gibbs average, which was established heavily
relying on the fact that the Ghirlanda-Guerra identities imply ultrametricity of the overlaps [38].
This allows us to show that the error term creates a nonnegative sign and ultimately leads to the
validity of the Guerra-Talagrand bound in the pure odd p-spin model if one restricts the functional
order parameters to be of one-step replica symmetry breaking. Whether this bound is valid for more
general functional order parameters remains open.
For other related works on the detection problem of spiked matrices and tensors, we invite the
readers to check a variety of low rank matrix estimation problems, including explicit characterizations of mutual information in [7, 28, 29, 31, 33] and the performance of the approximate message
passing (AMP) for MMSE method and compressed sensing in [7, 13, 23, 24, 27]. More recently,
the fluctuation of the likelihood ratio in the spiked Wigner model was studied in [25]. In the case
of spiked tensors, phase transitions of the mutual information and the MMSE estimator were recently studied for any p and given prior, see [9, 30] for symmetric case and [11] for non-symmetric
case. The performance of the AMP in the spiked tensor was also investigated in [30]. See also
[6, 8, 10, 21, 22, 36, 46]. For the study of Gaussian random p-tensor in terms of complexity, see [14].
3

This paper is organized as follows. In Section 2, we state our main results on the detection
problem. In Section 3, their proofs are presented and are essentially self-contained for those who
wish to learn only the roles of spin glass results in the detection problem. The high temperature
results on the pure p-spin model are gathered and established in Section 4 with great details.

2

Main results

We begin by setting some standard notation. Let p ∈ N. For any N ≥ 1, denote by ΩN := ⊗pj=1 RN
the space of all real-valued tensors Y = (yi1 ,...,ip )1≤i1 ,...,ip ≤N . For any two tensors Y and Y 0 , their
outer product and inner product are defined respectively by
(Y ⊗ Y 0 )i1 ,...,ip ,i01 ,...,i0p = yi1 ,...,ip yi01 ,...,i0p
and

N
X

Y, Y 0 :=

yi1 ,...,ip yi01 ,...,ip .

i1 ,...,ip =1

For τ ∈ RN , we define τ ⊗p = τ ⊗ · · · ⊗ τ ∈ ΩN as the p-th order power of τ. For any permutation
π ∈ Sp and any tensor Y , Y π ∈ ΩN is defined as yiπ1 ,...,ip = yiπ(1) ,...,iπ(p) . We say that a tensor Y is
symmetric if Y = Y π for all π ∈ Sp . Let ΩsN be the collection of all symmetric tensors. For any
measurable A ⊆ Rk for some k ≥ 1, we use B(A) to stand for the Borel σ-field on A.
The symmetric Gaussian random tensor is defined as follows. Denote by Y ∈ ΩN a random
tensor with i.i.d. entries yi1 ,...,ip ∼ N (0, 2/N ). Define a symmetric random tensor W by
W =

1 X π
Y .
p!
π∈Sp

For example, if p = 2, W is the Gaussian orthogonal ensemble, i.e., wij = wji are√independent of
each other with wij ∼ N (0, 1/N ) for i < j and wii ∼ N (0, 2/N ). Let SN := {±1/ N }N . Assume
that u is sampled uniformly at random from SN and is independent of W. Set the spiked random
tensor as
T = W + βu⊗p
for β ≥ 0. Let
dT V (W, T ) :=

sup
A∈B(ΩsN )

|P(W ∈ A) − P(T ∈ A)|

be the total variation distance between W and T . We now make the distinguishability and indistinguishability between W and T precise.
Definition 1. We say that
(i) W and T are indistinguishable if limN →∞ dT V (W, T ) = 0.
(ii) W and T are distinguishable if limN →∞ dT V (W, T ) = 1.
Let u be a realization of the prior. For a given tensor X ∈ ΩsN , consider the detection problem
that under the null hypothesis, X = W and under the alternative hypothesis, X = T. Item (i)
essentially says that any statistical test can not reliably distinguish these two hypotheses. Item (ii)
means there exists a sequences of events that distinguishes these two tensors. Next we define the
notion of weak recovery for u.

4

Definition 2. For β > 0, we say that weak recovery of u is possible if there exists a sequence of
random probability measures µN on ΩsN × B(SN ) and a constant c > 0 such that
Z

lim P
|hu, τ i|µN (T, dτ ) ≥ c = 1
(1)
N →∞

SN

and that weak recovery of u is not possible if for any random probability measure µN on ΩsN × B(SN )
and constant c > 0,
Z

lim P
|hu, τ i|µN (T, dτ ) ≥ c = 0.
(2)
N →∞

SN

Here µN is a random probability measure on ΩsN × B(SN ) means that µN is a mapping from ΩsN ×
B(SN ) to [0, 1] such that µN (·, A) is B(ΩsN )-measurable for each A ∈ B(SN ) and µN (w, ·) is a
probability measure on (SN , B(SN )) for each w ∈ ΩsN .
A few comments are in position. Consider a given realization of signal u and tensor T . Equation
(1) ensures that there exists some τ produced though the measure µN (T, dτ ) such that u and τ
have a nontrivial overlap. To understand (2), let φ : ΩsN → SN be any measurable function. If we
consider the random probability measure µN (w, τ ) defined by

1, if τ = φ(w),
µN (w, τ ) =
0, if τ 6= φ(w),
then from (2), for any c > 0,

lim P |hu, φ(T )i| ≥ c = 0.

N →∞

In other words, any vector generated by T is uncorrelated with the signal u and thus, it does not
provide indicative information about u. We emphasize that Definitions 1 and 2 are not directly
related to each other. Nevertheless, we will show that both of them hold up to a critical threshold
in our main result below.
Now we introduce the pure p-spin model. For each N ≥ 1, set ΣN := {±1}N . The Hamiltonian
of the pure p-spin model is defined by
HN (σ) =

1
N (p−1)/2

X

gi1 ,...,ip σi1 · · · σip

1≤i1 ,...,ip ≤N

for σ ∈ ΣN . Its covariance can be computed as
EHN (σ 1 )HN (σ 2 ) = N (R1,2 )p ,
where R1,2 is the overlap between σ 1 , σ 2 ∈ ΣN ,
R1,2 :=

N
1 X 1 2
σi σi .
N

(3)

i=1

In the terminology of detection problem, β is understood as the signal-to-noise ratio. In the pure
p-spin model, we regard β as a (inverse) temperature parameter. For a given temperature β ≥ 0,
define the free energy by
FN (β) =

X 1
1
β
log
exp √ HN (σ).
N
N
2
2
σ∈ΣN

5

(4)

If p = 2, this model is known as the Sherrington-Kirkpatrick model and it has been intensively
studied over the past decades. The readers are referred to check the books [39, 49, 50] for recent
mathematical advances for the SK model as well as more general models involving a mixture of pure
p-spin interactions. In particular, it is already known that the thermodynamic limit of FN (N → ∞)
converges to a nonrandom quantity that can be expressed as the famous Parisi formula, see, e.g.,
[40, 48]. Denote this limit by F . A direct application of Jensen’s inequality to (4) implies that for
all β ≥ 0,
F (β) ≤

β2
.
4

Define the high temperature regime for the pure p-spin model as
n
β2 o
R = β > 0 : F (β) =
.
4
Set the critical temperature by
βp := max R.
Our main result shows that βp is the critical threshold in the detection problem.
Theorem 1. Let p ≥ 3. The following statements hold:
(i) If 0 < β < βp , then W and T are indistinguishable and weak recovery of u is impossible.
(ii) If β > βp , then W and T are distinguishable and weak recovery of u is possible.
Our main contribution in Theorem 1 is the part on the indistinguishability of W and T in the
statement (i). Previous results along this line were established in [44], where the authors showed
that there exists some βp0 < βp so that W and T are indistinguishable for any β < βp0 . Theorem 1(i)
here proves that this behavior is indeed valid up to the critical value βp . As one will see from
Theorem 2 below, we give a characterization of the high temperature regime R and provide one way
to simulate βp in terms of an auxiliary function deduced from the optimality of the Parisi formula
for the free energy at high temperature. Numerically, it is obtained that
p
3
4
5
6

βp
1.535
1.621
1.647
1.657

This agrees with the prediction in [44, Figure 1]. We comments that for Theorem 1(i), a polynomial
rate of convergence for the total variation distance can also be obtained, see Remark 2 below. In
comparison, we add that Theorem 1 is quite different from the BBP transition for p = 2, see
[5, 34, 37, 45]. In this case, β2 = 1 and it is known that for β > β2 , one can distinguish W and T in
the sense of Definition 1 by using the top eigenvalue. For 0 < β < β2 , it presents a weaker sense of
distinguishability, limN →∞ dT V (W, T ) ∈ (0, 1), see Remark 1.
As mentioned before, the work [30] investigated the present detection problem for any given
prior. Their results state that one can distinguish W and T by the MMSE method and weakly
recover the signal through the MMSE estimator when β > βp ; if β < βp , they concluded that weak
recovery of the signal is not possible. In other words, their results imply the weak recovery part of
item (i) as well as the statement of item (ii). Nevertheless, we emphasize that their approach and
6

the way how the critical value βp was discovered are fundamentally different from the argument we
present here. As one will see, while Theorem 1(ii) follows directly from a relation (see Lemma 2)
between the total variation distance and the free energies, the delicate part is Theorem 1(i), which
is the major component of this paper.
Acknowledgements. The author thanks G. Ben Arous for introducing this project to him and A.
Auffinger and A. Jagannath for some fruitful discussions. He is indebted to D. Panchenko for asking
good questions that lead to a major improvement on the result of weak recovery of u and several
suggestions regarding the presentation of the paper. He also thanks J. Barbier, A. Montanari, and
L. Zdeborová for suggesting several references and valuable comments. Research partly supported
by NSF DMS-1642207 and Hong Kong Research Grants Council GRF-14302515.

3
3.1

Proof of Theorem 1
Total variation distance

In this subsection, we prepare some lemmas for Theorem 1. Recall that Y is a random tensor with
i.i.d. yi1 ,...,ip ∼ N (0, 2/N ) and W is the symmetric random tensor generated by Y. Throughout
the remainder of the paper, we use I(S) to standard for an indicator function on a set S. We first
establish an elementary expression of the total variation distance.
Lemma 1. Let U, V be two n-dimensional random vectors with densities fU and fV satisfying
fU (r) 6= 0 and fV (r) 6= 0 a.e. on Rn . Then
1

Z
dT V (U, V ) =
0

Z 1 
 f (V )

fU (U )
1
U
P
< x dx =
P
>
dx.
fV (V )
fV (U )
x
0

Proof. Note that
1
dT V (U, V ) =
2

Z

Z
|fV (r) − fU (r)|dr =

Rn


fV (r) − fU (r) dr.

fU (r)≤fV (r)

Using Fubini’s theorem and this equation, the first equality follows by
Z 1 
Z 1Z

 f (r)

fU (V )
U
P
< x dx =
I
< x fV (r)drdx
fV (V )
fV (r)
0
0
Rn
Z Z 1 

fU (r)
=
I
< x dxfV (r)dr
fV (r)
n 0
ZR 

fU (r)
fU (r) 
=
I
≤1 1−
fV (r)dr
fV (r)
fV (r)
n
ZR

=
fV (r) − fU (r) dr.
fU (r)≤fV (r)

To obtain the second equality, one simply exchanges the roles of U, V .
Recall the free energy FN (β) and the Rademacher prior u from Section 2. Define an auxiliary
free energy of the pure p-spin model with a Curie-Weiss type interaction as
N
 β
p 
X 1
1
β2  1 X
√
AFN (β) =
log
exp
H
(σ)
+
N
h
σ
,
i
i
N
N
2N
2
N
2
i=1

σ∈ΣN

7

(5)

√
where hi := N ui . In Appendix, it will be established that the limit of AFN converges a.s. to a
nonrandom quantity for any β ≥ 0. Denote this limit by AF (β). The following lemma relates the
total variation distance between W and T to the free energy FN and the auxiliary free energy AFN .
Lemma 2. For any β ≥ 0, we have that
Z 1 
β 2 log x 
(6)
dT V (W, T ) =
P FN (β) <
+
dx
4
N
0
Z 1 
β 2 log x 
(7)
P AFN (β) >
=
−
dx.
4
N
0

Proof. Note that W has density fW (w) = exp −N hw, wi/4 /C on ΩsN for some normalizing constant
C > 0. For any A ∈ B(ΩsN ), a change of variables gives



P T ∈ A = Eu PW W ∈ A − βu⊗p
Z


= Eu
fW (w)dw
A−βu⊗p
Z
Z


fW (w − βu⊗p )dw =
Eu fW (w − βu⊗p )dw,
= Eu
A

A

where Eu is the expectation with respect to u only and dw is the Lebesgue on ΩsN . This implies that
the density of T = W + βu⊗p is given by fT (w) := Eu fW (w − βu⊗p ). Now since
−N
1
Eu exp
w − βu⊗p , w − βu⊗p
C
4

N
= fW (w)Eu exp
2β w, u⊗p − β 2 u⊗p , u⊗p ,
4

fT (w) =

we obtain

fT (w)
N
= Eu exp
2β w, u⊗p − β 2 u⊗p , u⊗p .
fW (w)
4

(8)

Here, since W, τ ⊗p = Y, τ ⊗p for any τ ∈ RN and u⊗p , u⊗p = 1, we see that
log

 d β2N
fT (W )
N
= log Eu exp
2β Y, u⊗p − β 2 = −
+ N FN (β)
fW (W )
4
4

and
log

 d β2N
N
fT (T )
⊗p
= log Eu0 exp
2β Y + βu⊗p , u0
+ N AFN (β),
− β2 = −
fW (T )
4
4

where Eu0 is the expectation of u0 , an independent copy of u and independent of W , and the second
p
√
d
equality of both displays used the assumption that yi1 ,...,ip = gi1 ,...,ip 2/N and N SN = ΣN . Our
proof is then completed by applying Lemma 1.
Remark 1. Aizenman, Lebowitz, and Ruelle [1] showed that N (FN (β) − β 2 /4) converges to a
Gaussian central limit theorem. From (6), one immediately sees that limN →∞ dT V (W, T ) ∈ (0, 1).

8

3.2

Proof of Theorem 1(i)

The central ingredient throughout our proof is played by the high temperature behavior of the pure
p-spin model stated in Section 4 below, namely, a tight upper bound for the fluctuation of the free
energy in Proposition 1 and a good moment control for the concentration of the overlap R1,2 around
zero under the Gibbs measure in Theorem 4. The former will be directly used to show that the total
variation distance dT V (W, T ) vanishes via the exact expression (6), while the latter is vital in order
to establish the impossibility of weak recovery of u.
Proof of Theorem 1(i): Indistinguishability. Let p ≥ 3. Assume that 0 < β < βp . For any
R 1 R 1−ε R 1
0 < ε < 1, writing 0 = 0 + 1−ε in (6) gives
1−ε


β 2 log x 
P FN (β) <
+
dx
4
N
0

β 2 log(1 − ε)−1 
−
≤ ε + P FN (β) <
4
N

β2
log(1 − ε)−1 
≤ ε + P FN (β) −
≥
.
4
N
Z

dT V (W, T ) ≤ ε +

To complete the proof, we use a key property about the fluctuation of the free energy stated in
Proposition 1 below, which says that there exists a constant K such that

β2
log(1 − ε)−1 
K
P FN (β) −
≥
≤
2 p
4
N
log(1 − ε)−1 N 2 −1
for all N ≥ 1. From this,
K

dT V (W, T ) ≤ ε +

2 p .
log(1 − ε)−1 N 2 −1

(9)

Since p ≥ 3, sending N → ∞ and then ε ↓ 0 implies that W and T are indistinguishable.
Remark 2. Take ε = N −δ for δ = (p/2 − 1)/3 and use log(1 − ε)−1 ≥ ε in (9). We obtain the rate
of convergence,
dT V (W, T ) ≤ ε +

K
ε2 N

p
−1
2

=

1
1+K
K
+ p −1−2δ = 1 p  .
δ
N
N2
N 3 2 −1

Next we continue to show that weak recovery of u is impossible. For β > 0, define a random
probability measure on ΩsN × B(SN ) by


0 ⊗p i; A
Eu0 exp βN
2 hw, u
νN,β (w, A) =
(10)


0 ⊗p i
Eu0 exp βN
hw,
u
2
for any w ∈ ΩsN and A ∈ B(SN ), where Eu0 is the expectation with respect to u0 , an independent
copy of u. The following lemma relates the expectation of (u, T ) to W by a change of measure in
terms of EνN,β .
Lemma 3. Let ζN be a measurable function from SN ×ΩsN to [0, 1]. If W and T are indistinguishable,
then
Z
lim EζN (u, T ) − E
ζN (τ, W )νN,β (W, dτ ) = 0.
N →∞

SN

9

Proof. Recall the densities fW and fT of W and T from Lemma 2. Let fu (τ ) be the probability
mass function for u. Since u is independent of W , the joint density of (u, T ) is given by
fu (τ )fW (w − βτ ⊗p ).
This implies that E[ζN (u, T )|T ] = ζN (T ), where
P
⊗p )
τ ∈SN ζN (τ, w)fu (τ )fW (w − βτ
ζN (w) :=
.
fT (w)
Note that 0 ≤ ζN (w) ≤ 1 since 0 ≤ ζN (τ, w) ≤ 1. For any k ≥ 1, define
 i
k , if s ∈ Ak,i for some 1 ≤ i ≤ k − 1,
φk (s) =
1, if s ∈ Ak,k ,
where Ak,i := [(i−1)/k, i/k) for 1 ≤ i ≤ k−1 and Ak,k := [(k−1)/k, 1]. Observe that |φk (s)−s| ≤ 1/k
for s ∈ [0, 1]. From this and the triangle inequality,
|EζN (T ) − EζN (W )|
≤ |EζN (T ) − Eφk (ζN (T ))| + |Eφk (ζN (T )) − Eφk (ζN (W ))| + |EζN (W ) − Eφk (ζN (W ))|
k

≤



2 Xi
+
P ζN (T ) ∈ Ak,i − P ζN (W ) ∈ Ak,i .
k
k
i=1

Since dT V (W, T ) converges to zero, each term in the above sum must vanish in the limit and thus,
letting N → ∞ and then k → ∞ yields
lim |EζN (T ) − EζN (W )| = 0.

(11)

N →∞

Now, write
Z
EζN (W ) =

X

ΩsN τ ∈S
N

ζN (τ, w)

fu (τ )fW (w − βτ ⊗p )fW (w)
dw.
fT (w)


Note that fW (w) = exp −N hw, wi/4 /C for some normalizing constant.
hτ ⊗p , τ ⊗p i = hu0 ⊗p , u0 ⊗ i = 1,

Since from (8) and


exp N4 −hw, wi + 2βhw, τ ⊗p i − β 2 hτ ⊗p , τ ⊗p i
fu (τ )fW (w − βτ ⊗p )fW (w)


=
fT (w)
C2N Eu0 exp N4 2βhw, u0 ⊗p i − β 2 hu0 ⊗p , u0 ⊗p i
= fW (w)νN,β (w, τ ),
it follows that
Z
EζN (W ) = E

ζN (τ, W )νN,β (W, dτ ).
SN

From this and (11), the announced result follows.
Proof of Theorem 1(i): Impossibility of weak recovery. Let p ≥ 3 and 0 < β < βp . Let µN
be a random probability measure on ΩsN × B(SN ) (see Definition 2) and c > 0. Our goal is to show
that
Z

lim P
|hu, τ i|µN (T, dτ ) ≥ c = 0.
(12)
N →∞

SN

10

Set
Z

hτ, τ 0 i2 µN (w, dτ 0 )

ζN (τ, w) =
SN

for (τ, w) ∈ SN × ΩsN . Note that ζN ∈ [0, 1] and ζN is measurable. From Lemma 3,
Z
Z
0 2
0
lim E
hu, τ i µN (T, dτ ) − E
hτ, τ 0 i2 µN (W, dτ 0 )νN,β (W, dτ ) = 0.
N →∞

(13)

SN ×SN

SN

We claim that the second expectation converges to zero. For notation convenience, we simply denote
µN (dτ 0 ) = µN (W, dτ 0 ) and νN (dτ ) = νN,β (W, dτ ). Note that
N
X

0 2

hτ, τ i =

τi1 τi2 τi01 τi02 .

i1 ,i2 =1

The second term in the above equation can be controlled by
Z
hτ, τ 0 i2 µN (dτ 0 )νN (dτ )
E
SN ×SN
N
X

Z

=E

i1 ,i2 =1 SN ×SN
N
X

=

Z

Z
τi1 τi2 νN (dτ ) ·

E

i1 ,i2 =1

SN

SN

N  Z
X
E

≤

τi1 τi2 τi01 τi02 µN (dτ 0 )νN (dτ )
τi01 τi02 µN (dτ 0 )

2 1/2  Z
τi1 τi2 νN (dτ )
· E

SN

i1 ,i2 =1

SN

τi01 τi02 µN (dτ 0 )

2 1/2

,

where the last inequality used the Cauchy-Schwarz inequality. Using the Cauchy-Schwarz inequality
again, the last inequality is bounded above by
N
 X

SN

i1 ,i2 =1

=

N
 X

·

N
2 1/2  X
Z
τi1 τi2 νN (dτ )
·
E

Z
E

SN

i1 ,i2 =1

Z
τi1 τi2 τ̂i1 τ̂i2 νN (dτ )νN (dτ̂ )

E

i1 ,i2 =1

SN ×SN

N
 X

Z
E

i1 ,i2 =1

 Z
= E

SN ×SN

2 1/2
τi01 τi02 µN (dτ 0 )

1/2

1/2
τi01 τi02 τ̂i01 τ̂i02 µN (dτ 0 )µN (dτ̂ 0 )

1/2  Z
hτ, τ̂ i νN (dτ )νN (dτ̂ )
· E
2

SN ×SN

hτ 0 , τ̂ 0 i2 µN (dτ 0 )µN (dτ̂ 0 )

1/2

.

SN ×SN

Here the second bracket is bounded above by 1. As for the first one, we observe that√νN is in
distribution
GN,β defined in (17) and if we write σ 1 = N τ and
√ 0 equal to the Gibbs measure
2
1
2
σ = N τ , then in distribution, σ , σ are independent samplings from GN,β and hτ, τ̂ i is the
overlap R1,2 between σ 1 and σ 2 . As a result,
Z
2
E
hτ, τ̂ i2 νN (dτ )νN (dτ̂ ) = EhR1,2
iβ ,
SN ×SN

11

where h·iβ is the Gibbs average with respect to the product measure GN,β × GN,β . Now, since
0 < β < βp , we can apply Theorem 4 to control the right-hand side by the bound
2
EhR1,2
iβ ≤

K
N

for some constant K independent of N. Hence, from the above inequalities,
Z
lim E
hτ, τ 0 i2 µN (dτ 0 )νN (dτ ) = 0.
N →∞

SN ×SN

From (13),
Z
lim E

N →∞

hu, τ 0 i2 µN (T, dτ 0 ) = 0,

SN

which gives the desired limit (12) by using Markov’s and Jensen’s inequalities.

3.3

Proof of Theorem 1(ii)

While we have seen that the high temperature behavior of the pure p-spin model has been of great
use in obtaining Theorem 1(i), the proof of Theorem 1(ii) below relies only on the low temperature
behavior of the free energies, that is, F (β) < β 2 /4 and AF (β) > β 2 /4 for β > βp . The proof is
relatively simpler than that for Theorem 1(i).
Proof of Theorem 1(ii): Distinguishability. Let p ≥ 3. Assume that β > βp . Since F (β) <
β 2 /4 and FN (β) − log x/N converges to F (β) a.s.,


β 2 log x 
β2 
lim P FN (β) <
+
= P F (β) ≤
= 1.
N →∞
4
N
4
Thus, from (6) and the dominated convergence theorem, W and T are distinguishable.
Next we show that weak recovery of u is possible. Recall hi from the definition of AFN (β). Let
u0 be an independent copy of u and be independent of Y. For fixed β > 0, define an interpolating
free energy between FN (β) and AFN (β) by
1
βN
⊗p
log Eu0 exp
Y + xu⊗p , u0
N
2
N
 β
p 
X 1
βx  1 X
d 1
√
H
(σ)
+
=
log
exp
h
σ
i
i
N
N
2N
2 N
2

LN (x) =

(14)

i=1

σ∈ΣN

for x > 0, where Eu0 is the expectation with respect to u0 only. Note that in distribution LN (0) =
FN (β) and LN (β) = AFN (β). Similar to AFN (β), it can be shown that LN also converges to a
nonrandom quantity for any x > 0, see Proposition 3 in Appendix. Denote this limit by L. From
now on, we use D+ f and D− f to denote the right and left derivatives of f whenever they exist.
Note that since L is convex, D− L exists everywhere. Recall νN,β from (10).
Lemma 4. Let β > 0. For any ε > 0, we have
Z

lim P
|hu, τ i|p νN,β (T, dτ ) ≥ D− L(β) − ε = 1.
N →∞

SN

12

Proof. Note that u⊗p , u0 ⊗p = hu, u0 ip . For any η > 0,
i
h
1
βN
⊗p
Y + βu⊗p , u0
; hu, u0 ip ≤ D− L(β) − ε
log Eu0 exp
N
2
i
h

βN
1
⊗p
⊗p 
≤
Y, u0
+ (β − η) u⊗p , u0
+ η D− L(β) − ε
log Eu0 exp
N
2

= LN (β − η) + η D− L(β) − ε .
To control the last inequality, write



LN (β) − LN (β − η) 
+ LN (β) − ηε
LN (β − η) + η D− L(β) − ε = η D− L(β) −
η
and pass to limit
lim

N →∞



LN (β − η) + η D− L(β) − ε





L(β) − L(β − η) 
= η D− L(β) −
+ L(β) − ηε .
η

Here, by the left-differentiability of L, the first bracket on the right-hand side converges to zero as
η ↓ 0. Thus, we can choose η small enough such that the right hand side is controlled by L(β) − ηε/2.
Consequently, from the sub-Gaussian concentration inequality for LN (see [18, Proposition 9]), we
see that there exists a positive constant K independent of N such that with probability at least
1 − Ke−N/K ,
i
h
ηε
1
βN
⊗p
; hu, u0 ip ≤ D− L(β) − ε ≤ LN (β) −
log Eu0 exp
T, u0
N
2
4
and this implies that
 

ηεN
νN,β T, τ ∈ SN hu, τ ip ≤ D− L(β) − ε ≤ e− 4 .
As a result, the assertion follows by
Z


ηεN 
ηεN
N
P
hu, τ ip νN,β (T, dτ ) ≥ D− L(β) − ε 1 − e− 4 − e− 4
≥ 1 − Ke− K
SN

and noting that

R

p
SN hu, τ i νN,β (T, dτ )

≤

R
SN

|hu, τ i|p νN,β (T, dτ ).

Proof of Theorem 1(ii): Possibility of weak recovery. Let p ≥ 3. Assume that β > βp . First
we claim that
AF (β) ≥

β2
.
4

(15)

Assume on the contrary that AF (β) < β 2 /4. Since AFN (β) + log x/N converges to AF (β) a.s., we
have


β2 
β 2 log x 
P AFN (β) >
−
→ P AF (β) >
= 0.
4
N
4
This and (7) together leads to a contradiction,
Z 1

β 2 log x 
1 = lim dT V (W, T ) =
lim P AFN (β) >
−
dx = 0.
N →∞
4
N
0 N →∞
13

Thus, (15) must be valid.
To show that weak recovery is possible, observe that since LN (β) = AFN (β) and LN (0) = FN (β)
in distribution, it follows from (15) that
L(β) = AF (β) ≥

β2
> F (β) = L(0).
4

Since L is convex, there exists a point x0 ∈ (0, β) such that D− L(x0 ) > 0. Indeed, if not L will be
a constant function on (0, β), a contradiction. Now using the convexity of L again gives D− L(β) ≥
D− L(x0 ) > 0. This and Lemma R4 together complete our proof
by letting µN (w, τ ) = νN,β (w, τ ) and
R
c = D− L(β)/2 and noting that SN |hu, τ i|p νN,β (T, dτ ) ≤ SN |hu, τ i|νN,β (T, dτ ).

4

The pure p-spin model

Recall the pure p-spin Hamiltonian HN and the high temperature regime R from Section 2. The
aim of this section is to establish a complete description of the high temperature behavior of the
pure p-spin model.

4.1

High temperature behavior

As mentioned before, the limiting free energy FN (β) converges to a nonrandom quantity F (β). This
quantity can also be expressed in terms of the famous Parisi formula, which we state as follows.
Throughout the rest of the paper, we set
ξ(s) =

sp
2

for s ∈ [0, 1]. Let M be the collection of all cumulative distribution functions on [0, 1] equipped with
the L1 distance with respect to the Lebesgue measure. This is usually called the space of functional
order parameters in physics. For β > 0, define a functional Pβ on M by
Pβ (α) = Φβ,α (0, 0) −

β2
2

Z

1

α(s)ξ 00 (s)sds,

0

where Φβ,α is the weak solution [26] to the following PDE,
∂t Φβ,α = −

2 
β 2 ξ 00 
∂xx Φβ,α + α ∂x Φβ,α
2

with boundary condition Φβ,α (1, x) = log cosh x. For any β > 0, the Parisi formula states that
lim FN (β) = inf Pβ (α).

N →∞

α∈M

Although we only consider the pure p-spin model here, this formula also holds in more general
setting. Indeed, Talagrand [48] established the Parisi formula in the case of the mixed even p-spin
models. Later Panchenko [40] extends its validity to general mixtures of the model. Recently, it was
understood by Auffinger and Chen [2] that the functional Pβ is strictly convex, which guarantees
the uniqueness of the minimizer for Pβ . We shall call this minimizer the Parisi measure and denote
it by αP .
Recall that the high temperature regime R of HN is the collection of all β > 0 that satisfy
F (β) = β 2 /4. By a direct computation, the validity of this equation is the same as saying that the
14

Parisi measure satisfies αP ≡ 1, concluding from the uniqueness of the Parisi measure. This case
is usually called the replica symmetric solution of the model in physics literature [32]. Recall that
the critical temperature βp is defined as the maximum of R. Let g be a standard normal random
variable. For β > 0, define an auxiliary function by
ρβ (s) := E tanh2 βg

p

p

 β2 0
ξ 0 (s) cosh βg ξ 0 (s) e− 2 ξ (s) , ∀s ∈ [0, 1].

Our first theorem provides one way to characterize R and βp .
Theorem 2. For any p ≥ 2, R = (0, βp ]. In addition, the following two statements hold:
(i) Let β > 0. Then β ∈ R if and only if
Z r

ξ 00 (s) ρβ (s) − s ds ≤ 0, ∀r ∈ (0, 1].
0

(ii) If 0 < β < βp , then
Z

r


ξ 00 (s) ρβ (s) − s ds < 0, ∀r ∈ (0, 1].

(16)

0

Item (i) is essentially the first order optimality condition in order to obtain the replica symmetric
solution. Item (ii) states that the replica symmetric solution is stable if β stays away from the criticality. This is the most crucial property that will allow us to establish the desired high temperature
behavior of the overlap all the way up to the critical temperature.
Define the Gibbs measure by
GN,β (σ) = P

exp βHN (σ)
.
0
σ 0 ∈ΣN exp βHN (σ )

(17)

For i.i.d. samplings σ 1 , σ 2 from GN,β , we use h·iβ to denote the expectation with respect to the
1
2
product measure G⊗2
N,β . Recall the overlap R1,2 between σ and σ from (3). Our next two theorems
show that the overlap is concentrated around 0 in the high temperature regime with exponential tail
probability and moment control.
Theorem 3. Assume that p ≥ 2. Fix 0 < a < b < βp . For any ε > 0, there exists a constant K
such that for any β ∈ [a, b],
 N

E I |R1,2 | ≥ ε β ≤ K exp −
, ∀N ≥ 1,
(18)
K
where I is an indicator function.
Theorem 4. Assume that p ≥ 3. Fix 0 < b < βp . For any k ≥ 1, there exists a constant K > 0
such that for any β ∈ [0, b],
2k
E R1,2

β

≤

K
, ∀N ≥ 1.
Nk

In the case of the Sherrington-Kirkpatrick model (p = 2), it was computed that β2 = 1 (see
Remark 2 in [19]) and the same results as Theorems 3 and 4 were obtained in Talagrand’s book [50,
Chapters 11 and 13]. As for p ≥ 3, Bardina, Márquez, Rovira, and Tindel [12] established Theorem
4 for some b  βp as p increases. Our main contribution here is that the concentration of the overlap
is valid up to the critical temperature. As an application of Theorem 4, we deduce a control on the
fluctuation of the free energy in high temperature regime.
15

Proposition 1. Assume that p ≥ 3. Fix 0 < b < βp . There exists a constant K such that for any
0 ≤ β ≤ b,


β2
K
P FN (β) −
≥ r ≤ 2 p/2+1
4
r N

(19)

for any r > 0 and N ≥ 1.
This theorem basically says that the fluctuation of FN (β) is at most of the order N −p/4−1/2 .
Indeed, if there exists some δN ↑ ∞ such that


p
1
β2
P FN (β) −
≥ δN N − 4 − 2 ≥ c > 0
4
for all N ≥ 1, then this contradicts (19). For p = 2, Aizenman, Lebowitz, and Ruelle [1] proved
that N −p/4−1/2 = N −1 is the right order of the fluctuation for FN (β) and N (FN (β) − β 2 /4) converges to a Gaussian random variable up to the critical temperature βp = 1. Similarly, for even
p ≥ 4, Bovier, Kurkova, and Löwe [16] also showed that N p/4+1/2 (FN (β) − β 2 /4) has a Gaussian
fluctuation up to certain temperature strictly less than βp . From these, it is tempting to conjecture
that N p/4+1/2 (FN (β) − β 2 /4) follows Gaussian law in the weak limit in the entire high temperature
regime for all p ≥ 3. Based on Theorems 3 and 4, this should be achievable by an adoption of the
argument for the Sherrington-Kirkpatrick model [50, Section 11.4]. We do not pursue this direction
here.
Remark 3. One can also consider the mixed p-spin model, i.e., the Hamiltonian HN is again a
Gaussian process P
on ΣN with zero mean and covariance
structure EHN (σ 1 )HN (σ 2 ) = N ξ(R1,2 ) for
P
some ξ(s) := 2−1 p≥2 cp sp with cp ≥ 0 and p≥2 cp = 1. In a similar manner, one can define its
free energy and high temperature regime as those for FN (β) and R. In this general setting, it can
be checked that Theorem 2 remains valid. As for Theorems 3 and 4 and Proposition 1, they also
hold as long as there exists some p ≥ 3 such that cp 6= 0 and cp0 = 0 for all 2 ≤ p0 < p.

4.2

Proof of Theorem 2

We now turn to the proof of Theorem 2 by solving the Parisi formula. First, we establish a key
lemma on the strict monotonicity of ρβ in β. This type of inequality was initially discovered in [3]
in order to establish a Legendre duality principle for the Parisi formula. Surprisingly, we find that
it also serves as one of the central ingredients in the description of the high temperature behavior
of the model.
Lemma 5. For any s ∈ (0, 1] and 0 < β1 < β2 , we have ρβ1 (s) < ρβ2 (s).
Proof. Let s ∈ (0, 1] and 0 < β1 < β2 be fixed. Denote
p
A1 (x) = log cosh(β1 x ξ 0 (s)),
p
A2 (x) = log cosh(β2 x ξ 0 (s)),
p
C(x) = tanh2 (β1 x ξ 0 (s)).
Let g 0 be standard normal independent of g. Set

exp (1 − t)A1 (x) + tA2 (x)
.
S(t, x) =
E exp (1 − t)A1 (g 0 ) + tA2 (g 0 )

16

Define f (t) = EC(g)S(t, g). Note that A1 , A2 , and C are even. A direct computation gives


f 0 (t) = EC(g) A2 (g) − A1 (g) S(t, g) − EC(g)S(t, g) · E A2 (g 0 ) − A1 (g 0 ) S(t, g 0 )


= EC(|g|) A2 (|g|) − A1 (|g|) S(t, |g|) − EC(g)S(t, |g|) · E A2 (|g 0 |) − A1 (|g 0 |) S(t, |g 0 |)



= E C(|g|) − C(|g 0 |) A2 (|g|) − A1 (|g|) − A2 (|g 0 |) − A1 (|g 0 |) S(t, |g|)S(t, |g 0 |).
Since β2 > β1 > 0, this implies that A2 − A1 and C are strictly increasing on [0, ∞). Therefore, with
probability one,



C(|g|) − C(|g 0 |) A2 (|g|) − A1 (|g|) − A2 (|g 0 |) − A1 (|g 0 |) > 0.
p
2 0
It follows that f 0 (t) > 0 for t ∈ (0, 1) and as a result, noting that E cosh(β ξ 0 (s)) = eβ ξ (s)/2 gives
p
β2
− 22 ξ 0 (s)
0
ρβ1 (s) = f (0) < f (1) = E tanh (β1 g
< ρβ2 (s),
2 g ξ (s))e
p
p
where the last inequality used the fact that tanh2 (β1 x ξ 0 (s)) < tanh2 (β2 x ξ 0 (s)) for all x 6= 0
since β1 < β2 .
2

p

ξ 0 (s)) cosh(β

Proof of Theorem 2. To prove R = (0, βp ], we first notice two useful facts established in (32) and
(33) below that
Z β
β2
p
EFN (β) −
=
lE R1,2
dl
l
4
0
and
p
E R1,2

l

≥ 0.

Now if F (β) = β 2 /4, then the first display implies
Z β

β2 
p
= 0.
lim
lE R1,2
dl
=
lim
EF
(β)
−
N
l
N →∞ 0
N →∞
4
Consequently, from the second display, for any β 0 ∈ [0, β],
Z β0

β02 
p
0
lim EFN (β ) −
= lim
lE R1,2
dl = 0.
l
N →∞
N →∞ 0
4
Thus, (0, β] ⊂ R. This implies that R = (0, βp ] by the definition of R.
Next we justify (i) and (ii). From [19], one can compute the directional derivative of Pβ using
the stochastic optimal control theory. In particular, by applying [19, Theorem 2] and taking α0 ≡ 1,
Z



β 2 1 00
D+ Pβ (1 − λ)α0 + λα
=
ξ (s) α(s) − α0 (s) ρβ (s) − s ds
(20)
2 0
λ=0
for all α ∈ M. Write by using Fubini’s theorem,
Z 1


ξ 00 (s) α(s) − α0 (s) ρβ (s) − s ds
0
Z 1Z s
Z 1


=
ξ 00 (s) ρβ (s) − s α(dr)ds −
ξ 00 (s)α0 (s) ρβ (s) − s ds
0
0
0
Z 1 Z 1
Z 1



00
=
ξ (s) ρβ (s) − s ds α(dr) −
ξ 00 (s) ρβ (s) − s ds.
0

r

0

17

Assume that 0 < β ≤ βp . In this case, α0 is the Parisi measure and thus, the above equation is
nonnegative for all α by the optimality of α0 . This implies
Z 1
Z 1


00
ξ 00 (s) ρβ (s) − s ds
ξ (s) ρβ (s) − s ds ≥
0

r

for all r ∈ [0, 1]. Consequently, for all r ∈ [0, 1],
Z r

ξ 00 (s) ρβ (s) − s ds ≤ 0.

(21)

0

Conversely, if this inequality holds for some β > 0, then we can argue in the backward order to see
that the directional derivative (20) of Pβ at α0 is nonnegative for all α ∈ M. Consequently, from
the strict convexity of Pβ , α0 is a minimizer and it must be the Parisi measure. It then follows that
F (β) = Pβ (α0 ) = β 2 /4 and thus β ∈ R. This gives (i). As for (ii), note that βp also satisfies (21).
If there exists some 0 < β < βp such that
Z r

ξ 00 (s) ρβ (s) − s ds = 0
0

for some r ∈ (0, 1], then from Lemma 5, we arrive at a contradiction,
Z r

0<
ξ 00 (s) ρβp (s) − ρβ (s) ds
Z r
Z0 r


00
ξ 00 (s) ρβ (s) − s ds
=
ξ (s) ρβp (s) − s ds −
0
Z0 r

ξ 00 (s) ρβp (s) − s ds
=
0

≤0
Therefore, (16) must valid.

4.3

Proof of Theorems 3 and 4

First we give a brief description of our arguments for Theorems 3 and 4. Let BN be the collection
of all v such that v = R1,2 for some σ 1 , σ 2 ∈ ΣN . Let 0 < β < βp and ε > 0 be fixed. For v ∈ BN ,
consider the following coupled free energy
CFN,v (β) :=

X 1

1
β
1
2
√
log
exp
H
(σ
)
+
H
(σ
)
.
N
N
N
22N
2

(22)

R1,2 =v

Our approach relies on finding a good bound for this coupled free energy so that as long as v is away
from zero, then there exists a constant δ > 0 such that
ECFN,v (β) ≤ 2EFN (β) − δ.

(23)

If this is valid, then an application of sub-Gaussian concentration inequality for the free energies
(see [18, Proposition 9]) implies that with overwhelmingly probability,
δ
CFN,v (β) ≤ FN (β) − ,
2
18

which is equivalent to hI(R1,2 = v)iβ < e−δN/2 . This means that R1,2 can not charge the value v 6= 0
and the exponential tail control allows us to deduce Theorem 3. Based on Theorem 3, we adopt the
cavity method [49, 50] to obtain Theorem 4. In order to obtain (23), we use the two-dimensional
Guerra-Talagrand bound as in [50, Proposition 14.6.3.]. In the case of even p, this bound is known
to be valid and we show that the above argument can be carried through. However, for odd p ≥ 3,
the validity of the Guerra-Talagrand bound remains unknown. Surprisingly, if we consider v ≥ 0
and restrict the functional order parameters to be of one-step replica symmetry breaking, it can be
shown that this bound indeed holds, see the discussion in Subsection 4.5. As for v < 0, this case is
relatively easy in that we can control (22) by a direct use of Jensen’s inequality to obtain a good
upper bound for (22). Combining these two cases together, we show that (23) is also achievable for
odd p ≥ 3 and this gives Theorems 3 and 4.
4.3.1

Even p case

Proof of Theorem 3: even p ≥ 2. Let ε > 0. Fix v ∈ BN with v ≥ ε. The two-dimensional version of the Guerra-Talagrand bound [19, Chapter 15] states that if one chooses the same parametrization as [50, Proposition 14.6.3], then the coupled free energy CFN,v (β) can be controlled by an upper
bound of a similar expression as Pβ (α). More precisely, let Nv be the space of functional order parameters, the collection of all nonnegative and nondecreasing functions with right continuity and
γ(v) ≤ 2 on [0, v]. For γ ∈ Nv , consider the following PDE solution,
∂s Ψγ = −

2 
β 2 ξ 00
∂xx Ψγ + γ ∂x Ψγ
2

(24)

for (s, x) ∈ [0, v) × R with boundary condition
Ψγ (v, x) = log cosh x +


β2 0
ξ (1) − ξ 0 (v) .
2

Define a functional on Nv by
Lv (γ) = 2Ψγ (0, 0) − β

2

Z

v

00

Z

γ(s)ξ (s)sds +

0

1


ξ 00 (s)sds .

v

Note that if α ∈ M with α(v) = 1, then Lv (γ) = 2Pβ (α) for all γ ∈ Nv satisfying γ(s) = α(s) on
[0, v]. The Guerra-Talagrand inequality states that
ECFN,v (β) ≤ Lv (γ)

(25)

for all γ ∈ Nv . Take γ0 ∈ Nv by letting γ0 (s) = αP (s) on [0, v]. Similar to the directional derivative
of Pβ , we can also compute that for any γ ∈ Nu ,
Z v
2
D+ Lv ((1 − λ)γ0 + λγ)
=β
ξ 00 (s)(ρβ (s) − s)(γ(s) − γ0 (s))ds.
λ=0

0

Note that αP (s) ≡ 1 on [0, 1]. If we fix γ = 2αP ∈ Nv , then from (16), the above equation implies
Z v
2
D+ Lv ((1 − λ)γ0 + λγ)
=β
ξ 00 (s)(ρβ (s) − s)ds < 0.
λ=0

0

This means that there exists some λ0 > 0 such that
Lv ((1 + λ0 )αP ) = Lv ((1 − λ0 )γ0 + λ0 γ) < Lv (γ0 ) = 2Pβ (αP ).
19

Note that the functional Lv and the space Nv can be defined for all v ∈ [0, 1]. It also can be checked
(see, e.g., [19]) that (v, β) ∈ [0, 1] × [a, b] 7→ inf 0≤λ≤1 Lv ((1 + λ)αP ) is continuous. Therefore, there
exists a constant δ > 0 such that
inf Lv ((1 + λ)αP ) < 2Pβ (αP ) − δ

(26)

0≤λ≤1

for all v ∈ [ε, 1] ∩ BN and β ∈ [a, b]. Consequently, from (25) and this inequality,
ECFN,v (β) ≤ 2Pβ (αP ) − δ
for all v ∈ [ε, 1]∩BN , β ∈ [a, b], and N ≥ 1. Note that it is a classical result (see [47]) that if a sequence
of convex functions is convergent on an open interval of R, then it must be uniformly convergent on
any compact subset of this open interval. Thus, EFN (β) converges to Pβ (αP ) uniformly on [a, b].
From this, a standard application of the sub-Gaussian concentration inequality for the free energies
(see, e.g., [18, Appendix]) implies that there exists some K > 0 independent of N and δ 0 > 0 such
that for any β ∈ [a, b] and v ∈ [ε, 1] ∩ BN , with probability at least 1 − Ke−N/K ,
CFN,v (β) ≤ 2FN (β) − δ 0
for any N ≥ 1. This clearly implies that there exists a constant K 0 > 0 such that for any β ∈ [a, b],
E I(R1,2 ≥ ε)

β

≤ KN exp(−δ 0 N ) + Ke−N/K ≤ K 0 e−N/K

for all N ≥ 1. Finally, since p is even, E I(R1,2 ≥ ε)

β

0

= E I(R1,2 ≤ −ε) β . Thus, (18) holds.

Next we use the cavity method to establish Theorem 4 for even p ≥ 4. Our proof is based on a
mixed argument of [49, Chapter 1] and [50, Chapter 13]. Before we start the main proof, we define
some notation and establish some auxiliary lemmas. For any subset A of {1, . . . , p}, let IA be the
collection of all (i1 , . . . , ip ) ∈ {1, . . . , N }p such that ia = N for all a ∈ A and ia ∈ {1, . . . , N − 1} for
all a ∈
/ A. Set the Hamiltonian
X
1
A
HN
(σ) = (p−1)/2
gi1 ,...,ip σi1 · · · σip
N
(i1 ,...,ip )∈IA

for σ ∈ ΣN , where
A 1
A 2
EHN
(σ )HN
(σ ) =

1
N |A|−1

−
R1,2

p−|A|

1 2
σN
σN

|A|

.

(27)

From this, we can express
HN (σ) =

p
X
X

A
HN
(σ),

j=0 A:|A|=j

Consider the interpolating Hamiltonian by
p
 N − 1 (p−1)/2
X
√ X
A
HN,t (σ) =
HN −1 (σ) + t
HN
(σ).
N
j=1 A:|A|=j

Denote by (σ ` )`≥1 a√
sequence
of i.i.d. samplings from the Gibbs measure associated to the Boltzmann

weight exp βHN,t / 2 . For clarity, we omit the variable β and denote the Gibbs average with
respect to this sequence simply by h·it . Assume that f is a bounded function of the i.i.d. σ 1 , . . . , σ n
samplings. For t ∈ [0, 1], set νt (f ) = Ehf it . It is easy to check that HN,t = HN when t = 1. For
PN −1 ` `0
−
−1
simplicity we denote ν(f ) = ν1 (f ). Set R`,`
0 = N
i=1 σi σi .
20

Lemma 6. Let f be a bounded function depending only on the i.i.d. samplings σ 1 , . . . , σ n . Then
p  
n

 
β2 X p
1 hX
− p−j
` `0 j
νt0 (f ) =
ν
f
R
σ
σ
0
t
N
N
`,`
j N j−1
2
0
j=1

`<`

−n

n
X

−
νt f R`,n+1

p−j

` n+1
σN
σN

j 

`=1

+

p−j n+1 n+2 j i
n(n + 1)
−
νt f Rn+1,n+2
σN σN
.
2

Proof. Compute directly
p
n
E
β X X D X A `
A n+1
.
E f
HN (σ ) − nHN
(σ
)
νt0 (f ) = √
t
2 2t j=1 A:|A|=j
`=1

Using Gaussian integration by parts and (27) gives
√
n
n
D X
E
D
X

 E
β t
− p−|A|
A `
` `0 |A|
√
E f R`,`
σN
σN
E f
HN (σ ) =
0
t
t
N |A|−1 2 `,`0 =1
`=1
√
n
p−|A| ` n+1 |A| E
nβ t X D
−
√
E f R`,n+1
σN σN
−
t
N |A|−1 2 `=1
and
E

E

A n+1
f HN
(σ
)

√
n+1
X D
p−|A| ` n+1 |A| E
β t
−
√
E f R`,n+1
σN σN
=
t
t
N |A|−1 2 `=1
√ D
p−|A| n+1 n+2 |A| E
(n + 1)β t
−
√ E f Rn+1,n+2
−
.
σN σN
t
N |A|−1 2

Plugging these two equations into νt0 (f ) and performing some rearrangement gives the announced
result .
Lemma 7. Let f be a nonnegative bounded function depending only on the i.i.d. samplings σ 1 , . . . , σ n .
We have

νt (f ) ≤ exp 2p n2 β 2 ν(f ).
Proof. Observe that from Lemma 6,
|νt0 (f )| ≤ 2p n2 β 2 νt (f ).
Thus,
−νt0 (f ) ≤ 2p n2 β 2 νt (f ).
Taking integral on the interval [t, 1] leads to
Z
log νt (f ) − log ν1 (f ) = −
t

1

νs0 (f )
ds ≤ 2p n2 β 2 (1 − t) ≤ 2p n2 β 2 ,
νs (f )

which finishes the proof of the claim.

21

Lemma 8. Assume that
K0
2j 
ν R1,2
≤ j , ∀0 ≤ j ≤ k
N
for some K0 ≥ 1. Then

K0
ν |R1,2 |j ≤ j/2 , ∀0 ≤ j ≤ 2k,
N

22k K0
− 2k
ν |R1,2
|
≤
.
Nk
Proof. The first inequality follows directly by Hölder’s inequality and noting that K0 ≥ 1. As for
−
1 σ 2 /N and using the Binomial
the second one, it can be established by noting that R1,2 = R1,2
+ σN
N
formula. Indeed,
ν

− 2k
|R1,2
|



≤

2k  
X
2k

j

j=0

≤ K0

1
N 2k−j

2k  
X
2k

ν |R1,2 |j

1
N 2k−j

j
j=0
1
1 2k
≤ K0
+√
N
N
2k
2 K0
.
≤
Nk

·



1
N j/2

Lemma 9. For any positive integer l, we have
− l+1
l+1
(R1,2
)
− R1,2
≤


l
− l
|R1,2
| + |R1,2 |l .
N

Proof. The proof follows simply by using |xl+1 − y l+1 | ≤ l|x − y|(|x|l + |y|l ) for any x, y ∈ R.
Proof of Theorem 4: even p ≥ 4. Let 0 < b < βp be fixed. We proceed by induction. Assume
that there exists some K0 ≥ 1 independent of N ≥ 1 such that for any β ∈ [0, b],
K0
2j 
ν R1,2
≤ j , ∀N ≥ 1
N
for all 0 ≤ j ≤ k. Our goal is to prove that there exists a constant K00 ≥ 1 such that for any β ∈ [0, b],
2(k+1) 

ν R1,2

≤

K00
, ∀N ≥ 1.
N k+1

To this end, write by symmetry among sites,

2k+2
1 2 2k+1
ν(R1,2
) = ν σN
σN R1,2 .
Using Lemma 9 gives



− 2k+1
1 2 2k+1
1 2
ν σN
σN R1,2
= ν σN
σN R1,2
+ E,
22

where from the induction hypothesis and Lemma 8,
|E| ≤


 2(2k + 1)C1
(2k + 1)
− 2k
2k
,
ν R1,2
+ ν (R1,2
)
≤
N
N k+1

1 σ 2 (R− )2k+1 . We control ν(f ) by using the mean value theorem,
where C1 := 22k K0 . Set f = σN
1,2
N

|ν(f ) − ν0 (f )| ≤ sup |νt0 (f )|.
t∈[0,1]
1 , . . . , σ 4 are i.i.d. Bernoulli random variables on {−1, 1} with
Note that under the measure ν0 , σN
N
−
mean zero and are independent of R`,`
0 . This implies that ν0 (f ) = 0. In addition, from Lemma 6,

νt0 (f )

p  

 
1 h
β2 X p
− 2k+1+p−j
1 2 j+1
νt R1,2
σN
σN
=
j−1
j N
2
j=1
X


 ` 3 j 
− 2k+1
− p−j
1 2
−2
νt R1,2
R`,3
σN
σN σN
σN
`=1,2
−
+ 3νt R1,2

2k+1

−
R3,4

p−j

1 2
σN
σN



3 4
σN
σN

j i

.

It follows by Hölder’s inequality and Lemma 7 that
|νt0 (f )|
p  
i


β2 X p
1 h
− 2k+1 − p−j
− 2k+1+p−j
− 2k+1 − p−j
≤
|
|
+
3ν
|
|R
ν
|
+
4ν
|
|R
|R
|R
|R
t
t
t
3,4
1,3
1,2
1,2
1,2
2
j N j−1
j=1
p  
X

p
1
− 2k+1+p−j
2
≤ 4β
|
ν
|R
t
1,2
j N j−1
j=1
p  
X

p
1
− 2k+1+p−j
2
p+2 2
≤ 4β exp 2 β
|
.
ν |R1,2
(28)
j−1
j N
j=1

Here, write
p  
X
p
j=1

j

1
N j−1

ν

− 2k+1+p−j
|R1,2
|



= pν

− 2k+p
|R1,2
|



+

p  
X
p
j=2

j

1
N j−1


− 2k+1+p−j
ν |R1,2
|
.

To control the first term, we use Lemma 9 to get




(2k + p)
− 2k+p
− 2k+p−1
ν |R1,2
|
− ν |R1,2 |2k+p ≤
ν |R1,2
|
+ ν |R1,2 |2k+p−1
N


(2k + p)
− 2k
≤
ν |R1,2
|
+ ν |R1,2 |2k
N
(2k + p)C1
≤
.
N k+1
As for the second term,
p  
X
p
j=2

 2p
 2p

2 p C1
− 2k+1
− 2k
− 2k+1+p−j
ν
|R
|
≤
ν
|R
|
≤
ν
|R
|
≤
.
1,2
1,2
1,2
j N j−1
N
N
N k+1
1

23

From (28), the above two inequalities give
 C3 (β)
|νt0 (f )| ≤ C2 (β)ν |R1,2 |2k+p + k+1 .
N
for

C2 (β) := 4pβ 2 exp 2p+2 β 2 ,


C3 (β) := 4β 2 exp 2p+2 β 2 (2k + p)C1 p + 2p C1 .
As a result,
2k+2
ν(R1,2
) = ν(f )

≤ ν0 (f ) + sup |νt0 (f )|
t∈[0,1]

 C3 (β)
≤ C2 (β)ν |R1,2 |2k+p + k+1
N

C
3 (β)
(29)
≤ C2 (β)ν |R1,2 |2k+3 + k+1 ,
N
where the last inequality used the assumption that p ≥ 3. Note that C2 and C3 are nondecreasing
functions of β. Now we divide our discussion into two cases:
Case I: Let 0 < a ≤ b be the largest number such that C2 (a) ≤ 21 . From the above inequality, since
 C3 (a)
2k+2
) ≤ C2 (a)ν |R1,2 |2k+2 + k+1 ,
ν(R1,2
N
we see that for any β ∈ [0, a],
2k+2
)≤
ν(R1,2

2C3 (a)
.
N k+1

Case II: Let a be the constant we chose from Case I. Fix ε > 0 such that εC2 (b) < 1/2. For this ε,
we use Theorem 3 to find a constant K > 0 independent of N such that for any β ∈ [a, b],
 N

ν I |R1,2 | ≥ ε ≤ K exp −
, ∀N ≥ 1.
K
Therefore,



ν |R1,2 |2k+3 ≤ ν I |R1,2 | ≥ ε + ν |R1,2 |2k+3 I |R1,2 | < ε
 N

2k+2
≤ K exp −
+ εν R1,2
.
K
From (29), this implies that
 N
 C3 (b)
2k+2
2k+2
ν(R1,2
) ≤ C2 (b)K exp −
+ εC2 (b)ν R1,2
+ k+1 .
K
N
Since εC2 (b) < 1/2, this inequality deduces that for any β ∈ [a, b],

 N  C (b) 
3
2k+2
ν(R1,2
) ≤ 2 C2 (b)K exp −
+ k+1 .
K
N
Combining the above two cases together implies the existence of a constant K00 independent of N
such that
K00
2k+2
ν(R1,2
) ≤ k+1
N
for all β ∈ [0, b] and N ≥ 1. This completes our proof.

24

Remark 4. We have seen in Case II that if p ≥ 3, it is possible to obtain moment control for the
overlap for big β by using (29) as long as we know the tail control of the overlap. If p = 2, (29) loses
2k+2
its power and one must go further to consider the second derivative of ν(R1,2
) in order to obtain
the moment control in the Sherrington-Kirkpatrick model. See [50, Chapter 11] for detail.
4.3.2

Odd p case

In this subsection, we establish Theorems 3 and 4 for odd p ≥ 3. It relies on the validity of the GuerraTalagrand bound stated in the following proposition. Recall the coupled free energy CFN,v (β) from
(22). For any v ∈ [0, 1] and ε > 0, define
CFN,v,ε (β) =

X

1
β
log
exp √ HN (σ 1 ) + HN (σ 2 ) ,
N
2

where the sum is over all σ 1 , σ 2 ∈ ΣN with R1,2 ∈ [v − ε, v + ε]. Recall Lv (γ) from (25).
Proposition 2. Let p ≥ 3 be an odd number. For any v ∈ [0, 1], we have
lim lim sup ECFN,v,ε (β) ≤ Lv (γ)
ε↓0 N →∞

if γ ∈ Nv is a constant function on [0, v].
As we mentioned before, for even p ≥ 2 the Guerra-Talagrand bound (25) is valid for all γ ∈ Nv ,
but it is not clear if the same inequality holds for odd p. Nevertheless, this proposition states that
the Guerra-Talagrand bound is true in the limit N → ∞ as long as we consider v ∈ [0, 1] and take
only constant γ’s. This choice of γ is called the one-step replica symmetry breaking functional order
parameter in spin glass literature. We now turn to the proof of Theorems 3 and 4. We defer the
proof of Proposition 2 to Subsection 4.5.
Proof of Theorem 3: odd p ≥ 3. Let 0 < a < b < βp . Let ε0 > 0 be fixed. Recall that in the
argument for Theorem 3 with even p, we have that from (26), there exists some δ > 0 such that
inf Lv ((1 + λ)αP ) < 2Pβ (α) − δ

0≤λ≤1

for all v ∈ [ε0 , 1] and β ∈ [a, b]. As this part of the argument does not rely on whether p is odd or
even, the same inequality is still valid for odd p. Since (1 + λ)αP ≡ 1 + λ on [0, v], it follows from
Proposition 2 that
lim lim sup ECFN,v,ε (β) ≤ 2Pβ (αP ) − δ
ε↓0 N →∞

for any v ∈ [ε0 , 1] and β ∈ [a, b]. Since the left-hand side of this inequality is in the logarithmic scale,
from the sub-Gaussian concentration inequality for the free energies [18, Proposition 9], it can be
argued by a covering argument that for any β ∈ [a, b],
lim sup
N →∞

1
E log
N

1

X
R1,2 ∈[ε0 ,1]

22N


β
δ
exp √ HN (σ 1 ) + HN (σ 2 ) ≤ 2Pβ (αP ) − .
2
2

Now using the uniform convergence of the free energies for β ∈ [a, b] on both sides and the Parisi
formula, there exists a constant δ 0 > 0 such that
1
E log
N

X
R1,2 ∈[ε0 ,1]

1
22N


β
exp √ HN (σ 1 ) + HN (σ 2 ) ≤ 2EFN (β) − δ 0
2

25

for all N ≥ 1 and β ∈ [a, b]. From this, we can argue by another application of the sub-Gaussian
concentration inequality for the free energies in an identical manner as the last part of the proof of
Theorem 3 with even p to get that there exists some positive constant K such that
E I(R1,2 ∈ [ε0 , 1])

β

≤ Ke−N/K

for any N ≥ 1 and β ∈ [a, b], where h·iβ is the Gibbs average with respect to the product of the
Gibbs measure GN,β in (17). It remains to show that there exists some K 0 > 0 such that
E I(R1,2 ∈ [−1, −ε0 ])

β

≤ K 0 e−N/K

0

(30)

for any N ≥ 1 and β ∈ [a, b]. To see this, from Jensen’s inequality,
1
E log
N
≤

1

X
R1,2 ∈[−1,−ε0 ]

1
log
N

22N

X
R1,2 ∈[−1,−ε0 ]


β
exp √ HN (σ 1 ) + HN (σ 2 )
2

1
22N

exp


β2N
β2
p 
2 + 2R1,2
≤
2 − 2εp0 ,
4
4

where the last inequality used the fact that p is odd. Since limN →∞ FN (β) = β 2 /4 for β ∈ [a, b], a
similar argument as above gives (30).
Proof of Theorem 4: odd p ≥ 3. Note that given the validity of Theorem 3, the assumption of
p being even is not important in the proof of Theorem 4 for even p, so the statement of Theorem 4
for odd p remains valid by the same cavity argument and using Theorem 3 for odd p.

4.4

Proof of Proposition 1

Recall that R1,2 is the overlap between two i.i.d. samplings σ 1 and σ 2 from the Gibbs measure (17)
and h·iβ is the Gibbs average with respect to these random variables.
Lemma 10. For any p ≥ 2 and β ≥ 0, we have


β2
2
p
P FN (β) −
≥ r ≤ 2 E R1,2
4
r N

β

+

1 
2r2

Z
0

β

p
lE R1,2
dl
l

2

,

∀r > 0.

Proof. For any r > 0, Chebyshev’s inequality yields


1 
β2
β 2 2
≥ r ≤ 2 E FN (β) −
P FN (β) −
4
r
4

2
β 2 2 
≤ 2 Var(FN (β)) + EFN (β) −
,
r
4

(31)

where the second inequality used the trivial bound (a + b)2 ≤ 2a2 + 2b2 . The two terms in the last
inequality can be controlled as follows. First, from the Poincaré inequality for Gaussian measure,
since
β
∂gi1 ,...,ip FN (β) = (p+1)/2 σi1 · · · σip β ,
N
we have

2 β 2
X
β
p
Var(FN (β)) ≤ E
σ
·
·
·
σ
=
E R1,2
.
(32)
i
ip β
β
N
N (p+1)/2 1
1≤i1 ,...,ip ≤N

26

On the other hand, using Gaussian integration by parts,
d
1 D HN (σ) E
β
p
EFN (β) = √ E
=
1 − E R1,2
dβ
N
2
β
2


β

and thus,
β
d
EFN (β) = EFN (0) +
EFN (l)dl
0 dl
Z β

l
p
1 − E R1,2
dl
=
l
0 2
Z
β2 1 β
p
=
lE R1,2
dl,
−
l
4
2 0

Z

(33)

which implies


β 2 2 1 
EFN (β) −
=
4
4

β

Z
0

p
lE R1,2
dl
l

2

.

This together with (31) and (32) clearly completes our proof.
Proof of Proposition 1. Let 0 < b < βp be fixed. From Theorem 4, there exists a constant K
such that
E |R1,2 |p iβ ≤

K
N p/2

for any N ≥ 1 and 0 ≤ β ≤ b. Here we used Jensen’s inequality in the case that p is odd. From
Lemma 10, for any r > 0,
Z


1  β lK 2
2K
β2
dl
P FN (β) −
≥ r ≤ 2 p/2+1 + 2
p/2
4
2r
r N
0 N
2K
β4K 2
= 2 p/2+1 + 2 p
8r N
r N

1
b4 K 2 
≤ 2 p/2+1 2K +
.
8
r N
This completes our proof.

4.5

Proof of Proposition 2

This subsection is devoted to establishing Proposition 2. We briefly outline our argument as follows.
Our approach is based on an interpolation of the coupled free energy CFN,v,ε (β) via Guerra’s replica
symmetry breaking scheme. In the case of the mixed even p-spin models, the same interpolation
was also considered in Talagrand [50], where it was understood that the error term in the derivative
of the interpolated coupled free energy consists of a sum of four main parts, in terms of the overlap
matrix and the functional order parameter. In this case, it can be easily checked (see Remark 5) that
each of the four parts in the error term is nonnegative, which critically determines the validity of the
Guerra-Talagrand inequality. In our case, the model involves purely odd p-spin interactions. Due to
the oddness of p, it is not clear that the error term remains nonnegative. To overcome this difficulty,
we add a vanishing perturbation of higher order spin interactions to the coupled systems in the same
27

manner as that performed in Panchenko [42]. On the one hand, this will not influence the coupled
free energy in the thermodynamic limit. On the other hand, this perturbation will be strong enough
such that the system satisfies the Ghirlanda-Guerra identities and then leads to the ultrametricity of
the overlaps [38]. One of the important consequences of the ultrametricity, discovered by Panchenko
[41, 42], is that the entries in the overlap matrix will be synchronized in the sense that the whole
overlap matrix becomes asymptotically symmetric and positive semi-definite. From these, if we in
particular choose the functional order parameters to be of one-step replica symmetry breaking, the
four main parts together in the error term exhibits a nonnegative sign and gives the desired upper
bound with this choice of the order parameters.
We now turn to our proof. Throughout the remainder of this subsection, let p ≥ 3 be a fixed
odd number. The following lemma is crucial to our argument. Define
Γ(v, x) = xp − pxv p−1 + (p − 1)v p
for v ∈ [0, 1] and x ∈ [−1, 1].

Figure 1: Graph for Γ(v, ·) with p = 3 and v = 0 (dashed line), = 0.3 (solid line), = 0.7 (dotted line)

Lemma 11. For any x, y, z ∈ [−1, 1], if the matrix


x z
z y

(34)

is positive semi-definite, then Γ(v, x) + Γ(v, y) + 2Γ(v, z) ≥ 0 for any v ∈ [0, 1].
Proof. Let v ∈ [0, 1] be fixed. For convenience, set
f (x) = Γ(v, x).
Let us begin by stating some properties of f (see Figure 1), which can be easily verified by a direct
computation. First, since p is odd, f is convex on [0, 1] and concave on [−1, 0]. In addition, f ≥ 0
on [0, 1]; on the interval [−1, 0], either f ≥ 0 on [−1, 0] or there exists a unique x0 ≥ v such that
f ≤ 0 on [−1, −x0 ] and f ≥ 0 on [−x0 , 0]. Finally, f 0 ≥ 0 on [−1, −v].
Next, we turn to the proof of the announced inequality. Note that the positive semi-definiteness
√
of (34) ensures x, y ≥ 0 and |z| ≤ xy. From the above stated properties of f , it suffices to assume
that x0 exists and z ≤ −x0 . Since f is convex on [0, 1] and x, y ≥ 0,
f

x + y 
2

≤

f (x) + f (y)
.
2

28

√
Also since f 0 ≥ 0 on [−1, −x0 ] and −(x + y)/2 ≤ − xy ≤ z, we see that
 x + y
√
f (z) ≥ f (− xy) ≥ f −
.
2
From these,
 x + y 
 x + y 
f (x) + f (y) + 2f (z) ≥ 2 f
+f −
.
2
2
Our proof is then completed by noting that f (c) + f (−c) ≥ 0 for any c ∈ [0, 1]. This holds because
p is odd and this yields

f (c) + f (−c) = cp − pcv p−1 + (p − 1)v p + −cp + pcv p−1 + (p − 1)v p = 2(p − 1)v p ≥ 0.

To establish the proof of Proposition 2, we first make some preparations in four steps.
Step 1: Perturbation. We construct a Hamiltonian of smaller order in the same fashion as that in
[42]. It will be used later as a perturbation along Guerra’s interpolation. Let (λl )l≥1 be a numeration
of Q ∩ [−1, 1]. For σ ∈ ΣN and e = (i1 , . . . , ir ) ∈ {1, . . . , N }r , denote
σe = σi1 · · · σir .
For any σ 1 , σ 2 ∈ ΣN and l, l0 ≥ 1, we set


l,l0 1
(σ , σ 2 ) = λl σe11 + λl0 σe21 · · · λl σe1n + λl0 σe2n
Sr,I
n

0 ≥ 1, denote by
. For m, n1 , . . . , nm , l1 , l10 , . . . , lm , lm

0
ω = m, n1 , . . . , nm , l1 , l10 , . . . , lm , lm
.

for any I = (e1 , . . . , en ) ∈ {1, . . . , N }r

(35)

Set

ω
σ1, σ2 =
XN

1
N r(n1 +···+nm )/2

X

0
l ,l0 ,...,l ,lm

m
1 1
gr,I
1 ,...,Im

m
Y

lj ,l0

Sr,Ijj (σ 1 , σ 2 ),

j=1

I1 ,...,Im

0
n
l1 ,l10 ,...,lm ,lm
are standard normal
where Ij = (e1 , . . . , enj ) ∈ {1, . . . , N }r j for j = 1, . . . , m and gr,I
1 ,...,Im
random variables and are independent of all indices and other randomness. For any (σ 1 (k), σ 2 (k))
and (σ 1 (k 0 ), σ 2 (k 0 )) ∈ Σ2N , set the overlap matrix Qk,k0 by
"
#

 

1,2
Q1,1
Q
R σ 1 (k), σ 1 (k 0 ) R σ 1 (k), σ 2 (k 0 )
0
0
k,k
k,k
Qk,k0 =
:=
,
2,2
R σ 2 (k), σ 1 (k 0 ) R σ 2 (k), σ 2 (k 0 )
Q2,1
k,k0 Qk,k0

where R(σ, σ 0 ) := N −1

PN

0
i=1 σi σi

ω can be computed through
for any σ, σ 0 ∈ ΣN . The covariance of XN

m
 ω 1 0 2 0  Y
ω
EXN
σ 1 (k), σ 2 (k) XN
(σ (k ), σ (k ) =
Q◦r
k,k0 λlj ,lj0 , λlj ,lj0

nj

,

(36)

j=1

where Q◦r
k,k0 is the Hadamard product of Qk,k0 for r times, λl,l0 is the column vector (λl , λl0 ), and h·, ·i
means the usual dot product. Note that (36) is bounded by 4n1 +···+nm . Let θ = (θω )ω be a sequence
29

of i.i.d. random variables sampled uniformly at random from the interval [1, 2] indexed by ω defined
in (35). From these, set the perturbation Hamiltonian as
 X θω ω 1 2 
θ
XN
σ1, σ2 =
X σ ,σ ,
8|ω| N
ω
where |ω| is the sum of all entries in the index ω. Then conditioning on θ, the covariance of
θ σ 1 (k), σ 2 (k) and X θ σ 1 (k 0 ), σ 2 (k 0 ) is given by
XN
N
m
X (θω )2 Y
ω

64|ω|

nj

Q◦r
k,k0 λlj ,lj0 , λlj ,lj0

.

j=1

Step 2: Guerra’s Interpolation scheme. In what follows, we introduce Guerra’s interpolation
scheme for the coupled free energy. Fix v ∈ [0, 1]. Let m0 = 0 < m1 < m2 < m3 = 1. Let (dj )j∈N
be the non-decreasing rearrangement of a Poisson point process of intensity measure x−m1 −1 dx. For
each j1 , let (dj1 ,j )j∈N be a non-decreasing rearrangement of a Poisson point process of intensity
x−m2 −1 dx. These are all independent of each other for all j1 and of (dj ). For each η = (j1 , j2 ) ∈ N2 ,
we define
d∗η = dj1 dj1 ,j2 .
The Ruelle probability cascades is defined by the probability weights (cη )η∈N2 ,
cη = P

d∗η

η 0 ∈N2

d∗η0

.

Set
1,1
1,1
ρ1,1
0 = 0, ρ1 = v, ρ2 = 1,
1,2
1,2
ρ1,2
0 = 0, ρ1 = v, ρ2 = v,
2,1
2,1
ρ2,1
0 = 0, ρ1 = v, ρ2 = v,
2,2
2,2
ρ2,2
0 = 0, ρ1 = v, ρ2 = 1.

Let (z11 , z12 ) and (z21 , z22 ) be two independent Gaussian random vectors with mean zero and covariance,
0

0

0

0 `,`
Eza` za` = ξ 0 (ρ`,`
a ) − ξ (ρa−1 )
2
1 , z2 )
1
for a = 1, 2 and `, `0 = 1, 2. Let (z1,j
1,j1 j1 ∈N and (zi,1,j1 , zi,1,j1 )j1 ∈N for 1 ≤ i ≤ N be i.i.d. copies
1
1
2
1
2
1
2
of (z1 , z1 ). Also, let (z2,j1 ,j2 , z2,j1 ,j2 )(j1 ,j2 )∈N2 and (zi,2,j1 ,j2 , zi,2,j1 ,j2 )(j1 ,j2 )∈N2 for 1 ≤ i ≤ N be i.i.d.
copies of (z21 , z22 ). We assume that these are all independent of each other. For (σ 1 , σ 2 , η) ∈ Σ2N × N2 ,
set
N
X X


0
`
`
HN
σ1, σ2, η =
σi` zi,1,j
+ zi,2,j
.
1
1 ,j2
`=1,2 i=1



Note that for any two σ 1 (1), σ 2 (1), η(1) , σ 1 (2), σ 2 (2), η(2) ∈ Σ2N × N2 , the covariance of this
Hamiltonian can be computed as
X
 0 1


0
0
0 `,`0
EHN
σ 1 (1), σ 2 (1), η(1) HN
σ (2), σ 2 (2), η(2) =
Q`,`
(37)
1,2 ξ ρη(1)∧η(2) ,
`,`0 =1,2

30

where for η(1) = (j1 (1), j2 (1)) and η(2) = (j1 (2), j2 (2)),

 0, if j1 (1) 6= j1 (2) and j2 (1) 6= j2 (2),
1, if j1 (1) = j1 (2) and j2 (1) 6= j2 (2),
η(1) ∧ η(2) =

2, if j1 (1) = j1 (2) and j2 (1) = j2 (2).
Let 1/4 < χ < 1/2 be a fixed constant. For t ∈ [0, 1], define the interpolating Hamiltonian with
perturbation by
√



t
t,θ
1
2
HN σ , σ , η = √ HN σ 1 + HN σ 2
2
√


0
θ
+ 1 − tHN
σ 1 , σ 2 , η + N χ XN
σ1, σ2 .
√
θ should be regarded as a
0 are of order
N and XN,θ is of order 1, so N χ XN
Note that HN and HN
vanishing perturbation. Let ε > 0 be fixed. Set


ΛN (ε) := σ 1 , σ 2 ∈ Σ2N × N2 : R1,2 ∈ [v − ε, v + ε] .
Define the interpolating free energy as
CFNt,θ (β) =

X cη

1
t,θ
log
exp βHN
σ1, σ2, η
2N
N
2
ΛN (ε)

and the Gibbs measure by
1
2
Gt,θ
N (σ , σ , η) =

1
t,θ
ZN

·

cη
t,θ 1
(σ , σ 2 , η)
exp βHN
22N

t,θ
is the normalizing constant. From now on, we denote
for (σ 1 , σ 2 , η) ∈ ΛN (ε), where ZN

(σ 1 (k), σ 2 (k), η(k))k≥1
as i.i.d. samplings from this Gibbs measure and the Gibbs average with respect to this sequence is
denoted by h·it,θ
N . For t ∈ [0, 1], define
ψN (t) = Eθ ECFNt,θ (β),
where the expectation E is with respect to the Gaussian randomness and the Ruelle probability
cascades, while Eθ is respect to the uniform random variable θ only. Now following the proof of
Lemma 15.7.2 in [50] using Gaussian integration by parts and (37) gives
0
ψN
(t) = −

β2
β2
t,θ
Eθ Πt,θ
−
Eθ EN
+ O(ε)
N
2
2

(38)

for
Πt,θ
N :=

X 

0

0

`,`
θ(ρ`,`
2 ) − E θ(ρη(1)∧η(2) )

t,θ
N



,

`,`0 =1,2
t,θ
EN
:=

X

0

0

0

0

`,` 0 `,`
`,`
E ξ(Q`,`
1,2 ) − Q1,2 ξ (ρη(1)∧η(2) ) + θ(ρη(1)∧η(2) )

`,`0 =1,2

31

t,θ
N

Here O(ε) means that |O(ε)| ≤ Cε for some constant C > 0 depending only on ξ. To handle Πt,θ
N and
t,θ
EN , we recall a crucial consequence of the Ruelle probability cascades that from Proposition 14.3.3.
[50], for any θ and t,

E I η(1) ∧ η(2) = a

t,θ
N

= ma+1 − ma , a = 0, 1, 2.

(39)

From this,
Πt,θ
N

=

X 

0
θ(ρ`,`
2 )

−

`,`0 =1,2

=

X

2
X


0
θ(ρ`,`
a )(ma+1 − ma )

a=0
2
X

0
`,`0 
mp θ(ρ`,`
a ) − θ(ρa−1 )

`,`0 =1,2 a=1




= 2 2m1 θ(v) − θ(0) + m2 θ(1) − θ(v) .

(40)

t,θ
is handled in the following two steps.
The control of EN

Step 3: Positive semi-definiteness of Q1,2 . We proceed to argue that the overlap matrix Q1,2 is
asymptotically symmetric and positive semi-definite. Recall the index ω from (35) and the covariance
ω from (36). Set
of XN
ω
Ck,k
0 =

m
Y

Q◦r
k,k0 λlj ,lj0 , λlj ,lj0

nj

.

(41)

j=1

For any n ≥ 2, let Fn be the collection of all measurable functions f of (Qk,k0 )1≤k6=k0 ≤n with |f | ≤ 1.
ω
From Theorem 3.2. [39], it is known that Ck,k
0 satisfies the so-called Ghirlanda-Guerra identities in
the average sense, i.e., for any ω,
lim Eθ ∆t,θ,ω
= 0,
N

(42)

N →∞

where
∆t,θ,ω
N

:= sup sup E
n≥2 f ∈Fn

t,θ
ω
f C1,n+1
N

1
− E f
n

n

t,θ
N

·E

ω t,θ
C1,2
N

1X
ω
−
E f C1,k
n

t,θ
N

.

k=2

Set
¯ t,θ =
∆
N

X 1 t,θ,ω
∆
.
2|ω| N
ω

From (42),
Z

1

lim

N →∞ 0

¯ t,θ dt = 0.
Eθ ∆
N

¯ t,θ converges to zero in L1 with respect to dPθ dt. From this, we can pass to a
In other words, ∆
N
¯ t,θ converges to zero dPθ dt-a.s. Let (t, θ) a realization such that
subsequence (Nj )j≥1 such that ∆
Nj
this limit holds. Note that (Qk,k0 )k,k0 ≥1 takes value in [−1, 1]N×N , which is a compact space with
respect to the metric
X
0
0
d(q, q 0 ) =
2−(k+k ) |qk,k0 − qk,k
0|
k,k0 ≥1

32


0
for q = (qk,k0 )k,k0 ≥1 and q 0 = (qk,k
0 )k,k 0 ≥1 . Thus, E I (Qk,k 0 )k,k 0 ≥1 ∈ ·

t,θ
Nj

for j ≥ 1 is a tight

sequence of probability measures on the measurable space
[−1, 1]N×N . As a result,
we can pass to a subsequence (Njl )l≥1 such that the overlap matrix (Qk,k0 )k,k0 ≥1 under Eh·it,θ
Nj
[−1, 1]N×N , B

l

t,θ,ω
0
converges in distribution. We use (Qt,θ
k,k0 )k,k ≥1 to denote this limit and set Ck,k0 via (41). Denote
t,θ
¯ t,θ and this weak convergence, we obtain that for
Qt,θ
n = (Q 0 )k,k0 ≤n . From the convergence of ∆
Njl

k,k

any n ≥ 1, index ω, and any bounded measurable function f depending on Qt,θ
n ,
n

t,θ,ω
Ef (Qt,θ
n )C1,n+1

1
1X
t,θ,ω
t,θ,ω
= Ef (Qt,θ
Ef (Qt,θ
n )EC1,2 +
n )C1,k .
n
n
k=2

One of the important consequences of these identities is that the overlap matrix Qt,θ
1,2 satisfies
Theorem 5 (Theorem 4 [42]). For almost surely P, Qt,θ
1,2 is symmetric positive semi-definite.
0

For any δ ≥ 0, set Aδ to be the collection of all matrix x = (x`,` )`,`0 =1,2 satisfying
x1,1 ≥ −δ,
x2,2 ≥ −δ,
|x1,2 − x2,1 | ≤ δ,
x1,1 x2,2 ≥ x1,2 x2,1 − δ.
Note that if x is a symmetric positive semi-definite matrix, then x ∈ Aδ . From Theorem 5,
lim E I Q1,2 ∈ Aδ



l→∞

t,θ
Njl

= 1, ∀δ > 0.

Observe that this limit holds independent of the choice of the subsequence (Njl )l≥1 of (Nj )j≥1 such
that (Qk,k0 )k,k0 ≥1 converges weakly under Eh·it,θ
Njl . Therefore, from the tightness of the sequence
 t,θ
E I (Qk,k0 )k,k0 ≥1 ∈ · N for j ≥ 1, we conclude that for any δ > 0,
j

lim E I Q1,2 ∈ Aδ

t,θ
Nj



j→∞

= 1.

Since this holds a.s. under the measure dPθ dt, the dominated convergence theorem implies that
Z 1
 t,θ
lim
Eθ E I Q1,2 ∈ Aδ N dt = 1, ∀δ > 0.
(43)
j

j→∞ 0

t,θ
Step 4: Control of the error term. Using Step 3, we now control EN
. Recall Γ from Lemma 11.
Note that
0
1
`,`0
`,`0 
`,`0 0 `,`0
`,`0
ξ Q`,`
1,2 − Q1,2 ξ (ρη(1)∧η(2) ) + θ(ρη(1)∧η(2) ) = Γ ρη(1)∧η(2) , Q1,2 .
2

Write
t,θ
EN
=

1 t,θ
t,θ
t,θ 
EN,1 + EN,2
+ EN,3
2

33

for
D
E
 X
0  t,θ
t,θ
EN,1
:= E I η(1) ∧ η(2) = 0
Γ 0, Q`,`
,
1,2
`,`0 =1,2

N

D
E
 X
0  t,θ
t,θ
EN,2
:= E I η(1) ∧ η(2) = 1
Γ v, Q`,`
,
1,2
`,`0 =1,2

N

D
Et,θ
 X
0
t,θ
`,`0 
.
EN,3
:= E I η(1) ∧ η(2) = 2
Γ ρ`,`
,
Q
2
1,2
`,`0 =1,2

N

From the asymptotic symmetry and positive semi-definiteness (43) and Fatou’s lemma, for any δ > 0,
Z

1

t,θ
Eθ EN
dt
j ,1
Z 1
D
 X
Et,θ
0
dt
Eθ E I η(1) ∧ η(2) = 0
Γ 0, Q`,`
= lim inf
1,2 ; Q1,2 ∈ Aδ

lim inf
j→∞

0

j→∞

Z

1

≥
≥
0

1

N

`,`0 =1,2

Et,θ
D
 X
0
Γ 0, Q`,`
;
Q
∈
A
dt
lim inf Eθ E I η(1) ∧ η(2) = 0
1,2
δ
1,2
j→∞

0

Z

0

N

`,`0 =1,2



lim inf Cδ Eθ E I η(1) ∧ η(2) = 0
j→∞

where
Cδ := inf

n X

t,θ
N



dt,

o
0
0
Γ(0, x`,` ) : (x`,` )`,`0 =1,2 ∈ Aδ .

`,`0 =1,2

Since the distance between Aδ and A0 converges to zero as δ ↓ 0 and Γ(0, x) is continuous on [−1, 1],
these imply that limδ↓0 Cδ = C0 ≥ 0 by Lemma 11. Thus,
Z
lim inf
j→∞

0

1

t,θ
Eθ EN
dt ≥ 0.
j ,1
0

t,θ
t,θ
are
, note that since ρ`,`
. As for EN
The same reasoning also gives the same inequality for EN
2
j ,3
j ,2
t,θ
. Nevertheless, from (39), this term is
not all the same, we can not use Lemma 11 to control EN
j ,3
bounded above by


t,θ
|EN
|
≤
4pE
I
η(1)
∧
η(2)
=
0
j ,3

t,θ
Nj

= 4p(m3 − m2 ) = 4p(1 − m2 ).

In conclusion, we arrive at
Z
lim inf
j→∞

0

1

t,θ
Eθ EN
dt ≥ −4p(1 − m2 ).
j

(44)

θ increases the coupled free
Proof of Proposition 2. Note that adding a Gaussian perturbation XN
energy ECFN,v,ε (β) (see, e.g., [50, Lemma 12.2.1.]), so

ECFN,v,ε (β) ≤ ψN (1).

34

(45)

θ is bounded above by a constant D > 0 independent of N, it
In addition, since the variance of XN
follows by releasing the overlap constraint and applying Jensen’s inequality that

ψN (0) ≤

=

1
E log
N

X
(σ 1 ,σ 2 ,η)∈Σ2N ×N2


cη
β2D
0
1
2
exp
βH
σ
,
σ
,
η
+
N
22N
2N 1−χ

X


β2D
1
1
1
2
2
cη coshN β z1,j
+ z2,j
coshN β z1,j
+ z2,j
+
E log
1
1 ,j2
1
1 ,j2
N
2N 1−χ
2
η∈N

=

 2m


1
β2D
1
log E1 exp
log E2 exp m2 log cosh β z 1 + z 2
+
,
m1
m2
2N 1−χ

where E1 and E2 are the expectations with respect to independent

z 1 ∼ N 0, ξ 0 (v) − ξ 0 (0) ,

z 2 ∼ N 0, ξ 0 (1) − ξ 0 (v) ,
respectively. Here the second equality of the above inequality used an identity for the coupled free
energy, weighted by the Ruelle probability cascades, from [50, Proposition 14.2.2]. From (38) and
the above inequality,
Z 1
ψN (1) = ψN (0) +
ψN (t)dt
0
 2m


1
1
log E1 exp
log E2 exp m2 log cosh β z 1 + z 2
≤
m1
m2
Z 1
Z
2
β
β2 1
β2D
t,θ
t,θ
−
dt +
Eθ ΠN dt −
Eθ EN
+ O(ε).
2 0
2 0
2N 1−χ
Let (Nj0 )j≥1 be any sequence with Nj0 ↑ ∞ as j → ∞ such that
lim ECFNj0 ,v,ε (β) = lim sup ECFN,v,ε (β).

j→∞

N →∞

In view of the argument of Steps 3 and 4, we can pass to a subsequence (Nj0l )l≥1 of (Nj0 )j≥1 such
that the conclusion (44) holds for this subsequence, i.e.,
Z 1
t,θ
lim inf
Eθ EN
0 dt ≥ −4p(1 − m2 ).
l→∞

0

jl

As a result, from this, (40), and (45),
lim sup ECFN,v,ε (β) = lim ECFNj0
l→∞

N →∞

≤

l

,v,ε (β)

 2m


1
1
log E1 exp
log E2 exp m2 log cosh β z 1 + z 2
m1
m2

2


β
2m1 θ(v) − θ(0) + m2 θ(1) − θ(v) + O(ε) + 2β 2 p(1 − m2 ).
−
2

Since this inequality holds for any ε > 0 and 0 < m2 < 1, sending ε ↓ 0 and m2 ↑ 1 leads to


1
lim lim sup ECFN,v,ε (β) ≤
log E1 exp 2m1 log E2 cosh β z 1 + z 2
ε↓0 N →∞
m1



− β 2 2m1 θ(v) − θ(0) + θ(1) − θ(v) .
35

By directly solving the PDE (24) via Cole-Hopf transformation for γ ∈ Nv satisfying γ ≡ 2m1 , the
first term of the right-hand side of the above inequality can be written as 2Ψγ (0, 0) and the two
terms together gives Lv (γ). This completes our proof.
Remark
As we have seen from the above proof, the most difficult part is to show that the error
R 1 5. t,θ
term 0 Eθ ENj dt has a nonnegative sign. In the case that p is even, one does not need to add
perturbation in order to achieve this. In fact, since ξ is convex on [−1, 1] for even p, it is clear that
t,θ
ξ(x) − yξ 0 (x) + θ(y) ≥ 0 for all x, y ∈ [−1, 1]. This immediately deduces EN
≥ 0 and then the
validity of the Guerra-Talagrand inequality.

Appendix
This appendix is devoted to establishing the existence of the limits for the auxiliary free energy
AFN (β) and the interpolating free energy LN (β) defined in (5) and (14), based on the approach in
[20], where the author obtained a variational representation for the limiting free energy of the mixed
even p-spin model with Curie-Weiss interaction. Define the free energy of the pure p-spin model
with external field by

 β
X 1
1
√
FN (β, x) =
H
(σ)
+
xN
m
(σ)
,
log
exp
N
N
N
2N
2
σ∈Σ
N

where
mN (σ) =

N
1 X
hi σi
N
i=1

is the magnetization of σ. It is known that the above free energy converges to a nonrandom constant,
which can be computed by the Parisi formula, see [39]. Denote this limit by F (β, x). We show that
the limiting free energies of AFN and LN can be expressed in terms of F (β, x).
Proposition 3. Let p ≥ 2. For any β > 0 and x > 0, the following two equations hold a.s.,
  β 2 pmp−1  β 2 (p − 1)mp 
AF (β) := lim AFN (β) = max F β,
−
,
N →∞
2
2
m∈[0,1]
  βxpmp−1  βx(p − 1)mp 
L(x) := lim LN (β) = max F β,
−
.
N →∞
2
2
m∈[0,1]

(46)
(47)

Before we turn to the proof of Proposition 1, we recall a few properties of FN (β, x) and F (β, x).
First, one of the important consequences of the Parisi formula states that F (β, x) is differentiable in
x ∈ R and ∂x F (β, x) > 0 for x > 0. See, for instance, [41]. For any measurable set A ⊂ [−1, 1], set

 β
X
1
1
√
log
H
(σ)
+
xN
m
(σ)
.
FN (β, x, A) =
exp
N
N
N
2N
2
m (σ)∈A
N

From the above differentiability of F (β, x) in x, it follows from [4, Theorem 1] that for any x > 0,
the magnetization mN (σ) is concentrated around ∂x F (β, x) > 0 under the free energy, i.e., for any
ε > 0,

lim FN β, x, ∂x F (β, x) − ε, ∂x F (β, x) + ε = F (β, x).
N →∞

This evidently implies that

lim FN β, x, [0, 1] = F (β, x).

N →∞

36

(48)

Proof of Proposition 3. For any measurable A ⊂ [−1, 1], define
1
AFN (β, A) =
log
N

X
mN (σ)∈A

 β

1
β2N
p
√
HN (σ) +
exp
mN (σ) .
2N
2
2

To prove (47), we first consider the case that p is odd. Since sp is convex on [0, 1],

mN (σ)p ≥ mp + pmp−1 mN (σ) − m = pmp−1 mN (σ) − (p − 1)mp ,

(49)

whenever m, mN (σ) ∈ [0, 1]. This inequality deduces that
 β 2 pmp−1
 β 2 (p − 1)mp

AFN β, [0, 1] ≥ FN β,
, [0, 1] −
2
2
for any m ∈ [0, 1], from which letting N → ∞ and using (48) give that
  β 2 pmp−1  β 2 (p − 1)mp 

lim sup AFN β, [0, 1] ≥ max F β,
−
.
2
2
m∈[0,1]
N →∞

(50)

To obtain the upper bound, set mk = k/N for 0 ≤ k ≤ N. Write

AFN β, [0, 1]
N
 β
X
X
β 2 pmkp−1
β 2 (p − 1)mpk 
1
1
=
log
exp √ HN (σ) +
N mN (σ) −
N
2N
2
2
2
k=0 m (σ)=m
N

≤

1
log
N

N X
X
k=0 σ
N
X

k

 β
β 2 pmkp−1
β 2 (p − 1)mpk 
1
√
H
(σ)
+
exp
N
m
(σ)
−
N
N
2N
2
2
2

β 2 pmkp−1  β 2 (p − 1)mpk 
exp N FN β,
−
2
2
k=0
  β 2 pmp−1  β 2 (p − 1)mp 
log(N + 1)
≤
+ max FN β,
−
.
N
2
2
m∈[0,1]
1
log
=
N





Note that FN (β, ·) is convex and converges to F (β, ·) pointwise. It follows by the classical theory of
convex functions [47] that this convergence must be uniform on compact intervals. As a result,
  β 2 pmp−1  β 2 (p − 1)mp 

lim inf AFN β, [0, 1] ≤ max F β,
−
.
N →∞
2
2
m∈[0,1]
This and (50) together lead to
  β 2 pmp−1  β 2 (p − 1)mp 

lim AFN β, [0, 1] = max F β,
−
.
N →∞
2
2
m∈[0,1]
Next since sp is concave on [−1, 0), the inequality (49) is flipped,
mN (σ)p ≤ pmp−1 mN (σ) − (p − 1)mp
whenever m, mN (σ) ∈ [−1, 0). Thus, for any m ∈ [−1, 0),
 β 2 pmp−1  β 2 (p − 1)mp

AFN β, [−1, 0) ≤ FN β,
−
2
2
37

(51)

and then,

lim sup AFN β, [−1, 0) ≤
N →∞

  β 2 pmp−1  β 2 (p − 1)mp 
F β,
−
.
2
2
m∈[−1,0]
min

(52)

Denote by
  β 2 pmp−1  β 2 (p − 1)mp 
−
,
Γ+ = max F β,
2
2
m∈[0,1]
  β 2 pmp−1  β 2 (p − 1)mp 
Γ− = min F β,
−
.
2
2
m∈[−1,0]
Evidently Γ+ ≥ Γ− . From (51) and (52), with probability one, for any ε > 0, as long as N is large
enough,
eN (Γ+ −ε) ≤ eN AFN (β,[0,1]) ≤ eN (Γ+ +ε)
and
eN AFN (β,[−1,0)) ≤ eN (Γ− +ε) .
Since eN AFN (β) = eN AFN (β,[−1,0)) + eN AFN (β,[0,1]) , we obtain that
eN (Γ+ −ε) ≤ eN AFN (β) ≤ eN (Γ+ +ε) + eN (Γ− +ε) .
Consequently, taking N −1 log and sending N → ∞ and ε ↓ 0,

Γ+ = AF (β) = max Γ+ , Γ− = Γ+ ,
where the third equality used Γ− ≤ Γ+ . This establishes (46) for odd p. As for the case of even p,
since sp is convex on [−1, 1], this case is identical to that of (51). This gives (46). The proof for
(47) is the same as that for (46) without essential changes. We omit the details here.

References
[1] M. Aizenman, J. L. Lebowitz, and D. Ruelle. Some rigorous results on the SherringtonKirkpatrick spin glass model. Comm. Math. Phys., 112(1):3–20, 1987.
[2] A. Auffinger and W.-K. Chen. The Parisi formula has a unique minimizer. Comm. Math. Phys.,
335(3):1429–1444, 2015.
[3] A. Auffinger and W.-K. Chen. The Legendre structure of the Parisi formula. Comm. Math.
Physi., pages 1–20, 2016.
[4] A. Auffinger and W.-K. Chen. On concentration properties of disordered hamiltonians. ArXiv
e-prints, 2017.
[5] J. Baik, G. Ben Arous, and S. Péché. Phase transition of the largest eigenvalue for nonnull
complex sample covariance matrices. Ann. Probab., 33(5):1643–1697, 2005.
[6] J. Barbier, M. Dia, N. Macris, and F. Krzakala. The mutual information in random linear
estimation. 54th Annual Allerton Conference on Communication, Control, and Computing,
pages 625–632, 2016.
38

[7] J. Barbier, M. Dia, N. Macris, F. Krzakala, T. Lesieur, and L. Zdeborová. Mutual information
for symmetric rank-one matrix estimation: A proof of the replica formula. Advances in Neural
Information Processing Systems, 29:424–432, 2016.
[8] J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová. Phase transitions, optimal
errors and optimality of message-passing in generalized linear models. ArXiv e-prints, 2017.
[9] J. Barbier and N. Macris. The stochastic interpolation method: A simple scheme to prove
replica formulas in bayesian inference. ArXiv e-prints, 2017.
[10] J. Barbier, N. Macris, M. Dia, and F. Krzakala. Mutual information and optimality of approximate message-passing in random linear estimation. ArXiv e-prints, 2017.
[11] J. Barbier, N. Macris, and L. Miolane. The layered structure of tensor estimation and its mutual
information. 55th Annual Allerton Conference on Communication, Control, and Computing,
2017.
[12] X. Bardina, D. Márquez-Carreras, C. Rovira, and S. Tindel. The p-spin interaction model with
external field. Potential Anal., 21(4):311–362, 2004.
[13] M. Bayati and A. Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Trans. Inform. Theory, 57(2):764–785, 2011.
[14] G. Ben Arous, S. Mei, A. Montanari, and M. Nica. The landscape of the spiked tensor model.
ArXiv e-prints, 2017.
[15] F. Benaych-Georges and R. R. Nadakuditi. The eigenvalues and eigenvectors of finite, low rank
perturbations of large random matrices. Adv. Math., 227(1):494–521, 2011.
[16] A. Bovier, I. Kurkova, and M. Löwe. Fluctuations of the free energy in the REM and the p-spin
SK models. Ann. Probab., 30(2):605–651, 2002.
[17] M. Capitaine, C. Donati-Martin, and D. Féral. The largest eigenvalues of finite rank deformation
of large Wigner matrices: convergence and nonuniversality of the fluctuations. Ann. Probab.,
37(1):1–47, 2009.
[18] W.-K. Chen. Chaos in the mixed even-spin models. Comm. Math. Phys., 328(3):867–901, 2014.
[19] W.-K. Chen. Variational representations for the Parisi functional and the two-dimensional
Guerra-Talagrand bound. ArXiv e-prints, January 2015.
[20] Wei-Kuo Chen. On the mixed even-spin Sherrington-Kirkpatrick model with ferromagnetic
interaction. Ann. Inst. Henri Poincaré Probab. Stat., 50(1):63–83, 2014.
[21] Y. Deshpande, E. Abbe, and A. Montanari. Asymptotic mutual information for the balanced
binary stochastic block model. Inf. Inference, 6(2):125–170, 2017.
[22] Y. Deshpande and A. Montanari. Information-theoretically optimal sparse pca. IEEE Internation Symposium on Information Theory, pages 2197–2201, 2014.
[23] D. L. Donnoho, A. Maleki, and A. Montanari. Message-passing algorithms for compressed
sensing. Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009.
[24] D. L. Donnoho, A. Maleki, and A. Montanari. Message-passing algorithms for compressed
sensing: I. motivation and construction. IEEE Information Theory Workshop (ITW), pages
115–144, 2010.
39

[25] A. El Alaoui, F. Krzakala, and M. I. Jordan. Finite-size corrections and likelihood ratio fluctuations in the spiked wigner model. ArXiv e-prints, 2017.
[26] A. Jagannath and I. Tobasco. A dynamic programming approach to the Parisi functional. Proc.
Amer. Math. Soc., 144(7):3135–3150, 2016.
[27] A. Javanmard and A. Montanari. State evolution for general approximate message passing
algorithms, with applications to spatial coupling. Inf. Inference, 2(2):115–144, 2013.
[28] S. B. Korada and N. Macris. Exact solution of the gauge symmetric p-spin glass model on a
complete graph. J. Stat. Phys., 136(2):205–230, 2009.
[29] F. Krzakala, J. Xu, and L. Zdeborová. Mutual information in rank-one matrix estimation.
IEEE Information Theory Workshop (ITW), pages 71–75, 2016.
[30] T. Lesieur, L. Miolane, M. Lelarge, F. Krzakala, and L. Zdeborová. Statistical and computational phase transitions in spiked tensor estimation. IEEE 2017 International Symposium,
pages 511–515, 2017.
[31] Lelarge. M. and L. Miolane. Fundamental limits of symmetric low-rank matrix estimation.
Proceedings of the 2017 Conference on Learning Theory, PMLR 65.
[32] M. Mézard, G. Parisi, and M. A. Virasoro. Spin glass theory and beyond, volume 9 of World
Scientific Lecture Notes in Physics. World Scientific Publishing Co., Inc., Teaneck, NJ, 1987.
[33] L. Miolane. Fundamental limits of symmetric low-rank matrix estimation: the non-symmetric
case. ArXiv e-prints, 2017.
[34] A. Montanari, D. Reichman, and O. Zeitouni. On the limitation of spectral methods: from the
Gaussian hidden clique problem to rank one perturbations of Gaussian tensors. IEEE Trans.
Inform. Theory, 63(3):1572–1579, 2017.
[35] A. Montanari and E. Richard. A statistical model for tensor pca. Neural Information Processing
Systems, pages 2897–2905, 2014.
[36] A. Montanari and E. Richard. Non-negative principal component analysis: message passing
algorithms and sharp asymptotics. IEEE Trans. Inform. Theory, 62(3):1458–1484, 2016.
[37] A. Onatski, M. J. Moreira, and M. Hallin. Asymptotic power of sphericity tests for highdimensional data. Ann. Statist., 41(3):1204–1231, 2013.
[38] D. Panchenko. The Parisi ultrametricity conjecture. Ann. of Math. (2), 177(1):383–393, 2013.
[39] D. Panchenko. The Sherrington-Kirkpatrick model. Springer Monographs in Mathematics.
Springer, New York, 2013.
[40] D. Panchenko. The Parisi formula for mixed p-spin models. Ann. Probab., 42(3):946–958, 2014.
[41] D. Panchenko. The free energy in a multi-species Sherrington-Kirkpatrick model. Ann. Probab.,
43(6):3494–3513, 2015.
[42] D. Panchenko. Free energy in the mixed p-spin models with vector spins. ArXiv e-prints,
December 2015.
[43] S. Péché. The largest eigenvalue of small rank perturbations of Hermitian random matrices.
Probab. Theory Related Fields, 134(1):127–173, 2006.
40

[44] A. Perry, A. S. Wein, and A. Bandeira. Statistical limits of spiked tensor models. ArXiv e-prints,
2017.
[45] A. Perry, A. S. Wein, A. Bandeira, and A. Moitra. Optimality and sub-optimality of PCA for
spiked random matrices and synchronization. ArXiv e-prints, 2016.
[46] G. Reeves and H. D. Pfister. The replica-symmetric prediction for compressed sensing with
gaussian matrices is exact. ArXiv e-prints, 2016.
[47] R. T. Rockafellar. Convex analysis. Princeton Landmarks in Mathematics. Princeton University
Press, Princeton, NJ, 1997. Reprint of the 1970 original, Princeton Paperbacks.
[48] M. Talagrand. The Parisi formula. Ann. of Math. (2), 163(1):221–263, 2006.
[49] M. Talagrand. Mean field models for spin glasses. Volume I, volume 54 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results
in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics].
Springer-Verlag, Berlin, 2011. Basic examples.
[50] M. Talagrand. Mean field models for spin glasses. Volume II, volume 55 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results
in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics].
Springer, Heidelberg, 2011. Advanced replica-symmetry and low temperature.

41

