INSTRUCTIONS: This paper is in Tex. Reference is made to several figures, which we have not incorporated into electronic format. They can be requested from the author. The paper will appear in the Reseach/Expository section of the Bulletin of the AMS in October, 1991. \magnification 1200 \hsize=5.8truein \hoffset=.25truein \vsize=8.8truein %\voffset=1truein \parskip=0 pt \parindent=20pt \lineskip=0pt \lineskiplimit=0pt \overfullrule=0pt \pageno=0 \baselineskip=16pt \font\bit=cmbxti10 \footline={\ifnum\pageno=0 \tenrm\hfil *Research supported in part by NSF Grant No. DMS-9001475\hfil \else\hfil\tenrm \folio\hfil \fi} \hbox{} \vskip 1truein\centerline{{\bf GLOBAL ORDER FROM LOCAL SOURCES}*} \vskip .5truein\centerline{by} \centerline{Charles Radin} \vskip .2truein\centerline{Mathematics Department} \centerline{University of Texas} \centerline{Austin, TX\ \ 78712} \centerline{USA} \centerline{email: radin@math.utexas.edu} \vskip .8truein \centerline{TO APPEAR IN THE RESEARCH-EXPOSITORY PAPERS SECTION} \vskip .2truein \centerline{OF THE BULLETIN OF THE AMS, OCTOBER 1991} \vskip .4truein \centerline{Subject classification: 47A35, 52A45, 82A55} \vfil \eject \hbox{}\vskip 0truein\noindent 1. {\bf INTRODUCTION} This article contains introductions to three open problems of significant research interest, taken from number theory, logic, and condensed matter physics. All three problems will be shown to have at their core special cases of one simply-stated optimization problem. Our goal is to use the intuition gained from these three perspectives to direct attention to this common core, which constitutes, in fact, one problem of remarkable depth and importance. We will also show that some of the tools developed in the separate problems are of real value in the others. Since each of the three problems uses jargon peculiar to its field, we will give an informal introduction to each, together with all relevant definitions, in the following section. However it may be useful to include here a very brief description of each of them to give some idea of our eventual goal. Our first problem is ``sphere packing'', in which we consider arrangements of infinitely many unit diameter spheres, each sphere having a variable position in ${\bf R}^3,$ and try to determine those ``optimal'' arrangements in which the spheres are disjoint and yet occupy the largest possible fraction of space. The problem from logic was originally concerned with the ``decidability of AEA formulas''. It then expanded to the area now known loosely as ``tiling theory'', in which one analyzes the tilings of the plane which are possible from a given set of tiles. Neighboring tiles must satisfy color (or matching) rules, and we try to optimize agreement of these rules. >From physics we consider the ``crystal problem''. Here the concern is to understand why real matter seems, experimentally, to have a strong tendency to have crystalline order at low temperature and high pressure. The problem is modeled using the equilibrium statistical mechanics of interacting particles, and a concise way to summarize that theory is that the state of the particles must be a minimum of the free energy. A common theme for all three problems is that they involve a system of many objects (spheres, tiles, particles) each of whose position in space has some influence on the others nearby, and we seek those arrangements in space of the objects which optimize something (density, agreement of matching rules, free energy). One remarkable feature which generates interest in these problems is the conviction, based on a variety of evidence, that {\bf in optimal arrangements the objects tend to be very regularly positioned in space -- although the mechanism causing this tendency is completely unknown.} This will be formalized in section 3, leading to natural measures of ``regularity'' or ``order''. In the above snapshots of the problems we have used the jargon of the relevant fields. In the next section we will flesh out the snapshots with the appropriate definitions needed by a nonspecialist. \vskip .2truein\noindent {\bf 2. THREE OPEN PROBLEMS} \vskip .1truein\noindent {\bf 2a. Sphere Packing} In sphere packing we try to find that arrangement in space of unit diameter spheres or balls which are nonoverlapping and yet cover the highest possible fraction of space. (This is part of problem 18 in Hilbert's celebrated list of open problems [17]. A solution has recently been announced by Wu-Yi Hsiang, though no manuscript is generally available yet. ) First let us be more precise about the meaning of ``cover the highest possible fraction of space''. Take the balls to be open -- that is, translates of $\bigl\{(x_1,x_2,x_3)\in {\bf R^3} : x_1^2 + x_2^2 + x_3^2 < 1/4\bigr\}$ -- and, given an arrangement $A$ of infinitely many disjoint balls, consider an increasing sequence $S(n)$, of spheres of radius $n$, all centered at the origin in ${\bf R^3}$. Let $d(A)$ (the ``density of $A$'') be the fraction of the volume of $S(n)$ which is contained in those balls of $A$ which are inside $S(n)$, asymptotically in $n$, namely $$ d(A) = \liminf_{n\to\infty}{{\hbox{ volume of balls of $A$ in }S(n)}\over \hbox{ volume of }S(n)}.$$ \noindent What is then desired is the supremum of $d(A)$ over all possible arrangements $A$, and those ``optimal'' arrangements $A'$ such that $d(A') = \sup_Ad(A).$ (It is not hard to see that such optimal arrangements exist: the supremum is really a maximum.) The sphere packing problem is old (going back at least to Gauss [13]) and unsolved, though for many years it has been generally accepted [34] that one optimal arrangement (among others) has the centers of the balls at the points of a ``face-centered cubic lattice'', which, using a Euclidean basis of ${\bf R}^3$, can be given by: $\{a_1(0,s,s) + a_2(s,0,s) + a_3(s,s,0) : s=\surd(1/2),\ a_j\in {\bf Z}\}$. (This collection of points is called a ``lattice'' because it is of the form $\{a_1v_1 + a_2v_2 + \cdots + a_nv_n : a_j\in {\bf Z}\}$ for some basis $\{v_1,v_2,\cdots, v_n\}$ of ${\bf R}^n;$ see Fig.~1a. Since we will frequently refer to the centers of balls, from now on we will use the word ``configuration'' for the set of points which are the centers of the balls in some ``arrangement''. Also, it is not hard to show that there are other ways to arrange spheres in ${\bf R}^3$ to obtain the same density as that of the ``optimal'' face-centered cubic lattice. This degeneracy is something we will need to discuss further in section 2d.) The simpler problem concerning disjoint unit diameter disks in ${\bf R}^2$ has a complicated history going back to Thue in 1910 [39], and has as an optimal configuration the ``hexagonal lattice'': $\{a_1(1,0) + a_2(\surd(1/2),\surd(3/2))\ :\ a_j\in {\bf Z}\};$ see Fig.~1b. Mathematical interest in sphere packing was originally due to a connection with minimization of quadratic forms. Specifically, there is a direct connection between the lattice $\{a_1v_1 + a_2v_2 + \cdots + a_nv_n : a_j\in {\bf Z}\}$ with basis $\{v_1,\cdots,v_n\}$, and the quadratic form $$f(a_1,\cdots,a_n) = \sum_{j,k=1}^na_ja_k\ v_j\!\cdot\!v_k $$ \noindent in the integer variables $a_1,\cdots,a_n$, where $v_j\!\cdot\!v_k$ refers to the inner product in ${\bf R}^n.$ Forms are called ``integrally equivalent'' if they correspond to the same lattice under a change of basis. The density $d(A)$ of the corresponding lattices $A$ is therefore an invariant for this equivalence, and the forms corresponding to the ``densest lattice packing'' have a natural place in this theory. (The difference between a ``densest packing'' and a ``densest lattice packing'' is that in the latter we only consider lattice configurations $A$ when minimizing the density $d(A)$.) Sphere packing, especially when restricted to lattice packings, has also played a role in coding theory and several other allies of number theory. For an encyclopedic survey of the uses of lattice packings see [8]. As a separate subject the sphere packing problem owes its depth to the highly ordered or regular structure of the known optimal configurations; it is appropriate to restrict consideration to lattice configurations in number theory, but not here. To clarify the meaning of ``optimal'' then, it is convenient to reformulate the sphere packing problem in the following terms. We have at our disposal many variables (the centers of the balls in ${\bf R}^n$), summarized in the one quantity we call a configuration. For arbitrarily large bounded regions $R$ in ${\bf R}^n$ we are trying to optimize certain functions $F_R$ over all possible configurations $A,$ where $F_R(A)$ is defined to be: $+\infty$ if there is a point of $A$ which is both in $R$ and also separated by a distance less than 1 from some other point of $A$, and otherwise $F_R(A)$ is defined to be the negative of the number of points of $A$ which are in $R$. ($F_R$ basically counts the contribution to the density of the spheres of $A$ in $R$, subject to a ``penalty'' if two spheres overlap.) In these terms then, the interesting fact is that in order {\bf to minimize the function $F_R$ for large $R$ we are lead to configurations $A$ which are highly ordered (lattices)}\footnote{*}{We repeat that the conjectured optimal configuration, the face centered cubic lattice, is not unique; there are other configurations, which are not lattices or even periodic, with the same density as the face centered cubic lattice [29,8]. This degeneracy is not central to our discussion however [29]. The role of degeneracy in our problem will be discussed below.}. \vskip .2truein\noindent {\bf 2b. AEA Formulas and Tiling} The relevant analysis of our logic problem was initiated by Hao Wang, and originally concerned the ``decidability'' of the class of all ``AEA formulas'' [43,44]. AEA formulas are sentences that begin ``For every $x$ there exists a $y$ such that for every $z \ldots$'', followed by a logical combination of predicates not containing the quantifiers ``for every'' or ``there exists''. (For example: For every subset $x$ there exists a least upper bound $y$ such that for every upper bound $z$ it follows that $z \ge y.$) And a class of formulas is said to be decidable if (informally) there is an algorithm by which, given any member of the class, we can determine in finitely many steps if the formula is consistent, i.e. not self contradictory. Wang found a way to analyze this decision problem for the class of AEA formulas through a game he invented called ``tiling''. In the game of tiling one uses (an unlimited number of) translates, called ``tiles'', of each of a finite set of ``prototiles''. A tile or prototile is a unit square in the plane, with each edge having some specified color, and with edges parallel to a fixed set of axes. For each color there is defined a ``complementary'' color. The object of the game is to cover the plane with tiles in checkerboard fashion (that is, abutting tiles touch full edge to full edge), with the condition -- called the color (or matching) rules -- that abutting edges must have complementary colors; see Figs.~2a,b. We will use the word ``configuration'' for a covering of the plane by tiles in checkerboard fashion, and reserve the term ``tiling'' for a configuration in which abutting tiles also satisfy the color rules; see Fig.~2c. (Given a set of prototiles there may or may not be any tilings of course -- see Fig.~2d, but there are always configurations. Also, note that in placing tiles in the plane one may translate but not rotate or reflect them from the prototile.) One of the remarkable features of this tiling game is its versatility, and much of this is due to its relation with Turing machines, to which we now give an informal introduction. A Turing machine is an imaginary computer consisting of a ``tape'', a ``head'' and a ``program''. The tape is one dimensional, oriented as to right and left, and consists of ``cells'' one of which is said to be ``under'' the head at any time. There are infinitely many cells to the left and right of this cell. Each cell is marked by one symbol from the finite set $\{s_0,s_1,\ldots,s_p\}$, and cells marked with symbol $s_0$ are called ``blank''. The program is a permanent, finite, labeled list $\{q_0,q_1,\ldots,q_r\}$ of ``instructions'' for the head, of which one is ``current'' at any given time. The instruction in operation at a given time is that of the ``current'' instruction of the program, and may depend in its effect on the mark of the cell under the head. Each single operation of the machine takes one second for completion and is of two types; either it replaces the contents of the cell under the head with a given mark, then moves the tape one cell to the left or right, and installs a specified instruction as the next ``current'' instruction, or else it causes the machine to Halt! (permanently). We can represent the nonhalting operations by quintuples of the form $(q_i,s_j,s_k,M,q_t)$, which means that if the current instruction is $q_i$ and the cell under the head is marked $s_j$ then the mark in that cell is made to be $s_k$, the tape is moved $M$ (a variable taking the values ``left'' or ``right'') and the next current instruction becomes $q_t$. Any pair $(q_i,s_j)$ not the beginning of such a quintuple is assumed to make the machine halt. At the initial time the instruction is assumed to be $q_0$ and all but finitely many of the cells of the tape are blank. The ``Halting problem'' asks whether or not there is a Turing machine -- i.e. an algorithm -- which can determine precisely which Turing machines will eventually halt if the tape is blank initially. It was proven by Turing that there can be no such algorithm; the Halting problem is ``undecidable'' [40,20,35]. Now given any Turing machine one can construct a set of prototiles which mirrors the action of the machine by a special one of its tilings. This is done as follows. (This construction is due to Wang, with important generalizations by Berger [5], Robinson [33] and others.) We represent the state of the machine (that is, the current instruction, the markings on the tape cells, and which cell is under the head) at two consecutive seconds by colors on the top and bottom edges of an infinite row of tiles, one tile for each cell, the top representing the later time. Each of these top and bottom edges has a color representing the marking of the corresponding cell of the machine, and precisely one top edge and one bottom edge has an altered color denoting that it corresponds to the cell under the head, and also denoting the current instruction. Horizontal edges are also colored. We will denote the colors of the edges by a set of some or all of the following: a head or tail of an arrow perpendicular to the edge (an arrow head by definiton has its point touching the edge, as in the top of Fig.~3a), a cell marking and an instruction. The complement of a color is the set with the same marking and instruction, but opposite end of the arrow. There are several classes of prototiles. Those in Fig.~3a are for cells whose markings $s_j$ do not change during the machine operation under consideration. Those in Figs.~3b,c represent a cell with marking $s_j$ which is being put under the head, from the left or right, and will be subject to instruction $q_i$. And those in Figs.~3d,e represent cells with marking $s_j$ which are being re-marked $s_k$ under instruction $q_i$, moved left or right, and with next current instruction $q_s$. We only have prototiles with markings which correspond to quintuples of nonhalting operations. To represent the initial state of the machine which for convenience we assume includes a blank tape, we need the three prototiles of Figs.~3f-h (we will call the middle of these the ``center prototile''), and the last prototile we require is that in Fig.~3i, which we will call the ``blank'' tile. It follows that in any (partial) tiling of the plane containing a center tile, the tiles making up the horizontal row containing that tile must be those of Figs.~3f,h. Each successive row above this one is then completely determined by the operation of the Turing machine being ``mirrored'', for as many rows as there are nonhalting operations of the machine. And the rows below the initial one must consist of blank tiles. Therefore given any Turing machine we have specified a set of prototiles which can tile the plane {\bf using the center prototile} if and only if the Turing machine never halts. However, the tiling game does not contain the condition that a given prototile (such as the center prototile) must be used, and without the condition we could tile the plane just using blank tiles. To eliminate this feature, R.~Berger [5] developed a method, refined by Robinson [33] and others, by which given a Turing machine one extends the above construction to a more complicated set of prototiles which can tile the plane if and only if the Turing machine never halts; there is no longer a condition that some specified prototile must be used. The technique consists of mirroring at many points within {\bf every possible} tiling of the plane arbitrarily large centered squares of the above construction, the only obstruction to tiling the plane being due to halting of the machine. (Thus it is possible, by adroit choice of the Turing machine being mirrored, to build sets of prototiles which can tile the plane but only with tilings having special features. This will be discussed further below.) We will expand on this connection between Turing machines and the tiling game in various contexts, but first we want to clarify the original connection. By the above construction and the known solution of the Halting problem, it was proven that the game of tiling is undecidable; that is, there can be no algorithm by which, given a set of prototiles, one can determine in a finite number of steps if the corresponding tiles can tile the plane. On the other hand, given any finite set of prototiles which can tile the plane, Wang showed how to construct an AEA formula which specifies the positions of the tiles in the plane. It follows that if the class of AEA formulas were decidable, the tiling game would be; since the tiling game is not decidable, neither is the class of all AEA formulas. This is a rough outline of the role that the tiling game played in the original decidability problem for AEA formulas. At this point we will cease discussing the predicate calculus aspect of this circle of ideas, and concentrate on the tiling game and Turing machines. Wang proved [43] that the tiling game is decidable if the following is true: that every set of prototiles which can tile the plane can also tile the plane in a ``periodic'' manner. (By ``periodic'' we mean that there is some ``unit cell'' consisting of a bounded collection of specified tiles in the plane, and the rest of the tiling consists of translations of this collection, in fact by a set of translations which constitute a lattice; see Fig.~2b.) We note that although it is easy to construct examples of sets of prototiles, as in Fig.~2a, which can tile the plane periodically, it is very hard to construct a set which can tile the plane but {\bf only nonperiodically}. In fact the next big step was taken by Berger, who used the above ideas to construct such a set of prototiles, which can tile the plane, but only nonperiodically, in his proof that the tiling game is undecidable [5]. Although we will refer again to the use of Turing machines in constructing sets of prototiles whose tilings all have interesting properties, at this point we want to emphasize the simplest case, the existence of sets of prototiles which can tile the plane but only nonperiodically. See Fig.~4. This is reminiscent of our discussion of the sphere packing problem. To make the connection more transparent we assume given a set of prototiles and construct, for each bounded region $R$ of the plane, a function $F_R$ on the set of configurations $A$ of the tiles. Define $F_R(A)$ to be the number of those pairs of abutting tiles in $A$ that do not satisfy the color rules, and are also such that at least one of the pair is contained in the region $R$ of the plane. In this notation we are interested in configurations $A$ in the plane which minimize $F_R$ for large $R,$ and in fact for which $F_R(A) = 0$ for all $R$. Berger's example is then a solution of the same type of optimization problem as the sphere packing problem, but somewhat less ordered since the optimal $A$'s are not lattices. Although the motivating question of decidability has been answered, tiling is in fact a growing area of research. Now interest is basically due to the attempt to understand the contrast between the ease with which examples of prototiles can be given (such as those of Fig.~2a) which can tile the plane periodically, and the great difficulty of producing examples (such as those of Fig.~4) which can tile the plane but only nonperiodically. As we will discuss in section 3d, methods are being developed to produce prototiles which tile the plane but only with tilings of greater and greater ``disorder''. (There is also interest in the geometrical aspects of tiling, ``five fold symmetry'' and all that, spurred in large part by the examples due to Penrose [25,15] of tilings with nonsquare ``tiles''; see Fig.~5. The connection between our problem of the ``orderliness'' of tilings and this geometrical subject -- the study of the {\bf symmetries} of tilings by nonsquare prototiles, is by no means clear, although the role of such symmetries in the study of quasicrystals has tended to mix the two [38].) Now we have used the words ``order'' and ``disorder'' so far in a colloquial sense, to refer for example to the intuitive feeling that the (periodic) configurations of the sphere packing solutions (Fig.~1b) are more orderly or regular than the (nonperiodic) tilings of some sets of prototiles (Fig.~4). However it will be one of our main goals to introduce and justify specific technical measures of order for problems of the sort we are discussing. Some of these measures will come from considerations in our next open problem, the crystal problem from condensed matter physics. %\hfil\eject %\hbox{} \vskip .2truein\noindent {\bf 2c. Crystals}\hfil \penalty -10000 In the crystal problem we seek the fundamental mechanisms underlying the tendency of real bulk matter towards crystalline order at low temperature and high pressure. By crystalline order we mean that the atomic nuclei in the material, which can be roughly localized as fixed points in ${\bf R}^3,$ form a point set which is either a lattice, or more generally, periodic (that is, there is a ``unit cell'' associated with each point of a lattice; see Fig.~6). The crystal problem is old, and considered a major unsolved problem [7,41,42,\break 37,29,2]. There is a mathematical formalism (equilibrium statistical mechanics) in which to set up the problem, and we begin with a review of this formalism. Assume we are modeling a material made of nuclei and electrons, and to be definite assume there are precisely $N-1$ different types of nuclei, $N$ some fixed integer ($N = 3$ for table salt, which contains the nuclei of sodium and chlorine). In statistical mechanics our model of the material contains several parameters, such as temperature, pressure, etc., appropriate to its macroscopic state -- there are alternative choices for these parameters, and for convenience we will use the temperature $T$ and the chemical potentials $M_1,\ldots,M_N$ of each of the constituent particle types -- electrons and $N-1$ types of nuclei. (The chemical potential of a particle type measures the energy it would take to increase by one the number of that type of particle in the material.) At this point we need to decide on the mechanics we will use to describe the local state of each particle. For our purposes (understanding the origin of the crystalline state) it is convenient to use classical mechanics instead of the slightly more accurate quantum mechanics. The state of the $j^{th}$ particle then consists of the triple $(x_j,s_j,p_j),$ where $x_j\in {\bf R}^3$ is its position, $s_j \in \{1,\ldots,N\}$ is its particle type and $p_j \in {\bf R}^3$ is its momentum. So associated with each particle there are several real variables. In {\bf statistical} mechanics these are {\bf random} variables, and their degree of dependence on one another is governed to a large extent (specified below) by the forces between the particles; that is, the formalism does not yield specific values for the variables, but the (joint) {\bf probability} that particles will have specific positions, particle types and momenta. (The temperature and chemical potentials are parameters on which these probabilities will depend.) The forces between the particles enter the formalism as potential energies (from which the forces could be recovered by differentiation).\footnote{*}{If we were using quantum mechanics we could use the static Coulomb potential energy of charged nuclei and electrons; some remarkable work has been performed in this way by Fefferman [10,11], Lieb [18,19] {\it et al}, but not for condensed matter, as we require. Since we chose to use classical mechanics we are now forced to use phenomenological forces to describe, not interacting nuclei and electrons but interacting ions and electrons, or even interacting atoms. What this means is that we still have $N$ types of ``particles'' in our model, but now we need to chose some appropriate potential energy function.} Before specifying the potential energy that is appropriate (so as to determine the probabilities mentioned above), we need to make one further simplification wherein the local state of a particle has discrete values, and in particular the position varies through the cubic lattice ${\bf Z}^3$ or more generally ${\bf Z}^n$ instead of ${\bf R}^3$. So instead of variables such as the position $x_j$ of the $j^{th}$ particle, we will use variables $A_j$ where $j \in {\bf Z}^n$ is a variable point or ``site'' of the lattice; $A_j$ then represents whether or not there is a particle at $j$, and its local state (particle type etc.) if there is one. We assume $A_j$ runs through some finite set $\{1,\ldots,m\}$, and associate a chemical potential $M_{\alpha}$ to each possible local state $\alpha \in \{1,\ldots,m\}.$ By a ``configuration'' we will mean an element of $\{1,\ldots,m\}^{{\bf Z}^n}$. We are now prepared to describe the type of potential energy that is appropriate for our model. We will use a ``short range, two-body, translation invariant interaction potential'', that is a real function $V(\cdot\,,\cdot)$ on $\bigl(\{1,\ldots,m\}\times {\bf Z}^n\bigr)^2$ such that $$\eqalign{&V(A_i,A_j)\exp(\vert i - j\vert) \to 0\hbox{ as }\vert i - j\vert \to\infty\cr &V(A_{i+k},A_{j+k}) = V(A_i,A_j),\hbox{ for all }i,j,k\in {\bf Z}^n.\cr} \eqno 1)$$ \noindent Then given any bounded region $R$ of ${\bf Z}^n$ (in the middle of some very large region $\hat R$), we know from statistical mechanics that the relative probability that the sites $j$ of $R$ are in states $A_{j}$ is: $$\sum_{j\in \hat R/R}\sum_{A_j=1}^m \exp \Bigl(-[E_{\hat R}(A) - M_1n^{\hat R}_1(A)-\cdots - M_mn^{\hat R}_m(A)]/T\Bigr)\eqno 2)$$ \noindent where $$E_{\hat R}(A) = \sum_{{i,j\in Z^n;\ i\ne j\atop i\ and/or\ j\ \in \hat R}} V(A_i,A_j)\eqno 3)$$ \noindent and $n^{\hat R}_{\alpha}(A)$ is the number of the sites of $\hat R$ in state $\alpha$\footnote{*}{This relative probability depends negligibly on sites outside $\hat R,$ in a sense discussed below.}. These probabilities simplify greatly in the limit where $T \downarrow 0$, but to describe this we need some further notation. The set $\{1,\ldots,m\}^{{\bf Z}^n}$ of all configurations $A$ has, as a product, a conventional topology and Borel measure structure. So by taking $\hat R$ to be a variable cube centered at the origin and expanding to ${\bf Z}^n,$ we can use 2) to define in the limit a probability measure $\mu^V_{T,M_1,\ldots,M_m}$ on $\{1,\ldots,m\}^{{\bf Z}^n}$ by its values on ``cylinder sets'' $$C(A_{j_1},\ldots,A_{j_p}) \equiv \Bigl\{A' \in\{1,\ldots,m\}^{{\bf Z}^n} : {A'}_{j_k}=A_{j_k}, k=1,\ldots,p\Bigr\}. $$ \noindent That is\footnote{**} {In general the following limiting procedure depends on a choice of $A_j$ for $j$ outside $\hat R$, through $E_{\hat R}(A)$. However since we are trying to model a pure solid phase we are only interested in those values of $T,M_1,\ldots,M_m$ for which there is one and only one translation invariant measure that can be obtained by such a limit -- which is therefore independent of such choices of $A_j$ for $j$ outside $\hat R$ -- and we denote this measure by $\mu^V_{T,M_1,\ldots,M_m}.$}, $$\mu^V_{T,M_1,\ldots,M_m}[C(A_{j_1},\ldots,A_{j_p})] = \lim_{\hat R\to {\bf Z}^n}{N(\hat R)\over Z(\hat R)} \eqno 4)$$ \noindent where $$ N(\hat R) = \sum_{{j\in \hat R\atop j\ne j_1,\ldots,j\ne j_p}}\sum_{A_j=1}^m \exp -\Bigl([E_{\hat R}(A) - M_1n^{\hat R}_1(A)-\cdots - M_mn^{\hat R}_m(A)]/T\Bigr)$$ \noindent and $$ Z(\hat R) = \sum_{j\in \hat R}\sum_{A_j=1}^m \exp -\Bigl([E_{\hat R}(A) - M_1n^{\hat R}_1(A)-\cdots - M_mn^{\hat R}_m(A)]/T\Bigr).$$ \noindent (By ``translation invariant'' we mean that $\mu^V_{T,M_1,\ldots,M_m}[C(A_{j_1},\ldots,A_{j_n})]$ is unchanged as the sites ${j_1},\ldots,{j_n}$ of $C(A_{j_1},\ldots,A_{j_n})$ are subjected to any fixed translation of ${\bf Z}^n$.) It is instructive to note that for the ``free model'' (otherwise known as a ``Bernoulli shift'' in probability theory), in which the interaction potential $V$ is identically 0, the measure $\mu^V_{T,M_1,\ldots,M_m}$ is simply the product $\otimes_{j\in Z^n}\mu_j$ of copies of the local measure $\mu$ on $\{1,\dots,m\}$ given by $$\mu(\beta) = {\exp(M_{\beta}/T)\over \sum_{\alpha =1}^m\exp(M_{\alpha}/T)}.$$ \noindent Thus the interaction is the source of the dependence among the random variables $A_j$. We now define the probability measure $\mu^V_{0,M_1,\ldots,M_m},$ called the ``ground state for $V$'', by the further limit $\mu^V_{T,M_1,\ldots,M_m} \to \mu^V_{0,M_1,\ldots,M_m}$ as $T \downarrow 0,$ again by using the values of the measures on cylinder sets\footnote{*}{Here again one can question the existence of the limit, but again on physical grounds this limit should exist if the states $\mu^V_{T,M_1,\ldots,M_m}$ stay within a pure phase as $T\downarrow 0.$ This is proven to hold for generic interactions in [28].}. As a limit of $\mu^V_{T,M_1,\ldots,M_m}$ we know that $\mu^V_{0,M_1,\ldots,M_m}$ is also translation invariant. (We are really only interested in $\mu^V_{T,M_1,\ldots,M_m}$ for $T=0$, but we introduced the distribution for $T>0$ to emphasize the fact that the ground state $\mu^V_{0,M_1,\ldots,M_m}$ is a probability distribution on configurations, not just a configuration, a fact that is crucial for our problem.) Eventually we will determine $\mu^V_{0,M_1,\ldots,M_m}$ for some interaction potentials $V,$ but first we want to record one very useful fact about $\mu^V_{0,M_1,\ldots,M_m}$: the set of ``ground state configurations for $V$'' has measure 1 with respect to this measure, where a configuration $A$ is a ground state configuration for $V$ if, for every bounded region $R$ in ${\bf Z}^n,$ $$F_R(A) = \inf\Bigl\{F_R(A') : A' \in \{1,\ldots,m\}^{{\bf Z}^n},\hbox{ and } {A'}_j = A_j\hbox{ for all }j\in R\Bigr\}\eqno 5)$$ \noindent where the function $F_R$ is defined by: $$F_R(A) = E_R(A) - M_1n_1^R(A) -\cdots - M_mn_m^R(A).\eqno 6)$$ It has required a lot of definitions, but finally we are at a useful point to contemplate what we have. The ground state $\mu^V_{0,M_1,\ldots,M_m}$ for the interaction $V$ (and fixed chemical potential parameters $M_{\alpha}$) is a translation invariant probability measure concentrated on the set of ground state configurations, and the ground state configurations are the solutions $A$ of the set of optimization conditions~5) for all bounded regions $R$ of ${\bf Z}^n$. The basic objective of the crystal problem consists in understanding why solutions $A$ to this optimization problem tend to be periodic, or highly ordered -- that is, crystals. \vskip .2truein\noindent {\bf 2d. Comparisons} We complete this section with a demonstration that the optimization formulations we gave for tilings and for sphere packing are closely related to the one for the crystal problem,~5). Returning then to the game of tiling, we consider all possible finite sets of prototiles which can tile the plane. We are interested in certain features of the tilings of the plane which are possible for specific sets; for example, whether or not only nonperiodic tilings are possible. Consider some set of $m$ prototiles which can tile the plane, as in Fig.~2a. Construct a coordinate system in the plane containing the tilings, with the integer points ${\bf Z}^2$ at the centers of the tiles. Now define a discrete statistical mechanical model on ${\bf Z}^2,$ with $m$ states per site (and for configuration $A,$ $A_j = \alpha$ means that the state at site $j$ ``is'' a translate of the $\alpha^{th}$ prototile -- see Fig.~7), with interaction potential $V$ defined by: $$\eqalignno{V(A_i,A_j) &= 0,\hbox{ if }\vert i - j\vert \ne 1\cr &= -1,\hbox{ if }\vert i - j\vert = 1\hbox{ and tiles }A_i,A_j\hbox{ at }i,j\hbox{ satisfy the color rules}&7)\cr &= 0,\hbox{ if }\vert i - j\vert = 1\hbox{ and tiles }A_i,A_j\hbox{ at }i,j \hbox{ don't satisfy the color rules.}\cr}$$ \noindent (With the specific prototiles of Fig.~2a this statistical mechanical model is called the Ising antiferromagnet [36,14].) Now consider the set of ground state configurations for this statistical mechanical model, assuming for simplicity that all chemical potentials have value 0. It is easy to see that any configuration corresponding to a tiling of the plane will be a ground state configuration. The converse however is not quite true. For example, with respect to the model using the prototiles of Fig.~2a consider the configuration of tiles with a ``fault line'' as in Fig.~2c. It is easy to check that this is not a tiling but is a ground state configuration. There is however a sense in which this configuration is negligible, and that brings us back not just to ground state configurations, but to the ground state $\mu^V_{0,0,\ldots,0}$ itself. At this point we need some further background material. First we note that for any collection of prototiles the corresponding set of tilings of the plane is a translation invariant, closed -- and therefore compact -- subset of the space of all configurations. Similarly, for any discrete statistical mechanical model the set of all ground state configurations is a translation invariant, closed -- and therefore compact -- subset of the space of all configurations. We define the ``support'' of a measure on a compact space to be the complement of the union of all open sets of measure zero, and, finally, we say a system consisting of a compact set, a group of homeomorphisms of the set, and a probability measure on the set invariant under the homeomorphisms, is ``uniquely ergodic'' if there is only one probability measure on the set invariant under the homeomorphisms. This implies the better known property of ergodicity of the system, which only requires that there be no other invariant probability measure {\bf absolutely continuous} with respect to the given one. (A circle carrying Lebesgue measure is uniquely ergodic under iterates of an irrational rotation. Bernoulli shifts -- noted above in the example of free models, and discussed further below -- are ergodic but not uniquely ergodic; we can see the latter from the existence of those invariant probability measures which give full measure to a single constant configuration.) The best known result concerning unique ergodicity is its relation with pointwise ergodic theorems, as we discuss in connection with 11) below. Now without loss of generality we can assume for the interactions we consider that the set of ground state configurations is uniquely ergodic under translations. (This is usually easy to check for any given interaction of interest, and it has been proven that this is true for ``generic'' interactions in some reasonable spaces of interactions. The proof [28], which is a variant of the classical theorem that a convex function is differentiable almost everywhere, shows that the condition of unique ergodicity is just a condition of nondegeneracy, a requirement that the optimization problem have a unique solution among invariant probability measures. This condition fails for sphere packing in three dimensions if the conjectured solution is correct, and this degeneracy means that the sphere packing problem is to that extent atypical, and consequently of less value as a guide to our intuition about such optimization problems. Because of the proof that unique ergodicity is generic, and other physical reasons, it is appropriate to require of any model of the ground state of a pure solid phase -- as opposed to a state of coexistence of a fluid and solid phase say -- that the condition hold that the set of ground state configurations must be uniquely ergodic; see [31,29,28].) For the interaction corresponding to Fig.~2a this is easy to check. In fact, if we denote by $A$ and $A'$ the (only) two tiling configurations allowed by the tiles of Fig.~2a, the one in Fig.~2b and its translate by one unit, then the ground state of the associated interaction must be $\mu^V_{0,0,\ldots,0} = ({\delta}_{A} + {\delta}_{A'})/2,$ the average of the point masses concentrated on the points $A$ and $A'$. There are other ground state configurations for that interaction, such as that of Fig.~2c, but it is easy to show that the set of ground state configurations is uniquely ergodic, with this measure. So for this interaction (and others built from sets of prototiles) there is a one-to-one correspondence between the associated tilings of the plane and the ``relevant'' ground state configurations, the configurations in the support of the ground state $\mu^V_{0,0,\ldots,0}$ [21]. We now see that the tiling problem can be considered a special case of the crystal problem in which: a) all chemical potentials are taken to be zero, and b) the interaction has the special form of equations~7). To see sphere packing as a special case of the crystal problem requires more terminology since it relates to a continuum statistical mechanical model, not a discrete one as we have used. Physically, all that is needed is a force that prevents two particles from getting too close -- what is called a ``hard core repulsion'' in the physics literature -- together with either a chemical potential favoring a positive density or else a pressure, which would have the same effect. An added complication is that in fact unique ergodicity does not hold for sphere packing. For these reasons we take the cowards' way out and refer the reader to [29] for the messy details; nothing new is involved other than the technical definitions needed to deal with continuously distributed variables. We will only discuss the discrete version of our general optimization problem from here on. To summarize what we have discussed so far, we have considered three different problems: sphere packing, tiling, and the crystal problem, and have seen that at heart they are all of the form of the optimization problem 5), where the functions $F_R$ to be optimized are of the form given by 6) and 3). This type of optimization problem is interesting because there seems to be a strong tendency for solutions $A$ to either be periodic (even a lattice), or at least highly ordered, though the reason for this is unknown. %\hfil\eject %\hbox{} \vskip .2truein\noindent \line{\bf 3. ORDER AND THE ERGODIC THEORY OF SYMBOLIC\hfil} \line{\hphantom{\bf 3. }\bf DYNAMICS} \vskip .1truein\noindent {\bf 3a. The general problem and solution in dimension 1} It is now time to analyze the concept of ``order''. To do that we will make use of the mathematical structure developed in section 2, the ergodic theory of symbolic dynamics. In the ergodic theory of symbolic dynamics we have: some closed subset $X$ of a product space $\{1,\ldots,m\}^{{\bf Z}^n},$ invariant under the group ${\bf Z}^n$ of translations (sometimes called ``shifts''), and a Borel probability measure $\mu$ on $X$ which is invariant under the translations. For convenience we review here the meaning of the symbol $X^V_{M_1,\ldots,M_m}.$ Consider the set of all $A\in \{1,\ldots,m\}^{{\bf Z}^n}$ such that for every bounded region $R$ in ${\bf Z}^n,$ $$F_R(A) = \inf\Bigl\{F_R(A') : A' \in \{1,\ldots,m\}^{{\bf Z}^n},\hbox{ and } {A'}_j = A_j\hbox{ for all }j\in R\Bigr\}\eqno 5)$$ \noindent where $$F_R(A) = E_R(A) - M_1n_1^R(A) -\cdots - M_mn_m^R(A),\eqno 6)$$ $$E_{R}(A) = \sum_{{i,j\in Z^n;\ i\ne j\atop i\ and/or\ j\in R}} V(A_i,A_j),\eqno 3)$$ \noindent the ``chemical potentials'' $M_{\alpha}\in {\bf R}$, $n^R_{\alpha}(A)$ is the number of the sites of $R$ in state $\alpha$, and the ``interaction potential'' $$V : (A_i,A_j)\in \Big(\{1,\ldots,m\}\times {\bf Z}^n\Big)^2\to V(A_i,A_j)\in {\bf R}$$ \noindent satisfies $$\eqalign{&V(A_i,A_j)\exp(\vert i - j\vert) \to 0\hbox{ as }\vert i - j\vert \to\infty\cr &V(A_{i+k},A_{j+k}) = V(A_i,A_j),\hbox{ for all }k\in {\bf Z}^n.\cr} \eqno 1)$$ \noindent We assume that on the set of such $A$ there is only one invariant probability measure (the ``ground state'') denoted $\mu^V_{0,M_1,\ldots,M_m}$, and define $X^V_{M_1,\ldots,M_m}$ as the support of $\mu^V_{0,M_1,\ldots,M_m}$. So taking for $X$ the set $X^V_{M_1,\ldots,M_m}$ of solutions $A$ of our optimization problem~5), and for $\mu$ the ground state $\mu^V_{0,M_1,\ldots,M_m},$ we find that the structure of our problem refinements we have made are: a) the assumption that $X$ be uniquely ergodic under translations, that is, that $\mu$ should be the {\bf only} invariant probability measure on $X,$ and b) that the support of $\mu$ should be $X$. In dynamical systems there is a more convenient way to express condition b). A closed subset $Y$ of $\{1,\ldots,m\}^{{\bf Z}^n},$ invariant under translations, is called ``minimal'' if it contains no nontrivial closed invariant subset. It is easy to see that if a) holds then condition b) is just the restriction that $X$ be minimal. Finally, the two conditions that $X$ be uniquely ergodic and minimal are summarized in the one condition, that $X$ be ``strictly ergodic''. So in this new language our problem becomes: \vskip .1truein\noindent {\bit The General Optimization Problem.~Consider those strictly ergodic symbolic dynamical systems $X^V_{M_1,\ldots,M_m} \subset \{1,\ldots,m\}^{{\bf Z}^n}$ which arise as the solution sets of the above optimization problems. The goal is to ``measure'' the order in such systems, and determine the degree of order which is generic and the causes of the various degrees of order.} \vskip .1truein Now in most studies of strictly ergodic symbolic dynamical systems the dimension $n$ is 1, which is unfortunate because that is the one dimension that is fairly trivial for us, at least if the interaction potential $V$ is ``of finite range'', that is: $$V(A_i,A_j) = 0\ \ \hbox{ if }\vert i - j\vert > D \eqno 8)$$ \noindent for some $D \ge 1.$ In that case we have: \vskip .1truein \noindent {\bf Theorem 1} (C.R. and L.~Schulman [27]). In dimension 1, if the interaction $V$ is of finite range and $X^V_{M_1,\ldots,M_m}$ is strictly ergodic then $X^V_{M_1,\ldots,M_m}$ must be a finite set, namely the translates of some periodic configuration. \vskip .1truein \noindent This is a positive solution of our problem for dimension 1: every 1 dimensional problem has a periodic ground state. (We will see that the problem is much more interesting in higher dimensions.) In particular, consider those ``tiling dynamical systems'' which define strictly ergodic $X^V_{0,\ldots,0}$ using $V$ of the form 7). Since these $V$ are of range 1, they (and the game of tiling itself) are relatively trivial in dimension 1. But as we will see this does not make irrelevant the known results of uniquely ergodic symbolic dynamics for dimension 1. To get back to the question of ``order'', we are now ready to introduce three central ideas: entropy, recursive functions and spectrum. We will see that these measure different aspects of the ``orderliness'' of a dynamical system. In practice such a multifaceted approach seems to be the safest way to try to make precise the intuitive notion of order, though of course this still leaves open the use of other possible measures of order besides these three. We begin with entropy. \vskip .2truein\noindent {\bf 3b. Entropy} Using the above framework of a symbolic dynamical system $X\subseteq \{1,\ldots,m\}^{{\bf Z}^n}$ with invariant measure $\mu$, the (topological) entropy $h(X)$ is given by: $$h(X) = \lim_{N\to \infty}{1\over (2N+1)^n}\sum_{C\in C(N)}\eta[\mu(C)],\eqno 9)$$ \noindent where $$\eqalign{\eta[t] &= -t\log(t),\hbox{ if t$>$0}\cr &= 0,\hbox{ if t~=~0}\cr}$$ \noindent and ${\bf C}(N)$ is the collection of all cylinder sets based in the cube $\{(j_1,\ldots,j_n)\in{\bf Z}^n : \vert j_k\vert \leq N\}$. (Since $X$ is strictly ergodic, it is known that this topological entropy coincides with ``measure theoretic entropy'' [23]. It is also relevant that it coincides with the entropy for ground states that is used in physics [1].) It is instructive to compute $h(X)$ for the following two examples. If $X$ is the finite set of translations of some periodic configuration of period $p$ -- see Fig.~2b, then $\mu(C)$ is only nonzero for about $p^n$ cylinder sets $C \in {\bf C}(N)$, and since this bound is uniform in $N$, $h(X) = 0$. The other example, called a ``Bernoulli shift on ${\bf Z}^n$'', is defined by taking $\mu = \otimes_{j\in Z^n} \mu_j$ on $X = \{1,\ldots,m\}^{{\bf Z}^n}$ with $\mu_j = (1/m)\sum_{\alpha=1}^m\delta_{\alpha}.$ It is easy to check that $h(X) = \log(m).$ (Note the connection between Bernoulli shifts and the free models of section 2c.) Now entropy has been widely used as a measure of disorder, for example in information theory [6] and physics [36]. In physics, the Third Law of Thermodynamics says that the ground state of any macroscopic material has zero entropy, and this is usually ``understood'' theoretically to be an expression of the small number of configurations contributing to the distribution 2) at low temperature: basically, translations and small perturbations of some periodic configuration. Of course this {\bf assumes} that the ground state is a perfect crystal, corresponding to a periodic configuration. The closest there is to a proof of this law is the recent: \vskip .1truein\noindent {\bf Theorem 2} (J.~Mi\c ekisz and C.R. [31]) If the interaction potential $V$ is of finite range (and $X^V_{M_1,\ldots,M_m}$ is strictly ergodic), then the entropy $h(X^V_{M_1,\ldots,M_m}) = 0$. \vskip .1truein \noindent (There is a stronger version of this result that holds for interactions of longer range [30].) This proves that, at least for finite range interactions, our optimal configurations must be orderly as measured by entropy. The next idea we will use to measure the regularity or complexity of solutions of our optimization problem is that of ``recursive function''. \vskip .2truein\noindent {\bf 3c. Recursive functions} A function in ${\bf Z}^{{\bf Z}^n}$ is said to be recursive if there is a Turing machine program which can, with variable tapes corresponding to the points in the domain of the function, produce output (when the machine halts) interpretable as the corresponding values of the function [35]. We can use this notion to catagorize the tilings of the plane for a given set of prototiles (the tilings being functions in $\{1,\ldots,m\}^{{\bf Z}^2}\subset {\bf Z}^{{\bf Z}^2}$), or the ground state configurations of a given statistical mechanical model. It is clear that a periodic configuration is recursive, as it is easy to give an algorithm to specify uniquely, step by step, each local state in such a configuration. What is not so obvious is that there exists a set of prototiles (as was proven by Myers [22] using the technique noted in section 2b), which can tile the plane, but such that {\bf all} such tilings of the plane are {\bf nonrecursive}; {\bf none} of the tilings can be uniquely specified by an algorithm. (We note that this is an existence result -- no such set of prototiles has been exhibited by Myers or anyone else.) In this sense these tilings are ``complex''. It is debatable whether or not we should call such tilings irregular or disordered, but this is perhaps more a question of semantics than of substance. It seems reasonable to say that such a set of prototiles, or corresponding interaction potential, is relevant in our search for the structure of solutions to our optimization problem. (It is possible to measure the degree by which a function, in particular a tiling, fails to be recursive. See [22].) The next measure of order that we will use is the spectrum. \vskip .2truein\noindent {\bf 3d. Spectrum} Given a symbolic dynamical system $X \subseteq \{1,\ldots,m\}^{{\bf Z}^n}$, with invariant probability measure $\mu$, the spectrum we are interested in is associated with the unitary operators $T(j)$ representing translations by $j \in {\bf Z}^n$ on the complex Hilbert space $L^2(X,\mu).$ (So $[T(j)f](x) = f(y)$ where $y = x - j$.) We refer to the projection valued measure $dE(\lambda)$ on $[0, 1)^n$ such that for any vector $f \in L^2(X,\mu),$ $$ \ = \int_{[0, 1)^n}\exp(i\ j\!\cdot\!\lambda)d\!, \ \ \ j \in {\bf Z}^n, \eqno 10)$$ \noindent where $<\,,>$ refers to the inner product in $L^2(X,\mu).$ The vector $f$ belongs to the pure point, singular continuous or absolutely continuous subspace of $L^2(X,\mu)$ if the real valued measure $$ is pure point, singular continuous or absolutely continuous on $[0, 1)^n.$ Finally, since the subspace of $L^2(X,\mu)$ consisting of the constant functions is invariant under translations, we can and will restrict attention to $f$ in its orthogonal complement in $L^2(X,\mu).$ See [32]. There is an intuitive feeling that the more smooth these measures $$ are, the more disordered the configurations in $X$ are. For example, in the ``most ordered'' case where $X$ is the finite set of translations of some periodic configuration, the measure $$ consists of a finite number of point masses for any $f$. At the other extreme, for the Bernoulli shift on ${\bf Z}^n$ discussed above, the typical element of $X$ with respect to $\mu$ is intuitively as disordered as possible, and any measure $$ is absolutely continuous. Our objective is to analyze the degree of order which occurs in strictly ergodic symbolic dynamical systems of the form $X^V_{M_1,\ldots,M_m}.$ We know from Theorem 2 that, for interaction potentials $V$ of finite range, disorder is small in the sense that the entropy is zero. (And this has been generalized somewhat to longer range interactions [30].) On the other hand we know from the tiling examples of Myers [22] noted above that there exist finite range interactions for which $X^V_{M_1,\ldots,M_m}$ is disordered in the sense of being nonrecursive. We now want to consider the possible degree of disorder using the notion of spectrum, but we make a short digression first. Fixing the number $m$ of states per site, and a bound $D$ on the range of the interaction (as defined by 8)), the space of interactions is finite dimensional. It is therefore natural to ask whether some specific sort of order is ``generic'' (either of full Lebesgue measure, or contains the countable union of dense open sets). Note that this approach would not be available if we restricted attention to tilings, or statistical mechanical models which come from tilings through 7), since the corresponding space of interactions would then contain only finitely many points, and there could be no useful notion of genericity. This is one reason why the generalization from tilings to statistical mecahnics can be useful: it effectively changes the mathematics from algebra to analysis. Unfortunately we do not know whether generic models are recursive. Before we continue with this analysis we need to emphasize another aspect of the strictly ergodic systems we are studying. As we alluded above, an $n$-dimensional ergodic symbolic dynamical system $X$ with invariant measure $\mu$ is uniquely ergodic if and only if $$1/(2N+1)^n \sum_{\vert j\vert\leq N}[T(j)f](x) \to\int_X f\ d\mu(x),\eqno 11)$$ \noindent as $N \to \infty,$ {\bf uniformly in $x \in X,$} for every continuous function $f$ on $X$ [24]. Intuitively, this means that all the points $x \in X$ are in some sense equivalent, and studying the disorder of $X$ is the same as studying the disorder of any one configuration $x$ of $X.$ Note the essential difference between this situation and that of the Bernoulli shift mentioned above. For the latter at best we could only hope to get one type of ``order'' for {\bf generic} configurations of $X$ (in either the measure theoretic or topological sense) but certainly not for {\bf all} configurations. Also, the {\bf uniform} convergence in 11) contrasts sharply with the {\bf pointwise} almost-everywhere convergence of Birkhoff's ergodic theorem, which applies to ergodic dynamical systems (such as the Bernoulli shift) which are not strictly ergodic. For these reasons, as well as others, the restriction we have made to strictly ergodic dynamical systems means that we are trying to determine the degree of order of a fairly well defined ``pattern'', (in one interpretation the ground state configuration of a model of a solid), as opposed to the degree of order of a measure (which, again in this interpretation, could be that of a model of a fluid -- to which one does not usually attribute any one ``pattern''). We will now describe the types of spectrum which are known to occur for our dynamical systems $X^V_{M_1,\ldots,M_m}.$ Of course it is easy to obtain isolated pure point spectrum, corresponding to the highest possible order, in any perfectly periodic $X^V_{M_1,\ldots,M_m}$ as in Fig.~2b. The spectrum corresponding to the nonperiodic tiling models such as in Fig.~4 has not been worked out in detail, though it is again expected to be pure point, but now dense in $[0,2\pi)^2$ (for appropriate $f$), as seems to be the case of real quasicrystals [38]. Recently an important new method for constructing prototiles with spectral disorder has been developed by Mozes [21], and we will discuss this after some preliminary background. First we outline the notion of (1 dimensional) ``substitution dynamical systems''. Such a system $X\subseteq \{1,\ldots,m\}^{\bf Z}$ is defined as the set of all points $x = \bigl\{x_j : x_j\in \{1,\ldots,m\},\ j \in {\bf Z}\bigr\}$ for which all ``blocks'' $\{x_j : J\le j\le K\}$ in $x$ satisfy certain restrictions. These restrictions are defined through ``substitution rules'' by which, for each element $\alpha \in \{1,\ldots,m\},$ we associate a finite sequence $\{\alpha_1, \cdots , \alpha_k\}$ where $\alpha_j \in \{1,\ldots,m\}$ and $k$ (the so-called ``length'' of the rule) may depend on $\alpha$. As an example with $m =2$, the ``Morse'', or ``Thue-Morse'' substitution rules: $$0\ \to \ 01,\ \ 1 \to 10\eqno 12)$$ \noindent are both of length 2. Now given any finite sequence $B$ of elements of $\{1,\ldots,m\}$, we define $D(B)$ as the finite sequence obtained by replacing each of the elements of $B$ using its rule. (So $01$ becomes $0110$ using 12).) Next define $ W_0 = \{1,\ldots,m\},\ W_{n+1} = \bigcup_{B\in W_n}D(B)$ and $\ W = \bigcup_{n\ge0}W_n$. Then $X$ is the set of all sequences $x$ for which every subblock of $x$ is a subblock of an element of $W$. (Once we have defined $X$ we have a dynamical system, with discrete ``time'' represented by translation in $\{1,\ldots,m\}^{\bf Z}$. And since under very mild conditions substitution dynamical systems are uniquely ergodic [26], they automatically come equipped with a canonical measure.) Finally, given a set of substitution rules defining the set $X$, we say the dynamical system has ``unique derivation'' if for every $x\in X$ there is a unique $y\in X$ (unique only up to translation) such that $x$ is obtained from $y$ when the substitution rules are used to replace the elements of $y$. For example, the dynamical system $X \subset \{0,1\}^{\bf Z}$ defined [9] by $$0\ \to \ 001,\ \ 1\ \to \ 11100\eqno 13)$$ \noindent has unique derivation, as does the better known Thue-Morse system, defined by 12). An example of a dynamical system without unique derivation is $X \subset \{0,1\}^{\bf Z}$ with the rules $0\to 010,\ 1\to 101$. See [21,26]. One other definition we need is that of the 2 dimensional symbolic dynamical system ``associated with'' a pair $X_1, X_2$ of 1 dimensional symbolic dynamical systems, with translations $T_1 : X_1 \to X_1$ and $T_2 : X_2 \to X_2$. The associated 2 dimensional dynamical system consists of the cartesian product $X_1\times X_2$ with translations $$\eqalign{T_1\times I &: (x_1,x_2) \in X_1\times X_2 \to (T_1x_1,x_2)\in X_1\times X_2 \cr I\times T_2 &: (x_1,x_2) \in X_1\times X_2 \to (x_1,T_2x_2)\in X_1\times X_2.} \eqno 14)$$ \noindent (For completeness we note that substitution dynamical systems can be generalized to higher dimensions [21].) It is perhaps noteworthy that Thue introduced the system 12) in one of a series of works devoted to combinatorial modeling of the ``antithesis'' of periodicity. Specifically, the sequences defined by 12) are precisely those sequences of 0's and 1's which have the following ``BBb property'': for no block $B = \{b_1, b_2, \ldots, b_m\}$ of 0's and 1's does the block $$BBb \equiv \{b_1, b_2, \ldots, b_m, b_1, b_2, \ldots, b_m, b_1\}$$ \noindent appear in the sequence. (See [16] for a discussion of Thue's work in this direction, and [12] for a version of the BBb characterization tailored to our problem.) Now that we have the notion of a substitution dynamical system, we can discuss the following recent result of Mozes, which relates substitutional dynamical systems with the 2 dimensional ``tiling'' dynamical systems considered above (where $X$ is the subset of $\{1,\ldots,m\}^{{\bf Z}^2}$ consisting of all the tilings associated with some set of $m$ tiles). \vskip .1truein \noindent {\bf Theorem 3} (S.~Mozes [21]). Given any pair of 1 dimensional substitutional dynamical systems with unique derivation and with substitution rules of length at least 2, one can exhibit a (2 dimensional) tiling dynamical system which is measure theoretically isomorphic to the 2 dimensional dynamical system associated with the pair of 1 dimensional substitution dynamical systems. \vskip .1truein Although we will not reproduce Mozes' proof, it is worth noting that it depends heavily on the techniques, discussed above, invented for constructing a set of prototiles which mirrors the action of a Turing machine in all its tilings. And just as Myers, who used these methods to prove the existence of tiling dynamical systems which are disordered in the sense that all the tilings are nonrecursive, Mozes uses the methods to exhibit tiling dynamical systems which are disordered in the sense of their spectrum. (This result is constructive; the prototiles can easily be exhibited.) An interesting aplication in this direction [31] uses the 1 dimensional system defined by 13), and generates a tiling dynamical system for which the measures $$ on $[0,2\pi)^2$ are singular continuous. Unfortunately this method cannot yield measures $$ which are absolutely continuous, because this already fails for the 1 dimensional substitutional dynamical systems used as components [9]. So it is an open question how smooth the measures can be for tiling dynamical systems, or more generally for $X^V_{M_1,\ldots,M_m}$ defined by $V$ of finite range. \vskip .2truein\noindent {\bf 3e. Comparison of various measures of order} We have now considered three ways to measure the order (or complexity) of our strictly ergodic $X^V_{M_1,\ldots,M_m}$, using entropy, recursive functions, and spectrum. By any of these measures the ``crystalline'' case, where $X^V_{M_1,\ldots,M_m}$ is the finite set of translates of some periodic configuration, has the highest possible order. For finite range $V$ we found that the entropy was always zero, but that we could get some disorder in the sense of recursive functions and spectrum. However in neither of these cases could we determine the generic situation. If we do not require that $V$ be of finite range, and also drop the requirement that $V$ be a {\bf two-body} interaction potential, we can (using a technique due to Aubry [3,4]) easily construct $V$ with very disordered $X^V_{M_1,\ldots,M_m}$ [31]. In particular we can then obtain $X^V_{M_1,\ldots,M_m}$ with positive entropy, and absolutely continuous spectrum. Such results seem to belong to a different class from the ones we have been discussing. Finally, we should mention the notion of ``order parameter'' which has been used extensively in physics to help understand the order properties of models {\bf at positive temperatures} [2]. Unfortunately this has not yet proven to be of much use for ground states; see however [30]. \vskip .2truein\noindent {\bf 4. SUMMARY} We have considered a general class of optimization problems which contains as special cases classic open problems in number theory and condensed matter physics. Informally, in such a problem there are many variable points in space, with points near each other contributing, in pairs, to some global quantity that we want to minimize. The motivating feature is that there seems to be a strong tendency for the solution of such an optimization problem to consist of an array of points very regularly positioned in space, while the reason behind this tendency is unknown. Therefore we seek the degree of order of the solution of a generic problem of the class. In unifying the problem in terms of the ergodic theory of symbolic dynamical systems we were lead to concentrate not on a single (optimal) array of points in space, but on its orbit closure under translations, and in place of periodic arrays we found that uniquely ergodic orbit closures are the natural setting. We considered a variety of ways of analyzing the degree of order of solutions, including entropy, recursive functions and spectrum. The calculation of entropy is complete, and turns out to be too coarse a measure of order for this problem. There are unexpected examples of disorder in terms of recursive functions and spectrum. It is hoped that this exposition will both alert experts in specific aspects of the problem to advances on other fronts, and enlist fresh troups to the fray. In particular, consider how we used nonperiodic tilings to construct very unexpected and enlightening examples in statistical mechanics. Benefit also flows the other way. The above presentation develops a shift in emphasis from the individual configurations of a problem, say a tiling problem, to the unique probability measure on the set of configurations; and this in turn lead to a shift from the original question of ``periodic versus nonperiodic'' to consideration of various aspects of order. (Questions of periodicity were then restated in terms of the discrete part of the spectrum of the measure.) Roughly, this constitutes the introduction of Analysis into the traditional Algebraic field of tiling. One example of the benefits of this reorientation is the set of examples due to Mozes described in section 3d. Finally, we note that Theorem 2 above, which implies that strictly ergodic tilings have zero entropy, is a natural application of statistical mechanical ideas to tiling. \hfil\eject \hbox{}\vskip 0truein\noindent {\bf 5. REFERENCES} \vskip.2truein\noindent [1] M.\ Aizenman and E.H.\ Lieb, The third law of thermodynamics and the degeneracy of the ground state for lattice systems, {\it J.\ Stat.\ Phys.}\ 24 (1981), 279-297. \vskip.1truein\noindent [2] P.W.\ Anderson, {\it Basic Notions of Condensed Matter Physics}, Benjamin/Cummings, Menlo Park, 1984. \vskip.1truein\noindent [3] S.\ Aubry, Weakly periodic structures and example, {\it J.\ Phys.\ (Paris), Coll.\ C3, supp.\ no.\ 3}\ \ 50 (1989), 97-106. \vskip.1truein\noindent [4] S.\ Aubry, ``Weakly periodic structures with a singular continuous spectrum'', preprint, Laboratoire L\'eon Brillouin, Gif-sur-Yvette, 1989. \vskip.1truein\noindent [5] R.\ Berger, The undecidability of the domino problem, {\it Mem.\ Amer.\ Math.\ Soc., no.\ 66}, (1966). \vskip.1truein\noindent [6] P.\ Billingsley, {\it Ergodic Theory and Information}, John Wiley, New York, 1965. \vskip.1truein\noindent [7] S.G.\ Brush, {\it Statistical Physics and the Atomic Theory of Matter, from Boyle and Newton to Landau and Onsager}, Princeton University Press, Princeton, 1983, p. 277. \vskip.1truein\noindent [8] J.H.\ Conway and N.J.A.\ Sloane, {\it Sphere Packings, Lattices and Groups}, Springer-Verlag, New York, 1988. \vskip.1truein\noindent [9] F.M.\ Dekking and M.\ Keane, Mixing properties of substitutions, {\it Z.\ Wahrsch.\ Verw. Geb.}\ 42 (1978), 23-33. \vskip.1truein\noindent [10] C.\ Fefferman, The atomic and molecular nature of matter, {\it Rev.\ Math.\ Iberoamericana}, 1 (1985), 1. \vskip.1truein\noindent [11] C.\ Fefferman, The N-body problem in quantum mechanics, {\it Commun.\ Pure Appl.\ Math.\ Suppl.}\ 39 (1986), S67-S109. \vskip.1truein\noindent [12] C.\ Gardner, J.\ Mi\c ekisz, C.\ Radin and A.\ van Enter, Fractal symmetry in an Ising model, {\it J.\ Phys.\ A.: Math.\ Gen.}\ 22 (1989), L1019-1023. \vskip.1truein\noindent [13] C.F.\ Gauss, Untersuchungen \"uber die Eigenschaften der positiven tern\"aren quadratischen Formen von Ludwig August Seeger, G\"ottingische gelehrte Anzeigen, 1831 Juli 9 = Werke, II (1876), 188-196. \vskip.1truein\noindent [14] J.\ Ginibre, in {\it Syst\`emes \`a un nombre infini de degr\'es de libert\'e}, CNRS, Paris, 1969, pp. 163-175. \vskip.1truein\noindent [15] B.\ Gr\"unbaum and G.C.\ Shephard, {\it Tilings and Patterns}, Freeman, New York, 1986. \vskip.1truein\noindent [16] G.A.\ Hedlund, Remarks on the work of Axel Thue on sequences, {\it Nordisk Mat.\ Tidskrift}\ 15 (1967), 148-150. \vskip.1truein\noindent [17] D.\ Hilbert, Mathematische Probleme, {\it Archiv.\ Math.\ Phys.}\ 1 (1901), 44-63 and 213-237, translated in {\it Bull.\ Amer.\ Math.\ Soc.}\ 8 (1902), 437-479. \vskip.1truein\noindent [18] E.H.\ Lieb and H.-T.\ Yau, The stability and instability of relativistic matter, {\it Commun.\ Math.\ Phys.}\ 118 (1988), 177-213. \vskip.1truein\noindent [19] E.H.\ Lieb and H.-T.\ Yau, Many-body stability implies a bound on the fine-structure constant, {\it Phys.\ Rev.\ Letts.}\ 61 (1988), 1695-1697. \vskip.1truein\noindent [20] M.L.\ Minsky, {\it Computation: Finite and Infinite Machines}, Prentice Hall, Englewood Cliffs, New Jersey, 1967. \vskip.1truein\noindent [21] S.\ Mozes, Tilings, substitution systems and dynamical systems generated by them, {\it J. d'Analyse Math.}\ 53 (1989), 139-186. \vskip.1truein\noindent [22] D.\ Myers, Nonrecursive tilings of the plane, II, {\it J. Symbolic Logic} 39 (1974), 286-294. \vskip.1truein\noindent [23] W.\ Parry, Symbolic dynamics and transformations of the unit interval, {\it Trans. Amer. Math. Soc.}\ 122 (1966), 368-378. \vskip.1truein\noindent [24] W.\ Parry, {\it Topics in Ergodic Theory}, Cambridge tracts in mathematics, Vol.\ 75, Cambridge University Press, 1981, pp. 14-15. \vskip.1truein\noindent [25] R.\ Penrose, The role of aesthetics in pure and applied mathemtical research, {\it Bull.\ Inst.\ Math.\ Appl.}\ 10 (1974), 266-271. \vskip.1truein\noindent [26] M.\ Queff\'elec, {\it Substitution Dynamical Systems - Spectral Analysis}, Lecture Notes in Mathematics, Vol.\ 1294, Springer-Verlag, Berlin, 1987. \vskip.1truein\noindent [27] C.\ Radin and L.S.\ Schulman, Periodicity of classical ground states, {\it Phys.\ Rev.\ Lett.}\ 51 (1983) 621-622. \vskip.1truein\noindent [28] C.\ Radin, Correlations in classical ground states. {\it J.\ Stat.\ Phys.}\ 43 (1986), 707-712. \vskip.1truein\noindent [29] C.\ Radin, Low temperature and the origin of crystalline symmetry, {\it Int.\ J.\ Mod.\ Phys. B} 1 (1987), 1157-1191 . \vskip.1truein\noindent [30] C.\ Radin, Ordering in lattice gases at low temperature, {\it J.\ Phys.\ A: Math. Gen.}\ 22 (1989), 317-319. \vskip.1truein\noindent [31] C.\ Radin, Disordered ground states of classical lattice models, {\it Rev.\ Math.\ Phys.} to appear. \vskip.1truein\noindent [32] F.\ Riesz and B.\ Sz-Nagy, {\it Functional Analysis}, tr. by L.F.\ Boron, Frederick Ungar, New York, 1955, pp. 392-393. \vskip.1truein\noindent [33] R.M.\ Robinson, Undecidability and nonperiodicity for tilings of the plane, {\it Invent.\ Math.}\ 12 (1971), 177-209. \vskip.1truein\noindent [34] C.A.\ Rogers, {\it Packing and Covering}, Cambridge University Press, 1964, p. 14. \vskip.1truein\noindent [35] H.\ Rogers, Jr., {\it Theory of Recursive Functions and Effective Computabiilty}, McGraw-Hill, New York, 1967. \vskip.1truein\noindent [36] D.\ Ruelle, {\it Statistical Mechanics; Rigorous Results}, Benjamin, New York, 1969. \vskip.1truein\noindent [37] B.\ Simon, in {\it Perspectives in Mathematics: Anniversary of Oberwolfach 1984,} Birkhauser Verlag, Basel, 1984, p. 442. \vskip.1truein\noindent [38] P.\ J.\ Steinhrdt and S.\ Ostlund, {\it The Physics of Quasicrystals}, World Scientific, Singapore, 1987. \vskip.1truein\noindent [39] A.\ Thue, \"Uber die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene, {\it Skr. Vidensk-Selsk., Christ., No.\ 1}, (1910), 1-9. \vskip.1truein\noindent [40] A.M.\ Turing, On computable numbers, with an application to the Entscheidungsproblem, {\it Proc.\ London Math.\ Soc., ser.\ 2,} 42 (1936), 230-265; 43 (1936), 544-546. \vskip.1truein\noindent [41] G.E.\ Uhlenbeck, in {\it Statistical Mechanics; Foundations and Applications,} ed. T.A.\ Bak, Benjamin, New York, 1967, p. 581. \vskip.1truein\noindent [42] G.E.\ Uhlenbeck, in {\it Fundamental Problems in Statistical Mechanics II,} ed.\ E.G.D.\ Cohen, Wiley, New York, 1968, pp. 16-17. \vskip.1truein\noindent [43] H.\ Wang, Proving theorems by pattern recognition II., {\it Bell Systs.\ Tech.\ J.}\ 40 (1961), 1-41. \vskip.1truein\noindent [44] H.\ Wang, Notes on a class of tiling problems, {\it Fund.\ Math.}\ 82 (1975), 295-305. \end