# Aperiodic Tilings, Order, and Randomness

Rodrigo Treviño

In 1619, Kepler published his Harmonices Mundi (Harmonies of the World), a volume of five books discussing mathematics, physics, astrology, and music. In Book II, Kepler sets out to understand the “Congruences of regular figures,” that is, how different types of regular polygons can be placed next to one another and tile parts of the plane. In Proposition XIX, he states:⁠Footnote1 There are six ways in which the plane can be filled around a point by figures of two kinds: in two ways using five angles, in one way using four angles, and in three ways using three angles. After discussing how the angles of equilateral triangles and squares can come together, he proceeds to consider angles which come up in regular pentagons (emphasis mine, see Figure 1):

1

I am using the translation by E. J. Aiton, A. M. Duncan, and J. V. Field published in 1997 by the American Philosophical Society.

if we now come to the pentagon angles we may take two of them, because together they come to more than two right angles; and a decagon angle fits into the space they leave. The decagon is encircled by ten pentagons, but this pattern cannot be continued in its pure form. See the inner part of diagram Z.

Here we must consider the star pentagon, since we can fit together three pentagon angles and one point of a star, because the re-entrant angle of the star takes one pentagon angle while, no less, the gap left by fitting together three pentagon angles takes the point of the star. See the outer part of the same diagram Z.

However, this pattern cannot be continued indefinitely, for the domain it builds up is unsociable and when it has added to its size a little it builds fortifications. You may see a different arrangement of these two forms marked with the letters Aa.

If you really wish to continue the pattern, certain irregularities must be admitted, two decagons must be combined, two sides being removed from each of them. As the pattern is continued outwards five-cornered forms appear repeatedly …as it progresses this five-cornered pattern continually introduces something new. The structure is very elaborate and intricate. See the diagram marked Aa.

And so Kepler recorded how it is difficult to tile the plane with shapes derived from pentagonal angles.

The modern theory of aperiodic tilings in dimensions greater than one started in the second half of the twentieth century: in the early sixties, motivated by questions of decision in logic, Wang investigated whether one could tile the plane with a finite collection of squares with decorated sides, where two tiles could be placed in an edge-sharing way if and only if the decorations on the sides were the same. He conjectured that if, given a finite set with edges decorations, a tiling of the plane could be found, then a periodic tiling could also be found. That is, a tiling that is invariant under a nontrivial element of the group of Euclidean translations. Any such element is called a period.

Wang’s student, Berger, soon disproved the conjecture, giving a set of 20,426 decorated squares—now known as Wang tiles—such that they tile the plane but only do so without any periods, that is, they tile the plane aperiodically. This was the first explicit finite set of tiles which gave an aperiodic tiling of the plane. Berger’s result marked the beginning of the modern study of aperiodic tilings of the plane, and his work was closely followed by R. Robinson, who soon constructed a set of 52 Wang tiles—obtained from rotations and reflections of a set of seven tiles—which tiled the plane aperiodically, in addition to other sets of tiles which tile the plane aperiodically.⁠Footnote2

2

And so the quest began to tile the plane aperiodically with the smallest number of tile types. Depending on the operations allowed (e.g., translations, rotations, or reflections) there are different results. The recent papers of Greenfeld and Tao give good historical accounts to these types of questions, which will not be the focus of this article. See for example GT22, §1 and references therein.

The 1970s was a critical period for the construction of various types of aperiodic tilings of the plane. In the early 1970s Penrose independently came up with the construction of an aperiodic tiling now known as the Penrose tiling, shown partly in Figure 2. His own account in 1974 in the Bulletin of the Institute of Mathematics and its Applications of how he arrived at the pattern goes like this:

I had often doodled by fitting together limited configurations of pentagons and similar shapes but I had never found a good rule for continuing such patterns indefinitely. However, recently I wanted to design something interesting for someone who was in hospital to look at and I realized that there was a certain definite rule whereby one could continue such a pattern to arbitrary size. The pattern never repeats itself–in the sense that there is no period parallelogram. Nevertheless, the rule that forces this pattern is a purely local one.

And thus Penrose tamed the pentagons which tormented Kepler.⁠Footnote3 In fact, comparing Figures 1 and 2 one sees how Penrose managed to coherently fill in the figures which had stumped Kepler in his drawing. Later, Penrose modified his construction so that there are only two types of tiles—“kites” and “darts”—which appear in the tiling in finitely many orientations. This construction graced the cover of Scientific American in 1977 and was described by Martin Gardner in that same issue (see Figure 3). Gardner mentioned in his article that he did not write about the construction sooner because Penrose was waiting to be granted a patent for his construction. The approval of the patent (US patent 4,133,152) led to one of the strangest cases of mathematical litigation: in 1997, Kimberly-Clark introduced a new toilet paper product with an interesting new pattern (see Figure 4). Penrose thought it infringed on his patent, and so he took the company to court, at which point his lawyer made the following statement: “When it comes to the population of Great Britain being invited by a multinational to wipe their bottoms on what appears to be the work of a Knight of the Realm without his permission, then a last stand must be taken.”

3

There is another way to extend Kepler’s configuration Aa in Figure 1 into a tiling of the plane, but this tiling is a periodic tiling. See GS16, §2.5 for details.

The study of tilings received an unexpected boost in the 1980s from chemistry. In early 1982, D. Shechtman discovered a metallic solid with unbelievable properties: it diffracted electrons like a crystal, but it did so in a way that its diffraction spectrum had an icosahedral group of symmetries, which was incompatible with a lattice molecular structure. That is, in some sense, it behaved like a metal whose atomic structure should be periodic but due to the crystallographic restriction theorem this alloy could not have such molecular structure.

Figure 6 shows some of the diffraction patterns from Shechtman’s discovery. What is remarkable is that—at once—it exhibits icosahedral symmetry and there are bright spots in the picture of the diffraction experiment. This means that the internal structure does not have a periodic structure but it experiences long range order (this will be revisited more precisely below). At the time, many scientists did not believe Shechtman’s discovery because the dogma at that point was that all well ordered metal alloys had to have a periodic structure, and this discovery challenged that dogma. This incredulity made it hard for him to publish his findings, eventually doing so in 1984. Slightly before this discovery, Mackay independently showed that the Penrose tiling diffracted, which led him to hypothesize that materials with nonperiodic but well-ordered molecular structures were theoretically possible. In 1984, Levine and Steinhardt made the explicit connection that Penrose-like structures were actually models for the material discovered by Shechtman, coining the term quasicrystal to describe such structures. Shechtman would go on to win the 2011 Nobel Prize in chemistry for his discovery.

Thus quasicrystals are materials whose atomic structures are not periodic but they share many properties with metals whose atomic structures are periodic (crystals). This augmented the raison d’être of aperiodic tilings in higher dimensions as they were suddenly found to be physically relevant. This catalyzed the development of the modern theory of aperiodic tilings in any dimension, and my goal here is to give a brief introduction to it.

I note that the theory of one-dimensional tilings is older than that of tilings of the plane. The reason is that there is only one type of connected tile in one-dimensional tilings—a line interval—and so some of the geometric complications which arise in higher dimension are not present for one-dimensional tilings (although there are geometric considerations when studying one-dimensional tilings).

In its earliest days, the study of aperiodic tilings in one dimension manifested itself in the study of aperiodic sequences. The earliest such sequence is the so-called Prouhet–Thue–Morse sequence, which showed up implicitly in the work of Prouhet in 1851, was made explicit and studied by Thue in 1906, and made widely known by Morse in 1921 when he (re)discovered the sequence and used in the study of geodesics in on surfaces of negative curvature. See AS99 for a full history of this sequence. Morse would go on to cofound—along with Hedlund—the field of symbolic dynamics in 1938 in their seminal paper of the same name, where they introduce the study of symbolic sequences as dynamical objects and derive properties of the Prouhet–Thue–Morse sequence.

There are many excellent references on different aspects of the theory of aperiodic tilings GS16Sad08BG13KLS15AA20 and I will reference them when needed. The Tilings Encyclopedia (https://tilings.math.uni-bielefeld.de) is also a great resource to see examples of many constructions.

## 1. Basic Definitions

A tiling of is a countable union of sets of the form —called the tiles—where is the support of the tile and belongs to a countable set of labels or colors, such that

where is the support of a tile in the tiling and the union is over the set of tiles in the tiling and where, if for some , then . There are all sorts of assumptions that can be made about the tiles, but a standard one is the following: the support of the tiles are connected compact sets with nonempty interior, and the set of labels is finite. Throughout this article this will be the standing assumption unless otherwise noted, and I will often refer to the supports of the tiles as tiles when it is not ambiguous. The reasons labels/colors are needed is that we get extra structure from considering them: for example, all Wang tiles have supports which are squares, but the decorations on their edges make them different as tiles, and the interesting properties about these tilings come from the labels. I will mostly focus on tilings of Euclidean spaces, but note that it is easy to define tilings of other spaces and/or groups in analogous ways.

There is a somewhat dual point of view to tilings. A Delone set is a countable subset such that it is

uniformly discrete

there exists an such that for all , and

relatively dense

there exists an such that for any , where is the open ball of radius around .

The rough duality between tilings and Delone sets comes from the fact that if is a Delone set then both the Delaunay triangulation of given by this point set as well as the Voronoi tessellation defined by this point set give a tiling of . Likewise, if is a tiling then the set consisting of the center of mass of each tile gives a Delone set, assuming the tiles of are nice enough. In what follows, properties of tilings will be discussed, and the corresponding properties for Delone sets are analogously defined.

A patch of a tiling is a compact subset of consisting of a finite union of tiles, usually taken to be connected. The -patch of around is the collection of all tiles in whose support intersects . Two patches and are translation-equivalent if there is a such that , where in slight abuse of notation the translation is meant in the support of a patch, but the equality is meant both in the support and the label. A tiling has finite local complexity (FLC) if for every there is a finite number of translation-equivalent classes of -patches, otherwise it has infinite local complexity (ILC). A tiling is repetitive if for every there is a such that every -patch is found as a subpatch in the -patch around every point in . Repetitivity necessitates finite local complexity but the converse is not true.

## 2. Constructions

There are three classical ways to construct aperiodic tilings: by matching rules, through substitution and expansion rules, and through the cut-and-project method. The Penrose tiling has the remarkable property that it can be obtained by all three of these methods. I will briefly describe each of these classical methods, but do note that recently there has been significant work on variations of these methods as means of constructing aperiodic tilings which I will not discuss here.

The method of matching rules is what was used to construct aperiodic tilings with Wang tiles: a finite number of types of tiles are given with rules on how two of them may share an edge. Defining matching rules does not immediately guarantee that a tiling of can be achieved through these matching rules, nor that the tiling obtained will be aperiodic or not.

The method of substitution and inflation/expansion is defined through a substitution rule: by starting with a finite collection of tiles in —the prototiles—and an expanding linear map , these tiles admit a substitution rule with expansion if there exist vectors such that for any , is a patch defined as

that is, there is a way to partition into the union of copies of different types of tiles. The collection of numbers is called the substitution matrix,⁠Footnote4 and the number describes exactly how many copies of tile are found in an expanded tile . We can then apply the substitution rule to each tile in the resulting patch which will give an even larger patch (see Figures 7 and 9 for some examples). This procedure can be done indefinitely and by carefully taking a limit we can cover all of with a tiling obtained from a substitution rule. The resulting tiling will be repetitive if the rule is primitive, which means there is a such that the matrix has strictly positive entries. Whether or not this tiling is aperiodic can be determined by looking at whether the substitution rule is recognizable; see BG13, §5.6. Finite local complexity of the resulting tiling can be guaranteed in some cases, e.g., if the prototiles are CW complexes and the union in 1 respects the CW structure to a certain extent. I do not know when the first substitution rule was discovered, but the substitution rule of well-known aperiodic tilings, such as the chair tiling and the half-hex tiling already appear in print in 1940 in a note of Langford Lan40, although it was not noticed that indefinite applications of these rules would lead to aperiodic tilings. If the rescaling is conformal, then the tiling is self-similar, otherwise it is self-affine.

4

Note that this matrix depends on how we index the prototiles, and so different indexing leads to different matrices. Some authors use the convention that here is the transpose of the substitution matrix.

Before proceeding to other methods of construction, it is worth noting how substitution works in one dimension. Let be a finite set—the alphabet—and the set of all finite words with symbols in . A symbolic substitution rule is a function . This rule can be iterated: if , then is obtained by applying to every symbol in . Assuming this rule is primitive, there is a symbol and sequence such that converges to an infinite aperiodic word which is invariant under (a power of) the substitution rule.⁠Footnote5 This symbolic tiling can be made geometric and realized as a rule in of the type 1 by using the Perron–Frobenius eigenvalues and eigenvectors of the substitution matrix .

5

For example, the Prouhet–Thue–Morse sequence is constructed using and rule and .

The cut-and-project method creates an aperiodic point set as follows. Let be a -dimensional irrational subspace (the physical space), where by irrational I mean , an -dimensional subspace (the internal space) transverse to (which we can assume is ) and a compact set called the window, which usually is taken to have nonempty interior, but does not have to. Denoting by and the projections, let . The cut and project set associated to this data, is the set , which is a Delone set. It is aperiodic, repetitive and of finite local complexity since was chosen to be irrational.

The Penrose tiling has the satisfying property that it can be recovered by any of the three constructions above: the first cut-and-project set was described by de Bruijn dB81, who sought to recover the Penrose tiling through a projection method and managed to recover the vertex set of the Penrose tiling. In his first description of his construction and in his patent application, Penrose himself managed also to give matching rules for his original aperiodic tiling (the version in Figure 5 is possible by the matching rules). Thus the Penrose tiling can be constructed by the three methods introduced above. In 1998, Goodman-Strauss proved that every aperiodic tiling constructed from a substitution rule in dimension greater than one can in fact be obtained through “decorated” matching rules. Not every substitution tiling can be recovered through the cut-and-project method, as there are obstructions given by a unitary representation of defined by a tiling which can get in the way (this will be discussed in §3 below).

### 2.1. Organizing the tilings

What do we do with tilings defined like this? We want good ways in which they can be distinguished. Here are a couple of ways of doing that.

First, it is helpful to throw all sorts of related tilings into one space, and call that space a space of tilings. There are a few ways in which tilings can be related. For and a tiling , let be the translation of by . That is, it is a new tiling where the tiles have supports , where is the support of a tile in . If and , then is a period of . A tiling is aperiodic whenever implies .

If is aperiodic then is a -parameter family of tilings which are all distinct but obviously related as they all are translates of . Without further structure, this set is essentially , which says nothing about . So we want to be able to compare and in a more meaningful way.

One way of doing this to define a new notion of distance between two different translates of . A common one is roughly described like this: two translates and are no more than apart if, when looking at their -patches around the origin they are the same up to an error of size . What “an error of size means can be subtle, but if has finite local complexity then it means a translation of size at most . More generally, the spirit of this type of metric is that the -patch around the origin of both tilings should be -close in a Hausdorff-ish metric, called the Chabauty metric.

With a choice of metric on the set of all translates of a given tiling, we can consider the metric completion of the set of all translates of

and call this the tiling space of . With the metric thus defined, it is a compact metric space, which is nice, since tilings themselves are not compact and it is often easier to deal with compact spaces than with noncompact spaces. Note that if a tiling is repetitive, then we cannot distinguish two tilings in its tiling space by purely local considerations, since repetitivity forces the two tilings to look the same on arbitrarily large patches. Thus, tiling spaces for repetitive tilings are sometimes called local isomorphism classes.

To get a good idea of what these spaces are like, let us assume for the moment that is aperiodic, repetitive, and of finite local complexity. Then its tiling space has the local product structure of the form , where is an Euclidean ball and is a Cantor set. The factor comes from the fact that by translating a tiling by a very small vector , is -close to by the definition of the metric above. Now for simplicity, suppose that the diameter of any tile in any tiling of is less than 1. Take a tiling from and assume that the origin is contained in the interior of (the support of) a tile . Consider as a patch and consider all tilings in which have the same patch, both in terms of the same support and same label. In how many ways does this patch appear as a subpatch of an -patch around the origin? By the assumptions of aperiodicity, repetitivity, and FLC, for some , this patch appears as a subpatch of an -patch in at least two ways. Applying the same reasoning, there is a sequence of numbers such that any -patch around the origin appears in at least two different ways as a subpatch of a -patch. This sequence of choices between finitely many but at least two choices should remind you of a Cantor set, and it shows that the local structure has a component which is a Cantor set.

This local structure extends to give the structure of a foliated object (think of puff pastry or phyllo dough for tiling spaces of two-dimensional tilings). Indeed, note that for all , and so tiling spaces come with an action by by translation. If is repetitive, then the orbit of every tiling is dense in the tiling space, and so can be seen as a compact metric space foliated by copies of which are the orbits of tilings in the space.

Tiling spaces of this type can also be seen to be inverse limits, which is especially convenient in the case of tilings constructed through a substitution rule. If is built from a substitution rule on CW complexes, then, as proved in AP98, we have the following homeomorphism

where is a CW complex and is a cellular map. This description of a tiling space will be useful below.

As noted by Penrose when he first wrote about his construction, the substitution and inflation/expansion method introduces a hierarchy of scales of the tiling. That is, once a tiling is constructed through a substitution rule, by the nature of the substitution and inflation/expansion rule, there are patches of tiles whose support is a scaled copy of one of the tiles. More specifically, consider the expanding linear map required in the definition of a substitution rule. If is a tile, then we call it a level- supertile, and, for every , is a level- supertile. The self-similarity of with expansion forces the structure of level-0 supertiles to be determined by the structure of level-1 supertiles, which are in turn determined by the structure of level-2 supertiles, etc. Thus there is a hierarchical structure of supertiles, each one determining the one preceding it.

This hierarchical structure is baked into the Anderson-Putnam AP98 point of view of a tiling space of a self-similar tiling being an inverse limit. However, a substitution rule is not necessary to have a hierarchical structure. Frank and Sadun have developed a theory of fusion, which aims to systematize tilings with hierarchical structure (see N. P. Frank’s notes in AA20 and references within).

### 2.2. Distinguishing different tilings

In what ways can tilings be different? Certainly if is not homeomorphic to then we would not expect and to be the same, perhaps even locally. Moreover, two tilings in the same tiling space can be compared by considering how close they are with respect to the distance on the tiling space. So we can talk about both local and global comparisons.

The tiling is locally derivable from (denoted ) if there is a and a rule from the set of all -patches of to the set of tile types of such that the -patch around in determines the tile(s) containing in . If and , then they are mutually locally derivable (MLD). This means that a finite amount of information around in determines the local information around in . This implies that the tiling spaces of the two tilings are homeomorphic, but the converse is not true. In addition, if two tilings and are MLD equivalent, then not only do we get a homeomorphism of tiling spaces but in fact a topological conjugacy of their respective actions: for all , where is the translation action on the appropriate tiling space. The bird tiling from Penrose’s patent (Figure 5) is not the same as the original Penrose tiling on the cover of Scientific American (Figure 3), but there are tilings in the respective tiling spaces which are MLD equivalent because the local information from one determines the local information from the other (see BG13, Theorem 6.1 for a fuller description of the Penrose tiling’s MLD class).

The concept of local derivability can capture the essence of a self-similar tiling, or one constructed from a substitution rule. If is an expanding linear map, then a repetitive FLC tiling is pseudo self-affine with expansion if . This captures the essence of a substitution rule: if the tiles of are expanded by , then a substitution rule determines how those expanded tiles can be subdivided to recover patches of the tiling .

Let me turn now to global comparisons. The first thing one may think about when trying to show that two tiling spaces are not homeomorphic is to compute some sort of topological invariant for both spaces and compare them. This is where the point of view of tiling spaces as inverse limits, especially in the substitution rule case, is very convenient. The Čech cohomology of the substitution tiling seen as the inverse limit 2 is the direct/inductive limit

In particular, it is computable—sometimes even by a human. There are also versions of de Rham cohomology for tiling spaces and under mild assumptions they are isomorphic to the Čech cohomology.

The last 20 years have seen the rise of different approaches to compute topological invariants of tiling spaces. Another topological invariant which has been studied is the -theory of tiling spaces which, at a somewhat superficial level, is related to the (rational) cohomology through the Chern character. However, crucial information can be lost in passing from integer cohomology to rational one. In any case, interest in -theories emanating from tiling spaces was first motivated by Bellissard’s program to label gaps in the spectrum of certain self-adjoint operators—so-called random Schrödinger operators—defined from aperiodic tilings. The labeling is understood for aperiodic tilings in dimensions at most 3, but not clear for higher-dimensional tilings.

You’re probably curious what the Čech cohomology of the tiling space for the Penrose tilings is. This has been computed by different methods and different people, leading to:

The calculation can be found in Sadun’s book Sad08, §4.7 on the cohomology of tiling spaces. Thus it is possible to distinguish two tilings by distinguishing their tiling spaces using topological invariants. It is worth mentioning that there are examples of aperiodic tilings whose cohomology groups contain torsion. This was noted later than it should have been, as substitution rules which lead to aperiodic tilings with torsion in their cohomology have appeared in the literature since 1940.⁠Footnote6

6

The cohomology of the tiling space obtained from the substitution rule in Figure 7 has torsion. This was verified using code written by Jianlong Liu.

Tiling cohomology is useful in distinguishing two tilings through their tiling spaces, but it can also help you create a different tiling from an initial tiling . Clark and Sadun CS06 started a theory of deformations of tiling spaces and it roughly starts like this: suppose we want to deform a polygonal, repetitive, FLC tiling of by deforming the edge of all tiles in which are translation-equivalent in the same way and at once. This is the same as deforming the shape of the prototile by perturbing its boundary. Thus the shape of its boundary—as a collection of vectors defined by the edges—can be seen as the image under some map of the cycle represented by the boundary of the tile, i.e., a cocycle. That these vectors/edges have to close up when added together is equivalent to the cocycle being closed, i.e., the shape is defined by a representative of a class in . Thus the shape of tilings in is defined by a class and any class close enough to defines slight deformation of resulting in a different tiling . These classes are called shape vectors. Building on these initial results, Julien and Sadun JS18 proved there is an open set which parametrizes nondegenerate deformations; do consult there for details on deformations.

The tiling obtained by the substitution rule in Figure 7 has , and thus the space of deformation parameters is four-dimensional (). Note that any tiling can be deformed using linear transformations defined by elements of . Since is four dimensional, the only deformations admitted by this tiling are the “trivial” deformations coming from . In contrast, since the first cohomology space of the Penrose tiling is five-dimensional (see above), there exists a six-dimensional space of nontrivial deformations. See CS06 for examples of these nontrivial deformations.

## 3. Dynamics and Order

Besides topological invariants, another powerful tool in the study of tiling spaces comes from ergodic theory. If is an aperiodic repetitive FLC tiling, then every orbit of the action on is dense in . It is typical to assume that this action is also uniquely ergodic, that is that there exists a unique -invariant probability measure on such that for any continuous function on and :

as . This is Birkhoff’s ergodic theorem in action. This type of convergence is a feature of all self-similar aperiodic tilings, and even of a larger class of tilings called linearly repetitive (see the survey on linearly repetitive sets in KLS15). In fact, it takes quite some effort to construct repetitive aperiodic FLC tilings which are not uniquely ergodic (see e.g. CN16).

It turns out that we can squeeze out a lot from the convergence of orbit averages above. For example, the asymptotic frequency of any patch is given by the convergence above by choosing the appropriate continuous function on . In addition, since the action on the tiling spaces defines a unitary representation of on through the family of Koopman operators for , it was noticed by Dworkin and Hof in the early 1990s that diffraction, which led Shechtman to his discovery of quasicrystals, can be recovered through an application of Birkhoff’s theorem by averaging the right “correlation functions” on the tiling space. That is, the bright spot in Shechtman’s diffraction diagram (Figure 6) correspond to the pure point part of the spectral measure of a correlation function .

A function is an eigenfunction of with eigenvalue if for all (constant functions are always eigenfunctions with eigenvalue 0 and so they are considered trivial eigenfunctions). By Bochner’s theorem, it is straightforward to verify that the spectral measure for a eigenfunction with eigenvalue is a Dirac mass at of magnitude , which is why the bright spots on a diffraction picture—called the Bragg peaks—are located at eigenvalues. The term “long range order” was initially used to describe systems with spectral measures which have nontrivial pure point components, meaning that they exhibit strong correlations at arbitrarily large scales.⁠Footnote7 These types of tilings are called mathematical quasicrystals.

7

This term is used more broadly now to describe different features of a tiling, but here I will exclusively use it in its original form.

The long range order coming from eigenfunctions can be seen as follows. Suppose for some and all . Then defines a countable collection of codimension-1 affine subspaces such that for all by the condition for . Thus is strongly-correlated with itself along : for all . Since is aperiodic, for all . However for all suggest a strong form of almost periodicity as measured by .

The strongest form of long range order occurs when every spectral measure in this system is purely discrete, which means is spanned by eigenfunctions of . These systems are said to have pure point or pure discrete spectrum and have a strong algebraic flavor: by the Halmos-von Neumann theorem, systems whose spectral measures are all pure point measures are—from a measurable point of view—rotations on locally compact abelian groups.

If a tiling does not define a system of pure point type, then it can have spectral measures of mixed types, or it can have the property that all spectral measures have trivial pure point component. Tilings of the last type are called weak mixing. Although long range order is missing in weak mixing tilings, they can still be very well structured. In particular, they can be repetitive and of finite local complexity constructed from substitution rules, thus giving them a nice hierarchical structure. The Godrèche–Lançon–Billard tiling in Figure 8 is one such example.

Due to Sol97, it is easy to determine when a substitution tiling is weak mixing, but determining when a substitution system has pure discrete spectrum is not so straight forward. Recall that a Pisot–Vijayaraghavan (PV) number is a real algebraic integer greater than 1 whose Galois conjugates are all less than 1 in absolute value. For a self-similar substitution system to have some long range order, it is necessary for the expansion factor to be a PV number. For example, the system defined by the Penrose tiling has pure discrete spectrum (though this can be deduced by other means) and its expansion factor is the PV number associated to the polynomial . On the other hand, the Godrèche–Lançon–Billard tiling (Figure 8), which is constructed using a substitution rule on Penrose rhombs has a non-PV inflation number (, where is the golden mean), making the tiling weak mixing.

How sufficient the PV condition is for pure point spectrum, however, is still an open question. The set of conjectures collectively known as the Pisot substitution conjectures assert that other forms of algebraic conditions (in addition to the PV condition) imposed on a substitution rule imply that the system is fundamentally algebraic, i.e., that all the spectral measures are pure point measures. There are several partial results towards proving this conjecture; see the survey on these conjectures in KLS15.

### 3.1. Renormalization

There is a rich interplay between ergodic theory and cohomology given through renormalization. Renormalization is the process of changing coordinates to view a familiar object from a different point of view and gaining information in the process. This is a powerful tool to upgrade qualitative statements such as the convergence in 4 to quantitative statements, such as the speed of convergence in 4. Suppose is a FLC aperiodic tiling constructed using a self-similar substitution rule. The substitution rule induces a self-homeomorphism with a nontrivial action on cohomology . It is that affords a change of variables which allows us to use renormalization techniques.

To be more precise, let be the ordered spectrum of the induced action of on . Then it can be shown that for regular enough,⁠Footnote8

8

This can be made precise, but is not very important here.

where are distributions and the are bounded. Thus the spectrum of the action of on determines the speed of convergence of 4 up to an error term given by the boundary of the averaging sets . In particular, the eigenvalues which are relevant in the estimate above are the ones which are strongly expanding. There are several approaches to prove this: first by Sadun using Čech cohomology, then by Bufetov and Solomyak using different tools, and then by myself and Schmieding using the version of de Rham cohomology for tiling spaces.

The action of on is also important in the discussion of order, for we may ask which tiling deformations, if any, preserve long range order. First note that if is an eigenfunction with eigenvalue and is the tiling obtained by deforming using some , then is an eigenvalue for the Koopman operator for the deformed tiling space. Thus the trivial deformations preserve the spectral types of the tiling, so one now wonders what happens with nontrivial deformations.

Clark and Sadun have a nice answer to this question CS06. Let be span of the generalized eigenvectors corresponding to expanding eigenvalues with respect to and be the span of those with eigenvalue strictly less than 1 in magnitude. Clark and Sadun proved that if with -dimensional, then for a typical choice of parameter the deformed tiling is weak mixing and thus lacks long range order.

If an aperiodic tiling is weak mixing, we may want to quantify how far it is from having long range order. Recall that the lower local dimension at of a measure is defined by

Since any pure point measure has for all , weak mixing can be made quantitative by proving lower bounds for the lower local dimension of spectral measures, that is, quantifying how far a measure is from have a pure point component. This was the idea used by Bufetov and Solomyak when they started off the study of quantitative weak mixing.

The general approach to study quantitative properties of spectral measures for self-similar tilings relies on the following spectral refinement to a substitution matrix. Given a tiling, let be the finite subset of vectors which describes the relative positions of tiles of type inside a level-1 supertile of type with respect to a “base” tile of type (this relies on a choice of base tile, but it turns out to be irrelevant). Note that a set of relative vectors is analogously for a deformed tiling . For a spectral parameter , define the matrix

which Bufetov and Solomyak call the spectral cocycle and BGM19 calls the Fourier matrix. Note that . For , define the family of matrix products , where is the expansion factor of the substitution rule. Quantitative and qualitative properties of spectral measures at of the deformed tiling can be determined by the growth properties of as measured through its Lyapunov exponent. More precisely, the slower grows (which is never faster than ), then the farther the system is from having a spectral measure with pure point mass at . See BGM19 and the many papers of Bufetov and Solomyak for details.

In GL89, Godrèche and Luck considered ways in which one could disorganize the perfect Penrose tiling through randomization. A distinction was made of doing so through “global randomness” or “local randomness.” To define these terms, suppose that for a finite set of tiles , you have two different substitution rules (Figure 9 provides an example). Recall that self-similar tiling is constructed through the sequential application of the same substitution rule. What if instead of applying the same rule over and over, we flipped a coin to decide which rule to apply each time? Globally random substitution tilings (sometimes also called mixed substitutions or -adic systems) impose the condition that once the coin is flipped, then the same substitution rule is applied to all of the tiles in a patch, whereas locally random substitutions have you flip a coin for each tile and apply a substitution rule accordingly. Both types of random tilings have seen a surge of activity in the past decade.

Let me mention what are some typical features of these constructions. First, in dimension greater than one, one should have little hope that one gets tilings with finite local complexity, as the different substitution rules need not fit together in a nice enough way to ensure this.⁠Footnote9 Secondly, although it may differ at every scale, these types of tilings still have a hierarchical structure for the same reason that substitution tilings have hierarchical structure. The most significant qualitative difference between the globally random and the locally random is their configurational complexities: globally random tilings have a polynomial growth (in ) of the number of distinct classes of -patches, whereas locally random tilings typically have exponential growth.

9

The study GKM15 is motivated by the desire to want to find compatible substitution rules on the same set of tiles, that is, rules which, when used together randomly still give tilings with finite local complexity.

Globally random constructions have a randomly chosen hierarchical structure. This can be combined with another type of “geometric randomness” as follows. If the substitutions are compatible so that the tiling has finite local complexity, the cohomology of the corresponding tiling space is still given by 3. Recall that there is an open set which parametrizes local deformations. Endowed with Lebesgue measure, we can refer to a typical element of as a random deformation.

A theory of locally random substitution tilings has mostly been developed for one-dimensional tilings. As mentioned above, the high amount of complexity introduced by locally random constructions yields tilings with properties not present in classical self-similar constructions, such as mixing properties MRST22, positive topological entropy as well as interesting measure theoretic entropy (see GMRS23 and references within). In dimension two, locally random constructions can be obtained in the same way as those of GL89 by using other triangular substitution rules with the same expansion rates (e.g. ones from GKM15), or by using variations on a known construction, such as the ones in Figure 9.

In globally random constructions which yield tilings of finite local complexity, long range order or lack thereof—from the point of view of the type of spectral measures—can sometimes be deduced for random choices of hierarchical structure and random deformations of the tiling space. A corresponding family of products can still be defined using matrices of the type 5, although each matrix in the product depends now on a random choice of substitution rule. These analyses fundamentally use renormalization schemes and techniques, and as such the growth properties of the products are determined by their Lyapunov exponents. The exponents give insight into the types of spectral measures the resulting tiling space has. This was done in dimension one by Bufetov and Solomyak and in higher dimensions in a recent paper of mine, where I framed 5 and the subsequent family of products as twisted traces on a locally approximately finite-dimensional -algebra. The generalization to the random setting of the result of Clark and Sadun reads as follows: if the renormalization cocycle on has more than positive Lyapunov exponents (this depends on how randomization is being done), then the typical deformation parameter gives a weak mixing tiling.

Remarkably, the high amount of complexity in locally random constructions is also compatible with order, as there are locally random constructions which yield systems whose spectral measures have pure point components. This was already pointed out in the original analysis of spectral measures in GL89, which already featured a precursor to the matrices 5 that was used to study randomized Penrose tilings. These facts emphasize the distinct roles that order and randomness play in the study of aperiodic tilings although they are interrelated.

To summarize: order comes from the strong correlations at large scales and this is determined by the geometry of the tiles and the geometry of the substitution rules (i.e., the hierarchical structure). Randomness in hierarchy or in shape may or may not affect long range order and this can be measured the the growth properties of the product of matrices determined by 5. There are self-similar tilings (i.e., not random) such as the one in Figure 8 which do not have long range order, and there are random tilings which have long range order. The fun is figuring out what happens when.

## 5. Conclusion

The study of aperiodic tilings is at the crossroads of many branches of mathematics such as combinatorics, logic, ergodic theory, algebraic topology, operator algebras, and mathematical physics, and so there are many points of view and many tools available to study them. There are also many open questions, especially for tilings in higher dimensions.

There are several topics which I did not discuss here that I would have liked to discuss. For example, little was mentioned here about tilings with infinite local complexity; see N. P. Frank’s survey in KLS15. Additionally, problems from mathematical physics are largely absent here. A major area of activity is the spectral theory of random Schrödinger operators on aperiodic tilings. The theory for one-dimensional self-similar tilings is rich (see the survey in KLS15), but in dimensions greater than one very little is known.

During the refereeing period of this article two remarkable things happened. First, a preprint by Smith, Myers, Kaplan, and Goodman-Strauss was posted on arxiv announcing the discovery of an aperiodic monotile—dubbed the hat—which is a shape which tiles the plane but only aperiodically.⁠Footnote10 Any aperiodic tiling constructed using the hat uses it and its reflection in 6 different orientations, giving a tiling with 12 prototiles. Secondly, less than two months after the announcement of this discovery, a preprint by Baake, Gähler, and Sadun was posted on arxiv computing the cohomology groups of the tiling space associated with the hat, as well as a proof that the associated system has pure-point spectrum. These two announcements show that the field is both young enough to contain plenty of of exciting open problems as well as mature enough to possess a robust set of tools—coming from many areas of mathematics—which can be used to determine properties of different tilings. If you find an aperiodic monotile which defines a weak mixing system, let me know.

10

Soon after the announcement of this discovery, some of the authors gave a virtual talk about it, and it can be found in MoMath’s YouTube channel: https://www.youtube.com/watch?v=FkZPMf73qYc.

## Acknowledgment

I am grateful to Scott Schmieding and two anonymous referees who provided very helpful feedback on the first version of this article and helped improve it considerably.

## References

[AA20]
Shigeki Akiyama and Pierre Arnoux (eds.), Substitution and tiling dynamics: introduction to self-inducing structures, Lecture Notes in Mathematics, vol. 2273, Springer, Cham, 2020. CIRM Jean-Morlet Chair, Fall 2017; Lecture notes from the Tiling Dynamical Systems research school held as part of Tilings and Discrete Geometry program, DOI 10.1007/978-3-030-57666-0. MR4200104,
Show rawAMSref \bib{JM:notes}{collection}{ title={Substitution and tiling dynamics: introduction to self-inducing structures}, series={Lecture Notes in Mathematics}, volume={2273}, editor={Akiyama, Shigeki}, editor={Arnoux, Pierre}, note={CIRM Jean-Morlet Chair, Fall 2017; Lecture notes from the Tiling Dynamical Systems research school held as part of Tilings and Discrete Geometry program}, publisher={Springer, Cham}, date={2020}, pages={xix+453}, isbn={978-3-030-57666-0}, isbn={978-3-030-57665-3}, review={\MR {4200104}}, doi={10.1007/978-3-030-57666-0}, } 
[AS99]
Jean-Paul Allouche and Jeffrey Shallit, The ubiquitous Prouhet-Thue-Morse sequence, Sequences and their applications (Singapore, 1998), Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 1999, pp. 1–16. MR1843077,
Show rawAMSref \bib{AS:T-M}{article}{ author={Allouche, Jean-Paul}, author={Shallit, Jeffrey}, title={The ubiquitous Prouhet-Thue-Morse sequence}, conference={ title={Sequences and their applications}, address={Singapore}, date={1998}, }, book={ series={Springer Ser. Discrete Math. Theor. Comput. Sci.}, publisher={Springer, London}, }, date={1999}, pages={1--16}, review={\MR {1843077}}, } 
[AP98]
Jared E. Anderson and Ian F. Putnam, Topological invariants for substitution tilings and their associated -algebras, Ergodic Theory Dynam. Systems 18 (1998), no. 3, 509–537, DOI 10.1017/S0143385798100457. MR1631708,
Show rawAMSref \bib{AP}{article}{ author={Anderson, Jared E.}, author={Putnam, Ian F.}, title={Topological invariants for substitution tilings and their associated $C^*$-algebras}, journal={Ergodic Theory Dynam. Systems}, volume={18}, date={1998}, number={3}, pages={509--537}, issn={0143-3857}, review={\MR {1631708}}, doi={10.1017/S0143385798100457}, } 
[BGM19]
Michael Baake, Franz Gähler, and Neil Mañibo, Renormalisation of pair correlation measures for primitive inflation rules and absence of absolutely continuous diffraction, Comm. Math. Phys. 370 (2019), no. 2, 591–635, DOI 10.1007/s00220-019-03500-w. MR3994581,
Show rawAMSref \bib{BGM:correlation}{article}{ author={Baake, Michael}, author={G\"{a}hler, Franz}, author={Ma\~{n}ibo, Neil}, title={Renormalisation of pair correlation measures for primitive inflation rules and absence of absolutely continuous diffraction}, journal={Comm. Math. Phys.}, volume={370}, date={2019}, number={2}, pages={591--635}, issn={0010-3616}, review={\MR {3994581}}, doi={10.1007/s00220-019-03500-w}, } 
[BG13]
Michael Baake and Uwe Grimm, Aperiodic order. Vol. 1, Encyclopedia of Mathematics and its Applications, vol. 149, Cambridge University Press, Cambridge, 2013. A mathematical invitation; With a foreword by Roger Penrose, DOI 10.1017/CBO9781139025256. MR3136260,
Show rawAMSref \bib{BG:book}{book}{ author={Baake, Michael}, author={Grimm, Uwe}, title={Aperiodic order. Vol. 1}, series={Encyclopedia of Mathematics and its Applications}, volume={149}, note={A mathematical invitation; With a foreword by Roger Penrose}, publisher={Cambridge University Press, Cambridge}, date={2013}, pages={xvi+531}, isbn={978-0-521-86991-1}, review={\MR {3136260}}, doi={10.1017/CBO9781139025256}, } 
[CS06]
Alex Clark and Lorenzo Sadun, When shape matters: deformations of tiling spaces, Ergodic Theory Dynam. Systems 26 (2006), no. 1, 69–86, DOI 10.1017/S0143385705000623. MR2201938,
Show rawAMSref \bib{ClarkSadun:shape}{article}{ author={Clark, Alex}, author={Sadun, Lorenzo}, title={When shape matters: deformations of tiling spaces}, journal={Ergodic Theory Dynam. Systems}, volume={26}, date={2006}, number={1}, pages={69--86}, issn={0143-3857}, review={\MR {2201938}}, doi={10.1017/S0143385705000623}, } 
[CN16]
María Isabel Cortez and Andrés Navas, Some examples of repetitive, nonrectifiable Delone sets, Geom. Topol. 20 (2016), no. 4, 1909–1939, DOI 10.2140/gt.2016.20.1909. MR3548461,
Show rawAMSref \bib{CN:examples}{article}{ author={Cortez, Mar\'{\i }a Isabel}, author={Navas, Andr\'{e}s}, title={Some examples of repetitive, nonrectifiable Delone sets}, journal={Geom. Topol.}, volume={20}, date={2016}, number={4}, pages={1909--1939}, issn={1465-3060}, review={\MR {3548461}}, doi={10.2140/gt.2016.20.1909}, } 
[dB81]
N. G. de Bruijn, Algebraic theory of Penrose’s nonperiodic tilings of the plane. I, II, Nederl. Akad. Wetensch. Indag. Math. 43 (1981), no. 1, 39–52, 53–66. MR609465,
Show rawAMSref \bib{dB:penrose}{article}{ author={de Bruijn, N. G.}, title={Algebraic theory of Penrose's nonperiodic tilings of the plane. I, II}, journal={Nederl. Akad. Wetensch. Indag. Math.}, volume={43}, date={1981}, number={1}, pages={39--52, 53--66}, issn={0019-3577}, review={\MR {609465}}, } 
[GKM15]
Franz Gähler, Eugene E. Kwan, and Gregory R. Maloney, A computer search for planar substitution tilings with -fold rotational symmetry, Discrete Comput. Geom. 53 (2015), no. 2, 445–465, DOI 10.1007/s00454-014-9659-5. MR3316232,
Show rawAMSref \bib{GKM:computer}{article}{ author={G\"{a}hler, Franz}, author={Kwan, Eugene~E.}, author={Maloney, Gregory~R.}, title={A computer search for planar substitution tilings with {$n$}-fold rotational symmetry}, date={2015}, issn={0179-5376}, journal={Discrete Comput. Geom.}, volume={53}, number={2}, pages={445\ndash 465}, doi={10.1007/s00454-014-9659-5}, review={\MR {3316232}}, } 
[GL89]
C. Godrèche and J. M. Luck, Quasiperiodicity and randomness in tilings of the plane, J. Statist. Phys. 55 (1989), no. 1-2, 1–28, DOI 10.1007/BF01042590. MR1003500,
Show rawAMSref \bib{GL:random}{article}{ author={Godr\eche, C.}, author={Luck, J.~M.}, title={Quasiperiodicity and randomness in tilings of the plane}, date={1989}, issn={0022-4715}, journal={J. Statist. Phys.}, volume={55}, number={1-2}, pages={1\ndash 28}, doi={10.1007/BF01042590}, review={\MR {1003500}}, } 
[GMRS23]
P. Gohlke, A. Mitchell, D. Rust, and T. Samuel, Measure Theoretic Entropy of Random Substitution Subshifts, Ann. Henri Poincaré 24 (2023), no. 1, 277–323, DOI 10.1007/s00023-022-01212-x. MR4533524,
Show rawAMSref \bib{GMRS:entropy}{article}{ author={Gohlke, P.}, author={Mitchell, A.}, author={Rust, D.}, author={Samuel, T.}, title={Measure {T}heoretic {E}ntropy of {R}andom {S}ubstitution {S}ubshifts}, date={2023}, issn={1424-0637}, journal={Ann. Henri Poincar\'{e}}, volume={24}, number={1}, pages={277\ndash 323}, doi={10.1007/s00023-022-01212-x}, review={\MR {4533524}}, } 
[GT22]
Rachel Greenfeld and Terence Tao, A counterexample to the periodic tiling conjecture, Preprint, arXiv:2209.08451, 2022.,
Show rawAMSref \bib{GT:periodic}{eprint}{ author={Greenfeld, Rachel}, author={Tao, Terence}, title={A counterexample to the periodic tiling conjecture}, date={2022}, arxiv={2209.08451}, } 
[GS16]
B. Grünbaum and G.C. Shephard, Tilings and patterns, Second Edition, Dover Books on Mathematics Series, Dover Publications, Incorporated, 2016.,
Show rawAMSref \bib{GS:book}{book}{ author={Gr{\"u}nbaum, B.}, author={Shephard, G.C.}, title={Tilings and patterns}, edition={Second Edition}, series={Dover Books on Mathematics Series}, publisher={Dover Publications, Incorporated}, date={2016}, isbn={9780486469812}, url={https://books.google.com/books?id=zY6nPwAACAAJ}, } 
[JS18]
Antoine Julien and Lorenzo Sadun, Tiling deformations, cohomology, and orbit equivalence of tiling spaces, Ann. Henri Poincaré 19 (2018), no. 10, 3053–3088, DOI 10.1007/s00023-018-0713-3. MR3851781,
Show rawAMSref \bib{JulienSadun:deformations}{article}{ author={Julien, Antoine}, author={Sadun, Lorenzo}, title={Tiling deformations, cohomology, and orbit equivalence of tiling spaces}, journal={Ann. Henri Poincar\'{e}}, volume={19}, date={2018}, number={10}, pages={3053--3088}, issn={1424-0637}, review={\MR {3851781}}, doi={10.1007/s00023-018-0713-3}, } 
[KLS15]
Johannes Kellendonk, Daniel Lenz, and Jean Savinien (eds.), Mathematics of aperiodic order, Progress in Mathematics, vol. 309, Birkhäuser/Springer, Basel, 2015, DOI 10.1007/978-3-0348-0903-0. MR3380566,
Show rawAMSref \bib{AO:book}{collection}{ title={Mathematics of aperiodic order}, series={Progress in Mathematics}, volume={309}, editor={Kellendonk, Johannes}, editor={Lenz, Daniel}, editor={Savinien, Jean}, publisher={Birkh\"{a}user/Springer, Basel}, date={2015}, pages={xi+428}, isbn={978-3-0348-0902-3}, isbn={978-3-0348-0903-0}, review={\MR {3380566}}, doi={10.1007/978-3-0348-0903-0}, } 
[Lan40]
C. Dudley Langford, 1464. uses of a geometric puzzle, The Mathematical Gazette 24 (1940), no. 260, 209–211.,
Show rawAMSref \bib{langford_1940}{article}{ author={Langford, C.~Dudley}, title={1464. uses of a geometric puzzle}, date={1940}, journal={The Mathematical Gazette}, volume={24}, number={260}, pages={209--211}, } 
[MRST22]
Eden Miro, Dan Rust, Lorenzo Sadun, and Gwendolyn Tadeo, Topological mixing of random substitutions, Israel J. Math., posted on 2022, DOI 10.1007/s11856-022-2406-3.,
Show rawAMSref \bib{MRST:mixing}{article}{ author={Miro, Eden}, author={Rust, Dan}, author={Sadun, Lorenzo}, author={Tadeo, Gwendolyn}, title={Topological mixing of random substitutions}, date={2022}, journal={Israel J. Math.}, doi={10.1007/s11856-022-2406-3}, } 
Lorenzo Sadun, Topology of tiling spaces, University Lecture Series, vol. 46, American Mathematical Society, Providence, RI, 2008, DOI 10.1090/ulect/046. MR2446623,
Show rawAMSref \bib{sadun:book}{book}{ author={Sadun, Lorenzo}, title={Topology of tiling spaces}, series={University Lecture Series}, volume={46}, publisher={American Mathematical Society, Providence, RI}, date={2008}, pages={x+118}, isbn={978-0-8218-4727-5}, review={\MR {2446623}}, doi={10.1090/ulect/046}, } 
[Sol97]
Boris Solomyak, Dynamics of self-similar tilings, Ergodic Theory Dynam. Systems 17 (1997), no. 3, 695–738, DOI 10.1017/S0143385797084988. MR1452190,
Show rawAMSref \bib{solomyak:SS}{article}{ author={Solomyak, Boris}, title={Dynamics of self-similar tilings}, journal={Ergodic Theory Dynam. Systems}, volume={17}, date={1997}, number={3}, pages={695--738}, issn={0143-3857}, review={\MR {1452190}}, doi={10.1017/S0143385797084988}, } `

## Credits

Opening image and Figures 2, 3, 7, and 9 are courtesy of Rodrigo Treviño.

Figure 1 is in the public domain.

Figure 4 is courtesy of ©The Board of Trustees of the Science Museum. Licensed under CC-BA-SA 4.0.

Figure 5 is courtesy of the United States Patent and Trademark Office.

Figure 6 is reprinted with permission from D. Shechtman et al., “Metallic Phase with Long-Range Orientational Order and No Translational Symmetry,” Physical Review Letters 53, 1951. Copyright (1951) by the American Physical Society.

Figure 8 is courtesy of D. Frettlöh, E. Harriss, F. Gähler: Tilings encyclopedia, https://tilings.math.uni-bielefeld.de/. Licensed under CC-BY-Sa 2.0.

Photo of Rodrigo Treviño is courtesy of Laurie DeWitt, Pure Light Images.