Chapter 6

Exponential inequalities

In the previous chapter, we have shown that for the SK-model, if β ≤ \frac{1}{3} we have

lim_{N→∞} E⟨(R(σ, σ′) − q)^{2}⟩ = 0. (6.1)

We will prove here considerably more accurate results in the same direction, namely the following.

Theorem 6.1. There exists a number L and a number β_{0} such that if β ≤ β_{0}, and h ≤ 1, then

E⟨exp \frac{N}{L} (R(σ, σ′) − q)^{2}⟩ ≤ L. (6.2)

Besides the fact that such an inequality is obviously a notable improvement on (6.1), it is also motivated by its possible relevance to the important open problem that will be discussed in the next chapter. The restriction h ≤ 1 is not really needed. We impose it to avoid secondary complications. It can be removed with a few extra lines of work. In fact, large values of h improve the situation: one can show that (6.2) holds for β ≤ β(h) with β(h) → ∞ as h → ∞.

An exponential integrability condition such as (6.2) amounts to a uniform control of moments. We will prove the following

Proposition 6.2. There exists a number β_{0} with the following property. Set A = 192. If β ≤ β_{0}, h ≤ 1 then for each k, N we have

E⟨(σ^{1} · σ^{2} − Nq)^{2k}⟩ ≤ A^{k}N^{k}k! (6.3)

Using that

e^{x^{2}} = ∑_{k≥0} \frac{x^{2k}}{k!} ,

we see that (6.3) implies (6.2). (These are in fact essentially equivalent).

An important observation before the proof starts is that to prove (6.3) we can assume N ≥ k. Indeed, since |σ^{1} · σ^{2} − Nq| ≤ 2N, the left-hand side of (6.3) is at most 4^{k}N^{2k}, so (6.3) holds provided

4^{k}N^{k} ≤ A^{k}k!

so that if N ≤ k, to prove (6.2) it suffices to see that k^{k} ≤ e^{k}k! This is a weak version of Stirling’s formula which is very easy to prove by induction upon k.

To prove (6.3) we will proceed by double induction. Let us denote by H(N, k) the validity of (6.3), so that H(N, 0) is valid for all N. We will prove by induction over k that H(N, k) is valid for all N. For a given k, we will prove the validity of H(N, k) by induction over N.

Let us write

U_{N,k}(β) = E⟨(σ^{1} · σ^{2} − Nq)^{2k}⟩. (6.4)

To prove Proposition 6.2, it suffices to prove the following

Proposition 6.3. If β′ ≤ β_{0} and if

∀l ≤ k U_{N,l}(β) ≤ A^{l}N^{l}l!, (6.5)

then

U_{N+1,k}(β′) ≤ A^{k}(N + 1)^{k}k! (6.6)

Here, as elsewhere in this Chapter, β and β′, q and q′ as well as ⟨ · ⟩ and ⟨ · ⟩′ are related as in Chapter 5.

Lemma 6.4. If β ≤ β_{0}, we have

(N + 1)|q − q′| ≤ 1

Proof. We write as Ψ(x, β) the quantity (5.57). Thus if q = Ψ(q, β), then

\frac{dq}{dβ} = \frac{\frac{∂Ψ}{∂β}(q, β)}{1 − \frac{∂Ψ}{∂q}(q, β)}.

Now ∂Ψ/∂β = 2q/β ∂Ψ/∂q, and the result follows from Lemma 5.10 and the fact that |β′ − β| ≤ β/2N. □

Let us start the proof of Proposition 6.3. (The reader is suggested to assume k = 1 at first reading). To simplify notation, we write

V = σ^{1} · σ^{2} − Nq, v_{N+1} = σ_{N+1}^{1}σ_{N+1}^{2} − q, δ = (N + 1)(q − q′).

We have

(6.7)  U_{N+1,k}(β′) = E⟨(σ^{1} · σ^{2} + σ_{N+1}^{1}σ_{N+1}^{2} − (N + 1)q′)^{2k}⟩′

= E⟨(V + v_{N+1} + δ)^{2k}⟩′

= ∑_{0≤l≤2k} \binom{2k}{l}δ^{l} E⟨(V + v_{N+1})^{2k−l}⟩′

≤ ∑_{0≤l≤2k} \binom{2k}{l}W^{\frac{2k−l}{2k}}

= (1 + W^{\frac{1}{2k}})^{2k}

where

W = E⟨(V + v_{N+1})^{2k}⟩′, (6.8)

and where we have used Lemma 6.4 and Hölder’s inequality in the fourth line. To prove (6.6), it suffices to prove that

W ≤ \frac{1}{2}(N + 1)^{k}A^{k}k! (6.9)

Indeed, by (6.7), we have

(6.10)  U_{N+1,k}(β′) ≤ (1 + W^{\frac{1}{2k}})^{2k} ≤ (1 + (\frac{1}{2}(N + 1)^{k}A^{k}k!)^{\frac{1}{2k}} )^{2k}

≤ \frac{1}{2}(N + 1)^{k}A^{k}k! exp(\frac{2k}{(\frac{1}{2}(N + 1)^{k}A^{k}k!)^{\frac{1}{2k}}} )

since, for x > 0,

(1 + x)^{2k} = x^{2k}(1 + \frac{1}{x})^{2k} ≤ x^{2k} exp(\frac{2k}{x}).

Now, N + 1 ≥ kandA^{k}k! ≥ 4^{2k+1}k^{k}, so that

(\frac{1}{2}(N + 1)^{k}A^{k}k!)^{\frac{1}{2k}} ≥ 4k

and (6.10) implies (6.6).

We turn to the proof of (6.9). Using symmetry between sites, we get

W ≤ (N + 1) E⟨v_{N+1}(V + v_{N+1})^{2k−1}⟩′. (6.11)

Of course in the bracket, average is integration of ϱ^{l} = (σ_{1}^{l}, …, σ_{N}^{l}, σ_{N+1}^{l}) (l ≤ 2) in G_{N+1}. We write

(V + v_{N+1})^{2k−1} = ∑_{0≤l≤2k−1} \binom{2k − 1}{l}V^{2k−1−l}v_{N+1}^{l}.

The most important term is for l = 0. For l ≥ 1, we bound |v_{N+1}|^{l+1} by 2^{l+1}, and we obtain from (6.11) that

W ≤ (N + 1) E⟨v_{N+1}V^{2k−1}⟩′ + S (6.12)

where

S = (N + 1) ∑_{1≤l≤2k−1} \binom{2k − 1}{l}2^{l+1} E⟨|V |^{2k−1−l}⟩′. (6.13)

We first perform the easy task, the control of S.

Lemma 6.5. If N + 1 ≥ k, we have

S ≤ \frac{1}{4}(N + 1)^{k}A^{k}k! (6.14)

Proof. We use (5.22), and the fact that Z ≥ 1 to get

E⟨|V |^{2k−1−l}⟩′ ≤ E⟨Av|V |^{2k−1−l}E_{2}⟩
≤ exp(2β^{2} + 2h) E⟨|V |^{2k−1−l}⟩,

by integrating first in g = (g_{i})_{i≤N}.

Next, we use Hölder’s inequality,

E⟨|V |^{2k−l−1}⟩ ≤ (E⟨V^{2k−2}⟩)^{\frac{2k−1−l}{2k−2}}
= (U_{N,k−1}(β))^{\frac{2k−l−1}{2k−2}} .

We use the trivial bound

\binom{2k − 1}{l} ≤ 2k(2(k − 1))^{l−1},

to obtain from (6.13) that

S ≤ 8k(N + 1) exp(2β^{2} + 2h) ∑_{1≤l≤2k−1}(4(k − 1))^{l−1}(U_{N,k−1}(β))^{\frac{2k−l−1}{2k−2}} . (6.15)

Now, we use that p^{p} ≤ 3^{p}p! for p = k − 1 to see that, since we assume N ≥ k − 1, we have

8^{2(k−1)}(k − 1)^{2(k−1)} ≤ A^{k−1}N^{k−1}(k − 1)!,

so that

(4(k − 1))^{l−1} ≤ 2^{1−l}(A^{k−1}N^{k−1}(k − 1)!)^{\frac{l−1}{2k−2}} . (6.16)

Next we use (6.5) to see that

U_{N,k−1}(β) ≤ A^{k−1}N^{k−1}(k − 1)! . (6.17)

and substitution of (6.16), (6.17) in (6.15) gives

S ≤ 16k(N + 1) exp(2β^{2} + 2h)A^{k−1}N^{k−1}(k − 1)!

≤ (\frac{16}{A} exp(2β^{2} + 2h))(N + 1)^{k}A^{k}k!

But since β ≤ \frac{1}{3}, h ≤ 1, we have \frac{16}{A} exp(2β^{2} + 2h) ≤ \frac{1}{4}. □

Now we turn to the main issue, the study of E⟨v_{N+1}V^{2k−1}⟩′. We use (5.22) to get

E⟨v_{N+1}V^{2k−1}⟩′ = E \frac{1}{Z^{2}} ⟨V^{2k−1} Av(ε_{1}ε_{2} − q)E_{2}⟩, (6.18)

where

E_{2} = exp ∑_{l≤2} ε_{l}(\frac{β}{\sqrt{N}} g · σ^{l} + h),

Z = ⟨Av exp ε(\frac{β}{\sqrt{N}} g · σ + h)⟩.

To study (6.18), we will use the following principle.

Proposition 6.6. There exists a number L with the following property. Consider a function f : Σ_{N}^{2} → ℝ and p, p′ with 1/p + 1/p′ = 1. Consider q in [0, 1]. Then if β ≤ 1, h ≤ 1, and if J is a subset of {1, 2} we have

(6.19) |E \frac{1}{Z^{2}} ⟨f Av ∏_{l∈J} ε_{l}E_{2}⟩ − E th^{m}(Y) E⟨f⟩|

≤ β^{2}L(E⟨|f|^{p}⟩)^{\frac{1}{p}} (E⟨|R(σ^{1}, σ^{2}) − q|^{p′}⟩)^{\frac{1}{p′}} ,

where Y = βg\sqrt{q} + h, and where g is N(0, 1).

The ideas behind Proposition 6.6 are of fundamental importance, so we delay their discussion until after the proof of Theorem 6.1.

We will use (6.19) when q is given by (5.4). This simply means that q = E th^{2} Y. We apply (6.19) to f = V^{2k−1}, p = 2k/(2k − 1), p′ = 2k, and for two choices of J : J = {1, 2} and J = ∅. Since

|f|^{p} = N^{2k}|R(σ^{1}, σ^{2}) − q|^{2k} = |V |^{2k},

we get

(6.20)  E⟨v_{N+1}V^{2k−1}⟩′ ≤ \frac{Lβ^{2}}{N} U_{N,k}(β)
≤ Lβ^{2}N^{k−1}A^{k}k!,

using (6.5). Going back to (6.12), and using (6.4), we get

W ≤ (N + 1)^{k}A^{k}k!(\frac{1}{4} + Lβ^{2})

and this proves (6.9) if Lβ^{2} ≤ 1/4. This proves Proposition 6.2 and hence Theorem 6.1.

We now turn to the proof of Proposition 6.6. Even though it will require some abstraction to see it, the true nature of the problem we face is as follows. Consider two centered jointly Gaussian families (u_{i})_{i≤n}, (v_{i})_{i≤n} and a smooth function F on ℝ^{n}. How do we compare

E F (u_{1}, …, u_{n}) and E F (v_{1}, …, v_{n})?

The circle of ideas we will use to do this will be referred to as Kahane’s principle (in honor of [K]). As in all great mathematics, the starting point is almost absurdly simple. It is to find a smooth path w(t) from the family u to the family v so that w(0) = u, w(1) = v, and to write

E F (v) − E F (u) = ∫_{0}^{1} θ′(t) dt, (6.21)

where θ(t) = E F (w(t)). The basic tool for computation of θ′(t) is integration by parts, and we first state the form we need.

Proposition 6.7. Consider a (centered) jointly Gaussian family u, u_{1}, …, u_{n} of r.v. Then

E uF (u_{1}, …, u_{n}) = ∑_{i≤n} E(uu_{i}) E \frac{∂F}{∂x_{i}} (u_{1}, …, u_{n}). (6.22)

Proof. This is an application of (5.56). We write

u′_{i} = u_{i} − \frac{E(uu_{i})}{E u^{2}}u

so that E(u′_{i}u) = 0. The family (u′_{i})_{i≤n} is independent of u. Setting c_{i} = E(uu_{i})/ E(u^{2}), we write

E uF (u_{1}, …, u_{n}) = E uF (u′_{1} + c_{1}u_{,} …, u′_{n} + c_{n}u)

and we use (5.56) at (u′_{i}) fixed. □

Here is a particularly elegant formulation.

Proposition 6.8. Consider two centered jointly Gaussian families of r.v. u = (u_{i})_{i≤n}, v = (v_{i})_{i≤n}. We assume that these families are independent of each other (but we do not assume that (u_{i})_{i≤n} or (v_{i})_{i≤n} are independent). For 0 ≤ t ≤ 1 consider

θ(t) = E F (\sqrt{1 − t} u + \sqrt{t} v). (6.23)

Then for 0 < t < 1 we have

θ′(t) = \frac{1}{2} ∑_{i,j}(E(v_{i}v_{j}) − E(u_{i}u_{j})) E \frac{∂^{2}F}{∂x_{i}∂x_{j}} (\sqrt{1 − t} u + \sqrt{t} v). (6.24)

Proof. We have

θ′(t) = \frac{1}{2} E ∑_{i≤n}(\frac{1}{\sqrt{t}} v_{i} − \frac{1}{\sqrt{1 − t}} u_{i})\frac{∂F}{∂x_{i}} (\sqrt{1 − t} u + \sqrt{t} v).

By independence of u, v, we have

E((\frac{1}{\sqrt{t}} v_{i} − \frac{1}{\sqrt{1 − t}} u_{i})(\sqrt{1 − t} u_{j} + \sqrt{t} v_{j})) = E(v_{i}v_{j} − u_{i}u_{j}),

so that the result follows from Proposition 6.7. □

The way Kahane uses this is that if

∀i, j E(v_{i}v_{j}) ≥ E(u_{i}v_{j}) and \frac{∂^{2}F}{∂x_{i}∂x_{j}} ≥ 0,

then E F (v) ≥ E F (u). (Slepian’s Lemma)

Proof of Proposition 6.6. For further purposes, we will consider a more general setting, namely replicas of order s rather than 2 and we will try to approximate

(6.25) E \frac{⟨f Av ε_{J}E_{s}⟩}{Z^{s}} = E \frac{⟨f Av ε_{J}E_{s}⟩}{⟨Av E_{s}⟩}

where J ⊂ {1, …, s} and ε_{J} = ∏_{l∈J} ε_{l}. We will work conditionally upon Gibbs’ measure on Σ_{N}, that is, we integrate first in g. Rather than Gibbs’ measure, it turns out to be very convenient to consider points (σ(j))_{j≤M} in Σ_{N} and the probability μ that gives mass 1/M to each σ(j), i.e. μ = M^{−1} ∑_{j≤M} δ_{σ(j)}. The points σ(j) are not assumed to be distinct. Fixing N, we will take M → ∞ to approximate Gibbs’ measure. Thus, we want to understand

(6.26) E_{g} \frac{∑ f Av ε_{J} exp ∑_{l≤s} ε_{l}(\frac{β}{\sqrt{N}} g · σ(j_{l}) + h)}{∑ Av exp ∑_{l≤s} ε_{l}(\frac{β}{\sqrt{N}} g · σ(j_{l}) + h)}.

Here

f = f(σ(j_{1}), …, σ(j_{s})), (6.27) and the sum ∑ are over all possible choices j_{1}, …, j_{s} ≤ M. It turns out to be very useful to think to the quantities g · σ(j_{l}) as Ms different variables (s for l ≤ s, M for the M possible values of j). That is, we consider x = (x(j, l))_{j≤M,l≤s} and we consider

(6.28)  F_{1}(x) = ∑_{j_{1},...,j_{s}} f Av ε_{J} exp(∑_{l≤s} ε_{l}(βx(j_{l}, l) + h))
(6.29)  F_{2}(x) = ∑_{j_{1},...,j_{s}} Av exp(∑_{l≤s} ε_{l}(βx(j_{l}, l) + h)),

where f is as in (6.27) and the summation is over all possible values of j_{1}, …, j_{s}. We set

F (x) = \frac{F_{1}(x)}{F_{2}(x)}. (6.30)

We consider the Gaussian family

v = (v(j, l))_{j≤M,l≤s}

where

v(j, l) = \frac{1}{\sqrt{N}} g · σ(j),

so that (6.26) is E_{g} F (v).

We consider now independent Gaussian variables u, w(j, l) such that E u^{2} = q (6.31) E w^{2}(j, l) = 1 − q. (6.32) We set u(j, l) = u + w(j, l). (6.33) Thus, if (j, l) ≠ (j′, l′), we have E u(j, l)u(j′, l′) = q. (6.34) The idea of considering u is as follows. We have M^{−s}F_{1}(u) (6.35)

= M^{−s} Av(ε_{J} exp(∑_{l≤s} ε_{l}(βu + h)) ∑ f exp(∑_{l≤s} βε_{l}w(j_{l}, l))).

Now, the variables w(j_{l}, l) are all independent, so by a trivial computation

E|M^{−s} ∑ f exp ∑_{l≤s} βε_{l}w(j_{l}, l) − M^{−s} ∑ f exp \frac{β^{2}}{2} s(1 − q)|^{2} ≤ \frac{K}{M} , (6.36)

where K depends upon f, β, s but not upon M. Proceeding as in (6.35) for F_{2}(u), we see that

(6.37) lim E_{g} \frac{F_{1}(u)}{F_{2}(u)} = ⟨f(σ^{1}, …, σ^{s})⟩ E_{g} \frac{Av ∏_{l∈J} ε_{l} exp ∑_{l≤s} ε_{l}(βu + h)}{Av exp ∑_{l≤s} ε_{l}(βu + h)}
= E_{g}(th(βu + h))^{card J}⟨f(σ^{1}, …, σ^{s})⟩.

In (6.37), the limit is taken as M → ∞ and as ν = M^{−1} ∑_{j≤M} δ_{σ(j)} converges to Gibbs’ measure. The reader has by now certainly understood that the purpose of introducing ν rather than working with Gibbs’ measure is not to use equal weights (this makes little difference) but to consider the atoms of Gibbs’ measure as made up from many different small pieces in order to use (6.37) as M → ∞. We consider

θ(t) = E_{g} F (\sqrt{1 − t} u + \sqrt{t} v)

so that

E_{g} F (v) − E_{g} F (u) = θ(1) − θ(0) = ∫_{0}^{1} θ′(t) dt, (6.38)

and we compute θ′(t) through Proposition 6.8

Lemma 6.9. We have

(6.39)  θ′(t) = ∑_{1≤l_{1}<l_{2}≤s} E_{g} F_{l_{1},l_{2}}^{1}(\sqrt{1 − t} u + \sqrt{t} v)

− ∑_{1≤l_{1}<l_{2}≤s} E_{g} F_{l_{1},l_{2}}^{2}(\sqrt{1 − t} u + \sqrt{t} v)

− ∑_{1≤l_{1},l_{2}≤s} E_{g} F_{l_{1},l_{2}}^{3}(\sqrt{1 − t} u + \sqrt{t} v)

+ ∑_{1≤l_{1},l_{2}≤s} E_{g} F_{l_{1},l_{2}}^{4}(\sqrt{1 − t} u + \sqrt{t} v),

where the functions F_{l_{1},l_{2}}^{r}, r = 1, 2, 3, 4 are defined as follows:

F_{l_{1},l_{2}}^{1}(x) = \frac{β^{2}}{F_{2}(x)} ∑_{j_{1},...,j_{s}} fA_{l_{1},l_{2}} Av ε_{l_{1}}ε_{l_{2}}ε_{J}E(x) (6.40)

for

\begin{matrix}E(x) = exp ∑_{l≤s} ε_{l}(βx(j_{l}, l) + h) ; \\ A_{l_{1},l_{2}} = \frac{σ(j_{l_{1}}) · σ(j_{l_{2}})}{N} − q \end{matrix} (6.41)

F_{l_{1},l_{2}}^{2}(x) = \frac{β^{2}F_{1}(x)}{F_{2}(x)^{2}} ∑_{j_{1},...,j_{s}} A_{l_{1},l_{2}} Av ε_{l_{1}}ε_{l_{2}}E(x). (6.42)

Moreover,

F_{l_{1},l_{2}}^{3}(x) = \frac{β^{2}}{F_{2}(x)^{2}} ∑_{j_{1},...,j_{2s}} fA_{l_{1},l_{2}+s} Av ε_{l_{1}}ε_{l_{2}+s}ε_{J}E(x)E′(x). (6.43)

Here j_{1}, …, j_{2s} take all values ≤ M, with (j_{l_{1}}, l_{1}) ≠ (j_{l_{2}+s}, l_{2}), the average Av is over ε_{1}, …, ε_{2s} = ±1, and

E′(x) = exp ∑_{1≤l≤s} ε_{l+s}(βx(j_{l+s}, l) + h) ;

A_{l_{1},l_{2}+s} = \frac{σ(j_{l_{1}}) · σ(j_{l_{2}+s})}{N} − q,

and finally

F_{l_{1},l_{2}}^{4}(x) = β^{2} \frac{F_{1}(x)}{F_{2}(x)^{3}} ∑_{j_{1},...,j_{2s}} A_{l_{1},l_{2}+s} Av ε_{l_{1}}ε_{l_{2}+s}E(x)E′(x), (6.44)

where j_{1}, …, j_{2s} take all values ≤ M with (j_{l_{1}}, l_{1}) ≠ (j_{l_{2}+s}, l_{2}).

This of course looks totally overwhelming! To prove that this is not the case, we finish the proof of Proposition 6.6.

We use that F_{2}(x) ≥ M^{s}. Taking absolute values, and expectations, we see that all these terms on the right of (6.39) are bounded by

β^{2}K(β, h, s)M^{−3s} ∑_{j_{1},...,j_{3s}}|f(σ(j_{1}), …, σ(j_{s}))||\frac{σ(j_{l}) · σ(j_{l′})}{N} − q|

where l, l′ ≤ 3s, l ≠ l′. Using Hölder’s inequality, this is at most

β^{2}K(β, h, s)(M^{−s} ∑_{j_{1},...,j_{s}}|f(σ(j_{1}), …, σ(j_{s}))|^{p})^{\frac{1}{p}}

× (M^{−2} ∑_{j,j′}|\frac{σ(j) · σ(j′)}{N} − q|^{p′})^{\frac{1}{p′}} .

This is a bound for the left-hand side of (6.38). As M → ∞ and M^{−1} ∑_{j≤M} δ_{σ(j)} converges to Gibbs’ measure, this bound becomes

β^{2}K(β, h, s)⟨|f|^{p}⟩^{\frac{1}{p}} ⟨|R(σ, σ′) − q|^{p′}⟩^{\frac{1}{p′}} ,

where K(β, h, s) remains bounded with β, h, s, and we conclude by Hölder’s inequality. □

Proof of Lemma 6.9. This is a mere computation, although of course not a pleasant one. We write, with obvious notation,

(6.45)  \frac{∂^{2}F}{∂x_{a}∂x_{b}} = \frac{∂^{2}F_{1}}{∂x_{a}∂x_{b}} \frac{1}{F_{2}} − \frac{∂^{2}F_{2}}{∂x_{a}∂x_{b}} \frac{F_{1}}{F_{2}^{2}}

− (\frac{∂F_{1}}{∂x_{b}} \frac{∂F_{2}}{∂x_{a}} + \frac{∂F_{1}}{∂x_{a}} \frac{∂F_{2}}{∂x_{b}} )\frac{1}{F_{2}^{2}} + 2\frac{∂F_{2}}{∂x_{a}} \frac{∂F_{2}}{∂x_{b}} \frac{F_{1}}{F_{2}^{3}}

so that

\frac{1}{2} ∑ E(v_{a}v_{b} − u_{a}u_{b})\frac{∂^{2}F}{∂x_{a}∂x_{b}} (6.46)

is the sum of four pieces, each of which creates one of the sums of (6.39). The indexes a, b in the sum (6.46) are of the type

a = (k_{1}, l_{1}), b = (k_{2}, l_{2}). (6.47)

Restricting the summation to l_{1}, l_{2} fixed will create the individual terms in the sums of (6.39). Let us observe that E v_{a}^{2} = 1 = E u_{a}^{2} so that in (6.46) we can restrict the sum to a ≠ b. If l_{1} = l_{2}, no term of the sum (6.28) can contain both variables x(k_{1}, l_{1}), x(k_{2}, l_{2}) if k_{1} ≠ k_{2} so that

\frac{∂^{2}F_{1}}{∂x_{a}∂x_{b}} = 0.

If l_{1} ≠ l_{2},

\frac{∂^{2}F_{1}}{∂x_{a}∂x_{b}} = β^{2} ∑ f Av ε_{l_{1}}ε_{l_{2}}ε_{J} exp ∑_{l≤s} ε_{l}(βx(j_{l}, l) + h)

where the sum is restricted over those families j_{1}, …, j_{s} such that j_{l_{1}} = k_{1}, j_{l_{2}} = k_{2}. Now if a ≠ b, we have seen (using again the notation (6.47)) that

E(v_{a}v_{b} − u_{a}u_{b}) = \frac{σ(k_{1}) · σ(k_{2})}{N} − q. (6.48)

Thus

∑ E(v_{a}v_{b} − u_{a}u_{b})\frac{∂^{2}F_{1}}{∂x_{a}∂x_{b}} = β^{2} ∑ f(σ(j_{1}), …, σ(j_{s}))(\frac{σ(j_{l_{1}}) · σ(j_{l_{2}})}{N} − q)

× Av ε_{l_{1}}ε_{l_{2}}ε_{J} exp ∑_{l≤s} ε_{l}(βx(j_{l}, l) + h),

where the sum on the left is over k_{1}, k_{2} ≤ M, a = (k_{1}, l_{1}), b = (k_{2}, l_{2}), l_{1}, l_{2} fixed. This is how (6.40) occurs. The restriction l_{1} < l_{2} creates a factor 2. The term (6.42) occurs for the same reason, so we turn toward (6.43), that occur from the term \frac{∂F_{1}}{∂x_{b}} \frac{∂F_{2}}{∂x_{b}}. Using again (6.47), we have

\frac{∂F_{1}}{∂x_{a}} (x)\frac{∂F_{2}}{∂x_{b}} (x) = β^{2}(∑ f Av ε_{l_{1}}ε_{J} exp ∑_{l≤s} ε_{l}(βx(j_{l}, l) + h))

× (∑ Av ε_{l_{2}} exp ∑_{l≤s} ε_{l}(βx(j_{l}, l) + h)),

where the first sum is restricted to j_{l_{1}} = k_{1}, while the second sum is restricted to j_{l_{2}} = k_{2}. We write this product of two sums as a single sum (replicas) to obtain

\frac{∂F_{1}}{∂x_{a}} (x)\frac{∂F_{2}}{∂x_{b}} (x) = β^{2} ∑ f Av ε_{l_{1}}ε_{l_{2}+s}ε_{J}

× exp(∑_{l≤s} ε_{l}(βx(j_{l}, l) + h) + ∑_{l≤s} ε_{l+s}(βx(j_{l+s}, l) + h)).

There the sum is over j_{1}, …, j_{2s} ≤ M, such that j_{l_{1}} = k_{1}, j_{l_{2}+s} = k_{2}, the average is over ε_{1}, …, ε_{2s}. If we recall (6.48), computation of the sum

∑ E(v_{a}v_{b} − u_{a}u_{b})\frac{∂F_{1}}{∂x_{a}} (x)\frac{∂F_{2}}{∂x_{b}} (x)

yields (6.43). The restriction (j_{l_{1}}, l_{1}) ≠ (j_{l_{2}+s}, l_{2}) is because (6.48) requires a ≠ b. The term (6.44) is similar. □

Challenge problem 6.10. a) After reading Chapter 7, prove that

|q − E \overline{q}| ≤ \frac{L}{N} .

b) Prove that lim_{N→∞} N(q − E \overline{q}) exists.

We now end this chapter by the following weaker version of Proposition 2.1. It was discovered around 1985 by G. Pisier[Pi].

Proposition 6.11. Consider a function f on ℝ^{M} and assume that

|f(x) − f(y)| ≤ L∥x − y∥. (6.49)

Then, for all t > 0,

P(|f(g) − E f(g)| ≥ t) ≤ 2 exp(−\frac{t^{2}}{4L^{2}} ).

Proof. We assume first f differentiable. Consider s, and the function F on R^{2M} given by

F (z) = exp s(f((z_{i})_{i≤M}) − f((z_{i+M})_{i≤M})). (6.50)

Consider the Gaussian family u given by

\begin{cases}u_{i} = g_{i} \\ u_{i+M} = g_{i} \end{cases} for i ≤ M.

Then F (u) = 1. Consider now i.i.d. N (0, 1) variables (v_{i})_{i≤2M}. Thus, for i ≤ j ≤ 2M we have E(v_{i}v_{j} − u_{i}u_{j}) = 0 unless j = i + M, in which case E(v_{i}v_{j} − u_{i}u_{j}) = −1. Consider now θ(t) = E F (\sqrt{1 − t} u + \sqrt{t} v) so that, by Proposition 6.8,

(6.51)  θ′(t) = ∑_{i<j} E(v_{i}v_{j} − u_{i}u_{j}) E \frac{∂^{2}F}{∂x_{i}∂x_{j}} (\sqrt{1 − t} u + \sqrt{t} v)

= − ∑_{i≤M} E \frac{∂^{2}F}{∂x_{i}∂x_{i+M}} (\sqrt{1 − t} u + \sqrt{t} v).

Now,

\frac{∂^{2}F}{∂x_{i}∂x_{i+M}} (x) = −\frac{s^{2}∂f}{∂x_{i}} ((x_{i})_{i≤M})\frac{∂f}{∂x_{i}} ((x_{i+M})_{i≤M})F (x). (6.52)

Since (6.49) implies

∀x, ∥∇f(x)∥ ≤ L,

i.e.

∑_{i≤M}(\frac{∂f^{2}}{∂x_{i}} (x))^{2} ≤ L^{2},

we see from (6.52) and Cauchy-Schwarz that

|∑_{i≤M} \frac{∂^{2}F}{∂x_{i}∂x_{i+M}} (x))| ≤ L^{2}s^{2}F (x),

so that (6.52) implies

θ′(t) ≤ s^{2}L^{2}θ(t)

and since θ(0) = 1 this implies

θ(1) = E F (v) ≤ exp s^{2}L^{2}.

Now by Jensen’s inequality (integration in (v_{i})_{i≥M}) we have

E exp s(f(g) − E f(g)) ≤ E F (v) ≤ exp s^{2}L^{2},

so that

P (f(g) − E f(g) ≥ t) ≤ exp(s^{2}L^{2} − st),

and

P (f(g) − E f(g) ≥ t) ≤ exp(−\frac{t^{2}}{4L^{2}} )

by optimization over s. Changing F into −F finishes the proof when F is differentiable. The general case follows by approximation (e.g. convolution with a smooth function). □