% %The original version of these macros is due to J.P. Eckmann % \magnification \magstep1 \vsize=22 truecm \hsize=16 truecm \hoffset=0.8 truecm \normalbaselineskip=5.25mm \baselineskip=5.25mm \parskip=10pt \immediate\openout1=key \font\titlefont=cmbx10 scaled\magstep1 \font\authorfont=cmcsc10 \font\footfont=cmr7 \font\sectionfont=cmbx10 scaled\magstep1 \font\subsectionfont=cmbx10 \font\small=cmr7 \font\smaller=cmr5 %%%%%constant subscript positions%%%%% \fontdimen16\tensy=2.7pt \fontdimen17\tensy=2.7pt \fontdimen14\tensy=2.7pt %%%%%%%%%%%%%%%%%%%%%% %%% macros %%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%% \def\dowrite #1{\immediate\write16 {#1} \immediate\write1 {#1} } %\headline={\ifnum\pageno>1 {\hss\tenrm-\ \folio\ -\hss} \else {\hfill}\fi} \newcount\EQNcount \EQNcount=1 \newcount\SECTIONcount \SECTIONcount=0 \newcount\APPENDIXcount \APPENDIXcount=0 \newcount\CLAIMcount \CLAIMcount=1 \newcount\SUBSECTIONcount \SUBSECTIONcount=1 \def\SECTIONHEAD{X} \def\undertext#1{$\underline{\smash{\hbox{#1}}}$} \def\QED{\hfill\smallskip \line{\hfill\vrule height 1.8ex width 2ex depth +.2ex \ \ \ \ \ \ } \bigskip} % These ones cannot be used in amstex % \def\real{{\bf R}} \def\rational{{\bf Q}} \def\natural{{\bf N}} \def\complex{{\bf C}} \def\integer{{\bf Z}} \def\torus{{\bf T}} % % These ones can only be used in amstex % %\def\real{{\Bbb R}} %\def\rational{{\Bbb Q}} %\def\natural{{\Bbb N}} %\def\complex{{\Bbb C}} %\def\integer{{\Bbb Z}} %\def\torus{{\Bbb T}} % % % \def\Re{{\rm Re\,}} \def\Im{{\rm Im\,}} \def\PROOF{\medskip\noindent{\bf Proof.\ }} \def\REMARK{\medskip\noindent{\bf Remark.\ }} \def\NOTATION{\medskip\noindent{\bf Notation.\ }} \def\PRUEBA{\medskip\noindent{\bf Demostraci\'on.\ }} \def\NOTA{\medskip\noindent{\bf Nota.\ }} \def\NOTACION{\medskip\noindent{\bf Notaci\'on.\ }} \def\ifundefined#1{\expandafter\ifx\csname#1\endcsname\relax} \def\equ(#1){\ifundefined{e#1}$\spadesuit$#1 \dowrite{undefined equation #1} \else\csname e#1\endcsname\fi} \def\clm(#1){\ifundefined{c#1}$\clubsuit$#1 \dowrite{undefined claim #1} \else\csname c#1\endcsname\fi} \def\EQ(#1){\leqno\JPtag(#1)} \def\NR(#1){&\JPtag(#1)\cr} %the same as &\tag(xx)\cr in eqalignno \def\JPtag(#1){(\SECTIONHEAD. \number\EQNcount) \expandafter\xdef\csname e#1\endcsname{(\SECTIONHEAD.\number\EQNcount)} \dowrite{ EQ \equ(#1):#1 } \global\advance\EQNcount by 1 } \def\CLAIM #1(#2) #3\par{ \vskip.1in\medbreak\noindent {\bf #1~\SECTIONHEAD.\number\CLAIMcount.} {\sl #3}\par \expandafter\xdef\csname c#2\endcsname{#1\ \SECTIONHEAD.\number\CLAIMcount} %\immediate \write16{ CLAIM #1 (\number\SECTIONcount.\number\CLAIMcount) :#2} %\immediate \write1{ CLAIM #1 (\number\SECTIONcount.\number\CLAIMcount) :#2} \dowrite{ CLAIM #1 (\SECTIONHEAD.\number\CLAIMcount) :#2} \global\advance\CLAIMcount by 1 \ifdim\lastskip<\medskipamount \removelastskip\penalty55\medskip\fi} \def\CLAIMNONR #1(#2) #3\par{ \vskip.1in\medbreak\noindent {\bf #1~#2} {\sl #3}\par \global\advance\CLAIMcount by 1 \ifdim\lastskip<\medskipamount \removelastskip\penalty55\medskip\fi} \def\SECTION#1\par{\vskip0pt plus.3\vsize\penalty-75 \vskip0pt plus -.3\vsize\bigskip\bigskip \global\advance\SECTIONcount by 1 \def\SECTIONHEAD{\number\SECTIONcount} \immediate\dowrite{ SECTION \SECTIONHEAD:#1}\leftline {\sectionfont \SECTIONHEAD.\ #1} \EQNcount=1 \CLAIMcount=1 \SUBSECTIONcount=1 \nobreak\smallskip\noindent} \def\APPENDIX#1\par{\vskip0pt plus.3\vsize\penalty-75 \vskip0pt plus -.3\vsize\bigskip\bigskip \def\SECTIONHEAD{\ifcase \number\APPENDIXcount X\or A\or B\or C\or D\or E\or F \fi} \global\advance\APPENDIXcount by 1 \vfill \eject \immediate\dowrite{ APPENDIX \SECTIONHEAD:#1}\leftline {\titlefont APPENDIX \SECTIONHEAD: } {\sectionfont #1} \EQNcount=1 \CLAIMcount=1 \SUBSECTIONcount=1 \nobreak\smallskip\noindent} \def\SECTIONNONR#1\par{\vskip0pt plus.3\vsize\penalty-75 \vskip0pt plus -.3\vsize\bigskip\bigskip \global\advance\SECTIONcount by 1 \immediate\dowrite{SECTION:#1}\leftline {\sectionfont #1} \EQNcount=1 \CLAIMcount=1 \SUBSECTIONcount=1 \nobreak\smallskip\noindent} \def\SUBSECTION#1\par{\vskip0pt plus.2\vsize\penalty-75 \vskip0pt plus -.2\vsize\bigskip\bigskip \def\SUBSECTIONHEAD{\number\SUBSECTIONcount} \immediate\dowrite{ SUBSECTION \SECTIONHEAD.\SUBSECTIONHEAD :#1}\leftline {\subsectionfont \SECTIONHEAD.\number\SUBSECTIONcount.\ #1} \global\advance\SUBSECTIONcount by 1 \nobreak\smallskip\noindent} \def\SUBSECTIONNONR#1\par{\vskip0pt plus.2\vsize\penalty-75 \vskip0pt plus -.2\vsize\bigskip\bigskip \immediate\dowrite{SUBSECTION:#1}\leftline{\subsectionfont #1} \nobreak\smallskip\noindent} %%%%%%%%%%%%%TITLE PAGE%%%%%%%%%%%%%%%%%%%% \let\endarg=\par \def\finish{\def\endarg{\par\endgroup}} \def\start{\endarg\begingroup} \def\getNORMAL#1{{#1}} \def\TITLE{\beginTITLE\getTITLE} \def\beginTITLE{\start \titlefont\baselineskip=1.728 \normalbaselineskip\rightskip=0pt plus1fil \noindent \def\endarg{\par\vskip.35in\endgroup}} \def\getTITLE{\getNORMAL} \def\AUTHOR{\beginAUTHOR\getAUTHOR} \def\beginAUTHOR{\start \vskip .25in\rm\noindent\finish} \def\getAUTHOR{\getNORMAL} \def\FROM{\beginFROM\getFROM} \def\beginFROM{\start\baselineskip=3.0mm\normalbaselineskip=3.0mm \obeylines\sl\finish} \def\getFROM{\getNORMAL} \def\ENDTITLE{\endarg} \def\ABSTRACT#1\par{ \vskip 1in {\noindent\sectionfont Abstract.} #1 \par} \def\ENDABSTRACT{\vfill\break} \def\TODAY{\number\day~\ifcase\month\or January \or February \or March \or April \or May \or June \or July \or August \or September \or October \or November \or December \fi \number\year} \newcount\timecount \timecount=\number\time \divide\timecount by 60 \def\DRAFT{\font\footfont=cmti7 \footline={{\footfont \hfil File:\jobname, \TODAY, \number\timecount h}} } %%%%%%%%%%%%%%%%BIBLIOGRAPHY%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\period{\unskip.\spacefactor3000 { }} % % ...invisible stuff % \newbox\noboxJPE \newbox\byboxJPE \newbox\paperboxJPE \newbox\yrboxJPE \newbox\jourboxJPE \newbox\pagesboxJPE \newbox\volboxJPE \newbox\preprintboxJPE \newbox\toappearboxJPE \newbox\bookboxJPE \newbox\bybookboxJPE \newbox\publisherboxJPE \def\refclearJPE{ \setbox\noboxJPE=\null \gdef\isnoJPE{F} \setbox\byboxJPE=\null \gdef\isbyJPE{F} \setbox\paperboxJPE=\null \gdef\ispaperJPE{F} \setbox\yrboxJPE=\null \gdef\isyrJPE{F} \setbox\jourboxJPE=\null \gdef\isjourJPE{F} \setbox\pagesboxJPE=\null \gdef\ispagesJPE{F} \setbox\volboxJPE=\null \gdef\isvolJPE{F} \setbox\preprintboxJPE=\null \gdef\ispreprintJPE{F} \setbox\toappearboxJPE=\null \gdef\istoappearJPE{F} \setbox\bookboxJPE=\null \gdef\isbookJPE{F} \gdef\isinbookJPE{F} \setbox\bybookboxJPE=\null \gdef\isbybookJPE{F} \setbox\publisherboxJPE=\null \gdef\ispublisherJPE{F} } \def\ref{\refclearJPE\bgroup} \def\no {\egroup\gdef\isnoJPE{T}\setbox\noboxJPE=\hbox\bgroup} \def\by {\egroup\gdef\isbyJPE{T}\setbox\byboxJPE=\hbox\bgroup} \def\paper{\egroup\gdef\ispaperJPE{T}\setbox\paperboxJPE=\hbox\bgroup} \def\yr{\egroup\gdef\isyrJPE{T}\setbox\yrboxJPE=\hbox\bgroup} \def\jour{\egroup\gdef\isjourJPE{T}\setbox\jourboxJPE=\hbox\bgroup} \def\pages{\egroup\gdef\ispagesJPE{T}\setbox\pagesboxJPE=\hbox\bgroup} \def\vol{\egroup\gdef\isvolJPE{T}\setbox\volboxJPE=\hbox\bgroup\bf} \def\preprint{\egroup\gdef \ispreprintJPE{T}\setbox\preprintboxJPE=\hbox\bgroup} \def\toappear{\egroup\gdef \istoappearJPE{T}\setbox\toappearboxJPE=\hbox\bgroup} \def\book{\egroup\gdef\isbookJPE{T}\setbox\bookboxJPE=\hbox\bgroup\it} \def\publisher{\egroup\gdef \ispublisherJPE{T}\setbox\publisherboxJPE=\hbox\bgroup} \def\inbook{\egroup\gdef\isinbookJPE{T}\setbox\bookboxJPE=\hbox\bgroup\it} \def\bybook{\egroup\gdef\isbybookJPE{T}\setbox\bybookboxJPE=\hbox\bgroup} \def\endref{\egroup \sfcode`.=1000 \if T\isnoJPE \item{[\unhbox\noboxJPE\unskip]} \else \item{} \fi \if T\isbyJPE \unhbox\byboxJPE\unskip: \fi \if T\ispaperJPE \unhbox\paperboxJPE\unskip\period \fi \if T\isbookJPE ``\unhbox\bookboxJPE\unskip''\if T\ispublisherJPE, \else. \fi\fi \if T\isinbookJPE In ``\unhbox\bookboxJPE\unskip''\if T\isbybookJPE, \else\period \fi\fi \if T\isbybookJPE (\unhbox\bybookboxJPE\unskip)\period \fi \if T\ispublisherJPE \unhbox\publisherboxJPE\unskip \if T\isjourJPE, \else\if T\isyrJPE \ \else\period \fi\fi\fi \if T\istoappearJPE (To appear)\period \fi \if T\ispreprintJPE Preprint\period \fi \if T\isjourJPE \unhbox\jourboxJPE\unskip\ \fi \if T\isvolJPE \unhbox\volboxJPE\unskip, \fi \if T\ispagesJPE \unhbox\pagesboxJPE\unskip\ \fi \if T\isyrJPE (\unhbox\yrboxJPE\unskip)\period \fi } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% SOME SMALL TRICKS%%%%%%%%%% \def \breakline{\vskip 0em} \def \script{\bf} \def \norm{\vert \vert} \def \endnorm{\vert \vert} \def\cite#1{ [#1]} \def\bfx{{\bf x}} \def\bfn{{\bf n}} \def\bfe{{\bf e}} \def\bfu{{\bf u}} \def\SS{{\cal S}} \def\RR{{\cal R}} \def\OO{{\cal O}} \def\BB{{\cal B}} \def\CC{{\cal C}} \def\Tau{{\cal T}} \def\FF{{\cal F}} \def\tG{{\tilde G}} \TITLE AUBRY--MATHER THEORY FOR FUNCTIONS ON LATTICES. \footnote{${}^{\rm (1)}$ } {\rm \baselineskip = 12 pt This preprint is available from the math-physics electronic preprints archive. Send e-mail to {\tt mp\_arc@math.utexas.edu} for instructions} \AUTHOR Hans Koch \footnote{${}^2$}{ e-mail address {\tt koch@math.utexas.edu}}, Rafael de la Llave \footnote{${}^3$}{ e-mail address {\tt llave@math.utexas.edu}}, Charles Radin \footnote{${}^4$}{ e-mail address {\tt radin@math.utexas.edu} } \FROM Mathematics Department The University of Texas at Austin Austin TX\ \ 78712 \ENDTITLE \ABSTRACT We generalize the Aubry-Mather theorem on the existence of quasi-periodic solutions of one dimensional difference equations to situations in which the independent variable ranges over more complicated lattices. This is a natural generalization of Frenkel-Kontorovna models to physical situations in a higher dimensional space. We also consider generalizations in which the interactions among the particles are not just nearest neighbor, and indeed do not have finite range. \ENDABSTRACT \SECTION Introduction. The goal of this paper is to generalize the Aubry-Mather theorem on the existence of quasi-periodic solutions of certain difference equations to cases in which the unknown depends not just on one, but on several variables by modifying a method used in [Go] in the one-dimensional case. Such generalizations are natural from the point of view of the solid state motivations of the theorem. For example, the Frenkel-Kontorovna model considered by Aubry and Mather describes configurations which are one-dimensional chains of particles in a periodic external potential and interacting with their nearest neighbors via a harmonic potential. Such models are one-dimensional caricatures of the physical situation of a layer of a material over a substratum of other material. If we denote by $V(x) = V(x+1)$ the periodic potential and by $u_i$ the displacement of the $i^{\rm th}$ particle from the its equilibrium position, we seek configurations that are critical points of the energy: $$ \SS(u) = \sum_{i\in\integer} {1 \over 2} (u_i -u_{i+1} -a)^2 + V(u_i) \EQ(ActionFK) $$ (We also point out that there are other physical interpretations. For example, we could have atoms whose state is described by an internal variable $u_i$. The internal energy is periodic but there is a coupling between nearest variable. For example, the model \equ(ActionFK) has been used as models of spin waves. In that interpretation, $V(u_i)$ would be the magnetic energy of the $i^{\rm th}$ atom and the term ${1 \over 2} (u_i -u_{i+1})^2$ -- or a modification -- would be the exchange interaction between neighboring spins.) Even if the sum on the R.~H.~S. of \equ(ActionFK) is only formal, the variational equations are quite well defined, namely: $$ u_{i+1} + u_{i-1} - 2 u_i + V'(u_i) = 0 \EQ(variationFK) $$ which are equivalent to the well known standard-like mappings of Hamiltonian mechanics. The Aubry-Mather theorem establishes, among other things, that for every $\omega \in \real$ the variational equations \equ(variationFK) admit a solution $u$ such that $\sup_i |u_i - \omega i| < \infty$. In this paper we will be concerned with generalizing this theorem to situations in which: \item{$\bullet$} The physical space is higher dimensional. \item{$\bullet$} The interactions are not necessarily just nearest neighbor. \item{$\bullet$} The interactions are invariant under a smaller symmetry group than the full lattice. An example to keep in mind of a model to which our results apply is the $n$-dimensional analogue of the Frenkel-Kontorovna model, described by the action $$ \SS(u) = \sum_{i \in \integer^n} {1 \over 2 n}\sum_{j:|j-i| =1}|u_i -u_j|^2 +V(u_i) $$ which leads to the variational equations: $$ (\Delta u)_i + V'(u_i) =0 $$ where $\Delta$ denotes the discrete Laplacian. Such models for $n=2$ have been considered in [V], where one can also find an extensive discussion of properties of solutions, and physical consequences. Another generalization which we will be able to deal with is $$ \SS(u) = \sum_{i \in \integer^n} {1 \over 2 n}\sum_{j:|j-i| =1}|u_i -u_j|^2 +V(u_i,i) $$ where $V(x,i)$ is periodic in $i$ and similar generalizations. In the case $n = 1$, this admits the dynamic interpretation of a composition of finite number of standard maps or, alternatively, as a map in a higher dimensional space. These generalizations, however do not seem to include higher dimensional standard maps. The method of proof we will use is motivated by a recent paper of Gol\'e [Go] which presents a new proof of the classical Aubry-Mather theorem for one dimensional Frenkel-Kontorovna models. We point out that it is also possible using the methods employed here to give a simple proof of generalizations of a theorem of Moser [Mo] on partial differential equations. Since the latter results seem to require other ingredients from P.D.E., and have different motivation, we will report on them elsewhere. The use of heat flow methods in Aubry-Mather theory was introduced in the paper \cite{An}, but the methods we use here are more elementary. We also point out that results very related to those of this paper, can be found in [Bl1], [Bl2] by using quite different methods. We also note that the papers [Bl1] and [Bl2] look for minimal solutions. Following the lead of [Mo], [An] and [Go], we look for solutions of the variational problem that are well ordered. This makes the estimates at infinity much simpler. In this respect, it is interesting to point out that in higher dimensional ambient spaces there are examples in [Bl2] of minimal solutions which are not well ordered. These phenomena have been observed numerically in [OV]. \SECTION Acknowledgments We thank C. Gol\'e for acquainting us with [Go] prior to publication, and for his encouragement. He and F. Tangerman made very useful comments on a preliminary version of this paper. We also thank L. M. Floria for making us aware of [V] and providing us with a copy and J. Moser for several discussions and making us aware of [Bl1], [Bl2]. The authors have been supported by NSF grants. R.L. also acknowledges the support of the AMS Centennial Fellowship and a URI from U. Texas during the last revision of this paper. \SECTION Notation and statement of results. We will be concerned with functions defined on lattices (i.e. discrete subgroups of $\real^d$ with its additive structure). We will find it useful to distinguish between the lattices as subsets of $\real^d$ and as groups of motions. (For example, we will find it useful to consider smaller groups of motions that the full lattice.) Hence, we will use the word crystals when we want to emphasize the fact that the group structure is irrelevant We will also refer to functions on lattices as configurations. This is motivated by the physical interpretation of the models in \equ(ActionFK) for which the $i$ represent labels of atoms, $u_i$ represent characteristics of each atom. The function $u_i$ represents the state -- or configuration of the crystal -- and the action in \equ(ActionFK) is the energy associated to the configuration. As it is well known, discrete subgroups of $\real^d$ can be identified with sets of the form $\{ x \in \real^d\ \big| \ \ x = \sum_{i = 1}^n k_i v_i, k_i \in \integer\}$ for some linearly independent vectors $v_i$. (Without loss of generality we will assume that $n = d$) Hence, all crystals can be identified with $\integer^d$. The identification is not unique, but we will assume it is done and fixed through the proof. This allows us to define the distance between two points in the crystal using the absolute value of points in $\integer^d$ (The sum of the absolute value of the coordinates) Again, this is a non-canonical choice and many others would have worked, but we fix it for the sake of definiteness. We will denote by $\Gamma$ the points of a lattice and denote by $G$ a group of translations that leaves invariant. Clearly, $G$ is a subgroup of the lattice and indeed we will fins it useful to consider the case where it is a non-trivial subgroup. If $k$ is an element of the lattice, we denote by $T_k$ the translation by $k$ on the crystal. That is $T_k x = x + k$. For each subset $B$ of $\Gamma$ we denote by $|B|$ the number of elements of $B$, and by $\partial_n B$ the set: $$ \partial_n B \equiv \{ x \in \Gamma - B\ :\ {\rm dist}(x,B) \le n\} \cup \{ x \in B\ :\ {\rm dist}(x,\Gamma - B) \le n\}$$ We write that $ \lim_n \Lambda_n = \Gamma$ if for any site $j \in \Gamma$ there is an $N(j)$ such that $n > N(j)$ implies $j \in \Lambda_n$. A particularly important role in the argument will be played by collections of sets that cover the whole space but are hierarchically ordered in sizes of different scales. The sets of one scale can be decomposed into pieces which are sets of the smaller scale. (This is quite similar to the usual Calder\'on-Zygmund decompositions of harmonic analysis) For example, using the representation of the crystal as $\integer^d$, we can consider the collection $\CC$ of finite subsets $\Lambda$ which are of the form: $$ \Lambda = [ k_1 -l_m, k_1 + l_m] \times [ k_2 -l_m, k_2 + l_m] \times \cdots [ k_n -l_m, k_n + l_m] $$ for some $k_1,\ldots,k_n \in \integer$, $l_m = (3^{m+1} -1)/2$. In other words, cubes of sizes $l_m$ growing exponentially and centered at any point. It is important to note that since $[k -l_m, k+l_m] = [ (k -l_m +l_{m-1}) -l_{m-1}, (k -l_m +l_{m-1}) + l_{m-1}] \cup [ (k -l_m + 3 l_{m-1} +1) -l_{m-1}, (k -l_m + 3 l_{m-1} +1 ) + l_{m-1}] \cup [ (k -l_m + 5 l_{m-1} +2) -l_{m-1}, (k -l_m + 5 l_{m-1} +2 ) + l_{m-1}] $ (Recall that $-l_m + 6 l_{m-1} +2 = l_m$.) we conclude that the cubes of size $l_m$ can be divided into $3^n$ disjoint cubes of size $l_{m-1}$. We also note that as the sizes of the cubes grow, their boundaries are negligible with respect to their volume. This property will also play an important role. We will record these in a definition to make clear what properties of the collection $\CC$ will be needed later. This may lead to developing an Aubry-Mather theory in a more abstract setting. We also note that very similar properties play a role in the theory of the thermodynamic limit (See e.g \cite{Ru}). \CLAIM Definition (inflation) We say that a collection $\CC$ of finite subsets of a lattice $\Gamma$ admits an inflation rule if: \item{$i)$} If $\{ \Lambda_n\}_{n \in \natural} \subset \CC$ and $|\Lambda_n| \to \infty$, then there are translations $k_n \in G$ such that $\lim_n T_{k_n}(\Lambda_n) = \Gamma$. \item{$ii)$} There exist $N, L \in \natural$ and $M \in \real$ such that for any set $\Lambda \in \CC$ with $|\Lambda| > L$, we can find $N$ mutually disjoint sets $\Lambda_1,\cdots,\Lambda_N \in \CC$, $|\Lambda_i| > M$, such that $\Lambda = \Lambda_1 \cup \Lambda_2,\cup \cdots, \cup \Lambda_N.$ \item{$iii)$} For every $n \in \natural$, if we define $\phi_n(m) \equiv \max\{|\partial_n \Lambda|\ :\ |\Lambda| \le m,\ \Lambda \in \CC\}$, we have $ \lim_{m\to \infty } \phi_n(m)/m^\alpha = 0$, for any $\alpha > \log(M) / \log(N)$ for the $N,M$ in $ii)$. It is obvious that for the $M,N$ in $ii)$ we should have $M \ge N$. The difference between $M$ and $N$ is a measure of the difficulty of fitting sets of the same size in $\CC$ together. For example, if we consider the sets of cubes with all possible translations, we can take $M=N$. For the set consisting of up and down triangles of size at least $S$ on a two dimensional hexagonal lattice we can take $N = 4$ and $M = 4 + O(1/S)$. For the above two cases it is easy to verify condition $ii)$ with $\alpha =1$, but nevertheless for fixed $n$ and sufficiently large sets, $|\partial_n \Lambda| \approx n |\delta_n \Lambda| \approx n |\Lambda|^{1 - 1/\nu}|$ where $\nu$ is the dimension of the lattice. Aubry-Mather theory will assert the existence of real valued functions on the lattice satisfying certain properties. Again, we point out that we will use the physically motivated name ``configurations" often. \CLAIM Definition(configuration) A configuration is a map $u:\Gamma \mapsto \real$. We define sums of configurations and their multiplication by numbers in the usual way for maps. Our next goal is to find a definition, analogous to that of Birkhoff orbits, that generalizes to higher dimensional situations. We observe that the essential part of the definition of Birkhoff orbits is that translations preserve order properties. In what follows, we note that the group of translations that we consider may be a subgroup of finite index of the full group of translations of the lattice. To emphasize that, we will denote it by $\tG$. \CLAIM Definition (actions) If we have a crystal $\Gamma$, a subgroup $\tG$ -- of finite index -- of the group $G$ of translations of the lattice. we will denote the action of $\tG$ acting on configurations by $(\Tau_k u)_i = u_{i+k}$. Similarly, for $\ell \in \integer$ we denote by $\RR_\ell$ the mapping defined by $(\RR_\ell u)_k = u_k + \ell$. Note that $\Tau_k$ are linear operators and the $\RR_\ell$ are affine. An immediate consequence of these definitions is: \CLAIM Proposition (commute) $\Tau_k \Tau_{k'} = \Tau_{k'}\Tau_k = \Tau_{k + k'}$, $\RR_\ell \RR_{\ell'} = \RR_{\ell'}\RR_\ell = \RR_{\ell + \ell'}$, and, for $k$ in ${\tilde G} $, $\Tau_k \RR_\ell = \RR_\ell \Tau_k$. \CLAIM Definition (order) Given two configurations $u, u'$, we write $u \le u'$ if $u_i \le u'_i \hbox{ for all } i \in \Gamma$, with analogous definitions for any of the other comparison symbols $\ge,\ <$ or $>$. Notice that these comparisons among configurations are not total orders (except in the trivial case where $\Gamma$ consists of one element). That is, there are pairs of configurations which do not satisfy any of the comparisons. This order works very nicely with all the other elements of structure that we have introduced so far (actions of translations, addition of configurations) \CLAIM Proposition (orderpreserved) If $u \le u'$, then for every $k \in \tG$ and every $\ell \in \integer$ and for any configuration $u''$ we have: $\Tau_k u \le \Tau_k u'$, $\RR_\ell u \le \RR_\ell u'$, and $u + u'' \le u' +u''$. \CLAIM Definition (uniform) Given a vector $\omega\in\real^n$, we say that a configuration $u$ is of type $\omega$ if $$ \sup_{j \in \Gamma}|| u_j - \omega \cdot j|| < \infty \EQ(newuniform) $$ where we denote by $\omega \cdot j$ the usual scalar product. We denote by $\OO_\omega$ the set of configurations of type $\omega$. We refer to the configuration $u^\omega$ defined by $u^\omega_k = \omega \cdot k$ as the plane wave of frequency $\omega$ We observe that $\Tau_k \RR_\ell (\OO_\omega) = \OO_\omega$. Notice also that $\OO_\omega$ is an affine space modeled on $ \ell^{\infty}( \Gamma, \real) \equiv \{ u:\Gamma \to \real\ : \ || u || \equiv \sup_{j \in \integer^n} |u_j| < \infty .\} $ Part of the difficulties of the theory arise from the fact that $\ell^\infty$ is a space ill suited for many constructions in the calculus of variations. Nevertheless, there is a natural way to restore some control at $\infty$. The following is a definition that has played an important role in dynamical systems. \CLAIM Definition (Birkhofforbit) Given a discrete subgroup $\tG$ of trasnlations leving invariant a crystal $\Gamma$, we say that a configuration $u \in \OO_{\omega}$ is a Birkhoff configuration if for every $k \in \tG$, every $\ell \in \integer$ we have either $ \Tau_k \RR_\ell u \ge u$ or $ \Tau_k \RR_\ell u \le u$ We denote by $\BB_\omega$ the set of Birkhoff configurations in $\OO_\omega$. We note that this set is not empty (e.g. the plane wave $u^\omega$ belongs to it). Note that the concept of Birkhoff depends on the subgroup $\tG$ that we are considering. We will omit this from the notation when it does not lead to confusion. Usually in Aubry-Mather theory, one just takes $\tG$ = $G$. consider other models. \CLAIM Proposition (orders) Let $u \in \BB_\omega$. If for some $k \in \tG$, $\ell \in \integer$, $\omega \cdot k + \ell < 0$. Then $\Tau_k \RR_\ell u \ge u$. If $\omega \cdot k + \ell > 0$ then $\Tau_k \RR_\ell u \le u$. (In other words, the choice of sign in the Birkhoff definition is the same as for the plane wave of frequency $\omega$) \PROOF We will only prove the first case. Assume the hypothesis was true and the conclusion false. By the Birkhoff property, if $\Tau_k \RR_\ell u \ge u$ is false then, we should have $\Tau_k \RR_\ell u \le u$. If $\Tau_k \RR_\ell u \le u$ then, for any natural number $n$ we also have $ (\Tau_k \RR_\ell)^n u \le u $. If we compare with the plane wave solution, using that $ (\Tau_k \RR_\ell)^n u^\omega = u + ( k \cdot \omega +\ell)n $, we have using that $\Tau_k$ is linear and $\RR_\ell$ affine $$ (\Tau_k \RR_\ell)^n u - (\Tau_k \RR_\ell)^n u^\omega = (\Tau_k \RR_\ell)^n u - u + ( u - u^\omega) - n(k \cdot \omega + \ell) \le (u -u^\omega) - n(k \cdot \omega + \ell). $$ On the other hand $ \inf_j [(\Tau_k \RR_\ell)^n u]_j - [(\Tau_k \RR_\ell)^n u^\omega]_j = \inf_j u_j - u^\omega_j $ This is the desired contradiction. \QED \CLAIM Proposition (bounds) For every $k \in \tG$, there exist $\ell^{-}, \ell^{+} $ such that for every $u \in \OO_\omega$, $ \RR_{\ell^{-}} u \le \Tau_k u \le \RR_{\ell^{-}} u $. Actually, this is the main property of the set of Birkhoff orbits that we will use. Notice that its strength comes from the fact that $\ell^{-}, \ell^{+}$ depend only on $k$ and not on the element of the set. If $\omega \cdot k$ is not an integer, we can get $\ell^{+}$ and $\ell^{-}$ to differ by $1$. If $\omega \cdot k $ happens to be an integer, we can get them to differ by $2$. Another property of Birkhoff sets we will use is: \CLAIM Proposition (Rpreserves) $\Tau_k \RR_\ell \BB_\omega$ $= \BB_\omega$, for $k \in \tG$. From this we deduce that if we define an equivalence relation among configurations by $u \RR u' $ if and only if $ u = \RR_\ell u'$ for some $\ell$, it is possible to restrict this relation to $\BB_\omega$ and hence speak of $\BB_\omega/\RR$. This set will play an important role. The previous definitions involve only the geometry of configurations. To obtain meaningful physical models it is necessary to define interactions among the particles. The following definition is standard in statistical mechanics. See e.g [Ru]. \CLAIM Definition (interaction) An interaction is a collection of maps $\{ H_B\ :\ B \subset \Gamma,\ B\ {\rm finite}\}$ that to each configuration $u$ associate a number $H_B(u)$ which depends only on the restriction of $u$ to $B$. \CLAIM Definition (invariances) We will say that an interaction is invariant under the group $\tG$ of translations if for all the translations $k \in \tG$, all $B$, and all configurations $u$, $H_{T_k B}(\Tau_k u ) = H_B(u)$. We will say that an interaction has periodic phase space if for all $\ell \in \integer$, all $B$, and all configurations $u$, $$ H_B( \RR_\ell u) = H_B(u). \EQ(perphase) $$ One consequence of \equ(perphase) is that the maps $H_B$ can be considered not just as maps $\BB_\omega \to \real$ but rather as $\BB_\omega/\RR \to \real$. Notice that the Frenkel-Kontorovna models correspond to taking $H_{\{i\}}(u) = V(u_i)$, $H_{\{i,j\}}(u) = {1 \over 2n } (u_i - u_j)^2 $ when $|i -j | = 1$, and all other $H_B(u)$ equal to zero. They are translation invariant and have periodic phase space. The variational principle we will consider comes from the formal action: $$ \SS(u) = \sum_{B \subset \Gamma \atop B {\rm finite}} H_B(u) \EQ(actionstatmech) $$ The variational equations corresponding to the formal variational principle above are: $$ \sum_{B \ni i} {\partial \over \partial u_i } H_B( u ) = 0, \quad \hbox{for all } i \in \Gamma \EQ(variationsstatmech) $$ The equations \equ(variationsstatmech) are well defined whenever the sums converge in a sufficiently strong sense. This motivates the following definitions. \CLAIM Definition (rbounded) We say that an interaction is $r$-bounded on the configurations in the convex set $\OO$ of configurations if: $$ || H||_{r} \equiv \sup_{u\in \OO} \sup_{j_1}\sum_{j_2, \cdots,j_r} \big| \sum_{B \ni j_1,\cdots j_r} {\partial \over \partial u_{j_1} }\cdots {\partial \over \partial u_{j_r}} H_B(u)\big| < \infty \EQ(rbounded) $$ \REMARK Note that we have chosen the definition in such a way that $||H||_r$ depends only on the derivatives of $H$ of order exactly $r$. In particular, assuming that a function is $r$-bounded does not afford any control on derivatives of order less than $r$. \REMARK Note that the equations \equ(variationsstatmech) make perfectly good sense when the interaction is $1$ bounded. \REMARK Notice that the property of being $1$ bounded depends on the set of configurations we are considering. For example, if we consider the Frenkel-Kontorovna model, it is $1$ bounded on sets of the form $\OO^K_\omega = \{ u\ :\ \sup_i | u_i - \omega \cdot i | \le K < \infty \}$ (Hence, it is $1$ bounded in $\BB_\omega$) Nevertheless, it is not $1$ bounded on $\OO_\omega$. We will still omit the dependence on the set when it is obvious to which set we are referring. Notice that by \clm(bounds) the set $\BB_\omega$ is contained in $\OO^2_\omega$. The reason for introducing these semi-norms is that the variational equations can be written as $ \FF_i(u) = 0 $ where $ \FF_i(u) = \sum_{B \in i} {\partial \over \partial u_i} H_B(u)$. In the cases that we will be interested in, $\OO$ will be an affine space over $\ell^\infty$ and the conditions \equ(rbounded) are conditions that ensure that the $r-1$ derivative of $\FF$ exists and is uniformly bounded in the sense of derivatives in the Banach space $\ell^\infty$. In particular we have: \CLAIM Corollary (interpolation) If we define $\FF$ as above, we have $||\FF(u) - \FF(\tilde u)||_{\ell^\infty} \le ||H||_{2} ||u - \tilde u||_{\ell^\infty}$. Finally, we will need an extra hypothesis which is analogous to the twist condition in Hamiltonian mechanics and to ferromagnetism in statistical mechanics. \CLAIM Definition (twist) We will say that an interaction which is $2$ bounded on $\OO$ satisfies the twist condition -- or is ferromagnetic -- if for all configurations $u\in \OO$, and all $j \ne j' \in \Gamma$, $$ \sum_{B \ni j} {\partial^2 \over {\partial u_j \partial u_{j'}}} H_B(u) \ge 0 \EQ(twist) $$ The property \equ(twist) is obviously implied by the stronger one: $$ {\partial^2 \over \partial u_j \partial u_{ j'}} H_B(u) \ge 0 \EQ(strongtwist) $$ for all $j \ne j' \in \Gamma$, $B \subset \Gamma$. We refer to \equ(strongtwist) as the strong twist condition or the strong ferromagnetic condition. (Notice that the Frenkel-Kontorovna models satisfy \equ(strongtwist).) \CLAIM Theorem (main) Let $\Gamma$ be a crystal with group of translations $G$. Let $H$ be an interaction invariant under the group $\tG$ of finite index in $G$, $2$ bounded on $\OO^3_\omega$. Assume furthermore either: \item{$a)$} $H$ satisfies the twist condition and is finite range. \item{$b)$}$H$ satisfies the strong twist condition. \vskip 0em Then, there is a solution of \equ(variationsstatmech) which lies in $\BB_\omega$. The crux of the proof is to verify the second part. Then, the first part is just a very easy approximation argument. We also note that the hypothesis of boundedness of the flow can be weakened considerably. See the remarks at the end of the proof for the details. \SECTION Proof of \clm(main) Our first task will be to prove \clm(main) under the extra assumption that the interaction is of finite range and that it is $3$-bounded. Later, we will use this result to prove the full result by approximating our original problem by $3$-bounded finite range models. The proof of this weak version of \clm(main) will follow, roughly, the scheme in [Go]. We will derive a contradiction to the assumption that there are no critical points of \equ(variationsstatmech) of the desired type; namely, we will show that if there is no critical point of \equ(variationsstatmech) in $\BB_\omega$, then we can find a map $T: \BB_\omega \to \BB_\omega$, and a continuous function $G:\BB_\omega \to \real$, such that $G(T(u)) \ge G(u) + \delta$ for some $\delta>0$, and this will lead to a contradiction. The argument in [Go] uses the fact that if a configuration $u_0$ is not a critical point of \equ(variationFK) we can find a $G$ such that $G(T(u) ) \ge G(u)$ with the inequality being strict for $u$ in a neighborhood of $u_0$. Unfortunately, some steps of the argument of [Go] do not generalize when the dimension of ``time'' is greater than one and we have to use a more direct argument. \CLAIM Lemma (compact) $\BB_\omega/\RR \subset \OO_\omega/\RR$ is compact when $\OO_\omega/\RR$ is given the topology generated by the following basis: $\{O_{B,A}\ :\ B \hbox{ a finite subset of }\Gamma, A \hbox{ an open subset of } \real^d\}$, where $\{O_{B,A}\} \equiv \{\hat u\ :\ (u_j - \omega \cdot j) \subset A\hbox{ for } j\in B, \hbox{ for some } u \in \hat u\}$. (We will refer to this topology as the topology of component-wise convergence since convergence in it is just convergence component by component.) \PROOF If we pick $p$ representatives $\{i_1,\cdots,i_p\}$ of the classes $\Gamma/ {\tilde G}$, -- here we use that $\tG$ is of finite index in $G$ --, given a configuration $u$ we can apply one and only one $\RR_\ell$ in such a way that $0 < u_{i_\alpha} <= 1$. This means that we can identify $\BB_\omega/\RR$ as the set of configurations $u$ in $\BB_\omega$ which satisfy $u_{i_\alpha} \in (0,1]$ if we identify the ends of $(0,1]$. If a configuration $u \in \OO_\omega$ is Birkhoff by \clm(bounds) $$ [\omega \cdot k ] + u_{i_\alpha} \le u_{i_\alpha+ k} \le [\omega \cdot k ] +1 + u_{i_\alpha} \EQ(coordinatebounds) $$ for every $\alpha = 1,\cdots, p$ and every $k \in {\tilde G}$, where $[\quad]$ denotes integer part. Since, by assumption, the $i_1,\cdots,i_p$ cover all the conjugacy classes of $\Gamma/ {\tilde G}$, we see that if an orbit belongs to $\BB_\omega$ and the $u_{i_\alpha}$ remain bounded, then the values at each site have a bounded range. Applying Tychonov's theorem, we can conclude that $\BB_\omega / \RR$ is precompact when we give it the topology of point-wise convergence. By the definition of Birkhoff orbit, it is clear that $\BB_\omega$ is closed in this topology since it is expressed as the intersection of conditions on each coordinate that are preserved under point-wise limits. \QED \CLAIM Lemma (flow) Consider the map $\FF$ defined on $\OO^3_\omega$ by: $$ \left[ \FF(u)\right]_j = - \sum_{B \ni j } {\partial \over \partial u_j} H_B(u); \EQ(flowequations) $$ If $H$ is $1$-bounded on bounded sets of $\OO_\omega$, then $\FF$ maps $\OO_\omega$ into $\ell^{\infty}$. Moreover if $H$ is $r$--differentiably bounded, then $\FF^i$ is a ${r-1}$ map from $\OO_\omega$ to $\ell^{\infty}$, and the norm of the derivatives of order $r-1$ is uniformly bounded. \PROOF The proof just consists of restating the definition of $1$ bounded and noting that if an interaction is $2$ bounded the derivative of the right hand side of \equ(flowequations) can be obtained by taking derivatives term by term in the sum. \QED \REMARK Notice that $\FF$ is formally the derivative of the variational principle \equ(actionstatmech). Notice also that in the Frenkel-Kontorovna case it reduces to an analogue of the heat equation in which the Laplacian is discrete. If we remember that $\OO_\omega$ is an affine space modeled on $\ell^\infty$, the usual existence theorem of differential equations implies that we can define a local flow $\Phi_t: \OO_\omega \to \OO_\omega$ satisfying $$ {d \over dt } \Phi_t(u) = \FF(\Phi_t(u)). \EQ(floweq) $$ From the fact that the right hand side of \equ(flowequations), is uniformly Lipschitz, we conclude that the solutions are defined for all time. Using the hypothesis about the symmetry of the coefficients of the interaction we obtain that for $k \in {\tilde G}$, $q \in \integer$. $$ \Tau_k R_q \FF = \FF \Tau_k. \EQ(symmetries) $$ \noindent Hence, using the uniqueness of solutions of the differential equations defining the flow, we also have for $k \in {\tilde G}$ and $q \in \integer$: $$ \Tau_k \RR_q \Phi_t = \Phi_t \Tau_k \RR_q \EQ(symmetryflow) $$ We show next that the partial orders of \clm(order) are also preserved by the flow when the interaction is ferromagnetic. \CLAIM Lemma (comparison) Let $\FF$ be defined as before and let $H$ be a ferromagnetic interaction. Then if $u \le {\tilde u}$ (resp. $u \ge {\tilde u}$) we have $\Phi_t(u ) \le \Phi_t({\tilde u})$ (resp.$\Phi_t(u) \ge \Phi_t( {\tilde u})$). \PROOF It suffices to prove the result in the case $u \le {\tilde u}$. Define $u_\lambda = \lambda u + (1 - \lambda){\tilde u}$. By the theorem on smooth dependence on parameters of solutions of O.D.E.'s in Banach space, we have that $\Phi_t( u_\lambda)$ is $C^{r-2}$ with respect to parameters if $H$ is $r$-bounded. (In finite dimensions, one does not need an extra derivative since, in that case, continuous functions on closed bounded sets are uniformly continuous.) Hence, if $r \ge 3$ we have that $\Phi_t( u_\lambda)$ is $C^1$ and, hence, to prove the conclusion it suffices to show ${ d \over d \lambda} \Phi_t( u_\lambda) \le 0$. Recall that if we consider ${ d \over d \lambda} \Phi_t( u_\lambda)$ as a function of $t$ it satisfies the variational equations: $$ \eqalign{ & {d \over dt } \left[ {d \over d \lambda} \Phi_t( u_\lambda)\right] = D\FF( \Phi_t(u_\lambda) \left[ {d \over d \lambda} \Phi_t( u_\lambda)\right] \cr & {d \over d \lambda} \Phi_t( u_\lambda)\big|_{t = 0} = u - {\tilde u} } \EQ(variation) $$ \noindent Observe that, for fixed $t$ and $\lambda$, $D\FF(\Phi_t(u))$ is a bounded linear operator on $\ell^\infty( \Gamma, \real).$ And note that in this representation the matrix elements of $D \FF( \Phi_t( u_\lambda)) $ are positive if they are off the diagonal, and are bounded on the diagonal. Let $M(t) = D\FF(\Phi_t(u_\lambda))$, $D_t$ be the diagonal part of $M(t)$ and $N(t)$ be the non-diagonal part. If $H$ is $C^3$ it follows that the mappings $t \mapsto M(t), D(t), N(t)$ are $C^1$ and the derivatives are uniformly bounded. Following the method of variation of constants, we try to write the solution of \equ(variation) as $\exp\left[ \int_0^t D(s) ds \right] C(t)$. Since all the diagonal elements commute among themselves, we have: $$ {d \over dt } \exp\left[ \int_0^t D(s) ds \right] = \exp\left[ \int_0^t D(s) ds \right] D(t) = D(t) \exp\left[ \int_0^t D(s) ds \right].$$ Hence equation \equ(variation) becomes: $$ \eqalign{ &{d \over dt} C(t) = \left( \exp\left[ -\int_0^t D(s) ds \right] N(t) \exp\left[ -\int_0^t D(s) ds \right] \right) C(t) \cr & C(0) = u - {\tilde u} \cr } \EQ(Cequation) $$ Noting that $\exp\left[ -\int_0^t D(s) ds \right]$, $ N(t)$, $\exp\left[ -\int_0 ^t D(s) ds \right]$ all have non-negative matrix elements, it follows that the initial value problem \equ(Cequation) is equivalent to: $$ C(t) = ( u - {\tilde u} ) + \int_0^t R(s) C(s) ds \EQ(integeq) $$ where $R(s)$ is a matrix that has non-negative entries. As is standard, we obtain that the R.H.S. of \equ(integeq) can be considered an operator acting on continuous functions defined on an interval $[0,T]$. It is a contraction if this space of continuous functions has the metric $ d( C, \tilde C) = \sup_{t \in [0,T]} || C(t) - {\tilde C} (t) || e^At,$ where $A$ is sufficiently large. From the fact that $R(s)$ has positive entries and that $u - \tilde u \le 0$ it follows that the operator defined by the R.H.S. of \equ(integeq) preserves the set of $C$'s such that $C(t) \ge 0$ for all $t$. And finally, since the solution can be obtained by iterating the R.H.S. of \equ(integeq) with starting point $u - \tilde u$, it follows that the solution is negative and the proof of \clm(comparison) is complete. \QED Since the fact that a configuration is Birkhoff can be expressed in terms of the translations that commute with the heat flow, and of the order (which we have shown is preserved), we obtain: \CLAIM Corollary (birkhoffpreserved) Under the above conditions, $$ \Phi_t( \BB_\omega) \subset \BB_\omega. $$ Moreover, the flow $\Phi_t$ can be defined on $\BB_\omega/ \RR$. Given any finite $\Lambda \subset \Gamma$ we define: $$\SS_\Lambda (u) = \sum_{B\cap \Lambda \ne \emptyset} H_B (u ).$$ \noindent A simple calculation shows: $$\eqalign{ {d\over dt} S_\Lambda \bigl(\Phi_t (u)\bigr)\Big|_{t=0} &= \sum_{B\cap \Lambda\ne \emptyset} \sum_{j\in B;i} {\partial H_B (u) \over\partial u^i_j} \FF(u)_{j} (u)\cr & = \sum_{B\cap \Lambda \ne\emptyset} \sum_{j\in B\cap\Lambda;i} {\partial H_B (u) \over \partial u^i_j} \FF(u)_{j} (u) + \sum_{B\cap \Lambda \ne\emptyset} \sum_{j\in B/\Lambda;i} {\partial H_B (u)\over \partial u^i_j} \FF(u)_{j} (u) \cr &= \sum_{j\in\Lambda;i} \FF(u)_{j} \sum_{B\owns j} {\partial H_B(u)\over\partial u^i_j} + \sum_{B\cap \Lambda \ne \emptyset} \sum_{j\in B/\Lambda;i} {\partial H_B(u)\over \partial u^i_j} \FF(u)_{j} (u)=\cr &= -\sum_{j\in\Lambda;i} |\FF(u)_{j}(u)|^2 + \sum_{B\cap \Lambda\ne\emptyset} \sum_{j\in B/\Lambda;i} {\partial H_B(u)\over\partial u^i_j} \FF(u)_{j} (u)\ .\cr}$$ \noindent Notice that on the last line the first term is obviously non positive and that the second one only involves boundary terms. Intuitively, the first term should dominate since it is a term that depends on the bulk while the other depends only on the boundary. In the case $m=1$ and nearest neighborhood interactions this was proved in [Go]. Nevertheless, that proof does not generalize to higher dimensions since it relies on the fact that there are only two boundary terms independently of the size of the cube. Fortunately, for our purposes considerably less is needed. \CLAIM Lemma(bulkbounds) Let $\CC$ be a collection of subsets of $\Gamma$ as in \clm(inflation). Assume that there is no critical point in $\BB_\omega$. Then we can find $\epsilon_0 > 0$ and $L_0 \in \natural$ such that for all configurations $u \in \BB_\omega$, all sets $\Lambda \in \CC$, and $|\Lambda| > L_0$, we have: $$\sum_{j \in \Lambda} |\FF(u)_{j}|^2 \ge \epsilon_0.$$ \PROOF Let $E_{\Lambda}(u) \equiv \sum_{j \in \Lambda;i} |\FF(u)_{j}|^2$. Notice that $E_{\Lambda'}(u) \le E_{\Lambda}(u)$ whenever $\Lambda' \subseteq \Lambda$. We now proceed by contradiction and assume, contrary to the conclusion, that we can find a sequence $u^{(n)}\in {\BB _{\omega}}$ and a sequence $\Lambda_n$ of sets in $\CC$ with $|\Lambda_n| \to \infty$ such that $$E_{\Lambda_n} (u^{(n)}) \longrightarrow \ 0 \qquad \hbox{ as }n\to \infty. $$ \noindent By assumption $i)$ in \clm(inflation), we can find ${k_n} \in {\tilde G}$ such that $T_{k_n} \Lambda_n$ converges to $\Gamma$. Since $E_{\Lambda}$ is invariant under translations in ${\tilde G}$, (i.e. $E_{\Lambda} (u)=E_{T_k \Lambda} ( \Tau_k u)$ whenever $k \in {\tilde G}$), if we consider $\Lambda'_n = T_{k_n} \Lambda_n$ and $u'^{(n)} = \Tau_{k_n} u^{(n)}$ we have obtained a sequence of sets ${\Lambda'}_n$ converging to $\Gamma$ and a sequence of configurations $u'^{(n)} \in \BB_\omega$ such that $E(\Lambda'_n)( {u'}^{(n)} )$ converges to zero. By the compactness of $\BB_{\omega}/\RR$ we can find a subsequence $u'^{(n_k)}$ that converges (in $\BB_{\omega}/\RR$) to $u^{(\infty)}.$ We want to conclude that $u^{(\infty)}$ is a critical point. (This would contradict the assumption that there is no critical point and hence prove \clm(bulkbounds). In effect, if we fix $j \in \Gamma$ we have $$ |\FF (u^{(\infty)})_j|^2 = \lim_k |\FF(u'^{n_k})_j|^2 \le \lim_k E(\Lambda'_{n_k})( u'^{(n_k)}) $$ The first equality is true because $\FF_j$ depends only on the value of the configuration on a finite number of sites and we have point-wise convergence. The second holds because $E$ is a sum of non-negative terms one of which is eventually $|\FF_j|^2$; since the limit of the R.H.S. is zero, we conclude that $\FF_j = 0$ for any $i,j$. Hence, $u^{(\infty)}$ is a critical point and our contradiction is established. \QED \CLAIM Corollary(bulkboundsimproved) Assume there are no critical points in ${\BB}_\omega$. Then we can find $\epsilon^* >0$ and $L^* \in \natural $ such that for all configurations $u\in {\BB}_\omega,$ and all sets in $\CC$ of size longer than $L^*,$ we have $$\sum_{j \in \Lambda;i} |\FF(u)_j|^2 \ge \epsilon^* |\Lambda|^\alpha$$ where $\alpha$ is as in \clm(inflation). \PROOF Let $L^*$ be as in \clm(bulkbounds). Applying repeatedly part $iii)$ of \clm(inflation), we obtain that all sets $\Lambda$ of sufficiently large size can be broken into $N^k$ disjoint pieces contained in $\CC,$ each of which has size larger than $|\Lambda|/M^k$. If we choose $k = [ \log( | \Lambda|/N*)/ \log(N) ] $ we conclude that we can divide the set into at least $K |\Lambda|^\alpha$ disjoint pieces each of which is of size at least $N^*$. Since the sum can be divided into the sum of each of these pieces, and \clm(bulkbounds) tells us that they are bounded uniformly away from zero, the claim is established.\QED Continuing the argument to prove \clm(main) for finite range systems, we have on the other hand that if the range of the interaction is $r$ and $\Lambda$ is a set in $\CC$: $$ \left| \sum_{B\cap \Lambda\ne\emptyset} \sum_{j\in B/\Lambda;i} {\partial H_B (u) \over \partial u^i_j} \FF(u)_j\right| \le \sum_{B\cap \Lambda\ne\emptyset} \sum_{j\in B/\Lambda;i} \left| {\partial H_B (u) \over \partial ui_j}\right| M_1 \le K \phi(r,|\Lambda|) $$ \noindent where $\phi$ has the same meaning as in \clm(inflation). Since by assumption $iii)$ of \clm(inflation) this is negligible compared with the lower bounds in \clm(bulkboundsimproved), we obtain: \CLAIM Corollary(derivative) If there are no critical points in ${\BB}_\omega$, then for all large enough sets $\Lambda$ of $\CC$ we have: $${d\over dt} S_\Lambda (u)\big|_{t=0} \ge K(|\Lambda|) >0$$ where $K(|\Lambda|)$ does not depend on $u$. Furthermore, since ${d^2\over dt^2} \Phi_t(u)$ is a continuous function on ${\BB}_\omega/\RR$, which is a compact set, we can bound it uniformly in $u$. It follows that if there is no critical point in $\BB_\omega$ we can find $t_0 >0$ and a cube $\Lambda\subset \integer^m$ such that $$S_\Lambda (\Phi_{t_0}(u)) \ge S_\Lambda (u) +\delta$$ with $\delta >0$. This is impossible since $\SS_\Lambda$ is a continuous function on the compact set. From this contradiction we conclude there is a critical point in $\BB_\omega$ and \clm(main) is proved under the assumption that $H$ is of finite range and $3$ bounded. To conclude the proof of \clm(main) as stated, we just have to show that a $2$ bounded interaction can be approximated by a sequence of interactions for which the theorem as proved so far applies in such a way that the critical points thus produced converge to a critical point of the interaction. \CLAIM Lemma (approximation) Let $\FF^n$ be a sequence of vector fields derived as in \equ(flowequations) from an interaction $H^n$ satisfying condition \equ(perphase) (periodic phase space). Assume that each of the $\FF$'s admits a critical point in $\BB_\omega$. Assume furthermore that there is another vector field $\FF^\infty$ coming from an interaction $H^\infty$ satisfying condition \equ(perphase). Finally, assume: \item{$i)$} For every $i \in \Gamma$, every $u \in \BB_\omega$, $\FF^n(u)_i \to \FF^\infty(u)_i$ \item{$ii)$} $\sum_l \sup_n \sum_{|B| = l} \sup_{u \in \OO_\omega} \sum_{i \in \Gamma} | {\partial^2 \over \partial u_i \partial u_j } H^n_B(u)| $ \vskip 0em Then $\FF^\infty$ has a critical point in $\BB_\omega$. \REMARK The interpretation of condition $ii)$ is that if we truncate any of the interactions $H^n$ to those interaction terms which correspond to sets of size $L$, the error incurred can be made arbitrarily small uniformly in $n$, in the sense of the $||\quad||_{2}$ semi-norm. This is a technical condition that will be easy to verify for the cases that we have in mind. The main one is when we consider a $2$ bounded interaction and approximate it by finite range ones which are obtained by ignoring the interaction terms that have size larger than a certain number. \PROOF Denote by $\FF_n$ the vector field in $\OO_\omega$ corresponding to the interaction $H^n$. Denote by $\FF_\infty$ the vector field corresponding to the limiting interaction. If $u^n$ are the critical points corresponding to $H^n$, we have $\FF_n(u^n) = 0$. Given the invariance under $\RR$ of the interaction, by substituting $\RR_{q_n} u^n$ for our original configurations and using \equ(coordinatebounds), we can assume that for all $n,n'\in \natural$ we have $||u^n - u^{n'}||_{\ell^\infty} \le 2 p$, so $$ ||u^n - u^{\infty}||_{\ell^\infty} \le 2 p. \EQ(uniformdistance) $$ By the compactness of $\BB_\omega/\RR$ given a sequence as above, we can obtain a subsequence that converges to a limiting configuration in the sense of point-wise convergence. So that, by passing to a subsequence, we can assume without loss of generality that $u^n \to u^\infty$ in the point-wise sense and $\FF^n(u^n) = 0$. If we fix $i \in \Gamma$, we have for any $n, L \in \natural$: $$ \eqalign{ |\FF^\infty( u^\infty )_i | = &|\FF^\infty(u^\infty)_i - \FF^n(u^n)_i| \cr &\le | \FF^\infty(u^\infty)_i - \FF^n(u^\infty)_i| + | \FF^n(u^\infty)_i - \FF^n(u^n)_i| \cr &\le |\FF^\infty(u^\infty)_i - \FF^n(u^\infty)_i | \cr &\ \ \ + \big|\sum_{B\ni i \atop |B| \le L} {\partial \over \partial u_i} H^n_B( u^\infty) - \sum_{B\ni i \atop |B| \le L} {\partial \over \partial u_i} H^n_B( u^n)\big| \cr &\ \ \ +\sum_{B\ni i \atop |B| > L} \left| {\partial \over \partial u_i} H^n_B( u^\infty) - {\partial \over \partial u_i} H^n_B( u^n)\right|\cr } \EQ(splitting) $$ Given any $\epsilon > 0$, by condition $ii)$ $ \sup_{u \in \OO_\omega} \sum_{|B| > L} \sum_{i'} |{\partial^2 \over \partial u_i \partial u_{i'}} H^n_B(u^n) | \le \epsilon/6p $. Using \equ(uniformdistance) and \clm(interpolation), this implies that $| {\partial \over \partial u_i} H^n_B( u^\infty) - {\partial \over \partial u_i} H^n_B( u^n)| \le \epsilon/3$ independently of $n$. Once $L$ is chosen, we can find $n$ large enough so that the first term in the sum in \equ(splitting) is smaller that $\epsilon/3$, and given the uniform convergence assumption in \clm(approximation) we can make arbitrarily small the last term in \equ(splitting). \QED To conclude the proof of \clm(main), we observe that a $2$ bounded function of finite range can be approximated, in the sense required \clm(approximation), by $C^3$ functions of finite range by using just the usual smoothing of finite dimensional variables for each of the $H_B$'s. The twist condition is preserved since it only depends on the second derivatives of sums of of finitely many functions of finitely many variables, which we are approximating. Hence, we can use the results we have already proved to prove $a)$ of \clm(main). In the case where we have an interaction satisfying $b)$ of \clm(main), we can just approximate the interaction by the cut-off interactions which agree with the original interaction on sets of size up to $n$ and are zero for larger sets. It is easy to check that under the hypothesis of the strong twist condition all these interactions will also satisfy the strong twist condition and also converge in a sense strong enough for \clm(approximation) to apply. This concludes the proof of \clm(main). \QED \REMARK We note that the regularity hypothesis in \clm(main) can be slightly weakened. The most delicate analytical point of the proof is that the heat flow can be defined on $\BB_\omega$ for all time. Then, one can use the argument starting in \clm(bulkbounds). We concluded the existence of the flow for all time by making assumptions that implied that $\FF$ was uniformly Lipschitz and then showed that the comparison principle and symmetries lead to the preservation of the Birkhoff character. Note that since we know that $\BB_\omega \subset \OO^2_\omega$, it would have sufficed to show that there is a flow defined defined for a positive time for conditions starting in $\OO^3_\omega$ and that comparison held. Then, the same argument we have detailed shows that the $\BB_\omega$ is preserved, hence, that the flow exits for all times when the conditions are Birkhoff. There are indeed some models for which this generality leads to new results, but we do not know of any physically interesting one. Nevertheless, analogues of these arguments are needed when generalizing this argument to PDE's. \SECTION Applications In this section, we discuss some models that can be reduced to situations in which $G \ne \tG$. That is, the group that leaves invariant the interaction -- and with respect to which we define Birkhoff orbits -- is smaller than the group that leaves invariant the lattice. Besides the conceptual simplification of not identifying objects that play different roles, having these models was an important motivation. As a first example we show how finite compositions of twist mappings can be considered in this framework. (This application had been considered by other methods in \cite{Ma3}) This addresses the fact that even if the conclusions in the dynamical version of Aubry-Mather theory are invariant under changes of coordinates, the twist hypothesis is not. Relatedly, even if the conclusions of Aubry-Mather theory for a map $f$ imply the same conclusions for $f^n$, it is not true in general that $f^n$ satisfies the twist hypothesis. We recall -- we refer to \cite{Ma1} for further details and for some precisions about uniformity assumptions that one has to do to deal with the the absence of -- that, given a diffeomorphisms $M$ of $\torus^n\times \real^n$ that preserves the symplectic form $\omega = \sum_i d p_i \wedge d q_i$ and is exact ($ M^* ( \sum_i p_i d q_i ) = \sum_i p_i d q_i + d S$) where $S: \torus^n\times\real^n \to \real$. If we denote by $(P',Q')$ the image of $(P,Q)$ under the map and assume that $(Q,Q')$ is a good system of coordinates. (This happens if $ |det(\partial Q' \partial P) | \ge a > 0$.) Then, we can find a generating function $h$ such that the statement $M(P,Q) = (P',Q')$ is equivalent to $P'= \partial_2 h(Q,Q')$, $P = - \partial_1 h(Q,Q')$. In that case, a sequence $Q_n$ is the projection of an orbit if and only if it is a critical point of the formal action $ \sum_{n \in \integer} h(Q_n,Q_{n+1})$ If $h^\alpha$, $\alpha = 1,\cdots,p,$ is a finite set of these generating functions, corresponding to twist maps $M_\alpha$, we see that if we consider the formal action principle: $$ \SS( Q) = \sum_n h^\alpha( Q_{n p + \alpha}, Q_{np +\alpha +1}) \EQ(actioncomposition) $$ the variational equations are: $$ \partial_1 h^\alpha( Q_{n p + \alpha}, Q_{n p + \alpha +1}) + \partial_2 h^{\alpha -1} ( Q_{n p + \alpha -\alpha}, Q_{n p + \alpha }). \EQ(hamiltoniancritical) $$ That is, if we set $$ P_{n p + \alpha} = -\partial_1 h^\alpha( Q_{n p + \alpha}, Q_{n p + \alpha +1}), \EQ(Pdefinition) $$ the equations \equ(hamiltoniancritical) imply that: $$ P_{n p + \alpha +1} = \partial_2 h^\alpha( Q_{n p + \alpha}, Q_{n p + \alpha +1}). \EQ(derivedcritical) $$ Taking together \equ(Pdefinition) and \equ(derivedcritical), we obtain: $$( Q_{n p + \alpha +1}, P_{n p + \alpha +1} ) = M^\alpha( Q_{n p + \alpha}, P_{n p + \alpha} ).$$ \noindent Hence $ \{ (Q_{n p}, P_{n p}) \}$ is an orbit for $M^p \circ M^{p-1} \circ M^1$. The variational principle for the action \equ(actioncomposition) can be fitted into those considered in \clm(main) if we consider a one-dimensional lattice $\Gamma = \integer$ with group of translations $\integer$ and reduced group $p \integer$. Clearly, the action is invariant under these reduced groups. The only partial derivatives that are not zero are those corresponding to neighboring points, and in this case they reduce to the twist condition for the individual maps. Notice that this problem is equivalent to the problem of considering the map obtained by composing the $p$ twist maps. Nevertheless, in general the map will not satisfy the twist condition. This construction has an analogue in higher dimensions if we associate to a site in a lattice $\integer^d$ a value in $\real^{l^{(d-1)2d}}$. Notice that there is an identification $\sigma$ between $[1, {l^{(d-1)2d}}]$ and the boundary of $\Lambda_l$, the cube of size $l$. Given a state $u$ we can associate to it the energy $V(u) = \min\{E({\tilde u})\ :\ {\tilde u}: \Lambda_l \to \real, {\tilde u}|_{\partial \Lambda_l} = u\circ \sigma\},$ where $E({\tilde u})$ satisfies the twist conditions. The Frenkel-Kontorovna model for this interaction can be identified with a one-component Frenkel-Kontorovna model in which each of the sites is blown up to a cube $\Lambda_l$ and the interaction between the new sites is given by the expression $E$ if they are in the same block, and by the original Frenkel-Kontorovna if they have adjacent boundaries. In general this process leads to models in which the potential cannot be expressed as a sum of functions of the one-dimensional variables. Hence the multidimensional analogue of the twist condition is violated. This is very similar to the process that is called {\sl ``conjunction''} in [Ma3]. It can also be considered an analogue of the block spin renormalization of statistical mechanics, and indeed the renormalization group picture of [McK] can also be formulated in this language. Notice that if the dimension of the {\sl `` time'' } is larger than one the renormalization process increases the number of variables. In the one-dimensional time case -- the one most interesting for dynamics -- the number of variables does not increase. We also point out that an statistical mechanics interpretation of these models is molecules laid in a linear substratum. The atoms in the molecule interact with their nearest neighbors and with the substratum in a way that depends on the chemical element. Since the molecules are arranged periodically, the interactions are periodic with a period equal to the number of atoms in the molecule. We also point out that this formalisms also allows to deal with some restricted classes of several component models. In the statistical mechanics interpretation, this would correspond to situations where the internal state of an atom is describe by several parameters. Frenkel-Kontorovna models with $p$ components have configurations which are maps $u: \integer^n \to \real^p$. We will denote the components by superscripts and, as before, the site of the lattice by a subindex. So for a vector $i \in \integer^n$, $u_i$ denotes the vector in $\real^p$ which is the value taken by the configuration at the site $i$. For an integer $j \in \{1,\cdots,p\}$, $u_i^j$ will denote component $j$ of the $\real^p$ vector $u_i$. Similarly, we will denote by $u^j$ the mapping $\integer^n \mapsto \real$ that to each site associates the $j^{th}$ component of the configuration at the site. The interaction of such a multicomponent Frenkel-Kontorovna model is given by $H_{\{i\}} = V(u_i)$, where $V(x + e) = V(x)$ if $e$ is a vector with integer components of length $1$, $H_{\{i,j\}}(u) = 1/2n\ |u_i - u_j|^2$ if $|i -j| = 1$, and $H_B(u)=0$ for any other set $B$. To reduce such models to the situation discussed in \clm(main), we introduce an auxiliary one-component model in which $ \hat \Gamma = \integer^n \times \integer$. The group $G$ of the new model will be $\integer^n \times \integer$ acting in the obvious way, and ${\tilde G} = \integer^n \times p \integer$. The configurations $\hat u$ in the auxiliary model can be obtained from those in the old one by setting ${\hat u}_{(i_1,\cdots,i_p,i_{p+1}) } = u_{(i_1,\cdots,i_p)}^{i_{p+1} \bmod p}$. The interactions are given by: $$ \hat H_{\{(i_1,\cdots,i_p, pn +1), \cdots, (i_1,\cdots,i_p, pn +p)\}} = V( {\hat u}_{(i_1,\cdots,i_p,p n +1)},\cdots,{\hat u}_{(i_1,\cdots,i_p,p n +p)} $$ If $\sum_{\alpha = 1,\ldots,p} |i_\alpha - j_\alpha| = 1$, we define: $$ {\hat H}_{ \{(i_1,\ldots,i_p, \ell),(j_1,\ldots,j_p,\ell)\}} = {1 \over 2}\left( {\hat u}_{(i_1,\cdots,i_p,\ell)} - {\hat u}_{(j_1,\cdots,j_p,\ell)}\right)^2 $$ This identification can be interpreted as saying that we lump together segments of $p$ elements in the vertical direction and consider them as a site in the original problem. If we have a configuration $\hat u$ of the extended system satisfying $$ {\hat u}_{(i_1,\ldots,i_p,i_{p+1})} = {\hat u}_{(i_1,\ldots,i_p, i_{p+1} +p )} \EQ(periodicity) $$ and it satisfies the equations \equ(variationsstatmech) the $p$ component configuration $u$ satisfies the equation \equ(variationsstatmech) for the reduced model. Given a frequency $\omega =(\omega_1,\ldots,\omega_p)$ we can consider an extended frequency $\hat \omega = (\omega_1,\ldots,\omega_p, 1/p)$. The Birkhoff configurations of this extended frequency have to satisfy the periodicity condition \equ(periodicity). Unfortunately, these models, even if they have a natural interpretation in Statistical Mechanics, they do not have such a nice interpretation as twist maps in the annulus. (They are dynamical systems in $\real^{2d}$.) For the Frenkel Kontorovna model to verify the twist condition of \clm(main) we have to assume that ${\partial^2 \over \partial u_{i} \partial u_{i'} } V(u) \ge 0$ when $i' \ne i$. Unfortunately, if we want that they are functions in a torus $ V(u_1 +1, u_2,\cdots,u_p) = V( u_1, u_2 +1,\cdots,u_p)= \cdots = V(u_1,u_2,\cdots,u_p+1) = V(u_1,u_2,\cdots, u_p)$ we have considered this implies that $V(u) = V_1(u_1)+\cdots+V_p(u_p)$, so the model reduces to uncoupled one-dimensional cases. \SECTION References \ref \no{AD} \by{S. Aubry, P. Y. Le Daeron} \paper{ The discrete Frenkel Kontorovna model and its extensions: Exact results for the ground state} \jour{Physica} \vol{8D} \pages{240-258} \yr{1983} \endref \ref \no{An} \by{S. Angenent} \paper{ Monotone recurrence relations, their Birkhoff orbits and topological entropy} \jour{Ergod. Th. and Dyn. Syst.} \vol{10} \pages{15-41} \yr{1990} \endref \ref \no{BK} \by{D. Bernstein, A. Katok} \paper{ Birkhoff periodic orbits for small perturbations of completely integrable systems with convex Hamiltonians} \jour{Inv. Mat.} \vol{88} \pages{225-241} \yr{1987} \endref \ref\no{Ba} \by{V. Bangert} \paper{Mather sets for twist maps and geodesics on tori} \jour{Dynamics Reported} \vol{1} \pages{1-54} \yr{1988} \endref \ref\no{B1}\by{M.L. Blank}\paper{Metric properties of minimal solutions of discrete periodical variational problems} \jour{Nonlinearity}\vol{2}\pages{1-22}\yr{1989}\endref \ref\no{B2}\by{M.L. Blank}\paper{Chaos and order in the multidimensional Frenkel-Kontorovna model} \jour{Sov. Phy. JEPT}\vol{85}\pages{1255-1268}\yr{1989}\endref \ref \no{He} \by{M. Herman} \paper{In\'egalit\'es `` a priori'' pour des tores Lagrangiens invariantes par des diff'eomorphismes symplectiques} \jour{Pub. Mat. I.H.E.S} \endref \ref\no{Go}\by{C. Gol\'e}\paper{A new proof of Aubry--Mather's theorem}\jour{E.T.H. preprint}\endref \ref \no{Gr} \by{R. Griffiths} \paper{Frenkel-Kontorovna models of commensurate-incommensurate transitions} \jour{preprint} \yr{1991} \endref \ref\no{McK}\by{R.S. McKay}\paper{Scaling exponents at the transition by breaking of analyticity for incommensurate structures}\jour{Physica}\vol{50D}\pages{71-79}\yr{1991}\endref \ref\no{Ma1}\by{J. Mather}\paper{A criterion for non existence of invariant circles}\jour{Pub. Mat. I.H.E.S.}\vol{63}\pages{153 --204}\yr{1987}\endref \ref\no{Ma2}\by J. Mather\paper{Existence of quasiperiodic orbits for twist homeomorphisms of the annulus}\jour{Topology}\vol{21} \pages{457-467}\yr{1982}\endref \ref \no{Ma3} \by{J. Mather} \paper{Variational construction of orbits of twist diffeomorphisms} \jour{Jour. Am. Math. Soc.} \vol{4} \pages{207-263} \yr{1991} \endref \ref \no{Mo} \by{J. Moser} \paper{Minimal solutions of variational problems on a torus} \jour{Ann. Inst. H. Poinc. An. non lin.} \vol{3} \pages{229-272} \yr{1986} \endref \ref \no{Mo2} \by{J. Moser} \paper{A stability theorem for minimal foliations on a torus} \jour{Ergod. Theo. Dyn. Syst.} \vol{8} \pages{251-281} \yr{1988} \endref \ref\no{OV}\by{A. Olvera, C. Vargas}\paper{A continuation method to study periodic orbits in the Froeschl\'e map}\jour{Physica}\vol{72 D} \pages{351-371}\yr{1994}\yr{1992}\endref \ref \no{Ru} \by{D. Ruelle} \book{Statistical Mechanics} \publisher{Benjamin, Reading MA} \yr{1969} \endref \ref \no{V} \by{F. Vallet} \paper{Thermodynamique unidimensionelle, et structures bidimensionelles de quelques mod\`eles pour des syst\`emes incommensurables} \jour{ U. Paris VI thesis} \yr{1986} \endref \end