Sub Rosa, A System of Quasiperiodic Rhombic Substitution Tilings with n-Fold Rotational Symmetry

Abstract

In this paper we prove the existence of quasiperiodic rhombic substitution tilings with 2n-fold rotational symmetry, for any n. The tilings are edge-to-edge and use $\lfloor {\frac{n}{2}\rfloor }$ rhombic prototiles with unit length sides. We explicitly describe the substitution rule for the edges of the rhombuses, and prove the existence of the corresponding tile substitutions by proving that the interior can be tiled consistently with the given edge substitutions.

1 Introduction

A tiling is a covering of the infinite plane using copies of a finite number of different prototiles, without leaving gaps or letting the tiles overlap. In this paper we consider edge-to-edge substitution tilings of the plane with rhombuses whose edges are of unit length. The edge-to-edge condition means that two tiles in the tiling are either disjoint, have one common vertex or have one common edge. A substitution rule tells how to replace enlarged tiles by patches of tiles. By iterating the process of inflating the tiles and substituting the corresponding patches, one obtains a sequence whose limit is a tiling of the infinite plane. Such substitutions are a popular way to produce non-periodic tilings. The Penrose tilings [4, 9] are the best known examples of this effect.

We say that a tiling has n-fold rotational symmetry (with center P) if the tiling is invariant under the rotation around P by the angle $\frac{2\pi }{n}$. Note that this requires a perfect global symmetry of the entire tiling. There may exist an infinite number of centers of rotation for n-fold rotations only if $n=2,3,4$ or 6. For all other values there can be at most one central point of rotational symmetry. This fact is known as the crystallographic restriction.

All our tilings are by rhombic prototiles with unit length sides. As usual we shall define the substitution process in two steps. A tile is first enlarged by a constant called the scaling factor. The enlarged tile is then replaced by a patch of prototiles that cover the same area as the enlarged tile does. This second step is called the substitution rule. The boundaries of this new replaced tile do not have to go along the boundaries of the merely enlarged tile but their areas have to be equal. If there are some kind of “dips” inwards in the perimeter of the replaced tile also corresponding “dips” outwards have to exist and in the right places, so that no overlapping occurs along the edge of two neighbouring enlarged tiles. This condition can be guaranteed by an associated edge substitution rule.

Starting with any tile, the substitution process may be iterated to obtain higher order images. The substitution is primitive if there exists k such that the k’th order image of every tile contains a copy of every prototile. All our substitutions will be primitive with $k=1$, so that each tile appears in the image of each tile.

A substitution tiling is any non-overlapping covering of the plane by the tiles such that every finite patch of tiles present in the tiling appears in some higher order image of some tile. Such patches are called legal. In practice, we generate tilings by iterating the substitution from an initial patch of tiles, positioning the obtained patches so that each generation properly contains the previous one in its interior, and take the limit of the process. If the initial patch is such that it appears in a higher order image of some tile then the obtained limit is clearly a substitution tiling.

A tiling is recurrent if every finite patch of tiles that appears in the tiling appears infinitely many times in it. It is uniformly recurrent (or quasiperiodic, or repetitive [1]) if every finite patch that appears somewhere in the tiling appears within distance D of every point of the plane, for some D. The value D may depend on the patch. If D can be bounded by a linear function of the diameter of the patch then the tiling is linearly recurrent, or linearly repetitive [1]. Tilings generated by primitive substitutions are automatically uniformly recurrent. Indeed, any finite patch that appears in a tiling is legal, i.e., appears in some higher order image of some tile, and by primitivity then, in the m’th order image of every tile, for some m. Radius D can be taken to be the maximum diameter of the m’th order images of the tiles. A more careful analysis reveals that our tilings are even linearly recurrent.

In this paper we are considering the problem of finding a primitive substitution that generates a tiling with n-fold rotational symmetry. Values $n=2,3,4$ and 6 are trivial, and there are even periodic solutions: The regular square tiling for $n=4$ and the case $n=6$ are considered below as the first member of the Sub Rosa family. The famous Penrose rhombuses provide a solution to the case $n=5$ [4, 5, 9], and the Ammann–Beenker tiling for $n=8$ [2]. Recently, in [3] a computer algorithm was described to search for solutions for arbitrary n. Many substitution rules were discovered for $n=5$ and $n=7$, but the computational complexity of the problem was reported to be prohibitive already in the case $n=11$.

We are not aware of known solutions for general n. In [6] primitive rhombic substitutions were provided for all n that can be iterated on an n-fold rotationally symmetric initial patch to obtain in the limit a tiling with n-fold symmetry. However, the initial patch does not appear in any higher order image of any tile, so the obtained tiling is “singular” and not a substitution tiling according to the stricter definition of the present paper. Moreover, the tiling is not recurrent, since the initial patch only appears once in the tiling. In [6] the term non-singular substitution tiling was used to describe the type of substitution tilings used in the present paper.

The main result is the following theorem.

Theorem 1

For every n, there exists a quasiperiodic rhombic substitution tiling with 2n-fold rotational symmetry.

We start by setting the notations in Sect. 2. The discussion is then divided in two parts, depending on whether n is odd or even. In Sect. 3 we show, as examples, our substitutions for small odd n, and discuss the scaling factors and the edge substitution rules for arbitrary odd n. Section 4 provides the analogous discussion for even n. In Sect. 5 we provide the main proof. We explicitly describe the edge substitution rule, and express the boundary of the enlarged rhombus as a circular word of unit vectors. In Sect. 5.1 we develop a rewrite system on the boundary word to check the tileability of the interior. In Sect. 5.2 the notation is set up for the complete case analysis that we do in Sect. 5.3.

2 Notations

We use only rhombic tiles. Let $n\ge 2$ be a fixed integer. For any positive integers x and y that satisfy $x+y=n$, we denote by pair (x, y) the rhombus with unit length edges, and angles $\frac{x\pi }{n}$ and $\frac{y\pi }{n}$. Pairs (x, y) and (y, x) are the same shape. These $\lfloor \frac{n}{2}\rfloor$ unit rhombuses are used in our 2n-fold symmetric solutions. We label the corners of the (x, y) rhombus by x and y. In a valid edge-to-edge tiling then, the labels of the corners meeting at a vertex have to sum up to 2n. The patch of tiles that is an image of a rhombus under our substitution is called a super-rhombus.

The system described here utilizes a rotational and reflection symmetric simple arrangement of rhombuses around a single point. We present here two such patterns: The first one has n-fold rotational symmetry, the second one 2n-fold symmetry.

First we construct the smaller pattern where we assume $n\ge 3$. We place n copies of $(2,n-2)$-rhombuses around a point with their $\frac{2\pi }{n}$ vertices meeting at the point. This pattern is surrounded by a ring of n copies of $(4,n-4)$-rhombuses. These properly match at the corners since $(n-2)+(n-2)+4$ equals 2n. This pattern is in turn surrounded by a ring of $(6,n-6)$ rhombuses, then by $(8,n-8)$ rhombuses, and so on. This procedure is repeated until the outmost ring of $(n-1,1)$ or $(n-2,2)$ is reached, depending on whether n is odd or even. On each step, the angles add up properly at each vertex: on the k’th round the four meeting angles have labels $2(k-1)$, $n-2k$, $n-2k$ and $2(k+1)$, and these add up to 2n. Note that this analysis also holds on the first round $k=1$, with the interpretation that the process is initialized with n zero rhombuses, i.e., mere edges.

The boundary of the obtained pattern is a regular 2n-polygon with edges of length 1, if n is odd, and a regular n-polygon with edges of length 2 when n is even. The patterns for $n=3,4,\dots , 8$ are shown in Fig. 1.

Fig. 1

Rose $R_1$ for $n=3,4,5,6,7,8$

Secondly we construct the larger pattern. Here $n\ge 2$. We place 2n copies of $(1,n-1)$-rhombuses around a point with their $\frac{\pi }{n}$ vertices meeting at the point. This pattern is surrounded by a ring of 2n copies of $(2,n-2)$-rhombuses. Which in turn is surrounded by a ring of 2n copies of $(3,n-3)$-rhombuses. This procedure is repeated until we construct the outmost ring using $(n-1,1)$ rhombuses. The result is a regular 2n-polygon with edges of length 2. Again, it is straightforward to verify that the angles add up properly at each vertex. Also here we can imagine the zeroth round to consist of 2n zero rhombuses (= unit edges) around the central point.

Frequently we leave out a number of outer rings. For example, Fig. 2 shows patterns for $n=2,3,\dots ,7$ where the last ring of $(n-1,1)$-rhombuses is omitted. Note that in the case $n=2$ the omission of the last ring leaves only the degenerate zeroth round.

Fig. 2

Rose $R_2^1$ for $n=2,3,4,5,6,7$

These patterns greatly resemble a flower with its petals and therefore we call them roses and denote them by $R_a^b$, where $a\in \{1,2\}$ denotes the type of the rose, and $b\in {\mathbb {N}}$ denotes number of missing rings. That is, the patterns shown in Fig. 1 are $R_1^0$, or simply $R_1$, and patterns in Fig. 2 are $R_2^1$. Roses $R_1^b$ have n-fold rotational symmetry while roses $R_2^b$ have 2n-fold rotational symmetry. Note that $R_1$ for even n only uses tiles (x, y) with even x and y. In fact, $R_2$ for any n is identical to $R_1$ for 2n. For $n\ge 6$ it is possible to construct even larger, a third type of rose-pattern with 2n-fold rotational symmetry. Examples of such larger type are in Figs. 6 and 8, and if completed, the result is a regular 2n-polygon with edges of length 4. However, this, or $R_1$, or any another possible new type of rose is not necessary to prove our main theorem. Instead, roses $R_2^1$ play a central role in the constructions.

The tilings discussed in this paper use substitutions and rose like patterns, the system is hence called Sub Rosa. We first consider separately the cases of odd n and even n, starting with the odd cases.

3 Scaling Factors and Substitution Rules for Odd n

For $n\in {\mathbb {N}}\setminus \{0\}$ we define S(n) to be the scaling factor of the substitution. For odd n,

$$\begin{aligned} S(n)=\cos \Big (\frac{\pi }{2n}\Big )/\sin ^2\Big (\frac{\pi }{2n}\Big ). \end{aligned}$$

(1)

3.1 Substitution Rule for $n=3$

For $n=3$ the Sub Rosa tiling is periodic. For the sake of completeness we will first examine the tiling for value $n=3$ before moving to the non-periodic tilings starting with $n=5$. For $n=3$ there is only one rhombus in the tile set, namely (1, 2). The substitution rule is shown on the left in Fig. 3. The enlarged rhombus is depicted with thick edges and is replaced by 12 rhombuses (1, 2). The edges of the enlarged rhombus bisect two unit rhombuses out of which one is counted in while the other one is counted out. The resulting tiling after one step of substitution on the starting pattern $R_2^1$ is seen on the right in Fig. 3.

Fig. 3

Substitution rule for $n=3$, and the rose $R_2^1$ for $n=3$ after one substitution

The following aspects are easy to see in the case $n=3$, but they also hold for the larger values of odd n.

• The edge substitution rule All edges of enlarged rhombuses bisect an identical sequence of unit rhombuses. The sequence has even length and it is mirror symmetric. If we represent each bisected unit rhombus as the label of its bisected angle, the edge substitution rule can be written down as the sequence $\Sigma (n)$ of these labels. For example, the edge substitution rule for the case $n=3$ is represented by the sequence $\Sigma (3)=1,1$ since the edge of an enlarged rhombus cuts two unit rhombuses along their long diagonals, bisecting their angles of label 1. The edge substitution rules for larger values of odd n are shown in Table 1.

• The edge substitution rule above guarantees that the super-rhombuses match each other without gaps or overlaps, so that tile substitutions are consistent. We simply include in the super-rhombus half of the unit rhombuses that are bisected by its edge. More precisely, when following the edges of the enlarged rhombus clockwise, we count in the first half of the bisected unit tiles of each edge and count out the second half. In this way each unit rhombus gets included exactly once since each orientation of an edge between two rhombuses is clockwise for one of the incident rhombuses and counterclockwise for the other.

• In an edge-to-edge tiling by super-rhombuses there are roses $R_2^1$ centered at all corners of the super-rhombuses. In other words, a super-rhombus has a sector of $R_2^1$ centered at each corner, and these four sectors together form the full $R_2^1$ rose. Combined with the fact that there is at least one unit rhombus vertex completely in the interior of each super-rhombus, this implies that the second order image of each tile contains pattern $R_2^1$. Also, since $R_2^1$ contains a copy of every prototile in our system, the patch substituted for each tile contains a copy of every prototile and the substitution is then primitive.

• We iterate the substitution from the starting pattern $R_2^1$. By the point above, the image of $R_2^1$ has $R_2^1$ at its center, so we can align the centers of consecutive generations and take the limit to obtain a substitution tiling, Sub Rosa. Strictly speaking, for odd n, the central rose $R_2^1$ quarter turns in each generation. The roses at even generations and odd generations properly align with each other, but between consecutive generations a quarter turn is required. The generated tiling is a fixed point of the second iterate of the substitution.

• In all our drawings the depicted unit rhombuses, in fact, come with an isometry $\varphi$ that maps a rhombic prototile T into the given position. Because the rhombuses have the dihedral $D_2$ symmetry group ($D_4$ in the case of a square), the image $\varphi (T)$ alone does not contain the full information about $\varphi$. To identify $\varphi$ uniquely, one may consider the unit rhombuses in our illustrations oriented. All tiles are positively oriented, i.e., they come with an even isometry. The orientations in the starting pattern $R_2^1$ are invariant under the 2n-fold rotational symmetry of the pattern, and the sectors of $R_2^1$ at the corners of super-rhombuses are oriented correspondingly to guarantee the proper orientations in the roses $R_2^1$ that are formed around the vertices of the super-rhombuses. Note that the orientation of tiles becomes irrelevant if the super-rhombuses have the same symmetries as the corresponding unit rhombus: in this case the substitution is deterministic even without knowing the orientations. We argue in Remark 2 in Sect. 5.1 that our substitutions can always be made with the necessary symmetries.

• We always iterate Sub Rosa from the start pattern $R_2^1$. As patch $R_2^1$ has 2n-fold rotational symmetry, the obtained tiling has that symmetry as well. As the substitution is primitive and the start pattern $R_2^1$ appears in the second order image of each tile, the tiling is uniformly recurrent.

Fig. 4

Substitution rule for $n=5$

3.2 Substitution Rules for $n=5$

For $n=5$ the tile set consists of two rhombuses, (1, 4) and (2, 3). The substitution rule is shown in Fig. 4. In the figure each integer label represents a multiple of $\frac{\pi }{5}$. It is easy to see that each meeting point of vertices sums up to 10 or in other words, is a full circle $2\pi$. All six points listed above for $n=3$ apply also here, as they do for all odd n. Figure 5 shows the first image of rose $R_2^1$. Note, again, roses $R_2^1$ centered at all corners of the super-rhombuses.

Fig. 5

Rose $R_2^1$ for $n=5$ after one substitution

3.3 Substitution Rules for $n=7$

The substitution rule for $n=7$ is shown in the Fig. 6. Similarly to case of $n=5$, it is easy to verify that at each intersection of rhombuses, the sum of the angles is $2\pi$.

Fig. 6

Super-rhombuses of substitution rule for $n=7$

3.4 Compositions of Super-Rhombus’ Edges

Every Sub Rosa tiling is formed in such a way that the edge of the super-rhombus bisects all unit rhombuses along it. The length of this edge is S(n), the scaling factor of the substitution.

Recall that we identify the edge substitution rule by the sequence $\Sigma (n)$ of the labels of the angles the edge bisects. In Table 1 is depicted the sequence $\Sigma (n)$ for small odd n, where symbol $\mid$ denotes the middle point of the edge. The underlined values in the table represent rhombuses which are inside roses $R^1_2$ centered at the corners of the super-rhombus. There is a simple rule to form $\Sigma (n)$: The first half of $\Sigma (n)$ consists of the (underlined) sequence $1,3,5,\dots ,(n-2)$, followed by the mirror images of the underlined parts of $\Sigma (3), \Sigma (5), \dots , \Sigma (n-2)$, that is, by 1, 31, 531, etc. The second half of $\Sigma (n)$ is the mirror image of its first half. This blueprint provides the edge substitution rule for all odd n.

Table 1 Composition of super-rhombus’ edges for first n given in unit rhombuses

We choose all the rhombuses on the left side of the midpoint to be counted in and all rhombuses on the right side of midpoint to be counted out from the super-rhombus. Any other partition would work as well, as long as it is mirror symmetric.

Diagonal measure is the length of the diagonal of a unit rhombus $(k,n-k)$ that bisects k, and is denoted by $d_n(k)$. The diagonal measure is given by the formula

$$\begin{aligned} d_n(k)=2\cos \Big (k\frac{\pi }{2n}\Big ). \end{aligned}$$

(2)

From $\Sigma (n)$ we can read the scaling factor S(n) as a sum of diagonal measures $d_n(k)$. For example, from $\Sigma (7)=1,3,5,1,3,1,1,3,1,5,3,1$ we obtain that

$$\begin{aligned} S(7)=2(d_7(1)+d_7(3)+d_7(5)+d_7(1)+d_7(3)+d_7(1)). \end{aligned}$$

From the proposed general structure of $\Sigma (n)$ for all odd n, we get

$$\begin{aligned} S(n)=(n-1)d_n(1)+(n-3)d_n(3)+\cdots +2d_n(n-2). \end{aligned}$$

The scaling factor in (1) was inferred from this relation to diagonal measures (2).

4 Substitution Rules for Even n

In this section we consider briefly Sub Rosa tilings for even values of n. Now the scaling factor is different

$$\begin{aligned} S(n)= \frac{2}{1-\cos \big (\frac{\pi }{n}\big )}. \end{aligned}$$

(3)

The smallest case $n=2$ has scaling factor 2: it is the square substitution where the square is replaced by four squares. The resulting tiling is the regular square tiling, which is also the only edge-to-edge rhombic tiling in this case.

Consider an arbitrary even $n\ge 2$.

• The edge substitution rule The edges of enlarged rhombuses bisect some unit rhombuses and coincide with the edges of some unit rhombuses. In the latter case we say the edge bisects a zero rhombus, and indicate such situation by label 0 in $\Sigma (n)$. The sequence $\Sigma (n)$ is mirror symmetric and of even length. This means that, as in the odd case, the super-rhombuses match each other without gaps or overlaps if we count in the super-rhombus the bisected tiles in the first half of $\Sigma (n)$, and count out the bisected tiles in the second half of $\Sigma (n)$. The edge substitution rules for small even n are shown in Table 2.

• The starting pattern is again $R_2^1$. All super-rhombuses have a sector of $R_2^1$ at each vertex, but now the sector is aligned so that the first label of $\Sigma (n)$ is 0 rather than 1. This means that the image of $R_2^1$ contains at its center $R_2^1$ in its original orientation. In other words, no quarter rotation is needed to match consecutive generations, and the final tiling is a fixed point of the substitution.

• The general structure of $\Sigma (n)$ for even n is analogous to the odd case: The first half of $\Sigma (n)$ consists of the (underlined) sequence $0,2,4,\dots ,(n-2)$, followed by the mirror images of the underlined parts of $\Sigma (2)$, $\Sigma (4), \dots , \Sigma (n-2)$, that is, by 0, 20, 420, etc. The second half of $\Sigma (n)$ is the reversal of the first half. The obtained word is a palindrome of even length.

Table 2 Composition of super-rhombus’ edges for first even n

Rose $R_2^1$ for $n=4$ after one substitution can be seen in Fig. 7. For $n=6$ the substitution rule is shown in the Fig. 8.

Fig. 7

Rose $R_2^1$ for $n=4$ after one substitution

Fig. 8

Super-rhombuses of the substitution rule for $n=6$

5 General Case

We have shown substitution rules for small values of n. In the following we demonstrate that analogous substitutions exist for all values of n, thus proving Theorem 1. We use the explicit description of super-rhombuses’ boundaries as in Tables 1 and 2. Then we use the method in [7, 8] to prove that the interior can be tiled with the unit rhombuses.

We first set our notations. Let n be fixed. All angles will be expressed in units $\frac{\pi }{n}$. Number 2n is the full circle so that angles are considered modulo 2n. Direction 0 is drawn horizontally to the right, so that directions $\frac{n}{2}$, n and $-\frac{n}{2}$ refer to up, left and down, respectively. For each direction x, the antiparallel direction $x+n$ is denoted by . Hence .

In Tables 1 and 2 the structure of super-rhombuses’ edges is given in terms of the unit rhombuses along edges. In the following it is more convenient to consider the sequence of unit vectors that enclose the interior that needs to be tiled. Each unit vector is represented by its direction, so the boundary word of the super-rhombus is the sequence of directions of the unit vectors on the boundary. This sequence is a cyclic word so that conjugate words uv and vu denote the same boundary, just with a different starting point. We read the boundary word counterclockwise. The unit rhombuses bisected by the super-edge are not included in interior to be tiled. This means that a unit rhombus $(a,n-a)$ on a super-edge of direction k contributes in the boundary word two unit vectors in directions $k+\frac{a}{2}$ and $k-\frac{a}{2}$, in this order.

In fact, we want to show that the interior can be tiled in such a way that sectors of rose $R_2^1$ appear centered at all four corners of the super-rhombus. The underlined symbols in Tables 1 and 2 are inside these roses so they get replaced by the boundary of the rose sector. As an example, Fig. 9 shows the boundary of the region to be tiled in the case of the (2, 3) super-rhombus. Note how the boundary traces the sectors of the $R_2^1$ roses at the corners.

Fig. 9

The boundary of the region to be tiled with unit rhombuses, in the case $n=5$ and super-rhombus (2, 3). Lines connect the matching pairs of unit vectors along the boundary. Each crossing of the lines corresponds to a unit rhombus in the interior. In this case, each crossing provides a properly oriented rhombus which means that the crossing condition is satisfied

We use the standard notations on words. If u and v are two words then uv is their concatenation. A concatenation of k copies of word u is denoted as $u^k$. Though individual letters a are directions, and hence numbers modulo n, the power notation $a^k$ represents the word $aa\dots a$ of length k (rather than number a to power k). We denote by $u^R$ the reversal of word u, that is, the word obtained by writing the letters of u in the reverse order. Word u is a palindrome if $u^R=u$. The empty word is denoted as $\varepsilon$. It has length zero. Sometimes, for clarity, we write words with commas separating the letters. So aabab and a, a, b, a, b denote the same word of length five.

For any direction x, we define the operation $\sigma _x$ on words that increments each letter by constant x. This corresponds to turning the entire path by angle x. In particular, $\sigma _n$ orients the path in the opposite direction. We extend the notation of antiparallelism to words so that denotes the path antiparallel to u, that is, half turned u.

Since the same palindromic edge substitution is used on all four edges of a super-rhombus, it easily follows that the contributions on the boundary word by opposite super-edges are antiparallel to each other, and the same holds for the contributions by the rose sectors at opposite corners of the super-rhombus. Hence the boundary word is of the form where u is the word through half of the boundary. It follows from this symmetry that, in each direction a, the boundary contains equally many unit vectors in directions a and . This is the balance condition in [7].

It is also easy to see that the boundary does not cross itself. Only in the case of the $(1,n-1)$ super-rhombus for odd n the roses at the opposite $n-1$ corners touch in the middle, but without crossing each other. In the terminology of [7] the boundary is simple.

Based on [7], to prove that the interior can be tiled with the unit rhombuses it only remains to show that the boundary vectors can be matched in an appropriate way. Each letter a on the boundary word must be matched with an occurrence of the antiparallel letter . A crossing is formed by two matched pairs and if they occur in the circular boundary word in the interleaved order . For each such crossing, it is required that the path forms a rhombus in the counterclockwise direction, that is, $a<b<a+n \pmod {2n}$. This is the crossing condition.

The convex crossing condition used in [7] is slightly weaker as it also allows crossings between matched pairs and with the same labels. We prefer to forbid this because we then get unique matchings: In our setup, all occurrences of a and are in the opposite halves of the boundary word. This implies that there is a unique way of matching the occurrences of a and with each other without crossings. Indeed, the i’th occurrence of a must be paired with the i’th last occurrence of .

What needs to be checked is that this unique matching respects the crossing condition for all distinct directions a and b. This in mind, for any a and b we define the projection function $\pi _{a,b}$ that erases from a boundary word all letters except and . The crossing condition of the boundary word u can be expressed equivalently as the requirement that all projections $\pi _{a,b}(u)$ satisfy the crossing condition. This turns out to be equivalent in our setup to the property that $\pi _{a,b}(u)$ defines a non-crossing cycle in the counterclockwise direction.

Example 1

Consider the boundary word of the (2, 3) rhombus in Fig. 9. Keeping the orientation of the figure, the directions of the unit vectors are from ${\mathbb {Z}}+\frac{1}{2}$.

Reading counterclockwise, starting where the leftmost rose segment ends, the boundary word is

$$\begin{aligned} \begin{array}{l} \frac{-1}{2}, \frac{-3}{2},\frac{-1}{2}, \frac{-3}{2}\ \vline \ \frac{1}{2}, \frac{3}{2},\frac{-1}{2}, \frac{1}{2}, \frac{-3}{2}, \frac{-1}{2}\ \vline \ \frac{3}{2}, \frac{1}{2},\frac{3}{2}, \frac{1}{2}\ \vline \ \frac{5}{2}, \frac{7}{2},\frac{3}{2}, \frac{5}{2}\ \vline \ \\ \qquad \frac{9}{2}, \frac{7}{2},\frac{9}{2}, \frac{7}{2}\ \vline \ \frac{-9}{2}, \frac{-7}{2},\frac{9}{2}, \frac{-9}{2}, \frac{7}{2}, \frac{9}{2}\ \vline \ \frac{-7}{2}, \frac{-9}{2},\frac{-7}{2}, \frac{-9}{2}\ \vline \ \frac{-5}{2}, \frac{-3}{2},\frac{-7}{2}, \frac{-5}{2}\ \vline \ \\ \end{array} \end{aligned}$$

Vertical lines indicate the changes between the four rose segments and the four edge segments of the boundary. There are five different directions (when antiparallel directions are not counted separately), so there are ${5\atopwithdelims ()2}=10$ different pairs of directions that define projections $\pi _{a,b}$. For example, for $a=\frac{3}{2}$ and $b=\frac{5}{2}$, keeping in mind that and , the projection by $\pi _{a,b}$ is

This word defines a non-crossing boundary in the counterclockwise direction. Analogously we can determine the projections for all pairs a and b. The corresponding paths are shown in Fig. 10. The crossing condition is satisfied. $\square$

Fig. 10

All projections in pairs of distinct directions of the boundary of the (2, 3) super-rhombus. All paths are nonintersecting and counterclockwise, so the crossing condition is satisfied

The results in [7, 8] guarantee that a region surrounded by a simple boundary that satisfies the balance condition and whose (unique) matching satisfies the crossing condition has a tiling by parallelograms ([7, Thm. 2]). In our setup the only non-trivial aspect to check is the crossing condition. In the following section we develop a convenient rewrite system to check this condition.

Remark 1

While [7] guarantees a tiling by parallelograms, it is easy to see that the proof in [7] provides a tiling by unit rhombuses if the boundary consists of unit length segments.

5.1 Rewrite System to Check the Crossing Condition

Our standing assumption in the following is that a and b are directions such that $a<b<a+n \pmod {2n}$ so that is a proper rhombus in the counterclockwise direction. Let u, v be words over the alphabet . Consider the following eight rewrite rules:

(4)

An application of rule $x\longrightarrow y$ on word u means that we replace an occurrence of subword x in u by y. More precisely, if $u=u_1xu_2$ and $v=v_1yv_2$ and $x\longrightarrow y$ is a rewrite rule then u derives v and we write $u\rightarrow v$. We denote the transitive, reflexive closure of $\rightarrow$ by $\rightarrow ^*$, so that $u\rightarrow ^* v$ means that u can be turned into v by a sequence of rewrites. Iterating rule $ab \longrightarrow ba$, for example, allows us to move b’s any number of positions to the left on a word containing only a’s and b’s, or to move a’s to the right on such a word. In other words, $au \rightarrow ^* ua$ and $ub \rightarrow ^* bu$ for any word u that only contains letters a and b.

The top four rewrite rules in (4) correspond to snapping two consecutive edges of the rhombus in reverse order. The last four rules allow eliminating a letter and its reversal that are next to each other.

Suppose $u\rightarrow v$ using the first rewrite rule $ab\longrightarrow ba$. If v satisfies the crossing condition, so does u with the same matchings. Indeed, the only new crossing in u, not present in v, connects pairs and of symbols that appear in u in the (circular) order . Such order is allowed by the crossing condition. The same argument applies to all four rewrite rules that reverse the order of two symbols.

Suppose then that $u\rightarrow v$ using the eliminating rewrite rule . If v satisfies the crossing condition, so does u when we connect the two letters in the eliminated pair with each other, and match all other letters in the same way as they were matched in v. In this way u has exactly the same crossings as v. The same argument applies to any other eliminating rewrite rule.

We have seen that if $u\rightarrow ^* v$ and if v satisfies the crossing condition then also u satisfies the crossing condition. In particular, $u\rightarrow ^* \varepsilon$ guarantees that u satisfies the crossing condition. In fact, it is not difficult to see that this condition is also necessary:

Lemma 1

Let u be a word over the alphabet . Then u has a matching that satisfies the crossing condition if and only if $u\rightarrow ^* \varepsilon$.

Proof

We have seen above that $u\rightarrow ^* \varepsilon$ implies that there is matching in u that satisfies the crossing condition. Let us prove the converse direction. Define a partial order among words with matchings: $u<v$ if u is shorter than v, or if u and v have the same lengths but u has fewer crossings than v.

Let u be a non-empty word with a matching that satisfies the crossing condition. We want to prove that $u\rightarrow v$ for some $v<u$ that also satisfies the matching condition.

Assume first that u contains two consecutive letters that are matched with each other. Hence the letters are antiparallel to each other, and can be eliminated by a rewrite rule. This produces a shorter word v, so $v<u$. The remaining letters in v can be matched exactly as in u, satisfying the crossing condition.

Assume next that u contains two consecutive letters xy whose connections cross each other. By the crossing condition, must be a proper rhombus in the counterclockwise direction, so $xy\longrightarrow yx$ is a valid rewrite rule. When we apply it to u, and keep letter matchings unchanged, we obtain v that has the same length but one less crossing than u. Hence $u\rightarrow v$ and $v<u$. Clearly v satisfies the crossing condition since we obtained it from u by only untangling one crossing.

Finally, assume that u has no consecutive letters that are connected to each other or whose connections would cross each other. Let x and y be two letters in u that are either connected to each other or whose connections cross, and assume their (cyclic) distance d is as short as possible. The letters are not next to each other so there is a letter z between them. But z cannot be connected to another letter between x and y because then the distance from z to would be shorter than d, contradicting the choice of x and y. Hence the connection of z necessarily crosses the x, y pair, and hence it crosses either the connection of x or the connection of y. But the distance from z to both x and y is shorter than d, which again contradicts the minimality of d.

We have proved the claim that $u\rightarrow v$ for some $v<u$ that also satisfies the matching condition. Now, if $v\ne \varepsilon$ the argument can inductively applied on v. By iterating the argument we obtain a sequence $u \rightarrow v \rightarrow \dots$. The partial order $<$ does not admit infinite decreasing chains so $\varepsilon$ must be eventually reached. $\square$

Remark 2

In our setup the boundary u of the tileable region has all the symmetries of the enlarged rhombus: dihedral group $D_4$ or $D_2$ if the rhombus is or is not a square, respectively. The unique matching also respects these symmetries, and so do all projections $\pi _{a,b}(u)$. Shrinking the remaining tileable region by adding a unit rhombus tile with two edges on the boundary corresponds to the application of a rewrite rule on some $\pi _{a,b}(u)$. The analogous rewrite can be done on all symmetric positions, thus reducing the tileable region while keeping its symmetries. By iterating this process we obtain a tiling of the interior of the enlarged rhombus that has all the symmetries of the initial rhombus.

A detail to observe in this process is that each symmetry of the boundary takes any pair of consecutive edges to a disjoint pair, or to the identical pair of consecutive edges, but never to a pair that shares exactly one edge with the original pair. For this reason all symmetric positions can be rewritten independently of each other. In contrast, the reader may consider, for example, tiling the regular octagon of unit sides: the reflection symmetries prevent a fully symmetric tiling of the interior by unit rhombuses.

Notice that $u\rightarrow ^* v$ implies that . This is because for each rewrite rule $x\longrightarrow y$ there is also the rewrite rule in our toolbox (4). This also implies that if $u\rightarrow ^* v$ and $u\rightarrow ^* v^R$ for some word v then satisfies the crossing condition. Indeed, , where the last steps use elimination rewrites. In particular, if a palindrome can be derived from u then satisfies the crossing condition.

Example 2

Let $u=aaabab$ so that is the boundary word from Example 1. Since $aaabab\rightarrow ^* baaaab$ we have that . Analogously, all ten projections shown in Fig. 10 can be reduced into words of the form for some palindromes p, and hence into the empty word $\varepsilon$. $\square$

We are interested in the matching condition on boundary words that are of the type , by performing rewrites on the half word u. As we work with the half boundary, there is yet another useful operation on the words: If $u=xy$ is a concatenation of two words then we may swap the order of x and y while changing x into . We write . When such operation is performed on both halves of , the (circular) word remains unchanged, that is, if $u\leadsto v$ then and are the same (circular) words. Indeed, and for .

We denote $u\Rightarrow v$ if $u\rightarrow v$ or $u\leadsto v$, and by $\Rightarrow ^*$ we denote the reflexive transitive closure of $\Rightarrow$.

Lemma 2

If $u\Rightarrow ^* v\rightarrow ^* v^R$ for some v then satisfies the crossing condition.

Proof

As , by Lemma 1 we know that satisfies the crossing condition. For any $x\Rightarrow y$, if satisfies the crossing condition so does . Namely, if $x\rightarrow y$ then , and if $x\leadsto y$ then and are the same circular word. Hence, $u\Rightarrow ^* v$ implies that satisfies the crossing condition because does. $\square$

All our proofs of tileability use Lemma 2. We start with a half u of the boundary word , and derive from u a new word v using operations $\rightarrow$ and $\leadsto$. Then we operate on v using only rewrite operations $\rightarrow$ to reach its reversal $v^R$. Of course we could always work on the full boundary but working on u reduces the size of expressions and the number of operations by half. We frequently use

and simply cancel a prefix and a suffix from u if they are reversals of each other.

The following particular case will be used multiple times, so we state it as a separate lemma.

Lemma 3

Assume our usual hypothesis that is a rhombus in the counterclockwise orientation. If where $j\ge 1$ then $u\Rightarrow ^* v\rightarrow ^* v^R$ for some v. In particular, satisfies the crossing condition.

Proof

We apply the rewrite rules in (4) that move a to the right and to the left over b’s, and cancel a and as they meet.

If $i< j$ then

and the last two words are reverses of each other. In the last steps we moved $2i+1$ letters b from the beginning of the word to the end. If $i\ge j\ge 1$,

where the last steps of the derivation move $2j-1$ copies of b from the end of the word to the beginning. Also here the last words are reverses of each other. Lemma 2 confirms that satisfies the crossing condition. $\square$

5.2 Boundary Words of Super-Rhombuses

Let us fix $k\in \{1,2,\dots ,n-1\}$ and consider the super-rhombus S of type $(k,n-k)$. Let us orient S on the plane with its bottom edge horizontal and corner k at the left end of the base. Super-rhombuses $(k,n-k)$ and $(n-k,k)$ are identical, so it is sufficient to consider only one of them for each k. We name the rose and edge segments of the boundary of S by letters A through H, as shown in Fig. 11. Segments A, C, E and G are edge segments and B, D, F and H are rose segments. In the counterclockwise orientation, the directions of edges A and C are 0 and k, respectively.

Fig. 11

The eight segments of the boundary

Recall that, for odd n, the edge segments bisect the sequence

of unit rhombuses, where shape $(m,n-m)$ is represented simply as m, and the vertical lines are added to emphasize the structure of the sequence. When n is even, the sequence of bisected unit rhombuses is

where 0 denotes a single unit edge along the edge segment. The sequences are the non-underlined parts of $\Sigma (n)$, as shown in Tables 1 and 2. Remark that the sequences are palindromes, and that all numbers m in the sequences have the same parity as n. Let

$$\begin{aligned} f(m)=\frac{n-m}{2}-1, \end{aligned}$$

so that m appears f(m) times in both halves of $\tau (n)$.

Observe the following structure of $\tau (n)$: let $k,m\in \{1,3,\dots ,n-2\}$ or $k,m\in \{0,2,\dots ,n-2\}$ when n is odd or even, respectively, and $k<m$. Then the projected sequence obtained by erasing all other numbers from $\tau (n)$ has the form

$$\begin{aligned} k^i (m k)^j (k m)^j k^i, \text{ where } i=f(k)-f(m)\ge 1 \text{ and } j=f(m)\ge 0\text{. } \end{aligned}$$

(5)

On the horizontal segment A, each occurrence of m in $\tau (n)$ contributes symbols $\frac{m}{2},\frac{-m}{2}$ on the boundary word, when $m\ne 0$. This is because A is in direction 0, so that each m represents a unit rhombus $(m,n-m)$ whose edges are in directions $\frac{m}{2}$ and $\frac{-m}{2}$. Each occurrence of $m=0$ contributes a single 0 on the boundary word. When n is even, all symbols on the boundary word are integers; when n is odd they are from the set ${\mathbb {Z}}+\frac{1}{2}$. This is easily seen to be the case on all eight segments in Fig. 11, including both the edge and the rose segments. We have that in the case of odd n the directions of the unit vectors present on the boundary are not parallel to any edge of S. In contrast, on even n, each occurrence of 0 in $\tau (n)$ yields a unit vector parallel to an edge. In both even and odd cases, directions $\frac{\pm n}{2}$ perpendicular to A are possible.

For any direction x, where $x\in {\mathbb {Z}}$ or $x\in {\mathbb {Z}}+\frac{1}{2}$ if n is even or odd, respectively, we introduce the notation $\diamond _{x}=m$ if the unit rhombus $(m,n-m)$ on segment A contributes direction x on the boundary word. More precisely, $\diamond _{x}=m$ for all directions x such that $\pm 2x \equiv m \pmod {2n}$, and $0\le m\le n$. We also define

so that, among the two orientations x and , the actual contribution by rhombus $(\diamond _{x}, n-\diamond _{x})$ on the boundary word along segment A is ${\bar{x}}$.

Let us discuss next briefly the rose segments. The four segments combined in the order H, F, D, B form the full rose $R_2^1$ in the clockwise orientation. Each unit vector direction appears twice in the rose. In $R_2$ the directions would appear perfectly ordered in the increasing order, but omitting the outermost ring in $R_2^1$ swaps consecutive pairs of directions. In segment B, directions $\frac{n}{2}$ and $k-\frac{n}{2}$ both appear once (as the second, and the second last direction, respectively), while the directions x in the interval $k-\frac{n}{2} < x < \frac{n}{2}$ appear twice in B.

Let $a,b\in {\mathbb {Z}}$ (even n) or $a,b\in {\mathbb {Z}}+\frac{1}{2}$ (odd n) be two distinct directions of unit vectors on the boundary word. We denote by $\alpha (a,b)$, $\beta (a,b)$, $\gamma (a,b)$ and $\delta (a,b)$ the $\pi _{a,b}$ projections of the boundary word segments on A, B, C and D, respectively. We denote their concatenation by u:

$$\begin{aligned} u=\alpha (a,b)\beta (a,b)\gamma (a,b)\delta (a,b). \end{aligned}$$

The $\pi _{a,b}$ projection of the entire boundary is .

It is easy to see that $\alpha (a,b)$ depends on the directions a and b as follows:

• If $2a\equiv n \pmod {2n}$ so that a is orthogonal to segment A, then direction a does not appear in $\alpha (a,b)$ and hence

  $$\begin{aligned} \alpha (a,b) = {\bar{b}}^i, \end{aligned}$$

  where $i=2f(\diamond _{b})=n-\diamond _{b}-2$. Analogously, if $2b\equiv n \pmod {2n}$ then $\alpha (a,b)$ does not contain direction b.

• Otherwise $\diamond _{a}, \diamond _{b} < n$, so we can infer $\alpha (a,b)$ from (5). If $\diamond _{a}<\diamond _{b}$ then

  $$\begin{aligned} \alpha (a,b)={\bar{a}}^{f(\diamond _{a})-f(\diamond _{b})}({\bar{b}}{\bar{a}})^{f(\diamond _{b})} ({\bar{a}}{\bar{b}})^{f(\diamond _{b})}{\bar{a}}^{f(\diamond _{a})-f(\diamond _{b})}. \end{aligned}$$

  Notice that this word is a palindrome. Analogously, if $\diamond _{b}<\diamond _{a}$ then

  $$\begin{aligned} \alpha (a,b)={\bar{b}}^{f(\diamond _{b})-f(\diamond _{a})}({\bar{a}}{\bar{b}})^{f(\diamond _{a})} ({\bar{b}}{\bar{a}})^{f(\diamond _{a})}{\bar{b}}^{f(\diamond _{b})-f(\diamond _{a})}. \end{aligned}$$

  The last possibility is $\diamond _{a}=\diamond _{b}$. Now

  $$\begin{aligned} \alpha (a,b)=({\bar{a}}{\bar{b}})^{2f(\diamond _{a})} \text{ or } \alpha (a,b)=({\bar{b}}{\bar{a}})^{2f(\diamond _{a})}. \end{aligned}$$

The word $\gamma (a,b)$ along segment C is similar. Because the direction of C is k, directions a and b are oriented with respect to C in the same way as $a-k$ and $b-k$ are oriented with respect to A. We then have

$$\begin{aligned} \gamma (a,b)=\sigma _k(\alpha (a-k,b-k)). \end{aligned}$$

5.3 Case Analysis

We are interested to analyze the word $u=\alpha (a,b)\beta (a,b)\gamma (a,b)\delta (a,b)$ which is the first half of the projection of the boundary word on directions a and b, and to show that satisfies the crossing condition. There are a number of cases to analyze depending on the relationship between directions a, b and k.

Note that we can reduce the number of cases due to symmetries. Because a and , and b and define the same projections, we only need to consider one choice of each. We can also swap a and b if needed. We can therefore assume that

$$\begin{aligned} -\frac{n}{2} < a< b \le \frac{n}{2}. \end{aligned}$$

With this choice, is a proper rhombus oriented counterclockwise, and the rewrite rules in (4) can be used.

Case 1: a or b is perpendicular to a side of super-rhombus S

By suitably orienting S, and possibly replacing b by or a by , we can assume that $b=\frac{n}{2}$ and $-\frac{n}{2}<a<\frac{n}{2}$. We can further assume that $k\le \frac{n}{2}$. (If not, we flip the rhombus and consider $n-k$ instead of k.) In this case we have $\alpha (a,b)=a^i$ for some i.

(a) Assume $a>k-\frac{n}{2}$. Now $\beta (a,b)\in \{baa, aba\}$ and $\delta (a,b)=b$. In any case $\beta (a,b)\rightarrow ^*baa$. Word $\gamma (a,b)$ is either some palindrome p containing only letters a and b (if $\diamond _{a-k}\ne \diamond _{b-k}$), or $\gamma (a,b)=(ba)^j$ for some j (if $\diamond _{a-k}=\diamond _{b-k}$). In the first case

$$\begin{aligned} u\Rightarrow ^* a^i\ baa\ p\ b \Rightarrow ^* b\ a^{i+2}\ p\ b\rightarrow ^* b\ p\ a^{i+2}\ b. \end{aligned}$$

The last two words are reversals of each other, so by Lemma 2 we know that the boundary word $u$ satisfies the crossing condition. In the second case,

$$\begin{aligned} u\Rightarrow ^* a^i\ baa\ (ba)^j\ b \Rightarrow ^* b\ a^{i+1}\ a(ba)^j\ b \rightarrow ^* b\ a(ba)^j\ a^{i+1}\ b. \end{aligned}$$

Again, the last two derived words are reversals of each other.

(b) Next we assume that $a=k-\frac{n}{2}$. Now $\beta (a,b)=ba$, $\gamma (a,b)=b^j$ for some j, and , so that

The last two words are reversals of each other.

(c) If $-\frac{n}{2}<a<k-\frac{n}{2}$ then $\beta (a,b)=b$ and . As $\diamond _{a-k}\ne \diamond _{b-k}$, we know that $\gamma (a,b)$ is some palindrome p that contains letters and b only.

Also here, the last two words are reversals of each other.

In the remaining cases we can now assume that a and b are not perpendicular to the sides of S.

Case 2: $\diamond _{a}=\diamond _{b}$

Let us now assume that directions a and b are from the same unit rhombus on some edge segment. In a suitable orientation of S this means that $a=-b$. By symmetries, we can also assume that $0 < b<\frac{n}{2}$ and $k\le \frac{n}{2}$. Now $\alpha (a,b)=(ba)^i$ for $i=2f(\diamond _{b})=n-2b-2$.

(a) Assume $a>k-\frac{n}{2}$. We have $\beta (a,b)\in \{bbaa, baba\}$ and $\delta (a,b)=\varepsilon$, the empty word. Because $\diamond _{a-k}=2|a-k|=2k+2b$ and $\diamond _{b-k}=2|b-k|$, it follows that $\diamond _{a-k}-\diamond _{b-k}$ is 4b or 4k, depending on whether $b<k$ or $b>k$, respectively. In any case, $\diamond _{a-k}>\diamond _{b-k}$, so we have from (5) that $\gamma (a,b)=b^s(ab)^t(ba)^tb^s$ for some s, t. In fact, $s=\frac{1}{2}(\diamond _{a-k}-\diamond _{b-k})=\min \{2b,2k\}$.

If $s\ge 2$ then

$$\begin{aligned} u&\Rightarrow ^* (ba)^i\ bbaa\ b^{s}(ab)^t(ba)^tb^s\\&\Rightarrow ^* b^s(ab)^{i+2}\ (ab)^t(ba)^tb^s \\&\Rightarrow ^* (ab)^{i+2}\\&\rightarrow ^* (ba)^{i+2}. \end{aligned}$$

In the third step we eliminated $b^s(ab)^t$ and its reversal from the prefix and the suffix of the word, respectively. The last words are reversals of each other so Lemma 2 applies.

Suppose then $s<2$. Because $s=\min \{2b,2k\}$, we see that $s<2$ happens if and only if $b=\frac{1}{2}$, $a=-\frac{1}{2}$. But in this case, the rose segment B contains a unit vector in direction a between two unit vectors in direction b, so that $\beta (a,b)=baba$. (This is, interestingly, the reason why the rose segments come from the rose $R_2^1$ instead of the full rose $R_2$: in the full rose $R_2$ we would have bbaa instead of baba, which would make the crossing condition fail in the case $b=\frac{1}{2}$, $a=-\frac{1}{2}$.) Now we have $s=1$ and

$$\begin{aligned} u&= (ba)^i\ baba\ b(ab)^t(ba)^tb \\&= (ba)^{i+t+2}\ bb\ (ab)^t\\&\Rightarrow ^* (ba)^{i+2}\ bb\\&\rightarrow ^* bb\ (ab)^{i+2}, \end{aligned}$$

where the last two derived words are reverses of each other.

(b) The other possibility is that $-\frac{n}{2}<a<k-\frac{n}{2}$. (Note that the case $a=k-\frac{n}{2}$ is covered by Case 1 because then a is perpendicular to segment C of S.) Now $\beta (a,b)=bb$ and . Also we can calculate $\diamond _{a-k}=2(a-k+n)=2(n-k-b)$ and $\diamond _{b-k}=2|b-k|$ so that $\diamond _{a-k}-\diamond _{b-k} = 2\min \{n-2b,n-2k\}\ge 0$.

Assume first that $k=\frac{n}{2}$ so that $\diamond _{a-k}=\diamond _{b-k}$. We have for some j, so

The obtained word is of the form covered by Lemma 3.

Assume then that $k<\frac{n}{2}$ so that $\diamond _{a-k} >\diamond _{b-k}$. Then for some s, t. We derive

Lemma 3 applies to the derived word.

From now on we can assume that neither Case 1 nor Case 2 applies.

Case 3: Directions a and b appear in the same rose segment B

Now $k-\frac{n}{2}<a<b<\frac{n}{2}$ and $0<k<n$. (Note that we allow $k>\frac{n}{2}$ so that we do not assume the angle between segments A and B to be obtuse.) We can also assume that $b>0$ because otherwise we can reflect the super-rhombus to swap segments A and C.

In this setup we have $\beta (a,b)\in \{bbaa, baba\}$ and $\delta (a,b)=\varepsilon$. Moreover, $\alpha (a,b)$ and $\gamma (a,b)$ are palindromes containing only letters a and b, and $\diamond _{a}=2|a|$, $\diamond _{b}=2|b|=2b$, $\diamond _{a-k}=2|a-k|$ and $\diamond _{b-k}=2|b-k|$. Because Case 2 does not apply, we have $\diamond _{a}\ne \diamond _{b}$ and $\diamond _{a-k}\ne \diamond _{b-k}$.

(a) Assume first that $\diamond _{a} >\diamond _{b}$. Then $|a|>b>0$ but $a<b$, which clearly implies that $a<0$. Then also

$$\begin{aligned} \diamond _{a-k} = 2|a-k| = 2(|a|+k) > 2(b+k) \ge 2|b-k| = \diamond _{b-k}. \end{aligned}$$

Now $\alpha (a,b)=b^i(ab)^j(ba)^jb^i$, and $\gamma (a,b)=b^s(ab)^t(ba)^tb^s$ for some $i,s\ge 1$ and $j,t\ge 0$. More precisely,

$$\begin{aligned} \begin{array}{rcl} s&{}=&{}f(\diamond _{b-k})-f(\diamond _{a-k})=|a-k|-|b-k|= k-a-|b-k|,\\ i &{}=&{}f(\diamond _{b})-f(\diamond _{a})=|a|-|b|=-a-b. \end{array} \end{aligned}$$

In particular, $s-i=k+b-|b-k|> 0$ so that $s> i\ge 1$. Also, because $\diamond _{a-k}=-2(a-k)>-2a=\diamond _{a}$, we have that $t<j$. We derive

$$\begin{aligned} u&\Rightarrow ^* b^i(ab)^j(ba)^jb^i\ bbaa\ b^s(ab)^t(ba)^tb^s\\&\Rightarrow ^* (ab)^j(ba)^jb^{i+2}\ abab\ b^{s-2}(ab)^t(ba)^tb^{s-i}\\&\Rightarrow ^* (ab)^j(ba)^jb^{2s}\ abab\ (ab)^t(ba)^t\\&\Rightarrow ^* (ab)^{j-t}(ba)^jb^{2s}\ (ab)^{t+2}\\&\Rightarrow ^* (ba)^{2j-t}b^{2s}\ (ab)^{t+2}\\&\Rightarrow ^* (ba)^{2j-2t-2}b^{2s}\\&\rightarrow ^* b^{2s}(ab)^{2j-2t-2}. \end{aligned}$$

The last two words are reversals of each other.

(b) Assume next that $\diamond _{a} <\diamond _{b}$ and $\diamond _{a-k}<\diamond _{b-k}$. Then $k-b<k-a\le |k-a| < |k-b|$ so that $k-b<0$, that is, $b>k$.

Now $\alpha (a,b)=a^i(ba)^j(ab)^ja^i$, for $i=f(\diamond _{a})-f(\diamond _{b})$ and $j=f(\diamond _{b})$, and $\gamma (a,b)=a^s(ba)^t(ab)^ta^s$, for $s=f(\diamond _{a-k})-f(\diamond _{b-k})$ and $t=f(\diamond _{b-k})$. We have

$$\begin{aligned} t-j= & {} |b|-|b-k| = b-(b-k)=k>0, \text{ and } \\ i-s= & {} |b|-|a|-(|b-k|-|a-k|)\\= & {} b-(b-k)+|a-k|-|a| \ge k + (|a|-k)-|a| =0, \end{aligned}$$

so that $t>j$ and $i\ge s\ge 1$.

Assume first that $i\ge 2$. Then

$$\begin{aligned} u&\Rightarrow ^* a^i(ba)^j(ab)^ja^i\ bbaa\ a^s(ba)^t(ab)^ta^s\\&\Rightarrow ^* a^{i-s}(ba)^j(ab)^ja^i\ bbaa\ a^s(ba)^t(ab)^t\\&\Rightarrow ^* (ba)^j(ab)^j\ a^{2i-s}\ bbaa\ a^s(ba)^t(ab)^t\\&\Rightarrow ^* (ab)^{j+2}\ a^{2i} (ba)^t(ab)^{t-j}\\&\Rightarrow ^* (ab)^{j+2}\ a^{2i}\ (ba)^{2t-j}\\&\Rightarrow ^* a^{2i}\ (ba)^{2t-2j-2}\\&\rightarrow ^* (ab)^{2t-2j-2} a^{2i}. \end{aligned}$$

Note that we used the fact that $2i-s\ge 2$ on the fourth derivation line to change aabb into abab. The last two words are reversals of each other.

Consider then the case $i=1$, so that also $s=1$. But $i=b-|a|=1$ and $s=b-k-|a-k|=1$ happen simultaneously only if $b=a+1$. In this case, $\beta (a,b)=baba$ as the path follows rose $R_2^1$ instead of rose $R_2$. We derive

$$\begin{aligned} u= & {} a(ba)^j(ab)^ja\ baba\ a(ba)^t(ab)^ta\\&\Rightarrow ^* (ab)^{j+2}\ aa\ (ba)^t(ab)^{t-j}\\&\Rightarrow ^* (ab)^{j+2}\ aa\ (ba)^{2t-j}\\&\Rightarrow ^* aa\ (ba)^{2t-2j-2}\\&\rightarrow ^* (ba)^{2t-2j-2}\ aa, \end{aligned}$$

obtaining a word and its reversal. Note that also here it was essential that rose $R_2^1$ was used instead of rose $R_2$.

(c) The last possibility is that $\diamond _{b} >\diamond _{a}$ and $\diamond _{b-k}<\diamond _{a-k}$. Then $\alpha (a,b)=a^i(ba)^j(ab)^ja^i$ and $\gamma (a,b)=b^s(ab)^t(ba)^tb^s$ for some $i,s\ge 1$ and $j,t\ge 0$. We have

$$\begin{aligned} u&\Rightarrow ^* a^i(ba)^j(ab)^ja^i\ bbaa\ b^s(ab)^t(ba)^tb^s\\&\Rightarrow ^* a^{i-1}(ab)^{2j}a^{i-1}\ aa\ bbaa\ bbb^{s-1}(ab)^{2t}b^{s-1}\\&\Rightarrow ^* a^{i-1}b^{s-1}(ab)^{2j}aba\ baba\ b(ab)^{2t}b^{s-1} a^{i-1}\ \\&\Rightarrow ^* (ab)^{2j+2t+4} \\&\rightarrow ^* (ba)^{2j+2t+4}. \end{aligned}$$

The last two words are reversals of each other.

Case 4: None of the cases 1–3 apply

Because Case 3 does not apply, directions a and b do not appear on the same rose segment; because Case 1 does not apply the directions appear on unique rose segments, with the antiparallel directions then appearing on the opposite rose segments. We can orient rhombus S so that b appears in segment B and in segment D. Then $\beta (a,b)=bb$ and . Now $\alpha (a,b)$ and $\gamma (a,b)$ are palindromes containing only letters a and b, and only letters and b, respectively. Then

contains only letters and b.

Depending on whether $\diamond _{a}>\diamond _{b}$ or $\diamond _{a}<\diamond _{b}$ we have either $\alpha (a,b)=b^i(ab)^j(ba)^jb^i$ or $\alpha (a,b)=a^i(ba)^j(ab)^ja^i$, for some $i\ge 1$ and $j\ge 0$. In the first case,

$$\begin{aligned} u= & {} b^i(ab)^j(ba)^jb^i\ w\\&\Rightarrow ^* b^i (ba)^{2j}\ w\ b^i\\&\Rightarrow ^* (ba)^{2j}\ w, \end{aligned}$$

and also in the second case

We see that in any case, .

Analogously, depending on whether $\diamond _{a-k}>\diamond _{b-k}$ or $\diamond _{a-k}<\diamond _{b-k}$ we have either or , for some $s\ge 1$ and $t\ge 0$. In the first case,

According to Lemma 3, the crossing condition is satisfied. In the second case,

so again Lemma 3 applies.

This completes the case analysis. All possible cases were covered, and the crossing condition was confirmed in each case. This completes the proof of Theorem 1. $\square$

6 Conclusions

We have demonstrated primitive substitutions on unit rhombuses that generate substitution tilings with 2n-fold rotational symmetry for all n. The obtained tilings are uniformly recurrent, i.e., quasiperiodic. The proof was based on a rewrite system on the proposed boundaries of the enlarged rhombuses to check that the interior can be properly tiled.