## Penrose Tilings – 1

I gave a “Pizza Pi” talk in my department this past Wednesday (2/19) on Penrose Tilings.  It happened that back in December (’13) I had decided to start playing with Penrose Tilings, possibly to include it in a liberal arts math course I teach.  I was stunned how difficult it was to continue patterns.

The story starts in 1928 when David Hilbert posed the Entscheidungsproblem concerning whether you can decide if a given statement is provable.  In 1936 both Alonzo Church and Alan Turing independently answered this question in the context of first order theories for arithmetic (Peano?), the answer was no.  In the process Turing came up with the concept of a Turing machine, a simple machine which had an infinitely  long tape of zeroes and ones and a head that could read a digit and then write a digit.

If you imagine a series of snapshots of the tape in a Turing machine you could form a grid

like the one above which represents the steps a Turing machine would take to add together the numbers 2 and 3 to obtain 5.  The tape begins with a series of two ones, a zero and then three ones.  This is the input.  I’m purposefully glossing over this as there are many better sites on Turing machines than this one would pretend to be.  The last snapshot of the tape (at the bottom) has five consecutive ones which represents the output of the machine.  Notice that this representation of the Turing machine looks like a bunch of square tiles that have been fitted together.

In 1961 Hao Wang, working on other cases and settings of Hilbert’s Entscheidungsproblem, realized that one of the cases could be modeled by square tiles with labeled edges.

The Bell System Technical Journal – January 1961

The squares cannot be rotated or reflected and when you lay the tiles down the edges must match.  The image above is from Hao’s article and he gives an example in the middle.  The nine tiles form a tile that can be repeated over and over again, tiling the plane periodically.

Wang realized these tiles could act like a Turing machine.  My understanding is that a series of tiles represents a program that will halt if it can be assembled into a repeating pattern where the repeating pattern represents the finished calculation.  I’m not sure however.  Wang said,

4.1.2 The fundamental conjecture: A finite set  of plates is solvable (has at least one solution) if and only if there exists a cyclic rectangle of the plates, or, in other words, a finite set of plates is solvable if and only if it has at least one periodic solution. (1961)

Is there a way to determine, given an arbitrary collection of tiles, whether it tiles the plane?  This was shown to be equivalent to a couple of other conditions.  The argument would hinge on whether there existed a set of Wang tiles that would only tile the plane aperiodically.  This means that the only way of laying down the tiles and matching the edges would result in a tiling that had no translational symmetry.

His student, Robert Berger, showed (1964) that there is such a set.  It consisted of 20,426 tiles though Berger reduced it to just over a hundred very quickly.  In 1995 a set of 13 was found and this is the least known though I seem to remember reading that a lower bound of four would be the best possible. This set up a certain amount of interest in aperiodic tiles that was investigated by a  number of individuals.

Penrose found several sets, but two of them require only two tiles.  These are the rhombs and the kites and darts.

Penrose rhombs

Penrose kite and dart

These are intimately connected and so anything I say about one of them will be true about the other.  The images above are ‘decorated’ to insure that you assemble them the correct way to insure aperiodic tiling.  This is a convenience as you could simply alter the polygons to have various protrusions and indentations like the rhombs above.

These two tilings are studied by splitting them in half and creating a pair of triangles called Robinson Triangles

A tiling with these is called an A-tiling.  These turn out to be a bit simpler to study than the kites and darts.  There are also a similar set of  triangles which result in a B-tiling. Any A-tiling can be made into a tiling by kites and darts while any B-tiling can be made into a tiling by the rhombs.

Furthermore, if you start with an A-tiling and connect acute triangles to obtuse triangles along any shared edge that connects two differently colored vertices you will arrive at a B-tiling.  Conversely you can turn a B-tiling into an A-tiling by associating acute and obtuse triangles with edges joining identically colored vertices.  Starting with an A-tiling you can obtain a B-tiling and then another A-tiling and then another B-tiling and then another A-tiling etc.  Each time the triangles are scaled a bit.  Going from an A-tiling  to another A-tiling (with a B-tiling in between) results in all the A triangles being scaled by $\tau$, the golden ratio.

This process is called inflation and it has an inverse which is decomposition.

Starting with an A-tiling (or a B-tiling) you ca decompose it into smaller A-triangles (or B-triangles).  You can do this indefinitely.  You’ll notice that the acute A-triangle is decomposed into two L’s and one S.  The obtuse A-triangle is decomposed into one L and one S.  If you iterate this you can show that the ratio of L’s to S’s is the ratio of consecutive fibonacci numbers.  In the limit as $n\to\infty$ this is the golden ratio $\tau$ again.  This demonstrates aperiodicity.   If a tiling is periodic then there is a finite chunk that is repeating. That finite chunk has a finite number of pieces in it and the ratio of quantities of any of the tiles has to be rational so the ratios for the entire plane must be rational.  If the ratio is irrational it must be aperiodic.

Inflation and deflation also demonstrate another interesting property, nonlocality.  If you’re trying to set up a Penrose tiling of the plane whatever you’re doing has to be able to be inflated an arbitrary number of times.  Placements on opposite sides of your tiling can influence each other.  There’s an excellent column over at the AMS called “Penrose Tiles can talk across miles” which describes the process with excellent pictures.  Penrose has said the many of the tilings we see with his tiles often have mistakes in them and could not be continued indefinitely.  This is the surprise I came up against when trying to draw some tilings.  Its not enough to follow the matching rules, you have to have a big picture mentality.  Equivalent you can decompose a finite design and at each decomposition scale it up by a factor of $\tau$ and this will create a pattern that stretches over the whole plane (or could).

Penrose also recounts how he visited a tiling being made in front of the new math building where he has his office.  He felt uneasy at first and so found a higher vantage point.  It turned out that they had finished off the boundary of the tiling with an incorrect (but legal) placement.  This placement would cause a problem somewhere off in the middle of the lawn but he made them fix it all the same!

Penrose tilings are also arbitrarily similar.  Sections of Penrose tilings must be ‘inflatable’ and if you inflate up high enough any chunk will fit into either an acute or obtuse Robinson triangle.  But this is true of any Penrose tiling.  Take any pattern in any tiling and it will occur infinitely often in not only that tiling but every other tiling.  Punchline, a picture of a Penrose tiling is insufficient to identify which tiling it is.

At this point you might think that there is only one such tiling but there are many as it turns out, uncountably many. The Robinson triangles allow an easy parameterization of the tilings, though not unique as we’ll see.  Start with a tiling and turn it into a tiling of Robinson triangles.  Choose a point in the plane and identify what kind of triangle it’s in, inflate and identify, inflate and identify, again and again.  I’ll post more on this process eventually, it’s not hard but requires lots of pictures and words.  The result is a sequence of zeroes and ones and a rule that every one is followed by a zero (this will make sense when you see it drawn out).  If we denote by K, all such sequences we can see that $K\subset \{0,1\}^{\mathbb{N}}$.  As I mentioned above, these sequences do not uniquely identify tilings.  If two sequences disagree only on some finite initial segment then they represent the same tiling.

The identification of these sequences with tilings is a powerful tool even if it’s not unique.  You might be tempted to mod out by the obvious equivalence relation but it’ll turn out that this turns K into a pathological space called the Penrose Universe $X=K/~$.  Alain Connes treats it as a fun example of his Noncommutative Geometry.  That’s fairly heavy stuff that I’m not ready to talk about (and probably won’t be for a while).

$\{0,1\}^{\mathbb{N}}$ admits a rather obvious topology.  Give {0,1} the discrete topology and the product the product topology.  It then makes sense to look at K as a subspace.  I’m going to save this, all the all the rest of the ideas I’m about to drop for a later post as it’s getting late (for me). Here’s a couple ideas to think about:

(1) The Cantor set is homeomorphic to $\{0,1\}^{\mathbb{N}}$

(2) K is homeomorphic to the Cantor set (map $0\to 0$ and $10\to 2$ for elements of the Cantor set written in ternary).

This is enough for me to chew on for a bit as the Cantor set is an odd place to be sure, it’s homeomorphic to a countable product of itself!  This association brings a number of questions to the fore, one of which is does it make sense to talk about rational and irrational tilings?  The homeomorphism will associate to each sequence, a real number in the cantor set. Of course this is not unique, so how to do we translate the obvious equivalence relation on K to one on the Cantor set?  Or should we set up a bijection between K and the reals (in binary)?  Are there any number theoretic properties of these tilings?

I have, in the course of the last month, come across a lot of really interesting research on aperiodic tilings including but not limited to,

-Tilings as fiber bundles over the torus

-Tilings as dynamical systems

-Tilings and quasicrystals

-Tilings and C*-algebras, K-theory and inverse limits

-sympletic geometry and tilings.

These tilings are really interesting, not least of all because they provide a visual correspondence with interesting bits of algebra, topology and analysis.  I intend to follow this post up at various times with some of the heavier machinery.  The above is not too shabby of an introduction and explains my lapse in writing recently.