Monotillic Musings

Andrew Stacey


Creative Commons License


  1. Home

  2. 1. Introduction

  3. 2. Matching Rules

  4. 3. Charge

  5. 4. Substitution Rules

    1. 4.1. Super Clusters

    2. 4.2. The H7 and H8 Substitution Rules

    3. 4.3. Neighbourly Substitutions

    4. 4.4. Subclusters

  6. 5. Conclusion … for now

1 Introduction

The recent (at time of writing) announcement of an aperiodical tile, as in Figure 1, caught my attention for more than just the "Oh, this is interesting" reason.

Figure 1: The new aperiodical hat tile

I have two pieces of code that were originally developed for exploring Penrose tiles and so my first reaction was to include the new tile in those. That meant a fair bit of code refactoring1, but also a close examination of the new tile from a different perspective than if I'd just been exploring it as a tile.

1Mainly because the original code is relatively old and I've learnt a bit about programming since I originally wrote them.

The two programs are a TikZ library for drawing tilings and the other is a program I wrote using the iPad app Codea. Both originally were written specifically for Penrose tiles, but have been extended in the years since they were first devised.

Key features of the TikZ library are:

Key features of the Codea program are:

The validity testing and the generation mode both rely on the same underlying idea which is that when a tile is placed (either by hand or automatically) then the program will test its exposed edges to see if it is possible to place a tile next to each one that doesn't overlap the existing pattern2. This means that the program needs to know which edges can go alongside each other.

2This is the first level of checking, it can be made deeper. The normal Penrose tiles only needed one level of checking, but the pentagonal system needs two.

So my initial focus with the new tiles was to look carefully at the matching rules. I also wanted to include at least some of the clusters (super, meta, sub) in my code to make the programs as broadly useful as I could. The remark about the subclusters being awkward (starting on p16 of the preprint) intrigued me as well and this led to me looking at the subclusters more closely.

In this closer examination of the subclusters my attention was drawn to the F0 and P0 tiles in particular. These are especially interesting as they seem designed to allow alternative edge matches to those permitted "by default". That is, if we view the labelling of the edges in the Figure at top of p18 of the original article as the default matching rules for the H0 and T0 subclusters then the F0 and P0 provide exceptions to these rules.

Perhaps the mathematical habits of a lifetime came into play here and prompted me to focus for a bit on those exceptions. Indeed, removing the H0 and T0 tiles and looking just at the F0 and P0 provides interesting structures. These have been highlighted by others – including in the original paper – in regard to the super and meta clusters; I think that including the subclusters in this analysis is particularly illuminating.

This focus feeds in nicely to considering the substitution rules. With both the TikZ and Codea programs then I've found the substitution mechanism to be both useful and interesting. So it is a little disappointing that there isn't a direct substitution system for the polykite tiles themselves. Implementing them for the super clusters is straightforward, though, and for the TikZ library then I've adapted it to use the combinatorial substitution rules to generate polykite tilings. My current implementation for the Codea program uses the positional information more integrally so is a bit trickier to adapt to the neighbour information. So at the moment, the Codea program only implements the substitution system for the super clusters.

2 Matching Rules

A key feature of the standard sets of Penrose tiles is that they have matching rules. These can be enforced by deforming the edges but it is more common to decorate the tiles with arcs that have to align, as in Figure 2.

Figure 2: Penrose tiles

The new tile, which I'll call an aperiodical hat, doesn't need matching rules. It is made up of edges of two lengths3 and there are no a priori restrictions on which edge can match with which. So my first implementations, both for the TikZ library and the Codea program, allowed any edge of a given length to match or align with any edge of the same length.

3There is one extra long edge which is actually best viewed as two short edges.

The problem with this is that there are several of each, and this causes issues for both programs. When using the TikZ library I found myself continually counting and losing count of the edges and having to remember where the starting point was. The Codea program uses the matching rules to test whether a tile is valid by trying to place tiles next to it and if there are lots of ways a two tiles can be placed next to each other then this process is very slow.

In fact, it is even worse than just a linear increase. That there are many possible edge matches, but not all will be eventually valid, means that when checking a tile is valid then it is necessary to try placing not just one extra tile next to it but maybe two or more. If I can figure out some edge combinations that could never occur in a valid pattern then I can rule them out as potential matches from the outset and so make it easier to create patterns in both programs.

So for both programs I wanted to have a better understanding of the possible edge matchings. Because the subclusters (at least, the H0 and T0 tiles) are themselves hat tiles, I thought to examine them a little more closely to see if they could shed light on how the hat tile itself worked.

The diagram at the top of p18 and partially reproduced in Figure 3 is particularly intriguing. It is clear from that diagram that the individual edges of the hat tile are best thought of not separately but grouped. Also, the whiskers – and the comparison with the meta and super cluster tiles – show that these tiles should really be thought of as deformed equilateral triangles. So in the TikZ library, the subcluster tiles (that is, the H0 and T0 tiles) are actually equilateral triangles with a specific edge deformation already applied.

Figure 3: The subcluster tiles

This means that the subclusters are actually the most straightforward way to use the TikZ library at the moment, as there are only three edges for each of the main tiles, as in Example 4.

  every subcluster H/.style={draw, thick},
  every subcluster T/.style={draw, thick},
  every subcluster F/.style={draw=red, ultra thick}
\pic[subcluster H, name=A];
\pic[subcluster F, name=B, align with=A along b1];
\pic[subcluster F, name=C, align with=B along f];
\pic[subcluster F, name=D, align with=C along f];
\pic[subcluster H, name=E, align with=C along b using 1];
\pic[subcluster H, name=F, align with=D along b using 1];

Figure 4: Example of positioning subcluster tiles

This approach doesn't work for my Codea program as that hasn't been designed to allow for tile deformation, so I need to work with the original tiles4. However, the subcluster matching rules can be used to refine those for the hat tiles.

4For implementation reasons, I was already working with the original tile and its reflection.

The first step in this analysis is to label every segment of the subcluster tile paths, including the whiskers and also regarding the longest segments as two short segments. This is shown in Figure 5.

Figure 5: Labelling the edges of the subcluster tiles

Let's start with the T0 subcluster. The matching rules for the subclusters determine most of the matching rules for the individual edges directly, as in Figure 6.

Figure 6: H0 tiles surrounding a T0.

Sides 2 to 5 of T0 match against 11 to 8 or 5 to 2 of H0. Sides 8 to 11 match against 17 to 14 of H0 as do 14 to 17. This leaves just sides 1 and 18. To figure out what happens with these, consider Figure 7.

Figure 7: An H0 tile next to a T0.

The top edge of the H0 tile can be matched by either a T0, P0, or F0. The T0 and P0 both then force tiles that mean the original T0 is completely surrounded. The F0 leads to an overlap meaning that it actually doesn't fit. So the possible patterns are as in Figure 8, which means that sides 1 and 18 of T0 match against each other and against 14 and 15 (respectively) of H0. We'll see later that the left-hand side of Figure 8 is actually not possible so we can exclude the match between sides 1 and 18 of T0.

Figure 8: Continuing from an H0 tile next to a T0.

The H0 tile obviously has a lot more possibilities. Obviously, all the matches to edges on T0 are already accounted for so the focus is on H0 matching with itself. Figure 6 shows that edges 1 and 18 match but other than that, the self-matches of H0 must involve the P0 or F0 tiles. The two B0- edges on an H0 subcluster tile give two ways that the P0 directly attaches to H0s, as in Figure 9. For the F0 subcluster tile then it makes sense to put three together as that is the only way that the F0± edges can match, then there are four ways of directly attaching these to H0s, as in Figure 10. After attaching each H0, the P0 that attaches to the inner L edge of each F0 is forced and if the A0- edge of the P0 is free then that forces an H0.

Figure 9: H0 tiles with P0.

Figure 10: H0 tiles with F0.

The P0 tiles provide matches between 18, 17, and 16 with each of 3, 4, 5 and 9, 10, 11.

The F0 tiles provides matches as follows:

Lastly, we need to look at how the P0 and F0 tiles can be combined. These will adjoin along their L edges. At first sight there are several ways that these can combine but in fact it can't be that two P0 tiles adjoin.

The F0 tiles can align in multiple ways, both with themselves and with P0s. The focus is on how the L edges match, since the F± edges on an F0 can only align with another F edge on another F0 – so the F0s always come in threes. The Ls on an F0 can either match with any other L edge except that the inner L cannot align with itself.

A few of the possibilities are shown in Figures 11, 12, and 13. In the last of these, I've used a more colourful design partly because it looks nice and partly because the way that the F0 tiles intersect their neighbouring H0s means that it can be tricky to see which part of an H0 belongs to which tile.

Most of these yield combinations already encountered, but Figure 11 produces a match between the pair 18 and 1 with 15 and 14 while Figure 12 pairs 1 and 2 with each other. Also, the right-hand side of the lower right diagram in Figure 10 shows that sides 1 and 8 match.

Figure 11: A family of F0s with a P0 adjoined.

Figure 12: Two connected families of F0s.

Figure 13: A colour wheel of of F0s.

I claim that this is all the matches that can happen. To verify that, I can create a list that I know must contain all possible matches but which might have some that cannot actually occur and then look at the difference between the two lists. To make that list, I consider how edges align under the subcluster matching rules including the whisker edges on the H0 and T0 tiles. Then I trace how edges match up.

For example, edge 1 of T0 matches with edge 6 of H0. Edge 6 is back-to-back with edge 7 (of H0), so anything that edge 7 of H0 matches with is a potential match for edge 1 of T0. By tracking these potential matches, I can make a list of all the potential matches. I have a Python program to create this list.

The excess matches that this throws up are:

We've already examined edge 1 of T0 and seen that it can only match against H0 edge 15. The other potential matches all directly lead to overlaps and so are clearly invalid. Therefore, we have found the entire set.

Lastly on this, my iPad program can use this information to generate a tiling by successively adding tiles to an existing pattern. To do this, it obviously uses the matching rules to try to place a tile against an already placed one. But just because a tile matches against the existing pattern doesn't make it a valid tiling because it might lead to an invalid patch further down the road. As an attempt to avoid this, my program uses the following scheme:

The base level of invalidity is the most obvious one: the tile can't be physically placed because existing tiles block it. The next level works like this. The tile itself works, in that it is validly placed without overlapping existing tiles and it matches wherever it has an edge in common with the existing pattern, but when we try to place tiles around it then we can't. There is at least one edge where whenever we try to place a tile then it overlaps the existing pattern. Note that we don't look for a simultaneous surrounding of the tile, just each edge in turn.

So the program has a checking depth which means that when it tries to place a tile then it checks its validity to that depth. With kite-and-dart and rhombii Penrose tiles then I found it only necessary to check if a tile was 1–invalid. With the pentagonal Penrose tiles then I had to go to level 2.

I've not yet determined how deep the aperiodical hats have to go. I sometimes get a valid pattern with checking depth 2, but not always.

3 Charge

Maybe it's because I occasionally talk to particle physicists that the subcluster diagrams put me in mind of a couple of things from that field. The P0 and F0 "tiles" look very much like particle tracks, and the choice of ± for the edge matches puts me in mind of charge conservation.

I'll start with the second of these. Looking at the charges on their edges, it is clear that each H0 and T0 tile has net charge -1, the P0 tiles are neutral, and each F0 tile has net change +1. We can use this to look at how the subcluster tiles are put together.

The charge is also geometric in that the H0 and T0 tiles are essentially equilateral triangles with deformed edges. The deformations, though, are not balanced in that the deformed path cuts away part of the tile and so each H0 and T0 has less area than its underlying equilateral triangle. However, they can only be placed as if they were equilateral triangles. So eventually, the deficit (or charge) builds up until it needs addressing.

The other aspect that we need to bring in is the structure of the F0 and P0 tiles. An F0 tile has to form part of a triumvirate and those three F0 tiles produce six L edges which must match P0 tiles. The underlying shape of a P0 tile is a straight line and at its ends it must match either another P0 or an F0. So from an F0 triumvirate then six lines emanate travelling in the six hexagonal directions (though not co-central) and these are continued along P0s until they encounter another F0. This means that the F0s and P0s carve up the plane into triangular areas which are filled with H0s and T0s.

Since each matched edge is neutral, the net charge inside a region must be visible on its boundary. An equilateral triangular region with n equilateral triangles on its edge has n2 triangles in its interior, so as each of those triangles is an H0 or T0 it has a net charge of -n2. Each edge can transmit only one unit of charge, so the maximum charge across the boundary of such a triangular region is 3n. Therefore, the maximum size of a triangular region is when 3n+n2=0 which means that n=3.

However, this largest size is not possible. The reason being that along one of its edges there would have to be two P0s both pointing inwards meaning that they are pointing outwards of the next area and this can't happen. This can be seen at the bottom of Figure 14 where there is an unfillable region.

Figure 14: A triangular region with 9 subtriangles showing an impossible match at the bottom.

So the possible regions have size 1 or 2, as in Figure 15.

Figure 15: The possible triangular regions.

Now the F0 triumvirates have to contribute charge. Geometrically, this means that they have to somehow compensate for the area deficit between viewing the tiles as equilateral triangles and the actual deformed tiles. I think of the way that they do this as analogous to techniques from origami tessellation. When folding a tessellation pattern then there can come a point where one has "too much" paper at a location whereupon a twist is done to use up the excess paper. In Figure 16 then the grey lines are where the paper overlays itself via a fold with the black edges as the visible edge. Six such folds meet –roughly – at a point where a hexagon is formed to flatten the connection.

Figure 16: Origami tessellation

In this way, the F0 triumvirates can introduce "charge" – equivalently, compensate for the area deficit – by offsetting the regions against each other. The P0s along the sides of the regions then perpetuate this offset.

Focussing on the regions like this also brings in the other "particle physics" aspect: the jagged lines looking like particle tracks. By drawing just the outlines – so the P0 and F0 tiles – and not the H0 and T0s then it will look like particles splitting and recombining at the F0s and travelling along the P0s. Adding a little animation to this would be fun!

Figure 17: Particle tracks

4 Substitution Rules

I use the substitution rules for the Penrose tilings with both my iPad and TikZ code as a way to generate a tiling of a large area. Unfortunately, the substitution rules for the polykite tilings are a little more complicated as the true substitution system only works for the super clusters. However, the combinatorial data for a super cluster tiling can be used for a subcluster one so it is theoretically possible to generate a super cluster tiling using the substitution rules and then use the adjacency information to generate a subcluster tiling.

There's a very nice posting about this, and similar topics, which points out an issue with this in that the two tilings will cover different regions. However, for my use cases then this isn't a big factor – with the TikZ library, for example, it is never going to be the most computationally efficient way to draw a large patch – if one wanted to do that then a better strategy would be to generate a tiling by some other program which is then imported into TikZ. The more likely scenario for using the substitution rules is just going to be to draw a relatively small patch directly. Similarly, my iPad program isn't designed to produce extremely high resolution diagrams but just be a way to explore the tilings at "human" scale. So in both cases a bit of trial and error to get the right region will not, I think, be a huge drawback.

A more significant snag is that my original implementation of the substitution systems for Penrose tilings – in both the iPad and TikZ code – worked purely on positional information. So it was simplest to start with the super cluster substitution systems.

4.1 Super Clusters

Both my iPad and TikZ library have implementations of the super clusters so although my feeling is that they were introduced as a means to an end, it is nevertheless perfectly possibly to implement the substitution system directly for the super clusters using my existing framework.

In the TikZ library, the substitution rules work as follows. Starting with a seed string of characters, it applies replacement rules to each of those characters in turn. This is repeated until the required depth is obtained, at which point it switches from rules to actions. These interpret the symbols to, eventually, draw the tiles at certain locations and in certain orientations.

The dictionary of symbols that I use for the super clusters is:

  1. H, T, P, F represent the tiles themselves. In the replacement stage these are successively replaced by longer strings and in the action stage these represent the actual tiles.

  2. s denotes scaling by ϕ-2. In the replacement stage then the transformation symbols are not themselves replaced (but are left in the string).

  3. x{..}, y{..}. These all represent a movement by a certain step horizontally or vertically (relative to the current coordinate system). The units are set so that these move on a hexagonal grid.

  4. r{..}. This rotates by its argument.

  5. [ and ]. These introduce scoping so that transformations only apply within their scope.

The replacement rules are so that each tile is replaced by one or more tiles at a scale of ϕ-2 with certain positions and rotations. The positions and rotations depend to some extent on the orientations of the tiles. The original paper does not settle on a particular orientation for the clusters but rather draws them in different orientations at different places in the paper, as appropriate for the work of the given section. For the replacement rules, I've used the orientations as in Figure 18. Also important is to identify the "origin" of each tile. For the H, T, and P tiles I've set the origin to be its centre. For the F tile, imagine overlaying it with a P tile in the obvious way and fix its centre at the same as for the P tile.

Figure 18: The super cluster tiles with their orientations

With these orientations, the replacements are as follows.

Figure 19 shows a result of this substitution system.

Figure 19: A depth 3 substitution starting with the string H

4.2 The H7 and H8 Substitution Rules

On page 18 of the preprint, there is an alternative substitution system not based on the clusters but on two groupings of tiles, one with 7 tiles and one with 8. I initially thought this might be a positional substitution system so spent a little while thinking about implementing it. I no longer think that it is positional, based on trying to get the second level of substitutions to line up. It may be that I am not interpreting it correctly, but I've decided to leave it for the time being.

However, while investigating it then I did discover something interesting. I wanted to work out the ideal area scale factor, so looked at the long term behaviour of the system. Each H7 tile is replaced by a single H7 and five H8s, while each H8 by a single H7 and six H8s. So if there are a lots of H7 and b lots of H8 prior to a substitution then there will be a+b lots of H7 and 5a+6b lots of H8 afterwards. In the long run, this should stabilise so that the ratios of H7s to H8s is constant.

One way to investigate this is to set it up as a matrix equation:


To find out what happens in the long run we look at the eigenvectors and eigenvalues of the transition matrix. This has characteristic polynomial:


The solutions of this are:


The dominating eigenvalue is 2+3ϕ and it has eigenvector


So in the long run, the ratios of H7s to H8s converges to 1:1+3ϕ. In the limit, a single substitution multiplies the numbers of both H7s and H8s by 2+3ϕ, so this is the area scale factor.

The numbers 1+3ϕ and 2+3ϕ are ones that I've encountered before. This introduces a new angle on those Golden Numbers. The Golden Ratio itself, ϕ, can be found in the ratios of the eventual fate of the golden triangle and golden gnommon under their substitution rules and these are linked to Penrose tiles. So maybe each of the Golden Numbers can be associated with a tiling by a pair of tiles, say A and B, so that in the substitution then each of A and B are replaced by a single A and some number of Bs where the numbers of Bs differ by 1. In the notation of the Golden Numbers post, the ratio of As to Bs would then be some ϕn,α.

4.3 Neighbourly Substitutions

For the other families of tiles, if I want to use the substitution system then I need to figure out a way to retain the neighbour information.

When placing a tile, I need to know:

  1. The type of tile (H, T, P, or F);

  2. Its neighbour to position it against;

  3. The edge of the neighbour to use;

  4. The edge of the new tile to use.

The TikZ library accesses tiles via labels, so the second item on that list can be the label. It will be useful for the replacement system to also note the type of the neighbour tile, and its own label. Therefore, a tile is stored as a token list consisting of the type, label, and edge of both the new tile and the neighbouring tile. An example of such is:

 {HTa{A1}} {01} {00}

This represents a tile of type H with label 01 which is placed next to an existing tile of type T with label 00. The a edge of the H tile is placed next to the A1 edge of the T tile. Note that in the encoding system, the A± edges are labelled a for A+ and A for A-, and where a tile has multiple edges of the same type they are A1, A2 etc. The braces are for implementation reasons so that the code "sees" this in a particular way.

Now when this tile is replaced, then the H tile becomes 10 new tiles (a T, and three each of H, P, and F) while the T tile becomes an H tile. The new H tile (replacing the T) is placed first and then the tiles from the H are placed afterwards, starting with one of the tiles that is adjacent to the T tile. The order of placing these new tiles will depend on which edge is used to place the original H tile, meaning that there needs to (potentially) be replacement rules for every possible pairing of two tiles next to each other.

The current implementation is actually slightly shorter because unless the starting conditions are chosen specifically then every tile can be placed using an A or B type of edge, so only replacement rules for these need to be specified. In addition, there are a few shortcuts on creating the rules that I was able to exploit which made it relatively straightforward to code.

I even got to the point where my first guess for the rules was the right one, which was helped considerably by spotting that under the replacement rules then A± edges and B± edges swap. So that if, as above, an H tile was placed next to a T tile along an A–type edge then in the replacement a P tile (of the H) will end up next to the H (of the T) along a B–type edge.

With this, it is now possible to create diagrams such as Figure 20 in only a few lines of code.

Figure 20: A level 4 decomposition showing subclusters F0 and P0 only.

4.4 Subclusters

The subclusters have the same structure as the other clusters so it is interesting to see what happens to those with the substitution rules.

Figure 21 shows the replacements for the individual tiles, except for T0 which is simply replaced by an H0. Figure 22 shows a possible substitution for a set of 3 H0 tiles surrounding a T0. What is interesting about this substitution is that it looks as though the scale factor is 12 and that the extra space needed for the H0 tiles introduced by the P0 and F0 substitutions comes about by folding space, reminiscent again of tessellation origami.

Figure 21: Substitutions of F0, H0, and P0 subcluster tiles

Figure 22: Substitution of H0 and T0 subcluster tiles

5 Conclusion … for now

I'm quite pleased with what I've been able to implement in both the TikZ library and the Codea program. Getting the combinatorial substitution rules into the Codea program would require a fair amount of code refactoring that I'll shelve for the time being, but having it for the TikZ library feels quite significant.

There's plenty to continue investigating, and the relationship between tiling sets and Golden Numbers is intriguing.

For now, though, this seems like a reasonable place to pause on the development and maybe write up some documentation.