# The Symbolic Dynamics of Tiling the Integers

## 1. Introduction

For notation, terminology, and basic results of symbolic dynamics, see the book by D. Lind and B. Marcus \[LM\].

Let $`𝒫=\{P_1,\mathrm{},P_K\}`$ be a finite collection of finite subsets of the integers $`=\{\mathrm{},1,0,1,\mathrm{}\}`$, called prototiles. We normalize the prototiles so that each has minimum $`0`$. A tile is a translate of a prototile. A tiling of the integers by $`𝒫`$ is an expression of the integers as a disjoint union of tiles, $`=(t_j+P_{k_j})`$. Corresponding to this tiling is the point $`x=(x_i)_{i=\mathrm{}}^{\mathrm{}}\{1,2,\mathrm{},K\}`$ defined by $`x_i=k`$ if and only if there exists $`j`$ such that $`it_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 $`\sigma `$ denote the shift, $`\left(\sigma (x)\right)_i=x_{i+1}`$. The collection of points corresponding to tilings of the integers by $`𝒫`$, denoted $`T(𝒫)`$, is closed and shift-invariant. We call $`\sigma :T(𝒫)T(𝒫)`$ a 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.

###### Main Theorem

Let $`\sigma :\mathrm{\Sigma }\mathrm{\Sigma }`$ be a shift of finite type. Then there is a positive integer $`m`$ and a tiling system $`\sigma :TT`$ such that

###### Corollary

The set of topological entropies of tiling systems is the same as that of shifts of finite type, i@.e@., the set of logarithms of roots of Perron numbers.

###### Remark Remark

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

## 2. Tiling systems are sofic

Consider the following three examples. (1) $`𝒫=\{\{0\},\{0,1\}\}`$. It is more convenient to think of $`𝒫`$ as $`\{R,BB\}`$, ($`R`$ = red, $`B`$ = blue). Then $`T(𝒫)`$ 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(𝒫)`$ is also a renewal system, although we do not use that fact here. Recall that a 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(\{\{0\},\{0,1\}\})`$.

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

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

To show that every tiling system is sofic, recall the proof that the even system $`\sigma :T(R,BB)T(R,BB)`$ is sofic — it is the image of the shift of finite type $`\sigma :\stackrel{~}{T}(R_1,B_1B_2)\stackrel{~}{T}(R_1,B_1B_2)`$ under the “drop the subscripts” map. Here $`\stackrel{~}{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 tiling system” is a shift of finite type. Clearly every tiling system can be obtained from a subscripted tiling system by dropping the subscripts.

Formally, let $`𝒫=\{P_1,\mathrm{},P_K\}`$ be a finite collection of prototiles. Write

$$P_k=\{0=p_{k,1}<p_{k,2}<\mathrm{}<p_{k,\mathrm{}_k}\}$$

and define $`\stackrel{~}{T}=\stackrel{~}{T}(𝒫)`$ on alphabet $`\{(k,\mathrm{}):1kK,1\mathrm{}\mathrm{}_k\}`$, by $`x\stackrel{~}{T}`$ iff there is a tiling of the integers by members of $`𝒫`$, $`=(t_j+P_{k_j})`$, such that for every $`i`$, there exist $`j=j(i)`$ and $`\mathrm{}=\mathrm{}(i)`$ such that $`it_j+P_{k_j}`$ and $`x_i=(k_j,\mathrm{})`$. Equivalently, $`x\{(k,\mathrm{}):1kK,1\mathrm{}\mathrm{}_k\}`$ is in $`\stackrel{~}{T}`$ if and only if for every $`i`$, $`x_i=(k,\mathrm{})`$ and $`1\mathrm{}^{}\mathrm{}_k`$ imply $`x_{i+p_{k,\mathrm{}^{}}p_{k,\mathrm{}}}=(k,\mathrm{}^{})`$. 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.

###### Theorem

Every “subscripted tiling system” is a shift of finite type.

###### Demonstration Proof

Let $`L`$ be the length of a longest prototile in $`𝒫`$. (For example, $`B\mathrm{\_}B`$ has length $`3`$.) We show that $`\stackrel{~}{T}=\stackrel{~}{T}(𝒫)`$ is a shift of finite type by showing that if $`x\{(k,\mathrm{})\}`$ and every solid $`L`$@-word which appears in $`x`$ appears in some point of $`\stackrel{~}{T}`$, then $`x\stackrel{~}{T}`$.

Suppose that every solid $`L`$@-word which appears in $`x`$ appears in some $`y\stackrel{~}{T}`$. Let $`x_i=(k,\mathrm{})`$. Since $`p_{k,\mathrm{}_k}+1L`$, there exists $`y\stackrel{~}{T}`$ such that

$$y_{ip_{k,\mathrm{}}},\mathrm{},y_{ip_{k,\mathrm{}}+p_{k,\mathrm{}_k}}=x_{ip_{k,\mathrm{}}},\mathrm{},x_{ip_{k,\mathrm{}}+p_{k,\mathrm{}_k}}.$$

But $`y\stackrel{~}{T}`$ and $`y_i=(k,\mathrm{})`$, so $`y_{ip_{k,\mathrm{}}+p_{k,\mathrm{}^{}}}=(k,\mathrm{}^{})`$ for $`1\mathrm{}^{}\mathrm{}_k`$. Hence $`x\stackrel{~}{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\stackrel{~}{T}`$. ∎

###### Corollary

Every tiling system is sofic.

###### Remark Remark

We cannot use $`L1`$ in the proof of the theorem. Again let $`𝒫=\{R,BB\}`$, so $`\stackrel{~}{T}=\stackrel{~}{T}(R_1,B_1B_2)`$ and $`L=2`$. Every $`1`$@-word appearing in $`x=\mathrm{}B_1B_1B_1\mathrm{}`$ appears in some point of $`\stackrel{~}{T}`$, but $`x\stackrel{~}{T}`$.

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

###### Proposition

A tiling system which has a point of period $`2`$ must have at least two fixed points.

###### Demonstration Proof

The point of period $`2`$ is $`\mathrm{}abab\mathrm{}`$, so there are two prototiles, 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 $`\mathrm{}aaa\mathrm{}`$ and $`\mathrm{}bbb\mathrm{}`$ are in the tiling system. ∎

Similarly, if a tiling system 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.

## 3. The main theorem

###### Main Theorem

Let $`\sigma :\mathrm{\Sigma }\mathrm{\Sigma }`$ be a shift of finite type. Then there is a positive integer $`m`$ and a tiling system $`\sigma :TT`$ such that

###### Demonstration Proof

We may assume that $`\mathrm{\Sigma }=\mathrm{\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 $`\mathrm{\Sigma }_A`$ is the set of arcs (directed edges) of $`G`$ and $`x=(x_i)\mathrm{\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`$, $`\sigma ^m:\mathrm{\Sigma }_A\mathrm{\Sigma }_A`$ is topologically conjugate to $`\sigma :\mathrm{\Sigma }_{A^m}\mathrm{\Sigma }_{A^m}`$. We find a tiling system $`\sigma :TT`$ and a positive integer $`m`$ such that $`T=T_0T_1\mathrm{}T_{m1}`$, the $`T_i`$ are closed and cyclically permuted by the shift, and $`\sigma :\mathrm{\Sigma }_{A^m}\mathrm{\Sigma }_{A^m}`$ is topologically conjugate to $`\sigma ^m:T_0T_0`$. Hence $`\sigma ^m:\mathrm{\Sigma }_A\mathrm{\Sigma }_A`$ is topologically conjugate to every $`\sigma ^m:T_iT_i`$.

Suppose that $`A`$ is $`V\times V`$. Choose $`n>V`$ so that

$$(V\mathrm{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!)+\mathrm{}+c_n(n!),$$

where $`0c_kk`$ for $`1kn`$.

We now construct the tiling system. The prototiles will be of two types: barbells and 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\stackrel{2r+1}{\mathrm{\_}\mathrm{}\mathrm{\_}}a^2$$

for $`0r2n2`$.

The racks are chosen from the broken words of the form $`HCT`$ of length $`13n+2J`$, $`1JV`$, where the head is

$$H=(a\mathrm{\_})^Ia^{2n2I}$$

for some $`I`$, $`1IV`$; the tail is

$$T=(\mathrm{\_}a)^J$$

for some $`J`$, $`1JV`$; and the center is

$$C=a^{3n+i}\stackrel{2k}{\mathrm{\_}\mathrm{}\mathrm{\_}}a\stackrel{2k}{\mathrm{\_}\mathrm{}\mathrm{\_}}a^{8n4k1i}$$

for some $`i`$ and $`k`$, $`0ik1`$ and $`1kn`$.

Given $`I,J`$ with $`1I,JV`$, write

$$(A^{13n})_{IJ}=c_1(1!)+c_2(2!)+\mathrm{}+c_n(n!),$$

where $`0c_kk`$ for $`1kn`$. If $`c_k0`$, choose the racks to be the $`c_k=c_k(I,J)`$ broken words of the form

$$\left[(a\mathrm{\_})^Ia^{2n2I}\right]\left[a^{3n+i}\stackrel{2k}{\mathrm{\_}\mathrm{}\mathrm{\_}}a\stackrel{2k}{\mathrm{\_}\mathrm{}\mathrm{\_}}a^{8n4k1i}\right]\left[(\mathrm{\_}a)^J\right]$$

for $`0ic_k1`$.

The barbells and racks have the following properties.

$``$ The head $`H=(a\mathrm{\_})^Ia^{2n2I}`$ of a rack can be filled by the tail $`T=(\mathrm{\_}a^{})^J`$ of a rack in a tiling if and only if $`I=J`$.

$``$ Label the blanks in the center

$$C=a^{3n+i}\stackrel{2k}{\mathrm{\_}\mathrm{}\mathrm{\_}}a\stackrel{2k}{\mathrm{\_}\mathrm{}\mathrm{\_}}a^{8n4k1i}$$

of a rack by $`\{1,2,\mathrm{},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,\mathrm{},k\}`$ by $`\pi (j)=\mathrm{}`$ if and only if a barbell $`a^{}a^{}\stackrel{2r+1}{\mathrm{\_}\mathrm{}\mathrm{\_}}a^{}a^{}`$ occupies places labelled $`2j1,2j,2(k+\mathrm{})1,2(k+\mathrm{})`$.

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

Let $`T`$ be the tiling system with prototiles the barbells and racks chosen above. Then $`T=T_0T_1\mathrm{}T_{13n1}`$, 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 $`\overline{H}\overline{C}`$, starting at multiples of $`13n`$, where $`H`$ and $`C`$ are the head and center of a rack, and $`\overline{H}`$ and $`\overline{C}`$ are the solid words resulting from filling them in a tiling. Recall that if $`H=(a\mathrm{\_})^Ia^{2n2I}`$, then it must be filled by a tail $`T=(\mathrm{\_}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,\mathrm{},V`$, and an arc from $`I`$ to $`J`$ for each rack with head $`(a\mathrm{\_})^Ia^{2n2I}`$, tail $`(\mathrm{\_}a)^J`$, and center tiled by barbells. There are $`(A^{13n})_{IJ}`$ arcs from $`I`$ to $`J`$, and an arc with head $`(a\mathrm{\_})^Ia^{2n2I}`$ can follow an arc with tail $`(\mathrm{\_}a^{})^J`$ if and only if $`I=J`$. Therefore since $`m=13n`$, the adjacency matrix of $`G^{}`$ is $`A^m`$ and $`\sigma ^m:T_0T_0`$ is topologically conjugate to $`\sigma :\mathrm{\Sigma }_{A^m}\mathrm{\Sigma }_{A^m}`$, which in turn is topologically conjugate to $`\sigma ^m:\mathrm{\Sigma }_A\mathrm{\Sigma }_A`$. ∎

###### Corollary

The set of topological entropies of tiling systems is the same as that of shifts of finite type, i@.e@., the set of logarithms of roots of Perron numbers.