\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}} \def\N{{\bf N}} \def\Q{{\bf Q}} \def\R[{{\bf R}} \def\T{{\bf T}} \def\Z{{\bf Z}} \def\mod{\mathop{\rm mod}\nolimits} \pageno=1 \footline{\ifnum\pageno=1\hss\else\hss\tenrm\folio\hss\fi} \hbox{} \vskip 2truein\centerline{\bf ARE THERE CHAOTIC TILINGS?} \vskip .8truein\centerline{by} \vskip .1truein \centerline{{Daniel Berend$^{\,1,2}$ \footnote*{Research supported in part by a grant from the Israel Science and \hbox{Technology Ministry}}} \ \ and\ \ \ {Charles Radin$^{\,1}$ \footnote{**}{Research supported in part by NSF Grant No. DMS-9001475\hfil}}} \vskip .2truein\centerline{\vbox{ 1\ \ Mathematics Department, University of Texas, Austin, TX\ \ 78712 \vskip.1truein 2\ \ Department of Mathematics and Computer Science, Ben-Gurion \vskip0truein\ \ \ \ University, Beer-Sheva 84105, Israel}} \vskip1truein\centerline{{\bf Abstract}} {\narrower\vskip.1truein\noindent We modify a method of S.~Mozes to produce interesting tiling dynamical systems with an {\bf R}$^n$-action in place of {\bf Z}$^n$-action. An example is given which is weakly mixing. \smallskip} \vfil\eject \parindent=20pt \hbox{}\vskip -.2truein \noindent {\bf 1.\ Introduction} \vskip .1truein The objective of this paper is to unify and extend work done by various people in the last few years on the {\bf order/disorder properties} of tilings of Euclidean n-space, $E^n$. A {\bf tiling} of $E^n$ is a decomposition of $E^n$ into a union of ``tiles'' where: \vskip .1truein \item{(a)}there is a fixed finite set ${\cal P}$ of ``prototiles'', which are homeomorphic images of the closed $n$-ball; \item{(b)}each tile is an isometric copy of some prototile, \item{(c)}the interiors of the tiles do not overlap, \item{(d)}the isometries in (b) are restricted to some fixed subgroup $G$ of the full isometry group of $E^n$. \vskip .1truein One of our main goals is to unify the work done on two types of tilings of $E^n$: the so-called ``Robinson-like tilings'' and the ``Penrose-like tilings'', the chief difference being that in the former only discrete (lattice) translations are used (to make tiles from prototiles), whereas in the latter the full translation group of $E^n$ is used [5,8,16]. (A significant motivation is the connection with quasicrystals [8,16].) Before discussing tiling any further, we need to endow the space $V({\cal P})$ (assumed nonempty) of all tilings by some given set ${\cal P}$ of prototiles with a topology. The motivating idea for the topology is that tilings should be close if they differ only slightly inside some large bounded region. To implement this we use the Hausdorff distance of a pair of compact subsets $A, B$ of $E^n$, defined as $h[A, B] = \max \{s(A, B), s(B, A)\}$, where $s(A, B) = \sup_{a \in A} \inf_{b \in B} \|a - b\|$. A finite set of nonoverlapping tiles will be called a swatch. We define a countable base for the topology on $V({\cal P})$, using some countable dense subset $G'$ of the topological subgroup $G$ (usually ${\bf Z}^n$ or ${\bf R}^n$) of the isometry group of $E^n$, as follows. Given a positive integer $k$, a set of positive rationals $\{r_j\}_1^k$, and a swatch of tiles $\{g'_j(P'_j)\}_1^k$ (where $g'_j \in G',\,P'_j\in {\cal P}$), we define the open set consisting of all tilings containing a swatch $\{g_j(P_j)\}_1^k$ such that $h[g_j(P_j), g'_j(P'_j)] < r_j$ for all $j\le k$. We note that the space $V({\cal P})$, of tilings from a given prototile set ${\cal P}$, is compact and metrizable, and $G$ acts continuously on $V({\cal P})$ [10]. \vskip .1truein As said earlier, our interest here is in the order/disorder properties of tilings. Now questions about order properties are best discussed in the framework of ergodic theory, since this allows us to make use of probabilistic notions of order through the spectral or mixing properties of certain dynamical systems associated with tilings of $E^n$. (By a dynamical system we mean a (compact metrizable) space $X$ on which some topological group $H$ is continuously represented by homeomorphisms. In most classical examples $H$ is ${\bf Z}$ or ${\bf R}$ but we will also need ${\bf Z}^n$ and ${\bf R}^n$.) Dynamical systems with $H={\bf Z}^n$ will be called discrete, those with ${\bf R}^n$ continuous. If there is also a probability measure $\mu$ on $X$, invariant under the group action, we have further techniques going under the heading of ergodic theory.) We will be couching much of our discussion in the framework of ergodic theory. For example, we mentioned above that one of our primary objectives is to unify the work done on two types of tilings of $E^n$; this will be accomplished by associating similar dynamical systems with such tilings, the main difference being that for the former type one has the action of ${\bf Z}^n$ and for the latter ${\bf R}^n$. To illustrate the relationship between the two types of dynamical systems to be considered, we begin with the following (oversimplified) situation. Consider any subshift $(X,T)$ over a finite alphabet ${\cal A}\,;$ that is, $X\subseteq{\cal A}^{\bf Z}$ is compact and $T$ is lattice translation on $X$ in the usual sense that $T:x=(x_j)_{j\in {\bf Z}}\in X \longrightarrow Tx\in X$, where $(Tx)_j = x_{j+1}$. (We will need to refer on occasion to the cylinder sets ${\cal C}_a\equiv \{x\in X\,:\, x_0=a\}$, $a \in {\cal A}$.) Then, given a positive real-valued function $f$ on the alphabet ${\cal A\,,}$ we associate with this subshift $(X,T)$ (which is a {\bf discrete} dynamical system, the group ${\bf Z}$ being represented by powers of $T$), the {\bf continuous} dynamical system $(X_f, T_f)$ defined as follows. $X_f$ is the set of all two-sided sequences $\{y_j=[a_j,a_{j+1})\subset {\bf R}\,:\,j\in {\bf Z}\}$ of abutting intervals, for which $0 \in y_0$ and there is some $x\in X$ such that the lengths satisfy $|y_j|= f(x_j)$ for all $j\in {\bf Z}$. (Translates of such sequences of abutting intervals are distinguished as points of $X_f$.) $X_f$ is compact in the topology generated by sets of the form ${\cal C}_{y, B, \epsilon}\equiv\{y'\in X_f\,:\,\hbox{there exists } s,\ |s|<\epsilon,\hbox{ with } {y'}_j = y_j+s \hbox{ for all }j\in B\}$, where $B$ is a finite subset of ${\bf Z}$, $\epsilon > 0$ and $y\in X_f$. Finally, the group ${\bf R}$ is represented by the family $T_f^t$ of translations, where as usual $(T_f^ty)_j=y_j+t$. (An illustrative example has for $X$ the orbit closure under translation of the ``Morse sequence'', and an arbitrary fixed $f$.) By construction, the two spaces $X_f$ and $X$ are closely related, but of course the dynamical action is quite different for the two, and that for $X_f$ depends in any case on the function $f$. In particular, any rational relation between the values of $f$ (for example if $f$ is constant) essentially introduces a relation in the elements of $X_f$ between the roles that the letters of ${\cal A}$ play in the elements of $X$, so it is natural to focus attention on those $f$ for which the range is a rationally independent set. We are primarily interested, for reasons discussed below, in cases where there are natural invariant probability measures $\mu_X$ (resp.~$\mu_Y$) on $(X,T)$ (resp.~$(X_f, T_f))$, and we want to know the relation between the spectra of the pair of related dynamical systems. To remind the reader of the definition of spectrum, consider the complex Hilbert subspace ${\cal H}_X\subset L^2(X,\mu_X)$ (resp.~${\cal H}_Y\subset L^2(X_f,\mu_Y)$) which is the orthogonal complement of the subspace of constant functions, and the unitary operators $T^j$ on ${\cal H}_X$ for $j\in {\bf Z}^n$ (resp.~$T_f^t$ on ${\cal H}_Y$ for $t\in {\bf R}^n$), with spectral resolutions $T^j = \hbox{$\int_{[0,1]^n}\exp(2\pi i\lambda\mkern1mu\cdot\mkern1mu j)\,dE_{\lambda}$}$ (resp.~$T_f^t = \hbox{$\int_{{\bf R}^n}\exp(2\pi i\lambda\mkern1mu\cdot\mkern1mu t)\,dE_{\lambda}.$}$) Such spectral resolutions define [12], for nonzero vectors $\psi$, measures $\mu_\psi = (\psi,\,dE_\lambda\psi)$ on $[0,1]^n$ (resp.~${\bf R}^n$). We are interested in the smoothness in $\lambda$ of such measures as $\psi$ varies over the unit sphere of ${\cal H}_X$ (resp. ${\cal H}_Y$). Every measure $(\psi,\,dE_\lambda\psi)$ decomposes uniquely into three parts: discrete, singular continuous and absolutely continuous [15]. Similarly, the space ${\cal H}_X$ (resp. ${\cal H}_Y$) admits a decomposition into orthogonal subspaces such that for a vector $\psi$ in one of these, the measure $\mu_{\psi}$ is indecomposable (that is, has only one part) [11]. A dynamical system is said to have purely discrete (resp.~singular continuous, resp.~absolutely continuous) spectrum if exactly one of these subspaces is nonzero, and the measures corresponding to its vectors are discrete (resp.~singular continuous, resp.~absolutely continuous.) We continue our discussion by specifying $(X,T)$ as the substitution dynamical system determined by the substitution $\xi$: $$\xi(0) = 0101,\ \ \ \xi(1) = 1110\ .\eqno (1)$$ \noindent Thus $(X,T)$ is the subshift defined as follows. For each finite sequence $B$ of 0's and 1's let $\xi(B)$ be the finite sequence obtained by applying the above substitution rules to each 0 and 1 in B. Then define $D_0 = \{0,1\}$, $D_{j} = \bigcup_{B\in D_{j-1}}\xi(B)$ for each $j\in{\bf N}$, and $D = \bigcup_{j\ge 0}D_j$. The ``subblocks'' of a finite or infinite sequence $x=(x_j)_{j\in S} \in \{0,1\}^S$, where $S$ is a subinterval of ${\bf Z}$, are the restrictions of the ``function'' $x$ to finite subintervals of $S$. Then, finally, $X$ is defined as the subset of $\{0,1\}^{{\bf Z}}$ consisting of those $x$ all of whose subblocks belong to $D$. We note that $(X,T)$ is uniquely ergodic [7] (i.e., there exists a unique $T$-invariant probability measure on $X$), which easily implies that $(X_f,T_f)$ is also uniquely ergodic for any $f$. \vskip .2truein \noindent {\bf 2.\ Preliminary results} \vskip .1truein Our first result is \vskip .1truein\noindent \noindent {\bf Lemma 1}.\ \ Let $(X,T)$ be the substitution dynamical system defined by the substitution $\xi$ given by (1). If $f(0)$ and $f(1)$ are rationally independent, then the associated {\bf continuous} system $(X_f,T_f)$ has no discrete spectrum. \vskip .1truein Before giving the proof, it is appropriate to note the similarity of this result to an elegant result of Dekking and Keane [3]. The definition given above, of the continuous system $(X_f,T_f)$ associated with the (general) discrete system $(X,T)$, is equivalent to what is known in ergodic theory [1,2] as ``the flow under $\tilde f$ over $T$'', where $\tilde f$ is the continuous function on $X$ given by $\tilde f(x)= f(x_0)$, and is defined as follows. The underlying compact space for the system is ${X'_f} \equiv \{(x,s)\in X\times{\bf R}\,:\,0\le s\le \tilde f(x)\}$ in which all pairs of points $(x,\tilde f(x))$ and $(Tx,0)$ are identified, and the dynamics is determined by ${T'_f}^t(x,s) \equiv (x,s+t)$ for $0\le t < \tilde f(x) -s$, given the identification in the definition of ${X'_f}$. This system $({X'_f},{T'_f})$ can be viewed as follows. Each point $x$ in the ``base'' $X$ generates a fiber $\{(x,s)\,:\,0\le s \le \tilde f(x)\}$ in ${X'_f}$ of height $\tilde f(x)$, and the dynamics moves $(x,0)$ up the fiber at constant speed until it hits the ``ceiling'' at which it ``jumps'' to the point $(Tx,0)$ and continues the motion. Of course, the jump is actually continuous because of the identification. There is an analogous construction, which however associates with $(X,T)$ another {\bf discrete} system, $(\hat X_f, \hat T_f)$. Here the function $f$ on ${\cal A}$ assumes positive {\bf integer} values. The system $(\hat X_f,\hat T_f)$, called a tower over $(X,T)$, is defined as follows. $\hat X_f\equiv \{(x,j)\in X\times{\bf Z}\,:\, 0\le j\le f(x_0)+1\}$ in which we identify pairs of points of the form $(x,f(x_0)+1)$ and $(Tx,0)$. The dynamics is determined by $\hat T_f(x,j) \equiv (x,j+1)$ whenever $0\le j < f(x_0)+1$, given the identification in the definition of $\hat X_f$. The above tower constuction is conceptually very similar to that of the flow under a function. And as was the case with the flow under a function, it is sometimes preferable to have the following alternative picture of this tower. It is easy to see that $(\hat X_f,\hat T_f)$ is isomorphic to the subshift defined as the sequences in ${\cal A}^{\bf Z}$ obtained from those in $X$ by replacing each letter $a$ by $f(a)$ copies of itself; in a sense, the tower ``stretches'' each letter $a\in {\cal A}$ by the factor $f(a)$. Given this, it is not so surprising that our proof of Lemma 1 is very similar to that by Dekking and Keane of \vskip .1truein \noindent {\bf Lemma 2}\ [3].\ \ Let $(X,T)$ be the dynamical system defined by the substitution $\xi$ given by (1). If $f(0)=2$ and $f(1)=1$, then the associated {\bf discrete} system $(\hat X_f,\hat T_f)$ has no discrete spectrum. \vskip .1truein At this point we give the proof of Lemma 1. \vskip .1truein\noindent {\bf Proof.}\ Suppose we have an eigenfunction $g$ of the family ${T^t_f}$: $${T^t_f}g(x,s)=e^{2\pi i\lambda t}g(x,s)\ .\eqno(2)$$ Let $u$ be the function on $X$ defined as the restriction of $g$ to some height $s_0$, $0\le s_0<\min\{f(0),f(1)\}$ (where (2) holds for all $t$ a.e.): $$u(x)=g(x,s_0),\qquad x\in X\ .$$ In view of (2) we have: $$Tu(x)=\cases{ e^{2\pi i\lambda f(0)}u(x),&$\ x\in {\cal C}_0$\cr e^{2\pi i\lambda f(1)}u(x),&$\ x\in {\cal C}_1\ .$\cr } $$ Defining a sequence of functions $f_n\,:\,X\to {\bf R}_+\,,\ n\ge 1$, by $$f_n(x)=\sum_{k=0}^{4^n-1}f([T^k x]_0)\ ,$$ we have: $$T^{4^n}u\ =\ e^{2\pi i\lambda f_n}u\ .$$ As in the proof of Theorem 1 in [3], this implies that $e^{2\pi i\lambda f_n}\buildrel L^2\over \longrightarrow 1$, or, equivalently, $$\lambda f_n\buildrel L^2\over \longrightarrow 0\ (\mod\,1)\eqno(3)$$ (where $\buildrel L^2 \over \longrightarrow$ denotes convergence in $L^2$ norm). Again as in [3] we can find sets $A_n \subseteq X$ whose measures are bounded away from $0$ such that $$f_n(x)\ =\ {4^n-1\over 3}f(0)+{2\cdot 4^n+1 \over 3}f(1)\,,\qquad x\in A_n\ .\eqno(4)$$ From (3) and (4) it follows that: $$4^n\lambda {f(0)+2f(1)\over 3}\longrightarrow \lambda {f(0)-f(1)\over 3}\ (\mod\,1)\ .\eqno(5)$$ In particular, the right hand side is invariant under multiplication by $4$ modulo $1$: $$4\lambda {f(0)-f(1)\over 3}=\lambda {f(0)-f(1)\over 3}\ (\mod\,1)\ .$$ Consequently, $\lambda f(1)=\lambda f(0)+l$ for some $l\in {\bf Z}$. Again by (5), $3\lambda f(0) + 2l$ is a ($2$-adic) rational, so both $\lambda f(0)$ and $\lambda f(1)$ are rationals. As $f(0)$ and $f(1)$ are rationally independent, this implies $\lambda =0$. This means in turn that $u$ is a $T$-invariant function. As $T$ is ergodic, $u$ is constant a.e. Also, since $\lambda=0$ the function $g$ is constant as a function of $s$ for each fixed $x$. Thus, $g$ is constant in both variables.\qed \vskip .2truein\noindent {\bf 3.\ Tilings and Order} \vskip .1truein One could try to understand the order properties of all types of tilings [13], but we are primarily concerned with prototile sets which {\bf force} interesting features in {\bf all} their tilings. This line of development is due to Wang [17], who (motivated by certain questions in logic) initiated the study of sets of prototiles which can tile the plane but {\bf only} with tilings which are {\bf nonperiodic}. (A tiling is periodic if it consists of a lattice of translates of one of its swatches.) Two of the early notable examples are the sets of prototiles discovered by Robinson [14] and by Penrose [4] which can tile the plane but only nonperiodically. The work of Wang eventually led to a succession of efforts to find sets of prototiles for which the tilings are of necessity (that is, for which {\bf all} tilings are) more and more ``disordered'' -- a notion which is inherently vague, but which we specify for this work below. This in turn has developed beyond tilings into a separate subfield of mathematics, in which one analyzes the order and symmetry properties which are determined by the optimization of a function of many weakly interacting variables [8]. A major step forward in this field was the development by Mozes [6] of a technique which combined the ideas in Robinson's example with the (more developed) mathematics of substitution dynamical systems. Simply put, Mozes showed how, given any two substitution dynamical systems (satisfying some mild conditions), one can construct a (large) set of prototiles in $E^2$, each of which is a unit square with small bumps and dents on its edges, all centered at the origin in the plane and with edges aligned, such that the associated discrete dynamical system (with ${\bf Z}^2$ ``dynamics'') is uniquely ergodic, and is measure- theoretically isomorphic to the product of the two given substitution dynamical systems. If the systems are $(X_1,T_1)$ and $(X_2,T_2)$, with alphabets ${\cal A}_1$ and ${\cal A}_2$, the product is $(X_1\times X_2,{\bf T})$, where ${\bf T}=(T_1^j\times T_2^k)_{j,k=-\infty}^{\infty}, T_1^j\times T_2^k\,:\, (x_1,x_2) \longrightarrow (T_1^jx_1,T_2^kx_2)$. The isomorphism is a simple one-to-one correspondence between the tilings and the elements of $X_1\times X_2$; there is a many-to-one correspondence between the prototiles and pairs $(a,b)\in {\cal A}_1\times{\cal A}_2$, and each tiling, which is a two-dimensional array of (essentially) unit square tiles, is naturally identifiable with the corresponding element of $X_1\times X_2$. This was used in [9] as follows. In proving Lemma 2, Dekking and Keane had noted that the tower associated with (1) is again a substitution dynamical system. \vskip .1truein\noindent {\bf Theorem 1}\ [9].\ \ Using the tower associated with (1) for both factors in the construction of Mozes, one obtains a {\bf discrete}, uniquely ergodic tiling system which is weakly mixing; that is, has no discrete spectrum. \vskip .1truein We now note that the above is easy to modify to adapt to continuous tilings. We begin by using the substitution dynamical system $(X,T)$ defined by (1) for both factors in Mozes' construction. Next we modify the shapes of the ``square'' prototiles that the construction produces, by ``stretching'' each one associated with the pair $(a,b)\in\{0,1\}\times\{0,1\}$ to a rectangle with horizontal edges $f(a)$ and vertical edges $f(b)$, where $f(0)$ and $f(1)$ are fixed and rationally independent. Lemma 1 then implies that the continuous tiling system thus produced is weakly mixing. We summarize in \vskip .1truein\noindent {\bf Theorem 2}.\ \ Using the flow under the function associated with (1) for both factors in our modification of the method of Mozes, one obtains a {\bf continuous}, uniquely ergodic tiling system which is weakly mixing; that is, has no discrete spectrum. \vskip .2truein \noindent {\bf 4.\ Closing Remarks} \vskip .1truein Notice that for our examples there are invariant probability measures which we use to describe the disorder. It is essential for our purposes that there is no choice involved with these measures: they are uniquely defined by the prototile sets themselves. If one could {\bf choose} an invariant measure, there would be no depth to the subject: one could very easily find a prototile set with associated dynamics which was very wild. For example, the one-dimensional continuous tiling system, with prototile set consisting of two intervals of incommensurate lengths, is strongly mixing if one chooses an appropriate measure; just use the method of the introduction, applying the flow under a function to the ``Bernoulli shift'', $X = \{0,1\}^{{\bf Z}}$, equipped with the product measure $\mu_B$ for which $\mu_B({\cal C}_0)=\mu_B({\cal C}_1)=1/2$. On the other hand, it is a major unsolved problem to determine whether or not there is a uniquely ergodic tiling dynamical system (discrete or continuous) which has purely absolutely continuous spectrum [9], which we would call ``chaotic'', and which explains the title of this paper. The method of Theorem 1 cannot produce a strongly mixing {\bf discrete} system since the factors, being substitution systems, cannot be strongly mixing [3,7]. It is unclear to us whether or not the method of Theorem 2 can produce a strongly mixing {\bf continuous} system. \bigskip \baselineskip=12pt \frenchspacing \centerline{\bf Bibliography} \smallskip \item{[1]} W. Ambrose, Representation of ergodic flows, {\it Ann.\ Math.}\ {\bf 42} (1941), 723--739. \item{[2]} I.P. Cornfeld, S.V. Fomin and Ya.G. Sinai, {\it Ergodic Theory}, Springer-Verlag, Berlin, 1982. \item{[3]} F. M. Dekking and M. Keane, Mixing properties of substitutions, {\it Zeit.\ Wahr.}\ {\bf 42} (1978), 23--33. \item{[4]} M. Gardner, Mathematical Games, {\it Sci.\ Amer.}\ {\bf 236} (1977), 110--121. \item{[5]} B. Gr\"unbaum and G.C. Shephard, {\it Tilings and Patterns}, Freeman, New York, 1986. \item{[6]} S. Mozes, Tilings, substitution systems and dynamical systems generated by them, {\it J.\ d'Analyse Math.}\ {\bf53} (1989), 139--186. \item{[7]} M. Queff\'elec, {\it Substitution Dynamical Systems -- Spectral Analysis}, Springer-Verlag, Berlin, 1987. \item{[8]} C. Radin, Global order from local sources, {\it Bull.\ Amer.\ Math.\ Soc.}\ {\bf 25} (1991), 335-364. \item{[9]} C. Radin, Disordered ground states of classical lattice models, {\it Revs.\ Math.\ Phys.}\ {\bf 3} (1991), 125-135. \item{[10]} C. Radin and M. Wolff, Space tilings and local isomorphism, {\it Geometriae Dedicata}, to appear. \item{[11]} M. Reed and B. Simon, {\it Methods of Modern Mathematical Physics, I}, Academic Press, New York, 1972. \item{[12]} F. Riesz and B. SZ. Nagy, {\it Functional Analysis}, tr. by L.F. Boron, Frederick Ungar, New York, 1955. \item{[13]} A.E. Robinson, The dynamical theory of tilings and quasicrystallography, preprint, 1991. \item{[14]} R. Robinson, Undecidability and nonperiodicity for tilings of the plane, {\it Invent.\ Math.}\ {\bf 12} (1971), 177--209. \item{[15]} H. L. Royden, {\it Real Analysis}, Macmillan, New York, 1964. \item{[16]} M. Senechal and J. Taylor, Quasicrystals: The view from Les Houches, {\it Math.\ Intelligencer} {\bf 12} (1990), 54-64. \item{[17]} H. Wang, Proving theorems by pattern recognition -- II, {\it Bell Systems Tech.\ J.}\ {\bf 40} (1961), 1--41. \end