10 1. BASIC NOTIONS tilings, pseudo-self-similar tilings, and (pseudo) self-aﬃne tilings. One di- mensional examples include the Thue-Morse and Fibonacci tilings (see Fig- ure 1.6), and the period-doubling tiling. Two dimensional examples include the chair tiling, the “table” or “domino” tiling, the half-hex, the Penrose tiling, and the pinwheel tiling. Most of the examples in this book will be substitution tilings. Our second class of tilings also goes by many names. Cut-and-project tilings are closely related to model sets, to canonical projection tilings, and to diffractive sets. Examples include the Fibonacci tiling in one dimension, the Penrose and octagonal tilings in two dimensions, and the icosahedral tiling in three dimensions. This class of tilings overlaps with the substitution tilings, but neither is a subset of the other. There are plenty of substitution tilings that are not cut-and-project, and plenty of cut-and-project tilings that do not come from a substitution. The third class of tilings are those defined by local matching rules. Imag- ine being given a box of tiles and having to tile the plane in any manner that fits. The tilings that result form a space that may or may not be the hull of a single tiling. Substitutions in one dimension. To understand substitution tilings, we begin in one dimension. Pick a finite set (or “alphabet”) A, whose el- ements are called “letters”. For instance, we might take A = {a, b}. A sequence of letters is called a “word”. We associate a word to each letter. (E.g., in the Thue-Morse tiling we associate a → ab, b → ba.) The substitu- tion σ maps words to words, replacing each letter with its associated word. For instance, the Thue-Morse substitution has σ(abbab) = abbabaabba. Definition. The substitution matrix M keeps track of the populations of different letters, with Mij equaling the number of times that the i-th letter appears in σ(j-th letter). For example, the Thue-Morse substitution has M = ( 1 1 1 1 ). In general, (M n )ij is the number of times that the i-th letter appears in σn(j-th letter). Definition. A (substitution) matrix M is primitive if there is a positive integer n such that every entry of M n is positive. Equivalently, there is an n such that σn(any letter) contains every letter at least once. In such cases we will say that σ is a primitive substitution. Theorem 1.2 (Perron-Frobenius). Let M be a primitive matrix, and let λP F be its largest positive real eigenvalue (sometimes called the Perron- Frobenius eigenvalue). This eigenvalue has multiplicity one, and the corre- sponding right- and left-eigenvectors have strictly positive entries. All other eigenvalues have norm strictly less than λP F . For Thue-Morse, λP F = 2, the left-eigenvector is L = (L1, L2) = (1, 1), and the right-eigenvector is R = ( R1 R2 ) = ( 1 1 ) .

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2008 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.