\magnification 1200 \hsize=5.8truein \hoffset=.25truein %was \hoffset=1.2truein \vsize=8.8truein %\voffset=1truein \pageno=1 \baselineskip=12pt \parskip=0 pt \parindent=20pt \overfullrule=0pt \lineskip=0pt \lineskiplimit=0pt \hbadness=10000 \vbadness=10000 % REPORT ONLY BEYOND THIS BADNESS \let\nd\noindent % NOINDENT \def\NL{\hfill\break}% NEWLINE \def\qed{\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}} \parindent=40pt \pageno=1 \footline{\ifnum\pageno=1\hss\else\hss\tenrm\folio\hss\fi} \hbox{} \vskip 1truein\centerline{{\bf Z$^n$ Versus Z Actions for Systems of Finite Type}\footnote*{Research supported in part by NSF Grant No. DMS- 9001475\hfil}} \vskip .7truein\centerline{by} \centerline{Charles Radin} \vskip .2truein\centerline{Mathematics Department} \centerline{University of Texas} \centerline{Austin, TX\ \ 78712} \centerline{USA} \vskip 1truein\centerline{Conference talk at ``Symbolic Dynamics and its Applications''} \vskip0truein \centerline{July 28 - August 2, 1991 at Yale University} \vskip .5truein\centerline{ABSTRACT} {\narrower\vskip .2truein\noindent We consider dynamical systems of finite type with {\bf Z$^n$} \hbox{actions,} and discuss the differences between the cases $n=1$ and \hbox{$n\ge 2$.} For the latter we examine the degree of ``order'' which is \hbox{possible} when the system is uniquely ergodic.\smallskip} \hfil\eject \parindent=20pt \leftline{{\bf Systems of finite type.}} \vskip .05truein We begin with some notation. Let {\it A} be a finite alphabet, and consider the ``infinite arrays'' ${\it A}^{{\bf Z}^n}$ as functions on ${\bf Z}^n$. We say that the dynamical system which consists of the natural action of ${\bf Z}^n$ on $X \subseteq {\it A}^{{\bf Z}^n}$ is ``of finite type'' if there is some finite $C \subset {\bf Z}^n$ and finite set of finite arrays $F \subset {\it A}^C$ (thought of as restrictions $x\vert _C$ to $C$ of functions $x$ in ${\it A}^{{\bf Z}^n}$) such that $$ X = X_F \equiv \{x \in {\it A}^{{\bf Z}^n}\,:\,\hbox{for all }t\in {\bf Z}^n,\, x_t\vert _C \notin F\} \eqno 1)$$ \noindent where $x_t(j) \equiv x(j-t)$ for $t,j\in {\bf Z}^n$. It is easy to see that certain choices of $F$ will lead to an empty $X_F$. For this and other reasons it is useful to ``redefine'' $X_F$, whereby instead of {\bf forbidding} restrictions in $F$ from appearing in the arrays we just {\bf minimize their appearance}. We do this using the ``energy function'' $E\,:\,{\it A}^C \to {\bf R}$ defined to be the characteristic function of $F$. (That is, $E(f) = 1\hbox{ for }f\in F,\ E(f) = 0\hbox{ for } f\notin F$.) We then define: $$\eqalign{\tilde X_E \equiv \big\{x \in {\it A}^{{\bf Z}^n}\,:\,\hbox{for every } &\hbox{finite }B\subset {\bf Z}^n,\cr &E^B(x) = \inf\{E^B(y)\,:\,y = x\hbox{ outside }B\}\big\}\cr}\eqno 2)$$ \vskip .1truein \noindent where $E^B(z) \equiv \sum\{E(z_t\vert _C)\,:\,t\in Z^n,\,B_{-t}\cap C\neq\emptyset\}$. Clearly $X_F \subseteq \tilde X_E$. Furthermore it is easy to prove using the compactness of ${\it A}^{{\bf Z}^n}$ that $\tilde X_E$ is always nonempty, in fact for an arbitrary function \hbox{$E\,:\,{\it A}^C\to {\bf R}$}, not just characteristic functions. We therefore define a ``zero temperature'' dynamical system as one defined by 2) for any fixed function $E$. \vskip .2truein \leftline{{\bf Unique ergodicity.}} \vskip .05truein We say $X \subset {\it A}^{{\bf Z}^n}$ is ``uniquely ergodic'' if there is one and only one Borel probability measure on $X$ invariant under the natural action of ${\bf Z}^n$. Consider the following three classes of uniquely ergodic systems. \vskip .1truein\noindent i)\ All uniquely ergodic $X \subset {\it A}^{{\bf Z}^n}$ \vskip .05truein\noindent ii)\ All uniquely ergodic zero temperature $X \subset {\it A}^{{\bf Z}^n}$ \vskip .05truein\noindent iii)\ All uniquely ergodic $X \subset {\it A}^{{\bf Z}^n}$ of finite type \vskip .1truein\noindent It is clear by construction that there is containment as one descends the list, but proper containment is not obvious. Our first result along this line is the following (known as the Third Law of Thermodynamics). \vskip .1truein\noindent Theorem (J.~Mi\c ekisz and C.~R.~[7]).\ All uniquely ergodic zero temperature \vskip 0truein\noindent$X \subset {\it A}^{{\bf Z}^n}$ have zero topological entropy. \vskip .1truein\noindent This together with the theorem of Jewett-Kreiger-Weiss [11] shows that the first containment is proper. We do not know a proof that the second containment is proper, but there is a preprint by Mi\c ekisz [3] going part way. \vskip .2truein \leftline{{\bf ${\bf Z}^n$ Versus {\bf Z} Actions.}} \vskip .05truein\noindent To say that a symbolic system $X \subset {\it A}^{{\bf Z}^n}$ is of finite type implies that each variable, with values in {\it A}, corresponding to a point of ${\bf Z}^n$ can only directly affect nearby variables. This is reminiscent of the differential equations of the natural sciences. One of the main points we wish to make follows by analyzing such nonmathematical applications of ${\bf Z}^n$ and {\bf Z} actions. We envision {\bf Z} actions as typically modeling {\bf evolution} problems; that is, {\bf Z} represents time. We reformulated the condition of finite type above as an optimization condition, for reasons we will soon discuss. With this in mind, we note that evolution problems can also sometimes be reformulated as optimization problems -- think of the least action principle for Hamiltonian systems for example. However in such a reformulation it is typical that one seeks as solutions critical points, not global optima, and that such critical points can represent a wide variety of curves. On the other hand, the $n$ translation variables of ${\bf Z}^n$ actions often represent spatial translations, and, as in the crystal problem of condensed matter physics, or the sphere packing problem, or the problems of space tiling, what one seeks is typically (generically [5,6,7]) a {\bf unique} solution (a well defined ``structure'', so to speak) to a global optimization problem of the general form of our zero temperature condition [8]. When properly formulated, the solution is sought in a space of invariant probability measures, and the uniqueness of the solution translates into the property of unique ergodicity. Thus {\bf Z} actions and ${\bf Z}^n$ actions naturally represent very different situations, the former accomomodating a very flexible class of arrays (in particular they are highly nonunique), and the latter representing some unique structure such as a crystal or quasicrystal. This is ``why'' unique ergodicity is not as natural for {\bf Z} actions as it is for ${\bf Z}^n$ actions. Our interest is primarily with ${\bf Z}^n$ actions, and more specifically in the degree to which uniquely ergodic zero temperature systems (or systems of finite type) tend to be ``ordered''. (Why does low temperature matter tend to be crystalline, why do there always seem to be periodic examples among the densest sphere packings in any dimension, why is it hard to find tiles which can only tile space nonperiodically? See [8].) Consider the following extreme cases of ``order'' for a zero temperature system $X$ with unique invariant measure $\rho$. \vskip .1truein\noindent \vbox{\noindent a)\ Periodic; (corresponding to a finite set $X$, the orbit of a periodic array) \vskip .05truein\noindent b)\ Quasiperiodic; (corresponding to $X$ with purely discrete dense spectrum) \vskip .05truein\noindent c)\ Weakly mixing $\rho$; (corresponding to purely singular continuous spectrum) \vskip .05truein\noindent d)\ Strongly mixing $\rho$; (corresponding to purely absolutely continuous spectrum)} \vskip .1truein\noindent (Note that as in probability theory we are using measure theoretic -- chiefly spectral -- properties to analyze the order of the dynamical system.) \vskip .1truein Examples of a) are easy to obtain. Examples of b) were first obtained by R.~Berger in 1966 [1], with nicer examples by R.~Robinson [9] and others. Examples of c) are due to S.~Mozes in 1989 [4,7]. It is unknown if there are examples of d), and this is an important open problem. There are several reasons for our introduction of the class of zero temperature systems. They constitute a natural generalization of systems of finite type with the conditions defining the system still strictly local, and there are real parameters for the class so that one can address questions of genericity. Furthermore, ever since the work of G.~Toulouse [10,2] it has been commonly felt by condensed matter theorists that energy functions $E$ as above which are ``frustrated'' (that is, cannot be reformulated as a characteristic function as is the case for systems of finite type), are more likely to lead to ``disorder'' -- or smooth spectrum, as in models of spin glasses. In other words, physical intuition suggests that the class of zero temperature systems is broader than, and should contain more disordered examples than (perhaps of type d) above), the class of systems of finite type. Needless to say, it would be most interesting if this could be proved true. \hfil\eject \centerline{{\bf REFERENCES}} \vskip .2truein\noindent [1] R.\ Berger, The undecidability of the domino problem, {\it Mem.\ Amer.\ Math.\ Soc. no.\ 66}\ (1966). \vskip.1truein\noindent [2] J.\ Mi\c ekisz, Frustration without competing interactions, {\it J.\ Stat.\ Phys.}\ 55 (1989), 351-355. \vskip.1truein\noindent [3] J.\ Mi\c ekisz, ``The global minimum of energy is not always a sum of local minima -- a note on frustration'', preprint, University of Louvain-la-Neuve, June, 1991 \vskip.1truein\noindent [4] S.\ Mozes, Tilings, substitution systems and dynamical systems generated by them, {\it J. d'Analyse Math.}\ 53 (1989), 139-186. \vskip.1truein\noindent [5] C.\ Radin, Correlations in classical ground states, {\it J. Stat. Phys.}\ 43 (1986), 707-712. \vskip.1truein\noindent [6] C.\ Radin, Low temperature and the origin of crystalline symmetry, {\it Int.\ J.\ Mod.\ Phys.}\ 1 (1987), 1157-1191. \vskip.1truein\noindent [7] C.\ Radin, Disordered ground states of classical lattice models, {\it Revs.\ Math.\ Phys}\ 3 (1991) 125-135. \vskip.1truein\noindent [8] C.\ Radin, ``Global order from local sources'', to appear in October, 1991 issue of {\it Bull.\ Amer.\ Math.\ Soc}. \vskip.1truein\noindent [9] R.M.\ Robinson, Undecidability and nonperiodicity for tilings of the plane, {\it Invent.\ Math.}\ 12 (1971), 177-209. \vskip.1truein\noindent [10] G.\ Toulouse, Theory of frustration effect in spin glasses, I, {\it Commun.\ Phys.\ (G.B)}\ 2 (1977), 115-119. \vskip.1truein\noindent [11] B.\ Weiss, Strictly ergodic models for dynamical systems, {\it Bull. Amer. Math. Soc.}\ 13 (1985), 143-146. \end