THE SYMBOLIC DYNAMICS OF TILING THE INTEGERS

Ethan M. Coven William Geller Sylvia Silberger William Thurston

Abstract. A finite collection P of finite sets tiles the integers iff the integers can be expressed as a disjoint union of translates of members of P. We associate with such a tiling a doubly infinite sequence with entries from P. The set of all such sequences is a sofic system, called a tiling system. We show that, up to powers of the shift, every shift of finite type can be realized as a tiling system.

1. Introduction

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

Let P = {P_{1}, …, P_{K}} be a finite collection of finite subsets of the integers ℤ = {…, −1, 0, 1, … }, 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 P 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=−∞}^{∞}{1, 2, …, K} defined by x_{i} = k if and only if there exists j such that i ∈ 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 σ denote the shift, (σ(x))_{i} = x_{i+1}. The collection of points corresponding to tilings of the integers by P, denoted T (P), is closed and shift-invariant. We call σ : T (P) → T (P) 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.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 58F03.

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.

Main Theorem. Let σ : Σ → Σ be a shift of finite type. Then there is a positive integer m and a tiling system σ : T → T such that

(1) T = T_{0} ∪ T_{1} ∪ ⋯ ∪ T_{m−1}, where the T_{i} are closed and cyclically permuted by the shift σ.

(2) σ^{m} : Σ → Σ is topologically conjugate to every σ^{m} : T_{i} → T_{i}.

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. In the sequel we will sometimes, as is common in symbolic dynamics, call the space T a tiling system, the space Σ a shift of finite type, etc.

2. Tiling systems are sofic

Consider the following three examples.

(1) P = {{0}, {0, 1}}. It is more convenient to think of P as {R, BB}, (R = red, B = blue). Then T (P) 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 (P) 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) P = {{0}, {0, 2}}, which we replace by {R, B B}. Then T (P) is the renewal system generated by words R, BRB, and BBBB.

(3) P = {R, BB B, Y Y }, i.e., {{0}, {0, 1, 3}, {0, 3}}. In this case T (P) is not a renewal system.

To show that every tiling system is sofic, recall the proof that the even system σ : T (R, BB) → T (R, BB) is sofic — it is the image of the shift of finite type σ : T̃(R_{1}, B_{1}B_{2}) → T̃(R_{1}, B_{1}B_{2}) under the “drop the subscripts” map. Here T̃(R_{1}, B_{1}B_{2}) is the set of all bi-infinite indexed concatenations of R_{1} and B_{1}B_{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 = {P_{1}, …, P_{K}} be a finite collection of prototiles. Write

P_{k} = {0 = p_{k,1} < p_{k,2} < ⋯ < p_{k,ℓ_{k}}}

and define T̃ = T̃(P) on alphabet {(k, ℓ) : 1 ≤ k ≤ K, 1 ≤ ℓ ≤ ℓ_{k}}, by x ∈ T̃ iff there is a tiling of the integers by members of P, ℤ = ⋃(t_{j} + P_{k_{j}}), such that for every i, there exist j = j(i) and ℓ = ℓ(i) such that i ∈ t_{j} + P_{k_{j}} and x_{i} = (k_{j}, ℓ). Equivalently, x ∈ ∏{(k, ℓ) : 1 ≤ k ≤ K, 1 ≤ ℓ ≤ ℓ_{k}} is in T̃ if and only if for every i, x_{i} = (k, ℓ) and 1 ≤ ℓ′ ≤ ℓ_{k} imply x_{i+p_{k,ℓ′} −p_{k,ℓ}} = (k, ℓ′). 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.

Proof. Let L be the length of a longest prototile in P. (For example, B B has length 3.) We show that T̃ = T̃(P) is a shift of finite type by showing that if x ∈ ∏{(k, ℓ)} and every solid L-word which appears in x appears in some point of T̃, then x ∈ T̃.

Suppose that every solid L-word which appears in x appears in some y ∈ T̃. Let x_{i} = (k, ℓ). Since p_{k,ℓ_{k}} + 1 ≤ L, there exists y ∈ T̃ such that

y_{i−p_{k,ℓ}}, …, y_{i−p_{k,ℓ}+p_{k,ℓ_{k}}} = x_{i−p_{k,ℓ}}, …, x_{i−p_{k,ℓ}+p_{k,ℓ_{k}}} .

But y ∈ T̃ and y_{i} = (k, ℓ), so y_{i−p_{k,ℓ}+p_{k,ℓ′}} = (k, ℓ′) for 1 ≤ ℓ′ ≤ ℓ_{k}. Hence x ∈ 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 ∈ T̃. □

Corollary. Every tiling system is sofic.

Remark. We cannot use L−1 in the proof of the theorem. Again let P = {R, BB}, so T̃ = T̃(R_{1}, B_{1}B_{2}) and L = 2. Every 1-word appearing in x = … B_{1}B_{1}B_{1} … appears in some point of T̃, but x ∉ 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.

Proof. The point of period 2 is … abab …, 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 … aaa … and … bbb … 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 σ : Σ → Σ be a shift of finite type. Then there is a positive integer m and a tiling system σ : T → T such that

(1) T = T_{0} ∪ T_{1} ∪ ⋯ ∪ T_{m−1}, where the T_{i} are closed and cyclically permuted by the shift σ.

(2) σ^{m} : Σ → Σ is topologically conjugate to every σ^{m} : T_{i} → T_{i}.

Proof. We may assume that Σ = Σ_{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 Σ_{A} is the set of arcs (directed edges) of G and x = (x_{i}) ∈ Σ_{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, σ^{m} : Σ_{A} → Σ_{A} is topologically conjugate to σ : Σ_{A^{m}} → Σ_{A^{m}}. We find a tiling system σ : T → T and a positive integer m such that T = T_{0} ∪T_{1} ∪⋯∪T_{m−1}, the T_{i} are closed and cyclically permuted by the shift, and σ : Σ_{A^{m}} → Σ_{A^{m}} is topologically conjugate to σ^{m} : T_{0} → T_{0}. Hence σ^{m} : Σ_{A} → Σ_{A} is topologically conjugate to every σ^{m} : T_{i} → T_{i}.

Suppose that A is V × 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!) + ⋯ + c_{n}(n!),

where 0 ≤ c_{k} ≤ k for 1 ≤ k ≤ n.

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} …^{← 2r+1 →} a^{2}

for 0 ≤ r ≤ 2n − 2.

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

H = (a )^{I}a^{2n−2I}

for some I, 1 ≤ I ≤ V; the tail is

T = ( a)^{J}

for some J, 1 ≤ J ≤ V; and the center is

C = a^{3n+i} …^{←2k→} a …^{←2k→} a^{8n−4k−1−i}

for some i and k, 0 ≤ i ≤ k − 1 and 1 ≤ k ≤ n.

Given I, J with 1 ≤ I, J ≤ V, write

(A^{13n})_{IJ} = c_{1}(1!) + c_{2}(2!) + ⋯ + c_{n}(n!),

where 0 ≤ c_{k} ≤ k for 1 ≤ k ≤ n. If c_{k} ≠ 0, choose the racks to be the c_{k} = c_{k}(I, J) broken words of the form

[(a )^{I}a^{2n−2I}] [a^{3n+i} …^{←2k→} a …^{←2k→} a^{8n−4k−1−i}] [( a)^{J}]

for 0 ≤ i ≤ c_{k} − 1.

The barbells and racks have the following properties.

• 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.

• Label the blanks in the center

C = a^{3n+i} …^{←2k→} a …^{←2k→} a^{8n−4k−1−i}

of a rack by {1, 2, …, 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 π of {1, 2, …, k} by π(j) = ℓ if and only if a barbell a′a′ …^{← 2r+1 →} a′a′ occupies places labelled 2j − 1, 2j, 2(k + ℓ) − 1, 2(k + ℓ).

• 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_{0} ∪ T_{1} ∪ ⋯ ∪ 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 H̄C̄, starting at multiples of 13n, where H and C are the head and center of a rack, and H̄ and 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, …, 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 σ^{m} : T_{0} → T_{0} is topologically conjugate to σ : Σ_{A^{m}} → Σ_{A^{m}}, which in turn is topologically conjugate to σ^{m} : Σ_{A} → Σ_{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.

References

[LM] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995.

Department of Mathematics, Wesleyan University, Middletown, CT 06459-0128

E-mail address: ecoven@wesleyan.edu

Department of Mathematics, Indiana University-Purdue University at Indianapolis, Indianapolis, IN 46202-3216

E-mail address: wgeller@math.iupui.edu

Department of Mathematics, Lafayette College, Easton, PA 18042 Current address: Department of Mathematics, Hofstra University, Hempstead, NY 11549

E-mail address: silbergs@lafayette.edu

Department of Mathematics, University of California Davis, Davis, CA 95616

E-mail address: wpt@math.ucdavis.edu