Beyond “Beyond the wall”

Some more thoughts on finite-state transducers for aperiodic tilings

[Simon Tatham, 2024-07-16]

[Part of a series: Penrose and hats | Spectres | finite-state transducers | more transducers]

• Introduction
  • Recap of the setup
• Improved algorithms
  • Improved adjacency recogniser
    • Building a state machine via equivalence relations
    • Iterating to completeness
    • Evaluation
  • Coordinate finder
    • How the coordinate finder works
    • Output modes
• Penrose tilings via whole-tile substitution systems
  • P2 whole tiles: ugly but practical
  • P3 whole tiles: practical and pretty!
• The H₇/H₈ systems for hats and Spectres
  • Matching up the edges
  • Doing the same for Spectres
  • What’s the point of all this?
  • Transducer construction failure
• Singular tilings
  • P3 tilings via de Bruijn’s pentagrids
    • Singular pentagrids
    • Finding singular and symmetric tilings
  • Singular Spectre tilings
  • Singular hat tilings
• Stars and propellers
  • Spectre + star + propeller tiling
  • Doing the same for hats
• What’s the best substitution system?
• Conclusion
• Software
• Acknowledgements and references

Introduction

The more articles in a series you write, the harder it becomes to write the introductions.

This is now my fourth article on the subject of generating aperiodic tilings by using string-processing algorithms. In two last year, I described recursive algorithms that allowed practical software generation of random patches of Penrose, hat and Spectre tilings while avoiding integer overflow, floating-point errors, or wasting lots of time on generating parts of the tiling that were only going to be thrown away. And in a followup last month, I found a way to replace the recursive algorithm with a non-backtracking finite state machine, giving slightly better performance, but also making it possible to generate (and also, sometimes, discover) particularly interesting non-random instances of all of those tilings.

That last article, ‘Beyond the Wall’, took me a long time to write, because when I’d nearly finished it, I fixed one last bug in my code and found it had completely changed my conclusions, so I had to rewrite half of what I’d already written. So by the time I was finished, I thought, phew, it’s time for a rest, let’s think about something other than tilings.

But I had so much interesting feedback from ‘Beyond the Wall’ that I quickly found there was enough material for a followup article. And then I also made a breakthrough of my own, improving the previous article’s algorithms so they can handle really hard tilings that I didn’t know how to do last month.

So here’s the followup article, containing everything I’ve learned since the last one!

Recap of the setup

As I write more articles in this series, it also becomes harder to recap everything that’s gone before. If you haven’t read ‘Beyond the Wall’ then perhaps not a lot of this will make sense. It’s probably best to treat this article as one of those sequels that really expects you to remember the previous episode.

But I’ll give it a quick try anyway. If this doesn’t make enough sense, there are three previous articles in the series – linked from the header above – to fill in more detail.

All of the Penrose, hat and Spectre tilings are generated by various ‘substitution systems’, which give a procedure for turning one tiling of the plane into a finer one by substituting each tile for a collection of smaller ‘subtiles’ in a fixed pattern. Moreover, every tiling of the plane can be shown to be a possible output of this process, starting from a larger set of ‘supertiles’. (That’s normally how you prove tilings like this are aperiodic.)

This idea allows you to take a single tile T in a tiling, and assign it an infinite sequence of ‘coordinates’ describing its place in the substitution hierarchy. You start by saying what type T itself is; then you say what type its supertile S is, and identify which of S’s subtiles T corresponds to. And then you give the same information relating S to its supertile S′, and so on.

In my notation, I write this as a tile type, followed by a sequence of (supertile type, child index) pairs, where the ‘child index’ refers to an arbitrary numbering system I chose for the subtiles of each supertile. For example, in the hat HTPF substitution system, where after the first layer of actual hats you have metatiles named by those four letters, a tile’s coordinates might start something like “hat, (F, 0), (H, 2), (F, 1), …”. This is saying that the tile is a hat, which is #0 of a lowest-order F metatile (this type expands into two hats, which my arbitrary numbering system indexes as #0 and #1); that F in turn is child #2 of a higher-order H (in another arbitrary numbering system I chose), which is #1 of another F, and so on.

(For the triangle-based substitution systems for Penrose tilings I vary this slightly. Those systems have the property that no supertile has two subtiles of the same type, so I leave out the child indices and just give the sequence of triangle types, which is unambiguous and a lot shorter.)

These coordinates are purely combinatorial: they don’t describe the tile’s geometric position in the plane at all, still less the position of any of its supertiles. They only describe its place within the hierarchy of parent/child relationships between tiles and supertiles. And it turns out to be possible to determine the combinatorial coordinates of a tile’s neighbour, starting from those of the tile itself, by one of two algorithms:

• Recursively ascend the layers of the hierarchy until you find a supertile containing both the tile and its neighbour. Then the coordinates from that point on are all the same between the two tiles, and you can work back down from that point generating the low-order coordinates of the neighbour.
• Where possible, use a finite-state transducer to output the neighbour’s coordinates from the low order upwards, by consuming the original coordinates in the same order. The output will sometimes lag behind the input, but only by a bounded distance.

In each case, you also tell the algorithm which edge of the starting tile you want to cross, and the output tells you not only what tile is on the other side of that edge, but which edge of the destination tile corresponds to the specified edge of the source tile.

The transducer approach is more powerful in one way: it doesn’t depend on there being any single supertile containing both the tile and its neighbour. Therefore it can cross ‘infinite-order supertile’ boundaries, of which I showed many examples in the previous article. My particular approach is especially interested in cases where the sequence of coordinates is eventually periodic, which means that I often represent an infinite-order supertile by describing just the repeating section of its coordinates, ignoring the initial part (which just describes whereabouts in that supertile you are). For example, in the previous article I showed a picture of the (E, 6)(G, 2) supertile in the 10-hex hats system – and also the (G, 2)(E, 6) one, which is not the same one, because they differ in whether the (E, 6) coordinates appear in the even or odd positions.

On the other hand, not every substitution system makes it possible to construct a transducer. The hat HTPF algorithm in particular does not – but a different substitution system for the hat tiling, based on 10 different hexagonal metatiles found by Brad Klee and Bowen Ping, does.

Transducers are constructed from a simpler kind of state machine that I call an ‘adjacency recogniser’. This consumes two input coordinate strings, by taking one symbol at a time from each one (as if they were combined by Python zip()), and tells you whether they represent neighbouring tiles. The initial pair of symbols, giving the types of the two actual tiles, is augmented with a pair of indices specifying an edge of each tile, so that the question the machine is answering is ‘Is this edge of this tile adjacent to that edge of that tile?’.

For the hat HTPF system, it’s easy enough to make an adjacency recogniser, but the process that turns one into a finite-state transducer fails, because it doesn’t stop after finitely many states. But some tilings are even difficult to construct an adjacency recogniser for in the first place.

Improved algorithms

At the end of my previous article, I mentioned a couple of things I’d still like to improve on in my algorithmic techniques. I wanted a better technique for building the ‘adjacency recogniser’ state machines, capable of handling extra-difficult spurs and disconnectedness which my previous algorithms struggled with. I also had an untested idea about a ‘coordinate finder’ algorithm, which could walk around an unannotated patch of tiling and figure out what combinatorial coordinates might represent it, by refining a state machine every time it stepped between two tiles.

I’m pleased to say that I’ve successfully managed both of those! So I’ll start by presenting them.

Improved adjacency recogniser

The way I presented adjacency recognisers in the previous article, each state of the machine (apart from START) represented a pair of tile types, and a pair of edges along which those tiles were adjacent. From there, you could figure out whether to accept an input symbol giving you each tile’s relationship to its supertile, and if so, how the supertiles would have to be adjacent in turn.

That setup was nice and simple. You could draw an adjacency recogniser for a simple substitution system (like the ones for Penrose half-tile triangles) by hand on paper, if you wanted to. And you could look at the output of the generation code and check by eye whether you thought it looked sensible.

But that technique is fundamentally not powerful enough to handle this substitution system for entire Penrose tiles, mentioned at the end of the previous article:

In this system, suppose you’re told that edge #3 of a kite is supposed to join to edge #1 of a dart, and then you find out that the kite is #1 of a larger kite, and the dart is #2 of a larger kite. What happens?

Initial tiles With siblings Supertiles

The two supertiles don’t share any edge. Instead, they only join at a corner. The previous system has no way to represent that state of affairs – but it certainly is a legal thing that can happen in a P2 tiling!

So the previous adjacency-recogniser scheme is too limited. It’s not enough just to have states that represent a pair of tiles sharing an edge. We also need to be able to represent situations like this one, in which the tiles touch at a vertex, with some particular angle between them.

I tried rewriting the code that generates adjacency recognisers so that its state descriptions were in this form. I got it working on at least one tiling, but very slowly: partly because it was relying on Sage’s algebraic number system to calculate vertex coordinates without rounding error, and mostly because there are a lot of possible states of this type, but most of them are dead ends, in the sense that they’ll never lead to an accepting state. Exploring all the dead ends was taking most of the time.

Then I had a much better idea.

Building a state machine via equivalence relations

Each symbol in a tile’s coordinate string, after the initial one, indicates what its supertile type is, and which child of that supertile the original tile was. This implies a fixed geometric relationship between the tile and its supertile.

And a particular symbol pair, as received by the adjacency recogniser, transforms the geometric relationship between its input tiles into a geometric relationship between its output tiles, in a fixed way. So if two states of the adjacency recogniser are ‘equivalent’ in the sense that they represent the same two tiles in the same relative position and orientation, and both states make a transition on the same symbol pair, then the two destination states are also equivalent. Conversely, two states that make transitions to equivalent states on the same symbol pair must also be equivalent.

This leads to a purely symbolic algorithm for constructing a state machine, as follows:

1. Use the recursive coordinate transition algorithm to generate a corpus of finitely long pairs of coordinate strings that are adjacent.
2. Rearrange these into strings of symbol pairs, i.e. into input strings which the adjacency recogniser should accept.
3. Make a nondeterministic state machine that matches only those strings. For each input string S, add a path of transitions from START to the appropriate ACCEPT(tile type) state for S, via its own collection of intermediate states not used for anything else, with the transitions labelled with each symbol of S in turn.
4. Now find equivalences between the states of this machine, according to these two rules:
   1. If two states s,t have transitions on the same symbol pair to states u,v respectively, and s,t are already known to be equivalent, then mark u,v as equivalent too. (In particular, if s,t are actually the same state, this will be true. So the algorithm begins by merging a lot of pairs of states that are both reachable from START by the same symbol pair.)
   2. Conversely, if the destination states u,v of the two transitions are already equivalent, or are the same state (such as an ACCEPT state), then mark s,t as equivalent.

After step 3 of this procedure, we have an adjacency recogniser that is sound (it won’t accept any invalid input), but very incomplete: it won’t accept any input that wasn’t in our finite input corpus. But step 4, merging states, enables it to recognise a much larger set of strings, including strings longer than any in the input corpus – and by the geometric argument above, it preserves soundness.

That’s a bit abstract, so I’ll show a simplified example. In this example I’ll temporarily forget the detail that input symbols are pairs of two-part coordinates, and pretend our state machine is dealing with simple letters of the alphabet; I’ll also forget that an adjacency recogniser needs multiple accepting states (one for each tile type), and pretend we have just one.

I’ll also imagine that our input corpus, showing strings that must be accepted by the machine, consists of just two strings: “abc” and “abdbc”.

In this simplified situation, step 3 would build a state machine looking like this:

Now step 4 finds equivalences:

• States 1 and 3 are both reached from START on the same symbol a, so we mark them as equivalent.
• Now, states 2 and 4 are reached from the equivalent states 1 and 3 on the same symbol b, so we mark those as equivalent too.
• States 2 and 6 both transition to the same state ACCEPT on the same symbol c, so we mark them as equivalent.
• And now, states 1 and 5 transition to equivalent states 2 and 6 on the same symbol b, so we mark those as equivalent.

Now we’ve merged all the states we can, and we have four equivalence classes left: START, {1, 3, 5}, {2, 4, 6}, and ACCEPT. If we condense each of those classes into a single state in the diagram, then the transition from state 4 to 5 on symbol d becomes a backward edge – so we get this:

To begin with, this state machine has become deterministic, because the equivalence-finding procedure merged any pair of states that were reached by the same transition from the same previous state.

But also, we can see from this diagram that the machine doesn’t just match “abc” and “abdbc” any more. Now it also matches “abdbdbc”, “abdbdbdbc”, and every longer string with more repetitions of bdbdbd in the middle. We’ve extended the input corpus, sort of ‘by analogy’, to match an infinite set of strings that it didn’t mention explicitly.

Iterating to completeness

That’s the simplified example. Now we return to the original application of building an adjacency recogniser.

In this case, our input corpus consists of a finite set of pairs of coordinate strings describing adjacent tiles. After we do the Step 4 merging operation, we’ve extended our state machine to match an infinite set of pairs of coordinate strings.

But have we got all of them? It will depend on the input corpus – and if the corpus isn’t big enough, we can try again with a bigger one.

As the initial input to this algorithm, we provide all the pairs of strings that the recursive algorithm is able to generate without needing to recurse beyond some fixed depth k – that is, pairs of input and output strings with length up to k. We start by choosing k reasonably small, so that we can make some progress quickly. So it’s likely that the initial step won’t produce a complete recogniser.

Next, we check if it is complete, using the technique described in the previous article: make its Cartesian product with the much simpler state machine that represents all legal coordinate strings, and search that product machine to see if it contains any state where the ‘legal input’ machine has a transition but the adjacency recogniser doesn’t.

If it’s not complete, we go back to step 1 of the procedure above, using a larger k, so that some longer pairs of strings appear in the input corpus.

We don’t need to start from scratch in each iteration. We can keep all the states and equivalences we’ve already generated; we only need to generate some extra strings to add to the input corpus, and some extra states. Then we don’t need to redo any of the existing work.

Also, we don’t need to generate all input strings of the new longer length. Many of them will just be extensions of shorter strings we already saw. So we can remember each input string where the recursive algorithm went too deep on the previous iteration, and use those as the starting points to generate strings for the next iteration. That way we avoid redoing any work.

So now we just keep on iterating, increasing k each time, until the completeness check passes.

Is there a guarantee that this will terminate? Not that I know of. Outside the context of adjacency recognisers, it’s certainly possible to think of cases in which the equivalence-class algorithm won’t terminate.

But in every case I’ve tried involving an actual tiling, this technique has terminated, and delivered a complete and fully usable adjacency recogniser. It works for all the tilings that the previous system was able to handle; it works for the P2 whole-tiles system shown above; it works for the corresponding P3 system, which is even more difficult – see below. And it even works for the hat and Spectre H₇/H₈ systems, which I didn’t mention in the previous article, and which are also too difficult for the old algorithm. I’ll discuss those later as well.

Evaluation

I’m really pleased with this technique!

The code is considerably simpler than my original algorithm, which needed to do a lot of detailed thinking about tile edges and vertices, and had special-case code for getting round spurs. And yet it handles a strict superset of tilings.

Despite being a geometrically inspired algorithm, it doesn’t actually have to think about geometry at any point: it never has to calculate any coordinates, or perform any geometric transformation. In particular, it makes no difference at all that the Spectre expansion systems reverse the handedness of everything. My previous attempt, computing all the geometry explicitly, needed a special case for that which negated all the rotations. This algorithm doesn’t even notice, and if it did notice, it wouldn’t care.

It’s also fast. It avoids both of the problems that made the explicitly geometric approach slow: it doesn’t do any calculation at all with numerical coordinates, and it never wastes time on exploring dead ends, because every state generated from its input corpus is pre-selected to have at least one possible path to an ACCEPT state. In fact it turns out to run faster even than my original adjacency recogniser construction, although not by much.

It handles spurs – even extra-difficult ones – without even having to know they were there. When we call the recursive algorithm to generate the input corpus, that deals with spurs, by recursing an extra time every time it has to cross one. But once we have an input corpus, that work is done, and all we have to do in this algorithm is to make a machine that matches whatever the resulting patterns in the input strings were – without knowing or caring whether any spur traversals were involved in generating the input strings. It ‘just works’, almost like magic!

A measure of how well it works is that I don’t even know how far it ended up having to go to handle the difficult tilings. We can see from the above example that in the P2 whole-tiles system you can have pairs of tiles meeting only at a vertex. Maybe that means there are even worse cases in which the geometric relationship between two tiles doesn’t even involve them meeting at a vertex, but somehow, still have a path back to an accepting state? I have no idea! If there are any cases like that, then this algorithm handled them without needing any special code, and I never even had to find out whether that’s a thing that can happen.

I feel as if this general algorithm ought to have other uses! But I haven’t thought of one yet.

Coordinate finder

In the previous article I mentioned another possible application for a transducer: instead of using it to convert an input string of coordinates into an output patch of tiles, you could run it in reverse, if you already had a patch of tiles and wanted to find some coordinates consistent with them.

That seemed like a fairly theoretical sort of possibility at the time. Yes, you might see a patch of Penrose tiling in a book and have some reason to need to reproduce it in a coordinate-based system – but it’s not exactly likely. I was curious to try the idea out to see if it worked, but I didn’t really expect it to be useful for anything.

But I was wrong! Not long after I published the previous article, I was presented with just this problem, because somebody had generated a Spectre patch of particular interest via a totally different technique, and we wanted to find its coordinates. (I’ll discuss the patch in question later.) So I wrote the coordinate-finder and tried it out.

It worked almost exactly the way I’d imagined, except for one detail I got wrong when I suggested it in the previous article: you don’t actually need a transducer to do this job. It turned out actually easier to use the adjacency recogniser directly, because that delivers exactly one output symbol per state transition, which was more convenient than the way a transducer delivers output in irregular lumps, sometimes not delivering a symbol at all and sometimes more than one. The tradeoff is that the adjacency recogniser isn’t deterministic – sometimes it can deliver multiple possibilities for the next symbol – but in this case, where we wanted to keep track of all the possibilities anyway, that was just fine.

So the coordinate-finder I ended up with works with NFAs rather than DFAs, and depends only on an adjacency recogniser, not a transducer. This is actually better, because it means you can still use it for substitution systems that don’t admit a transducer!

How the coordinate finder works

The basic idea of the coordinate finder is: you’re sitting on a particular tile of your input patch of tiling, and you have an NFA representing all the possible infinite coordinate strings that might describe that tile. Initially, you know nothing except the shape of that one tile – so your starting NFA simply represents all legal coordinate strings that describe a tile of the appropriate shape.

Now you walk around the patch by stepping from one tile to a neighbour. At each stage, you build a new NFA that describes all the possible coordinate strings for the destination tile, consistent with whatever you knew about its neighbour that you just came from, and the way in which those tiles are connected to each other. This is done by making the Cartesian product of the previous NFA with the adjacency recogniser; searching that combined state machine to find the subset of states in which the NFA is consistent with one side of the input to the adjacency recogniser; and using the other side of the adjacency recogniser’s input in those states to generate the output NFA.

So, as you walk around the tiling, your NFA changes in two ways. At every step it describes the possible coordinates of the tile you’re currently sitting on, so as you walk around, it changes to reflect a different actual tile. But also, it ‘remembers’ the history of every tile it’s already visited, so as you walk around, it becomes more and more constrained, due to the need to stay consistent with all that history.

So now you just have the problem of walking around your entire patch of tiling, visiting every tile so as to collect as much information as you can, and finally returning to whichever tile you actually wanted to know the coordinates of. After you’ve done that, the NFA will show you possible coordinates for the tile you finished on, that are consistent with everything you visited on your walk.

I considered finding an efficient route around the patch using a sophisticated approach like an approximate TSP solver, but it wasn’t necessary: this algorithm runs quickly enough that it probably would have wasted more time to try to plot an optimal route to save building a few NFAs.

So instead I did the simplest possible thing: do a depth-first search over the input patch of tiling to make a spanning tree of it, and then your route around the patch is simply to traverse that tree starting and ending at the root. This can’t take more than twice the optimal number of steps, and that’s fast enough.

(I considered the possibility that the algorithm might need to traverse every edge of the tiling patch, but it doesn’t seem to have been needed: visiting every tile has worked fine for me so far.)

Output modes

As I’ve described it, the output you get from this coordinate finder is an NFA – a non-deterministic state machine – which describes all the possible coordinate sequences consistent with your input patch of tiling. There will be infinitely many possible sequences, because in tilings based on hierarchical substitution any finite patch of tiles shows up infinitely often all over the place. Also, each individual sequence is infinitely long in its own right. So the only way to show all the possibilities, in full, in finite space, is to exhibit a finite state machine that generates them.

A nondeterministic state machine isn’t very readable; it improves readability to determinise it first, using the standard NFA→DFA subset construction. That way, if the input tiling patch is large enough to leave only one possibility for the first (say) five coordinates of the output, you can see that at a glance, because each of the first five states of the machine has only one transition to the next. With the raw NFA you might have to explore lots of branches before you could be sure there was only one possibility.

Even so, a DFA is not the most readable thing. You’d like to be able to return an actual coordinate string! But, of course, the problem is that there are too many options to choose from.

One thing you could do would be to choose randomly. Generate an output patch of tiling using the ordinary recursive algorithm, making up coordinates lazily as if you were making a random patch – but keep track of your location in the output DFA, and whenever you make up the next coordinate, choose randomly from the options in that DFA. This would give you a random tiling which agrees with the input patch – and you could do it again with different random numbers, generating lots of random outputs all agreeing on the input patch.

Here I show an example of doing this. I manually retyped the details of the central decagon figure from the P2 “cartwheel pattern” that I showed in the previous article’s appendix; then I fed it to the coordinate finder, and got it to generate five different random patterns consistent with the resulting state machine.

Input

Random outputs: 1 2 3 4 5

But in the case where I first used this algorithm, I didn’t want a random extension of the input patch. I had reason to believe that the input patch was likely to correspond to a simple and eventually periodic infinite coordinate string, like many of the examples in the previous article – and I was trying to recover that string.

There will be lots of different eventually periodic coordinates that are consistent with any NFA of this kind. You only have to follow transitions at random, and at some point, when you’re in a state you’ve been in before, choose to start repeating your past route forever. And there are infinitely many choices you could make, because you don’t have to start repeating yourself the first time you return to a previous state – you could wander around for as long as you like first.

But if a large input patch ‘really’ corresponds to some particularly simple thing, like repeating the same single coordinate forever, then you’d be likely to get an output NFA in which the first (say) five coordinates were fixed; the last four of them were all the same; and repeating that final coordinate forever is permitted by the NFA. In that situation, that eventually periodic string is far more likely to be the true answer than any you’d find by choosing some other random repeating loop after the five fixed coordinates.

So I also wrote an output mode that would answer the question “What is the simplest eventually periodic coordinate string consistent with this NFA?”, where ‘simplest’ is defined as a combination of the length of the repeating string, and the length of initial segment until you reach the repeating part. This worked very well, and recovered the coordinates I wanted.

So, those are the three potentially useful outputs from the coordinate finder: a DFA that shows you all possibilities, randomised selection that gives you an arbitrary concrete example, and the specialist mode of ‘find the simplest repeating one’ which is suitable for the kind of highly symmetric and theoretically interesting patterns the previous article was focusing on.

Penrose tilings via whole-tile substitution systems

The improved adjacency recogniser algorithm can handle some substitution systems that the previous one couldn’t. Let’s look at two of them in particular, relating to Penrose tilings.

P2 whole tiles: ugly but practical

In a previous section I showed an example of a substitution system operating directly on P2 kites and darts, without having to cut them up into half-tile triangles first. This was one of the substitution systems that my previous algorithms couldn’t handle at all, but my improved algorithms can. So I now know how to build an adjacency recogniser for that system, and better still, it successfully generates a deterministic transducer.

Using this transducer to generate P2 tilings is convenient, because you don’t need a postprocessing step in which you expand each triangle back into its full tile and discard duplicates. If I wanted to recommend a practical tiling generation mechanism to someone now, for random patches of tiling or interesting symmetric ones with eventually periodic coordinates, I’d definitely pick this. The transducer is a tiny state machine (31 states); the algorithm never has to backtrack (whereas the recursive algorithm would if you used it with this system, due to the spur in the dart’s expansion); and it can directly generate the tiles you want as output.

However, the triangle-based system still has value when it comes to understanding Penrose tilings. The whole-tile system is practically convenient, but not nearly so illuminating.

In particular, Penrose tilings have a symmetry property, which is clearly shown in the triangle-based system: each triangle type has a mirror image, and the mirror image of a tiling is obtained by a simple transformation on its coordinates. But the whole-tile substitution system has to break that symmetry. As a result, it’s much harder to look at a coordinate string and have any idea whether you expect it to represent a symmetric instance of the tiling, or to find its mirror image if it doesn’t.

The infinite-order supertile boundaries show the same asymmetry. Here’s the ‘cartwheel pattern’ from the previous article’s appendix, regenerated using the whole-tile transducer, with the infinite boundary shown in a thick line:

What on earth is that boundary doing?! It’s weaving about all over the place, with apparently no relation at all to the ten-way near-symmetry structure of this pattern, and also no relation to the one line of true symmetry (the vertical line down the centre). It’s not even rotationally symmetric about the centre, or even nearly so.

If this pattern is drawn using the half-tile triangles, the infinite supertile boundary is a straight line, running vertically along the line of true symmetry. That makes logical sense; you can see why the line is there. But this boundary has no logic or usefulness at all. It’s absolutely unrelated to any structure you were interested in. And it’s not even pretty – on the contrary, it looks as if some vandal has scrawled an ugly jagged line across a beautiful pattern.

But as long as you don’t show the infinite supertile boundaries, this is a very convenient way to plot P2 tilings. So we’ll just leave it at that.

P3 whole tiles: practical and pretty!

Also in the previous article, I exhibited the following substitution system for the Penrose P3 rhomb tiling, again using the whole tiles instead of cutting them into two triangles:

I wasn’t at all sure whether it would even be possible to make a finite-state adjacency recogniser for this system. I tried for a while using variations of my older techniques, and the kinds of problem I ran into made me start to doubt that it would ever work. An obvious oddity is that the expansion of the thin rhomb isn’t even connected, at least in the sense of tiles meeting edge-to-edge. Once you expand by several levels and look at how larger patches relate, worse problems show up, like multiple spurs running along the same line, with potential ambiguities about which one is on which side. It looked almost unmanageable, and I gave up on trying to make a state machine for it at all.

But my new equivalence-class based adjacency recogniser algorithm has no difficulty with it! Once I’d got it working on a simpler system, I test-ran it on this one, without much hope – and, completely to my surprise, it just worked. It generates a complete and correct adjacency recogniser, which also admits a deterministic transducer.

(I have no idea how it got round all the problems I had when I tried to do this by hand. But it did. One of the great things about the new algorithm is that it doesn’t make you think about those details at all!)

So, just as in the previous section: if you want a practical technique for generating P3 tilings, then a transducer constructed from this system is now my recommended one.

As in the P2 case, the asymmetry in this system makes it less useful for understanding than the symmetric half-tile triangles system I was using before. But here’s some better news. Unlike that ugly lumpy infinite supertile boundary we saw in the P2 case, the results of the asymmetry in this case are really pretty!

When I successfully built a transducer for this system, my very first thought was: if the expansion of the dart isn’t connected (or rather, only vertex-connected), then what happens if we iterate expansion of the dart? What weird shape do you get if you take a dart, which is child #0 of a dart, which is child #0 of a dart, … for ever?

This is exactly the kind of question that transducers answer without any difficulty. And I hope you’ll agree that the results are well worth the effort:

That’s both intriguing and lovely! The infinite supertile containing the original dart is shown in blue. When I generated the whole image, it turns out to share the plane with three other different infinite-order supertiles, shown here in red, orange and yellow.

All four supertiles are disconnected if you consider only edge-to-edge adjacency of rhombs, although it looks as if they’re all connected vertex-wise. (I haven’t done the maths to prove whether or not this is true all the way out to infinity; I’m only going by what I see in this picture. But it looks very plausible to me.)

The blue supertile seems to be forming a kind of spiral. The connected regions get larger and larger as you spiral outwards, and smaller as you spiral inwards. At the inner end of the spiral, the single blue thin rhomb at the very centre of the image is the starting one.

The other three supertiles all have coordinates with period 3. One of them is (thin, 1)(thick, 0)(thick, 1) – that is, a thin rhomb which is child #0 of a thick, which is child #1 of another thick, which is child #1 of a thin, going on for ever. The other two are cyclic rotations of the same pattern (which you’d expect, since the pattern as a whole must be invariant under a single expansion).

I’m particularly pleased that these disconnected infinite supertiles worked, without confusing the transducer algorithm! That’s another thing I wouldn’t have been confident predicting in advance. But it’s all fine – as the drawing algorithm transitions into one of those isolated blue rhombs and out the other side, the transducer is quite happy to say ‘ok, you’ve left this infinite supertile and gone into that one’ on the first transition, and ‘… fine, whatever, you’re back in the first one again’ on the second, and nothing goes wrong. It’s really satisfying when your software effortlessly negotiates a special case that you hadn’t predicted and didn’t write any extra code to account for!

I mentioned in the previous section that these whole-tile substitution systems are asymmetric. So another question that sprang to my mind was: what would the mirror image of this tiling look like?

There are several ways to find that out. One approach is to convert to triangles and back. The triangle-based coordinates of one end of the central rhomb above are CCCC…, which implies that the coordinates of its mirror image must be DDDD…. (See what I mean about it being easy to work with symmetry in the triangle representation?) From there we could laboriously convert back into the whole-tile substitution system.

(Incidentally, in the triangles system, the coordinates CCCC… don’t lead to any infinite supertile boundary at all – there’s just one trivial infinite supertile, covering the whole plane.)

But an easier, if slightly cheating, approach is to reuse our coordinate finder! I generated a graph-theoretic description of the picture above, and then just rewrote all the edge indices in every description of an adjacency between tiles, so that they described the mirror-image edge. Then I fed that to the coordinate finder, and asked it for the simplest eventually periodic coordinate string matching the input patch. The input patch was big enough to be confident of the result.

The result is shown below, in mirror image. That is: I found the coordinates describing the mirror image of the above tiling, and then I reflected it again, so that it matches the above tiling. That way, you can flick back and forth between the two images using the radio buttons below, and see for yourself that all the actual rhombs are the same, and only the supertile structure has changed.

An equivalent way of describing this is: suppose that instead of finding the coordinates of the mirror-image tiling in the same substitution system, I had instead found the coordinates of the same tiling, under a P3 substitution system that is the mirror image of the one shown above.

Anyway, here’s the mirrored representation of the same tiling:

Reflected Original

It’s different, and yet, it’s the same. Here, there are only two infinite supertiles, namely the two rotations of (thin, 1)(thick, 0). But you can see the same kinds of feature in the boundary between them; I think they’re spiralling outwards in the same sort of way, although all the details are different.

Finally, here are a couple more particularly pretty tilings. These are the two P3 tilings with the symmetry of a pentagon, which I showed in the previous article, having generated them using the triangle-based substitution system. In that system, the infinite supertile boundaries were straight lines along the axes of reflection symmetry. In this system, they resemble the boundaries above – only vertex-connected, and asymmetric under reflection. But the patterns as a whole must still be rotationally symmetric, because they consist of five copies of the same infinite supertile. So this time the not-quite-connected fractal-ish boundaries spiral around the origin in a symmetric way:

Star Ring

Since the five supertiles in each of these pictures all have the same coordinates as each other, it was a challenge to find a way to colour them differently when generating these pictures! The trick is to think about directions. We assign a direction to each tile type by drawing an imaginary arrow on it; then, each (parent tile, child index) symbol in a coordinate string indicates a particular relationship between the arrow directions of the child and parent tiles. So you can start from the coordinates of any single tile in this picture, and determine the orientation of all of its supertiles. Every tile has an eventually periodic coordinate string, so sooner or later you reach the repeating section; after that point the sequence of orientations must repeat with period dividing 10, because the supertile coordinates themselves have period 2 and there are 10 possible orientations. So you can distinguish the supertiles by asking about the limiting orientation of the supertiles whose orders are multiples of 10.

The H₇/H₈ systems for hats and Spectres

Here’s another important pair of substitution systems which I didn’t mention in the previous article.

In the paper introducing the hat tiling, there’s a diagram of a substitution system with only two types of metatile, rather than the four in the HTPF system (or the ten of Brad Klee and Bowen Ping’s hexagons):

The two expanded clusters of hats are labelled H₇ and H₈, because they contain 7 and 8 hats respectively.

When I wrote the previous article, I didn’t mention this system. I’d seen it in the paper, but I’d never been able to make it work in my software at all, so I had nothing useful to say about it. I don’t just mean that my underpowered adjacency recogniser algorithm couldn’t handle it (although that would certainly have been true); I mean I couldn’t even make the simpler recursive algorithm work with it, because I couldn’t describe the system precisely enough to tell the code how to match up the edges. Which parts of the complicated edges of those clusters correspond to which edges of the hats they were expanded from? I tried quite hard to figure it out, but never managed it.

After I published the previous article, Pieter Mostert discussed it with me on Mastodon, and kindly provided the hint I was missing.

Matching up the edges

The first secret is to start by assigning two properties to each edge of the hat tile: a colour (shown here as either green or yellow), and an orientation (shown as an arrow on the edge, indicating which end is its ‘front’ and which its ‘back’). Orientations simply alternate forward and backward as you go round the tile; colours are assigned based on whether the edge’s direction is an odd or even multiple of 30°. This also means that the green edges are the shorter ones and the yellow edges are longer, because it’s the nature of the hat tiling that those two properties go together – all the short edges are multiples of 60° apart from each other, and the same for the long edges.

(I’ve drawn double arrows on the yellow edges, for an extra visual distinction.)

Once you’ve done that, the second secret is to expand each green edge consistently to a path of three edges, and each yellow edge to a path of five, in the patterns shown below. The arrow on the single input edge shows which way round the pattern of output edges goes. If the input edge is rotated, then the output edges are rotated by the same amount.

(This looks silly because the expanded edges don’t go in remotely the same direction as the originals, or even as each other! But it will all work out, you’ll see.)

Next, we start with the outline of an ordinary hat tile, and transform it by mapping each edge in turn through this transformation. The region enclosed by the resulting outline is a complicated shape which – as if by magic – just happens to be tileable with eight hats!

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Tiled

(If you’re wondering where those extremely weird and non-intuitive expansion rules came from, or why they work, I’m sorry to say that I have no real idea! I worked them out by starting from a different pair of edge expansions that Pieter Mostert described for a related tiling system, but that was routine algebra – the difficult part had already been done. Somebody somewhere did something extremely clever to come up with this, but it definitely wasn’t me. I tried, and failed!)

So that’s how you match up the edges of the original hat to the edges of the expansion: each hat edge maps to the 3 or 5 edges it was expanded into. If you’re expanding a tiling in which edge i of hat H and edge j of hat K coincide, then those edges must have the same type, and so they expand into the same sequence of 3 or 5 edges when each hat is turned into one of these patches. And then the rule is that the two expanded patches are placed so that the sequences of edges expanded from edges i and j also coincide.

In fact, this is generally the way the edges work in all these tiling systems – the edges of the tiles have various types, with or without directions, and each edge type expands consistently to the same pattern of output edges. It’s just that this system is particularly convoluted and non-obvious.

You can see that at one point in the diagram above, the path of output edges doubled back on itself, creating a zero-width spur. That too is normal – it’s the same way that spurs are created in the other systems that have them.

But we’re only half done. What about the other hat cluster, the H₇?

To answer that, I’ll start by showing what happens if you apply the same mapping to the reflected version of the hat:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

This procedure doubles back on itself a lot more than the previous one. Why’s that? Because the expansions of the green and yellow edges are set up so that when the input edges meet at a right angle with the original arrows both pointing toward the meeting point, the two output expansions either meet with the endmost arrows pointing towards each other (creating a double-length edge green edge with two inward arrows), or pointing in the same direction (causing the outline to double back), depending on which way the right angle goes. And in the hat outline, one direction of right angle happens much more often than the other. So expanding a normal hat gives you mostly straight edge segments, and only one doubling-back; expanding a reflected hat, where all the right angles reverse, it’s the other way round.

After you discount all those doublings-back, it looks as if the reflected hat has expanded into a single unreflected hat. But it’s stranger than that. The output outline has gone round the hat the wrong way – on the left-hand side we went anticlockwise, and on the right-hand side, clockwise. This indicates that the reflected hat has expanded into a true anti-hat: it cancels out a hat-shaped piece from whatever outline you combine it with!

So, when we combine a normal hat with a reflected one, the expanded outlines combine too, giving the outline of an H₈ cluster, composed with a reversed outline that cancels one of its hats. That’s where we get the H₇ outline from.

(It doesn’t matter whether the two hat outlines are traversed in full, going back and forth along the line separating them, or whether we just trace round the outside of the overall shape. If the input outline doubles back, then the output outline will too, so it makes no difference to the final shape.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Tiled

In this expansion there are some even stranger spurs. Many of the previous substitution systems I’ve shown have spurs poking out from the expansion of a tile, but this is the first that has a spur poking inwards. Even more confusingly, part of the actual outline is traversed three times – forwards in step 12 of the above animation, backwards in step 14, and forwards again in step 15. I find it easiest to think of that as a spur that just happens to lie along the boundary!

I made one arbitrary choice in doing this: there are two possibilities for which neighbour of the reflected hat you combine with it. The one above is from the hat paper, but making the other choice also works, and gives you this different outline:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Tiled

Doing the same for Spectres

There’s a similar system for Spectres, shown in Figure 2.1 of the Spectre paper. It works almost exactly the same way as the hat one we’ve just seen – the two tilings are closely enough related that you can derive one of these transformations from the other by group theory.

We begin in the same way, by assigning each edge of a Spectre a colour based on its direction, and an orientation alternating around the tile edge. But for Spectres, that means there are two classes of tile, because the majority of Spectres in a tiling are at angles that are a multiple of 60°, but a few of them are rotated by 30° compared to the rest. In this labelling system, that means all the edges swap colours:

In this system, the two colours of edge don’t correspond to different lengths: the transformation that turns a hat into a Spectre is precisely to make all the edges the same length. But the directions of the edges still correspond to the two colours.

The edge expansion rules are similar to the previous pair, but not quite the same. In particular, this time it’s the green edge that expands to five sub-edges, and the yellow to only three:

Using these rules, a single Spectre in the common orientation expands to a region that can be tiled with Spectres, very like the one for hats:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Tiled

There are two differences between this and the hats version. Firstly, it takes nine Spectres to tile the output cluster, not eight. But also, the Spectres on the right are reflected, compared to the one on the left! This is a consequence of a fact we’ve already seen in other Spectre expansion systems: each time you expand a Spectre tiling, it reflects the whole plane. You have to expand an even number of times to get back to the same way round you started.

The rest of the setup works analogously to hats. If we expand the skew type of Spectre, which has the green and yellow edge types swapped, then the expansion generates a Spectre in the ordinary orientation (though again reflected), but it traces the boundary in the opposite direction to the input. So, just as with the hats, the unusual kind of input Spectre expands to an anti-Spectre which cancels something from another expansion:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Finally, to avoid this awkward anti-tile in the resulting substitution system, we combine the skew Spectre with one of its neighbours, to create the symmetric double-tile described in the Spectre paper as a ‘Mystic’, and expand that via the same rules, to generate a patch with 8 rather than 9 output Spectres:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Tiled

Just as in the hat version, there’s an arbitrary choice of which neighbour you fuse the skew Spectre with. The above version is from the paper, but again, the other version works too if you prefer it. The two fused Spectres still have the same overall shape as the Mystic, but it’s not the true Mystic, as endorsed by the discoverers – you can tell, because its orientation is off by 30° and all its edges are the wrong colour. Perhaps we should call this combination a ‘Charlatan’?

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Tiled

What’s the point of all this?

I’ve described these two substitution systems in great detail for several reasons. Firstly, just because this information about the edge mappings is useful, and wasn’t available anywhere else obvious; it took me some effort to derive this even with hints, and having done so, I should share the results!

Secondly, as I mentioned above, this is also quite a good illustration of how these substitution systems in general work, when it comes to figuring out how the edges of tile expansions connect together. I didn’t bother to go into all the details in the previous articles in this series, but the general setup of all the substitution systems I’ve dealt with – with one exception – involves the same notion of tile edges having both types and orientations, so that two edges can only connect if they have the same type and orientation. (That is, the orientations match in the sense that the arrows go the same way along the edge where the tiles meet – but that means the orientations are opposite, from the point of view of walking in a consistent direction around each tile’s boundary, say anticlockwise.) Then each edge type expands in a consistent way to a sequence of other edges, so that the expansion of any single tile is made by expanding its outline and then filling in tiles in the interior of the resulting region, so that the edge types inside the region match the edge types generated by expanding the boundary.

In both P2 and P3 Penrose tilings, the edge types and orientations correspond exactly to the matching rules that prohibit the periodic tilings you’d be able to make easily if you treated the tiles as plain quadrilaterals. There are two edge types in each case; in P2 they correspond to the two different lengths of tile edge, but in P3, where all the edge lengths are the same, they’re selected in a less obvious way.

In the triangle-based substitution systems I’ve been using for those tilings in previous articles, we introduce two extra edge types when we cut each tile down the middle. Each of those edge types is unique, enforcing that the triangles must join back together in a way that makes full kites, darts or rhombs.

And when you expand each triangle into smaller triangles, each edge type maps consistently to the same sequence of other edge types, wherever it appears. The same is true for the whole-tile systems I’ve shown in this article; the only difference is that in the triangle-based mapping the image of each edge is a straight line, whereas in the whole-tile systems, the image of each edge involves output edges with angles between them. In fact most of these systems involve angles; the Penrose triangle systems are the only ones I know simple enough not to need them.

The Spectre paper, when it presents the 9-hex substitution system, gives an explicit labelling of eight different edge types for the hexagons. (One of them is unusual in not having an orientation, meaning that its expansion has to be 180° rotationally symmetric.) In my own presentation of the system I showed those edge types as jigsaw-piece distortions of the hexagon edges. I didn’t show the details of how the expansions were worked out, but again, the complicated outline of each expansion is obtained by mapping each edge type consistently to the same pattern of output edge types, with the same angles between them – and there’s one rule for mapping hexagons to another layer of hexagons, and a different one for the final mapping of hexagons to Spectres.

The one exception, of a substitution system that doesn’t have a mapping of edge types at all, is the overlapping version of the HTPF system for hats. That doesn’t need one, because it matches up adjacent tile expansions in a completely different way, by identifying the overlapping parts with each other! But the non-overlapping version of HTPF has a system of exactly the same kind again, which I luckily didn’t have to work out for myself, because I found an exposition of it in a paper (referenced from the previous article).

A third reason why I wanted to present these H₇/H₈ style systems for hats and Spectres is that, in some sense, they’re as close as you can practically get to the ‘true’ substitution system for these tilings, showing what’s ‘really’ going on.

What I think of as the ‘true’ substitution system for hat and Spectre tilings is the same as these systems, but without merging two tiles. That is:

• Classify the tiles into two types, ‘normal’ and ‘weird’. For hats, the weird tiles are the reflected ones; for Spectres, the weird tiles are the skew ones, rotated 30° compared to the rest.
• Each normal tile expands to a single weird tile, surrounded by a small cluster of normal tiles in a fixed layout, all rotated into whatever orientation the input tile had. (We’ve seen those layouts in the diagrams above: the 8-hat or 9-Spectre clusters.)
• These clusters almost always join up at the edges perfectly, no matter what orientations they connect in. The one exception is that wherever a weird tile appears in the input, two of the output clusters overlap in exactly one tile.
• But then, each input weird tile expands to an output anti-tile, cancelling one of the overlapping pair. So you end up with the whole plane covered exactly once.

Why do I say this is the ‘true’ substitution system? For three reasons. Firstly, it operates directly on the actual tiles – the individual hats and Spectres – without needing an auxiliary system of metatiles. If somebody gave you a patch of hat or Spectre tiling without any coordinate labels, you could directly expand it into a larger patch by applying these rules, without needing to first figure out how the tiles grouped into your favourite kind of metatile. Secondly, this system also permits you to reverse the expansion process, generating the supertiles that would have expanded to the pattern you started with. And thirdly, it even gives rise to a geometric relationship between the coordinates of the input and output tiles – you don’t have to place each tile with reference to a previous one, you can directly calculate where each one must end up, even if you only know about its single parent tile. (However, for that to work you have to pretend the coordinates are four-dimensional, by treating the green and yellow edges as if they lived in separate copies of the complex plane – the vector space ℂ². Then the geometric mapping is a linear transformation.)

But because of the anti-tiles, you can’t work directly with this system using my coordinate-based approach, which needs every tile to expand to a non-negative number of other tiles with nothing getting cancelled after the fact, so that each tile has a single sequence of coordinates. And the minimal modification to achieve that property is to merge each anti-tile into one of its neighbours, just as we see above.

There’s one final reason why these systems are interesting – and it’s important enough to have a section to itself.

Transducer construction failure

Once I understood the complicated edge mapping in these H₇/H₈ substitution systems, I was able to represent them in my software in a way that at least allowed the recursive coordinate transition algorithm to handle them. Next, of course, I tried to feed them to my adjacency-recogniser and transducer construction code.

The old adjacency recogniser had no hope of dealing with them, because of the extra-difficult spurs. The inward spur is only a little bit tricky; the one aligned with the tile boundary is more awkward. But the really hard one is the one sticking out of the expansion of a single hat, or single Spectre. It doesn’t look that much harder than spurs we’ve already seen, in substitution systems I was handling successfully in the previous article. But it is harder, because it’s so long. In particular, it’s long enough to completely separate the expansions of two other adjacent tiles. That makes my old spur-handling technique fail, because that relied on a spur only reaching part of the way between two adjacent expansions – so the algorithm could slide sideways along the outline to find a pair of edges connecting the same two expansions without the spur being in the way. In this system, there isn’t always such an edge at all.

But then I developed my new equivalence-class based adjacency recogniser algorithm. And, just like everything else I’ve tried it on, the new algorithm has no trouble at all with these systems! It somehow finds a way to deal with those extra-awkward spurs, and it doesn’t bother me with the details.

So now I do have working adjacency recognisers for the hat H₇/H₈ system, and the Spectre analogue. But neither of them allows construction of a transducer. The transducer-building algorithm fails in the same way that it failed for the hat HTPF system: you find that there are input coordinate strings which have more than one possible valid neighbour, so that a transducer might have to look ahead an unbounded distance to be certain of the next output symbol, and in some cases, would never know it.

When the hat HTPF transducer construction failed, I was able to extract information about the failure, and convert it into a pair of very similar hat tilings, in particular containing an infinite supertile boundary with one side the same, and the other side different. But I didn’t know of any such case in the Spectre tiling, because I only had the 9-hex substitution system to work with, and for that system, the transducer construction succeeded. In fact, when I first found that pair of hat tilings, I guessed that the hat tiling itself might have a fundamental ambiguity that the Spectre tiling didn’t. It was only later that I realised the difference might be an artefact of particular substitution systems.

And indeed it is, because now we have a transducer construction failure in a Spectre substitution system as well! There are ambiguous infinite supertile boundaries in the Spectre tiling – they just go away when you use the 9-hex substitution, in the same way that they went away for hats using Bowen Ping and Brad Klee’s 10-hex system.

So, what next? Of course, we do the same thing as we did for hats: extract details of an ambiguous boundary from the transducer constructor’s failure diagnostics, find a way to generate the multiple possibilities for the far side of the ambiguous boundary, and see what they look like.

This time, we already have an unambiguous substitution system for Spectres – the standard 9-hex system. Better still, it matches up in a natural way to the layout of Spectres in the H₈ patch shown above (not surprisingly, since as I understand it that’s how the 9-hex system was derived in the first place). So I’ve been able to look at the coordinates of the ambiguous H₇/H₈ situation, and directly work out what 9-hex coordinates correspond to each possibility.

In fact, there are three possibilities, in this case. Here they are:

(Y, 7) (P, 7)(X, 7) (X, 7)(P, 7)

Just as in the hats case in the previous article, when these alternative versions of the same supertile are generated using the unambiguous 9-hex system, you can see that the Spectre at the very corner of the invariant side changes its colour, showing that the 9-hex coordinates for the three options are all different. That’s what allows the 9-hex transducer to generate the rest of the plane differently each time.

Also, just as in that previous case, the rest of the plane isn’t always divided into the same set of other infinite supertiles. In one case there’s a single infinite supertile occupying the lower section of the picture; in the other two cases, there are two.

In fact, the other two cases are actually the same case, rotated by 60°. The (P, 7)(X, 7) and (X, 7)(P, 7) infinite supertiles actually appear alongside each other. So I’m really only showing two different tilings of the whole plane – it’s just that in one of them, there are two regions that are both the same shape as the (Y, 7) supertile in the first picture.

And we’re not out of surprises yet! If you were really paying attention to my previous article (and I wouldn’t at all blame you if you hadn’t been), you might recognise the supertile coordinates (Y, 7). They’re the very first example that I originally started investigating, and later, showed as the proof-of-concept picture demonstrating that I’d managed to get a transducer to cross infinite supertile boundaries in Spectre tilings at all.

In a later section of my previous article, I actually suggested this possibility, while talking about the way that the hat tiling apparently had more than one sequence of 10-hex coordinates that generated the same shape and layout of infinite supertile:

But wait – how do I know that’s not true for Spectres? For all I know, the example I originally found could be in exactly this situation, and I might just not have found the other sequence yet!

I didn’t particularly believe that was actually true – I just mentioned it as a theoretical possibility, because I knew I hadn’t actually proved it impossible. But it turns out that, without knowing it at the time, I’d hit the nail right on the head. My original example of a Spectre infinite supertile boundary does have another sequence of 9-hex coordinates that generates the same layout (in fact, two of them), and I hadn’t found the other ones yet!

Another thing to notice, in the picture above, is how little the tilings differ from each other, on the far side of the invariant boundary. The tilings you get by putting the (Y, 7) supertile and the (P, 7)(X, 7) in the same part of the plane differ by just one wiggly path of Spectres, in exactly the same way that my ambiguous pair of hat tilings differed by a single wiggly path of hats. So those are worth showing again by themselves, with the differing path shaded, and the rest of the colours weakened to make it more visible:

(Y, 7) (P, 7)(X, 7)

And if you match the (Y, 7) supertile and the (X, 7)(P, 7) against each other in the same way, the same is true again, only the path is a different shape! This time, it’s less wiggly – there are more Spectres in each bend:

(Y, 7) (X, 7)(P, 7)

What about the (P, 7)(X, 7) and (X, 7)(P, 7) infinite supertiles? I haven’t shown those against each other, but the fact that two rotations of the same pattern are very similar to each other is definitely significant too, and I’ll discuss it in a later section. Also, the fact that two infinite supertiles of the same shape fit exactly alongside each other has another consequence that I’ll discuss in another later section.

I said above that the transducer construction also failed for the hat H₇/H₈ system. This time there’s nothing new to be found, though: the conflicting options I got from the diagnostics were all infinite supertiles that appear in the previous article’s ambiguous case. So this system and HTPF both fail in the same way, which is at least reassuringly consistent, even if it doesn’t lead to any interesting cases I hadn’t already known about!

Singular tilings

When I showed the P3 cartwheel pattern at the end of the previous article, I didn’t talk about where it came from, because I didn’t know. I just knew that someone had already discovered it, and that it was famous enough to be on book covers.

But it seems very mysterious, at first glance. It’s clear enough why there would be perfectly symmetric Penrose tilings of the plane: I was able to construct those from first principles, just by thinking about the triangle view of the tiles, and the way axes of symmetry run along the triangle edges. But nothing in that view of the world predicts, or explains, why there should be a nearly symmetric tiling with breaks in the symmetry along particular lines. You couldn’t imagine it happening by pure coincidence – there must be some kind of underlying reason why such a tiling exists. What is that reason? What else does it give rise to?

Since then, I went and read Nicolas de Bruijn’s 1981 paper on the algebraic structure of P3 tilings (see the links below), which gives the answer to these questions. I don’t have space to expound the whole thing here, but I’ll show the key idea, and how it predicts the existence of the cartwheel pattern.

Then we’ll move on to looking at similar instances in the hat and Spectre tilings!

P3 tilings via de Bruijn’s pentagrids

De Bruijn’s paper defines a structure called a ‘pentagrid’. This consists of ruling a set of lines across the plane with unit spacing, and then doing the same thing again four more times, each at a 72° angle (one fifth of a whole turn) to the previous one.

0 1 2 3 4 Full grid

The most natural way to do this is to make one line in each direction pass through the origin. But we want to be more general than that, so we’re going to permit the lines in each direction to be translated arbitrarily. That gives us an uncountable infinity of possible pentagrids, all different.

Each individual set of lines divides the plane into strips. In the diagrams above, I’ve assigned consecutive integer indexes to each strip, so that in the first set of lines the index increments by 1 every time you move one strip to the right, and in the other four sets, the same is true for the appropriate rotation of ‘right’. So when all the lines are superimposed, we end up with each mesh of the pentagrid – each small region of the plane bounded by grid lines – being assigned a tuple of 5 integer coordinates, which I’ll denote (x₀, x₁, …, x₄).

In the picture above, I’ve shown a few example sets of coordinates in particular meshes. (In a desktop browser, you can check them by leaving your mouse pointer on one of the marked regions, and using the keyboard to cycle the radio buttons through the individual sets of grid lines to confirm that it’s in the appropriately numbered strip in each case.) But I can’t show all the coordinates, because most of the regions are too small for the numbers to fit in the picture!

If you look at an intersection where two grid lines cross, how do the coordinates of the four surrounding meshes differ from each other? Three of the coordinates will be the same for all four meshes – the ones relating to the three directions of grid line that don’t meet at this intersection. Each of the remaining two coordinates will vary by 1 depending on which side of that line you’re on.

So, suppose we map each mesh to a point in the plane, by choosing five fixed vectors (v₀, v₁, …, v₄) to represent the five directions, and calculating the vector sum of x_iv_i for i = 0, 1, …, 4. Then the four meshes surrounding a pentagrid intersection form a parallelogram, with its edges given by whichever two of the v_i correspond to the varying coordinates.

So, as long as there aren’t any points in the grid where more than two lines meet, any pentagrid automatically constructs a tiling of the plane with parallelograms. Moreover, there are exactly ten types of parallelogram, one for each pair of grid-line directions that can cross.

What vectors (v_i) should we choose? Any choices would give some kind of a tiling with parallelograms; if we make the vectors all the same length, then those parallelograms become rhombuses. But we’re aiming to end up at Penrose P3 tilings, so the right choice is to take each v_i to be a vector of the same length at angle i × 72°, i.e. perpendicular to the grid lines in the ith direction. Then our rhombuses will be the right shapes to be P3 tiles.

Pentagrid Meshes → points Final tiling

Not every mesh maps to a point actually in the mesh. (Where it doesn’t, I’ve drawn an arrow in the diagram above, showing which mesh the point corresponds to.) It wouldn’t work if they did, because in places where all five directions of lines pass very close to each other, there are a lot of tiny meshes all together, and the points for those meshes must move apart quite a lot to make room for rhombuses. But if you choose the rhombus edge vectors to have length 2/5 the grid spacing (as I’ve done here), then de Bruijn proves that the distance from each mesh to its tile vertex is bounded by a constant. So no vertex moves too far.

This is a tiling of the plane with rhombuses the same shape as the P3 tiles. But it’s not an actual Penrose tiling unless we can also show that it respects the matching rules – the arrows on the rhomb edges that I showed in a previous section.

It turns out that this isn’t guaranteed, for any old pentagrid. But it is guaranteed to work if the grid lines have been placed so as to give the following special property: if you choose a point in the plane and extend lines in each of the five cardinal directions until each one meets the nearest perpendicular grid line, then the lengths of those lines sum to an integer. (If this works for one point, it will work for any point of the plane.)

Given this extra condition, de Bruijn proves that it’s always possible to draw arrows on the rhombus edges in a consistent way, so that each rhombus is labelled correctly to be one of the P3 tiles, and they connect in the ways approved by the P3 system. So we’ve constructed a Penrose tiling!

Singular pentagrids

If an intersection in a pentagrid has just two lines meeting there, then it gives rise to a rhombus in the tiling, because there are four meshes around that point, and each one makes a vertex of the tile corresponding to the point.

So, what happens if more than two pentagrid lines meet at an intersection? De Bruijn calls a pentagrid ‘singular’ if this happens anywhere (and ‘regular’ if it doesn’t).

In that case, you have more than four meshes around that intersection. Each one still generates a point in the output plane. So you expect to end up with a tile that has more than four sides: you don’t have a rhombus tiling any more, you have a tiling with rhombuses and some other things, like hexagons. In this picture, the vertical grid line down the centre has three-way meeting points all along it, and you can see that happening:

Pentagrid Meshes → points Final tiling

Obviously, this isn’t itself a Penrose tiling – some of the tiles aren’t even the right shape. But it’s very close to one. If this pentagrid still obeys the ‘distances sum to an integer’ constraint, then all the tiles other than the hexagons are still the right shape, and de Bruijn’s construction for assigning arrows to the shapes still works. So we have a Penrose tiling of most of the plane, with only these hexagons missing.

But wait. Those hexagons look about the right shape to be filled with some Penrose tiles, don’t they?

This isn’t a coincidence. Imagine if you moved the vertical grid lines to the left by a tiny distance ε, and adjusted another set of grid lines by a similarly tiny amount to preserve the ‘sum to an integer’ constraint. The effect would be that in place of every 3-way intersection, you’d have three 2-way intersections very, very close together. And those give rise to perfectly good Penrose rhombs.

Perturbing the grid lines like this will change the overall structure of the tiling, because no matter how small you chose ε to be, if it’s greater than 0, then somewhere in the infinite plane that movement will cause 2-way intersections to cross over to the other side of a third grid line, so that the pattern of rhombs changes. But the smaller you make ε, the further away the first discrepancy will be. So you could imagine ‘taking the limit’ as ε → 0, to get a tiling that matches this one in all of the actual rhombs, and the only difference is that the hexagons have been filled in with more rhombs, completing the Penrose tiling.

But now, suppose instead of moving the vertical grid lines to the left by ε, you’d moved them to the right. Then the same thing would happen – but the hexagons would be filled in the opposite way round, because the three grid intersections replacing each 3-way point would be arranged differently.

So the limiting tilings you get as ε → 0 from the left, and as ε → 0 from the right, are almost exactly identical, and they differ only in that one strip of rhombs along the line of singularity.

Move line left Singular tiling Move line right

There always is a whole line of singularity. In any pentagrid where three lines meet at a point, one of the lines always bisects the angle between the other two. That makes the outer two lines symmetric about the middle one, and that in turn means that the rest of the lines in those two directions are symmetric about the same line. Also, it turns out, the ‘sum to an integer’ constraint forces the other two directions of grid line to be symmetric in the same line. So you always end up with a pattern that has a line of reflection symmetry, as long as you leave those hexagons empty – but when you fill them in, you have to make a choice of which way to break the symmetry.

Or rather: there’s always at least one line of singularity. There’s one extra-special singular pentagrid we can make: the one that probably seemed most obvious when I described the concept to begin with. What happens if all five directions of line pass through the origin, so that there’s a 5-way intersection point?

Pentagrid Meshes → points Final tiling

Just as we expect, the 5-way intersection point gives rise to an empty decagon at the centre of the pattern. And since the pentagrid lines have reflection symmetry in all five of the lines through the origin, it follows that so does the resulting tiling – but, again, only as long as you leave those higher-order polygons empty.

How many different ways are there to resolve these singularities? It’s tempting to think: there are five lines of hexagons, each one can be resolved in two ways, so we have 2⁵ possibilities. But in fact not all of them make sense, because the choices aren’t independent.

De Bruijn has a degrees-of-freedom argument that simplifies things. We start off with five degrees of freedom in a pentagrid: each set of grid lines can be translated by an arbitrary distance perpendicular to the lines (and it doesn’t matter if you translate it parallel to the lines). We lose one degree of freedom because of the ‘sum to an integer’ criterion. And two more degrees of freedom must correspond to translating the entire pentagrid around the plane while keeping all the grid lines in the same relation to each other. That leaves two remaining degrees of freedom, so we can consider that the shape of a Penrose tiling is characterised by a single point in the plane! And when you move that point around very near the origin to resolve the singularities in this decagon, the grid lines through the origin divide that region of the plane into ten sectors, and the only important thing is which of those sectors you’re in. So there are ten possible answers, all rotations of each other.

That sounds very like the P2 cartwheel pattern, so you probably won’t be surprised to hear that this is exactly its P3 analogue. In fact you can convert between the two using the interleaved substitution system I described in a previous article, which allows you to expand a P3 tiling into a P2 one, and vice versa. If you resolve the singularities in this P3 pattern, and expand it into P2, you get the same Batman figure we saw to begin with.

Here’s the finished version of the P3 cartwheel, which has coordinates XYXYXY… in the triangles system (similar to the ABABAB… that I derived in the previous article for the P2 version). Compared to the picture above, this one is rotated 90°, to bring it into the same orientation as the P2 version I’ve already exhibited, with the line of symmetry vertical.

So this has answered the fundamental question of why there are very-nearly-symmetric Penrose tilings that differ only along one straight line. They’re generated from pentagrids that are actually symmetric – but are also singular, meaning that something awkward happens on the line of symmetry.

Finding singular and symmetric tilings

So, now that we know that, can we use this to find all the interesting instances of P3?

We’ll start by enumerating the pentagrids with 5-way symmetry about the origin. There aren’t very many of those, because of the ‘sum to an integer’ constraint. In a 5-way symmetric pentagrid, the distances from the origin to a grid line in each direction must all be the same. So if the sum of all five of them is an integer, it follows that the distance must be a multiple of 1/5.

So there are just five pentagrids with 5-way symmetry. One of them is the 5-way singular one we’ve just seen. The other four are not singular: no three grid lines meet in a point, because the only place that could sensibly happen is the origin, and the lines don’t go through there.

But these grids are still 5-way symmetric – it’s just that the lines of symmetry are perpendicular to the grid lines.

These four patterns correspond to the 5-way symmetric Penrose tilings I showed in the previous article. I only showed two symmetric P3 tilings there – but the other two are just the first two rotated by 180°. In the previous article I found that the combinatorial coordinate strings for those patterns repeat with period 4 – and that’s consistent with this analysis saying there are four of them. Cycling the coordinates round one notch at a time iterates through all four.

What about patterns that have just one line of reflection symmetry, or just one line of singularity?

The same phenomenon happens here. In a singular tiling, the line of not-quite-symmetry has to run parallel to a pentagrid line, which makes it perpendicular to the tile edges; but in a truly symmetric tiling, it’s the other way round, perpendicular to the pentagrid lines and parallel to the tile edges. (The only way you could get a non-singular tiling with a line of symmetry parallel to a pentagrid line would be if it was exactly half way between two pentagrid lines – but it turns out that that possibility can’t work: you can’t make the distances sum to an integer without the other four pentagrid directions ending up asymmetric.)

I can’t list all the symmetric tilings, or all the singular ones, because in both cases, there’s an uncountable infinity of them. This is predicted by both the pentagrid view of things and the combinatorial coordinate view. With pentagrids, once you’ve arranged for two pairs of grid lines to have crossings on a line of symmetry (of either type), you still have an uncountable set of possible exact positions for those crossings along the line of symmetry. And with combinatorial coordinates, if you expand a small section of the line of symmetry a few times until it contains more than one subsection like the original, identify the original section with an arbitrarily chosen one of those subsections, and repeat at larger and larger scales, then you’re making a countably infinite number of arbitrary choices from sets of size > 1, which again gives you an uncountable number of sequences overall.

But there’s one finite class of interesting tiling we can enumerate. We can list the tilings that have both properties at once: a line of true symmetry, and a line of singularity, perpendicular to each other.

To enumerate those, suppose we put the origin at the intersection of the two lines of symmetry and singularity. What are the distances from the origin to the other four grid lines?

The other grid lines come in two pairs; for the required symmetry, grid lines of each pair must either both pass through the origin, or both miss it by 1/2. Making this choice independently for each pair gives four possibilities. One of those involves all five lines passing through the origin, so it’s the cartwheel pattern again – which does count, because it does have a line of true symmetry, and one of the lines of singularity is perpendicular to it. The other three possibilities give rise to less symmetric patterns which have only the two symmetries we asked for.

So we’re expecting three different patterns – or rather, six, because each one comes in two forms, depending on which way you resolve the singularities.

How to work out the combinatorial coordinate representation of these? There are several reasonable approaches. One is to generate a patch of tiling using this pentagrid technique, and feed it to our coordinate finder. But a more analytic approach is to look at the pattern of hexagons along the line of singularity in the earlier diagrams, and think about how that line could possibly have reflection symmetry:

Each of the two hexagon types is symmetric about a horizontal line through its centre. (No matter which way you resolve the singularity – that flips the hexagon left/right, but either way, it’s still symmetric in a top/bottom flip.) Also, the taller hexagon can appear next to another copy of itself, which suggests that perhaps the line of symmetry could appear between two of them. The shorter wider hexagon can’t appear next to itself in the same way – it doesn’t take much checking to confirm that if you put two of them side by side then no P3 tile could fit in the gap.

(Of course, in the picture above, the rest of the tiling isn’t symmetric in any horizontal line through the midpoint of one of those hexagons, or through the line between two tall ones. But then, that picture wasn’t chosen to have symmetry in any horizontal line at all. We’re hoping to do better!)

So that suggests that we should expect our three singular patterns to have the line of symmetry in those three places: one bisecting each hexagon type, and one between two tall hexagons.

Also, what happens if you apply the expansion rules to one of these singular patterns? You must still get a mostly symmetric plane, with an anomaly down the middle. So it seems quite likely that these patterns are expansions of each other, in some order.

By that point you can figure it out by hand, without needing to go as far as the coordinate-finder algorithm. Work out what triangle type appears at the centre of the line of symmetry in each case; apply the expansion rules to see what that turns into; and see what happens.

The result is that you find a cycle of six coordinates, repeating the pattern XXX YYY XXX YYY… forever. And just as we half-expected, the first three cyclic rotations of that string generate the three types of singular pattern we expected to find. The other three generate their mirror images, which don’t count as different if you’re thinking about pentagrids, but certainly do count as different for combinatorial coordinates, which always want to specify all the tiles uniquely.

We can be reasonably confident that we’ve got them all, because the two representations agree: the pentagrid analysis predicted three mirror-image pairs, and the combinatorial coordinate system has found a repeating cycle of six patterns.

So here are those patterns in full. Instead of showing both mirror images of each one, I’ve shaded the line of tiles that change under a reflection, and lightened the symmetric area. So reflecting one of these patterns in the vertical axis changes only the shaded tiles.

XXX YYY Y XXX YY YY XXX Y

What about the P2 tilings? By considering the the interleaved substitution system, we expect that there should be the same number of symmetric and singular tilings for P2 as there are for P3, and moreover, we can obtain them by half-expanding each P2 one. This turns the XXX YYY repeating sequence of coordinates into the slightly less regular AVVBUU: the Vs and Us are interleaved between consecutive XX or YY, and the A,B appear between XY or YX. And here they all are:

AVVBUU UAVVBU UUAVVB

Singular Spectre tilings

To summarise the previous section very briefly indeed: it turns out that there’s a correspondence between Penrose tilings and points in a continuous space (namely the space of possible pentagrids), but the correspondence isn’t quite 1–1, because sometimes an extra-difficult ‘singular’ point in the indexing space maps to a thing which isn’t quite a complete tiling, and which can be completed in more than one way by taking a limit, depending on which direction you approach the singular point from. And these singular points also have a lot of symmetry, meaning that outside the incomplete region, the tiling is symmetric.

Well, it turns out that this isn’t special to Penrose tilings. The Spectre tiling has singular instances too, following essentially the same pattern. The differences are, firstly, that the strips of differing tiles in the resulting tiling follow wiggly curves rather than straight lines; and secondly, Spectre tilings don’t have any possibility of reflection symmetry at all, even approximate, so all the singular tilings have to be nearly rotationally symmetric instead.

After I published my previous article, Pieter Mostert responded on Mastodon describing a scheme for indexing Spectre tilings via a point in the plane, with the same property that along some curves in the plane you get a choice of two different Spectre tilings by taking limits from opposite sides of the curve. And where those curves meet, you get even more choices, in the same way that P3 tilings have 10-way singularity where all the lines converge at the origin.

I’m not able to describe the scheme in detail, because I don’t know all the details myself. But it seems to work, because he was kind enough to send me several data files describing patches of Spectre tiling with a very similar kind of near-symmetry to those singular Penrose patterns.

Of course, I wanted to know the combinatorial coordinates corresponding to those patches, so that I could re-plot them in my own software, and describe them concisely to other people. But all I had was a .csv file describing individual edges of the Spectre tiles – not even the tiles themselves, let alone any description of the hierarchy of supertiles. What to do?

This was the incident that made me get round to writing the coordinate-finder algorithm that I’d speculated about in the previous article. I processed Pieter’s initial data file until I’d recovered a description in terms of Spectres rather than individual edges, and knew which pairs of Spectres were adjacent, and which edges of the pair met in every case. Then I fed that description to my newly written coordinate finder.

It worked very well! The first data file I received contains a little over 50,000 edges, which my processing script converts back into 7,000 or so Spectres, occupying a roughly circular region. That’s enough that the coordinate finder was able to be certain of the first six coordinates of the central tile: it’s a Spectre, expanded from an S hex, followed by four parent tiles which are also all S hexes, with each one being child #3 of its parent. So the natural guess would be that the infinite coordinate sequence corresponding to this patch continues (S, 3) for ever. And indeed that is also one of the possibilities allowed by the DFA output by the coordinate finder.

The patch Pieter provided had 6-way near-symmetry – and so does the version I recreated from those coordinates. I’ve rendered it using the same colour convention as in the previous section: the light-coloured tiles are symmetric in all six rotations of the whole pattern, whereas the dark ones can vary.

Like all the best pictures in these articles, this one is both beautiful, and mathematically interesting. I hardly need to explain the ‘beautiful’ part – just look at those interweaving wiggly lines of variable tiles. Fantastic! Beats the straight spokes of the Penrose cartwheel, hands down.

Part of the ‘interesting’ is simply that this is a six-way singular tiling in the first place. Now I have some understanding of where those come from, it’s not so surprising that they exist, but it’s still interesting to see it as one of the things that these very different aperiodic tilings have in common.

But here’s another thing. This picture is another copy of my very first example of a Spectre infinite supertile boundary!

I describe it here as the (S, 3) infinite supertile, because those are the coordinates of the supertile containing the very centre of the pattern. But that supertile doesn’t occupy the whole plane. There’s an infinite supertile boundary, which I haven’t shown in the above image because it would spoil the symmetry – and on the other side of that boundary is our old friend (Y, 7) again. When I showed it in the previous article I had mentioned that the other side of the boundary was (S, 3) – and when I saw that output from the coordinate finder, I recognised it.

When I discussed the same (Y, 7) supertile in a previous section of this article, I also showed that it was one of a pair of tilings differing only in a single path of Spectres. That suggests that the other one of those tilings might also be 6-way singular!

And it is. Here are the two shown together, so you can flip back and forth between them. You can see that the varying path between the two is not separate from the paths that vary under rotation: it’s one of the same paths.

(G, 2) (S, 3)

In fact you can see that the wiggly paths radiating from the centre come in two kinds: more wiggly, and less wiggly. We’ve seen those two different kinds of wiggliness before, in the previous pictures of these tilings. The way I’ve overlaid the two in this diagram, the differing path is one of the less wiggly ones, which means I must have made the (Y, 7) infinite supertile in the second picture occupy the same space as to the (X, 7)(P, 7) in the first. If I had rotated one of those tilings 60° with respect to the other, I could have made (Y, 7) correspond to (P, 7)(X, 7) instead, and then the two tilings would have differed along one of the more wiggly paths. Putting those together, we see that the real difference between these two actual tilings is that the more wiggly paths are rotated 60° relative to the less wiggly ones!

Pieter Mostert also sent data files describing a pair of singular Spectre tilings with 3-way and 2-way near-symmetry, and I ran those through the coordinate finder too. The 3-way one turns out to have coordinates that repeat with period 2, which means you can get another different 3-way instance by cycling those coordinates around a notch. Here are both:

(G, 6)(J, 2) (J, 2)(G, 6)

Here, again, the paths come in ‘more wiggly’ and ‘less wiggly’ forms, and there’s one singular tiling for each kind.

The singular pattern with 2-way near-symmetry wasn’t so clear. The first four parents of the lowest-order hex type were all different – and that’s about the point where the coordinate finder stopped having enough tiles to determine further coordinates. It looked as if repeating that sequence of four parents was the simplest possibility, but I wasn’t very confident that that would be right.

However, Pieter’s alternative representation came to the rescue, because that predicts a cycle of order 4. So, by using both representations together, these seem to be the 2-way singular Spectre patterns:

(G, 5)(P, 2)(F, 1)(D, 6) (D, 6)(G, 5)(P, 2)(F, 1) (F, 1)(D, 6)(G, 5)(P, 2) (P, 2)(F, 1)(D, 6)(G, 5)

What’s going on with the ‘more wiggly’ vs ‘less wiggly’ distinction in these pictures? Certainly there are two more-wiggly and two less-wiggly paths. But for each of those types, the two patterns of that type are still different in other ways. For example, in the two ‘more wiggly’ cases (G, 5)(P, 2)(F, 1)(D, 6) and (F, 1)(D, 6)(G, 5)(P, 2), the path has a mirror-image shape at the centre, curving like an S in the first one and a reversed S in the second.

Singular hat tilings

Of course, now I’ve shown a load of singular tilings for both Penrose tilings and Spectres, hats are next! It turns out that the singular tilings for hats follow very much the same pattern as the ones for Spectres.

I obtained the coordinates for all the singular Spectre tilings in the previous section by applying my coordinate finder to finite tiling patches generated by Pieter Mostert’s entirely different method. But the ones in this section I worked out myself, with (in one case) a minor hint.

Firstly, the six-way singular tilings. The clue I started from here was that in the Spectre system, one of the six-way singular tilings has two adjacent infinite supertiles which are the same shape, because although they have different coordinates in the 9-hex substitution system, both correspond to the same coordinates in the less detailed H₇/H₈ style system. So I was able to investigate the corresponding systems for hats, and found that there’s also a supertile in the H₇/H₈ system which can fit alongside itself with a 60° rotation. Finding the possible 10-hex coordinates of that supertile led me to the following two singular tilings with six-way near-symmetry:

(E, 2) (A, 2)

One difference you can immediately see here is that, where the Spectre singular tilings had two kinds of wiggly varying path with different styles of wiggle, in the hat version only one of the types of path is wiggly at all. The other type follows a perfectly straight line, at a slightly slanting angle. So this tiling has a mixture of the properties of the Penrose tiling (varying paths are all straight) and the Spectre tiling (all wiggly).

Just like the Spectre case, the way in which these two singular tilings differ is that one of the path types is rotated 60° relative to the other one. The way I’ve shown them here, the wiggly paths match up perfectly between the pair, but flipping back and forth changes the state of just one of the straight-line paths.

What would it have looked like if I’d instead rotated the diagrams so that the straight paths match and just one of the wiggly paths change? We’ve seen the answer already: that pair of nearly matching patterns is the one I found in the last article by having the HTPF transducer construction fail. These tilings are the same two as in that picture – I noticed that they were very similar to each other, because the transducer failure pointed that out, but I didn’t notice the fact that each of them was also very similar to itself under a 60° rotation, because both are 6-way singular!

Some more singular hat tilings are easy to find by thinking about the near-symmetries in the HTPF substitution system. The T tile expands to a mostly-symmetric pattern (varying only in the orientation arrows on the tiles) with a H at its centre; the H expands to a similarly mostly-symmetric pattern with an T at its centre. So expanding back and forth between H and T, keeping the expansions centrally symmetric, is bound to generate a mostly three-way symmetric tiling of the plane. The cycle of expansions is shown below: the circled H tile in the middle picture expands to the diagram on the right, and the circled T tile in the final picture is identified with the T we started from, and so on for ever.

Converting that idea back into 10-hex coordinates so that a transducer can generate it, we get the following pair of patterns, with the coordinates being cyclic rotations of each other:

(D, 4)(L, 0) (L, 0)(D, 4)

These two patterns are different from each other, but both of them have their variable tiles arranged into the wiggly kind of path, rather than the straight one – unlike the 3-way singular Spectre tilings, in which the two related coordinate sequences delivered one path of each kind.

(I haven’t found a three-way singular hat tiling with straight paths. That seems odd, because in the Spectre system we had three-way singular patterns for each of the two different kinds of path. Perhaps there’s one I’ve missed?)

Another case that’s easy to see in the HTPF system: the P tile has a mostly 2-way symmetric expansion with another P tile at its centre. So if you repeatedly expand a P keeping central symmetry, you expect to get a mostly 2-way symmetric tiling.

And indeed you do: it has coordinates (G, 6) in the 10-hex system, and it’s shown here, with a wiggly path of variable hats.

At this point I ran out of ideas for ways to find paths. But Pieter Mostert said that his alternative representation of the hat tiling system predicts some further 2-way singular patterns, with straight rather than wiggly paths.

It took me a while to figure those ones out. Eventually I did it by generating a larger patch of one of the 6-way singular tilings above, and looking further out from the origin to find a piece of straight path by itself. Then I zoomed in on that section and looked at the local coordinates of hats in that path until I saw a pattern.

The result turns out to have coordinates which repeat with period 3, which of course means there are three similar patterns with the same property. Here they are:

(M, 1)(D, 1)(A, 0) (A, 0)(M, 1)(D, 1) (D, 1)(A, 0)(M, 1)

A natural question about these three patterns is: if I wasn’t able to find them by thinking about the HTPF system, why not? What is the HTPF representation of these tilings? Did I just miss something obvious, or is it not obvious at all?

To find that out, let’s start by converting this tiling back into its lowest order of HTPF metatiles, and having a look at where the varying path goes. I’ve arranged the radio buttons for this set of images in a cyclic order that lets you flip between each hat tiling and its metatile translation, or between the two metatile tilings, or (if your browser lets you press Left/Right to cycle round the end) between the two hat tilings. But the important part is comparing the two metatile arrangements:

Hats (+) Metatiles (+) Metatiles (−) Hats (−)

No wonder I didn’t find those by any HTPF-related thought process! A whole row of metatiles is changing completely, but the underlying hats change much less, because of multiple correspondences that the metatiles themselves hide:

• the P and F metatiles expand to the same pair of hats connected the same way, so a P can change into an F in this rotation without the hats moving
• the flat end of an F and the ‘tail of the arrow’ corner of an H can similarly change into a whole F rotated 60°
• a T metatile and the ‘left of the arrowhead’ corner of an H can become a P.

In other words, the HTPF system actually obscures some of the ways in which the underlying hats match each other. But at the same time, it makes some of the other ones very clear – I was able to find the previous few tilings more easily than I could have done it for Spectres!

In fact, the HTPF coordinates of these final three singular tilings are obtained by the following cycle, in which an F tile is identified with the F between the two same-orientation H expanded from another H expanded from the pointy end of the original F (phew!):

Stars and propellers

Let’s go back to a thing we found out earlier about the Spectre tiling. The infinite supertiles (Y, 7), (P, 7)(X, 7) and (X, 7)(P, 7) all have exactly the same shape and the same layout of tiles. And because the last two of those supertiles appear in the same overall tiling of the plane, it follows that that shape fits next to another copy of itself, with a 60° rotation.

If you insist on filling the rest of the plane with actual Spectres, then we already know what happens: you get one of the 6-way singular Spectre tilings we’ve already seen above. But if you don’t, then there’s a much simpler thing you can do. Since this shape of infinite supertile fits next to itself with a 60° rotation, it follows that we can simply repeat it six times round the origin, to obtain a tiling of most of the plane with Spectres, with 6-way true symmetry.

Of course, there would be no way to fill in the gap in the middle with Spectres. Not just ‘no way to fill it in symmetrically’: no way to fill it in at all. That follows from the existing theory: without even checking what the shape of the gap turns out to be, we can already be confident that it won’t be tileable with Spectres.

But I thought it would be amusing to generate the pattern anyway. Partly, it would at least be pretty; also, it’s a sort of ‘near miss’ 6-way-symmetric Spectre tiling in a different sense from the singular ones we saw earlier. Those were tilings of the entire plane with Spectres, which were only mostly symmetric; this one is going to be entirely symmetric, but it’ll only be a Spectre tiling of most of the plane. So they’re sort of counterparts of each other.

The tiling looks like this:

Hooray, that is pretty! The pattern as a whole has 6-way rotational symmetry, so we expected the same from the gap at its centre. But it turns out we got even more: that star has 12-way rotational symmetry and is reflection-symmetric. Lovely!

I posted that on Mastodon, during the conversation that followed on from my previous article, and some things happened.

Spectre + star + propeller tiling

Robin Houston wondered if it was possible to get more than one star into the tiling, perhaps making it periodic in the process. He didn’t manage to produce a tiling of just stars and Spectres, but he was able to make a periodic tiling by surrounding each star with the first two rings of Spectres from the picture above, and then using a ‘propeller’ shape – also seen in the wheel tiling – to fill the remaining gaps:

But then Pieter Mostert observed that this tiling is one of an infinite family! You can derive it by extending the mapping rules we’ve previously seen, which give rise to the Spectre H₇/H₈ substitution system. We colour and orient the edges of the star and propeller shapes in the same way that we did for the Spectre tiles themselves: colours depend on whether the edge’s direction is an odd or even multiple of 30°, and orientation alternates around the tile. Then we can apply exactly the same rules as before for mapping the two edge types.

Under the same rules that expand a Spectre into a shape that can be tiled with 9 more Spectres (including a skew one), the propeller shape expands into a shape that can be tiled with 9 ordinary Spectres with another propeller at the centre:

0 1 2 3 4 5 6 7 8 9 10 11 12 Tiled

There’s a subtlety here, though. The Spectres on the right-hand side of this expansion are reflected compared to the ones we saw on the left in the earlier section. So it follows that the propeller must also be reflected – which, since it’s symmetric, turns out to be the same thing as saying that its orientation has changed from an even to an odd multiple of 30°. In other words, there are two propeller shapes we must consider: the one above, and the ‘skew propeller’.

The skew propeller does something completely different when you expand it, for the same reason as the skew Spectre: pairs of green and yellow edges which previously met at a right angle one way round, causing their expansions to meet at the centre of a double-length green edge, now meet at a right angle the other way round, so that their expansions double back to create a spur.

0 1 2 3 4 5 6 7 8 9 10 11 12

The result is that the skew propeller expands to … just a propeller. This time, nothing is confusingly negative: as the input outline goes anticlockwise round the input propeller, the output one also goes anticlockwise round the output propeller. So this isn’t a weird anti-tile that cancels something out: it just means that a skew propeller turns back into a regular one under expansion.

What about the star?

0 1 2 3 4 5 6 7 8 9 10 11 12 13
14 15 16 17 18 19 20 21 22 23 24

The star just expands into an exact copy of itself, if you discount the zero-thickness spurs as usual. So this time we’re not changing anything about its orientation or sense. This shape is simply invariant under expansion.

Putting this all together, we can expand Robin Houston’s original tiling into a larger one. But more than that: we can show that Robin’s tiling is itself the result of an expansion of this type, because you can start from just stars and propellers! Here are the first four tilings you get from this process.

Number of expansions: 0 1 2 3

In each expansion, the type of the propeller reverses. We begin at level 0 with regular propellers nestling between the stars. In the first expansion, generating Robin’s tiling, each regular propeller turns into 9 Spectres around a skew propeller – but all the Spectres are in one of the regular orientations (no skew ones). In the second expansion, the skew propellers turn back into regular ones, generating no additional tiles – but the existing Spectres all expand into multiple tiles, introducing skew Spectres for the first time. And in the final expansion I’ve shown here, both things happen at once – the regular propeller generates more Spectres around it and all the existing Spectres expand into more Spectres.

You can continue this process for ever, obtaining a sequence of periodic tilings with larger and larger fundamental regions, so that the stars and propellers move further apart, and more of the plane is covered in Spectres. My original tiling, with just one star, can be seen as a ‘limit’ of this infinite process: if you keep one star stationary in every expansion, as I’ve shown in the bottom left of the series of pictures above, then every part of the plane changes only finitely many times, and is eventually invariant. Taking the union of all the invariant parts, we get a tiling in which the propellers have all gone off to infinity and vanished completely, and the whole plane is covered in Spectres, except for the one remaining star. And that’s exactly the tiling I started with!

But that’s not the only way to take a limit of this tiling. What if we kept a propeller in the same place, instead of a star? Then all the stars ought to go off to infinity and vanish, and we’ll be left with a plane full of Spectres, except for one propeller at the centre.

There’s a minor hitch that if you expand that way round, nothing in the plane is eventually stationary, because the whole tiling oscillates with period 2 between one pattern centred on a regular propeller, and a completely different one centred on a skew propeller. So instead we have to consider the odd and even iterations separately, and take a limit of each one, obtaining two different limiting tilings:

Regular propeller Skew propeller

You can see that these tilings have all the properties we’d expect. Both have 3-way rotational symmetry, because the propeller itself does, and hence, so does its expansion, and therefore its nth-order expansion for any n. In the tiling around a skew propeller, the first skew Spectres are further away from the centre, because the skew propeller has just been expanded from a regular propeller, which surrounded it with a newly generated shell of 9 regular Spectres; flipping back to the other tiling, the skew propeller turns back into a regular one, and the Spectres nearest to it each expand into a patch containing a skew one.

Perhaps these tilings aren’t that impressive. The original tiling with a central star had more symmetry than you can get out of any pure Spectre tiling (those can only go up to 3-way rotational symmetry, or 6-way near-symmetry in the singular case). But these tilings with a central propeller are only 3-way symmetric, and we’ve already seen that you can do that with pure Spectres, without needing any kind of anomaly at the centre.

But the thing I like about these limiting propeller tilings is that they reject the hierarchical structure of normal Spectre tilings much more profoundly than the star tiling I started with. In that one, the plane (apart from the star) was divided into six regions, each of which was a legitimate infinite-order supertile from a full Spectre tiling. The only way I ‘cheated’ was by putting six of them around a point, which can’t work in a full Spectre tiling of the plane – but within each one, the hierarchical substitution system is still respected, on all scales.

But here, I’m pretty convinced that there is no infinite-order supertile that would also fit into the ordinary Spectre tiling. There are finite-order supertiles of every size, further and further away from the origin; but each oscillation between a regular and skew propeller introduces a fresh ring of Spectres at the centre, which pushes all the other supertiles further away. So the Spectres at the centre aren’t overlapped by any larger-order supertile at all, and therefore, the first ring of nth-order supertiles further out from the origin aren’t overlapped by any (n + 1)th-order supertile. The larger you make n, the larger the central region of this tiling which has no nth-order supertile structure at all.

In my imagination, that propeller is actually spinning, creating a current of Spectres flowing away from the origin in all directions, so that they never have a chance to build up into an infinite supertile!

Doing the same for hats

The same process can be carried through for the hat tiling, by making the hat analogues of the propeller and star outlines, and applying the hat edge mapping rules to find the shapes they expand into.

The outlines themselves are a little bit distorted, because the difference between the Spectre and hat worlds is that in the hat world our yellow edges are longer than the green ones by a factor of √3. So the propeller becomes asymmetric under reflection, and the star will have fewer axes of symmetry than the Spectre version did.

0 1 2 3 4 5 6 7 8 9 10 11 12 Tiled

Just as in the Spectre case, the propeller has expanded into a region that can be tiled with nine hats and another propeller. The hats are all the normal way round – no reflected hats here. But the propeller is the mirror image of the starting one (which is more obvious in this system, where the different edge lengths make it asymmetric, and the expansion process doesn’t introduce an extra reflection to confuse matters).

So next we need to know what the reflected propeller expands to. And, just as in the Spectre case, it turns back into a regular propeller, with no surrounding hats:

0 1 2 3 4 5 6 7 8 9 10 11 12

This is all looking so familiar that we’d be surprised if the star didn’t work exactly the same as before, expanding into an exact copy of itself with spurs sticking out. And indeed that is exactly what it does:

0 1 2 3 4 5 6 7 8 9 10 11 12 13
14 15 16 17 18 19 20 21 22 23 24

(Incidentally, the spurs in this expansion aren’t completely useless. The endpoint of each spur is the image of one of the vertices of the original star. So if you were to place two stars so that they touch at that vertex, then in the expansion, the endpoints of the two corresponding spurs would have to coincide. So the spurs show you how far apart the stars must move in the first level of expansion. The same is true for the Spectre case above.)

Putting all of that together, we can make an infinite series of periodic tilings in exactly the same way as before, starting from pure stars and propellers and expanding repeatedly by the above rules:

Number of expansions: 0 1 2 3

Again, this follows exactly the same pattern as before. We start with just stars and regular propellers; in the first expansion, the propellers turn into reflected ones and introduce only normal-orientation hats; in the second expansion reflected hats appear for the first time, while the propellers reset to the regular orientation; and so on.

What about the limiting tilings? Here are all three.

Regular propeller Reflected propeller Star

What’s the best substitution system?

By now, I’ve collected a lot of different substitution systems for all of these aperiodic tilings.

If you’ve been following this article series from the beginning, since I first thought it would be neat to allow players of Loopy to play it on the hat tiling, I’ve gone through four different substitution systems for hats. I started with overlapping HTPF (which is still what Loopy actually uses for its generation, because now it would break backwards compatibility to change it); moved to the non-overlapping version to try a transducer (unsuccessfully); heard about Bowen Ping and Brad Klee’s 10-hex system which fixed the transducer problem; and now I’ve been talking about the H₇/H₈ system.

Spectres have no HTPF analogue, and the 9-hex system from the Spectre paper worked first time with my transducers, so I’ve mostly stuck with that. But I’ve mentioned the H₇/H₈ style system for those as well in this article.

And I thought I was firmly committed to the triangles view of the Penrose tilings – until I found my new adjacency-recogniser algorithm, which makes the whole-tile substitution systems feasible to use.

I keep changing my mind about which systems are best. Which system is really best, for each tiling?

I think my answer has to be that well-known unsatisfying one: it depends on what you’re trying to achieve.

Taking the Penrose systems first: if you want to actually generate tiling instances in software in a practical way – especially if you want to do it completely at random, and don’t care whether or not you happen to hit any of these mathematically interesting cases with symmetry or singularity or infinite supertile boundaries – then I would now recommend the whole-tile systems, because they require the least code. You can just import one of my transducers (generated by the Sage program linked from the previous article) as a magic state-machine data table, and then all you need is code to transform a coordinate string using that transducer, code to randomly extend the starting string as necessary, and code to place the tiles in the plane. Doing it any other way requires more code: using the whole-tile systems with a recursive algorithm would require backtracking for spurs, and using the triangle system in any way would require a postprocessing stage.

But if you want to understand Penrose tilings and their structure, then I still think the triangles system has the edge over whole Penrose tiles – although, as we’ve seen above, it might also be worth learning about de Bruijn’s pentagrids, since they give an understanding of singularity, which the coordinates system in general doesn’t, even in the triangle system.

(On the other hand, I definitely don’t recommend using pentagrids for practical tiling generation! It is possible – I did it myself to generate the diagrams in the pentagrid section of this article – so if you want to try it for sheer curiosity and learning experience, I wouldn’t stop you. But it’s not very practical. It’s horribly slow, because you need an exact arithmetic package: you’d be overwhelmed by rounding errors if you tried it in fast floating point. Not only that, you might also need to model some kind of infinitesimals if you want to be able to resolve singular pentagrids reliably into tilings. Ugh.)

For Spectres: the 9-hex system is nicely unambiguous, in the sense that it’s possible to build a finite-state transducer, because the nth-order supertile type of a tile’s neighbour can always be determined with a bounded amount of information about the original tile’s supertiles at higher orders. As a corollary, every infinite-order supertile described in the 9-hex system has a unique neighbour, so that even infinitary uses of a transducer never run into an ambiguity: a single input string of coordinates reliably describes a whole plane tiling.

But, again, there are some kinds of understanding that the 9-hex system doesn’t deliver. The simpler H₇/H₈ style system, which is too ambiguous to build a transducer for, was useful to me precisely because the transducer construction failed – the failure pointed me to those pairs of similar Spectre tilings, which (with hindsight, although I didn’t make the leap at the time) could have been a clue to discovering at least one singular Spectre pattern by myself.

In fact, I think (although this is an intuitive handwave without proof) that the H₇/H₈ style system is likely to be maximally ambiguous. Because it’s so closely related to what I described as the ‘true’ substitution that operates directly on individual Spectre tiles, it conveys as little information as possible about what neighbours a tile has, so that the coordinates of a particular infinite supertile reflect only the necessary layout of tiles within that supertile, and not anything about its neighbouring supertiles. So the ‘local plausibility’ idea I mentioned in the previous article is defined as widely as possible: an adjacency recogniser built from H₇/H₈ will consider two coordinates as potentially adjacent if their shapes fit at all. By contrast, the 9-hex system is deliberately including extra information about the wider context of a tile, encoded in the larger set of tile types, and so its notion of local plausibility is narrower – so much so that no ambiguity remains.

This ‘maximal ambiguity’ property makes the H₇/H₈ style system very unhelpful for generating tilings, but again, useful for understanding, because it allows you to directly ask questions like ‘Which infinite-order supertiles fit alongside each other without any gaps?’. There are ways to ask that question by directly analysing the H₇/H₈ adjacency recogniser – and they wouldn’t work in the 9-hex system, which would miss the point entirely, by telling you that every supertile had only one possible neighbour.

(One of the links below goes to a web page where someone has already done some analysis on Spectre supertile shapes.)

And then, once you’ve identified the coordinates of a supertile of interest in the H₇/H₈ system, it becomes useful that that system and 9-hex are very strongly related: you can figure out the full set of 9-hex coordinate sequences that have that supertile shape, and look at them all to see what else fits along that supertile.

So if you really want to understand Spectres, I think it’s useful to know both systems, and play them off against each other.

What about hats? For very similar reasons, I think it can be useful to work with both an H₇/H₈ style system and the 10-hex system. The hat 10-hex system is similar to Spectre 9-hex in that you can match up its hexagons to the hats in a patch expanded from a single hat, so that again, after you’ve identified a thing of interest described in H₇/H₈ terms, you can reliably determine all of its possible 10-hex coordinates.

(One note of warning there. In the previous section where I described hat H₇/H₈, I mentioned that there were two choices of which neighbour you merge the reflected hat with, and both generate viable substitution systems. The 10-hex system I showed in the previous article turns out to be based on the other choice from the version in the hat paper. So if you use the alternative hat H₇/H₈ system for investigations like this, it’ll be easier to match up the results afterwards to 10-hex.)

Where does the HTPF system fit in? I’m not really sure. It was useful to me in the exercise of looking for singular hat tilings – its nice chunky metatiles with simple symmetric shapes made it immediately obvious where to find a 3-way singular pattern (at the centre of the T → H → T expansion cycle) and a 2-way one (P → P). But on the other hand, the other 2-way singular patterns appeared in a place that the HTPF system actively hid. So it’s good for some kinds of understanding but not others. I think I’d say: keep it in your toolbox but be aware that it doesn’t fit all situations.

For practical generation of hat tilings, I recommend the 10-hex system, because you can build a transducer from it. But if you prefer HTPF style systems, then here’s one little contribution of my own: an unambiguous version of HTPF, which my algorithms can build a transducer from. I constructed it by figuring out the correspondence between the HTPF tiles and clusters of 10-hex hexagons: it turned out that there were three different clusters of hexagons that correspond to an F tile, two clusters for an H, and still only one kind of T and one P. So I made this “HHTPFFF” system, which splits those tile types apart from each other, and shows which kind appears where:

(This is a bit of an afterthought, so I’ve shown these diagrams small, and without any of the detailed edge mapping. Everything not shown about this system is the same as the one for the previous non-overlapping HTPF, which I showed in the previous article. This system looks exactly like that one in the details of how the edges match, and how each metatile finally converts into hats. The only difference is that there are two H and three F, and these expansions show which ones appear in which positions.)

In this system, the ambiguous (F, 5) supertile shown in the previous article splits into two: you have to decide whether it’s (F0, 5) or (F1, 5), and whichever you choose, the far side of its boundary is now uniquely determined. So it resolves the previously ambiguous case just as the 10-hex system did, but it looks more like the HTPF system you were already familiar with.

Conclusion

This has been a miscellaneous collection of topics, so there’s not a lot of unifying conclusion I can draw from all of it together. But here’s one theme that has run through a lot of the article.

In the previous article, when I first demonstrated my Spectre transducer working by showing a picture of the (Y, 7) infinite supertile and its (S, 3) neighbour, I said this:

It’s almost a disappointment that it just looks like more of the same kind of Spectre tiling, isn’t it? There’s no obvious symmetry here; no noticeable change of quality between the two sides of the boundary. The boundary itself is the most interesting thing, with its self-similarly crinkly shape – but if I hadn’t drawn it in a thick line, you’d never have been able to pick it out, or even detect that this wasn’t a perfectly ordinary patch of Spectre tiling. There’s nothing special to be seen at all.

After getting to the end of this followup article, my biggest conclusion is: wow, was I wrong there. Wrong, wrong, wrong. Absolutely brimming over with wrongability.

That specific pattern turned out to be one of a ‘minimal pair’ in the Spectre tiling, analogous to the one I was so impressed by in the hat tiling. But I didn’t know it at the time, because I hadn’t found the other pattern it was almost identical to.

It’s also one of the two singular Spectre tilings with 6-way near-symmetry – the highest order that can possibly come up in any singular or truly symmetric Spectre tiling. That makes it (and its counterpart) the Spectre analogues of the Penrose cartwheel pattern – and that’s one of the most famous Penrose tilings in existence. I didn’t spot that either. (Come to think of it, I also didn’t spot the cartwheel pattern itself, when I generated it by chance in the previous article – or the fact that my ambiguous pair of hat tilings were also 6-way singular.)

And, as if that’s not enough, it also contains an infinite supertile capable of fitting alongside another copy of itself, giving rise to the star pattern I showed earlier.

It would be difficult to find a single other Spectre tiling with more interesting things about it than this one and its twin. And I called it boring! I apologise wholeheartedly to (Y, 7).

Software

I linked to my Sage implementation of these algorithms from the previous article, but for convenience, here it is again. I’ve updated it for the new improved features discussed here.

You can clone the git repository with this command:

git clone https://git.tartarus.org/simon/tilings.git

Or you can browse the repository on the web.

Acknowledgements and references

Pieter Mostert told me about the singular Spectre tilings, and generated enough information to identify their coordinates, via his cut-and-project system. At the time of me writing this, he didn’t have a full writeup of his system, but I’ll come back here and add a link if I hear of one in future. But here’s a link to the Mastodon thread where we discussed it.

Robin Houston had the idea of finding the initial Spectre-star-propeller tiling, starting from my simpler tiling with Spectres and just one star. Here’s a link to the separate Mastodon thread where that happened.

I’m further indebted to Pieter Mostert for (indirectly) describing the edge mappings for the two H₇/H₈ substitution systems. It was also his idea to apply them to the stars and propellers, generating the larger family of star+propeller tilings shown in this article.

I’ve been using some idiosyncratic terminology in this series of articles, because I’ve been working out for myself a lot of stuff that was already known in the mathematical literature under different names. So I should acknowledge some of the standard terms:

• When I’ve cut Penrose kites, darts and rhombs into two triangular halves to make the substitution systems easier, it turns out the usual name for these is Robinson triangles.
• The idea I’ve been calling ‘combinatorial coordinates’, representing a tile’s position within an infinite substitution system, is called an address in some works, such as Chaim Goodman-Strauss’s paper that I linked to in the previous article. But it’s also known as a Conway signature in other work, such as Maurizio Paolini’s web page that I link to below.
• When I turn one tiling into a finer one by mapping each input tile to multiple output tiles, I’ve been calling that ‘expansion’, by analogy with macro expansion in software. In the literature this is known as deflation, and its inverse (passing from a tiling to its supertiles) is therefore inflation. (It’s awkward that we’ve chosen opposite operations to correspond to the word that means ‘making something bigger’! I suppose both are natural in their way; inflation makes the tiles bigger, while deflation – my ‘expansion’ – makes any finite patch of tiling bigger, in the sense of containing more tiles.)
• The term Conway worm is used in various places for those individual paths of tiles that can be flipped into a different state without affecting the rest of a plane tiling. I’ve tried not to use that term in this article, because I was worried about using it wrongly: I haven’t found a formal definition, so I don’t know whether it applies to any such path, or specifically the ones that arise from the ‘singularity’ phenomenon.

Some references to papers and other web pages:

Nicolas de Bruijn, “Algebraic theory of Penrose's non-periodic tilings of the plane”, 1981. In two parts: [Part I] [Part II]

I recommend this whole paper – there’s more in it than the pentagrids I’ve shown here and the missing proofs. Also discusses lifting P3 tilings out of the plane into a ‘Wieringa roof’ with only one kind of rhombus tilted at different angles, and generation of P3 tilings by taking a slice through a five-dimensional cubic lattice.

Maurizio Paolini’s web page “Spectre tilings with given Conway signatures”

Catalogues infinite supertiles in the Spectre H₇/H₈-style substitution system, listing which ones fit alongside which other ones to cover the plane.

Arnaud Chéritat’s web page “4D lift of the tilings by the Smith et al. aperiodic monotile”

Describes the 4-dimensional coordinate system I mentioned in connection with direct inflation and deflation on the hat and Spectre tiles, and goes much further, discussing projections into particular subspaces of that 4-dimensional space.

Joshua Socolar, “Quasicrystalline structure of the Smith monotile tilings”

I said in my previous article that I probably wasn’t the first to find that pair of hat tilings differing only in a single path. Indeed I wasn’t: this paper found it in May 2023. Figure 18 is the same tiling as the one I described. Also, Figure 16 shows the rotated version I showed in this article, with a straight rather than wiggly path.

The references section in the previous article might also be useful.