\magnification 1200
  \hsize=5.8truein	\hoffset=.25truein 
  \vsize=8.8truein	
  \pageno=1     \baselineskip=12pt
  \parskip=0 pt		\parindent=20pt
  \overfullrule=0pt	\lineskip=0pt	\lineskiplimit=0pt
  \hbadness=10000 \vbadness=10000 %	REPORT ONLY BEYOND THIS BADNESS
\let\nd\noindent %						NOINDENT
\def\NL{\hfill\break}%						NEWLINE
\def\qed{\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}}
\parindent=40pt 
\pageno=1
\footline{\ifnum\pageno=1\hss\else\hss\tenrm\folio\hss\fi}
\hbox{}
\vskip 1truein\centerline{\bf SPACE TILINGS AND LOCAL ISOMORPHISM}
\vskip .8truein\centerline{by}
\vskip .1truein
\centerline{{Charles Radin$^{\,1}$
\footnote*{Research supported in part by NSF Grant No. DMS-9001475\hfil}}
\ \ \ \ \ Mayhew Wolff$^{\,2}$}
\vskip .2truein\centerline{
1\ \ Mathematics Department, University of Texas, Austin, TX\ \ 78712}
\vskip 0truein\centerline{
2\ \ Mathematics Department, University of California, Berkeley, CA\ \ 94720}
\vskip 1.2truein\centerline{Classification Numbers: 52A45, 47A35}
\vskip .5truein\centerline{{\bf ABSTRACT}}
{\narrower\vskip .1truein\noindent We prove that for every finite tile set,
isometric copies of which can tile euclidean $n$-space, there is a tiling
with the local isomorphism property.\smallskip}

\hfil\eject
\parindent=20pt
\hbox{}\vskip -.1truein
\centerline{{\bf 1.\ INTRODUCTION AND STATEMENT OF RESULTS}}
\vskip .1truein
The subject of this paper is the tiling of euclidean spaces. By
a tiling of {\bf R}$^n$ we mean a representation of {\bf R}$^n$ as the
union of ``tiles'' -- think of an $n$-dimensional jigsaw puzzle
filling all of {\bf R}$^n$ -- where: 
\vskip .1truein
\item{(a)}there is a fixed finite set $S$ of ``prototiles'', which are
pairwise noncongruent homeomorphs of the closed $n$-ball;

\item{(b)}each tile is an isometric ``copy'' of some prototile, that is, it
is the image of 
a prototile by a symmetry operation (translation and/or rotation);

\item{(c)}the interiors of the tiles do not overlap;

\item{(d)}given a tile, its boundary can be covered by other tiles,
with no overlapping, in only a finite number of ways.
\vskip .1truein 
\noindent (Condition (d) forbids the following pair of 3-dimensional
prototiles: a circular cylinder of diameter 1 and height $L$ (i.e.
$\{(x,y,z)\,:\, x^2+y^2\le 1/2,\, 0\le z\le L\}$), and 
a cube of side 2
with a semicircular groove of diameter 1 (i.e. 
$\{(x,y,z)\in [0,2]\times [-1,1]\times [0,2]\,:\, x^2+y^2\ge 1/2\}$).
These are not allowed because
one tile can be slid along the other. In fact if the height $L$ of the
cylindrical tile is irrational, this tile set would otherwise be a
counterexample to the Theorem below.)

Tilings of euclidean spaces are of interest for a myriad of reasons;
we are motivated by certain questions concerning sets of prototiles
(copies of) which can tile space but only in special ways.  This line
of development is due to Hao Wang, who (because of certain questions
in logic [15-18, 5]) first studied sets of prototiles which could tile
the plane but {\bf only} with tilings which were {\bf nonperiodic}. (A
finite set of nonoverlapping tiles is called a ``patch'', and a
tiling is called periodic if it consists a lattice of translates of
one of its patches.) A notable example is the set of
prototiles discovered by Roger Penrose which can tile the plane but
only nonperiodically [7, 5, 12].

The work of Wang eventually lead to a succession of efforts
(culminating in [6]) to find sets of prototiles for which the tilings
were of necessity more and more ``disordered'' -- a notion which is
inherently vague; see however [12].  We consider a property that
a tiling might have, called ``local isomorphism''.
\vskip .1truein\noindent
{\bf Definition}.\ \ A tiling enjoys the {\bf local isomorphism}
property if for every patch $P$ in the tiling there is some distance
$d(P)$ such that every sphere of diameter $d(P)$ in the tiling
contains an isometric copy of the patch.
\vskip .1truein
It is one of the frequently noted features of the Penrose set that all
of its tilings satisfy the local isomorphism property (and with a
rather small value of $d(P)$) [5]. Various authors have used the local
isomorphism property as a hallmark of the ``regularity'' or ``order''
of certain tilings [5, 8, 14] or similar arrays or patterns [1, 2, 3], 
sometimes
using terms such as ``weak periodicity'' or ``recurrence'' in place of
``local isomorphism''. There are two goals to this paper. The first is
the following technical result and its corollary.
\vskip .1truein\noindent
{\bf Theorem}.\ \ If a set of prototiles admits a tiling of space, it must
admit a tiling satisfying the local isomorphism property.
\vskip .1truein\noindent
This shows that local isomorphism is not at all an unusual property of
a set of prototiles; in fact it is universal! (This answers an open
problem, Exercise 11.2.4 in [5].) To further justify this
adjective it is useful to introduce the concept of ``unique
ergodicity''. This is a nondegeneracy condition that a set $S$ of
prototiles usually satisfies in practice, namely that the set $V(S)$
of all its tilings is nonempty and supports one and only one
$G$-invariant Borel probability measure (where $G$ is the symmetry
group of the euclidean space). (See [12] for a discussion of
this form of nondegeneracy.) For nondegenerate prototile sets we
prove the following corollary.
\vskip .1truein\noindent
{\bf Corollary}.\ \ If $V(S)$ is uniquely ergodic with unique measure
$\rho$, then all tilings in $V(S)$ have the local isomorphism property
except for a subset of $\rho$-measure zero. Furthermore, the diameter
function $d(P)$ is independent of the tiling.
\vskip .1truein
The second goal of this paper is to emphasize the usefulness of
ergodic theory as a tool in tiling theory: indeed, the main step in
our proof of the above results is to interpret the subject of tiling
as part of dynamical systems.
\vskip .2truein
\centerline{{\bf 2.\ PROOF OF THE RESULTS}}
\vskip .1truein
Our first step is to put a topology on the space $V(S)$ (assumed
nonempty) of all tilings of some given set $S$ of prototiles. The
motivating idea is that tilings should be close if they differ only
slightly inside some large bounded region. For this
we use the Hausdorff distance of a pair of compact subsets $A, B$ of
{\bf R}$^n$, defined as $\mu[A, B] = \max
\{h(A, B), h(B, A)\}$, where $h(A, B) = \sup _ {a \in A}
\inf _ {b \in B} \|a - b\|$. We define a countable base for
the topology on $V(S)$ using some countable dense subset
$G'\equiv\{g_j\,:\, j\ge 1\}$ of the topological group $G$ of
symmetries, as follows. Given some $n \ge 1$, a set of positive
rationals $\{r_j\}_1^n$, and a patch of tiles $\{g'_j(P'_j)\}_1^n$
(where $g'_j
\in G',\,P'_j\in S$), we define the open set: the set of all tilings 
which contain a patch $\{g_j(P_j)\}_1^n$ such that $\mu[g_j(P_j),
g'_j(P'_j)] < r_j$ for all $j\le n$.

A simple consequence of the definitions, particularly condition (d), is
the following.
\vskip .1truein\noindent
{\bf Lemma 1}.\ \ Given an open set $U$ defined by a finite patch
$\{g_j(P_j)\}_1^n$ and positive numbers $\{r_j\}_1^n$,
if the $r_j$ are sufficiently small then every
tiling in $U$ contains a patch of the form $\{h\circ
g_j(P_j)\}_1^n$ for some $h\in G$ near the identity, that is, a
small isometric shift of the patch defining the open set. 
\vskip .1truein\noindent
An important feature of the topology on $V(S)$ is the following.
\vskip .1truein\noindent
{\bf Lemma 2}.\ \ The space $V(S)$, of tilings from a given prototile set
$S$, is compact.
\vskip .1truein\noindent
\hfil\eject
\nd
{\bf Proof of lemma 2}.
\vskip 0truein\noindent
(Note that this proof does not require condition (d), and therefore
holds even for very general tilings.)  It is enough to prove the
sequential compactness of the metrizable space $V(S)$ [13]. Choose a
sequence $\{l_i\,:\,i\ge 1\}$ of points in {\bf R}$^n$ such that any
tile must contain some $l_i$. (For example, one could choose a
sufficiently fine lattice, numbered to spiral outward from the
origin.) Now suppose we are given a sequence $\{T_i\,:\,i\ge 1\}$ of
tilings in $V(S)$. The idea is to force the tilings to agree more and
more closely on larger and larger patches. The first part of our proof
will be an induction, where the induction hypothesis on $m \ge 1$ has
the following three parts.
\vskip .1truein

\item{1.}There is a subsequence $\{T_i^m\,:\,i\ge 1\}$ of
$\{T_i\,:\,i\ge 1\}$, and for each $i$ a patch 
of $m$ distinct tiles $\{\tau_{i,j}^m\,:\,1\le j\le m\}$ in
$T_i^m$, such that:

\itemitem{i)}$\{T_i^m\,:\,i\ge 1\}$ is a subsequence of
$\{T_i^{m-1}\,:\,i\ge 1\}$, where we define $T_i^0 = T_i$;

\itemitem{ii)}For $1 \le j \le m$, the sequence $\{\tau_{i,j}^m\,:\, i\ge 1\}$
converges, in the Hausdorff metric, to a tile (independent of $m$) 
which we will call $\tau_j$.

\item{2.}The interior of the tile $\tau_m$ is disjoint from the interiors of
all ``previous'' $\tau_j$,
(that is, $\tau_j$ for $1 \le j < m$).

\item{3.}$\tau_m$ contains the point $l_{p(m)}$, where $l_{p(m)}$
is defined to be the first $l_i$ which is not contained in any
previous $\tau_j$.

\vskip .1truein\noindent
The induction hypothesis holds for $m = 1$ by the following theorem.
\vskip .1truein\noindent
Selection Theorem ([5]). Given an infinite sequence of tiles $\tau_j$ all 
with some point in common and all congruent to a tile $\tau'$,
then some subsequence of the $\tau_j$ converges to a tile congruent to
$\tau'$.
\vskip .1truein\noindent
(In fact our proof uses some of the technique of that of the Selection 
Theorem.)
Now suppose $m \ge 2$ and that the hypothesis is true for $m-1$.  For
$i \ge 1$ pick some tile $\hat \tau_i^m$ in $T_i^{m-1}$ which contains
the point $l_{p(m)}$, and consider the sequence $\{\hat
\tau_i^m\,:\,i\ge 1\}$. (It is not hard to see that there exists $I(m)$ such 
that if $i \ge I(m)$ then $\hat \tau_i^m \ne \tau_{i,j}^{m-1}$, for
any $1\le j < m$.) By the Selection Theorem and the fact that $S$ is
finite, the sequence $\{\hat
\tau_i^m\,:\, i\ge 1\}$ contains a convergent subsequence, $\{\hat
\tau_{s(i)}^m\,:\, i\ge 1\}$; we also require that $s(m) > I(m)$ for
all $m$. For all $i \ge 1$ and $ 1 \le j < m$ define: $T_i^m =
T_{s(i)}^{m-1}$, $\tau_{i,j}^m = \tau_{s(i),j}^{m-1}$, and
$\tau_{i,m}^m = \hat \tau_{s(i)}^m$.  Finally, let $\tau_m = \lim_i
\hat \tau_{s(i)}^m$. It is easy to check that the induction holds for
this choice of $\tau_m$ and $T_i^m$.  Namely, for all $i \ge I(m)$ the
interior of $\tau_{i,m}^m$ is disjoint from those of any
$\tau_{i,j}^m$ for $1 \le j < m$, so when we take the limit in $i$ the
interior of $\tau_m$ is disjoint from those of all previous $\tau_j$.
Clearly $l_{p(m)} \in \tau_m$. And finally, the required convergence
property for the $\tau_{i,j}^m$ is preserved when we take a
subsequence.

So the induction holds for all $m\ge 1$. To continue the proof of the
lemma we now diagonalize: define $T'_i = T_i^i$, and let $T'$ be the
tiling consisting of the $\{\tau_j\}$. (That the $\{\tau_j\}$
constitute a tiling is easy to see since they can be approximated by
patches of tilings.) We claim that $T'_i \rightarrow T'$. To see this,
consider any open set $O$ defined by a patch $\{\tilde
\tau_{j}\,:\,1\le j\le k\}$ and positive numbers $\{r_j\,:\,1\le j\le
k\}$ and containing $T'$.  For $1\le j \le k$ we know $\lim_i
\tau_{i,j}^k = \tau_j$, so for large enough $i$ it follows that
$T'_i$ is in $O$. This proves that $T'_i \rightarrow T'$, and since
$\{T'_i\}$ is a subsequence of $\{T_i\}$ the lemma is proven.
\vskip .1truein\noindent
Getting back to the proof of the theorem, we note that the compact
space $V(S)$, together with the action on it of the group $G$ of
symmetries of {\bf R}$^n$, constitute a dynamical system. We say the
nonempty closed subset $X$ of $V(S)$ is ``minimal invariant'' if there
is no closed subset of $X$, other than $X$ itself or the empty set,
which is invariant under $G$. It is a simple application of the Axiom
of Choice to prove that such a subset of $V(S)$ must exist [4]; so fix
such an $X$. Given any relatively open subset $O$ of $X$, since
$\bigcup_{g\in G}g^{-1}(O)$ is a nonempty invariant relatively open
subset of $X$, it follows that it must equal $X$. From the compactness
of $V(S)$ and therefore of $X$ it follows that there exists a finite
subset $\{g_i\}$ of $G$ such that $\bigcup_ig_i^{-1}(O) = X$.

Using this, we will show that any tiling $T\in X$ has the local isomorphism
property:
so suppose we are given a patch $P$ in $T$. It is a simple
consequence of Lemma 1 that there is an open ball $B$ of diameter
$2\hbox{diam}(P) + 1$ in {\bf R}$^n$ containing $P$, and a basic
open set $U$ containing $T$, such that all the tilings in $U$
contain a copy of $P$ inside $B$. Let $\{g_i\,:\,i\in I\}$ be the finite
set of symmetries such that $\bigcup_{i\in I}g_i^{-1}(U)$ contains
$X$, as guaranteed above, and therefore contains the orbit of $T$
under $G$. Then any sphere in $T$ of diameter $2\sup\{\Vert g_i(b)
- b'\Vert\,:\,i\in I,\,b\in B,\,b'\in B\}$ will contain a copy of $P$,
which proves the theorem.  As for the corollary, it follows from the
fact that the support of a uniquely ergodic measure is minimal
invariant [4].\qed

\hfil\eject
\hbox{} \vskip-.4truein
\centerline{{\bf REFERENCES}}
\vskip .1truein\noindent
[1] S.\ Aubry, Weakly periodic structures and example, {\it J. Physique
(Paris), Coll.\ C3} 50 (1989), 97-106.
\vskip.1truein\noindent
[2] E.\ Bombieri and J.\ Taylor, Which distributions of matter diffract?:
An initial investigation, {\it J.\ Physique (Paris), Coll.\ C3}, 47 (1986), 
3-19.
\vskip.1truein\noindent
[3] E.\ Bombieri and J.\ Taylor, Quasicrystals, tilings, and algebraic
number theory, {\it Contemporary Mathematics}\ 64, Amer.\ Math.\ Soc.\ ,
Providence, 1987, 241-264.
\vskip.1truein\noindent
[4] H.\ Furstenberg, {\it Recurrence in Ergodic Theory and Combinatorial
Number Theory.}\ Princeton: Princeton University Press 1981    
\vskip.1truein\noindent
[5] B.\ Gr\"unbaum and G.C.\ Shephard, {\it Tilings and Patterns},
Freeman, New York, 1986.
\vskip.1truein\noindent
[6] S.\ Mozes, Tilings, substitution systems and dynamical systems
generated by them, {\it J. d'Analyse Math.}\ 53 (1989), 139-186.
\vskip.1truein\noindent
[7] R.\ Penrose, The role of aesthetics in pure and applied mathematical
research, {\it Bull.\ Inst.\ Math.\ Appl.}\ 10 (1974), 266-271.
\vskip.1truein\noindent
[8] J.\ Peyri\`ere, Frequency of patterns in certain graphs and in Penrose
tilings, {\it J.\ Physique (Paris) Coll.\ C3}, 47 (1986), 41-62.
\vskip.1truein\noindent
[9] C.\ Radin, Tiling, periodicity and crystals, {\it J. Math.\ Phys.}
26 (1985), 1342-1344.
\vskip.1truein\noindent
[10] C.\ Radin, Correlations in classical ground states. {\it J.\ Stat.\ 
Phys.}\ 43 (1986), 707-712.
\vskip.1truein\noindent
[11] C.\ Radin, Disordered ground states of classical lattice models, 
{\it Revs.\ Math.\ Phys.}\ 3 (1991), 125-135.
\vskip.1truein\noindent
[12] C.\ Radin, ``Global order from local sources'', to appear in October,
1991 issue of {\it Bull.\ Amer.\ Math.\ Soc}.
\vskip.1truein\noindent
[13] H.\ Royden, {\it Real Analysis}, 2$^{nd}$ ed.\ , MacMillan, New York, 
1968, pps.\ 163, 149.
\vskip.1truein\noindent
[14] M.\ Senechal and J.\ Taylor, Quasicrystals: The view from Les Houches,
{\it Math.\ Intelligencer} 12 (1990), 54-64. 
\vskip.1truein\noindent
[15] H.\ Wang, Dominoes and the AEA case of the decision problem,
{\it Mathematical Theory of Automata}, ed. Jerome Fox, Polytechnic
Press, New York, 1963, 23-56.
\vskip.1truein\noindent
[16] H.\ Wang, Proving theorems by pattern recognition II., {\it Bell 
Systs.\ Tech.\ J.}\ 40 (1961), 1-41.
\vskip.1truein\noindent
[17] H.\ Wang, Notes on a class of tiling problems, {\it Fund.\ Math.}\ 82 
(1975), 295-305.
\vskip.1truein\noindent
[18] H.\ Wang, {\it Computation, Logic, Philosophy: A Collection of Essays},
Kluwer Academic Pub., Dodrecht, 1990.

\end