A Self-Ruling Monotile for Aperiodic Tiling

Year: 2022 Authors: Pierre Gradit; Vincent Van Dongen

Core claim

HexSeed embeds scaling and substitution information in one tile, and the resulting infinite tiling is proven aperiodic through dendrite-based motif analysis.

Topics

aperiodic tiling, monotiles, substitution rules, hexagonal tilings, fractal motifs

Domains

tiling theory, substitution systems, aperiodic order, fractal geometry, pattern design, geometric aesthetics, motif exploration, visual abstraction

Methods

iterative substitution, finite motif coloring, dendrite analysis, aperiodicity proof

Media

hexagonal subtiles, binary color motifs, arrow motifs, edge bumps and holes

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2022 Conference Proceedings

A Self-Ruling Monotile for Aperiodic Tiling

Pierre Gradit ${}^1$ and Vincent Van Dongen ${}^2$

${}^1$ Independent researcher, France; pierre.gradit@gmail.com ${}^2$ Independent researcher, Canada; vincent.vandongen@gmail.com

Abstract

Can the entire plane be paved with a single tile that forces aperiodicity? This is known as the ein Stein problem (in German, ein Stein means one tile). This paper presents a monotile that delivers aperiodic tiling by design. It is based on the monotile developed by Taylor and Socolar (whose aperiodicity is forced by means of a non-connected tile that is mainly hexagonal) and motif-based hexagonal tilings that followed this major discovery. Here instead, a single substitution rule makes its shape, and when applying it, forces the tiling to be aperiodic. The proposed monotile, called HexSeed, is self-ruling. It consists of 16 identical hexagons, called subtiles, all with edgy borders representing the same binary marking. No motif is needed on the subtiles to make it work. Additional motifs can be added to the monotile to provide some insights. The proof of aperiodicity is presented with the use of such motifs.

Introduction

In the seventies, Penrose demonstrated that two aperiodic tiles can pave the plane without holes [8]. The two tiles are said to be aperiodic because they can only generate an aperiodic tiling. Soon after, people wondered whether an aperiodic monotile could exist. That is, could a single tile be aperiodic, not allowing any periodic tiling, and still pave the entire plane? This problem is known as the ‘ein-Stein’ problem. (‘ein Stein’ is German and means ‘one tile’). [2]

Figure 1: The monotile of $T-S$ tiling: (a) the tile consists of a central hexagonal-based shape with non-connected parts around, (b) its flip side and (c) the Sierpinski triangle (shown by the red marks on the tile) that appears when tiling.

The existence of a single connected tile to pave the entire plane only in an aperiodic manner with no other artefact than its shape is still unknown. However, some major discoveries were made. A decade ago, Taylor and Socolar [7] proposed a first solution to this problem. The tile is mainly hexagonal but non-connected (i.e. not in one piece as shown in Figure 1a). We will refer to it in this paper as T-S tiling. There is only

Gradit and Van Dongen

one way of covering the plane with it, initiated in Figure 1c, that is aperiodic, and it requires both sides of the tile (the other side is obtained by flipping the tile depicted in Figure 1b).

The marks on the non-connected version of the monotile provide some insight. Sierpinski triangle is generated which shows the aperiodicity of the tiling. In the same publication [7], a connected version of their monotile is also presented. This connected version is of hexagonal shape with an additional decoration for forcing the aperiodicity. Note that the decoration imposes constraints on non-adjacent tiles. In both versions of T-S tiling (connected and non-connected), a non-local constraint is needed for enforcing aperiodicity.

In [5], another hexagonal-based tiling, called $(1+\epsilon +\epsilon 2)$ -tiling, is presented with thin edge tiles and small corner tiles. Both T-S tiling and Penrose tiling are compared in [1] and [3]. It is noted that both tilings are based on a hierarchical system of nested equilateral triangles, i.e. the Sierpinski triangle. This is a well-studied fractal-based motif [6].

An alternative motif on hexagonal tiles was recently proposed in [4]. The solution makes use of a dendrite motif. As explained in their paper, the dendrite forms nested triangles of Sierpinski as well. The innovation here is that the monotile does not require to be flipped. The enforcement of aperiodicity is controlled by the dendrite property. This dendrite method will be the basis of our study on aperiodic tiling.

In this paper, we present yet another version of a hexagonal based tiling called HexSeed. Its aperiodicity is enforced by making our monotile self-ruling as explained in the next section. HexSeed can be compared to Limhex: the version of Limhex provided in [9] only covers partially the plane and the one presented in [10] contains overlaps.

A self-ruling monotile called HexSeed

A self-ruling monotile is a single tile self-containing scale and substitution information. Our monotile called HexSeed is shown in Figure 2c. It consists of 16 identical subtiles of different orientations. The scaling and substitution information contained in HexSeed are to be used to develop the aperiodic tiling. In other words, HexSeed is to be built out of the scaling/substitution rule shown in Figure 2. The process is iterative. At each iteration, each subtile is scaled by a factor of 4 and then replaced by a monotile with 16 subtiles.

Figure 2: HexSeed Scale/Substitution rule as depicted by its right-hand side alone.

Figure 3a shows HexSeed with an arrow on each subtile for its orientation. It also shows the close match between the monotile and the enlarged version of a subtile, both being an hexagonal-based shape. The hexagonal representation of HexSeed is shown in Figure 3b; depending on its sign (+ or -), the edge is with a bump or a hole.

A Self-Ruling Monotile for Aperiodic Tiling

(a)

(b) Figure 3: (a) HexSeed with an arrow motif on the subtile for its orientation and the close match between the enlarged subtile and the monotile. In (b), the hexagonal representation of HexSeed with plus sign (+) for bumps and minus sign (-) for holes.

HexSeed is closely related to the hexagon-based aperiodic tilings mentioned in the introduction. In order to demonstrate this, we need to add motifs to the tiles. In the remaining of this paper, we will consider two ways of applying the scale/substitution rule:

• Finite way that makes use of a finite number of application of rule: ${\mathbf{P}}_{\mathrm{n}+1}=\mathbf{Subst}(\mathbf{Scale}({\mathbf{P}}_{\mathbf{n}}))$
• Infinite way, by considering a plan partition which is a fix point of rule: $\mathbf{P}=\mathbf{Subst}(\mathbf{Scale}(\mathbf{P}))$

In the latter, we will explore properties of ${\mathbf{P}}_{\mathrm{n}}$ then prove that $\mathbf{P}$ is aperiodic.

A finite exploration with motifs

In order to explore the properties of the tile, we first propose to assign a single binary colour, either black or white, to each subtile. This already provides many possibilities and offers the best contrasting result. Using this exploratory technique, two main patterns are present: Sierpinski triangle and the dendrite. The first pattern is the Sierpinski triangle [6]. Figure 4 shows how it can be generated with a single line of black subtiles on the monotile.

Figure 4: The Sierpinski triangle can be generated by assigning a single line of subtiles in black on the monotile. Here the substitution rule is applied three times. Going from left to right, the subtiles are scaled down to keep the overall shape the same.

The other motif of particular interest is the dendrite. It can be created as shown in Figure 5.

Gradit and Van Dongen

Figure 5: The dendritic motif in black and white on the monotile and two applications of its substitution rule.

Let us now make use of a similar dendrite motif but with finer details on the subtile in order to better analyse the aperiodic property of HexSeed. With the representation provided on Figure 6, dendrites convey the idea of infinite paths originating from sources (i.e. the origin of a path) represented by circles.

Figure 6: Monotile with motif of dendrite with sources represented by circles.

In 2020, it was proven that if dendrites have no cycle, the tiling is aperiodic [4]. In the next section, we will indeed prove that the dendrites generated by HexSeed contain no cycle.

It can be observed that the subtiles in HexSeed take six orientations. For clarity, we have assigned a different color for each orientation: pink for $0^{\circ }$ , green for $60^{\circ }$ , grey for $120^{\circ }$ , white for $180^{\circ }$ , orange of $240^{\circ }$ and blue for $300^{\circ }$ . The tiling can be created in two steps. First, an infinite star that divides the plane in 6 zones is created, as shown on the left of Figure 7 and then the tiling of each triangular zone starting from the center of the star. This property is necessary to initiate a step in our final proof in the next part.

A Self-Ruling Monotile for Aperiodic Tiling

Figure 7: Tiling identical to HexSeed can be created directly from the subtiles in two steps: First (see on the left) an infinite star is created that divides the plane in 6 and then (see on the right) the tiling is completed starting from the center of the star.

The plane then can be tiled from the center of the star. The subtiles can simply be placed as imposed by the star through a process called “must-hex process”. The “must-hex process” is an incremental process in which we add at each iteration all subtiles that must be placed in a given orientation because of the occurrence of a concave sequence of similar shapes: two bumps $(++)$ or two holes $(--)$ . In this situation, to fill the concavity requires a specific orientation of the subtile.

Proving the aperiodicity of HexSeed

In order to prove that our monotile scale/substitution rule is aperiodic, we need to consider infinite scale/substitution rule application by calling P the infinite plane partition of HexSeed which is the fix-point of the scale/substitution rule application i.e. $P$ scaled 4 times, in which each tile is replaced by 16 subtiles, is again $P$ . The goal of this part is to prove that P is aperiodic, i.e. there exists no translation T such as $\mathrm{P}=\mathrm{T}(\mathrm{P})$ .

To prove this, we will reuse the context of [4] and equip our tile of sources and paths. A source is represented by a circle, and path by bezier curves. When assembled, as for example in Figure 8, a source is linked to a path. In [4] it is proven that if no path has cycles then the tiling is aperiodic.

Starting with P0, P1, P2, we can remark that most of the sources have their corresponding path leading to three straight paths called dendrites. The main one is headed to $-180^{\circ }$ , two other ones are the $60^{\circ }$ and $-120^{\circ }$ dendrites.

[Aperiodicity proof] any source is linked either to $180^{\circ }$ , $60^{\circ }$ or $-120^{\circ }$ dendrite - which implies the absence of cycles.

Our proof of aperiodicity relies on the capacity to colour all sources in P: white if they go to the $-180^{\circ }$ dendrite and black if they go to either the $60^{\circ }$ dendrite or the $-120^{\circ }$ depending on their position with respect to the horizontal infinite dendrite. If that colouring is decidable for any source then any source will go into an infinite dendrite, which implies it has no cycle, and therefore the tiling is aperiodic.

Gradit and Van Dongen

Figure 8: The tile $P_1$ - with Scale $(P_0)$ in surimpression - with sources and paths

1. The first stage of the proof is to complete the tile with “must-hex process” used at the end of previous part. This completion stage leads to Figure 9 after three iterations (green, yellow, orange), where all concavities are alternate bump/hole sequence:

Figure 9: Completing the HexSeed tile with three steps of “must-hex process”

2. The second stage of the proof is a computation by diffusion. As seen in Figure 7, the center subtile also has the property of being connected to all dendrites as it is situated on the $-180^{\circ }$ horizontal dendrite and contains the sources of both $60^{\circ }$ and $-120^{\circ }$ dendrites.

The initiation of the computing being that the origin subtile is on the infinite $-180^{\circ }$ dendrite (white) and both its sources are initiation of respective dendrites $60^{\circ }$ and $-120^{\circ }$ (black). Then by diffusion, the knowledge of the source colours gradually covers almost all Figure 10.

3. The third stage of the proof is to decide the colour of the sources of the six blue subtiles on the border of Figure 10 by applying the scale/substitution rule. The last stage of the proof, illustrated in Figure 11, relies on that infinite rule application that allows to decide the colour of the perimeter sources of the tile by the information contained in the tile itself using the fix-point property.

As soon as the color of any source of the self-ruling tile is decided, any source of any subtle of the plane can be decided by the same process used in the previous step.

For example, to decide the source colour of the tile at the immediate right of the center tile, as in Figure 12, you consider the small blue hexagon as giving the values for the big hexagon on the right. With this information, the subtle sources of the blank space on the right will be white sources except three perimeter sources on the upper side, black. These three sources are the two at the top and the one at upper-left edge.

A Self-Ruling Monotile for Aperiodic Tiling

Figure 10: Deciding colour by diffusion leaving six undecided subtiles

Figure 11: Use of scale/substitution information to conclude

Conclusion

The study of the “ein-stein” problem as opened in 2010 by Taylor and Socolar seems to be always associated with an hexagonal base and a rule conveying a non-strictly adjacent rule to insure aperiodicity. Our work embeds this constraint in a single tile, called HexSeed, that conveys sufficient information to tile the whole plane aperiodically and with no tile flipping.

By colouring its subtiles, we made apparent two motifs that are useful for proving its aperiodicity: the Sierpinski Triangle and the dendrite motif. In this paper we choose the dendrite motif and prove aperiodicity by deciding the final and infinite destination of any source $(-180^{\circ },60^{\circ }$ or $-120^{\circ })$ . As these dendrites are infinite, the absence of cycle and thus aperiodicity is proven.

We showed in this paper the importance of selecting the right motif for the study of aperiodic tilings. We feel this exploration is far from being completed and therefore plan to pursue it in the future. Other ways to convey the non-local constraint may be found, even lighter than these we know as granted, or the one we propose in this paper. Behind the potential applications that these tilings may bring, let us not forget the aesthetic value of them as it is how it all started.

Gradit and Van Dongen

Figure 12: Deciding source colours for the tile on the right

Figure 13: An example of HexSeed that we particularly enjoyed looking at. Going from left to right, the monotile and three successive iterations.

References

[1] M. Baake, F. Gahler and U. Grimm (2012, October 22). “Hexagonal Inflation Tilings and Planar Monotiles.” (Symmetry, Ed.) Milton Keynes, Buckinghamshire, UK. doi:10.3390/sym4040581 [2] Einstein Problem. (n.d.). Retrieved from Wikipedia: https://en.wikipedia.org/wiki/Einstein Problem [3] J.-Y. Lee and R. Moody (2017, May). “On the Penrose and Taylor-Socolar hexagonal tilings.” ACTA Crystallographica A-Foundations and Advances, 246-256. [4] M. Mampusti and M. Whittaker (2020). “An aperiodic monotile that forces nonperiodicity through dendrites.” University of Wollongong, Australia. [5] R. Penrose (1979). “Pentaplexity A Class of Non-Periodic Tilings of the Plane.” The Mathematical Intelligencer 2 (https://doi.org/10.1007/BF03024384), 32-37. [6] Wikipedia. (n.d.). https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle. Retrieved from Wikipedia. [7] J. Socolar and J. Taylor (2012). “Forcing nonperiodicity with a single tile.” The Mathematical Intelligencer, 34 (1), 18-28. [8] Wikipedia (n.d.). Penrose Tiling. Retrieved from https://en.wikipedia.org/wiki/Penrose_tiling [9] J. Socolar (n.d.) Retrieved from the online Tilings Encyclopedia https://tilings.math.uni-bielefeld.de/substitution/limhex [10] J. Socolar (n.d.). Limhex retrieved from https://demonstrations.wolfram.com/SubstitutionTilings/