# Why do matching rules make a substitution tiling aperiodic?

Wikipedia hath written:

Every substitution tiling (up to mild conditions) can be "enforced by matching rules"—that is, there exist a set of marked tiles that can only form exactly the substitution tilings generated by the system. The tilings by these marked tiles are necessarily aperiodic.

If I understand this correctly (and indeed I may not), it means that if you have a way of expanding any tile and then subdividing it into tiles, and your tiles have their edges marked in such a way that the subdivision does not allow any of the tiles to be flipped or rotated, then the resulting tiling will not have any translational symmetries. (For simplicity, I'm limiting this to tilings of the plane.)

I've seen this same idea expressed in pretty much the same way in several places. They seem to take it as intuitively clear that when the tile edges can only be lined up in one way in each subdivision, you can't shift the tiling to be coincident with itself, i.e. the tiling is non-periodic. I'm probably missing the obvious here, but I don't see the connection. Why does the inability to flip or rotate tiles in a subdivision prevent translational symmetry?

• This assume, obviously, that the substitution tiling that you begin with is aperiodic. There are substitutions which give periodic tilings, such as the one taking a single square to 4 identical squares, which clearly is periodic. – Dan Rust Dec 7 '17 at 15:50
• @DanRust The idea, as I understand it, is that even the substitution that takes a single square to four squares becomes aperiodic if you mark the edges as shown in my avatar. See p. 54 here. Am I mistaken? – Ben Kovitz Dec 7 '17 at 16:56
• Oh sure, there are plenty of square substitutions which are aperiodic if one allows labels on tiles. The result which says that every substitution tiling is induced by a set of tiles with matching rules is rather non-trivial though - this is a celebrated result of Goodman-Strauss (comp.uark.edu/~strauss/papers/MRandST.pdf) – Dan Rust Dec 7 '17 at 17:33
• @DanRust Hmm, that looks like a later version of the paper that my avatar comes from, with the important addition of Lemma 4.3 on p. 38 (and without all the formatting errors). Thanks! Now digesting… – Ben Kovitz Dec 8 '17 at 2:07

## 1 Answer

In a substitution tiling, each little tile is mapped to a “big tile” that is composed of one or more little tiles. Each big tile gets mapped to a “bigger tile”, composed of one or more big tiles (which are composed of little tiles), and so on forever, like this: If you slid the whole plane by a certain distance $d$, the substitution tiling must map a little tile $t$ to some little tile $t'$ in a corresponding bigger tile such that $t'$ is farther than $d$ from $t$, since the hierarchy of bigger and bigger tiles goes on forever.

The only question now is whether you could swap $t'$ with some other tile $t''$ nearer than $d$ to $t$ without upsetting the tiling. Then sliding the plane could move the tiling onto itself, as happens in this square tiling, since any square can be swapped with any other square: If the substitution forces each little tile to map to a unique placement of little tiles in a bigger tile, then you can’t swap little tiles. And so sliding the plane any distance $d$ must fail to map a tile $t$ to its mate $t'$ some distance $> d$ away. Hence such a substitution tiling must be non-periodic (like the first tiling shown above).

In many cases, you can force a unique placement of tiles by simply marking their edges so you can tell if there’s been a swap. You can even make the square tiling aperiodic if you mark the squares as shown in my avatar.

The above is my attempt to restate as simply as possible the proof of Lemma 4.3 in “Matching rules and substitution tilings” by Chaim Goodman-Strauss, in Annals of Mathematics, vol. 147, no. 1 (1998), pp. 181–223. Thanks to Dan Rust for pointing me to it. The diagrams are from Wikimedia Commons.