%tile.tex

\input amstex

\documentstyle{amsppt}

\magnification=\magstep1
\hcorrection{.25in}
\advance\vsize-.75in

\define \PP{\Cal P}
\define \ZZ{\Bbb Z}
\define \WW{\Cal W}
\define \nneg{nonnegative}
\define \st{such that}
\define \si{\sigma}
\define \sft{shift of finite type}
\define \ts{tiling system}
\define \pro{prototile}


\NoBlackBoxes



\topmatter

\title      The Symbolic Dynamics of Tiling the Integers \endtitle



\author Ethan M. Coven\\William Geller\\Sylvia Silberger\\William Thurston
\endauthor

\address Department of Mathematics,
         Wesleyan University,
         Middletown, CT  06459-0128                       \endaddress
\email   ecoven\@wesleyan.edu                              \endemail
\address Department of Mathematics,
         Indiana University-Purdue University at Indianapolis,
         Indianapolis, IN 46202-3216                          \endaddress
\email   wgeller\@math.iupui.edu 								                     \endemail
\address Department of Mathematics,
         Lafayette College,
         Easton, PA 18042                                     \endaddress
\curraddr  Department of Mathematics,
           Hofstra University,
           Hempstead, NY 11549                                \endcurraddr

\email    silbergs\@lafayette.edu                                      \endemail
\address Department of Mathematics,
         University of California Davis,
         Davis, CA 95616                                   \endaddress
\email   wpt\@math.ucdavis.edu                            \endemail

\thanks
Some of this work was done at the Mathematical Sciences Research Institute
(MSRI), where research
is supported in part by NSF grant DMS-9701755.  The first two authors thank
K.~Schmidt for useful conversations
and ideas.
\endthanks

\leftheadtext{E. COVEN, W.GELLER, S. SILBERGER, AND W. THURSTON}




\subjclass Primary 58F03 \endsubjclass


\abstract
{A finite collection~$\PP$ of finite sets {\it tiles the integers\/} iff
the integers can be expressed as a
disjoint union of translates of members of $\PP$.  We associate with such a
tiling a doubly infinite sequence with
entries from~$\PP$.  The set of all such sequences is a sofic system,
called a {\it tiling system}.  We show that,
up to powers of the shift, every shift of finite type can be realized as a
tiling system.}
\endabstract









\endtopmatter

\document

\head 1. Introduction   \endhead

For notation, terminology, and basic results of symbolic dynamics,
see the book by D.~Lind and B.~Marcus \cite{LM}.

Let $\PP = \{P_1,\dots, P_K\}$
be a finite collection of
finite subsets of the integers $\ZZ = \{\dots,-1,0,1,\dots\}$,
called {\it prototiles}.
We normalize the \pro s so that each has minimum~$0$.
A {\it tile\/} is a translate of a prototile.
A {\it tiling of the integers\/} by~$\PP$ is an expression of the integers
as a disjoint union
of tiles,
$\ZZ = \bigcup(t_j + P_{k_j})$.
Corresponding to this tiling is the point
$x = (x_i) \in \prod_{i=-\infty}^{\infty} \{1,2,\dots,K\}$
defined  by
$x_i = k$ if and only if there exists~$j$ such that
$i \in t_j + P_{k_j}$ and  $k_j = k$.
Thus we can think of a tiling as being given by a bi-infinite sequence of
colors,
where the colors are in one-to-one correspondence with the prototiles.

Let $\si$ denote the {\it shift}, $\left(\sigma(x)\right)_i = x_{i+1}$.
The collection of points corresponding to tilings of the integers by~$\PP$,
denoted~$T(\PP)$,
is closed and shift-invariant.
We call $\si: T(\PP) \to T(\PP)$ a {\it tiling system}.
We first show that every tiling system is sofic.
We then prove our main result: up to powers of the shift, every  shift of
finite type can be realized as a tiling system.

\proclaim{Main Theorem} Let $\si:\Sigma \to \Sigma$ be a  shift of finite
type.  Then there is a positive integer~$m$ and a tiling system
$\si: T \to T$ \st
 \roster
  \item $T = T_0 \cup T_1 \cup \dots \cup T_{m-1}$,
        where the ~$T_i$ are closed and cyclically permuted by the shift~$\si$.
  \item $\si^m : \Sigma \to \Sigma$ is topologically conjugate to every
$\si^m : T_i \to T_i$.
 \endroster
\endproclaim

\proclaim{Corollary}
The set of topological entropies of \ts s   is the same as that of  shifts
of finite
type, i@.e@., the set of logarithms of roots of Perron numbers.
\endproclaim

\remark{Remark}
In the sequel we will sometimes, as is common in symbolic dynamics, call
the space~$T$ a tiling system, the
space~$\Sigma$ a shift of finite type, etc.
\endremark





\head 2. Tiling systems are sofic  \endhead

Consider the following three examples.
\smallskip
\noindent (1) $\PP = \{\{0\},\{0,1\}\}$.
It is more convenient to think of~$\PP$ as~$\{R,BB\}$,  ($R$ = red, $B$ = blue).
Then $T(\PP)$ is the set of all bi-infinite indexed concatenations
of~$R$ and~$B$
such that between any two consecutive occurrences of~$R$ there is an even
number of~$B$'s,
the well-known  even system.
In this case $T(\PP)$ is also a renewal system, although we do not use that
fact here.
Recall that a {\it renewal system\/} is the collection of indexed
bi-infinite sequences
which are concatenations of a finite set of finite words from some alphabet.
In the sequel, we shall abuse notation and write $T(R,BB)$ in place of~
$T(\left\{\{0\},\{0,1\}\right\})$.


\smallskip

\noindent (2) $\PP = \{\{0\},\{0,2\}\}$, which we replace by~$\{R, B\ \_\ B\}$.
Then $T(\PP)$ is the renewal system generated by words
$R, BRB$, and~$BBBB$.

\smallskip

\noindent (3) $\PP = \{R,BB\ \_\ B,Y\_\ \_\ Y\}$,
i.e., $ \left\{\{0\},\{0,1,3\},\{0,3\}\right\}$.
In this case
$T(\PP)$ is not a renewal system.


\medskip




To  show that every tiling system is sofic, recall the proof that the even
system
$\si : T(R,BB) \to T(R,BB)$ is sofic ---
it is the image of the
\sft\ $\si : \widetilde T(R_1,B_1B_2) \to \widetilde T(R_1,B_1B_2)$
under the ``drop the subscripts'' map.
Here $\widetilde T(R_1,B_1B_2)$ is the set of all bi-infinite indexed
concatenations of ~$R_1$ and~$B_1B_2$.
We show that every ``subscripted \ts'' is a \sft.
Clearly every \ts\ can be obtained from a subscripted \ts\
by dropping the subscripts.

Formally, let $\PP = \{P_1,\dots,P_K\}$ be a finite collection of
prototiles.
 Write
$$P_k = \{0 = p_{k,1}  < p_{k,2} < \dots < p_{k,\ell_k}\}$$
and define
$\widetilde T = \widetilde T(\PP)$
on alphabet
$\{(k,\ell): 1 \le k \le K, 1 \le \ell \le \ell_k\}$,
by
$x \in \widetilde T$ iff there is a tiling of the integers by members of $\PP$,
$\ZZ = \bigcup (t_j + P_{k_j})$,
\st\ for every~$i$, there exist $j = j(i)$ and~$\ell = \ell(i)$ \st\
$i \in t_j + P_{k_j}$  and  $x_i = (k_j,\ell)$.
Equivalently, $x \in \prod \{(k,\ell): 1 \le k \le K, 1 \le \ell \le \ell_k\}$
is in~$\widetilde T$ if and only if for every~$i$, $x_i = (k,\ell)$
and $1 \le \ell' \le \ell_k$ imply
$x_{i + p_{k,\ell'} - p_{k,\ell}} = (k,\ell')$.
Informally, if $x_i$ is an element of a tile, then the other elements of that
tile appear in the appropriate places of~$x$.


The following result was proved in conversations with K.~Schmidt in Warwick
in~1994.

\proclaim{Theorem}
Every ``subscripted \ts'' is a \sft.
\endproclaim

\demo{Proof}
Let $L$ be the length  of a longest prototile in~$\PP$.  (For example, $B\
\_\ B$ has
length~$3$.)  We show that $\widetilde T = \widetilde T(\PP)$ is a \sft\
by showing that if
$x \in \prod \{(k,\ell)\}$
%: 1 \le k \le K, 1 \le \ell \le \ell_k\}$,
and every solid $L$@-word which appears in ~$x$
appears in some point of ~$\widetilde T$, then $x \in \widetilde T$.



Suppose that
every solid $L$@-word which appears in~$x$
appears in some $y \in \widetilde T$.
Let $x_i = (k,\ell)$.
Since $p_{k,\ell_k} + 1 \le L$,
there exists $y \in \widetilde T$ such that
$$    y_{i-p_{k,\ell}},\dots, y_{i-p_{k,\ell}+p_{k,\ell_k}}=
      x_{i-p_{k,\ell}},\dots, x_{i-p_{k,\ell}+p_{k,\ell_k}}.
$$
But $y \in \widetilde T$ and $y_i = (k,\ell)$, so
$y_{i-p_{k,\ell}+p_{k,\ell'}} = (k,\ell')$ for $1 \le \ell' \le \ell_k$.
Hence $x \in \widetilde T$.


Informally, suppose that every solid $L$@-word which appears in ~$x$
appears in a subscripted tiling.  Since no tile is longer than~$L$, if~$x_i$
is an element of a tile, then the other elements of that tile appear in the
appropriate places of~$x$.  Therefore $x \in  \widetilde T$.
\qed
\enddemo

\proclaim{Corollary}
Every tiling system is sofic.
\endproclaim

\remark{Remark}
We cannot use $L-1$ in the proof of the theorem.
Again let $\PP = \{R,BB\}$,
so $\widetilde T = \widetilde T(R_1,B_1B_2)$ and $L = 2$.
Every $1$@-word appearing in $x = \dots B_1B_1B_1 \dots$
appears in some point of~$\widetilde T$, but $x \notin \widetilde T$.
\endremark

\medskip

Not every sofic system can be realized as a \ts,
 as is shown by the following

\proclaim{Proposition}
A \ts\ which has a point of period~$2$ must have at least two fixed points.
\endproclaim

\demo{Proof}
The point of period~$2$  is $\dots abab \dots$,
so there are two \pro s, each of which consists entirely of even integers
or entirely of odd
integers. Both tile the even integers and hence tile the integers.
Then both $\dots aaa \dots$ and $\dots bbb \dots$ are in the \ts.
\qed
\enddemo

Similarly, if a \ts\ has a point of period~$3$ or one of period~$4$, then
it must have
at least one fixed point.  The existence of a point of period greater
than~$4$ does not
imply the existence of a fixed point.

\head 3. The main theorem
\endhead



\proclaim{Main Theorem} Let $\si:\Sigma \to \Sigma$ be a  shift of finite
type.  Then there is a positive integer~$m$ and a tiling system
$\si: T \to T$ \st
 \roster
  \item $T = T_0 \cup T_1 \cup \dots \cup T_{m-1}$,
        where the ~$T_i$ are closed and cyclically permuted by the shift~$\si$.
  \item $\si^m : \Sigma \to \Sigma$ is topologically conjugate to every
$\si^m : T_i \to T_i$.
 \endroster
\endproclaim

\demo{Proof}
We may assume that $\Sigma = \Sigma_A$, the edge shift determined by a
matrix~$A$
with nonnegative integer entries.
$A$ is the adjacency matrix of a directed graph~$G$.
The alphabet of~$\Sigma_A$ is the set of arcs (directed edges)
 of~$G$ and
$x = (x_i) \in  \Sigma_A$ if and only if
for every~$i$,
the terminal vertex of~$x_i$ is the initial vertex of ~$x_{i+1}$.

For every positive integer~$m$, $\si^m : \Sigma_A \to \Sigma_A$ is
topologically conjugate to $\si : \Sigma_{A^m} \to \Sigma_{A^m}$.
We find a tiling system
$\si : T \to T$ and a positive integer~$m$ \st\
$T = T_0 \cup T_1 \cup \dots \cup T_{m-1}$,
the $T_i$ are closed and cyclically permuted by the shift,
and $\si : \Sigma_{A^m} \to \Sigma_{A^m}$
is  topologically conjugate to $\si^m : T_0 \to T_0$.
Hence  $\si^m : \Sigma_A \to \Sigma_A$ is
topologically conjugate to every $\si^m :T_i \to T_i$.



Suppose that $A$ is $V \times V$.
Choose $n > V$ so that
$$( V\max A_{ij})^{13n} < (n+1)!$$
Let $m = 13n$. Then
every entry of~$A^m =A^{13n}$ can be written (uniquely) as
$$c_1(1!) + c_2(2!) + \dots + c_n(n!),$$
where $ 0 \le c_k \le k$ for $ 1 \le k \le n$.

 We now construct the tiling system.
The prototiles will be of two types: {\it barbells\/} and {\it racks} (to
hold barbells).
We will use the same terms for the corresponding tiles.
In the sequel we will use colors to
label prototiles.  The symbols $a,a'$ will stand for generic colors.

The barbells
are the
broken words of the form
$$a^2\ \overset \leftarrow\ 2r + 1 \ \rightarrow \to  {\_ \ \ \dots \ \
\_}\ a^2$$
for  $0 \le r \le 2n-2$.

The racks are chosen from the broken words
of the form ~$HCT$ of length~$13n + 2J$, $1 \le J
\le V$, where  the {\it head\/}  is
$$H = (a\ \_)^I a^{2n - 2I}$$
for some~$I$, $1 \le I \le V$;
the {\it tail\/}  is
$$T = (\_\ a)^J$$
for some~$J$, $ 1 \le J \le V$;
and the {\it center\/}  is
$$C=a^{3n+i}\ \overset \leftarrow 2k \rightarrow \to
{\_ \dots\_}\ a\
\overset\leftarrow 2k \rightarrow \to {\_\dots \_}
\ a^{8n-4k-1-i}$$
for some $i$ and $k$, $0 \le i \le k-1$ and $1 \le k \le n$.





Given $I,J$ with $1 \le I,J \le V$, write
$$(A^{13n})_{IJ} = c_1(1!) + c_2(2!) + \dots + c_n(n!),$$
where $0 \le c_k \le k$ for $1 \le k \le n$.
If $c_k \ne 0$,
 choose the racks to be the $c_k = c_k(I,J)$ broken words  of the form
$$\left[(a\ \_)^I a^{2n - 2I}\right]\left[ a^{3n+i}\ \overset \leftarrow 2k
\rightarrow \to
{\_ \dots\_}\ a\
\overset\leftarrow 2k \rightarrow \to {\_\dots \_}
\ a^{8n-4k-1-i}\right]  \left[(\_\ a)^J\right]$$
for $0 \le i \le c_k-1$.

The barbells and racks have the following properties.

\noindent $\bullet$ The head $H = (a\ \_)^I a^{2n - 2I}$ of a rack
                    can be filled by the tail $T = (\_\ a')^J$
                    of a rack
                    in a tiling
                    if and only if $I=J$.

\noindent $\bullet$  Label the blanks in the center
 																				$$C = a^{3n+i}\overset\leftarrow 2k   \rightarrow \to
{\_ \dots\_}\ a\
                       \overset\leftarrow 2k \rightarrow \to {\_\dots \_}\
a^{8n-4k-1-i}$$
                      of a rack by $\{1,2,\dots,4k\}$.
	                     Barbells can appear in a tiling only in the gaps in
the centers
                      of  racks,
                      starting only in  odd places and  straddling the ~$a$.
                      Furthermore, the blanks in this center can be tiled
by barbells
                      in exactly $k!$~ways. To see this, define a permutation
                      ~$\pi$ of $\{1,2,\dots,k\}$ by $\pi(j) = \ell$ if and
only if
                       a barbell $a'a'\ \overset \leftarrow\ 2r + 1 \
\rightarrow
                       \to {\_ \ \ \dots \ \ \_}\ a'a'$ occupies places labelled
                       $2j-1,2j,2(k+\ell)-1,2(k+\ell)$.






\noindent $\bullet$ The heads of racks can appear in a tiling starting only at
                    places which differ by multiples of~$13n$.

\medskip


Let $T$ be the tiling system with   prototiles the barbells and racks chosen
above. Then $T =T_0 \cup T_1 \cup \dots \cup
T_{13n-1}$, where $T_i$ is the set of indexed bi-infinite sequences in~$T$
in which the heads
appear starting at places congruent to~$i$ modulo~$13n$.
Thus $T_0$ consists of all indexed bi-infinite concatenations of words of
length~$13n$, of
the form $\bar H \bar C$, starting at multiples of~$13n$, where $H$ and~$C$
are the head and center of a rack, and
$\bar H$ and $\bar C$ are the solid words resulting from
filling them in a tiling.
Recall that if $H = (a\ \_)^I a^{2n - 2I}$,
then it must be filled by a tail
$T = (\_\ a')^I$.
$C$ can be filled only by barbells.

Define an edge shift as follows.
Let $G'$ be the directed graph with
vertices $1,2,\dots,V$,
and an arc from~$I$ to~$J$ for each rack
with head $(a\ \_)^I a^{2n - 2I}$,
tail $(\_\ a)^J$,
and center tiled by barbells.
There are $(A^{13n})_{IJ}$ arcs from~$I$ to ~$J$,
and an arc with head $(a\ \_)^I a^{2n - 2I}$
can follow an arc with tail $(\_\ a')^J$
if and only if $I=J$.
Therefore since $m = 13n$, the adjacency matrix of~$G'$ is~$A^m$
and $\si^m : T_0 \to T_0$
is  topologically conjugate to
$\si : \Sigma_{A^m} \to \Sigma_{A^m}$,
which in turn is topologically conjugate to
$\si^m : \Sigma_A \to \Sigma_A$.
\qed
\enddemo






\proclaim{Corollary}
The set of topological entropies of \ts s   is the same as that of  shifts
of finite
type, i@.e@., the set of logarithms of roots of Perron numbers.
\endproclaim


\Refs
\widestnumber\key{LM}

\ref
 \key LM
 \by    D. Lind and B. Marcus
 \book  An introduction to symbolic dynamics and coding
 \publ  Cambridge University Press
 \publaddr Cambridge
 \yr    1995
\endref


\endRefs


\vfil\eject

\enddocument


