Aperiodic Tilings

Intro to the How and Why of Aperiodic Tilings

Tilings! Also called tessellations, patterns in the Euclidian plane, space filling arrangements of infinitely many copies of geometric shapes, or just considered to be things in photos of interior design magazines... Tilings have a rich history, from the Sumerians in 4000BC, via the Romans' geometric mosaics, through the Girih and Zellij tilings used in Medieval mosques, to the modern theorems and ideas that have lead to new materials, facts about arrangements of things and packings, and interesting YT videos on the quirkier side of 'covering the plane with shapes'...  

To anyone who knows me personally, or professionally, it should be no surprise that I get rather very excited when I see videos on YouTube or blog posts or book sections on tilings. 

The reason why might not be that well known - but I spent the years on my PhD studying the computability and unsolvability of tilings!! (For the curious, here's my thesis: https://etheses.whiterose.ac.uk/26051/ ) I've found them fascinating for most of my life, and this post aims to share a portion of that.

There is a rich theory and history of results, many of which are surprisingly recent! Granted, 'recent' in pure maths does indeed include 'about 40 years ago', but when you consider that tilings in one shape or form (geddit?) go back over 6,000 years, it is remarkable that some of these ideas, as best we know from analysing old and ancient texts and artefacts, have only come to light in the 20th and 21st centuries. 

In this blog post, I want to talk about something that I've not seen explained or covered on YT or in many blogs - I want to show how to answer the following question: What makes a tiling aperiodic? 

Essentially, how do we show that a given tiling is 'aperiodic'? How do you prove that a tiling will never ever repeat itself in the plane? It sounds daunting, but it's surprisingly straightforward.

Whilst there are plenty of resources that talk about Penrose tilings, for example, and extoll the virtues of an aperiodic tiling, such as this frankly excellent video from Veritasium; 'The Infinite Pattern that Never Repeats', the fact of 'how and why' tilings are, or can be aperiodic is often glossed over. 

The mathematics that makes this fact true of Penrose tilings, and indeed other tilings such as those from Berger in the 60's, is rather beautiful and I think quite intuitive if you touch on all the salient points with some clarity.

But first...

What is a tiling?

It may seem rather intuitive, but defining a few terms will be useful later on:

• A tiling is a covering of the plane using selected shapes from a tile set.
• A tile set is just the set of prototypes for the shapes we are going to use. This is also called a 'palette' in the literature - poetically giving the impression of an artist choosing from the set the most beautiful options with which to cover the plane! 😊
• A patch is a finite 'block' of tiles covering some finite portion of the plane - think of it as a 'cutting' from the overall tiling of the plane.

The idea of a tiling then is that we have a 'finite box' of tiles, each of which we can make infinitely many copies of and arrange them in the plane, usually just using rotations and translations, such that we can cover the plane entirely using just shapes from that initial box. 

Now, there are lots and lots of questions and parameters you can apply... for example, in Wang tilings you are not allowed to rotate the square diagonally quadrisected and coloured tiles, whereas in most other tilings you can. In some tilings you might admit that you can 'flip' the tiles - like a pancake - so that they are mirrored across some axis - but we won't consider those for now. 

There are also questions about 'what counts as a tiling?' You might be able to tile the plane but you have to admit one or finitely many holes - is that ok? Do you have to use every tile in the original tile set? And use each one infinitely often? 

There are actually no hard and fast rules in general - this is in part what makes tilings quite interesting when you play with these options! For ease of use, we'll make the following assumptions - for a given tile set \(S\):

1. You must use every tile \(t\) in \( S \).
2. You must use each tile infinitely often.
3. You are not allowed any holes in your resulting \(S\)-tiling.

Rule 1 is fairly redundant, it just maintains that our tile sets will be as small as possible. Rule 2 maintains that our tilings are in some sense 'uniform', and rule 3 means we don't have to worry about any holes - if there's a hole, it's not a tiling! (Isn't pure maths nice, the way you can just 'get rid' of cases you don't want?)

So what is periodicity? 

Firstly, let's define periodicity - put simply, if a tiling is periodic, then it has a 'period'. This will be some linear shift (translation and/or rotation) that we can apply to the entire tiling, such that when we fix some point in the plane, and perform this shift on our tiling, we end up with a tiling that is the same (in maths terms, 'indistinguishable') from the tiling we started with.

For illustration, imagine an infinite squared sheet of paper. We can think of these squares as a tiling - just, all white squares, and probably not the most exciting tiling, but it is a tiling! 

Now, if we choose any corner and rotate this infinite sheet of squared paper by 90 degrees clockwise, we end up with a sheet of infinite squared paper that looks exactly the same as the one we started with. 

If we apply repeating coloured patterns to these square tiles, we may lost some of these rotations and translations, but we can see that there is a 'period' to our tiling; there is some number \(k\) such that if we shift a tiling \(T\) by \(k\)-many tiles in some direction, then we end up with another copy of \(T\).

So what about non-periodic and aperiodic?

It is fairly easy to just say 

"aperiodicity is when a tiling doesn't repeat itself in the plane...", 

or more mathematically

"An aperiodic tiling is one that has no translational or rotational 

symmetry in the plane."

... and these are well and good. However, we have to be a little more precise. 

As Veritasium very well shows - you can take some periodic tilings, change a few of them around without disturbing the rest of the tiling, and then it's not periodic anymore! Here's a screenshot of his example from his video (timestamp in the link above):

From this, it's clear here that 'non-periodic' isn't a necessary part of this tiling. It can be 'non-periodic' for sure - there are no points for which we can apply a linear transform to this example and get back the same tiling. But this lack of a period shift in this example does not mean that it can only form non-periodic tilings... and this is how we will define an aperiodic tiling set. 

So here is the last thing we are going to fix in our definitions - we are going to require that for a tile set \(S\) to be 'aperiodic' it must admit only non-periodic tilings... there must be no way to tile the plane periodically. 

Sound like quite the challenge, right? It's actually surprisingly straightforward in some cases to show that some tile sets have this property - though the reason may be surprising at first! Let's dive in... 

Similarity of Tiling Sets

This is a notion we are going to use in the following proof - the idea of similarity between two tilings. The idea is that for two given tilings, they have 'similarity' if we can find a 'cut' of patches of tiles in one tiling that give us the other tiling. 

For example, take Veritasium's tiling above - if I take the following cut (in GREEN) I get the 'squared paper' tiling I talked about earlier: 

Each pair of triangles that share a long edge, even the ones that are rotated out of place, now become squares. This is, by removing these diagonals, a square tiling of the plane! 

So we can see that, in this sense, the 'squared paper' tiling and 'Veritasium's triangular' tiling are similar by means of the cut we have defined. Hopefully this seems quite intuitive - linguistically, at least. 😅

So this notion of 'similarity' is a way of going "well, if two tiling sets look similar, then they are similar in a mathematical sense, too" - by means of this notion of a cut. 

(Note - I've glossed over quite a few technical details here, but they aren't that hard to formalise for the curious. For now, let's get on to how this works with aperiodicity...)

Self-Similarity and Aperiodicity

It may seem unusual or surprising (or just plain dumb) to connect these two things. What the heck does 'aperiodicity' and 'self-similarity' have to do with one another? Why would you consider 'self-similarity' of tilings? What even is 'self-similarity'? 

Well, having defined 'similarity', 'self-similarity' is perhaps unsurprisingly just 'similarity of a tiling with itself'. It's kinda anticlimactic, but the important notion is that for a tiling to be self-similar, there exists a cut such that each patch of tiles in our cut 'simulates' some tile in our original tile set. 

The general theorem, proved by Durand, Romashchenko, and Shen in 2010 (see: https://arxiv.org/pdf/1003.2801.pdf) is as follows:

Theorem: Any tile set \(S\) that is self-similar has only aperiodic tilings.

Your reaction may well be, at this point, "I'm sorry, whuuuut??" But let me walk you through the argument, and then show how Penrose tilings are a case of this theorem...

[Technical note - In the below I put 'same tiling' in quotes as it lets me gloss over notions of isomorphism and the details therein, for clarity]

Proof of Theorem: We are going to use a 'proof by contradiction' - this means we're going to assume that the theorem is false and then show that this leads to a contradiction. And if something leads to a contradiction, then the opposite of that statement must be the truth! (Welcome to pure maths, if you're new to this!)

So, we're going to assume that a self-similar tiling is actually periodic, and see what happens... 

Let's some tile set \(S\) be self-similar, and take two similar tilings; \(A\) and \(B\). Let \(A\) be the 'bigger' tiling - that is, \(A\) is a 'cut out' of \(B\), through the process of taking a 'cut' we outlined above. We know that \(A\) and \(B\) are the 'same tiling', but we have this intermediary cut that lets us easily get \(A\) from \(B\). Note that both \(A\) and \(B\) are periodic by our assumption.

By our definitions, for a tiling to be periodic, then there is some number \(k\) that is our 'period shift' of our tiling. Let \(k\) be a period of \(B\), and because \(A\) is the 'same tiling', it must also have a shift vector as well. Call this \(v\).

Let's take the tiling \(A\), our cut of \(B\), and rescale it to be the same proportions as \(B\). This 'cut-and-rescaled' tiling we'll call \(A^*\). Then \(A^*\)'s periodic shift vector must be \(v / k\). So each time we do this 'cut-and-rescale', we get a valid \(S\)-tiling, but one with a smaller periodic shift vector. 

Because we know that \(A^*\) is a self-similar tiling, we can repeat this operation of cutting and rescaling infinitely often!

So what does this mean for our periodic shift vectors? Well, they get smaller and smaller and smaller until in the limit... they are zero!! But if our shift vector is actually a 'zero vector' - that is, a vector of length zero - then we have a contradiction! We assumed that every cut-and-rescale had a periodic shift vector that wasn't zero (because we assumed every tiling from \(S\) was periodic). But then we showed that in the limit these periodicity vectors disappear under cut-and-rescale... 

This means that our assumption - that a self-similar tiling can be periodic - was wrong, and so the opposite of what we assumed must be true: namely, that any self-similar tile set must always be aperiodic! 

QED! 🥳

Intuitively, if you can agree with the argument that "after rescaling the period vector shrinks" then even if the limit case (as they are called) isn't something you grasp immediately, you can consider it perhaps another way... 

For a given period vector \(k\) as above, after enough cut-and-rescales the vector will be small enough to fit inside a tile... Clearly, this shift cannot ever line up with the original tiling that we start with, and so we can get our contradiction in a more intuitive way, so long as we are happy that no fractional shift of a tiling is a valid integer period.

It's worth noting, as a final point on this, that whilst being self-similar is sufficient for aperiodicity, it is not necessary! There are other ways that something can be aperiodic...

Other Notions of Aperiodicity

This is far from the only way we can prove aperiodicity! In fact, it wasn't even the first - Robert Berger, Hao Wang's student, proved it by embedding a Turing Machine into the square Wang tiles. 

By the existence of various computable phenomena, this leads to the natural existence of aperiodic tilings! To see this, consider a computer program that computes a number that never repeats - that is, has no periodicity. A really good example of this is the spigot algorithm for computing pi - we know that the digits of pi don't repeat (as if they did, pi would be rational, and we know that isn't the case), so a tiling that simulates the spigot algorithm churning out digits of pi sequentially will necessarily never repeat itself. 

Whilst this is a brief aside, it's worth mentioning, as it was a very important development in the recent history (well, the 60's) of the study of tilings of the plane. 

Penrose Tilings are Self-Similar

As a final nod to the proof above, we demonstrate that Penrose tilings have this by using this animated gif from Wikipedia - it shows how a Penrose rhombus tiling (known as 'type P3') can 'deflate' - that is the phrase used in the original proof to show that larger tiles decompose into smaller tiles:

But our proof is not quite complete - note that we proved that something is aperiodic if we can go from larger tiles to smaller ones and then rescale... so let's just reverse this gif! It looks like this: 

Now imagine that at each 'inflation' we complete the tiling of the plane, so that at the end we don't end up with just one tile, but a full tiling. The last step would then be to rescale our tiling down to the same size at each iteration and what we find is that we have recreated all the conditions of our proof! 

So, we can use this method to aptly prove that Penrose tilings are always, and only, periodic! 

Closing Remarks

It is my hope that this explanation of the 'why?' of the aperiodicity of tilings, with a worked example in Penrose tilings, help to satisfy some curiosity in those who have known of aperiodic tilings but perhaps not a full reason for how such things are shown. 

It's worth noting that such arguments involving these seemingly fractal properties of a tiling - that is, some kind of 'similarity under magnification' - are quite beautiful. But the rather abstract nature isn't removed from the real world - the link between Penrose tilings and quasicrystals is actually under quite active investigation! 

This part of discrete mathematics is great fun to study, and I hope that some of the satisfaction that can be found in this subject is slightly more accessible to more people! 

Yours mathematically, M.

Addendum

There are many areas of tilings that might be good for more experienced communicators to grapple with - these include:

• de Bruijn's work on complex pentagrids and Penrose tilings - there is a recent starter here, but the original papers are wonderful and quite accessible: http://www.neverendingbooks.org/de-bruijns-pentagrids 
• de Bruijn's proof that there are only 8 valid corner configurations (there are actually more but only 8 are valid in a tiling, and there are several routes into the why). See de Bruijn "Algebraic theory of Penrose’s non-periodic tilings of the plane" parts I and II. 
• van Emde Boas gives a very accessible way of coding Turing machines into Wang tiles (this was a method I used extensively in my PhD): https://www.researchgate.net/publication/2811622_The_Convenience_of_Tilings

This may be some good inspiration for future outreach stuff! :)