\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}
\date{}
\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{\+}{\!\!&+&\!\!} 
%\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 or energy function
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 and we will adopt it in the next section.

The equilibrium statistical mechanics of the REM  has been much studied,
e.g., 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 the (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 twice 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} on Section~\ref{sec:su})
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}.  

Besides being of its own interest, spin glass dynamics has been studied
in the hope of getting a better understanding of the phase picture at
equilibrium. As a matter of fact the early (non-rigorous) paper by
Sompolinsky and Zippelius on dynamics for the SK model
(\cite {kn:SZ}, \cite {kn:MPV}) takes mainly this point of view.
They considered a {\em soft spin} approach (real valued spin variables
in a confining bistable potentials) so that they could work with
quantities varying continuously and write down a Langevin equation.
Part of their theory  has been made rigorous by Ben Arous and Guionnet
(\cite {kn:BG1}, \cite {kn:BG2}, \cite {kn:G}). Their study is for time
scales shorter than the ones we are dealing with.

The physics literature on the subject of dynamics of disordered systems is
now very large and we will not make any reference to it here. The interested
reader is referred to Parisi's Varenna 1996 Lectures for an introductory
discussion and some bibliography (\cite {kn:P}).

On a rigorous ground there are at least two type of results one may
try to prove. Starting directly with an infinite system the goal is
to understand anomalous (e.g. non-exponential) relaxation to equilibrium.

Almost sure and average results in this direction have been obtained
by Gielis and Maes (\cite {kn:GM}), Cesi, Maes and Martinelli (\cite {kn:CMM1},
\cite {kn:CMM2}) and Guionnet and Zegarlinski (\cite {kn:GZ1}, \cite {kn:GZ2}).

We note here that some of these results are valid only for (disordered)
ferromagnets, while others apply to spin glasses as well.

Here we take a complementary point of view and ask questions on the
asymptotic behaviour of a dynamical quantity (the autocorrelation time)
in the infinite volume limit. A priori our results are consistent with
non-exponential relaxation in infinite volume. We plan to investigate the
relationship between the asimptotics of the gap and infinite volume
behaviour in a forthcoming paper.

\ep


The rest of the paper is organized as follows. In the next section we describe
the model in detail and introduce the spectral gap of the Metropolis dynamics
in its variational
characterization and its relation with relaxation time. In Sections 3 and 4, we 
derive upper and lower
bounds for the inverse of the gap, respectively, leaving Section 5 for the
the summing up of those in Theorem~\ref{teo1} and remarks. In Section 6
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

We recall now 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 sections, we derive  upper and lower bounds for $\t$ that
are sharp to logarithmic order. 


%%%%%%%%%%%%%%%% SECTION 3 %%%%%%%%%%%%%%%%%%%%%%%%

\section{Lower Bound for the Inverse of the Gap}
\setcounter{equation}{0}
\label{sec:lb}

From~(\ref{eq:tau}), 
as is 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

\brm
Before going to the proof, let us motivate the result by arguing heuristically that $\tau$ 
should be bigger than the time to exit any initial configuration, in particular the
configuration of least energy. Under Metropolis, this should be of the order of the 
exponential of the absolute value of the difference of the global minimum energy to the
minimum energy among configurations neighboring the least energy one. The right hand 
side of~(\ref{eq:lb}) follows. Although a rigorous proof could be written along 
these lines, we follow a different route, using~(\ref{eq:tau}) instead.
\erm

\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 $x<y$, where $F_{X_1}$ is the distribution function of $X_1$.

We break the integral above into an integral over $x<0$ and another
over $x>0$. 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





%%%%%%%%%%%%%%%%  SECTION 4 %%%%%%%%%%%%%%%%%%%%%%%%

\section{Upper Bound}
\setcounter{equation}{0}
\label{sec:ub}

In this section, we derive
the upper bound for the inverse of the gap. The 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  the section is devoted to estimate the right hand side of~(\ref{eq:ub2}).
Since the asymptotics for $\zn$ are known~(\ref{eq:HT}-\ref{eq:BTGMP3}),
we concentrate on the max expression.

We  will choose $\G$ so as to have the main contribution come from the sum. The
factor $\ebm$ will contribute only an error term. The motivation for the choice is
the following. Suppose $\ebm$ does not contribute anything, so we are 
left with
\beq
\label{eq:ub2a}
\max_{b=\ass}\sum_{\get\ni b}|\get|\ebs.
\eeq
If we choose $\G$ as $\G_1$ defined in~(\ref{eq:gi}) below, we first notice that
the longest path in $\G$ will have length $N$, so we can ignore this contribution
to leading order. We are left with
\beq
\label{eq:ub2b}
\max_{b=\ass}\sum_{\get\ni b}\ebs.
\eeq
For any bond $b$, the sum in~(\ref{eq:ub2b}) factors in a product of two sums which
can be seen as (sub)partition functions (see~(\ref{eq:prod1}) below).
An estimation along the lines of  an argument of  Olivieri and Picco
to estimate the REM partition function (see Subsubsection~\ref{sssec:op})
produces a sharp bound (see~(\ref{eq:ub1131}) below, compare to the lower
bound~(\ref{eq:lb})).

 
In order to control $\ebm$ in~(\ref{eq:ub2}) and work out a rigorous argument
from the above motivation, the strategy is to have a complete set of paths $\G$
that avoid as often as possible
points of the hypercube that have high (positive) energies. 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.
In the $\G$ we finally choose, high energies occur
only at the ends of the 
paths and therefore their contribution are depressed by the factor $\ebs$
appearing in~(\ref{eq:ub2}).

High energy points will be relatively rare, but not so rare that we can rule 
them out of the interior of the paths of $\G_1$. This motivates the consideration
of the family $\{\G_i,\,i=1,\ldots,N\}$ (see~(\ref{eq:gi}) below), 
which is formed with "copies" 
of $\G_1$. Choosing from this family, we guarantee the absence of interior high
energy points in paths of $\G$.

The details of the construction and the above mentioned estimation, as well as how
it survives with extra terms of lower order only, will be given in the next subsections
and subsubsections of this section.
 

%%%%%%%%%%%%%%%%%% GAMMA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{A choice of $\G$}
\label{ssec: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
\label{eq:gi}
\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 than $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 least $\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 almost surely, 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 almost surely 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 so as to make (almost)
sure, by the previous result, 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}\sum_{\get\ni b}\ebs. 
\eeq


%%%%%%%%%%%%%%%%%% SUM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Estimates for $\t_1$}
\label{ssec:sum}

We write 
\beq
\label{eq:tau1}
\t_1=\t_1^1 +\t_1^2, 
\eeq
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. 

\ep

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


%%%%%%%%%%%%%%%%%% OP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Estimates for $Z_{j-1}(\xi,\zeta')$ and $Z_{N-j}(-\xi,\zeta).$}
\label{sssec: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}<p_k<
\bc \frac {\sqrt N}{M} 2^{-\frac{k^2}{M^2}N},
\eeq
for all $k=1,\ldots,M$ and $N$ large enough.

Optimizing in the exponential Markov inequality, we get 
\beq
\label{eq:exp1}
\PP(N_k>\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}
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$.

%%%%%%%%%%%%%%%%%%  tau_1^2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Estimates for $\t_1^2$}
\label{sssec:tau12}

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}e^{-\b H(\sz)} \max_{\eta\in\on}
\sum_{\eta':||\eta'-\eta||<\frac{N}{\log N}}e^{-\b H(\eta')}.
\eeq

Notice that the sum in~(\ref{eq:ub1133}) is very similar to that 
in~(\ref{eq:prod20}) and
that it has less than $2^{\a N}$ (independent)
terms, with an arbitrary $\a>0$ (for $N$  large
enough). We can thus proceed to estimate the former in the 
same way as we did the latter 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 shows that~(\ref{eq:ub1131}) holds with $\t_1^1$ replaced by $\t_1^2$.

\ep

We are now ready for the main result of this section.
(\ref{eq:ub1131}) (also applied to $\t_1^2$) substituted into~(\ref{eq:ub40})  
via~(\ref{eq:tau1})  prove 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 \b \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


%%%%%%%%%% SECTION 5 %%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Summing Up}
\setcounter{equation}{0}
\label{sec:su}

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 the next section,
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 6  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  

\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 Section~\ref{sec: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 $i<M$ and $Y_i=X_{i+1}$
otherwise.

\blem
\label{lem:dom}
\beq
\label{eq:dom}
P(Y_i<y_i,\,i=1,\ldots,n)\geq \prod_{i=1}^n P(X_1<y_i).
\eeq 
\elem

\ep

It follows immediately that the maximum of any subset of
$\{Y_1,\ldots,Y_n\}$ is stochastically dominated by the maximum of the same
number of $X$'s.

\ep

\noindent{\bf Proof}
\beqn
&&P(Y_i<y_i,\,i=1,\ldots,n)\\
\=\sum_{j=1}^{n+1}P(Y_i<y_i,\,i=1,\ldots,n,\,M=j)\\
\=\sum_{j=1}^{n+1}P(X_i<y_i,X_i<X_j,\,i<j,\,X_i<y_{i-1},X_i<X_j,\,i>j)\\
\=\sum_{j=1}^{n+1}\int 
P(X_i<y_i,X_i<x,\,i<j,\,X_i<y_{i-1},X_i<x,\,i>j)\,dF(x)\\
\=(n+1)\int \prod_{i=1}^n P(X_1<y_i\wedge x)\,dF(x)\\
\ge\prod_{i=1}^n P(X_1<y_i)\int (n+1)F^n(x)\,dF(x)\\
\=\prod_{i=1}^n P(X_1<y_i),
\eeqn
where the inequality follows from
\beq
F(x\wedge y)\geq F(x)F(y),
\eeq
 for all $x,y$. $\bo$

\ep




%%%%%%%%%%%%%%%%%%%% ACKNOWLEDGEMENTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\bf Acknowledgements.}

L.~F.~and M.~I.~thank M.~Cassandro, A.~Galves and A.~Pellegrinotti 
for stimulating discussions. L.~F.~further thanks R.~F\'ernandez,
P.~Ferrari, E.~Jord\~ ao Neves, E.~Kira and V.~Sidoravicius for 
valuable comments, suggestions and discussions.
His work was partially supported by Fapesp grants nos.~94/4303-5 
and 95/8932-0 and is part of Fapesp Theme Grant 
no.~95/0790-1 and CNPq Pronex grant.  
He acknowledges support and hospitality when visiting the University
of Rome "La Sapienza" and the CPT, Luminy. 
Part of this work was written while he
was visiting the Courant Institute (under CNPq grant no.~200125/96-6),
where he found warm hospitality.
M.~I.~was partially supported by CNPq grant no.~453865/93-3.
He acknowledges hospitality in S\~ao Paulo.
Y.~K.~was partially supported by FAPESP (Proc.~96/04505--2) and by
CNPq (Proc.~300334/93--1 and ProTeM-CC-II Project ProComb).

\ep

%%%%%%%%%%%%%%%%%%%%%% REFERENCES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{xxxxxx 89}

\bibitem{kn:D1} Derrida B.,  
                Random Energy Model: Limit of a Family of
                Disordered Models, 
                {\em Phys. Rev. Lett.} {\bf 45}, 79-82 (1980) 

\bibitem{kn:D2} Derrida B., 
                Random Energy Model: An Exactly Solvable
                Model of Disordered Systems, 
                {\em Phys. Rev. B} {\bf 24}, 2613-2626 (1981)

\bibitem{kn:E} Eisele Th.,  
               On a Third Order Phase Transition, 
               {\em Comm. Math. Phys.} {\bf 90}, 125-159 (1983) 

\bibitem{kn:OP} Olivieri E., Picco P.,   
                On the Existence of Thermodynamics for the Random Energy Model, 
                {\em Comm. Math. Phys.} {\bf 96}, 125-144 (1984)

\bibitem{kn:DS}  Diaconis P., Stroock D.,   
                 Geometric Bounds for Eigenvalues of Markov Chains,  
                 {\em Ann. Appl. Probab.} {\bf 1},  36-61  (1991)

\bibitem{kn:CGP} Cassandro M., Galves J.A. and Picco P.,   
                 Dynamical phase  transition in disordered 
                 systems: the study of a random walk model,
                 {\em Ann. Inst. H. Poincar\'e (Physique Th\'eorique)} 
                 {\bf 55}, 689-706 (1991)

\bibitem{kn:GMP} Galves J.A., Martinez S. and Picco P.,
                 Fluctuations in Derrida's Random Energy and Generalized 
                 Random Energy Models, 
                 {\em J. Stat. Phys.} {\bf 54} 515-529 (1989)

\bibitem{kn:CMM1} Cesi F., Maes, C. and Martinelli F.,
                  Relaxation in Disordered Magnets in the the Griffiths Regime, 
                  {\em Comm. Math. Phys.} {\bf 188} 135-173 (1997)

\bibitem{kn:CMM2} Cesi F., Maes, C. and Martinelli F.,
                  Relaxation to Equilibrium for Two Dimensional Disordered 
                  Ising Models in the Griffiths Phase, 
                  preprint 1997

\bibitem{kn:MPV} Mezard M., Parisi G. and Virasoro M.,
                 Spin Glass theory and beyond, 
                 {\em World Scientific} (1980)

\bibitem{kn:P} Parisi G.,
               Slow dynamics of glassy systems, Varenna Lectures 1996
               preprint cond-mat/9705312 on http://xxx.sissa.it/archive/cond-mat

\bibitem{kn:SZ} Sompolinsky H. and Zippelius A.,
                Relaxational dynamics of the Edwards-Anderson 
                model and the mean-field theory of spin-glasses,
                {\em Phys. Rev. B} {\bf 25} 6860-6875 (1982)

\bibitem{kn:Z} Zegarlinski B., 
               Strong Decay to Equilibrium in one Dimensional Random 
               Spin Systems,
               {\em J. Stat. Phys.} {\bf 77} 717-732 (1994)

\bibitem{kn:G} Guionnet A., 
               Averaged and Quenched Propagation of Chaos for Langevin 
               Spin Glass Dynamics,
               preprint 1997

\bibitem{kn:GZ1} Guionnet A. and  Zegarlinski B., 
                 Decay to Equilibrium in Random Spin Systems on a Lattice,
                 {\em Comm. Math. Phys.} {\bf 181} 703-732 (1996)

\bibitem{kn:GZ2} Guionnet A. and  Zegarlinski B., 
                 Decay to Equilibrium in Random Spin Systems on a Lattice II,
                 {\em J. Stat. Phys.} {\bf 86} 899-xxx (1996)

\bibitem{kn:BG1} Ben Arous G. and Guionnet A.,  
                 Large Deviations for Langevin Spin Glass Dynamics, 
                 {\em Probab. Theory Relat. Fields} {\bf 102}, 455-509 (1995)

\bibitem{kn:BG2} Ben Arous G. and Guionnet A.,  
                 Symmetric Langevin Spin Glass Dynamics, 
                 {\em Ann. Probab.} {\bf 25}, 1367-1422 (1997)

\bibitem{kn:GM} Gielis G. and Maes C.,  
                Percolation Techniques in Disordered Spin Flip Dynamics: 
                Relaxation to the Unique Invariant Measure,
                {\em Comm. Math. Phys.} {\bf 177} 83-xxx (1996)

\bibitem{kn:S} Sinclair A.J.,  
               Improved bounds for mixing rates of Markov chains and 
               multicommodity flow. 
               {\em Combin. Probab. Comput.} {\bf 1} 351--370 (1992)

\bibitem{kn:JS} Jerrum, M., Sinclair, A., 
                Approximate counting, uniform generation and rapidly mixing 
                Markov chains, 
                {\em Inform. and Comput.} {\bf 82}, 93--133  (1989)

\end{thebibliography}



\end{document}












