The Turtle prototile is not periodic, a simple proof.

(This is a repost as the original is unavailable due to technical issues. An archive of the original post can be found here. Also, a re-worked version of this post to be built upon can be found here.)

Figure 0: A pair of Hat tiles, shown as polykites

When a group of mathematicians and tiling hobbyists announced the discovery of the Hat aperiodic monotile I, like many others, was very excited by the news.

As I read more detailed accounts of the hat, one thing started to bother me. The method of tiling the Hat was easy enough to see from the popular treatments, but I was unsatisfied with the explanations for excluding periodic tilings(‘Why must this map be a similarity?’).

Even in the paper accompanying the announcement(i.e. the Hat paper), the tiling method was easy to discern, but the other part of the proof was hard to grasp.

Other features of the Hat and related tiles caught my attention, but until recently I had little of hope of finding a satisfying proof of non-periodicity.

In this post I propose a simple, possibly original¹ proof that a close relative of the Hat cannot tile periodically.

Background

Figure 1: An example of a periodic tiling. Two translation vectors and a highlighted patch are shown.

Say that a tiling of the plane is periodic if you can slide a copy of the tiling on top of the original in two different directions by a specific amount in each and have the copy match exactly. That implies the existence of a finite patch of tiles whose copies can be shifted by sums and differences of those vectors to fill the plane. (see Fig. 1).

A tiling uses a number of tile shapes, or prototiles. A given set of prototiles may generate many different plane tilings, or it may fail to tile the plane at all. A set of prototiles may be called periodic if it it can generate at least one periodic tiling.

We call a set of prototiles aperiodic if it can tile the plane, but none of those tilings are periodic. In the 1960’s, the first aperiodic set of prototiles was found by Robert Berger, containing over 20,000 prototiles. Smaller sets were quickly found, and in about ten years Roger Penrose would find an aperiodic set with only two prototiles. While other two-prototile aperiodic sets were found, this size limit could not be lowered. The problem of finding an aperiodic monotile(the lone member of an aperiodic one-element set) lasted over forty years, long enough for the problem to gain notoriety even amongst the public.

To prove that a prototile is an aperiodic monotile, two things must be shown:

• The prototile can tile the plane non-periodically
• The prototile cannot tile the plane periodically(i.e. it is not periodic)

This post, as a supplement to existing coverage on the Hat, only covers the second item on the list.

Caveats

There is an important technical detail missing in this post that I am deferring to the Hat paper, specifically Appendix A. An attempt to fill this detail can be found in this post as well.

I am not against leaving out even critical technical details in a popular explanation of a proof, but if it can be done without excising the core reasoning of the proof, then it is all the better.

Some other details and asides have been placed into footnotes. These will not be essential to understanding the proof.

This proof only excludes the possibility of periodic tilings. It does not say anything about the existence of tilings. For our purposes, we will consider a prototile and its mirror to be the same shape.

Meet the Turtle

Figure 2: A sampling of the prototiles in the continuum described in the Hat paper. The darker shapes permit more tilings than the lighter shapes. The Hat is third from the left, the Turtle is fifth from the left.

The Hat paper describes a continuum of shapes that, barring three edge cases(no pun intended), all tile the same way. In fact, given a tiling by one eligible member of the continuum, you can construct the corresponding tiling by any other member of the continuum. The shape used in this proof is one of them.

Figure 3: Two Turtle tiles, one flipped, shown as composed of kites.

The Turtle prototile is made up of 10 kites, each with angles of 120°-90°-60°-90° going around clockwise. The kite that the Turtle prototile is made of can tile the plane in the [3.4.6.4] Laves tiling.

Figure 4: A component kite of the Turtle.

Figure 5: The [3.4.6.4] Laves tiling.

An important fact for this proof is that every tiling by the Turtle prototile alone can be aligned to the Laves tiling of the kite. In other words, given any tiling of the plane by Turtle tiles, if each Turtle tile were split up into kite tiles, the end result would be the Laves tiling.

This is proven for the Hat in the Hat paper(Lemma A.6), and it seems that this proof can be applied to the Turtle with minimal adaptation. For the purposes of this proof we will take it as given.

To continue our proof we will need to establish some facts about the Laves tiling, particularly of certain decorations.

Spars and corners

Figure 6: Left, a kite marked with a spar(maroon) and lead and lag corners. Right, a lead(orange) and lag(blue) corner, lead corner on top.

Let us decorate each kite in the Laves tiling with a line segment connecting its two right angles. We will call this line segment a spar.

We will also distinguish between the two right angles of a kite. Looking from the ‘inside’ of the right angle so it appears concave, if the long side of the kite is to the left, then it is a lead corner. If on the other hand, if the long side is to the right, then it is a lag corner.

Figure 7: [3.4.6.4] Laves tiling marked with lead corners, lag corners, and spars.

When the decorated kite is used to recreate the Laves tiling, we see that the spars arrange themselves into infinite lines. These spar lines run in three different directions, forming three line classes. Spar lines intersect each other in pairs, forming three orientations of spar crossings.

By the symmetry of the Laves tiling, the spar lines are equally spaced and have equal linear density in the three line classes. This symmetry also forces the three line classes to each be the same angle(60°) from each other.

Figure 8: Kites in the Laves tiling along a spar line.

Going along a spar line, we run over a pair of lead corners, across a kite, over a pair of lag corners, across another kite, and then we repeat. Every even number of spars along we are running over the same type of corner.

Figure 9: Kites in the Laves tiling surrounding a spar crossing.

Zooming in on a single spar crossing, we see a pair of lead corners and a pair of lag corners for four right angles in total. One of the spar lines passing through goes the lag corners, while the other line lies on the lead corners. Taking a broader look(see Fig. 7), we see there are no right angles outside of spar crossings, and every spar crossing looks like this one, except perhaps rotated.

Turtles, spar lines, and crossings

Figure 10: A Turtle tile made up of decorated kites.

If we use these decorated kites to construct a Turtle tile, we see four segments of spar lines within the tile. More importantly, each of these segments contains an even number of spars. Therefore, the ends of each spar segment lie on the same type of corner.

This implies that if this Turtle tile were placed ‘on-grid’ in the Laves tiling, then every spar line entering the tile would exit on the same colour of corner as it entered.

If the whole plane was tiled by the Turtle prototile, any spar lines leaving a Turtle tile would immediately enter another Turtle tile, again on that same type of corner, and so on. Each spar line would consistently enter and exit tiles on their own corner type. This allows us to consistently colour each spar line based on how they exit each tile.

Figure 11: Turtle tiles decorated with coloured spars. (Lead tile on top)

Say that a spar line is a lead line if it moves between tiles through a lead corner, and call it a lag line if lies on lag corner when doing so. Let spars and spar segments inherit the designation of their parent line. Again note that every coloured spar line faithfully represents the type of corner it runs over as it pierces a tile boundary.

Since the colour of a spar line is determined within a tile, we can decorate Turtle tiles to match this colouring. As lead and lag corners are not preserved by reflection, Turtle tiles must be decorated differently depending on their flip. Call a decorated Turtle tile containing mostly lead spars a lead tile, and its flipped version a lag tile.

One thing we might want to know is the fraction of spar lines which are lead lines in each line class. Because the line classes are equally linearly dense, this is proportional to the absolute linear density of lead lines in each direction.

In either case, the variability in Turtle tiles is an obstacle if we want find this. One thing that may persist over a tile flip is whether a spar crossing has lines that are the same or different. Spar crossings are also at a specific place, so they may be easier to deal with.

Figure 11: A patch of decorated Turtle tiles. Crossings with solid circles are controlled, while those with dashed circles are free. Uncircled crossings are not specified.

Call a spar crossing positive if its two lines are the same type, and negative if they differ. In the Laves tiling, spar lines always cross when lying on corners of opposite type. For positive crossings to exist, then there must be a mismatch between a line and the corners underneath.

By the way we’ve coloured the lines, this can only happen if a line is not moving between tiles. In other words, a positive crossing is only possible if one line’s spars right next to the crossing are both in the same tile. These spars are on the opposite sides of the crossing. Thanks to the shape of the Turtle prototile, this is equivalent to a Turtle tile containing at least three out of the four spars next to a crossing. This means that every positive crossing is ‘owned’ by just one tile in any Turtle tiling.

If a tile contains two opposite spars of a crossing, then we say that it is a controlled crossing, and that the tile controls that crossing. If no tile controls a crossing, then it is a free crossing.

Note that while every positive crossing is controlled, the converse is not the case, and controlled negative crossings are possible².

The proof

Assume that we have a periodic tiling by the Turtle prototile. This implies the existence of a finite patch of Turtle tiles repeating to create the entire tiling. The tiles in this patch determine the line colours in each of the three line classes, so the pattern of colours in each line class repeats as well.

This finite patch also sets the proportion of lead lines in each of the three classes. Since each of these is determined by a finite repetition of lines, they must all be rational.

The lead line fraction in each class affects the density of lead-lead crossings in each of the three orientations. At first glance, it seems that fraction of lead lines in each direction is independent.

However, every lead-lead crossing must be controlled by a lead tile, but a lead tile controls three lead-lead crossings, one in each orientation(see Fig. 11). Lead-lead crossings thus always come in a balanced set of three. Therefore, the density of lead-lead crossings in each orientation are equal.

This argument applies to lag tiles and lag-lag crossings as well. If there are no lead-lead crossings at all, that implies that there are only lag tiles used with their lag-lag crossings. We can then reason with the lag linear density instead. Without loss of generality, we assume that there are a positive fraction of lead tiles in the tiling.

Figure 12: A parallelogram in an infinite grid of lines. Line intersection density is reciprocal to average area of a parallelogram. Average parallel line spacing is reciprocal to linear density.

The density of lead-lead spar crossings of the same orientation is proportional to the product of the linear density of lead lines of two relevant line classes multiplied³ by the sine of their angle. For our classes the angle is constant, so we can ignore the sine. The equality of lead-lead crossings in all orientations forces the linear density of lead lines in each class to be equal, and hence their proportion.

Let be the fraction of spar lines that are lead lines. Again, it is not obvious how to constrain directly, but it is highly likely that it is related to the fraction of all crossings that are positive(call this ). It may also be possible to directly calculate from examining a Turtle tile.

Let’s choose a pair of classes, and from each class take consecutive spar lines, where is much larger then the period of either class. The number of lead lines we have from each class is about and the number of lag lines is about per class. From this we generate crossings, around of which are lead-lead, and about are lag-lag crossings.

The fraction of the crossings that are positive is thus around . If we let go to infinity then the expression becomes exact and it covers all crossings of one orientation. Repeating this over all pairs of classes shows that .

Figure 13: A flipped Turtle tile made up of decorated kites.

Now let us try to calculate from a Turtle tile directly. A single Turtle tile contains ten kites and thus 20 internal and external right angles. A spar crossing requires four right angles, so we expect a tile to contribute the equivalent of five crossings.

A Turtle tile controls four crossings, but it only contributes 14 right angles to those crossings. The missing two right angles come from (external) non-reflex right angles from other tiles. Note that the only way a non-reflex right angle can contribute to a controlled crossing is to fill in a reflex right angle.

The two right angles on the longest side of the tile contribute half of a free crossing. This leaves just the four non-reflex right angles of our tile. Two of these have to be ‘paid forward’ to fill in reflex right angles of other tiles. The other two have no more reflex right angles to fill so they contribute a quarter of a free crossing each, which brings us to five total crossings.

Of these five crossings one is free and thus negative. One of the controlled crossings is negative, so three of the five overall crossings are positive. This analysis applies to every Turtle tile in the tiling, so .

The two expressions for imply the following equation:

This equation permits the following values for .

Both of these values are irrational, which is impossible in a periodic tiling.

Random observations and thoughts

• For the sake of argument, in the proof above I assume a periodic tiling, but the final formula seems to apply more generally. For example, it correctly predicts the ratio of lead to lag tiles in the tiling given in the Hat paper.
• To what extent can you determine a patch of Turtle tiles from the colours of the spar lines passing through?
• In this paper, the ‘infinitesimal phason shift’ shown at the end seems to correspond to swapping a pair of adjacent parallel spar lines of different colour in a Turtle tiling, at least from a quick glance.
• Does the spar line have any significance for the Hat version of the tiling? What about the Hat & Turtle versions of the Spectre tiling? Do those tilings have their own significant lines/features?

Acknowledgements and Further Reading

Thanks to the authors of the Hat paper for their discovery. They have also provided an information page for the public. Other articles covering the discovery can be found here, here, and here.

Update

I have posted a follow-up that builds upon the ideas in this post. Check it out here.

Footnotes

1. This proof may be similar to the non-periodicity proof given by Shigeki Akiyama and Yoshiaki Araki in this paper released after the original post. ↩︎
2. In fact, for any tiling which allows you to colour spar lines like the Turtle prototile, at most half of all negative crossings are free. ↩︎
3. For two given parallel line spacings, each opposite side pair picks up a reciprocal sine from the angle between sides. You only get one sine back when you get parallelogram area. ↩︎