Chapter 3

The Sherrington-Kirkpatrick model at high temperature

The Hamiltonian of the Sherrington-Kirkpatrick model (SK) is given by

H_{N}(σ) = −\frac{1}{\sqrt{N}} ∑_{i<j} g_{ij}σ_{i}σ_{j}, (3.1)

where (g_{ij})_{i<j} are i.i.d. N (0, 1). Thus, given another configuration σ′ we have

(3.2)  E(H_{N}(σ)H_{N}(σ′)) = \frac{1}{N} ∑_{i<j} σ_{i}σ_{j}σ′_{i}σ′_{j}

= \frac{N}{2} (\frac{1}{N} ∑_{i≤N} σ_{i}σ′_{i})^{2} − \frac{1}{2},

and in particular

E(H_{N}^{2}(σ)) = \frac{N − 1}{2} . (3.3)

In (3.2) we see the first occurrence of

R(σ, σ′) = \frac{σ · σ′}{N} = \frac{1}{N} ∑_{i≤N} σ_{i}σ′_{i}, (3.4)

which is called the overlap of σ and σ′. The name is motivated by the relation

R(σ, σ′) = \frac{2}{N} card\{i ≤ N | σ_{i} = σ′_{i}\} − 1.

The overlaps will play a fundamental role in the sequel.

In this chapter we study the SK model for β < 1. This is basically simple, and comes as a natural second step after Derrida’s model. The reader should however keep in mind that many special features occur in this model, and that it definitely gives a false idea of our topic, as will start to be obvious in Chapter 5.

The SK model at inverse temperature β < 1 is well understood, in particular through the work of Comets and Neveu [C-N]. This pretty paper uses stochastic calculus. Unfortunately stochastic calculus has yet to demonstrate its use outside a few very special situations, so we will not talk about it (a good excuse for putting off one more time the task of learning something about it). We actually know how to prove some of the sharp results of [C-N] (central limit theorems) by other methods. These will be developed in Chapters 5 to 7, in situations that do not seem to be within the reach of stochastic calculus.

The really special feature of the present model is that

E(Z_{N}^{2}) ≤ K(β)(E Z_{N})^{2}, (3.5)

and proving this is our first goal. We first observe that, from (3.3)

E Z_{N} = 2^{N} exp \frac{β^{2}}{4} (N − 1). (3.6)

Lemma 3.1. If δ < 1 we have

2^{−N} ∑ exp \frac{δ}{2N} (∑_{i≤N} σ_{i})^{2} ≤ \frac{1}{\sqrt{1 − δ}} (3.7)

In (3.7), the sum is of course over σ ∈ Σ_{N}. This will not be mentioned anymore.

Proof. For all t,

(3.8) 2^{−N} ∑ exp t ∑_{i≤N} σ_{i} = (ch t)^{N} ≤ exp \frac{Nt^{2}}{2} ,

using the elementary inequality ch t ≤ exp \frac{t^{2}}{2} . Using (3.8) for t = g\sqrt{δ/N} where g is N (0, 1) and taking expectation yield (3.7). □

Comment. I learned this pretty argument in [C-N]. Of course, one can also deduce tail estimates from (3.8), from which weaker bounds than (3.7) follow that do not require this trick.

Lemma 3.2. If γ + β^{2} < 1 we have

(3.9)  E(∑ exp(−βH_{N}(σ) − βH_{N}(σ′)) exp \frac{γ}{2N} (σ · σ′)^{2})

≤ \frac{1}{\sqrt{1 − β^{2} − γ}} (E Z_{N})^{2}.

Of course here it is understood that the summation is over all values of σ, σ′.

Proof. Using (3.2), (3.3), we see that

E(H_{N}(σ) + H_{N}(σ′))^{2} = N − 2 + \frac{1}{N} (σ · σ′)^{2},

so that the left-hand side of (3.9) is at most equal to

exp \frac{β^{2}(N − 2)}{2} ∑ exp \frac{δ}{2N} (σ · σ′)^{2},

where δ = β^{2} + γ. Now, using (3.7), we have

∑ exp \frac{δ}{2N} (σ · σ′)^{2} = 2^{N} ∑ exp \frac{δ}{2N} (∑_{i≤N} σ_{i})^{2} ≤ \frac{2^{2N}}{\sqrt{1 − δ}} ,

which implies (3.9). □

If γ = 0 , (3.9) implies

E(Z_{N}^{2}) ≤ (1 − β^{2})^{−1/2}(E Z_{N})^{2}. (3.10)

Theorem 3.3 ([A-L-R]). If β < 1, we have

lim_{N→∞} p_{N}(β) = \frac{β^{2}}{4} + log 2 . (3.11)

Proof. Using Proposition 2.8 and (3.10) we see that

P(Z_{N} ≥ \frac{1}{2} E Z_{N}) ≥ \frac{1}{4}\sqrt{1 − β^{2}}, (3.12)

so that, using (3.6)

P(\frac{1}{N} log Z_{N} ≥ (\frac{β^{2}}{4} + log 2)\frac{N − 1}{N}) ≥ \frac{1}{4}\sqrt{1 − β^{2}}.

The end of the proof is then as in the proof of (2.22): by Proposition 2.2, we have

P(\frac{1}{N} log Z_{N} ≤ p_{N}(β) + \frac{uβ}{\sqrt{N}} ) ≥ 1 − exp(−u^{2}),

so that if exp(−u^{2}) < \sqrt{1 − β^{2}}/4 we have

p_{N}(β) ≥ \frac{β^{2}}{4} + log 2 − \frac{uβ}{\sqrt{N}} − \frac{K(β)}{N}.  □

We now prove a more sophisticated result.

Theorem 3.4. For each β < 1 there is a constant K(β) such that for each N, each u > 0,

(3.13) P(log Z_{N}(β) < N(\frac{β^{2}}{4} + log 2) − u) ≤ K(β) exp(−\frac{u^{2}}{K(β)}).

To understand this, we note that this really consists of two parts

(3.14)  |p_{N}(β) − \frac{β^{2}}{4} − log 2| ≤ \frac{K(β)}{N}
(3.15)  P(\frac{1}{N} log Z_{N}(β) ≤ p_{N}(β) − u) ≤ K(β) exp(−\frac{N^{2}u^{2}}{K(β)}).

Condition (3.15) gains a factor N in the exponent of the bound compared to Proposition 2.2. This is not a general phenomenon, but a very special feature of the present model. For this reason, Theorem 3.4 is not particularly important, but the proof is quite pretty. Before we start, we recall an essential notation, the bracket ⟨ · ⟩, that denotes average with respect to Gibbs’ measure

⟨f(σ)⟩ = ∫ f(σ) dG_{N}(σ) = \frac{1}{Z_{N}} ∑ f(σ) exp(−βH_{N}(σ)). (3.16)

A fundamental idea throughout the paper is that of replicas. This simply means that we will consider products of the probability space (Σ_{N}, G_{N}), where G_{N} corresponds to the same realization of the g_{ij}’s in each copy. Averages in a replica with respect to the corresponding power of G_{N} are also denoted by brackets, so that, for example,

⟨exp \frac{γ}{2N} (σ · σ′)^{2}⟩ = ∫∫ exp \frac{γ}{2N} (σ · σ′)^{2} dG_{N}(σ) dG_{N}(σ′)

= \frac{1}{Z_{N}^{2}} ∑ exp(−βH_{N}(σ) − βH_{N}(σ′) + \frac{γ}{2N} (σ · σ′)^{2}) (3.17)

and (3.9) means that

E(Z_{N}^{2}⟨exp \frac{γ}{2N} (σ · σ′)^{2}⟩) ≤ \frac{1}{\sqrt{1 − β^{2} − γ}} (E Z_{N})^{2}. (3.18)

Lemma 3.5. If β < 1 we have

P(Z_{N} ≥ \frac{1}{2} E Z_{N}, ⟨\frac{1}{N} (σ · σ′)^{2}⟩ ≤ K(β)) ≥ \frac{1}{K(β)}.

Comment. Here, as always, this means: “If β < 1, there exists a number K(β) depending upon β only such that … ”

Proof. Using (3.12), (3.18) for γ = \frac{1−β^{2}}{2} and Chebyshev inequality we see that

P(Z_{N} ≥ \frac{1}{2} E Z_{N}, Z_{N}^{2}⟨exp \frac{γ}{2N} (σ · σ′)^{2}⟩ ≤ K(β)(E Z_{N})^{2}) ≥ \frac{1}{K(β)}.

But since e^{x} ≥ x we have

\begin{matrix}Z_{N} ≥ \frac{1}{2} E Z_{N} \\ Z_{N}^{2}⟨exp \frac{γ}{2N} (σ · σ′)^{2}⟩ ≤ K(β)(E Z_{N})^{2} \end{matrix} \} ⟹ ⟨\frac{1}{N} (σ · σ′)^{2}⟩ ≤ K(β).

□

The proof of Theorem 3.4 will use a simple algebraic fact that is not so intuitive. This (and similar facts) will play a fundamental role, so it is better brought to light now.

Lemma 3.6. We have

⟨(σ · σ′)^{2}⟩ = ∑_{i,j}⟨σ_{i}σ_{j}⟩^{2} (3.19)

Proof. We write

σ · σ′ = ∑_{i≤N} σ_{i}σ′_{i},

so

(σ · σ′)^{2} = ∑_{i,j≤N} σ_{i}σ′_{i}σ_{j}σ′_{j} = ∑_{i,j≤N} σ_{i}σ_{j}σ′_{i}σ′_{j}.

Now

⟨σ_{i}σ_{j}σ′_{i}σ′_{j}⟩ = ⟨σ_{i}σ_{j}⟩^{2} (3.20)

because the bracket on the left deals with a product measure on G_{N}^{2}, with respect to which σ and σ′ are independent r.v. □

Comment. A very useful function of replica is that they transform products of integrals into integrals, such as in the formula

⟨f(σ)⟩⟨f′(σ)⟩ = ⟨f(σ)f′(σ′)⟩

which simply means that

∫ f(σ) dG_{N}(σ) ∫ f′(σ) dG_{N}(σ) = ∫∫ f(σ)f′(σ′) dG_{N}(σ) dG_{N}(σ′).

Proof of Theorem 3.4. It relies upon Proposition 2.1. To apply (2.8), it is convenient to reformulate Lemma 3.5 as follows. The subset B of ℝ^{M} (for M = \frac{N(N−1)}{2}) such that

(g_{ij}) ∈ B ⟺ \begin{cases}Z_{N} ≥ \frac{1}{2}EZ_{N}(β); \\ ⟨(σ · σ′)^{2}⟩ ≤ K(β)N \end{cases} (3.21)

satisfies

P((g_{ij}) ∈ B) ≥ \frac{1}{K(β)}. (3.22)

It is of course implicit here that the (g_{ij}) on the left are those used to define Z_{N} and Gibbs’ measure on the right. We apply (2.8) to the function

F (x) = d(x, B) = inf_{y∈B} d(x, y),

the Euclidean distance from x to B in ℝ^{M}. There, of course

d^{2}(x, y) = ∑_{i<j}(x_{ij} − y_{ij})^{2}. (3.23)

Thus, by (2.8), we have

P(|d(g, B) − E d(g, B)| ≥ u) ≤ exp(−\frac{u^{2}}{2} ). (3.24)

In particular, if u < E d(g, B), we have

\frac{1}{K(β)} ≤ P(g ∈ B) ≤ P(|d(g, B) − E d(g, B)| ≥ u) ≤ exp(−\frac{u^{2}}{2} ),

so that u ≤ K(β) and thus E d(g, B) ≤ K(β). It then follows from (3.24) that for u ≥ 0

P(d(g, B) ≥ u + K(β)) ≤ exp(−\frac{u^{2}}{2} ). (3.25)

To prove (3.13), it suffices to combine (3.25) with the following

log Z_{N}(g) ≥ N(\frac{β^{2}}{4} + log 2) − K(β)(d(g, B) + 1) (3.26)

where Z_{N}(g) means of course that Z_{N} corresponds to the choice g = (g_{ij}) of the r.v. Indeed, if (3.26) holds, and if

log Z_{N}(g) ≤ N(\frac{β^{2}}{4} + log 2) − u,

then d(g, B) ≥ \frac{u−K(β)}{K(β)}. Using (3.25) this is an event of probability at most

exp(−(min\{0, \frac{u − K(β)}{K(β)}\})^{2}) ≤ K(β) exp(−\frac{u^{2}}{K(β)}).

To prove (3.26), since log Z_{N}(g′) ≥ (N −1)(\frac{β^{2}}{4} +log 2) for g′ in B, it suffices to prove that if g ∈ ℝ^{M} we have

log Z_{N}(g) ≥ log Z_{N}(g′) − K(β)d(g, g′) (3.27)

where d is given by (3.23). We start with the algebraic identity

Z_{N}(g) = Z_{N}(g′)⟨exp −\frac{β}{\sqrt{N}} ∑_{i<j}(g_{ij} − g′_{ij})σ_{i}σ_{j}⟩′ (3.28)

where ⟨ · ⟩′ means that Gibbs’ measure is computed for g′_{ij}. Using successively Jensen’s inequality and Cauchy-Schwarz, we get

Z_{N}(g) ≥ Z_{N}(g′) exp(−\frac{β}{\sqrt{N}} ∑_{i<j}(g_{ij} − g′_{ij})⟨σ_{i}σ_{j}⟩′)

≥ Z_{N}(g′) exp(−\frac{β}{\sqrt{N}} d(g, g′) (∑_{i<j}⟨σ_{i}σ_{j}⟩′^{2})^{1/2}).

Using (3.19), and the fact that ⟨(σ · σ′)^{2}⟩′ ≤ NK(β) by (3.22) we have proved (3.27). □

Theorem 3.7. If β < 1, there exists K(β) < ∞ such that

E⟨exp \frac{1 − β^{2}}{8N} (σ · σ′)^{2}⟩ ≤ K(β). (3.29)

This implies a very good control of the overlap of two configurations σ, σ′, when the overlap is viewed as a function on Σ_{N}^{2}, provided with G_{N}^{⊗2}, or, if one prefers, when σ, σ′ are weighted according to their Gibbs weights. It will gradually become apparent that this type of information is of considerable importance. We will have to work very hard later to prove the extensions of (3.29) to other situations.

Proof of Theorem 3.7. Using Cauchy-Schwarz for ⟨ · ⟩ we have

⟨exp \frac{1 − β^{2}}{8N} (σ · σ′)^{2}⟩ ≤ ⟨exp \frac{1 − β^{2}}{4N} (σ · σ′)^{2}⟩^{1/2}.

Now

E⟨exp \frac{1 − β^{2}}{4N} (σ · σ′)^{2}⟩^{1/2} = E(\frac{1}{Z_{N}} (Z_{N}^{2}⟨exp \frac{1 − β^{2}}{4N} (σ · σ′)^{2}⟩)^{1/2})

≤ K(β)(E \frac{1}{Z_{N}^{2}} )^{1/2} E Z_{N},

using again Cauchy-Schwarz and (3.9) for γ = \frac{1−β^{2}}{2} . But (3.13) implies that for u > 1

P(\frac{(E Z_{N})^{2}}{Z_{N}^{2}} > u) ≤ K(β) exp(−\frac{(log u)^{2}}{K(β)} ),

so that

E(\frac{E Z_{N}}{Z_{N}} )^{2} ≤ K(β).

□

Theorem 3.7 has applications to a statement of the same nature as Proposition 2.9, but with card I about \sqrt{N}. We refer the reader to [T2] for this.

What about the global structure of G_{N} ? We will show that, in a strong sense, G_{N} is very far from the uniform measure μ on Σ_{N}. Let us denote by d the Hamming distance on Σ_{N}, given by

d(σ, σ′) = card\{i ≤ N | σ_{i} ≠ σ′_{i}\} = \frac{N − σ · σ′}{2} . (3.30)

Proposition 3.8. If β > 0, with overwhelming probability one can find two sets A, B ⊂ Σ_{N} with

\begin{cases}G_{N}(A) ≥ \frac{2}{3}; \\ μ(B) ≥ \frac{2}{3}; \\ d(A, B) ≥ \frac{N}{L} min(1, β^{2}). \end{cases} (3.31)

In this statement, as through these notes “with overwhelming probability” means that the probability of failure is ≤ exp(−N/K). A consequence of (3.31) is that “the transportation cost of G_{N} to μ is of order N”. (Don’t worry if you don’t know what this is.)

Proof of Proposition 3.8. We set β′ = min(1, β). We define

A = \{σ | −H_{N}(σ) ≥ \frac{Nβ′}{3} \}
B = \{σ | −H_{N}(σ) ≤ \frac{Nβ′}{4} \},

and we prove that A, B satisfy (3.31). To prove that G_{N}(A) ≥ 2/3 and in fact G_{N}(A) ≥ 1 − exp(−N/K) with overwhelming probability, we use Lemma 2.7, Proposition 2.2, Theorem 3.3 (and the convexity of p_{N} if β ≥ 1) to bound G_{N}(A^{c}). To prove that μ(B) ≥ 2/3 (and in fact μ(B) ≥ 1 − exp(−N/K)) with overwhelming probability, we will use Fubini Theorem. If we define

Ω(σ) = \{H_{N}(σ) ≥ \frac{Nβ′}{4} \},

then

E(∑ 1_{Ω(σ)}) = ∑ P(Ω(σ)) ≤ 2^{N} exp(−\frac{Nβ′^{2}}{16} ),

so that

P(2^{−N} ∑ 1_{Ω(σ)} ≥ exp(−\frac{Nβ′^{2}}{32} )) ≤ exp(−\frac{Nβ′^{2}}{32} ).

To prove that d(A, B) ≥ \frac{N}{K} with overwhelming probability, we observe that if σ ∈ A, σ′ ∈ B then

H_{N}(σ′) − H_{N}(σ) ≥ \frac{Nβ′}{12} . (3.32)

Now, using (3.2), (3.3), we have

E(H_{N}(σ′) − H_{N}(σ))^{2} = N(1 − (\frac{σ · σ′}{N} )^{2})

= N(1 − (1 − \frac{2d(σ, σ′)}{N})^{2})

≤ 4d(σ, σ′),

where we have used (3.30) in the last line. Thus

P(H_{N}(σ′) − H_{N}(σ) ≥ \frac{Nβ′}{12} ) ≤ exp(−\frac{N^{2}β′^{2}}{L d(σ, σ′)}).

This shows that if Nβ^{′2} > LD, with overwhelming probability there exist no pairs (σ, σ′) with d(σ, σ′) < D that satisfy (3.32). □

Definition 3.9. A probability measure G on Σ_{N} is ϑ-shattered if we can find two sets A, B ⊂ Σ_{N} such that

\begin{cases}G(A) ≥ \frac{1}{3}, \\ G(B) ≥ \frac{1}{3}, \\ d(A, B) ≥ ϑN. \end{cases} (3.33)

The idea there is that a ϑ-shattered probability utterly fails concentration of measure. It is better understood if one knows the following important result: nice probability measures on Σ_{N} (such as product measures) satisfy

\begin{matrix}ν(A) ≥ \frac{1}{3} \\ ν(B) ≥ \frac{1}{3} \end{matrix}\} ⟹ d(A, B) ≤ L\sqrt{N}.

Conjecture 3.10. If β > 0, there is ϑ(β) > 0 such that with overwhelming probability, G_{N} is ϑ-shattered.

Even though a physicist would probably consider this question as esoteric and far fetched, it seems that it possibly touches some central issues. If true, Conjecture 3.10 would mean that we can find two pieces A, B of the configuration space, that are well separated for d, and that both carry some mass. Moreover, such pieces would depend essentially upon the randomness. Certain central low temperature predictions of the physicists can be expressed with roughly the same words. It is conceivable that proving or disproving Conjecture 3.10 is really difficult.

Challenge problem 3.11. Construct a random probability measure ν on Σ_{N} that is ϑ-shattered for some ϑ > 0 but satisfies

E ∫∫ exp(\frac{1}{NL}(σ · σ′)^{2}) dν(σ) dν(σ′) < L.

The difference between an open problem and a challenge problem is that I have no clue about the former but that I know (or at least, I thought at some point I would know if I really tried) how to do the later.

Challenge problem 3.12. Prove that if β > 0, there exists ϑ = ϑ(β) such that the Gibbs’ measure associated to Derrida’s REM (Chapter 2) is ϑ-shattered with overwhelming probability.

What happens if β > 1? It is known that Theorem 3.3 fails, as is shown by the following

Theorem 3.13 ([C, K-T-J]). If β > 1, then

(3.34)  lim sup_{N→∞} p_{N}(β) ≤ log 2 + β − \frac{3}{4} − \frac{1}{2} log β.

Let us explain the basic idea. The starting point is that the joint law of a jointly Gaussian family of r.v. is determined by its covariance structure. Consider now independent N (0, 1) r.v. (g_{i})_{i≤N} (independent of the g_{ij}) and for x ∈ ℝ^{N} consider

H′_{N}(x) = −\frac{1}{\sqrt{N}} ∑_{i<j} g_{ij}x_{i}x_{j} + \frac{1}{\sqrt{2}} ∑_{i≤N} g_{i}x_{i}^{2}. (3.35)

An immediate computation shows that

E H′_{N}(x)H′_{N}(y) = \frac{1}{2N} (x · y)^{2}.

Thus, given any linear isometry R of ℝ^{N} the joint law of the family (H′_{N}(R(σ))) for σ in Σ_{N} is independent of R (since R(x) · R(y) = x · y) and thus

E \frac{1}{N} log ∑ ; σ exp(−βH′_{N}(R(σ))) (3.36)

is independent of R. It is in particular equal to its value when R = Id. In that case

H′_{N}(σ) = −\frac{1}{\sqrt{N}} ∑_{i<j} g_{ij}σ_{i}σ_{j} + \frac{1}{\sqrt{2}} ∑_{i} g_{i}.

The term ∑_{i} g_{i} is independent of σ. We can take it through the log and it gives no contribution. Thus, for each R,

p_{N}(β) = E \frac{1}{N} log ∑ ; σ exp(−βH′_{N}(R(σ))). (3.37)

Let us denote by dR the Haar (= uniform) measure on the set of all rotations of ℝ^{N}. We integrate (3.36) with respect to dR, and use Jensen’s inequality to put the integral inside the log. We observe that

∫ ∑ ; σ exp(−βH′_{N}(R(σ)) dR = 2^{N} ∫_{S_{N}} exp(−βH′_{N}(x)) dμ_{N}(x)

where μ_{N} is the uniform measure on S_{N} = {x ∈ ℝ^{N} | x_{1}^{2} + ⋯ + x_{N}^{2} = N}. Thus we have

(3.38) p_{n}(β) ≤ log 2 + E \frac{1}{N} log ∫_{S_{N}} exp(−βH′_{N}(x)) dμ_{N}(x).

(“Domination of the Ising model by the spherical model” in jargon.) The reason why the last term is easier to compute than p_{N}(β) is that it has more symmetries. We can compute the integral in whatever basis we choose. The result depends only upon the eigenvalues of the matrix (g′_{ij})_{i,j≤N} given by

\begin{cases}g′_{ij} = \frac{1}{2}g_{ij} & if i < j \\ g′_{ij} = \frac{1}{2}g_{ji} & if i > j \\ g′_{ii} = \frac{1}{\sqrt{2}}g_{i}. \end{cases}

These are well understood through a famous theorem of Wigner. They are (in a precise sense) essentially independent upon the realization of the (g′_{ij}), and follow “Wigner semi circle law”. This allows to bound in the limit the right-hand side of (3.38) by the right-hand side of (3.34). We will refer the reader to [C] for this pretty computation, because the entire approach we are following here is somewhat unsatisfactory. Conditioning upon the eigenvalues of the matrix (g′_{ij}) is possibly not the right idea. Moreover, while Wigner’s theorem is basically not difficult, it relies upon the very special structure of matrices (that can be multiplied), and it is unclear how to extend it, say to the situation of the next chapter.

What really happens for β > 1 ? The physicists have proposed an entire theory, of great complexity. It seems so much out of reach of the current rigorous methods that there is no point to even discuss it.

30 3. The Sherrington-Kirkpatrick model at high temperature Challenge problem 3.14. Consider the Hamiltonian H_{N}^{REM}(σ) of the REM and the Hamiltonian H_{N}^{SK}(σ) of (3.1). Assume these are independent. Find the exact region of parameters β_{1}, β_{2} for which

lim_{N→∞} \frac{1}{N} E log ∑ ; σ exp(−β_{1}H_{N}^{REM}(σ) − β_{2}H_{N}^{SK}(σ)) = log 2 + \frac{1}{4} (β_{1}^{2} + β_{2}^{2}).