Aperiodic tessellations of the plane

Question

Here are some examples of non-periodic tessellations of the plane. Sir Roger Penrose is the expert in that field. How could someone go about proving that a certain tiling of the infinite plane with specific tiles is possible but only in a non-periodic way? It seems impossible to me.

If that's too hard, how about periodic tiling, can we reduce that to a finite tiling and then prove by construction?

Are there any general tools/theory about tessellations or is every case on its own?

I welcome proof or anything really!

Answer 1

If I were to prove the fact that Penrose tiles (with matching rules!) only allow for non-periodic tilings, I'd start with substitution rules, inflation and deflation and the up-down generation of tilings. Given a valid tiling, you can replace its tiles with smaller tiles from the same set. That's deflation. This you can use to show that you can make tilings covering arbitrary areas.

But, in this context more interestingly, you can also perform the opposite direction, which is inflation. So if a tiling fills the whole plane, then you can locally replace combinations of tiles with larger tiles. This you can prove locally, by showing that any finite combination of tiles which can not be composed in this way also cannot lead to an infinite tiling because somewhere something doesn't match up. Composition is even unique, which again can be shown locally. Once you have the fact that every tile is part of an inflated version in a unique way, you can use this to label each tile. A small-triangle tile which is part of a large-triangle tile which is part of a large tirangle tile … would be labeled “sLL…”. So now every tile in your tiling has a name (of infinite length).

That name is pretty unique, since two tiles can only have the same name if they correspond to different bigger tiles for every subsequent inflation. This is only possible at a center of five-fold rotation, but not possible with translation since translated copies have the same orientation, so all their ancestors have the same orientation, so at some level they have to overlap.

So it follows that if tilings are possible, they may contain rotational symmetry but never translational. The fact that tilings of the whole plane are possible is just a slight step beyond the fact that you can create tilings of arbitrary size. You can simply pick a starting tile and choose an infinite name for it. Then you can construct all its ancestors in the inflated versions, and deflating those will cover the entire plane.

Answer 2

There are (at least) two general procedures for proving aperiodicity of tilings on the plane. The one mentioned in the other answer, which we may call hierarchy and summarize as 'unique hierarchy implies aperiodicity'.

The other general procedure is to exploit irrationtality. For example irrational proportions between appearences of the types of tiles also implies aperiodicity. As well as projecting strips of a periodic tiling of higher dimensional spaces onto totally irrational subspaces.