[Math] uncountable number of Penrose tiling

geometrytiling

I am interested in Penrose tiling, though I am not an expert, so I apologize in advance.

It is known that that the number of different Penrose tilings is uncountable. This may be implied from de Bruijn method, of inducing these tilings from a cross section of a regular (cubic) tiling in 5 dimensions (But maybe I am mixing here between the two areas, since it is not clear for me from de Bruijn method if the size of the tiles themselves vary for each cross-section). However, in Martin Gardner's book “Penrose Tiles to Trapdoor ciphers” (or PDF of first two chpters), the author describes a way of Conway to prove – in another way – that the number of different Penrose tilings is uncountable.

However, this method is completely unclear for me. Here is the description of Gardner for Conway's method:

Conway's proof of the uncountability of Penrose patterns (Penrose had earlier proved it in a different way) can be outlined as follows. On the kite label one side of the axis of symmetry $L$, the other $R$ (for left and right). Do the same on the dart, using $l$ and $r$. Now pick a random point on the tiling. Record the letter that gives its location on the tile. Inflate the pattern one step, note the location of the same point in a second-generation tile and again record the letter. Continuing through higher inflations, you generate an infinite sequence of symbols that is a unique labeling of the original pattern seen, so to speak, from the selected point.

[…] Not all possible sequences of the four symbols can be produced this way, but those that label different patterns can be shown to corespond in number with the number of points on a line.

How does this method induce a bijective function to the points on the line?

Best Answer

The set of tilings (which I'll call $T$) corresponds in number to the points on a line, so this essentially claims that $\lvert T\rvert=\lvert\mathbb R\rvert=\mathfrak c$. Instead of actually establishing a bijection, you can also establish two injections.

Upper bound on the cardinality

$\lvert T\rvert\le\lvert\mathbb R\rvert$ is easy: interpret $L,R,l,r$ as digits $0,1,2,3$ and the whole infinite sequence as a decimal fraction. Since the digit $9$ does not occur, you don't have to worry about things like $0.99\!\ldots=1$ so you know that every infinite sequence corresponds exactly to one real number. So you have an injective map from $T$ to $[0,1)\subset\mathbb R$.

Uncountability of sequences

$\lvert T\rvert\ge\lvert\mathbb R\rvert$ is harder. You could interpret rational numbers as fractions with base $4$, so every digit would correspond to one of the letters. You could also do the following preprocessing:

$$f(x):=\begin{cases} L,g(x) &\text{if } x\in[0,1) \\ R,g(1/x) &\text{if } x\in[1,\infty) \\ l,g(-x) &\text{if } x\in(-1,0) \\ r,g(-1/x)&\text{if } x\in(\infty,-1] \end{cases}$$

This will map any $x$ to the range $[0,1]$ which can then be used as input to the second function $g$ that represents that number in base $4$ and thus turns it into a sequence. You could write $1=0.333\!\ldots_4$ or tweak the definition of $f$ a bit (e.g. using $1-g(1/x)$ in the second case) to ensure that you only translate numbers from the range $[0,1)$ so that you can concentrate on the digits after the point.

Uncountability of point labels

So at this point, you have an injective function from $\mathbb R$ to infinite sequences in these four letters. But now you have a technical problem:

Not all possible sequences of the four symbols can be produced this way

You have to work out the exact conditions of which sequences can and which can not be produced in this way. My guess is that you can show that there are only countably many forbidden sequences, so the remaining sequences would still be uncountably many.

Uncountability of tilings

As Daniel reminded me in a comment, what we have worked to so far (at least if you manage to show the countability of the sequences which are not tilings) demonstrates that there are uncountably many sequences describing a pattern seen from a given tile. But there are infinitely many tiles from which you could label the pattern and it would still be the same pattern that should be counted only once.

Two sequences denote the same pattern if they agree after some point $k$. So you can generate alternate labels for the same pattern by subsequently modifying elements of the sequence, starting at the first. You have four options for the first sequence item, and for each of them four for the second, and so on. You could explore all possible sequence modifications in a breadth first search, therefore there are only countably many (i.e. $\lvert\mathbb N\rvert=\aleph_0$) of these.

So why does that not break the uncountability of $T$? I'm not sure how you feel, but (at least at the moment) a counter-argument works best for me. Suppose there were only countably many tilings in $T$, represented by any suitable sequence for each. Then you could use the common $\mathbb N^2$ iteration: Take the original label of the first tiling, then the original label of the second tiling followed by the first modification of the first tiling, then the original label of the thirs tiling followed by the first modification of the second tiling followed by the second modification of the first tiling, and so on. In the end you'd enumerate all point labels, so there could only be $\lvert\mathbb N^2\rvert=\lvert\mathbb N\rvert=\aleph_0$ of these. This is a contradiction to the uncountability of label sequences we showed before.

Now that I think about it, this only shows $\lvert T\rvert>\aleph_0$ but one would need the continuum hypothesis to deduce $\lvert T\rvert=\mathfrak c$ from this. So if anyone has a better explanation (which still works on an intuitive level) of why $\mathfrak c/\aleph_0=\mathfrak c$ feel free to edit this post, comment, or provide your own answer.

Related Question