Glossary

Search
$p$-adic

The internal space of a cut and project scheme is required to be a locally compact Abelian group. There are not too much locally Abelian groups out there. Besides the reals, there are the fields of p-adic numbers $\mathbb{Q}_p$. Indeed, it turns out that some substitution tilings - like the chair and the sphinx - are model sets with p-adic internal spaces (In these two examples: $H=\mathbb{Q}_2 × \mathbb{Q}_2$). Others - like the Watanabe Ito Soma 8-fold tilings - are model sets with respect to products of Euclidean and p-adic internal spaces (here, $H=\mathbb{R}^2 × \mathbb{Q}_2$).

Ammann Bars

In some substitution tilings it is possible to decorate the prototiles with line segments such that they produce a grid of straight lines extending over the whole tiling. Here is an example for the case of the Penrose Rhomb tiling.

Ammann bars

These decorations are called Ammann bars, because R.Ammann discovered the appropriate decorations for the Penrose rhomb tilings, as well as for some others. In some cases, they can be used to express matching rules by requiring, that tiles have to meet in a way such that the line segments continue as straight lines across the edges of the tiling. For more details, see [GS87] .

Aperiodic

There are disputations among the experts how to define “aperiodic”. One possibility is to use it synonymously with nonperiodic. This is somehow a waste of this term. Others refer to an “aperiodic tiling” as one, which is created by an aperiodic set of tiles. This is unsatisfactory since this is rather a property of the set of prototiles than the tiling itself. Another definition is: A tiling is aperiodic, if its hull contains no periodic tiling. Personally, I like the latter definition (DF). Then a sequence $\ldots aaaaabaaaaaaa\ldots $. is not aperiodic (since its hull comtains the periodic sequence $\ldots aaaaabaaaaaaa\ldots $.), but the Fibonacci sequence is aperiodic.

Border Forcing

Every instance of a supertile has the same tiles around its boundary.

Canonical Substitution Tiling
Cluster

see patch

Corona

Given a tile $T$ in a tiling $T$, the $0$-corona of $T$ is just $C0(T)={T}$. The $n$-corona of $T (n>0)$ is $C_n(T)=\{ S \in T | S \textrm{ has nonemtpy intersection with some tile in } C_{n-1}(T) \}$. Coronae can also be defined by starting with other objects in a tiling, like coronae of clusters, edges, vertices…. rather than tiles. The $1$-corona of a vertex is also called vertex star. Sometimes the definition of a corona reads ‘$S$ shares a full edge (face, facet) with some tile…’ instead of ‘$S$ has nonempty intersection with some tile…‘.

Cut and Project

A fundamental result in the theory of nonperiodic tilings was the discovery of the fact that some substitution tilings can be obtained by projecting certain points from higher dimensional point lattices. This was first carried out by deBruijn for the Penrose Rhomb tilings [de81] . In the following years it was developed further by a lot of authors (we cannot list all of them; for a start, see the references in [Moo00] and [Fog02] ). This work culminated in the development of the algebraic theory of model sets. Quickly it was realized that this theory is a reformulation of the work of Meyer [Lag96] , [Moo97] . The ingredients for a cut and project scheme are the ‘direct space’ G, where the model set (or the tiling) lives, the internal space $H$, a lattice $L$ in $G \times H$ and a compact set $W$ - the window - in $H$. The lattice $L$ is embedded in $G \times H$ such that the projection $p_H(L)$ of $L$ to $H$ is dense, and the projection $p_G$ to $G$ is invertible on $p_G(L)$. In general, $G$ and $H$ can be choosen as locally compact Abelian groups. In many cases it suffices to choose $G$ and $H$ as Euclidean vector spaces $R^d$ (but see $p$-adic window). Then the set $W$ tells us which points of $L$ will be projected by $p_G$ to $G$: Those which are projected to $W$ by $p_H$. Under these conditions, $V = \{ p_G(x) \mid x \in L, p_H(x) \in W \}$ is a uniformly discrete and relatively dense point set in $G$, called model set. There are many variations of this construction, some of them yielding tilings rather than point sets (e.g., the Klotz construction in [KS89] ). But essentially, the construction above is the main idea behind all the variations of the theme. A simple example is visualized in the description of the Fibonacci tiling. In this example, $G=H=R$, and $W$ is an interval: the strip in the image is $W \times R$.

Danzer's 7-fold
Danzer's 7-fold
Delone Set

A point set $S$ in $\mathbb{R}^d$ is called a Delone set, if it is uniformly discrete and relatively dense; i.e., if there are numbers $R>r>0$, such that each ball of radius $r$ contains at most one point of $S$, and every ball of radius $R$ contains at least one point of $S$.

Dual

One way to compute the window of a model set (resp. the Rauzy fractal of a tiling) is to consider the ‘lifted’ versions of the expanding maps of the substitution (which are automorphisms of the high dimensional lattice $L$) and their counterparts in the internal space. These are contracting maps yielding an iterated function system. The latter is known to have a unique compact nonempty solution. Multiplying the whole iterated function system by an appropriate factor yields the dual substitution. This was outlined in [Thu89] , see also [Gel97] , [Fre05] . Actually, this is not the only notion of dual tiling. Equivalent concepts in arbitrary dimension are the natural decomposition method [SW02] and - almost sure - the dual substitutions in [SAI01] . In dimension one there are even more equivalent concepts, see for instance [Lam98] .

Euclidean Windowed Tiling
FLC

A tiling has finite local complexity (flc) if it contains only finitely many types of patches with diameter less than some given R>0. ‘Types of patches’ is to be read either as congruence classes of patches, or as translation classes of patches. For instance, the pinwheel tiling is not flc w.r.t. translation classes, but it is flc w.r.t. congruence classes. In our classification, this qualifies the pinwheel tiling to be stored under infinite rotations, and there under finite local complexity. Equivalently, one may define flc by requiring that the tiling contains only finitely many n-coronae for a fixed n, or finitely many vertex stars. Here again, one has to consider the distinction between ‘up to congruence’ and ‘up to translation’.

Finite Local Complexity
Finite Rotations
Harriss's Rhomb substitutions with n-fold rotational symmetry

A generalisation of the Goodman-Strauss 7-fold rhomb , by E. Harriss. The details can be found in (Harriss:NRSTTAORS).

Hull

A plane tiling generates a dynamical system $(X,\mathbb{R}^2)$, where $X$ is the closure (w.r.t. a certain topology) of the orbit of the tiling under the actions of $\mathbb{R}^2$. This $X$ is called the hull of the tiling. For more details, see for instance [Kel00] and references therein.

Infinite Local Complexity

Here tilings are listed where the prototiles occur in infinitely many orientations, and the tilings are not flc .

Infinite Rotations

In many cases, the prototiles of a substitution tiling occur only in finitely many orientations. Here we list the tilings where this is not the case. Thus these don’t show flc up to translation, even though they may show flc up to isometries.

Inflation Factor

The linear map that gives the scaling for a substitution rule, before the replacement by new tiles. Often, the linear map is just a scaling by a real number, or, in the plane case - where $\mathbb{R}^2$ is identified with the complex plane - a multiplication by a complex number. Then this number is called the inflation factor. The algebraic properties of such a number are of special interest. If the tiling is volume hierarchic up to translation, then the inflation factor is an algebraic integer. If it is real, then this is a simple consequence from the fact that the substitution matrix is a nonnegative integer matrix: The largest eigenvalue (unique, real, positive because of the theorem of Perron Frobenius) is the inflation factor to the dimension. Thurston stated in [Thu89] that each inflation factor $q$ of a volume hierarchic tiling is a Perron number. That means, $q$ is an algebraic integer which is strictly larger than its algebraic conjugates in modulus (except the complex conjugate of $q$, if $q$ is a complex number). Kenyon gave a proof of the converse (for each complex Perron number there is a volume hierarchic tiling) in [Ken96] . An important property of the inflation factor $q$ of a volume hierarchic tiling is, whether it is a PV number or not. If so - and if $q$ is irrational - then this is a strong hint that the tiling is a cut and project tiling. If $q$ is also an algebraic unit, then the internal space will be Euclidean. If not, the internal space may be $p$-adic or a product of Euclidean and $p$-adic spaces. A lot of literature is devoted to this fact. We give just a short and highly incomplete list which may serve as starting points for further reading: [Fog02] , [Moo00] , [Lag96] , [Sir02] .

Internal Space

The space where the window of a model set lives in. For details, see cut and project.

Kenyon's Construction

As well as showing that there are substitution rules for every Perron Inflation Factor, [Ken96] gives an explicit construction for expansion factors $x$ with $x^n - p x^n-1+qx + r =0$, where $n,p,q,r$ are integers with $n>2, r$ positive, $p,q$ non-negative.

LI-Class

The equivalence class of tilings induced by the relation locally indistinguishable.

Limitperiodic

A nonperiodic tiling is called limitperiodic, if it is the union of countably many periodic patterns (up to a set of zero density). It is quite easy to see that this can only be the case if the inflation factor (or a power of it) is an integer number. A tiling is limitperiodic if and only if it can be obtained through a cut and project scheme with p-adic internal space

Locally Indistinguishable

Two tilings are called locally indistinguishable, if a copy of each patch of one tiling occurs in the other tiling and vice versa. For instance, any two tilings arising from the same primitive substitution s are locally indistinguishable. It is easy to see that local indistinguishability is an equivalence relation. Thus we can speak of li-classes.

MLD

Two tilings are called mld (mutually locally derivable), if one is obtained from the other in a unique way by local rules, and vice versa. For example, a tiling by Penrose Rhomb is obtained from a Robinson Triangle tiling easily: just delete the shortest and longest edges, keeping only the medium ones yields the Penrose Rhomb tiling; and vice versa: in a Penrose Rhomb tiling, add in each fat rhomb the long diagonal, and in each thin rhomb add the short diagonal. This gives again the Robinson Triangle tiling. The proper definition is as follows [BSJ91] : A tiling $T$ is locally derivable from a tiling $S$ (with radius $r$), if for all $x$ holds: If $S$ intersected with $B_r(x) = (S \textrm{ intersected with } B_r(y)) + (x-y)$, then $T$ intersected with ${x} = (T \textrm{ intersected with } {y}) + (x-y)$. Here, $B_r(x)$ denotes the open ball around $x$ of radius $r$. ‘$T$ intersected with $M$’ is to be understood as the set of all tiles in $T$ which have nonempty intersection with M. $S$ and $T$ are mld, if $S$ is locally derivable from $T$ and vice versa. It is easy to see that mld defines an equivalence relation. Sometimes it is more convenient to deal with mld-classes than with individual tilings.

MLD Class Ammann
MLD Class Chair
MLD Class Fibonacci
MLD Class Penrose
MLD Class Pinwheel
Matching Rules

Many interesting substitution tilings can alternatively be generated by a matching rule. Examples are (again) the Penrose Rhomb tilings: Note the red arcs on each tile. The matching rule is given by the condition that tiles have to meet in a way such that the arcs of each tile are connected with arcs on the neighboured tiles. The set of all tilings fulfilling this local condition is exactly the set of all tilings generated by the Penrose Rhomb substitution. In particular, the condition forces nonperiodic tilings. (Of course there are periodic tilings made of the Penrose rhomb tiles, but these do not obey the matching rule.) If one reads ‘this substitution tilings can be generated by a matching rule’ or so, two cases has to be distincted: Usually a matching rule is formulated by using a decoration of the prototiles (like the red arcs on the Penrose Rhomb). Either the original tilings are mld to the decorated ones, or they are just locally derivable from the decorated ones (but not vice versa). In the latter case, there is no way to derive the decorated tiling from the undecorated in a unique way locally. In the former case, the matching rule can be given by an ‘atlas’ of undecorated clusters. For instance, Danzer’s 7-fold tilings can be defined by the atlas of its vertex stars. Those tilings are classified here under ‘known matching rules without decoration’, in contrast to ‘… with decoration’. Goodman-Strauss showed in [Goo98] that every ‘nice’ family of substitution tilings can be generated by a matching rule with decoration.

Model Set

A model set is a discrete point set (more precisely, a Delone set) arising from a cut and project scheme. A theorem of Hof, generalized by Schlottmann, states that each model set is pure point diffractive [Hof95] , [Sch00] . In connection with quasicrystals, it is of interest if a substitution tiling can serve as a model for a physical quasicrystal. Since physical quasicrystals are detected via their diffraction properties, this leads to the question whether a substitution gives rise to a model set. This is true for many well-known substitution tilings, in particular for the Penrose Rhomb tilings and the Ammann-Beenker tilings. These are mld with model sets with Euclidean internal spaces and with polytopal windows. Other model sets may arise from Euclidean internal spaces and fractally shaped windows, like the conch or the tribonacci tilings. There are also tilings corresponding to model sets with p-adic internal spaces - like the chair and the sphinx tilings - as well as tilings corresponding to model sets with mixed p-adic and Euclidean internal spaces, like the Watanabe Ito Soma 8-fold tilings. Another interesting property of model sets is that each Meyer set is a subset of a model set. A Meyer set is a Delone set L, such that L-L is contained in L+F, where F is some finite set [Mey95] , [Mey72] . A central question in the theory of nonperiodic substitution tilings is the PV-conjecture: Essentially, it asks whether every primitive substitution tiling which inflation factor is an irrational PV number is mld to a model set (possibly under further conditions). Currently, the conjecture is proven for one-dimensional tilings with two prototiles [Hol03] , [Sir02] . The general case (more prototiles, higher dimensions) remains open.

Morphism

Substitutions - in particular 1dim substitutions - with m prototiles can be formulated as a endomorphism of the free group with m generators. If the endomorphism is an automorphism, i.e., if it is invertible, then the substitution is also called invertible.

Nonperiodic

A tiling $T$ is called nonperiodic, if from $T + x = T$ it follows that $x=0$. In other words, if no translation (other than the trivial one) maps the tiling to itself. In the theory of nonperiodic tilings usually the repetitive ones are the objects to be investigated. Usual constructions for repetitive nonperiodic tilings are substitutions, cut and project methods, and matching rules. Another well-studied class of nonperiodic (non-repetitive) tilings are random tilings, which can also be viewed as being generated by matching rules.

One Dimensional
PV

An algebraic integer q is a PV number (for Pisot-Vijayaraghavan number), if all its algebraic conjugates (except its complex conjugate, if $q$ is complex) are less than one in modulus. A profound theorem by Meyer states essentially, that a substitution tiling can only be a model set, if the inflation factor is a PV number [Mey95] .

Parallelogram Tiles
Patch

Dealing with tilings, it is useful to consider finite parts of a tiling. These are called patches (or clusters). The definition is simply: a patch is a finite subset of a tiling. Sometimes one requires, in addition, that the support of a patch should be connected, or homeomorphic to a ball. The latter leads to problems in higher dimensions. There are tilings where no patch with more than one tile is homeomorphic to a ball (although the prototiles are), see Fig. 3 in [Fre02] . Frequently, $R$-patches are used. The $R$-patch around $x$ in a tiling $T$ is the set $P_R(x) = \{ T \in T | T \textrm{ has nonempty intersection with the closed ball of radius } R \textrm{ around } x \}$.

Perron

A Perron number is an algebraic number that is strictly greater in absolute value than its algebraic conjugates. A complex algebraic number is greater in absolute value than its algebraic conugates with the exception of its complex conjugate. These numbers play an important role in the theory of substitution rules. For more see inflation factor.

Pinwheel Angles
Pinwheel Angles
Polyomio Tiling

Tiles made of joined unions of squares. Such tilings were introduced and studied in [Golomb:P not found].

Polytopal Tiles
Polytopal Windowed Tiling
Primitive

A non-negative Matrix $M$ is called primitive, if there is a power of $M$ which has strictly positive entries. A substitution is called primitive, if the corresponding substitution matrix is primitive.

Prototile

The tiles, which serve as building blocks for tilings. For more details, see tiling.

Rauzy Fractal
Rauzy Fractal
Rep-Tiles

Substitution rules with just a single tile.

Repetitive

A tiling $T$ is called repetitive, if for every $r>0$ there is $R>0$, such that a copy of every $r$-patch in $T$ is contained in every $R$-patch in $T$. In plain words, this means that each local part of the tiling occurs ‘everywhere’ in the tiling. In even plainer words: If you stand on a repetitive tiling, then your local surrounding do not tell you the in the slightest way where you are, even if you have a map of the whole tiling:

Face it

If $R$ depends on $r$ linearly, say, $R=ar+b$ for some $a,b>0$, then $T$ is called linearly repetitive. A weaker version is the following, which we prefer to call weakly repetitive: For every patch $P$ in $T$, there is $R>0$ such that every $R$-patch in $T$ contains a copy of $P$. Unfortunately, the latter is sometimes referred to as ‘repetitive’ in the literature, sometimes as ‘weakly repetitive’. Every repetitive tiling that is locally finite is of flc. Every primitive substitution tiling is weakly repetitive. For each substitution tiling $T$ holds: $T$ flc $\Leftrightarrow$ $T$ repetitive $\Leftrightarrow$ $T$ linearly repetitive.

Rhomb Tiles
Sadun's Generalised Pinwheels

A set of substitution rules constructed by generalisation of the Conway-Radin Pinwheel, by L. Sadun. The details of these rules can be found in [Sad98] .

Self-Similar Substitution

A substitution (at least here) consists of rules how to enlarge a tile and replace the enlarged tile with other tiles. If the union of the latter ones is similar to the original tile, then the substitution is called self-similar substitution. For example, the substitution for the Penrose Rhombs is not self-similar, but the substitution for the Robinson Triangles is.

In other words, a substitution is a self-similar substitution, if $\sigma(T)=T$. A substitution tiling is called self-similar, if it can be generated by a self-similar substitution. It is known that any - sufficiently nice, i.e., repetitive and flc wrt translations - tile substitution in the plane can be made self-similar, by using fractal boundaries.

A weaker version is described by the term ‘self-affine’ tiling [LW96] , [BG94] . The definition of this reads exactly as above if one replaces ‘similar to’ with ‘affine image of’.

Sadun’s generalised Pinwheels

Statistical Circular Symmetry

A tiling has statistical circular symmetry, if the orientation of the tiles of each kind are equidistributed on the unit sphere. It is shown in [Fre08] that all primitive substitution tilings with tiles in infinitely many orientations are of statistical circular symmetry. For a precise definition of statistical circular symmetry, see [Fre08] .

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.

Substitution Matrix

To a substitution $s$ with prototiles $T_1, \ldots T_m$ we assign the substitution matrix $M_s = (m_{ij})_{i,j = 1,\ldots ,m}$, where $m_{ij}$ is the number of copies of $T_i \in s(T_j)$. The substitution matrix carries a lot of information about the tilings arising from $s$. For simplicity, let’s assume the tilings are volume hierarchic. Then the eigenvector of $M_s$ which is largest in modulus is $q^d$; i.e., the inflation factor $q$ of $s$ to the dimension $d$. Note that this is true in any dimension $d$. If $M_s$ is primitive, then by the Perron-Frobenius theorem this largest eigenvalue is real, positive and unique. In this case, the corresponding (right) eigenvector contains the relative frequencies of the prototiles. Moreover, the left eigenvector (resp. the eigenvector of the transpose of $M_s$, if you don’t like left eigenvectors) contains the $d$-dimensional volumes of the prototiles. Further properties of the tilings can be derived from the algebraic properties of $q$, hence from the $d$-th root of the leading eigenvector of $M_s$ (for instance, see PV number).

Super-Tile

The n-th iterate $s^n(T)$ of a prototile under a substitution $s$.

Tile

For our purposes, a tile in $\mathbb{R}^d$ is defined as a nonempty compact subset of $\mathbb{R}^d$ which is the closure of its interior. Sometimes a tile is required to be connected, or to be homeomorphic to a closed ball. For a substitution one needs a finite set of tiles which serve as building blocks for the substitution tilings. These are called prototiles. Sometimes the term is used in a slightly different sense. If it is stated that ‘$T$ is a tile’, then this can mean that there is a tiling $T$ such that $T$ is the single prototile of $T$. For instance, in this sense each square is a tile, but a regular pentagon is not a tile.

Tiling

A tiling $T$ in $R^d$ is a countable set of tiles, which is a covering as well as a packing of $R^d$. I.e., the union of all tiles in $T$ is $R^d$, and the intersection of the interior of two different tiles in $T$ is empty. If $T$ contains only finitely many congruence classes of tiles (resp. translation classes), then a family ${T_1, T_2, \ldots ,T_m}$ of representants of each class is called the family of prototiles. With the help of these prototiles, $T$ can be written as $T=\{ f_i (T_{j(i)}) \mid f_i \textrm{ isometries }, i=1,2,3,\ldots \}$. In the case of finitely many prototiles up to translation one has an even simpler representation, namely $T=\{ T_{j(i)} + x_i \mid i=1,2,3,\ldots \}$.

Translation Module

For any tiling T, the translation module is the $\mathbb{Z}$-span of all translations $t$, such that there is a tile $T$ in $T$, and $T+t$ is also in $T$. If $T$ is periodic, the translation module is a lattice, and the set of periods is a subset of the translation module. Even if $T$ is nonperiodic, the translation module can be a lattice (for instance, see the Chair tilings). Whenever the translation module of a tiling is a lattice, this is a hint that the tiling may be a model set with $p$-adic internal space [LMS03] , [FS] .

Vertex

One can start a long discussion about the definition of a vertex in a tiling. We leave that to others and define a vertex in a plane tiling as a point in $\mathbb{R}^2$ which is contained in more than two tiles of the tiling.

Vertex Star

A vertex star is the 0-corona of a vertex of a tiling. In other words, the vertex star of a vertex $x$ in a tiling $T$ is the set of all tiles in $T$ which have nonempty intersection with $\{x\}$.

Window

The compact set in the internal space of a model set which tells which lattice points are projected. For details, see cut and project.

With Decoration
Without Decoration
p-adic Windowed Tiling