Aperiodic Tilings V: the Refinable Frontier

[Simon Tatham, 2025-09-02]

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

• Introduction
  • Recap
• Ambiguous substitution systems
  • Refining the set of tile types
• Making refined substitution systems from scratch
  • Clues to the secret
  • Neighbourhood-based refinement
  • Reducing the set of subtypes
• Trying it out on real aperiodic tilings
  • The auto-refiner rediscovers HHTPFFF from first principles
  • It figures out the Spectre 9-hex system too
  • And now look what happens with hats!
• Difficult cases
  • The ‘Awkward Squares’ substitution system
  • Extendable list of queries
  • Sometimes you have to refine more than once!
  • The test case that wasn’t a test case
• Conclusion

Introduction

(I know, I know. I’m running out of title ideas.)

This is article #5 in my series about generating aperiodic tilings using string-processing techniques. Every time, there’s more to recap from the previous ones. So I’m just going to start with the introduction to this article, and fill in the recap in a moment.

In the previous two articles I’ve talked about using a finite-state transducer to move around a tiling, tracking your current position as a string of combinatorial coordinates, and using the transducer to update the coordinate string as you step from each tile to the next. These transducers are ideally deterministic, generating a unique output coordinate string given any legal input. But not every substitution system admits a deterministic transducer: different systems describing the same actual tiling may or may not unambiguously identify the neighbouring coordinates of every tile in every situation.

What do you do if your substitution system doesn’t work with this technique? In the past, I’ve had to depend on luck. Some systems I wanted to use happened to work already; in cases where the system I started with didn’t work, someone else found an alternative system that did (though I think that was luck too, and this wasn’t the property they were specifically after).

In this article I’m going to talk about a technique for solving the problem without needing to depend on luck: if you have an ambiguous substitution system, you can construct a variation of it which is unambiguous, and make a transducer out of that instead.

Recap

I just said that there’s more to recap every time from previous articles. But it’s not quite true, because some of those articles contained ideas that I’ve now decided are superseded by better thoughts I had later. If you were to go back and re-read the whole lot, there would be entire sections I’d recommend skipping. So here I’ll try to summarise the useful parts.

This whole project has focused on tilings of the plane generated by substitution systems. A substitution system is a set of rules that allow you to turn each tile of tiling A into a cluster of tiles in tiling B, in a consistent way (each type of tile is transformed into the same cluster every time), and also specifies how those clusters fit next to each other when they’re expanded from neighbouring tiles. (Examples from previous articles: Penrose, Spectre, hats, hats done differently.)

So in principle – in the ideal world of mathematics where infinite processes can be imagined – you can take an entire infinite tiling of the plane, and apply these substitution rules to make a different complete tiling derived from the first one. I’ve been calling this ‘expansion’; mathematicians often say ‘deflation’.

More practically, you can take just one tile, and expand it repeatedly via the substitution system to turn it into a large patch of your tiling. This is a common technique for actually generating patches of (say) Penrose tilings in software.

But this series of articles has been about a better approach. If you have a tiling that was (or could have been) generated by iterating a substitution system – and with the famous aperiodic tilings like Penrose and hats, every tiling of the plane has this property – you can describe the combinatorial position of a tile in terms of the substitution system, by describing its position in the hierarchy of expansions. First say what type the tile T₀ itself is; then say how it was generated from its supertile T₁, by giving the type of T₁ and also saying which tile is T₀ in the cluster of multiple tiles expanded from T₁. Then describe how T₁ was generated from its parent T₂ in turn, via another (tile type, subtile index) pair, and so on.

Once you have a string of ‘combinatorial coordinates’ describing a tile T, it turns out that you can calculate the coordinates of a neighbouring tile U by several algorithms I’ve described in previous articles, all of which operate only on the string of coordinates, without having to think about geometry at all. So you can generate a patch of tiling that occupies a given region of the plane by generating each tile on demand as you find you need it, which is much more efficient than generating a much larger piece of tiling and then throwing most of its tiles away.

The first of these algorithms is recursive: ascend the hierarchy until you find a single supertile whose expansion contains both T and U, so that the coordinates of T and U are identical from that point onwards; then unwind the algorithm’s stack, generating the new set of low-order coordinates that describe U. The low-order part of this procedure’s output tells you which type of tile U actually is, and which edge of T is adjacent to which edge of U, so you know what tile to draw where in your output diagram. Then the rest of the output coordinate string contains enough information to run the algorithm again to step to U’s neighbour in turn, and so on.

You can use that recursive algorithm directly in simple cases, but I prefer a more sophisticated technique based on finite state machines, which requires more setup but is faster and simpler at run time, and can also handle special cases in which the recursion would never terminate. The first step of that is to use data obtained from the recursive algorithm to build a thing I call an ‘adjacency recogniser’. That’s a finite state machine which takes the coordinates of two tiles T and U, as if combined by Python zip(), and accepts or rejects depending on whether the two coordinate strings describe neighbouring tiles.

You can also imagine the adjacency recogniser as a state machine which takes T alone as input, by reinterpreting the input U as output. But this state machine is nondeterministic: there isn’t a unique output for all possible inputs. So next you try to transform it into a deterministic finite-state transducer, and see if that works.

A deterministic transducer, if you can build one, is my current gold standard for the best way to generate patches of tiling. It’s fast, simple (once you’ve built it), never needs to backtrack, and can cross ‘infinite-order supertile’ boundaries – a phenomenon that comes up in special cases of these tilings, where no finitely large supertile contains any two tiles on opposite sides of the boundary. The recursive algorithm can’t handle a case like that at all, but a deterministic transducer can bypass one of those boundaries effortlessly, and find the unique infinite-order supertile that fits to the far side in such a way that every patch of tiling along the border is consistent with how the tiles normally fit together.

But for some systems you can’t build a deterministic transducer, because not every infinite-order supertile boundary has a unique neighbour: there exists some infinite string of coordinates which describes only part of the plane, and multiple options for what goes on the other side. I call a substitution system of this kind ambiguous.

Ambiguous substitution systems

In previous articles, I’ve shown two cases of this kind of ambiguity. One occurred in the original HTPF system of metatiles for the hat tiling; the other was in the minimalist H₇ / H₈ substitution system for the Spectre tiling. In each case, there’s an infinite-order supertile boundary (shown as a thick line in the diagrams), with one side of the boundary fixed, and multiple possibilities for the other side.

To refresh your memory, here’s the hat example again:

(F, 5) and (H, 7) supertiles (F, 5) and (H, 8) supertiles

Refining the set of tile types

What do you do if you want to use a deterministic transducer on one of those tilings? In both cases, my previous articles provide an answer: you can switch to a substitution system very like the previous one, but with additional types of tile. I’m going to call this a refinement of the previous system.

In the HTPF case, I presented a substitution system of my own, which I called “HHTPFFF”. It looks just like the non-overlapping version of the standard HTPF system, except that the H tile type has been cloned into two subtypes H0 and H1, and the F tile has been cloned into three, F0, F1 and F2. (And the difficult part, which is mostly what I’m going to end up discussing in this article, is deciding which version of H and F should appear in which expansion diagrams.)

If you’re using this system, then what happens to the HTPF coordinate sequence that led to the ambiguity? The sequence in question was (F,5) repeated endlessly: that is, an F metatile which is child #5 of a larger F in turn, and so on forever. But in the more detailed HHTPFFF system, now you have to say which kind of F metatile you mean: you can either have an F0 which is child #5 of another F0 forever, or an F1 which is child #5 of another F1. (There’s no third option involving type F2, because child #5 of F2 is an F1, not another F2.)

And whichever of those options you pick, the HHTPFFF system only allows one possibility for the coordinates of the tile on the far side of the boundary. So we’ve removed the ambiguity, by forcing the user to specify which version of (F,5) they meant.

(F1, 5) and (H0, 7) supertiles (F0, 5) and (H1, 8) supertiles

(Of course, this doesn’t mean that only one set of tiles fits physically to the far side of the boundary. The infinite supertiles (F0,5) and (F1,5) occupy exactly the same shape of region in the plane, so each one fits perfectly to the other one’s official neighbouring supertile. But if you fit one to the wrong neighbour, the tile types aren’t consistent across the border: pairs of adjacent tiles occur which are never seen in any finitely large patch expanded from a single metatile. Transducers insist on maintaining that type of consistency.)

In the case of the Spectre H₇ / H₈ system, I didn’t even have to make up a substitution system of my own. The discoverers of the Spectre tiling had long since done it for me: the system of 9 hexagonal metatiles in the original Spectre paper essentially is a refinement of the H₇ / H₈ system. And it’s already unambiguous in this sense, so it allows a transducer to be constructed.

Making refined substitution systems from scratch

When I wrote the previous articles, I didn’t know how to construct an unambiguous refinement of an ambiguous substitution system.

That seems like an odd thing to say, given that I just said I had constructed one myself – the HHTPFFF system. But I didn’t do it from scratch: I had help. Bowen Ping and Brad Klee had already discovered a completely different unambiguous system for hats involving 10 types of hexagonal metatile. I derived the HHTPFFF system by looking at the correspondence between HTPF and those 10 hexagon types, and spotting that the H metatile in one system didn’t always correspond to the same group of hexagons in the other – there were two different clusters of hexagons occupying the space of an H metatile, and three different clusters corresponding to an F.

In other words, I made an unambiguous HTPF-like system by combining the original HTPF system with another system that was already unambiguous. I didn’t create the lack of ambiguity: I just copied it from one place to another.

In fact, I had previously tried to make an HHTPFFF-type system from scratch by hand, when I first discovered HTPF’s ambiguity. I was attempting exactly this kind of thing: split each tile into multiple types and somehow figure out which ones have to appear where in which expansion diagrams. I didn’t manage to solve the problem by hand. In fact, I eventually began to suspect it wasn’t possible, and gave up trying.

But it was possible, as it turned out. I just hadn’t found it by manually searching the large space of possible refinements, and I didn’t know of any principled approach to finding it without having to search a large space.

Well, now I do know! In fact, better than that: I’ve automated the process. I’ve found an algorithm, and implemented it in software, which can make an unambiguous version of a substitution system, given an ambiguous one as input.

At least, it’s worked on every ambiguous system I’ve tried so far, including an extra-awkward one I made up myself.

Clues to the secret

I’ll start by describing the clues that gave me the idea I ended up with.

After I published the previous article including a specification of the HHTPFFF tiling, I had a response on Mastodon from mathBlock, who had been studying a different property of the HTPF tiles, which they called “drainage” – if I haven’t totally misunderstood, it was about interpreting the tile outlines as contour lines and imagining how rivers of water would run down them. mathBlock had found that the HTPF metatile system didn’t provide quite enough information to determine the drainage: P metatiles always behaved in a consistent way, but F metatiles could do more than one thing, depending on where they appeared in the tiling. It turned out that my division of the F metatiles into F0, F1 and F2 seemed to match up to the different drainage behaviours.

I must admit that I never quite fully understood what the idea of drainage was useful for. But I know that what it was had to do with the neighbourhood of the tiles. What distinguishes the F0, F1 and F2 metatiles is: after you expand each one into two hats, look at two particular convex vertices of the resulting shape. Each one either meets two convex vertices of other hats, or meets a concave vertex of a single hat. Depending on which of those vertices do which, the metatile is either F0, F1 or F2. Similarly, a single vertex on the edge of the expansion of the H metatile into hats distinguishes H0 from H1.

In fact, it turns out that in each case there’s only one way that the neighbouring hat or hats around that vertex can be oriented. For example, here are the three subtypes of F, with the neighbouring hats around those vertices shown:

F0 F1 F2

We can check those diagrams against the ambiguous pair of (F,5) tilings I showed earlier. Here are those ambiguous tilings again, this time zoomed in to show the two hats expanded from the ‘central’ F metatile (the one which is child #5 of another F all the way up), with the two critical vertices marked as shown in the diagrams above:

(F1, 5) and (H0, 7) supertiles (F0, 5) and (H1, 8) supertiles

You can see that the hats on the other side of the boundary meet this F metatile in a way that’s consistent with the diagrams here. When the F metatile is an F1, the marked vertex of its hat #0 meets a concave corner of a hat (as it happens, labelled H0.0); when it’s F0, the same vertex meets convex corners of two hats (P.1 and H1.2). Meanwhile, the marked vertex of hat #1 meets convex corners of two hats in both cases, as we’d also expect from the previous diagrams (it would only meet a concave corner in the F2 subtype). So this even shows us how specifying the subtype of F tile has disambiguated the far side of the boundary: of the two possibilities, each is only consistent with one of F0 and F1.

So this was my first clue that in one of these refined tilings, the subtype of a tile is related in some way to what its neighbouring tiles are.

What about the Spectre 9-hex system, which is pretty much a disambiguating refinement of the H₇ / H₈ system?

The same is true there. In fact, the original Spectre paper says outright that the 9 hexagon types were derived by looking at the neighbourhood of each tile in the overall tiling.

And this also makes perfect sense from first principles. What problem were we originally trying to solve? The existence of a tile coordinate with more than one possible neighbour. How might you solve that? By making two (or more) copies of the tile and simply ruling that each one is only allowed to have a certain kind of neighbour. The F0 tile is the one which can be next to an H tile this way round, and not that way round; the F1 tile, vice versa.

That sounds like a pretty short thought process, now that I write it down. But initially these thoughts were very vague. (Not to mention that I’d forgotten that detail from the Spectre paper, and had to go and read it again before I noticed it!) I turned them over in my head for months before becoming gradually more confident that this was an idea that would work. Then I had to get from the general idea of ‘look at the neighbourhoods of the tiles’ to a concrete plan for how to determine those neighbourhoods and exactly what to do about them. And even then I didn’t get round to trying it, until I heard of another ambiguous substitution system that I wanted to try it on.

Neighbourhood-based refinement

The idea I settled on, as a technique for automated tiling refinement, was to make subtypes of each tile based on its whole neighbourhood. For each tile type in your original system, make a lot of clones of it, one for each possible pattern of all of its neighbouring tiles. Initially, by ‘neighbouring tiles’, I mean: for each edge of the tile, what type of tile is on the other side of that edge, and in what orientation?

As a worked example, I’m going to use a substitution system I haven’t shown in these articles before, because it’s usually too simple to be interesting, but here it’s just the right size to not be overwhelming. It’s the “chair” substitution system from Chaim Goodman-Strauss’s 1999 paper “Aperiodic hierarchical tilings”. The chair system has just one type of tile, and a single substitution rule that tiles a chair with four half-sized chairs:

(The chair tile isn’t an aperiodic tile, in the way that hats or Spectres are. It can tile the plane non-periodically, but it doesn’t force non-periodicity: there are also periodic tilings using the same tile type. But the particular tilings generated by this substitution system are hierarchical rather than periodic.)

So our first task is to analyse this substitution system to find every possible way that a chair tile can be surrounded by other tiles, and make a different subtype of the chair tile for each pattern. In this case, it turns out that there are seven different patterns, shown here:

To be clear, those aren’t all of the possible patterns of chair tiles that can possibly surround another chair. They’re not even all the possible patterns that can arise in the context of a tiling of the whole plane. But they’re all the patterns that can arise in a tiling generated by iterating this substitution – they were found by analysing the substitution system itself, and only considering possibilities that that system can generate.

The above analysis tells us what subtypes need to exist. But in order to completely specify the refined system, we must also look at the expansion of each tile into smaller tiles, and for each smaller tile, specify which clone of the original type it is.

To do that, we look at the original tile, and whatever neighbours a particular subtype assigns it; expand all of those into their subtiles via the original substitution system; and then, typically, that’s enough information to find all the neighbours of the subtiles we need to know.

For example, let’s take the above diagram for chair type 1 and its neighbours; expand all the tiles in the diagram into subtiles; and then we can determine the type of each of the central chair’s subtiles, based on its neighbours.

Supertiles Subtiles Bottom left Bottom right Top right Middle

If we do that for the other six tile types too, we end up with this complete 7-tile substitution system:

And if we feed this refined version of the chair tiling to my transducer-building code, it works! The original chair tiling didn’t admit a transducer, but the refined one does.

Why didn’t the original tiling admit a transducer? Because there exists at least one infinite supertile boundary where it’s ambiguous what’s on the far side. Here’s one: expand a chair into four chairs, at every stage keeping the bottom right corner fixed, so that you occupy one quadrant of the plane.

0 1 2 3 4 5

In the refined system, in order to describe that infinite supertile in the first place, you have to choose which subtype of chair you’re talking about at every level. Chair types 3 and 7 are the only two types that ever appear in the bottom right of another chair, and each of those has a bottom right subtile of the same type as itself. So you have the choice of a type-3 chair with type-3 supertiles forever, or a type-7 one with type-7 supertiles.

Either way, the ambiguity is removed, because each of those tile types embodies a strong opinion about what must appear to its bottom right. In the neighbourhood diagrams above, you can see that the type-3 chair tile appears ‘back to back’ with two other chairs, adjacent to each along a whole long edge. But the type-7 tile nestles in the concave corner of another chair. And in the diagrams below, if you look at the tile at the bottom right corner of the top-left quadrant, you can see that the same is true: when it’s type 3, there are two more type 3s back-to-back with it on the far side of the supertile boundary, but when it’s type 7, there’s a type 4 cuddling its corner.

Type 3 Type 7

Similarly to previous cases (Spectre, hat 10-hex), we can see that the far side of the boundary doesn’t have the same infinite supertile structure in both cases. In the type 3 version of the picture, four identical supertiles meet back to back in a 4-way symmetric tiling of the plane; in the type 7 version, the supertile we started with occupies one quadrant of the plane, and a single neighbour supertile occupies the other three quadrants. (That other supertile is constructed in a very similar way to the first one, except that we keep the concave vertex of the chair fixed at every stage instead of the bottom right vertex.)

Also similarly to previous cases, we see that most of the variable side of the boundary doesn’t actually vary! Almost all the chair tiles are the same in both diagrams, with the only changed ones being along a small number of narrow paths – in this case, three of the four diagonals out from the centre of the tiling (excluding the one in the top left, which belongs to the fixed supertile we started with).

That diagram is my excuse for this article’s terrible pun title, incidentally. We had a substitution system we couldn’t make a transducer for, meaning we couldn’t find out what was on the other side of that infinite supertile boundary; then we applied our shiny new algorithm to refine the tiling, and that enabled us to build a transducer and use it to cross the barrier. Perhaps more specifically, it became possible to cross the barrier once we’d distinguished which of two very similar barriers it actually was. So it was a refinable frontier, so there.

Reducing the set of subtypes

That’s proved the concept, at least. This refinement technique seems to work: it produces a version of the original tiling which allows a deterministic transducer to be constructed, even if the original tiling didn’t. (I have no proof that it works in all possible cases, but at this stage it’s worked in one, and that’s one more than I previously knew how to do!)

But you end up with a lot of tile subtypes. The reason I used the chair tiling as my example in the previous section is that anything bigger wouldn’t have fitted. The results of running this algorithm on the HTPF system delivers a set of 21 tile types in total: 7 kinds of H, 5 kinds of P and 8 kinds of F (but still only one kind of T). And we know that’s more than we need, because I’d already found the HHTPFFF system, with only one kind of P, and two H and three F!

Looking at the output, one thing I immediately noticed was that some of the output tile types had exactly the same expansion as each other. For example, in the chair tiling shown above, chair types 1, 2 and 3 all expand to exactly the same pattern, and so do types 5, 6 and 7.

So that led to the idea: what if we postprocess the refined system by merging tile types that have identical expansions?

This shouldn’t destroy ambiguity, because the aim is to distinguish what happens at the lowest level, in the final output tiling, and higher-order supertiles are only interesting in what they eventually expand to. (A handwave rather than a proof, but enough to make it look worth a try.)

Of course, merging some tile types might make further expansion diagrams identical, if they only differed in subtile types which we just merged into one. So we iterate the merging process if necessary, until we reach a fixed point.

For example, after re-merging those sets of identical subtypes in the chair tiling, the 7 subtypes of chair tile are reduced to only 3:

The reduced set of tile types no longer encapsulate all the information about each tile’s neighbourhood. But they still contain just enough of it to make a transducer work. To prove it, here are the same two tilings as above, regenerated using the reduced system:

Type 1 Type 2

(I have to admit that the rainbow versions of these pictures in the previous section were prettier! But the system with fewer tile types is more practical.)

You might wonder: what do these reduced types mean? We had a clear idea what the original seven chair subtypes meant: each one went with a specific diagram of how the chairs around it were arranged. But now that we’ve merged some of those subtypes into one, what information does a merged subtype convey, apart from ‘the tiles around it can be in one of [this potentially long list of patterns]’?

I think the answer is that a reduced tile type still tells you something about the neighbourhood of the original tile – but it doesn’t tell you everything about what tiles of the same size surround it. Instead, we’ve narrowed down to only saying something about the surrounding smaller tiles, at the next expansion level down. You can see an example of this in an earlier section, where I showed the three subtypes of F in the HHTPFFF tiling: choosing one of those three subtypes doesn’t nail down exactly what metatiles surround the F, but it does tell you something about which hats surround it. And not even on all sides: only at a small number of positions where the answers are crucial to telling the difference between something important.

Trying it out on real aperiodic tilings

This is all very well, and has given us a pretty picture or two, but the chair tiling isn’t all that interesting, because it’s not a real aperiodic tile: there are plenty of other ways to tile the plane with chairs which aren’t derived from the substitution system above, and many of those are periodic. In that respect it’s unlike Penrose tilings, or hats, or Spectres, which all have the property that the only ways you can tile the plane with those tiles are derived from their substitution systems. So those are the interesting ones to study.

So, now we’ve got a refinement algorithm that works on a small toy example of an ambiguous substitution system, how does it do when run on the cases we actually care about?

Answer: it does brilliantly!

The auto-refiner rediscovers HHTPFFF from first principles

As I mentioned above, when I ran the first stage of this refinement algorithm on the HTPF system of hat metatiles, it divided each metatile type into many more subtypes than necessary (apart from T, which remained unique). We got seven kinds of H, five P, and eight F, making 21 types of metatile in total.

But when I ran the postprocessing reduction pass, most of those subtypes ended up merging with each other again. Guess how many we ended up with?

We ended up with exactly seven tile types: the single T, two H, three F, and back down to a single P.

And that’s exactly the same set of tile types as in the HHTPFFF system I’d already found without this refinement algorithm. This automated analysis can do in a fraction of a second what I spent weeks failing to do in 2023: starting from only the HTPF system itself, it’s able to construct an unambiguous, transducer-capable refinement of it, without needing any input from someone who had already discovered an unambiguous substitution system of any other kind. Moreover, it finds exactly the same one: no pointless extra tile types. (On either side.)

It figures out the Spectre 9-hex system too

I’ve already mentioned a second ambiguous substitution system: the H₇ / H₈ substitution system for the Spectre tiling. In the previous article I used the ambiguity to zero in on one of the particularly interesting instances of the Spectre tiling.

To recap the H₇ / H₈ substitution system: it contains just two types of metatile. One is just a single Spectre; the other is the ‘Mystic’, two Spectres oriented at a 30° angle to each other and glued together into a double-sized tile. The expansion diagrams look like this:

A warning: these expansion diagrams are more complicated than they look, because – to put it mildly – it’s not obvious at all how the edges of the single Spectre or Mystic match up to the crinkly edges of the expansion. As well as the exterior spurs shown, there’s also an interior spur in the Mystic expansion, and even a section of boundary which is traversed three times, twice in one direction and once in the opposite direction in between. All of that detail is very difficult to show in a single diagram: if I labelled all the edges and sub-edges, as I did for the HTPF system in a previous article, the numbers would all overlap each other and it would still look horribly confusing. If you want to understand how the edges match up, my best suggestion is to go back to the diagrams in my previous article, where I showed the outline of each of these expansions being built up one edge at a time.

My first attempt to write the auto-refiner algorithm couldn’t handle this system at all, because when it was trying to find all the neighbour patterns it got stuck on even simple spurs – and this tiling has the worst spurs of all. Indeed, I wrote in an early commit message that this system (and its hat analogue) would be “the boss level” of the concept. But then I found a better way to do the analysis which doesn’t care about spurs, so I beat the boss fight in the end!

So my current refiner code runs quite happily, given this substitution system as input. It splits the plain Spectre metatile into eight versions, and leaves the Mystic unique, for a total of nine tile types. And it turns out that those nine tile types correspond exactly to the nine hexagon types described in the Spectre paper. I’ve shown the refined system here with my own Latin-alphabet labels for the tile types (and the original Greek ones too in the large tile pictures, in case that’s useful). And I’ve used the same colour scheme as I used in my Spectre article in 2023. So you can go back to that older article and easily check that all the expansion maps agree, if you want.

In other words, this automated algorithm has rediscovered exactly the Spectre 9-hex substitution system shown in the paper – except that it hasn’t bothered simplifying the tile shapes into hexagons. That wasn’t in its brief. The refiner’s job is to leave the tile shapes unchanged, and do nothing except make more versions of each tile type.

It doesn’t matter very much, either way. By the time you’ve built a transducer out of this system, the distinction between hexagonal metatiles and ones shaped like Spectres and Mystics has more or less vanished anyway. The lowest-level tiles (the actual Spectres) are the same in both systems, and the transducer has encapsulated all the combinatorial information about the metatiles, and didn’t care about their geometry in the first place. The two transducers are interchangeable – you can feed the same coordinate string to either, and it will give the same answers.

And now look what happens with hats!

Perhaps the most exciting result of this project was what happened when I ran the same refiner on the H₇ / H₈ substitution system for the hat tiling.

That system is very similar to the Spectre one, in that it has two types of metatile, one of which is a single ordinary hat, and the other is a fusion of two, including the unusual reflected one. As with the Spectre case above, I’ve left the details of which edge is which out of this diagram (and for the same reason – it’s horribly confusing), but my previous article has the missing detail in full.

In the previous two cases, when I ran my automated refiner, the output had been exactly identical to an unambiguous substitution system I already knew about. Here, I did already know of an unambiguous system that corresponds closely to the H₇ / H₈ system for hats: Bowen Ping and Brad Klee’s system of 10 hexagonal metatiles. So I was expecting that my refiner would most likely recreate that from first principles, in the same way that it recreated both HHTPFFF and Spectre 9-hex.

But it surprised me, by doing better! The output of my refiner, run on Hat H₇ / H₈, is a system of only eight tile types in total – the unique double-hat metatile and 7 subtypes of the single hat.

Is this a mistake, and the refined system doesn’t admit a transducer? Of course that was the first thing I checked, but no, the transducer construction works fine.

So, how has my just-written algorithm managed to beat Ping and Klee’s system of ten tile types?

An obvious way to answer that question would be to match up the tile types in this system against the ones in the 10-hex diagrams. Unfortunately, they don’t quite match correctly, because as I mentioned in the previous article, there are actually two ways you can set up the H₇ / H₈ system for hats, depending on which neighbour you fuse the reflected hat with – and my presentation of Ping and Klee’s 10-hex system, unfortunately, happened to pick the other one from the one in the hats paper, before I realised there was a right way to make that decision.

(Ping and Klee’s own presentation of their system was even stranger: it sawed the reflected hat in two, and assigned half of it to each of the neighbouring tiles! So this poor choice was mine, and not theirs.)

Running the refiner again on the other version of H₇ / H₈ also generates 8 tile types rather than 10, and this time, it is possible to match them up one by one to the 10-hex system and see what happened. It turns out that the refiner has merged the B and C hex types into a single “BC” tile, and similarly, merged the G and J hexes into one “GJ”.

If you go back and look in detail at the 10-hex diagrams, it is true that the B and C hexes expand to the same pattern of other hexagons. But the edges match up differently: the B hex has a spur sticking out of its expansion, and the details of how the edges of the original hexagon map to the crinkly edge of the expansion are quite different from each other. Similarly, G and J expand to the same pattern of hexagons but with different edge mappings. In the final mapping to hats, the B and C hexagons don’t work the same as each other either, and neither do G and J.

But in the H₇ / H₈, there are only two edge types in the whole system, corresponding to the long and short edges of hats. So in that system, the B and C tile types are completely identical, because the difference in edge types isn’t there. They’re just two tiles of the same shape with the same expansion. And similarly for G and J.

So it looks, to me, as if the reason my refiner managed to get away with fewer tile types is actually because it left the tile shapes as hats (and the fused double-hat), and didn’t try to simplify them to hexagons with lots of different edge types. It seems to me that that simplification to hexagons creates extra complication!

By some measure, this is now the most economical substitution system for hats that I know of, among those which admit an unambiguous transducer at all. It uses only 8 metatile types, compared to Ping and Klee’s 10. The HHTPFFF system gets away with one fewer – only 7 in total – but its metatiles are larger, with most of them expanding to 2 hats, and the two H metatiles expanding to 4. If you measure the system’s overall complexity by “total number of hats in the expansion of all lowest-order metatiles” – a metric that I only just made up but which seems to account for both types of complexity reasonably well – then this system is now the winner, at 9 hats total, to 11 for Ping and Klee’s hexagons or 17 for HHTPFFF.

Just to demonstrate this 8-tile system in action, here are the two 6-way singular hat tilings from the previous article, regenerated using a transducer made from it. (They’re also the same pair of hat tilings shown in the example at the top of this article, although there, I was focusing on the ambiguity for transducer purposes, rather than the six-way near-symmetry.) In terms of the new tiling system, one of these contains a type-2 hat tile which is the subtile of another type-2 hat forever, and the other contains a type-3 hat similarly. (In both cases, the subtile’s position within the supertile’s expansion is always the bottom right hat in the diagrams above.)

Type 2 Type 3

Difficult cases

I left a loose end somewhere back up there. My refinement algorithm starts by splitting each tile into subtypes depending on its neighbourhood, and I said that “initially” the neighbourhood would be defined as the tile on the other side of each edge (including which way round it is).

The main property we need from the concept of a “neighbourhood” is: given the neighbourhood of a supertile, we need to be able to determine the neighbourhoods of all its subtiles. For example, in the example above, I showed how you do this for a particular subtype of chair tile: draw in all the nearby large tiles according to the supertile’s type, and since all the smaller tiles bordering on each subtile are contained within those larger tiles, that’s enough information to know the type of every smaller tile.

But I wasn’t completely confident that that would be enough information in every case. It worked fine for all the tilings I’ve discussed above, but I could see a way it might not work, in principle.

Again it has to do with those awkward zero-thickness spurs that sometimes poke out of tile expansions. What if a tile X has its neighbour on a particular edge being tile Y, but when both are expanded into subtiles, the part of Y’s expansion bordering X turns out to be nothing but a zero-thickness spur? Then, if you were trying to ask our recursive coordinate transition algorithm what was on the other side of a particular edge of a subtile of X, it might find the spur, and then have to recurse back out of the other side of it to find out what the next large tile was. And that might not be one of X’s immediate edge-to-edge neighbours at all.

This hasn’t come up yet in any ‘real’ aperiodic tile system. Any spur creates a situation where it nearly happens. But usually, the tile whose spur is adjacent to some edge of X also has some nonzero-thickness part of its expansion adjacent to another part of X’s edge, which means that in spite of the spur you do still have enough information to find out everything you need.

But I couldn’t rule out this happening in some other more difficult tiling in future – and I wanted my algorithm to have an answer when it did. So I invented a substitution system designed deliberately to have this annoying property, and then used it as a test case to make sure my code could cope.

The ‘Awkward Squares’ substitution system

The substitution I devised is a thing I called ‘Awkward Squares’. That was just the working filename I assigned it when I started trying to write one: I wanted it to be awkward to my refinement algorithm. In fact it ended up even more awkward than I’d expected, so I decided it was a good name, and could stay.

The basic idea of Awkward Squares is that each tile is a simple square. The squares come in two colours, red and blue. Both types of square expand to two red and two blue squares, but in one case, horizontally adjacent pairs of squares are the same colour, and in the other, vertically adjacent.

This would be extremely boring, except for that spur poking out at the bottom. That’s the awkward part: I did something deliberately silly with the edge mappings.

To begin with, I assigned the horizontal and vertical edges different types, so that each one could be expanded into sub-edges in a different way:

There are two distinct edge types here: the horizontal edges (drawn in green, with one arrow), and the vertical edges (in purple with two arrows). Both edge types have a direction, so that traversing them backwards reverses the order of the sub-edges they expand into.

The edge types and arrows also function as matching rules: they constrain the squares in the tiling to join together with the same type of edges meeting each other, and the arrows pointing in the same direction. In this case, the effect is simply to keep all the squares the same way up: rotating one square relative to another isn’t allowed. (So far, still nothing awkward – that’s going out of its way to be simple!)

To expand one square into a square of twice the edge length, the obvious thing would be to expand a horizontal edge into two horizontal edges end to end, and similarly for vertical edges. But instead, I’ve done something different. A horizontal edge expands into two horizontal edges and a vertical one.

On the other hand, the vertical edge behaves normally, expanding to two vertical edges as you’d expect:

So when you expand a square, you still do get a larger square which can contain four of the smaller squares:

0 1 2 3 4 Tiled

But the effect of the knight’s-move expansion of the horizontal edge is that the next Awkward Square to the right of this one will be placed one (smaller) square lower down, because in that expansion of the edges, the right-hand vertical edge has to start below the baseline of the output square, where the expansion of the bottom horizontal edge ended. So that’s the part that matches up with the left edge of the next square.

You can also see that in the expansion diagrams above: the large circular blobs in the expansion of the R and B tile types show where the images of the original square’s vertices are. And those are the points which must match between one tile and the next.

So, suppose you know the types of all four neighbours L, R, U, D of an Awkward Square S of one size. Then here’s what it tells you about the next size down:

What’s on the right-hand side of the S3 sub-square? Or on the left-hand side of S0? You can’t answer this if all you know is which type of tile each of L, R, U, and D is. To tell what’s on the right of S3, you’d need to know the type of the larger tile diagonally adjacent to S, to the right of U and above R. Similarly, you also need to know what’s below L and left of D.

Formally, what’s immediately on the right of S3 is the spur poking downwards from the expansion of the U square. Similarly, to the left of S0 is the downward spur from the L square. It’s just that that doesn’t help us find out the identity of the smaller squares that must exist there in a full tiling.

So this is exactly an example of the scenario I suggested at the top of this section: we try to find out what’s to the right of the S3 subtile, we find it’s a zero-thickness spur of one of the neighbouring supertiles, and then we need to know what’s on the other side of that spur before we can answer the original question.

Extendable list of queries

My solution to this was to rewrite the part of the algorithm that determines all the necessary information about a tile to decide on its subtype.

In the initial version of the algorithm, that code simply looped over each edge, finding out what was on the far side of the edge. Now it has a list of more general queries that it needs to answer about a tile.

Of course, the initial list of queries is exactly the same as before: what’s on the far side of each edge? That’s the minimum information needed to determine a tile’s subtype.

But then, another piece of code is asked to determine the types of the child tiles expanded from a parent. And the only thing it’s told about the parent tile is the list of answers to the current set of queries. From that alone, it must answer all the same queries about the child tiles.

In the case of the Awkward Squares system, it will find that it can’t answer, for the reason shown in the previous section: if all you know is what large tiles borders the parent along its edges, you can’t always know what smaller tiles border the children along their edges. So the ‘determine the child subtypes’ code will fail to return an answer – and instead, it will return a description of the question it tried to ask about the parent tile which wasn’t answered.

These questions will in general be conditional on an answer to a previous question. For example, the question ‘What’s on the other side of parent edge 3?’ might give a tile type as answer which tells the code it must ask about some edge of that tile in turn. So its new question will be along the lines of ‘Given that the question about parent edge 3 turned out to be edge 5 of a type-foo tile, what’s on the other side of edge 4 of that?’. In cases where the question about parent edge 3 has a different answer, the answer to that would be None, or whatever form of ‘not applicable’ is appropriate to the programming language.

(These followup queries have to be conditional on the previous queries, because in many substitution systems, tiles aren’t all the same shape. If you have to ask a followup question to traverse a spur, it will very likely be specific to the tile type. In Awkward Squares that doesn’t come up, because both square types have the same shape of expansion, but in that respect, it’s not as awkward as some systems!)

Unfortunately, once a new query is identified, everything the code thought it knew about the subtypes of tiles becomes invalid, because it doesn’t have the answer to the new query for any of them. So it must start all over again, this time including the new query in the list of things it wants to know, right from square one.

In the case of Awkward Squares, we end up with eight extra queries. Basically they’re the obvious two: what are the upper-right and lower-left diagonal neighbours of the original tile? But the query list has to be different for each original tile type (tiles don’t even necessarily have the same number of edges!), and for the type of each tile encountered in a previous query. So the 8 queries cover all combinations of the original tile type (red or blue), which neighbour we initially asked about, and which type it was.

Sometimes you have to refine more than once!

After adding those 8 queries, the refiner restarts from the beginning, runs successfully to completion, and outputs a refined tiling. There are quite a lot of tiles in it, as it turns out: nine copies of the blue tile, and eight copies of the red one.

(That surprised me for an instant – wouldn’t you expect the same number of each? But no: the substitution rules treat horizontal and vertical lines differently, so it shouldn’t be surprising that tiles behave differently if their expansions are rotated 90° so that horizontal and vertical interchange.)

The real surprise came when I tried to make a transducer out of this refined Awkward Squares tiling. It still didn’t work!

But all is not lost. On the theory that it was a very easy experiment and worth a try, I simply fed the refiner’s output straight back into another run of the refiner. This time, it cloned only four of the tile types, each into just two copies … and the output of the second run, the doubly-refined tiling, does successfully produce a transducer. Phew!

I don’t know that it will be particularly illuminating, but here’s an example of one of the most difficult ambiguities in the Awkward Squares tiling. This was an ambiguity that the transducer-building code reported was still present in the tiling system even after the first refinement, and only went away in the second one: you can see that the infinite supertile in the bottom left is the same in both pictures except that the top tile on its right-hand edge changes its label between B3.1 and B3.2 – the two subtypes that the second refinement made out of the B3 tile generated by the first one.

Type 1 Type 2

I can’t make much sense of that myself – Awkward Squares didn’t include “readily comprehensible to humans” in its design goals! But it at least demonstrates the code to be doing what it said it did.

I was a bit surprised when the first run didn’t make the tiling unambiguous, but not too surprised. After all, “make it unambiguous” was not in the software’s actual instructions. All I told the algorithm to do was to bake some conveniently reachable information about each tile’s neighbourhood into the tile type. If that conveniently reachable information wasn’t enough to remove all ambiguities, well, who said it would be in the first place?

But if that wasn’t enough, then it does make reasonable sense to me that running the refiner again should help. Because the first run included information in each tile’s type about the unrefined types in its neighbourhood – and then the second run includes information in each tile’s type about the types in its neighbourhood as augmented by the first refinement. So each tile now includes information from an even wider radius of the original tiling.

My conjecture is that some number of refinement runs always ought to be enough. Rationale: any infinitely long string of combinatorial coordinates of a tile indicates not only its immediate type, but the type of all its larger and larger supertiles. The more you refine the substitution system, the more information is included about the neighbouring large supertiles. Eventually, surely, you’ll end up with the region determined by each coordinate growing on all sides, and then the union of all those regions must cover the whole plane – which is a sufficient criterion for the coordinate string unambiguously defining a single tiling of the whole plane, and not leaving any region less than fully determined.

But that’s a pretty handwavy argument, and also, I have no idea how many refinements might be needed! It was a surprise to me that the maximum number was more than 1. Is it bounded at all? Who knows!

The test case that wasn’t a test case

One last silly story:

When I was initially testing this refiner, the very first tiling I tested it on wasn’t the chair tiling shown above. It was the Ammann-Beenker tiling: an aperiodic system with two tile types, discovered around the same time as the Penrose tilings, but less famous.

One of the tiles in the Ammann-Beenker tiling is a rhombus with 45° and 135° angles. Depending on your point of view, the other is either a square, or a pair of mirror-image right triangles which always join along their hypotenuses. I’ve seen both interpretations; I think the squares look nicer, but the triangles make an easier substitution system. (For much the same reason as sawing the Penrose tiles into two triangles – each tile’s expansion fills exactly the same area as the original tile.)

Just like the simple shapes in Penrose tilings, either of those shapes – or both together – could tile the plane periodically, if it weren’t for some matching rules, shown by the arrows on the edges below:

(If you prefer to think of the tiling as having one square instead of two triangles, then the double-arrow edges vanish completely, and you just have a square and a rhombus, with all edges being of the same type, and just different patterns of edge directions around the two tiles’ perimeters. Up to you.)

I’ve had this tiling description in my source repository for a year or more. My code wasn’t able to build a transducer from it, and I didn’t know how to solve that problem by myself, or know of any alternative substitution systems that might happen to eliminate the ambiguity. And it’s a small and simple system, so it made a good first test case – not too large, and if it worked I’d get rid of a long-standing annoyance.

So I ran my draft refiner over the Ammann-Beenker tiling, and it worked, and generated me a refined tiling that did admit a transducer. Success!

What do you do once you’ve built a transducer for a previously ambiguous tiling? You identify a specific ambiguous case from the unrefined substitution system, and use the new transducer to draw both versions of it, to demonstrate that you really have solved the problem. That’s what I did for the hat ambiguity, and further up this article I did the same for the chair tiling (and Awkward Squares).

But when I examined the transducer failure report to try to figure out the ambiguous case, I became suspicious. It didn’t seem to make sense.

In fact, it turned out that my transducer-construction code simply had a bug: it had given up too soon when trying to build this transducer. The original Ammann-Beenker system, without any refinement, does admit a transducer after all, and it was only a bug in my code that made me think it didn’t!

At that early stage, I hadn’t written the part of the algorithm which automatically re-merges tile subtypes. So I got an over-refined tiling with lots of subtypes of each tile type, and had to re-merge as many as I could by hand, reverting any change that broke the transducer again. By the time I’d finished that, I was back down to just one rhombus, and two squares; merging the last two squares caused the transducer construction to fail. But if I’d had the automated tile-merging code at the time, it would have merged the last two squares anyway, which might have made me suspicious sooner!

Well, regardless of that, the upshot is that now I do have a working Ammann-Beenker transducer, when previously I didn’t – even if the reason why wasn’t quite what I expected it to be. So I should show some pretty pictures made from it, in celebration. But I can’t triumphantly show the two versions of an ambiguous Ammann-Beenker instance, because as it turns out, there aren’t any. So instead I’ll just show a couple of particularly symmetric tilings, which also contain infinite supertile boundaries, so it takes a transducer to render them conveniently:

2-way symmetric 8-way symmetric

This tiling is generated from the system shown above, with two rhombuses and a triangle, but I added a one-off mapping layer at the very bottom which maps one of the triangles to nothing and the other to a square. So the supertile boundaries ‘morally’ ought to be straight, but they just swerve around each square they come to.

Conclusion

I’m very pleased with this piece of work! It’s a significant advance in the practical uses of substitution-tiling transducers. Now if I hear about a new substitution system and want to try generating instances of it, I don’t have to worry if it turns out to be ambiguous. I can just run my new refiner, and most likely get a disambiguated version of it, without needing anyone else to have done the clever part for me.

For example, a July 2025 blog post by mathBlock shows an interesting alternative substitution system for the hat tiling, which takes two iterations of deflation to have the same effect as a single deflation in any of the normal systems – that is, you can half-deflate a hat tiling, obtaining a tiling that’s intermediate between the original tiling and its full deflation. That struck me as an interesting thing to investigate: what happens if you half-deflate some of the special instances of the tiling, like the rotationally symmetric ones, or the “singular” nearly-symmetric ones? But when I coded up mathBlock’s system in the form of one of my tiling description files, I tried to build a transducer, and sadly, found it was ambiguous.

That was what inspired me to try out this refiner idea – and it worked, so I was able to produce an unambiguous refinement of mathBlock’s substitution, and use that for my investigations. (And it turns out that some of the symmetric and singular hat patterns half-deflate to each other, which is an interesting finding, and perhaps would have been an alternative way to discover the singular patterns!)