## Substitution

In general, even restricted to mathematics, the term substitution can have several meanings. In connection with tilings, it describes a simple but powerful method to produce tilings with many interesting properties. The main idea is to use a finite set of building blocks $\{T_1, T_2 \ldots T_m\}$ (the prototiles), an expanding linear map $Q$ (the inflation factor) and a rule, how to dissect each scaled tile $QT_i$ into copies of the original prototiles $T_1, T_2\ldots T_m$. This information can be encoded in terms of parametrized tiles and affine maps (see example below), or, more appealing, in a diagram. In our encyclopedia, we use the latter method. Essentially, from such a diagram one can extract all needed information about the substitution. An important object in this context is the substitution matrix, which contains quite a lot information about the corresponding tilings. A similar concept are symbolic substitutions. Instead of prototiles, one uses a finite alphabet $A=\{a,b,c,\ldots \}$. The substitution s is then a map from $A$ to $\mathring{A}$, the set of all finite words over $A$. Such a symbolic substitution yields sequences over $A$, which encode one-dimensional tilings: Each letter stands for an interval of a certain length. The lengths can be read off the substitution matrix.

Example: The substitution rule for the domino. There is only one prototile up to congruence , a $2 \times 1$ rectangle (resp. two prototiles up to translation, the blue rectangle and the yellow one). The inflation factor is 2, so each prototiles is blown up by a factor 2 and divided into 4 tiles as shown in the diagram. This process can be iterated: apply the rule to the four tiles simultaneously (this second iteration is also shown in the diagram), and then again to the 16 tiles and so on. In this way, we obtain larger and larger clusters. In terms of parametrized tiles and affine maps, this substitution reads as follows. First, with respect to congruence classes: Let T be the rectangle with vertices $(0,0), (1,0), (1,2), (0,2)$. Further, let $f_1(x) := R(x)+(2,0), f_2(x) := x+(0,1), f_3(x) := x+(1,1), f_4(x) := R(x)+(2,3)$, where $R$ is the rotation through 90 degrees about the origin. Then $s(T)=\{f_1(T), f_2(T), f_3(T), f_4(T) \}$. In a natural way, s extends to tiles $T+x: s(T+x) = s(T) + 2x$. In the plane, there is an obvious way how to define s via complex numbers, which can be useful for some purposes. The definition of $s$ with respect to translation classes works analoguously. Further iterations of s are written as $s^2, s^3, s^4\ldots$

A proper way to define the family of all substitution tilings belonging to a certain substitution $s$ with prototiles $T_1, T_2 \ldots T_m$ is the following. Definition: The set of substitution tilings belonging to s is the family of all tilings $T$, where every cluster in $T$ is congruent to some cluster in a super-tile sn(Ti), for appropriate n,i.

This definition coincides with other common definitions, as li-classes, or hulls, if the considered tilings are not too pathological. Again, in the above definition one may replace ‘congruent to’ with ‘translate of’, if one prefers to work with translation classes rather than with congruence classes. We should note, that there is no need to distinguish between the two concepts, if one deals with tilings where the prototiles occur only in finitely many orientations. This is true for most of the substitution tilings in the literature as well as in our encyclopedia. Counterexamples are classified here as having infinite rotations.