Distortion Reversal in Aperiodic Tilings

Herein we prove that homeomorphic images of certain two-dimensional self-similar aperiodic tilings are recognizable, in both mathematical and practical senses. In the practical sense our results say it is possible to search for and recognize distorted aperiodic structures, for example in natural and physical settings. We recall that the mathematical discovery of aperiodic tilings by Penrose in 1972 and Ammann in 1975 preceded the discovery by Shechtman in 1982 of quasicrystals, and the subsequent examples of quasicrystals in meteorites in 2009 [13].

In this paper we focus on Ammann-A2 tilings [2], but the ideas are more generally applicable. Our results illustrate that aperiodic tilings can be retrieved from their images distorted by unknown homeomorphisms. For example, we show how distorted Ammann-A2 tilings, such as the ones in Figure 1, are recognizable both practically and mathematically. In Figure 2 an algorithm (without knowledge of the distorting homeomorphism) is applied to the distorted tiling to successively retrieve a patch of the original Ammann-A2 tiling.

The situation is a bit strange: the unknown distortion may be such as to change the Hausdorff dimension of the boundaries of the tiles in a very rough way, or to transform an Ammann-A2 tiling to a tiling by triangles. Nevertheless, the key properties of the tiling may still be discernable.

There is a substantial literature on the occurrence of two-dimensional tilings in physics [14]. Many of these are distortions of tilings by hexagons. Many naturally occurring tilings have an average of six faces per tile, and typical tiles are hexagons. Ammann-A2 tiles are hexagonal and comprise among the simplest of self-similar tilings. Despite this, they do not seem to show up in nature. Are they hiding in plain sight? We provide some tools which may be applied to this question.

Let $P$ be a finite aperiodic prototile set. This means that there exist tilings of the plane by copies of the tiles in $P$, but every such tiling is non-periodic, i.e., has no translational symmetry. Such tilings have been objects of fascination, both in research and recreational mathematics, since their introduction in the 1960’s. The most well-known such prototile set consists of the two Penrose tiles. To develop the ideas in this paper we concentrate, because of their simplicity, on tilings based on the set of two Ammann-A2 tiles. There are uncountably many corresponding Ammann-A2 tilings, obtained either by matching rules or by substitution rules. Basic properties of such Ammann-A2 tilings are provided in Section 3.

Many non-periodic tilings have a hierarchical structure, meaning that if $T$ is such a tiling, then there exist a sequence of tilings $T=\overline{T}_{0},\overline{T}_{1},\overline{T}_{2},\dots$, such that, for all $n\geq 1$, each tiling in $\overline{T}_{n}$ is the non-overlapping union of tiles in $\overline{T}_{n-1}$. For the Ammann-A2 tilings, the tiling $\overline{T}_{n}$, appropriately scaled, is again an Ammann-A2 tiling. Specifically, there is a constant $s$ such that $T_{n}:=s^{n}\overline{T}_{n}$ is an Ammann-A2 tiling for all $n$. There is a well-defined procedure, which we call amalgamation, taking $T_{n}$ to $T_{n+1}$, and denoted $T_{n+1}=a(T_{n})$. Amalgamation and hierarchy for the Ammann-A2 tilings is explored in Section 4.

Here is the question that is the subject of this paper. Suppose that we are given a distorted version $T^{\prime}$ of an Ammann-A2 tiling $T$. Specifically, there is an unknown (not revealed to us) homeomorphism $h$ of the plane such that $T^{\prime}=h(T)$. Is it possible to retrieve the undistorted Ammann-A2 tiling $T$ from its distorted image $T^{\prime}$ - without knowledge of $h$? As long as the distance between any point $x$ in the plane and its image $h(x)$ is bounded, we answer this question in the affirmative. Suppose that amalgamation can be carried over to the distorted tiling $T^{\prime}$. Then Section 5 contains the following somewhat surprising result: if $T^{\prime}_{n}=a^{n}(T^{\prime}),\,n\geq 0,$ are the tilings obtain by successive application of the amalgamation operator $a$ applied to the distorted image $T^{\prime}$, then the sequence $\{T_{n}\}$ of tilings converges, in the sense of Theorem 1 in Section 5 and Remark 1, to the original tiling $T$. This is illustrated in Figure 2.

The above distortion reversal result is predicated on being able to amalgamate tiles of the distorted tiling $T^{\prime}$, a tiling in which metric and geometric properties of the original tiling are lost. Only the combinatorial properties of $T$ are carried over to $T^{\prime}$. In Section 6 we obtain, completely combinatorially, the needed amalgamation operator $a$ applied to $T^{\prime}$. This is done in Algorithm A in Section 6; see Theorem 2. Of course, the plane and tilings of it, are unbounded. We would like to perform the distortion reversal efficiently on a large patch of the tiling $T^{\prime}$, say on a patch that contains the disk $D_{R}$ of radius $R$ centered at the origin. Algorithm B, a variation of Algorithm A, accomplishes this. Theorem 3 in Section 6 states that each application of the combinatorial amalgamation applied to such a patch can be performed in running time $O(R^{2})$.

An alternative method for reversing the distortion in an Ammann-A2 tiling is provided in Section 7. It uses the combinatorial amalgamation operator applied to the distorted tiling $T^{\prime}$ to generate an infinite binary string $c$, called the code of the tiling. The code is the input for an iterated function system based method to retrieve the original tiling $T$. This method, encapsulated in Theorem 4 of Section 7, has the advantage that there is no restriction on the homeomorphism $h$. It has the disadvantage that there is no sequence of increasingly accurate images converging to the original tiling $T$; it simply produces $T$ or, in finite time, an arbitrarily large patch of $T$.

In this paper a tile is defined as a set in the plane homeomorphic to a closed disk. A tiling of the plane is a set of non-overlapping tiles whose union is ${\mathbb{R}}^{2}$. By non-overlapping is meant that the intersection of any two distinct tiles has empty interior. For all tilings in this paper, the intersection of any two distinct tiles is connected (possibly empty). A patch of a tiling is a finite number of tiles whose union is a topological disk.

The classical Ammann-A2 hexagon $G$, sometimes referred as the golden bee, is depicted in Figure 3. It is the only polygon, other than any right triangle and any parallelogram with side lengths in the ratio $\sqrt{2}:1$, that is the non-overlapping union of two smaller similar copies of itself [12]. These two smaller copies are isometric to $sG$ and $s^{2}G$, where $s=1/\tau$ and $\tau$ is the square root of the golden ratio, i.e., $\tau$ is the positive real root of $x^{4}-x^{2}-1=0$.

An Ammann-A2 tiling is a tiling of the plane by non-overlapping isometric copies of $sG$ and $s^{2}G$, which we will refer to as the large and small tiles, respectively. The tiling must obey matching rules dictated by the elliptical markings on the upper tiles of the left panel in Figure 4. Other alternative but equivalent sets of markings are also possible, for example the markings shown in the right panel of Figure 4. Although the decorations on small and large tiles at the top of the left panel and the decorations on the small and large tiles of the right panel differ, matching according to either set of decorations define the Ammann-A2 tilings, as observed in [7, p. 551]; see also [1, 2, 4, 10].

Hereafter we will call an Ammann-A2 tiling simply an Ammann tiling. A portion of an Amman tiling is shown in Figure 5. Two tilings $T$ and $T^{\prime}$ are said to be congruent if there is an isometry $U$ such that $T^{\prime}=U(T)$. Much has been written on Ammann tilings both in mathematics journals, for example [4, 7] and in recreational sources, notably [8, 11]. There are uncountable many Ammann tilings, each being non-periodic. Every Ammann tiling is repetitive and every pair of Ammann tilings are locally isomorphic. A tiling $T$ is repetitive, also called quasiperiodic, if, for every finite patch $P$ of $T$, there is a real number $R$ such that every ball of radius $R$ contains a patch congruent to $P$. Two tilings are locally isomorphic if any patch in either tiling also appears in the other tiling.

The Ammann tilings may be defined, as an alternative to matching rules, by substitution rules, see [4, 6]. Another method of construction appears in [3] and is used in Section 7 of this paper.

Let $T$ be an Ammann tiling. For each small tile $\mathsf{s}$ in $T$, there is a partner, defined as the unique large tile $\mathsf{b}$ in $T$ such that the union of $\mathsf{s}$ and $\mathsf{b}$, called the amalgamation of $\mathsf{s}$ and $\mathsf{b}$, is a hexagon congruent to $G$. Any two distinct small tiles have distinct partners. The tiling obtained from $T$ by amalgamating each small tile with its partner is denoted $A(T)$. The scaled tiling $a(T):=sA(T)$ is an Ammann tiling called the amalgamation of $T$.

Related comments on matching rules for the Ammann tilings are given in [1, 2, 4]. In particular see [1] for a discussion of replacement of markings and the notion of ghost markings. Equivalence of different sets of markings is discussed in [10].

The sequence of tilings $H(T):=\{T,A(T),A^{2}(T),\dots\}$, consisting of Ammann tilings at larger and larger scales, will be referred to as the hierarchy of $T$. In general, if $t$ is any tile at any level of the hierarchy, then $t$ is the non-overlapping union of tiles in $T$. Denote this tiling of $t$ by $\mathcal{T}(t)$. The tiling $\mathcal{T}(t)$ is sometimes referred to as a supertile in the tilings literature; see for example [5, 7, 9]. Any large tile $t$ in $A^{n}(T)$ is congruent to $\tau^{n-1}(G)$. For such a large tile $T$ in $A^{n}(T)$, denote $\mathcal{T}(t)$ by $\mathcal{T}_{n}$ which, by Proposition 4.2 below, is well-defined, independent of $t$. The tiling $\mathcal{T}_{6}$ appear in Figure 6.

Lemma  1 below is needed to prove a main result in Section 6. We first introduce a useful combinatorial notion. Define a planar map $M$ to be a 2-cell embedding of a locally finite simple graph $\Gamma$ in the plane. By locally finite is meant that the degree of each vertex is finite, and by simple is meant no loops or multiple edges. The faces of $M$ are the closures of the connected components of ${\mathbb{R}}^{2}\setminus\Gamma$. By $2$-cell embedding is meant that each face of $M$ is homeomorphic to a closed disk. Two planar maps $M$ and $M^{\prime}$ with underlying graphs $\Gamma$ and $\Gamma^{\prime}$, respectively, are isomorphic if there is a graph isomorphism taking $\Gamma$ to $\Gamma^{\prime}$ that preserves faces.

A tiling $T$ can be considered a planar map. A vertex of $T$ is the intersection point of three or more distinct tiles of $T$, assuming that the intersection is not empty, and an edge of $T$ is the intersection, if not empty or a single point, of two distinct tiles of $T$. The faces of $T$ are the tiles of $T$.

From an Ammann tiling $T$, a tiling $\widehat{T}$ is constructed as follows. Note that the degree (number of incident edges) of any vertex of an Ammann tiling $T$ is either $3$ or $4$. Color red each edge of $T$ (and its two incident vertices) that joins two vertices of degree $4$. For any red vertex lying on only one red edge, remove the color red from that vertex and remove the incident edge. Let $\widehat{T}$ be the tiling induced by the red edges and vertices, i.e., by removing all edges and vertices not colored red. For any face $f$ of $\widehat{T}$, it’s red boundary $\partial f$ together with all enclosed tiles of $T$ is a finite tiling which is denoted $T(f)$.

Let $\mathbb{X}$ denote the set of tilings as defined in Section 3. For a tiling $T\in\mathbb{X}$, let $\partial T$ denote the union of the boundaries of the tiles of $T$. Define a distance function on $\mathbb{X}$ as follows.

where $d_{H}$ is the Hausdorff distance. Intuitively, the $d$-distance between tilings is small if the tilings are almost the same over the entire plane. The next corollary follows immediately from Lemma 2.

If $T$ is an Ammann tiling and $h$ is a homeomorphism of the plane, then $h$ acts on $T$. Let $T^{\prime}=h(T)$ be the image of an Ammann tiling $T$ under a homeomorphism $h$. The small and large tiles in $T^{\prime}$ are defined to be the images of the small and large tiles in $T$. If $\mathsf{s}^{\prime}$ is a small tile in $T^{\prime}$ corresponding to a small tile $\mathsf{s}$ in $T$, then the partner of $\mathsf{s}^{\prime}$ is the image under $h$ of the partner of $\mathsf{s}$. Therefore the amalgamation $a(T^{\prime})$ and the hierarchy $H(T^{\prime})$ can be defined for $T^{\prime}$ exactly as they are for $T$.

Let $\mathbb{T}$ be the set of all images of Ammann tilings of the plane under homeomorphisms of the plane. Essential to Theorem 1 is being able to apply the amalgamation operator $a:\mathbb{T}\rightarrow\mathbb{T}$. Let $T$ be an Ammann tiling and $T^{\prime}=h(T)$, where $h$ is a homeomorphism of the plane. In this section it is proved that $a(T^{\prime})$ can be determined combinatorially, without knowledge of the homeomorphism $h$.

The proof of Theorem 2 appears after a few simple lemmas. With terminology from Section 4, the following lemma is clear.

Two planar maps $M_{1}$ (left) and $M_{2}$ (right) are shown in Figure 7 (ignoring the dots and arrows). Recalling the definition of $\mathcal{T}_{n}$ from Section 4, the following two lemmas are apparent by inspection.

Each arrow in Figure 7 points from a face bounded by a $4$-cycle to an adjacent face. A consequence of Lemma 5 is that, if $M$ is any planar map isomorphic to $M_{1}$ or $M_{2}$ in Figure 7, then arrows can be uniquely assigned to $M$ such that there is an arrow from face $f_{1}$ to $f_{2}$ in $M$ if and only if there is an arrow from $\phi(f_{1})$ to $\phi(f_{2})$ in $M_{1}$ or $M_{2}$, where $\phi$ is the isomorphism.

unknown homeomorphism.

Perform the following steps to obtain the tiling $a(T^{\prime})$ from $T$.

1. (1)

   Color red each edge (and its two incident vertices) of $T^{\prime}$ that joins two vertices of degree $4$. But, for any red vertex lying on only one red edge, remove the color red from that vertex and remove the incident edge.

2. (2)

   Let $\widehat{T^{\prime}}$ be the tiling induced by just the red edges and vertices of $T^{\prime}$, i.e., by removing all edges and vertices not colored red.

3. (3)

   For every tile $f\in\widehat{T^{\prime}}$, let $T^{\prime}(f)$ be the set of tiles of $T^{\prime}$ contained in $t$. Viewed as a planar map, each $T^{\prime}(f)$ is isomorphic to one of the planar maps in Figure 7. (This is shown to be the case in the proof below of Theorem 2.) For every $f\in\widehat{T^{\prime}}$ do:

   • •

     For every tile $\mathsf{s}$ of $T^{\prime}(f)$ that is bounded by a $4$-cycle, do:

     • –

       Locate the partner $\mathsf{b}$ of $\mathsf{s}$ using the relevant arrow in Figure 7.

     • –

       Replace the two tiles $\mathsf{s}$ and $\mathsf{b}$ in $T^{\prime}$ by their union to form a single tile in $A(T^{\prime})$, and hence in $a(T^{\prime})$ after scaling by $s=1/\tau$.

Algorithm A acts on the tiling $T^{\prime}$ of the entire plane and hence does not run in finite time. From a practical point of view, it may be asked whether it is possible to efficiently compute the amalgamation of the distorted tiling $T^{\prime}$ on a finite subset of the plane, for instance on a patch containing the disk $D_{R}$ of radius $R$ centered at the origin. We tweak Algorithm A to obtain a combinatorial Algorithm B that applies to a finite patch of a tiling. Algorithm B computes $a(T^{\prime})$ on $D_{R}$ and runs in time quadratic in $R$. This is the content of Theorem 3 below. Figure 8 illustrates Algorithm A above and Algorithm B below, showing the red edges of a distorted Ammann tiling before and after the red edges that do not belong to cycles are removed.

The notation $T^{\prime}|R$ and $a(T^{\prime}|R)$ in Theorem 3 are defined as follows. If $T^{\prime}$ is a tiling, $T^{\prime}|R$ the set of tiles of $T^{\prime}$ with non-empty intersection with $D_{R}$. If $T^{\prime}$ is an Ammann tiling or a homeomorphic image of an Ammann tiling, the amalgamation $a(T^{\prime}|R)$ is obtained by replacing every small tile $t$ in $T|R$ by the union of $t$ and its partner - even if the partner of $t$ has empty intersection with $D_{R}$.

unknown homeomorphism of bounded distortion $C$, and a positive real

number $R$.

1. (1)

   Set $\widehat{R}=R+2C+\tau^{6}$ Perform the following steps to obtain the tiling $T^{\prime\prime}$ from the tiling $T^{\prime}|\widehat{R}$:

2. (2)

   Color some edges and vertices of $T^{\prime}|\widehat{R}$ red according to the following rules:

   • •

     Color red each edge (and its two incident vertices) of $T^{\prime}|\widehat{R}$ that joins two vertices of degree $4$.

   • •

     Remove the color red from any red vertex or edge not lying on a red cycle in $T^{\prime}|\widehat{R}$.

3. (3)

   Let $\widehat{T^{\prime}}$ be the tiling induced by the red edges and vertices of $T^{\prime}|\widehat{R}$.

4. (4)

   For every tile $t\in\widehat{T^{\prime}}$, let $T^{\prime}(t)$ be the set of tiles of $T^{\prime}|\widehat{R}$ contained in $t$. Viewed as planar map, each $T^{\prime}(t)$ is isomorphic to one of the planar maps in Figure 7. For every $t\in\widehat{T^{\prime}}$ do:

   • •

     For every tile $\mathsf{s}$ of $T^{\prime}(t)$ that is bounded by a $4$-cycle, do:

     • –

       Locate the partner $\mathsf{b}$ of $\mathsf{s}$ using the the relevant arrow in Figure 7.

     • –

       Replace the two tiles $\mathsf{s}$ and $\mathsf{b}$ in $T^{\prime}|\widehat{R}$ by their union to form a single tile in $T^{\prime\prime}$.

Let $T$ be an Ammann tiling and $T^{\prime}=h(T)$, where $h$ is a homeomorphism of the plane. In this section we extract from $T^{\prime}$, without using $h$, an infinite binary string $\theta=\theta_{1}\,\theta_{2}\,\,\theta_{3}\cdots$. A tiling $T(\theta)$ will be combinatorially constructed from $\theta$ such that $T=T(\theta)$.

Theorem 4 below states that $c(T^{\prime},t^{\prime})$ completely determines the original Ammann tiling $T$, and can be used to generate $T$. An intuitive way to see this is to start with a patch $P_{0}$ consisting of a single large Ammann tile $t$. Let $c(T,t)=c_{1}\,c_{2}\,\cdots$. If $c_{1}=1$, embed $P_{0}$ in a patch $P_{1}$ as shown at the start of the bottom row in Figure 9; if $c_{1}=2$, embed $P_{0}$ in a patch $P_{1}$ as at the start of the top two rows in Figure 9. Continue in this way to get a nested sequence of patches as in Figure 9. The nested union is $T$.

A more rigorous formulation of the above method of retrieving the original tiling from the code uses the following combinatorial construction. Recall that $s=1/\tau$, where $\tau$ is the square root of the golden ratio. The fact that the golden bee $G$ is the non-overlapping union of two small similar copies of itself can be stated more precisely as follows.

where $f_{1}(G)$ and $f_{2}(G)$ are non-overlapping and

For $\sigma=\sigma_{1}\,\sigma_{2}\,\dots\,\sigma_{k}\in\{1,2\}^{*}$ let

and let $\sigma_{*}:=\sigma_{k}$ denote the last term in the string $\sigma$. We introduce the notation

and

for $\theta=\theta_{1}\,\theta_{2},\cdots\in\{1,2\}^{\infty}$. By convention, $\theta|0$ is the empty string $\emptyset$; $e(\emptyset)=0$, and $f_{\emptyset}$ is the identity.

Let

Intuitively, the finite strings $\sigma\in W(\theta,k)$ are those whose sum differs from the sum of the elements of $\theta|k$ by zero or one. This forces each tile $t(\theta,k,\sigma)$ in Definition 3 below to be congruent to either a large or small Ammann tile.