\documentstyle[12pt]{article}
\oddsidemargin -3mm % Remember this is 1 inch less than actual
%\evensidemargin 7mm
\textwidth 17cm
\topmargin -9mm % Remember this is 1 inch less than actual
%\headsep 0.9in % Between head and body of text
\headsep 20pt % Between head and body of text
\textheight 23cm
\scrollmode
\begin{document}
%\baselineskip=24pt
\title{\bf The Spectral Gap of the REM under Metropolis Dynamics}
\author{L. R. G. Fontes \\ Universidade de S\~ao Paulo\\ [5mm]
M.~Isopi \\ Universit\'a di Roma 1\\ [5mm]
Y.~Kohayakawa\\ Universidade de S\~ao Paulo\\ [5mm]
P.~Picco \\ CPT, CNRS, Marseille}
\maketitle
\newtheorem{defin}{Definition}[section]
\newtheorem{Prop}{Proposition}
\newtheorem{teo}{Theorem}
\newtheorem{prop}{Proposition}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{rmk}{Remark}[section]
\newtheorem{cor}{Corollary}[section]
\renewcommand{\theequation}{\thesection .\arabic{equation}}
\newcommand{\G}{\Gamma}
\newcommand{\gi}{\Gamma_i}
\renewcommand{\L}{\Lambda}
\newcommand{\PP}{I\kern-.25em{P}}
\newcommand{\1}{1\kern-.25em\hbox{\rm I}}
\newcommand{\E}{I\kern-.25em{E}}
\newcommand{\lk}{\lambda_k}
\newcommand{\rk}{\rho_k}
\newcommand{\pk}{p_k}
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\bc}{\b_c}
\newcommand{\bt}{\frac{\b}{2}}
\renewcommand{\u}{\mbox{\boldmath $1$}}
\newcommand{\g}{\gamma}
\newcommand{\gie}{\gamma^i_{\eta,\eta'}}
\newcommand{\giep}{\gamma^i_{\eta,\eta''}}
\newcommand{\giepp}{\gamma^i_{\eta',\eta''}}
\newcommand{\gioe}{\gamma^{i_1}_{\eta,\eta'}}
\newcommand{\goe}{\gamma^1_{\eta,\eta'}}
\newcommand{\gine}{\gamma^{i_n}_{\eta,\eta'}}
\renewcommand{\d}{\delta}
\newcommand{\D}{\Delta}
\renewcommand{\ln}{{\L}}
\newcommand{\lnd}{\{1,\ldots,N\}^d}
\newcommand{\e}{\cal E}
\newcommand{\eps}{\epsilon}
\renewcommand{\l}{\lambda}
\renewcommand{\o}{\Omega}
\newcommand{\s}{\sigma}
\renewcommand{\sl}{\sigma'}
\newcommand{\si}{\s_i}
\newcommand{\sil}{\s'_i}
\newcommand{\sj}{\s_j}
\newcommand{\sa}{\s_\a}
\newcommand{\sal}{\s'_\a}
\newcommand{\sz}{{\underline\s}}
\renewcommand{\sb}{{\bar\s}}
\renewcommand{\sp}{\sigma^\prime}
\newcommand{\spp}{\sigma^{\prime\prime}}
\renewcommand{\t}{\tau}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqn}{\begin{eqnarray}}
\newcommand{\beqnn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray}}
\newcommand{\eeqnn}{\end{eqnarray*}}
\newcommand{\bprop}{\begin{prop}}
\newcommand{\eprop}{\end{prop}}
\newcommand{\bteo}{\begin{teo}}
\newcommand{\bcor}{\begin{cor}}
\newcommand{\ecor}{\end{cor}}
\newcommand{\eteo}{\end{teo}}
\newcommand{\brm}{\begin{rmk}}
\newcommand{\erm}{\end{rmk}}
\newcommand{\blem}{\begin{lem}}
\newcommand{\elem}{\end{lem}}
\newcommand{\da}{\downarrow}
\newcommand{\ar}{\rightarrow}
\newcommand{\on}{\o}
\newcommand{\oj}{\o_{j-1}}
\newcommand{\onj}{\o_{N-j}}
\newcommand{\ojm}{\o_j^-}
\newcommand{\ojp}{\o_j^+}
\newcommand{\olm}{\o_\ell^-}
\newcommand{\olp}{\o_\ell^+}
\newcommand{\oi}{\o_i}
\newcommand{\mn}{\mu_{N}}
\newcommand{\zn}{Z_{N}}
\newcommand{\hn}{H^(N)}
\newcommand{\hnn}{H_(N)}
\newcommand{\cn}{C_N}
\newcommand{\lab}{\langle}
\newcommand{\rab}{\rangle}
\newcommand{\bbz}{{Z\kern-0.45emZ}}
\newcommand{\bz}{{Z\kern-0.30emZ}}
\renewcommand{\r}{{\rm I}\!{\rm R}}
\newcommand{\zd}{\bbz^d}
\newcommand{\N}{I\kern-.22em{N}}
\newcommand{\zzd}{\bz^d}
\newcommand{\h}{{\bf h}}
\renewcommand{\u}{\mbox{\boldmath $1$}}
\newcommand{\sii}{\s_{i}}
\newcommand{\jij}{J_{ij}}
\newcommand{\ja}{J_{\a}}
\newcommand{\nn}{\nonumber}
\renewcommand{\=}{&=&}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\renewcommand{\t}{\tau}
\newcommand{\tf}{\t(\phi)}
\newcommand{\tfsz}{\t(\phi_{\sz})}
\newcommand{\tfs}{\t(\fss)}
\newcommand{\ef}{{\e}(\phi,\phi)}
\newcommand{\vf}{Var(\phi)}
\newcommand{\inv}{\frac{1}{\sqrt2}}
\renewcommand{\ge}{\!\!&\geq&\!\!}
\renewcommand{\>}{\!\!&>&\!\!}
\renewcommand{\le}{\!\!&\leq&\!\!}
\renewcommand{\+}{\!\!&+&\!\!}
\newcommand{\de}{\Delta}
\newcommand{\ep}{\vspace{.5cm}}
\newcommand{\bo}{\mbox{ }_\Box}
\newcommand{\bp}{\noindent{\bf Proof:}}
\newcommand{\pss}{P(\s,\sp)}
\newcommand{\qss}{Q(\s,\sp)}
\newcommand{\pssp}{P(\s,\spp)}
\newcommand{\hs}{H(\s)}
\newcommand{\he}{H(\eta)}
\newcommand{\hep}{H(\eta')}
\newcommand{\hsz}{H(\sz)}
\newcommand{\hsb}{H(\sb)}
\newcommand{\fss}{\phi_\s}
\newcommand{\fs}{\phi(\s)}
\newcommand{\fsp}{\phi(\sp)}
\newcommand{\hsi}{H_i(\sii)}
\newcommand{\hsp}{H(\sp)}
\newcommand{\ehs}{\exp\{-\b\hs\}}
\newcommand{\ehsp}{\exp\{-\b\hsp\}}
\newcommand{\ehhsp}{\exp\{-\bt\hsp\}}
\newcommand{\ephs}{\exp\{\b\hs\}}
\newcommand{\ephsp}{\exp\{\b\hsp\}}
\newcommand{\ehsz}{\exp\{-\b\hsz\}}
\newcommand{\ethsz}{\exp\{-2\b\hsz\}}
\newcommand{\ehsb}{\exp\{\b\hsb\}}
\newcommand{\ehhsz}{\exp\{-\bt\hsz\}}
\newcommand{\ebm}{e^{\b(\hs\vee\hsp)}}
\newcommand{\ebs}{e^{-\b(\he+\hep)}}
\newcommand{\ebmm}{\exp\{-\b(\hs\vee\hsp)\}}
\newcommand{\ds}{\hsp-hs}
\newcommand{\dh}{\D H(\hs,\hsp)}
\newcommand{\ch}{{\cal H}}
\newcommand{\zi}{\frac{1}{\zn}}
\newcommand{\zq}{\frac{1}{\zn^2}}
\newcommand{\un}{\frac{1}{\nd}}
\newcommand{\urn}{\frac{1}{{\nhd}}}
\newcommand{\ohn}{\frac{1}{N\cn}}
\newcommand{\ass}{\lab\s,\sp\rab}
\newcommand{\assz}{\lab\sz,\sp\rab}
\newcommand{\aij}{\lab i,j\rab}
\newcommand{\hcn}{{\cal C}_N}
\newcommand{\gn}{\G_N}
\newcommand{\get}{\g_{\eta,\eta'}}
\newcommand{\zbn}{{\bar\zn}}
\newcommand{\nd}{N}
\newcommand{\nmd}{\nd^{-1}}
\newcommand{\nhd}{\nd^{-1/2}}
\newcommand{\sums}{\sum_{\s}}
%%%%%%%%%%%%%%%%%% ABSTRACT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
We derive upper and lower bounds
for the spectral gap of the Random Energy Model under Metropolis
dynamics which are sharp in exponential order.
They are based on the variational characterization of the gap.
For the lower bound, a Poincar\'e inequality derived
by Diaconis and Stroock is used.
The scaled asymptotic expression is a linear function of
the temperature. The corresponding function for
a global version of the dynamics exhibits phase transition
instead.
We also study the dependence of lower order terms on the volume.
In the global dynamics, we observe a phase transition.
For the local dynamics, the expressions we
have, which are possibly not sharp, do not change their order of dependence
on the volume as the temperature changes.
\end{abstract}
\ep
{\em Mathematics Subject Classification 1991:} 60K35, 82B44.
\noindent{\em Key words and phrases:} Disordered systems, spin glasses,
random energy model, Metropolis dynamics, Glauber dynamics, convergence
to equilibrium, spectral gap, dynamical phase transition
\ep
%%%%%%%%%%%%%%%%%% SECTION 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\setcounter{equation}{0}
\label{sec:int}
The Random Energy Model (REM)(\cite{kn:D1}, \cite{kn:D2}) is a disordered hamiltonian
spin system designed as a
caricature of the Sherrington-Kirkpatrick (SK) Spin-Glass Model
(\cite{kn:MPV}).
Both models are mean-field ones. While in the SK model one has gaussian
pair interactions only, in the REM there are gaussian multibody interactions.
The hamiltonian for the SK model is (for $\s$ a given configuration of spins
$+$ or $-1$ in a volume $\L$)
\beq
H_{{SK}}(\s)=-|\L|^{-1/2}\sum_{i,j\in\L}\jij\si\sj,
\eeq
where the sum is over all pairs of distinct sites in $\L$ and $\{\jij,\,i,j\}$ is a
family of i.i.d.~standard gaussians, whereas that for the REM is
\beq
\label{eq:mic}
H_{REM}(\s)=-\frac{|\L|^{1/2}}{2^{|\L|/2}}\sum_{\a\subset\L}\ja\sa,
\eeq
where the sum is over all the $2^N$ subsets $\a$ of $\L$, $\{\ja,\,\a\}$
is a family of i.i.d.~standard
gaussians defined on a common probability space $({\cal E},\Sigma,\PP)$
and $\sa=\prod_{i\in\a}\si$ ($\s_\emptyset=1$).
We observe that for the REM the hamiltonians of all configurations form a
family of i.i.d.~gaussians with mean zero and variance $|\L|$. A proof of
this elementary fact is provided in the appendix A. That could be
taken as an alternative description of this model, indeed it is the
usual one. We will adopt it in the next section.
The equilibrium statistical mechanics of the REM has been much studied.
In a non rigorous way in (\cite{kn:D1}, \cite{kn:D2}) and in a rigorous
way in (\cite{kn:E}, \cite{kn:OP}, \cite{kn:GMP}).
We quote some of these rigorous results that will
be important for understanding
some aspects of the dynamics.
Given $\b\geq 0$, the inverse temperature, taking $\L=\{1,\dots,N\}$,
let us denote by
\beq
\label{eq:part}
Z_N\equiv Z_N(\b)= \sum_{\s} e^{-\b H_{REM}(\s)}
\eeq
the finite volume partition function and by
\beq
\label{eq:free}
F_N(\b)= \frac 1{N} \log Z_N(\b)
\eeq
the finite volume free energy.
It was proved in \cite{kn:OP} that for all $\b\geq 0$,
the limit $\lim_{N\rightarrow \infty} F_N(\b)=F(\b)$
exists $\PP$-almost surely and in $L^p({\cal E},\PP)$ for $1\leq p<\infty$.
$F(\b)$ is a non random function which is differentiable in $\b$
but the second derivative has a jump at $\bc=\sqrt {2\log 2}$.
In fact, $F(\b)$ is equal to $\b^2/2 +\bc^2/2$ for $\b<\bc$ and $\bc\b$ for
$\b\geq \bc$, as expected from the results of \cite{kn:D1}.
This is called in the physics literature a third order phase transition.
The point is, depending if we are in a high temperature regime ($\b<\bc$)
or in a low temperature one ($\b\geq \bc$),
not only that the free energy changes from a quadratic function of $\b$
to a linear one but that the difference between the finite volume free energy
and its infinite volume limit
is exponential in the high temperature case and this occurs almost surely,
whereas in the low temperature regime this difference behaves as
$C(\omega,\b,N)\frac {\log N}{N}$ for some random function $C(\omega,\b,N)$.
This function converges in $\PP$-probability to a non-random limit but
does not converge $\PP$-almost surely and an interval
where $C(\omega,\b,N)$ fluctuates $\PP$-almost surely is identified.
More precisely,
it was proved in \cite{kn:OP} that if $0\leq \b <\bc$ then
\beq
\label{eq:HT}
F(\b) -e^{-\lambda(\b)N} \leq F_N(\b) \leq F(\b) +e^{-\lambda(\b)N}
\eeq
$\PP$-almost surely and in $L^1({\cal E},\PP)$
for some $\lambda(\b) >0$ if $\b<\bc$.
If $\b\geq \bc$ then the rate of convergence is more subtle,
depending if we want a $\PP$-almost sure result or one in $\PP$-probablity.
Namely, calling
\beq
\label{eq:BT}
{\cal V}_N(\b) = \frac {\bc}{\b}
\frac {\log \left[ Z_N e^{-N F(\b)}\right]}{\log N},
\eeq
this quantity has a behavior which is radically different in $\PP$-probability
and $\PP$ almost surely.
It was proven in \cite{kn:OP}
that $\PP$-almost surely
\beq
\label{eq:BTOP1}
\limsup_{N\rightarrow \infty} {\cal V}_N(\b)\leq \frac {1}{2}
\eeq
and also $\PP$-almost surely
\beq
\label{eq:BTOP2}
\liminf_{N\rightarrow \infty} {\cal V}_N(\b)\geq -\frac {1}{2}.
\eeq
These two results do not imply that ${\cal V}_N(\b)$ does not
converge $\PP$ almost surely, this question was solved later, namely,
it was proven in \cite{kn:GMP} that we have $\PP$-almost surely
\beq
\label{eq:BTGMP1}
\limsup_{N\rightarrow \infty} {\cal V}_N(\b)= \frac {1}{2}
\eeq
and also $\PP$-almost surely
\beq
\label{eq:BTGMP2}
\liminf_{N\rightarrow \infty} {\cal V}_N(\b)= -\frac {1}{2}.
\eeq
The result in $\PP$-probability (and in $L^1(\Omega,\PP)$ ) is simpler.
In \cite{kn:GMP} it is proved that
\beq
\label{eq:BTGMP3}
\lim_{N\rightarrow \infty} {\cal V}_N(\b)= -\frac {1}{2}
\eeq
as it was expected from \cite{kn:D2}.
In this work we consider a dynamical version of the
model, namely, the REM
undergoing a Glauber dynamics (Metropolis). That is, we are considering
a dynamics in random environment.
We study the speed of convergence to
equilibrium, the exponential rate of which is given by the {\em spectral
gap} (or just {\em gap}) of the dynamics, which is
the difference between the first and second eigenvalues of the transition
probability matrix of the continuous time Markov chain defining it
(see~\cite{kn:DS} Proposition 3, also~\cite{kn:S}).
As in other dynamics of spin systems, this gap goes to zero when the volume
goes to infinity and one of the main questions in the study of the approach
to equilibrium is the exact rate at which it does so.
It is natural to consider the inverse of the gap instead of the gap,
the former quantity being linked to the relaxation time.
In non random mean field models at low temperature,
the logarithm of the inverse of the gap grows like the volume. At high temperature,
it is $o(N)$ and grows at least as the logarithm of the volume.
In short range random systems, it is expected that the inverse of the
spectral gap grows in a slower way at low temperature.
This is a very active line of research.
Therefore, it is important to clarify at least the case of one of
the standard random mean field models, where we know very well the statics.
To get bounds for the inverse of the gap, we use a variational
characterization and a bound
derived by Diaconis and Stroock based on that (\cite{kn:DS}).
A nice percolation problem in the hypercube with $|\L|$ dimensions comes into play.
We prove that for the REM the logarithm of the inverse of the spectral gap
grows like the volume.
We give its exact asymptotic behavior by dividing it by the volume and proving that
this normalised quantity converges $\PP$-almost surely {\em for all } $\b$
to the linear non random function
$\bc\b$ (which is also the free energy of the REM at low temperature).
We give $\PP$ almost sure upper and lower bounds for the finite volume
error of approximation of this quantity
to its limit, in the very same spirit of (\ref{eq:BTOP1})
and (\ref{eq:BTOP2}).
The magnitude of these bounds are of order $\sqrt {\frac {\log N}{N}}$,
which suggests that the actual error may be bigger than that for the
free energy (which is of order $\frac {\log N}{N}$ for $\b\geq\bc$ and exponentially
decaying in $N$ for $\b<\bc$, as pointed above).
We conjecture that this is indeed the case and that the constant of proportionality
is random.
Also, we do not expect to see any phase transition in the
behavior of this constant.
Our first theorem (Theorem~\ref{teo1} at the end of Section~\ref{sec:ulb})
implies that there is no dynamical phase transition (interpreted
as a change of behavior in the limiting scaled gap as a function of
the temperature) for this model.
Note that in the Curie-Weiss model, there is a dynamical phase transition for the
dynamics induced on the magnetizations,
in the sense that, at low temperature, the logarithm of the spectral gap is
proportional
to the volume times the difference between the canonical free energy computed at
magnetization
zero and the canonical free energy computed at its minimum, whereas at high
temperature it is $o(N)$.
In the final section of this paper, we consider a {\em global} Metropolis
dynamics for the REM
for which the scaled gap behaves asymptotically as a function of the
temperature which does undergo a (third order) phase transition.
We give also $\PP$-almost sure bounds for the rate at which the scaled gap converges
to its limit and we see here also a phase transition on the rate.
As regards other disordered dynamical models, Cassandro et al.~have
studied a
random walk with random traps, with a different approach, using coupling
techniques, to get the order of the speed of convergence to equilibrium
\cite{kn:CGP}.
Dynamics of spin glasses were also studied (non-rigorously) by Sompolinsky and
Zippelius (\cite {kn:SZ}) which considered a {\em soft spin} approach
so that they could work with quantities varying continuously. This has been
made rigorous by Ben Arous and Guionnet (\cite {kn:BG}). But their study is
for time scale shorter than the one we are dealing with.
Some recent work (\cite {kn:Z} and \cite {kn:GZ}) shows that non exponential
relaxation is possible in infinite volume for models with short range
interaction. This is of course not in contradiction with our result for a
(large) finite sample. We plan to investigate infinite volume behaviour
and the relationship with the short range models results
in a forthcoming paper.
The rest of the paper is organized as follows. In the next section we describe
the model in detail. In Section 3 we derive upper and lower
bounds for the inverse of the gap of the Metropolis dynamics. In Section 4
we consider a modification of this dynamics.
Appendices are devoted to auxiliary results.
\ep
%%%%%%%%%%%%%%%%%% SECTION 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Model}
\setcounter{equation}{0}
\label{sec:mod}
Throughout we consider the Random Energy Model (REM) as a
non-equi\-li\-bri\-um
system undergoing Metropolis
dynamics in finite volume.
We want to study the behavior of the gap between the
first and second eigenvalues of the infinitesimal generator
of the corresponding continuous time Markov process
(or of the probability transition matrix; the gap is the same)
as the volume goes to infinity.
Let $\ln$ be a nonempty set with $|\L|=N$
and let $\on$ denote $\{-1,1\}^\ln$.
Let $\ch=\{\hs,\s\in\on\}$ be an independent family of Gaussian
random variables with common mean zero and common variance $\nd$
defined on a probability space $({\cal E},\Sigma,\PP)$. $\ch$
plays the role of the random hamiltonian or energy function.
We consider a continuous-time Markov chain with state space $\on$
with transition
probabilities that are reversible with respect to the Gibbs measure
$\mn$ on $\on$, which is obtained from $\ch$ and the inverse temperature parameter
$\b$ in the usual
way, that is $$\mn(\s)=\zi\exp\{-\b\hs\},\quad\s\in\on.$$
More specifically, we consider Metropolis type transition probabilities,
given by
\beqn
\nonumber
\pss\=\exp\{-\b(\hsp-\hs)^+\}/N,\quad\mbox{if}\quad ||\sp-\s||=1,\\
\nonumber
\= 0,\quad\mbox{if}\quad ||\sp-\s||>1,\\
\label{eq:locdyn}
\= 1-\sum_{\spp\ne\s}\pssp,\quad\mbox{if}\quad\sp=\s,
\eeqn
where $a^+=\max\{a,0\}$ and $||x||=\frac{1}{2}\sum_{i=1}^{\nd}|x_i|$.
Note that these transition probabilities are random variables defined on
$({\cal E},\Sigma,\PP)$. That is, we have an inhomogenous random walk on the hypercube
$\on$ in the random environment defined by the transition probability valued
random variables $\pss$.
We are interested in properties of this dynamics
that are true for almost all realisations
of the random hamiltonian $\ch$.
\ep
%%%%%%%%%%%%%%%% SECTION 3 %%%%%%%%%%%%%%%%%%%%%%%%
\section{Upper and Lower Bounds}
\setcounter{equation}{0}
\label{sec:ulb}
We recall here some basic facts about Markov chains.
Let $P(\cdot,\cdot)$ be the transition probability for
an irreducible Markov chain in a finite
state space $S$ which
is reversible with respect to a measure $\mu$ on $S$.
That is, $\mu(x)P(x,y)=\mu(y)P(y,x)$ for all $x,y\in S$.
Let $\phi$ be a real valued function on $S$. Let us define
\beqn
\label{eq:vf}
\vf\=\frac {1}{2}\sum_{\s,\sp}(\fs-\fsp)^2\mu(\s)\mu(\sp),\\
\label{eq:ef}
\ef\=\frac {1}{2}\sum_{\s,\sp}(\fs-\fsp)^2\qss,
\eeqn
where $\qss=\mu(\s)\pss$.
$\vf$ is the variance of $\phi$ and $\ef$ is the Dirichlet form of
the Markov semi-group associated to $P(\cdot,\cdot)$.
Since $P(\cdot,\cdot)$ has largest eigenvalue $1$ and the constant functions
are the only eigenvectors with eigenvalue $1$, using the minimax characterization of
eigenvalues, if we define
\beq
\label{eq:tf}
\tf=\frac{\vf}{\ef},
\eeq
then the inverse of the gap between the first and second eigenvalues
of $P(\cdot,\cdot)$ is given by (\cite{kn:DS})
\beq
\label{eq:tau}
\t=\sup_{\phi}\tf,
\eeq
where the sup is taken over non constant $\phi$'s.
We will use this characterization of the gap to derive bounds
for it in the case of the dynamics given by~(\ref{eq:locdyn}).
(Later on, in the final section, we will consider a {\em global}
modification of it.) In this context, $S=\on$ and $\mu=\mn$.
We have also the following bound, given in \cite{kn:DS},
for the distance in variation.
\beq
\label{eq:equi}
\|P_t(x,\cdot)-\mn(\cdot)\|_{var} \leq \sqrt {\frac {1-\mn(x)}{4\mn(x)}} e^{-t/\t}
\eeq
Here $P_t(x,y)=e^{-t}\sum_{n=0}^{\infty} \frac {t^n}{n!}P^n(x,y)$
is the transition kernel. (There is a similar lower bound for the maximum
in $x$ of the left hand side. See~\cite{kn:S}.)
In the next two subsections, we derive upper and lower bounds for $\t$.
%%%%%%%%%%%%%%%% SUBSECTION 3.1 %%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lower Bound}
\label{subsec:lb}
As usual in this kind of variational problem, we take a trial function to get a
lower bound.
We choose for $\phi$ the indicator of a spin configuration, that is, we
define $\fss$ by $\fss(\sp)=\d(\s,\sp)$, where $\d(\cdot,\cdot)$ is the
Kronecker delta. We have
\beq
\label{eq:lb1}
\tfs=\frac{\ehs}{\zn\sum_{\ass}\qss}(1-\mn(\s)),
\eeq
where the sum is over the $N$ nearest neighbors of $\s$, denoted
$\sp$.
For the Metropolis dynamics, $\qss=(\nd\zn\ebm)^{-1}$ and thus
(\ref{eq:lb1}) equals
\beq
\label{eq:lb2}
\frac{\nd\ehs}{\sum_{\ass}\ebmm}(1-\mn(\s)).
\eeq
Let $\sz$ be the (unique) spin configuration $\s$ for which $\hs$ is
minimal. Then we get the bound
\beq
\label{eq:lbm}
\t\geq\max_{\s}\t(\fss)\geq\tfsz=\frac{\nd\ehsz}{\sum_{\assz}\ehsp}
(1-\mn(\sz)).
\eeq
\bprop
\label{prop:lb}
There exists a positive constant $c$ such that,
for all $\b$, with $\PP$-probability 1, for all but a finite number of indices $N$ we have
\beq
\label{eq:lb}
\frac{1}{\nd}\log\t\geq\bc\b -c \b\sqrt {\frac{\log\nd}{\nd}},
\eeq
where $\bc=\sqrt{2\log2}$.
In particular
\beq
\label{eq:lb01}
\liminf_{\nd \rightarrow \infty}
\frac{1}{\nd}\log\t\geq\bc\b
\eeq
$\PP$-almost surely.
\eprop
\noindent{\bf Proof}
Let us first consider the term $1-\mn(\sz)$.
Let $D_N=H(\sz')-H(\sz)$ where $\sz'$ is
the location of the second minimum of $H$. Then
\beq
\label{eq:lb012}
(1-\mn(\sz))^{-1}=1+\frac{e^{-\b H(\sz)}}{\sum_{\s\ne\sz}e^{-\b H(\s)}}
\leq 1+\frac{e^{-\b H(\sz)}}{e^{-\b H(\sz')}}\leq 2 e^{\b D_N}.
\eeq
Now, given $\eps>0$, one has
$$\PP(D_N>N\eps)=\int_{-\infty}^\infty
\frac{\bar F(x+N\eps)}{\bar F(x)}\,dF_{N}'(x),$$
where $F$ is the gaussian with mean $0$ and variance $N$
distribution function, $\bar F=1-F$
and $F_{N}'$ is the distribution function of
$-H(\sz')$. Here we use the elementary fact that
for a sequence $X_1,\ldots,X_n$ of i.i.d.~continuous random variables,
if $Y_1,\ldots,Y_n$ are its increasing order statistics, then
$$\PP(Y_n>y|Y_{n-1}=x)=\frac{1-F_{X_1}(y)}{1-F_{X_1}(x)}$$
for all $x0$. The former is bounded from above by
$$\PP(H(\sz')>0)=(2^N+1)2^{-2^N},$$
where the equality follows from elementary computations.
To bound the latter integral, we observe that,
since $x$ is positive, $\bar F(x+N\eps)\leq e^{-\eps^2 N/2}\bar F(x)$
by a simple linear change of variables.
Thus $e^{-\eps^2 N/2}$ is an upper bound for this integral.
Therefore, given $\gamma>0$, choosing
$\eps=\sqrt{ \frac {2\log N}{N}(1+\gamma)}$,
we get
\beq
\label{eq:lb02}
\PP\left( \frac {D_N}{N}\geq \sqrt{ \frac {2\log N}{N}(1+\gamma)}\right)
\leq
(2^N+1)2^{-2^N} + \frac {1}{N^{1+\gamma}}.
\eeq
Using the first Borel-Cantelli lemma, we then get that for any $\gamma>0$,
with $\PP$-probability 1, for all but a finite number of indices $N$
\beq
\label{eq:lb03}
\frac {1}{N} \log (1-\mn(\sz)) \geq - \frac {\log 2}{N} - \b\sqrt{ \frac{2\log
N}{N}(1+\gamma)}.
\eeq
To bound from below the term $\ehsz$, we use the easily checked fact that
for all $\eps>0$
\beq
\label{eq:lb04}
\PP\left(\hsz \geq -\bc N+\frac{1}{2\bc}(1+\eps)\log N \right) \leq e^{-cN^{\eps}}
\eeq
for some positive constant $c$.
Thus, using again the Borel-Cantelli lemma, we get that
for any $\eps>0$,
with $\PP$-probability 1, for all but a finite number of indices $N$
\beq
\label{eq:lb05}
\frac {1}{N} \log \ehsz \geq \b\bc -\frac {\b}{2\bc}(1+\eps) \frac {\log N}{N}.
\eeq
Note that the corrections are of smaller order than the ones in \ref{eq:lb03}.
It remains to consider the denominator in (\ref{eq:lb2}).
We first bound from above the sum by $N$ times the maximum of the summands.
Since $\sz$ is the configuration where the infimum is reached, these
summands are not independent. However, the maximum is stochastically
dominated by the maximum of N independent summands.
A proof of this fact can be found in the appendix.
Now if $m_N$ is the minimum of $N$ independent
standard gaussian random variables then if $c>1$
\beqn
\nonumber
\PP\left(\bigcup_{N=N_o}^{\infty}\left\{m_N \leq
-\sqrt{ (1+\eps)2\log N}\right\}\right)
\le \sum_{k=k_0}^{\infty}\PP\left(\bigcup_{N=c^k}^{c^{k+1}}
\left\{m_N \leq -\sqrt{(1+\eps)2\log c^{k}}\right\}\right)\\
\label{eq:lb06}
\le \sum_{k=k_0}^{\infty} e^{-\eps k \log c} <\infty.
\eeqn
Therefore we get that with $\PP$-probability 1 for all but a finite of indices
$N$
\beq
\label{eq:lb060}
m_N \geq -\sqrt {2(1+\eps)\log N}.
\eeq
We used now the classical fact that if two families $(X_i)_{i\in \N}$
and $(Y_i)_{i\in\N}$ of real random
variables are such that
for any $i\in \N$ $X_i$ is stochatically
dominated by $Y_i$, then we can construct a
common probability space such that, $\PP$-almost surely,
$ X_i\leq Y_i$ for all $i\in\N$.
Therefore, we get
for any $\eps>0$, with $\PP$-probability 1 for all but a finite of indices $N$
\beq
\label{eq:lb07}
\frac {1}{N}\log({\sum_{\ass}\ebmm})^{-1} \geq - \b \sqrt{2(1+\eps)\frac {\log
N}{N}}.
\eeq
Collecting (\ref{eq:lb03}), (\ref{eq:lb05}) and
(\ref{eq:lb07}), we get (\ref{eq:lb}).
$\bo$
\brm
The bound~(\ref{eq:lb07}) is optimal, in the sense that it can be proved,
by restricting the sum to the $\s'$ which realises the maximum, that
with $\PP$-probability 1, infinitely often (in N)
we have
\beq
\label{eq:lb70}
\frac {1}{N} \log ({\sum_{\ass}\ebmm})^{-1}\leq -\b \sqrt{2(1-\eps)\frac {\log
N}{N}}.
\eeq
Note that it can be also proved, but it is rather long,
that
\beq
\label{eq:lb71}
\frac {1}{N} \log (1-\mn(\sz)) \geq - \frac {\log 2}{N} - c\b {\frac{\log
N}{N}(1+\gamma)}
\eeq
for all large enough $N$.
Since the proof we gave here is really shorter and, on the other hand, the upper
bound for the correction to the upper
bound for $\t$ we will get in the next chapter is of order
$ \sqrt {\frac{\log N}{N}}$ and we have no proof of the optimality for that part,
we prefer not to argue~(\ref{eq:lb71}) in detail.
\erm
%%%%%%%%%%%%%%%% SUBSECTION 3.2 %%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Upper Bound}
\label{subsec:ub}
The upper bound is based on the {\em Poincar\'e inequality} derived
in~\cite{kn:DS}. It is given in terms of the {\em canonical paths}
of Jerrum and Sinclair~\cite{kn:S},~\cite{kn:JS}.
Let $\hcn$ denote the hypercube in $\nd$ dimensions obtained from
$\on$ by adding nearest neighbor bonds (the ones over which the
transition probabilities are positive) between the points of $\on$, that we will
call with a little abuse sites, {\it i.e.}~a site is just a spin configuration.
We will call $\s_j$ the j-coordinate of the site $\s$.
Let $\G$ be a complete
set of directed paths in $\hcn$, that is, $\G$ is a set of directed paths in $\hcn$
such that every two distinct sites in $\hcn$ are ends of a directed path in $\G$.
The paths are self avoiding {\it i.e.}~for a given path a bond is visited
just once.
>From Proposition $1'$ in~\cite{kn:DS} one has the bound
\beq
\label{eq:ub1}
\t\leq\max_{b}Q(b)^{-1}\sum_{\get\ni b}|\get|\mn(\eta)\mn(\eta'),
\eeq
where the $\max$ is over the nearest neighbor bonds $b=\ass$
of $\hcn$, $Q(b)=Q(\s,\sp)$ and the
summation is over all paths in $\G$ (indexed by their endpoints
$\eta$ and $\eta'$) which pass through $b$.
Writing the bound more explicitly, we have
\beq
\label{eq:ub2}
\t \leq
\frac{\nd}{\zn}\max_{b=\ass}\ebm\sum_{\get\ni b}|\get|\ebs.
\eeq
The rest of this subsection is devoted to exhibit a choice of
$\G$ such that one has control on~(\ref{eq:ub2}) enough
to obtain an upper bound for it of the same logarithmic order
as the lower bound of last subsection, with corrections of the same
order.
One term to control is $\ebm$, which is too big when
a path passes through values of $H$ close to the maximum.
The strategy is to avoid
those {\em bad} points as often as possible. This cannot be done always since
there must be paths that visit sites with high positive values of $H$.
This is because the set of paths is {\it complete}.
On a heuristic level, one wants to take advantage of the fact that the Gibbs
measure of such high positive values
of the energy is very small.
To take this into account in a rigorous way, we define the set of paths in
such a way that
if these high positive values are visited, this will occur
only at the ends of the
path and therefore their contribution are depressed by the factor $\ebs$
appearing in~(\ref{eq:ub2}).
It is not obvious that this can be done and, if it can, then the set
of paths we get is certainly dependent on the realizations of $\cal H$,
which in turn puts a problem on the subsequent control of the sum
in~(\ref{eq:ub2}).
Fortunately, the bad points are sufficiently rare
that the first control is obtained with a set of paths with randomness
limited so that the second control becomes possible.
%%%%%%%%%%%%%%%%%% GAMMA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{A choice of $\G$}
\label{subsec:ga}
To choose $\G$, we start by considering a family of sets
of paths $\gi,\,i=1,\ldots,\nd,$ as follows.
For $i\in\{1,\ldots,\nd\}$, $\eta$ and $\eta'\in\on$ fixed
such that $\eta_i\neq \eta'_i$,
let $\gie$ be the path from $\eta$ to $\eta'$ obtained by
going left to right cyclically from $\eta$ to $\eta'$ successively
flipping the disagreeing spins, starting at the coordinate $i$.
Let
\beq
\gi=\{\gie,\,\eta,\eta'\in\on\}.
\eeq
Given $\eta,\eta'$ and $\get$, let $\overline{\get}$ be the set of points visited
by the path $\get$ and $\get^o=\overline{\get}\setminus\{\eta,\eta'\}$ the set of interior
point of the path $\get$. We say that a family of paths ${\gamma_1,\dots,\gamma_n}$
is {\it interior-disjoint} if $\gamma_i^o\cap\gamma_j^o=\emptyset$ for all $1\leq i\ne j\leq n$.
We will need the following result, which is easy to check but fundamental.
\blem
\label{lem:disj}
Given $\eta$ and $\eta'$ in $\on$ at distance $n$
(that is, $||\eta-\eta'||=n$), there exist $n$
interior-disjoint paths in $\{\gie,\,i=1,\ldots,\nd\}$.
\elem
\noindent{\bf Sketch of Proof}
Indeed, if $i_1,\ldots,i_n$ are the coordinates where $\eta$
and $\eta'$ disagree, then one easily checks that
$\gioe,\ldots,\gine$ are interior-disjoint. Notice all such
paths have $n-2$ interior points. $\bo$
\ep
The set $\G$ will be chosen depending on a positive
parameter $c_e$ to be chosen later. It will be formed by
indicating for each pair ($\eta,\eta'$) the path connecting
the respective sites.
We will distinguish between {\em good} and {\em bad} sites
of $\on$. Good sites
are those $\sigma$ for which $H(\sigma)\leq \sqrt{2(1+c_e)N\log N}$; otherwise, they are bad.
We say that a path $\gamma$ is good if all its interior points $\gamma^o$
are good, and that a set of paths is good if all
its elements are good.
We construct the random set of paths $\G$.
For $||\eta-\eta'||\geq \frac {N}{\log N}$, if there is a good path in
$\{\gie,\,i=1,\ldots,\nd\}$, choose the first such for $\G$;
otherwise, choose $\goe$.
For $||\eta-\eta'||<\frac {N}{\log N}$, if there exists a good site
$\eta''$ in $\on$ such that
$||\eta-\eta''||\geq\frac {N}{\log N}$,
$||\eta'-\eta''||\geq\frac {N}{\log N}$
and there are good paths, one in
$\{\giep,\,i=1,\ldots,\nd\}$ and another in
$\{\giepp,\,i=1,\ldots,\nd\}$, such that the union of
these two good paths is a self avoiding path, select this union
as the path connecting $\eta$ and $\eta'$
in $\G$ (notice that this is a good path since $\eta''$ is good); otherwise, select
$\goe$. Notice that all the paths constructed in this way have length smaller
than $\nd$, so we have the
bound
\beq
\label{eq:ub3}
\t \leq\frac{\nd^2}{\zn}\max_{b=\ass}\ebm\sum_{\get\ni b}\ebs.
\eeq
The next result controls the term $\ebm$.
\bprop
With $\PP$-probability 1, for all but a finite number of indices $N$,
the set of paths $\G$ previously constructed is good.
\eprop
\noindent{\bf Proof}
We will argue that for an arbitrary pair ($\eta,\eta'$) in $\on$,
the probability not to find a good path connecting them as prescribed
in the construction above is not bigger that $e^{-c(e) N}$ for some constant $c(e)$
that depends on $c_e$ which can be chosen as big as we need. Since the number
of such pairs does not exceed $4^N$, choosing $c(e) > \log 4$,
the result follows from the first Borel-Cantelli Lemma.
We assume that $N$ is large enough to keep only the exponential
factor in gaussian estimates.
For pairs of sites more than distance $\frac {N}{\log N}$ apart, using the previous
lemma, there are at least
$\frac {N}{\log N}$ disjoint paths of length at most $N$ connecting them.
The probability for a given site to be bad is no bigger than
$\exp\{-(1+c_e)\log N\}$.
Thus the probability of a given path among the
disjoint ones to be not good is at most $N\exp\{-(1+c_e)\log N\}=
\exp\{-c_e \log N\}$, since all
the paths constructed have length smaller than $N$.
We conclude that the probability that {\it all} the $\frac {N}{\log N}$
disjoint paths constructed in the previous lemma are not good is
at most $\exp\{-c_e N\}$.
For $(\eta,\eta')$ less than distance $\frac {N}{\log N}$ apart,
let $D(\eta,\eta')$ be the coordinates where $\eta$ and $\eta'$ disagree.
Given $\tilde \eta $ that coincides with $\eta$ on $D(\eta,\eta')$ and has
$\frac {N}{\log N}$ discrepancies with $\eta$,
let $\g_{\tilde \eta,\tilde \eta'}$
be the path starting at the site $\tilde \eta$, constructed by flipping the coordinates
in $D(\eta,\eta')$ in increasing order. The probability that the set of visited points
by this path is not good is at most $\exp\{-c_e \log N\}$. Since, for any $\eps >0$, there are
at most $\exp cN^{1-\eps}$ many such $\tilde \eta$s and, as it is easy
to check, all the paths $\g_{\tilde \eta,\tilde \eta'}$ obtained by varying
$\tilde \eta$ are disjoint, we get that the probability that {\it all} the disjoints
paths $\g_{\tilde \eta,\tilde \eta'}$ are not good is at most
$\exp\{-c_e\log N \exp \{cN^{1-\eps}\}\}$ for some positive constant $c$. Therefore, for $N$
large enough, we can find at least one such good site $\tilde \eta$, say $\eta"$
and the corresponding path, say $\g_{\eta",\eta"'}$ with all its visited points good.
By construction, $\eta"'$ coincides with $\eta'$ on $D(\eta,\eta')$ and is
at distance $\frac {N}{\log N}$ apart from it. Therefore we are in the very same
hypothesis as before and we can find good paths $\g_{\eta"',\eta'}$ and
$\g_{\eta,\eta"}$ for $N$ large enough. Now glueing the three
good paths $\g_{\eta,\eta"}$, $\g_{\eta",\eta"'}$ and $\g_{\eta"',\eta'}$, we get
a good path $\g_{\eta,\eta'}$ and by construction this path is self avoiding.
All cases have now been covered and the result is proven. $\bo$
\ep
We will now suppose that $N$ is large enough, how large is an almost
surely finite random variable by the previous result, so that we can
take $\G$ good.
Notice that, in this case, a bad site can appear only at the ends of
any path of $\G$. So, if $b$ contains a bad site, say $\s$, and a
path $\g$ of $\G$ contains $b$, then $\s$ is an end of $\g$ and summing
over all such paths is equivalent to summing over all sites of $\on$
but $\s$.
So, if $b$ contains a bad site,
the term inside the max sign in~(\ref{eq:ub3}) can be bounded
above by $\zn$.
Let $G$ be the collection of bonds of $\hcn$ that contain no
bad site. By the last paragraph,
\beq
\label{eq:ub4}
\frac {\t}{N^2} \leq 1\vee \zn^{-1}\max_{b\in G}\ebm\sum_{\get\ni b}\ebs.
\eeq
Using the fact that $b\in G$, we get
\beq
\label{eq:ub40}
\frac {\t}{N^2} \leq 1\vee \left[ e^{\b \sqrt{2(1+c_e)N\log N}}\t_1\right]
\eeq
where
\beq
\label{eq:ub41}
\t_1\equiv \zn^{-1}\max_{b\in G}\sum_{\get\ni b}\ebs.
\eeq
%%%%%%%%%%%%%%%%%% SUM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Estimates for $\t_1$}
\label{subsec:sum}
We write $\t_1=\t_1^1 +\t_1^2$, where in
$\t_1^1$ the sum in~(\ref{eq:ub41}) is over paths connecting sites at distance
$N/ \log N$ or more apart and in $\t_1^2$ the sum is over paths connecting sites
at distance less than $N/ \log N$ apart.
We consider first $\t_1^1$. The sum can be estimated by
\beq
\label{eq:ub7}
\zn^{-1}\sum_{i=1}^{N}{\sum_{\get\ni b}}^{\!\!\!\!(i)}\ebs,
\eeq
where the sum $\sum^{(i)}$ is over all paths of $\G_i$.
Note that we have replaced here a random set of paths by non random ones.
This follows from the fact that the subset of paths of $\Gamma$
connecting sites which are
more than distance $O(N/ \log N)$ apart is
contained in $\cup_{i=1}^N \G_i$.
We have then the estimate
\beq
\label{eq:ub8}
\t_1^1 \leq N
\zn^{-1}\max_{i}\max_{b}{\sum_{\get\ni b}}^{\!\!\!\!(i)}\ebs.
\eeq
The random variables $$Z_N(i)\equiv \max_{b}{\sum_{\get\ni b}}^{\!\!\!\!(i)}\ebs,$$
$i=1,\ldots,N,$ have the same distribution. It will suffice to
consider the first one.
We will need some further notation.
Given a bond $b=\ass$, let $\ell=\ell(b)$ be the coordinate where
there is a discrepancy.
Given a coordinate $j$ and a site $\s$,
define the collections of sites
\beqn
\label{eq:ojm}
\ojm(\s)\=\{\eta\in\on:\eta(i)=\s(i),\,i=j,\ldots,N\}\\
\label{eq:ojp}
\ojp(\s)\=\{\eta\in\on:\eta(i)=\s(i),\,i=1,\ldots,j\}.
\eeqn
Now
\beq
\label{eq:prod1}
{\sum_{\get\ni b}}^{\!\!\!\!(1)}\ebs=\sum_{\eta\in\olm(\s)}e^{-\b H(\eta)}
\sum_{\eta\in\olp(\s')}e^{-\b H(\eta)},
\eeq
since the paths in $\G_1$ through $b$ connect sites in $\olm(\s)$
to sites in $\olp(\s')$.
Thus
\beqn
\nonumber
&&\!\!\!\!\max_{b}{\sum_{\get\ni b}}^{\!\!\!\!(1)}\ebs\\
\label{eq:prod2}
\=\!\!\!\max_j\max_{b=\ass:\ell(\s,\s')=j}
\sum_{\eta\in\oj}e^{-\b H(\eta,\s_j,\ldots,\s_N)}
\sum_{\eta'\in\onj}e^{-\b H(\s_1',\ldots,\s_j',\eta')}
\eeqn
where $\oi=\{1,-1\}^i$.
Therefore calling
\beq
\label{eq:prod20}
Z_{j-1}(\xi,\zeta')=\sum_{\eta\in\oj}e^{-\b H(\eta,\xi,\zeta')}
\eeq
and
\beq
\label{eq:prod21}
Z_{N-j}(-\xi,\zeta)=\sum_{\eta'\in\onj}e^{-\b H(\zeta,-\xi,\eta')},
\eeq
the right hand side of (\ref{eq:prod2}) equals
\beq
\label{eq:prod3}
\max_j\max_{\xi=\pm1}\max_{\zeta'\in\onj}
Z_{j-1}(\xi,\zeta')
\max_{\zeta\in\oj}Z_{N-j}(-\xi,\zeta).
\eeq
\ep
%%%%%%%%%%%%%%%%%% OP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We now estimate $Z_{j-1}(\xi,\zeta')$ and
$Z_{N-j}(-\xi,\zeta)$
in the same way Olivieri and Picco
estimated the REM partition function
(see Section III in \cite{kn:OP} through to equation~(III.17)),
rather using the exponential Markov inequality than the simple
one in order to be able to control the max signs
in~(\ref{eq:prod3}) that involve an exponential number of terms.
However, this section is self contained.
Let $j$ and $\zeta'\in\onj$ be fixed and
take $\xi=1$ (for definiteness).
Let $M$ be a positive integer to be chosen later
and make a partition of the real line with the intervals
\beqnn
\D_{0}\=\left(-\infty,\bc\frac{N}{M}\right],\\
\D_k\=\left(\bc\frac{kN}{M},\bc\frac{N(k+1)}{M}\right],
\quad\mbox{if $1\leq k\leq M$},\\
\D_{M+1}\=\left(\bc(1+1/M)N,+\infty\right).
\eeqnn
Now write
\beqn
\nonumber
&&Z_{j-1}(\xi=1,\zeta')=\sum_{\s\in\oj}\sum_{k=0}^{M+1}\1_{\D_k}(-H(\s,1,\zeta'))
e^{-\b H(\s,1,\zeta')}\\
\label{eq:br}
\le 2^{j-1}e^{\bc\b N/M}+\sum_{k=1}^{M}N_ke^{\bc\b(k+1)N/M}
+ N^\ast e^{-\b H(\sz)},
\eeqn
where
$$
N_k=N_k(\zeta',i=1,\xi=+1)=\sum_{\eta\in\oj}\1_{\D_k}(-H(\eta,1,\zeta'))
$$ for
$k=0,\ldots,M$ and $$N^\ast=\sum_{\s\in\o}\u_{\D_{M+1}}(-H(\s)).$$
Let us suppose now that $j-1=\a N$ and focus on the middle
sum in~(\ref{eq:br}).
Let $p_k$ denote $\PP(-H(\s)\in\D_k)$.
We then have
\beq
\label{eq:pk}
\bc \frac {\sqrt N}{M}2^{-\frac{(k+1)^2}{M^2}N}\rk E(N_k))\leq e^{-\lk 2^{\a N}},
\eeq
where
\beqn
\label{eq:rk}
\rk\=2^{(\frac{(k+1)^2+1}{M^2}-\a)^+N+2}\\
\nonumber
\lk\=\rk\pk\log\frac{\rk(1-\pk)}{1-\rk\pk}-
\log\left[1-\pk+\frac{\rk\pk(1-\pk)}{1-\rk\pk}\right],\\
\nonumber
&&\mbox{if}\quad\rk\pk<1,\\
\label{eq:lk}
\=\infty,\quad\mbox{otherwise.}
\eeqn
In any case, we have $\lk\geq c\rk\pk$ for some positive constant $c$
and thus,
\beq
\label{eq:exp2}
\PP(N_k>\rk E(N_k))\leq \exp\{-c\rk\pk 2^{\a N}\}.
\eeq
Also
$$\rk\pk 2^{\a N}\geq 2^{N/M^2}.$$
Let the reader be reminded that $N_k=N_k(\zeta',j,i=1,\xi=1)$
and that the previous estimates are done for a fixed configuration
$\zeta'\in\onj$ with $j\in \{1,\dots,N\}$,
$i\in \{1,\dots,N\}$ and $\xi=\pm 1$.
Recalling~(\ref{eq:prod3}), we have to make this
estimates uniformly with respect to all those possible values.
Since there are not more
than $2N^2 2^N$ random variables that come into account, we need to have a
probability estimate in~(\ref{eq:exp2}) that compensates this factor.
This suggests that we choose $M$ in such a way that $2^{N/M^2}\geq c_u N$
for a positive constant $c_u$ that will be chosen later.
That is, we take
\beq
\label{eq:lk2}
M=M(N)= \sqrt{ \frac{N\log 2}{\log c_u N}}
\eeq
and we get, for all $\eps>0$,
\beqn
\nonumber
&\PP&\!\!\!\!\left[\max_i\max_j\max_{\zeta'\in\onj}\max_{1\leq k\leq M}
N_k(\zeta',i,\xi)>\rk E(N_k)\right]\\
\label{eq:lk3}
\le2N^2 M(N)2^Ne^{-c_u N}\leq e^{-\eps N}
\eeqn
choosing $c_u> \log 2 +2 \eps$.
We conclude that the middle sum in~(\ref{eq:br})
is bounded above by constant times
\beqn
&& \frac {\sqrt{N}}{M}\sum_{k=1}^{M}\rk 2^{\a N} 2^{-\frac{k^2}{M^2}N}
e^{\bc\b(k+1) N/M}\\
\label{eq:br2}
\= \frac {\sqrt{N}}{M}\sum_{k=1}^{\sqrt{\a M^2-1}}
e^{(\a-k^2/M^2)\log2+\bc\b(k+1) N/M}
+ \frac {\sqrt{N}}{M} \sum_{k=\sqrt{\a M^2-1}}^{M}e^{\bc\b(k+1) N/M}2^{N/M^2}\\
\label{eq:br4}
\le \sqrt {N}\left(\sup_{x\in[0,1]}e^{\a G_{\b/\sqrt\a}(x)N}e^{\bc\b N/M}
+e^{\bc\b(1+1/M)N}2^{N/M^2}\right),
\eeqn
where $G_\b(x)=\bc\b x+\frac{\bc^2}{2}(1-x^2)$, except for an event
of probability
not bigger than $\exp\{-\eps N\}$.
The sup term in~(\ref{eq:br4}) equals $\exp\{\a F(\b/\sqrt\a)N\}$,
where
\beqn
\label{eq:F1}
F(x)\=(x^2+\bc^2)/2,\quad\mbox{if $0\leq x\leq\bc,$}\\
\label{eq:F2}
\=\bc x,\quad\mbox{if $x\geq\bc$}
\eeqn
and $\a F(\b/\sqrt\a)|_{\a=0}\equiv0.$
So, uniformly in $i,j,\xi, \zeta'$ we have
\beq
\label{eq:f2}
\max_{\zeta'\in\onj}Z_{j-1}(\zeta',\xi)
\leq cMe^{\a F(\b/\sqrt\a)N}e^{\bc\b N/M}
+Me^{\bc\b(1+1/M)N}2^{N/M^2}+ N^\ast e^{-\b H(\sz)}
\eeq
with $\PP$-probability not smaller than $1-\exp\{-\eps N\}$,
where we have absorbed the factor $2^{\a N}$ in~(\ref{eq:br}) by changing the
constant $c$, since
$2^{\a N} \leq e^{\a F(\b/\sqrt\a)N}$, as it can be easily checked.
Notice that $\PP$-almost surely, $N^\ast=0$ for all but a finite number of indices $N$, since
$$P(-H(\s)>(1+1/M)N\bc)\leq 2^{-(1+1/M)^2N}.$$
After a similar reasoning with
$$
Z_{N-j}(-\xi,\zeta)=
\max_{\zeta\in\oj}\sum_{\eta'\in\onj}e^{-\b H(\zeta,-1,\eta')},
$$
we conclude that $\PP$-almost surely for all but a finite number of indices
$N$
\beq
\label{eq:ub9}
\t_1^1 \leq N\zn^{-1}
\max_{0\leq\a\leq1}\psi(\a,N,M)\psi(1-\a,N,M),
\eeq
where
\beqnn
\psi(\a,N,M)\=cMe^{\a F(\b/\sqrt\a)N}e^{\bc\b N/M}
+Me^{\bc\b(1+1/M)N}2^{N/M^2}\\
\le e^{c\sqrt{N\log N}}e^{\left[\a F(\b/\sqrt\a)\vee\bc\b\right]N}
\eeqnn
and $c$ is a positive constant, not necessarily the same everytime
it appears.
Collecting, we get that
\beq
\label{eq:ub111}
\frac {1}{N} \log \t_1^1 \leq \max_{0\leq\a\leq1}\Psi(\a,\b)-F(\b)
+ c\b{\sqrt \frac{\log N}{N}}+c'\frac{\log N}{N}.
\eeq
where $$\Psi(\a,\b)=[\a F(\frac{\b}{\sqrt\a})+
(1-\a)F(\frac{\b}{\sqrt{1-\a}})]\vee
[\a F(\frac{\b}{\sqrt\a})+\bc\b]\vee2\bc\b$$
and $c'$ is a positive constant.
Now one checks that $\max_{0\leq\a\leq1}\Psi(\a,\b)-F(\b)\leq\bc\b$
for all $\b$.
Therefore, we get that $\PP$-almost surely for all but a finite number of indices $N$
\beq
\label{eq:ub1131}
\frac {1}{N} \log \t_1^1 \leq \b\bc +
c\b{\sqrt \frac{\log N}{N}}+c'\frac{\log N}{N}
\eeq
for some constants $c$, $c'$ and all $\b$.
We consider now the term $\t_1^2$.
We estimate it in two different ways, one for $\b$ close to $0$,
another for $\b$ away from $0$.
The first bound follows from the fact that the sum is over a
set of paths connecting sites in a
hypercube of dimension at most $(N/ \log N)$ around $b$, so we have
\beq
\label{eq:ub1132}
\t_1^2 \leq \zn^{-1}e^{cN/ \log N}e^{-2\b H(\sz)}
\eeq
Unrestricting the paths to go through $b$, we get the other bound
\beq
\label{eq:ub1133}
\t_1^2 \leq \zn^{-1} \max_{\eta\in\on}
\sum_{\eta':||\eta'-\eta||<\frac{N}{\log N}}e^{-\b H(\eta')}.
\eeq
Notice that~(\ref{eq:ub1133}) is very similar to~(\ref{eq:prod20}),
with a sum over less than $2^{\a N}$ (independent)
terms, with an arbitrary $\a>0$ (for $N$ large
enough). We can thus proceed to estimate~(\ref{eq:ub1133}) in the
same way as we did~(\ref{eq:prod20}) to get the
bound~(\ref{eq:f2}) from which the right hand side
of~(\ref{eq:ub1131}) follows as an upper bound
for the log of~(\ref{eq:ub1133}) divided by $N$ when $\b>\b_0$,
where $\b_0$ is a suitable positive fixed number close to $0$ (the bound is in fact
true for $\b>0$, but then $N$ large enough will depend on $\b$).
For $\b$ close to $0$, we use~(\ref{eq:ub1132})
to get
\beq
\label{eq:ub1134}
\frac {1}{N}\log \t_1^2 \leq 2\bc\b-F(\b)+c/\log N
\eeq
which is negative for $N$ large enough.
This finishes the estimation of $\t_1^2$.
The bound~(\ref{eq:ub1131}) is seen to carry to $\t$ by~(\ref{eq:ub40}).
Together with the previous results, this proves the following.
\bprop
\label{prop:ub}
For all $\b$, there exist finite constant $c$ and $c'$ such that,
with $\PP$-pro\-ba\-bi\-li\-ty~1,
for all but a finite number of indices $N$,
we have
\beq
\label{eq:ub1141}
\frac {1}{N} \log \t \leq \b\bc
+ c \sqrt {\frac {\log N}{N}}+c'\frac{\log N}{N}.
\eeq
In particular,
\beq
\label{eq:ub}
\limsup_{\nd\to\infty}\frac{1}{\nd}\log\t\leq\bc\b.
\eeq
\eprop
\ep
\brm
The argument leading to inequality~(\ref{eq:ub1131}) proves a
weak form of the inequality
\beq
\label{eq:det}
\sum_{\eta\in\oj}e^{-\b H(\eta,\xi,\zeta')}
\sum_{\eta'\in\onj}e^{-\b H(\zeta,-\xi,\eta')}
\leq e^{-\b H(\sz)}\zn
\eeq
for all $1\leq j\leq N$, $\zeta\in\oj$, $\xi=\pm1$ and $\zeta'\in\onj$.
Namely, it is true almost surely after taking logs,
dividing by $N$ and passing to the limit as $N\to\infty$.
One might wonder whether
a stronger, deterministic form of this inequality is true.
It would simplify the long probabilistic
argument of the last subsubsection and make extensions to
similar models easier.
But this is unfortunately not the case, as the following example
shows. Let $N$ be an odd number, $j=(N+1)/2$, $\xi=-1$ and define
\beqnn
x(\eta,-1,-1,\ldots,-1)\=1\quad\mbox{for all $\eta\in\oj$},\\
x(-1,\ldots,-1,1,\eta')\=1\quad\mbox{for all $\eta'\in\onj$},\\
x(\s)\=0\quad\mbox{in all other cases.}
\eeqnn
Then it is clear that the left hand side in~(\ref{eq:det}) (with
the Boltzmann factors replaced by $x(\cdot)$) equals $2^{N-1}$
while the right hand side equals $2^{(N+1)/2}$.
\erm
Combining the bounds of Propositions~\ref{prop:lb} and~\ref{prop:ub},
we have the following result.
\bteo
\label{teo1}
For all $\b$, there exist finite constants $c$, $c'$ and
$c''$ such that,
with $\PP$-pro\-ba\-bi\-li\-ty~1,
for all but a finite number of indices $N$, we have
\beq
\label{eq:ulbteo}
\b\bc
- c\b \sqrt {\frac {\log N}{N}}\leq\frac {1}{N} \log \t \leq \b\bc
+c' \b \sqrt {\frac {\log N}{N}}+c''\frac{\log N}{N}.
\eeq
In particular,
\beq
\label{eq:lim}
T(\b):=\lim_{\nd\to\infty}\frac{1}{\nd}\log\t
\eeq
exists with probability 1 and equals $\bc\b$.
\eteo
\brm
Although the REM as an equilibrium model exhibits a (third order)
phase transition at $\b=\bc$,
this leaves no trace in the dynamical model (as regards $T$),
neither at $\bc$ nor
elsewhere. We might then say that
there is no dynamical phase transition for the REM under Metropolis
dynamics. We did not work out the details, but believe this is so
also for other (local) Glauber dynamics. In an appendix to the paper,
we consider a modification of Metropolis so that it is a global
dynamics for which~(\ref{eq:lim}) has a third order phase transition
at $\bc$.
\erm
\brm
An explanation for the result of Theorem~\ref{teo1}
is as follows. Since the energies of the REM are independent,
the minimum one is surrounded by order 1 energies that can have fluctuations
of order $\sqrt {N \log N}$.
Therefore, the time
to exit the ground state under a local dynamics is of the order
of $\exp{\bc\b N}$ and the fluctuations are of order $\exp \sqrt {N\log N}$.
This should be the main contribution to
$\t$ to leading order. In the high temperature regime,
the dominant contribution to the free energy comes from energies
that are larger than the ground state, but the entropy comes into play
to give a smaller free energy. However,
with the local dynamics, the stochastic process is trapped into the ground
states, that do not contribute to the statics, for a time which is bigger
than all the exit times of the other states.
\erm
By using equations (\ref{eq:equi}) and (\ref{eq:BTOP1}),
it is not difficult to check the following result.
\bteo
\label{teo2}
There exists a positive constant $c$ such that
for all $\eps>0$, all $\b>0$ and all $t'>0$, if
\beq
t_N(t')=e^{N\b\b_c+ c\sqrt{N\log N}}
\left[\frac N2(F(\b)+\b\b_c)+\frac {\b}{2\b_c}(\log N +\eps)+ t'\right]
\eeq
then, with $\PP$-probability 1, for all but a finite number of indices $N$
we have
\beq
\label{eq:equith}
sup_{\s}\|P_{t_N(t')}(\s,\cdot)-\mn(\cdot)\|_{var} \leq e^{-t'}.
\eeq
\eteo
\brm For the proof of this theorem, we need only
an upper bound for the square root term in
(\ref{eq:equi}), so a lower bound on $\mu(\s)$ is needed.
Since we want a result which is
uniform with respect to the initial conditions, we cannot
exclude a priori to start with a
configuration which corresponds to the spin configuration
that makes $H(\s)$ maximal.
Even if the Gibbs measure of such configuration is
very small. Also, we cannot
expect to have any cancellation of the error terms that are
of order $\log N$. This is because a part of
the errors terms are coming from the fluctuations of
a Gibbs factor
computed on a maxima and the other part is coming
from the fluctuations of the partition
function, the latter coming from the fluctuations
of the minimum.
\erm
%%%%%%%%%%%%%%%%%%%%%% SECTION 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A Global Dynamics}
\setcounter{equation}{0}
\label{sec:glo}
In this chapter, we consider a {\em global} Metropolis dynamics,
where the system can make all possible jumps, not only nearest
neighbor ones as in the {\em local} dynamics.
When scaled as for the local dynamics of the previous sections,
$\t$ is shown to exhibit a phase transition as a function
of $\b$ (see Theorem~\ref{teo:gd} below).
Consider the following continuous-time Markov chain in $\on$.
\beqn
\nonumber
\pss\=2^{-N}\exp\{-\b(\hsp-\hs)^+\},\quad\mbox{if}\quad \sp\ne\s,\\
\label{eq:gldyn}
\= 1-\sum_{\spp\ne\s}\pssp,\quad\mbox{if}\quad\sp=\s,
\eeqn
This is an irreducible, reversible with respect to $\mn$
chain and thus we can apply the
variational characterization of the gap~(\ref{eq:tau}).
We use the same trial function for $\t$ as in Subsection~\ref{subsec:lb}
to obtain
\beq
\label{eq:lbg}
\t\geq\tfsz=\frac{2^Ne^{-\b H(\sz)}}{\zn}.
\eeq
The upper bound is much simpler to derive than the corresponding
local one, either directly from the variational characterization
or by using the Poincar\'e inequality~(\ref{eq:ub1}). We choose
the latter, using the set of paths
$$\G=\{(\s,\s'):\,\s,\s'\in\on,\,\s\ne\s'\}$$
constituted of all bonds in $\on$ (notice that the global transition
probabilities are nonzero over these) to get
\beq
\label{eq:ubg}
\frac{2^N}{\zn}\max_{\s\ne\s'}\ebm e^{-\b (H(\s)+H(\s'))}
=\frac{2^Ne^{-\b H(\sz)}}{\zn}.
\eeq
We conclude from~(\ref{eq:lbg}) and~(\ref{eq:ubg}) that
\beq
\label{eq:ext}
\t
=\frac{2^Ne^{-\b H(\sz)}}{\zn}.
\eeq
Therefore, since $\lim_{N\ar\infty}F_N(\b)=F(\b)$ $\PP$-almost surely,
we get the following result.
\bteo
\label{teo:gd}
$\PP$-almost surely,
\beq
\label{eq:exlt}
T(\b)=\lim_{N\to\infty}(\log\t)/N=\bc\b+\bc^2/2-F(\b),
\eeq
where $F$ is given by~(\ref{eq:F1}) and~(\ref{eq:F2}) above.
\eteo
\brm
Since $F$ undergoes a third order phase transition in $\b=\bc$,
then so does $T$.
\erm
\brm
The identity~(\ref{eq:ext}) is valid for the same dynamics
for any spin system. Applied to the Ising model, it shows
that $T$ inherits its phase transition (whenever that occurs).
\erm
To consider the error terms, we introduce the quantity
\beq
\label{eq:gd1}
{\cal T}(\b)\equiv \log \left[\t e^{-NT(\b)}\right].
\eeq
The first result is an {\em almost sure} one.
\bteo
\label{teo:gd2}
If $\b\geq\b_c$, then
\beq
\label{eq:gd0}
{\cal T}(\b)\leq 0\quad\mbox{for all $N$}
\eeq
and, with $\PP$-probability 1,
\beq
\label{eq:gd2}
\liminf_{N\to\infty}\frac{ {\cal T}(\b)}{\log\log N}\geq-\frac{\b}{\b_c}.
\eeq
If $\b<\b_c$, then, with $\PP$-probability 1,
\beq
\label{eq:gd3}
\limsup_{N\to\infty} \frac {{\cal T}(\b)}{\log N}
=-\liminf_{N\to \infty} \frac {{\cal T}(\b)}{\log N}=\frac{\b}{2\b_c}.
\eeq
\eteo
\brm
The important fact is that the almost sure finite volume corrections
to the free energy, that are of order $\log N/N$
in the low temperature regime, are coming precisely from the
fluctuations of the ground states, and there is an exact cancellation
of these fluctuations when $\t$ is considered. This gives fluctuations
that are of order at most $\log\log N/N$ for $T(\b)$.
In particular this implies that there is also a phase transitions in the errors
terms.
\erm
One could be interested in the error terms in probability.
In this case the results are simpler.
\bteo
\label{teo:gd3}
If $\b\geq \b_c$, then
\beq
\label{eq:gd4}
\lim_{N\to\infty} \frac {{\cal T}(\b)}{\log N}=0\quad
\mbox{in $\PP$-probability.}
\eeq
\noindent If $\b<\b_c$, then
\beq
\label{eq:gd5}
\lim_{N\to\infty} \frac {{\cal T}(\b)}{\log N}=-\frac{\b}{2\b_c}\quad
\mbox{in $\PP$-probability.}
\eeq
\eteo
\noindent{\bf Proof of Theorem \ref{teo:gd2}}
We consider first the case where $\b<\b_c$. Using the explicit formula
for $F(\b)$ see (\ref{eq:F1}) and (\ref{eq:F2}) we get
\beq
\label{eq:gd6}
{\cal T}(\b)=-\b(\hsz +N\b_c) -\log \zn e^{-NF(\b)}.
\eeq
Using the proposition 5 in (\cite{kn:OP}), that is (\ref{eq:HT}), we get that
with $\PP$-probability 1, for all but a finite number of indices $N$
the last term is of order at most $Ne^{-\lambda(\b)N}$.
For the first term, using (\ref{eq:lb04}) we get
with $\PP$-probability 1, for all but a finite number of indices $N$
\beq
\label{eq:gd7}
{\cal T}(\b)\geq -\frac{\b}{2\b_c}(1+\eps) \log N.
\eeq
On the other hand we have also, with $\PP$-probability 1
\beq
\label{eq:gd8}
\liminf_{N\to \infty} \frac {{\cal T}(\b)}{\log N}=
-\frac{\b}{2\b_c}.
\eeq
This is a direct consequence of the proof of the formula (2.7) in \cite{kn:GMP}
(see pages 520-521 there).
Moreover we have
with $\PP$-probability 1, for all but a finite number of indices $N$
\beq
\label{eq:gd9}
{\cal T}(\b)\leq \frac{\b}{2\b_c}(1+\eps) \log N,
\eeq
which is a consequence of the following estimate that is easy to check.
\beq
\label{eq:gd91}
\PP\left(-\hsz\leq \b_c N(1-\frac {\log N}{2\b_c^2 N}-\frac{\log\log N^{1+\d}+
\log {\sqrt {2\pi}}}{\b_c^2 N})\right)
\leq \frac {c}{N^{1+\d}}
\eeq
for some positive constant $c$.
Moreover it is not too difficult to see that we have, with $\PP$-probability 1
\beq
\label{eq:gd10}
\limsup_{N\to \infty} \frac {{\cal T}(\b)}{\log N}=
\frac{\b}{2\b_c},
\eeq
from which we get (\ref{eq:gd3}).
For the proof of~(\ref{eq:gd0}), we use again the
explicit formula for $F(\b)$. If $\b\geq \b_c$ we have
\beq
\label{eq:gd11}
{\cal T}(\b)= -\log \zn e^{\b \hsz}.
\eeq
Since $\zn e^{\b \hsz}\geq 1$, we get ${\cal T}(\b)\leq 0$.
The proof of~(\ref{eq:gd2}) is just a little more involved
and will make use of results of \cite {kn:OP} with some modifications.
We define as in \cite {kn:OP} (page 135), the real interval
\beq
\label{eq:gd12}
I_1=\left[ N\b_c\left( 1-\frac {1}{2\b_c^2} \frac {\log N}{N}
+\frac {(1+\eps)}{\b_c^2}\frac {\log\log N}{N}\right),(1+\eps)N\b_c \right].
\eeq
Then we have
\beq
\label{eq:gd13}
\sum_{\sigma}e^{-\b(\hs-\hsz)}\1_{I_1}(-\hs)
\leq\sum_{\sigma}\1_{I_1}(-\hs),
\eeq
since $\hs-\hsz\geq 0$.
Now is it easy to check that
\beq
\label{eq:gd14}
2^N\E(\1_{I_1}(-\hs))\leq \frac {1}{\b_c}\left(\frac {1}{\log N}\right)^{1+\eps}.
\eeq
Using now the following nice, but not known as it deserves, inequality, which is a
simple consequence of the Markov inequality,
\beq
\label{eq:gd15}
\PP(S_n\geq r)\leq e\left(np(n)\right)^r,
\eeq
where $S_n=\sum_{i=1}^Nx_i$ and $(x_i)_{i=1,\dots,N}$ is a family of independent
identicaly
distributed random variables with values in ${0,1}$ and $\PP(x_1=1)=p(n)$,
we get
\beq
\label{eq:gd16}
\PP\left(\sum_{\sigma}\1_{I_1}(-\hs)\geq \frac {\log N}{\log\log N}\right)
\leq \frac {1}{N^{1+\eps}}.
\eeq
We consider now the interval
\beq
\label{eq:gd17}
I_2=(-\infty,
N\b_c( 1-\frac {1}{2\b_c^2} \frac {\log N}{N}
+\frac {(1+\eps)}{\b_c^2}\frac {\log\log N}{N})].
\eeq
Using Lemma 7 in \cite {kn:OP}, we have, with $\PP$-probability 1, for all
large enough $N$
\beq
\label{eq:gd18}
\sum_{\s}\1_{I_2}(-\hs)e^{-\b\hs}\leq
\frac{(1+\eps)}{\b_c}\log\log N e^{N\b\b_c(1-\frac{\log N}{2\b_c^2 N})}.
\eeq
Therefore, collecting on the one hand (\ref{eq:gd91})
together with (\ref{eq:gd18})
and on the other hand (\ref{eq:gd16}) together with (\ref{eq:gd13}),
using the first Borel-Cantelli Lemma, we get
that, with $\PP$-proba\-bi\-li\-ty~1, for all large enough $N$
\beq
\label{eq:gd20}
\zn e^{\b \hsz}\leq
\frac {\log N}{\log\log N} +
\frac{(1+\eps)}{\b_c}\log\log N e^{\frac{\b}{\b_c} \log\log N^{1+\d}},
\eeq
from which we get immediately
\beq
\label{eq:gd21}
{\cal T}(\b)\geq - \frac {\b}{\b_c} \log\log N - \log\log\log N
\eeq
and this concludes the proof of the Theorem \ref{teo:gd2}.
The proof of Theorem \ref{teo:gd3} is immediate.
We leave as an exercise to the reader to state and prove the
corresponding of Theorem~\ref{teo2} for this dynamics.
%%%%%%%%%%%%%%%%%%%%%% APPENDIX %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
\section{Microscopic Representation}
\setcounter{equation}{0}
\label{sec:mic}
We establish here the microscopic representation for the REM hamiltonian
mentioned in the introduction. This representation already appears in
Derrida's papers without proof. We give an argument here for completeness.
\bprop
Let ${\cal H} = \{H(\s),\s\in\o\}$ be defined by Equation~(\ref{eq:mic}),
where $\{\ja,\,\a\subset\L\}$ is a family of i.i.d. standard gaussian random
variables.
Then ${\cal H}$ is a family of i.i.d.~gaussian random variables with mean $0$
and variance $N$.
\eprop
\noindent {\bf Proof}
The gaussianness, correct marginal mean and variance are clear. It suffices
thus to establish independence. It is enough to show that the matrix
\beq
\{\s_\a;\,\s\in\o,\a\subset\L\}
\eeq
is orthogonal, that is,
\beq\sum_{\a\subset\L}\sa\sal=0\eeq
for all distinct $\s,\sl\in\o$.
Given $\s,\sl\in\o$ with $\s\ne\sl$, let $\D$ denote the
(nonempty) set where $\s$ and $\sl$ disagree, that is
\beq\D=\{i\in\L:\si\ne\sil\}.\eeq
We have
\beq\sum_{\a\subset\L}\sa\sal=\sum_{\a\subset\L}(-1)^{|\a\cap\D|}.\eeq
The last sum can be rewritten as
\beq\sum_{k=0}^M\,\,\sum_{\a\subset\L:|\a\cap\D|=k}(-1)^k,\eeq
where $M=|\D|$. It then equals
\beq\sum_{k=0}^M g_\D(k)(-1)^k,\eeq
where $g_\D(k)$ is the number of distinct subsets $\a$ of $\L$
intersecting $\D$ at
exactly $k$ points. There are $k$ choices out of $M$ in $\D$, which yields
$M\choose k$ possibilities for $\a\cap\D$,
and total freedom in $\L\backslash\D$, which yields $2^{N-M}$
possibilities for $\a\backslash\D$. Thus
\beq g_\D(k)={M\choose k}\, 2^{N-M}.\eeq
We finally have
\beq
\sum_{\a\subset\L}\sa\sal=2^{N-M}\sum_{k=0}^M {M\choose k} (-1)^k
=2^{N-M}(1-1)^M=0,
\eeq
since $M>0$. The result is proven. $\bo$
\vspace{.5cm}
\section{A Domination Lemma}
\setcounter{equation}{0}
\label{sec:dom}
It is enough for the purposes of supporting the argument
in the proof of Proposition~\ref{prop:lb} to consider the following
setup. Let $X_1,\ldots,X_{n+1}$ be a sequence of continuous
i.i.d.~random variables with distribution function $F$
and let $M_n$ denote their maximum
(which is almost surely unique) and let $M$ denote the corresponding
index (so that $M_n=X_M$). Define $Y_i=X_i$ if $ij)\\
\=\sum_{j=1}^{n+1}\int
P(X_ij)\,dF(x)\\
\=(n+1)\int \prod_{i=1}^n P(X_1