Generating the P3 Tiling

# Generating the P3 Tiling Source: [https://k-monk.org/blog/generating-the-p3-tiling/](https://k-monk.org/blog/generating-the-p3-tiling/) - [HOME](https://k-monk.org/) - [BLOG](https://k-monk.org/blog) - [RSS](https://k-monk.org/feed.xml) ### 2026\-06\-28 Have you heard of Penrose tilings? Today, I want to describe one algorithm you can use to generate them\. My hope is that this article will serve as necessary background material for some future subjects I have in mind, the details of which I'll leave in suspense for now\. ## [Introduction to Tilings](https://k-monk.org/blog/generating-the-p3-tiling/#introduction-to-tilings) What's a tiling, in the first place? Mathematicians call any pattern that covers the 2D plane with no gaps a*tiling*of the 2D plane\. For example, imagine a chessboard extending infinitely in all directions\.  The set of shapes that appear in a tiling are called its*prototiles*\. The chessboard tiling uses only one prototile, a square\. A tiling is called*periodic*if there is a way of shifting the whole plane in such a way that gets you back to the pattern you started at\. The chessboard tiling is periodic, because, for example, you can shift the whole thing one square to the right and arrive at an identical pattern\. A tiling is called*aperiodic*if it admits no such translational symmetry\. Penrose tilings were the first known aperiodic tilings of the plane to use only two prototiles\. They were discovered by Roger Penrose in the 1970s\. There are three variants that I'm aware of, known as P1, P2, and P3\. P1 uses four prototiles, while P2 and P3 use only two\. We'll concentrate on P3 today\. ### P1  ### P2 \(Kites and Darts\) ### P3 \(Rhombii\) ## [Subdivision Rules](https://k-monk.org/blog/generating-the-p3-tiling/#subdivision-rules) The following set of four rules constitutes an algorithm to generate P3:  We have four triangles, identified by their color\. Each rule explains how to replace one triangle with a set of smaller ones\. Starting from any one of the four, we can recursively apply the rules\. Each round of subdivision will result in a more detailed tiling of the starting triangle\. Watch what happens when you execute the rules a few times using the buttons below\. These prototiles are named Robinson triangles after Raphael Robinson, who discovered them not long after Penrose first discovered P2 and P3\. See section 10\.3 of[*Tilings and Patterns*](https://archive.org/details/isbn_0716711931)by Grünbaum and Shephard, if you're interested in the history\. You may be noticing that Robinson triangles don't look like the rhombii in P3\. Well, it turns out that these rules will always generate patterns of pairs\. The acute triangles come in pairs, as do the obtuse ones; always joined at the base\. \(Except for the tiles on the rim\.\) So, once we're done subdividing, we can sew these pairs together to get our rhombii\. The red rhombii in the rendering of P3 above are the acute pairs, and the blue rhombii are the obtuse pairs\. Why are the rules guaranteed to generate pairs in this way? Essentially, by structural induction on the subdivision rules\. ## [A Term Rewriting System](https://k-monk.org/blog/generating-the-p3-tiling/#a-term-rewriting-system) I claimed the subdivision rules constitute an algorithm\. That's only sort of true\. The rules are given pictorally, and computers can't operate directly on pictures\. There's a framework for writing down systems like this amenable to machine execution: term rewriting\. Let's see if we can express the rules as term rewriting rules\. If you've not encountered term rewriting before, don't worry; I'll explain as we go\. The first chapter of*Term Rewriting and All That*by Baader and Nipkow is a good introduction to the theory, if you want one\. A Robinson triangle is uniquely identified by its color together with its vertices\. Say we choose the lettersCC,DD,XX, andYYto represent the four triangle colors in the order presented above\. Then, a light blue triangle with verticespp,qq, andrr, for example, can be represented symbolically asC\(p,q,r\)C\(p, q, r\)\. That's a*term*— a piece of syntax — and we want to express the subdivision rules as manipulations of terms\.  Above is a reproduction of the subdivision rules, with labels added for reference\. Notice each subdivision rule creates at least one new vertex\. The vertices created by subdivision are labeledSSandTTon the right hand side of each rule\. If we're going to express the rules as manipulations of terms, we'll need a way of expressingSSandTTin terms of the parent vertices\. Robinson triangles have a nice geometric property we can leverage:SSandTTalways lie1φ\\frac\{1\}\{\\varphi\}of the distance along the edge, whereφ\\varphiis the golden ratio\. The golden ratio shows up here because it's the ratio of a regular pentagon's diagonal to its side, and the Penrose tilings are all about fivefold rotational symmetry\. We'll writep⇒qp \\Rightarrow qto represent the point reached by traveling1φ\\frac\{1\}\{\\varphi\}of the distance frompptoqq\. With that in mind, we're ready to express the subdivision rules as term rewriting rules\. C\(p,q,r\)C\(p, q, r\)→\\rightarrowC\(q,r⇒q,p\)×Y\(r,p,r⇒q\)C\(q, r \\Rightarrow q, p\) \\; \\times \\; Y\(r, p, r \\Rightarrow q\)D\(p,q,r\)D\(p, q, r\)→\\rightarrowD\(r⇒p,p,q\)×X\(q,r,r⇒p\)D\(r \\Rightarrow p, p, q\) \\; \\times \\; X\(q, r, r \\Rightarrow p\)X\(p,q,r\)X\(p, q, r\)→\\rightarrowC\(r,p⇒r,p⇒q\)×X\(q,r,p⇒q\)×Y\(p,p⇒q,p⇒r\)C\(r, p \\Rightarrow r, p \\Rightarrow q\) \\; \\times \\; X\(q, r, p \\Rightarrow q\) \\; \\times \\; Y\(p, p \\Rightarrow q, p \\Rightarrow r\)Y\(p,q,r\)Y\(p, q, r\)→\\rightarrowD\(q⇒r,r,q⇒p\)×X\(q⇒p,q,q⇒r\)×Y\(r,p,q⇒p\)D\(q \\Rightarrow r, r, q \\Rightarrow p\) \\; \\times \\; X\(q \\Rightarrow p, q, q \\Rightarrow r\) \\; \\times \\; Y\(r, p, q \\Rightarrow p\)The color symbolsCC,DD,XX, andYYare what are called "function symbols" in the term rewriting literature: names with a fixed arity \(a fixed number of inputs\)\. The splitting symbol⇒\\Rightarrowand the product symbol×\\timesare also function symbols, but I've chosen to use them in infix form for clarity\. If we were being completely formal, we'd need separate product symbols for arity 2 and for arity 3\. The lowercase letterspp,qq, andrrare variables\. They range over arbitrary terms\. The left hand side of each rule is a pattern; the rule can be applied whenever a satisfying instantiation of the variables in it is found\. Translated into code, this might look something like the recursive function I wrote to generate the P3 images on this page: ``` function generateP3(type, p, q, r, depth) { const triangle = { type: type, depth: depth, p: p, q: q, r: r, }; if (depth > 0) { switch (type) { case "C": { const s = midpoint(r, q); triangle.y = generateP3("Y", r, p, s, depth - 1); triangle.c = generateP3("C", q, s, p, depth - 1); break; } case "D": { const s = midpoint(r, p); triangle.x = generateP3("X", q, r, s, depth - 1); triangle.d = generateP3("D", s, p, q, depth - 1); break; } case "X": { const d = midpoint(p, q); const e = midpoint(p, r); triangle.x = generateP3("X", q, r, d, depth - 1); triangle.y = generateP3("Y", p, d, e, depth - 1); triangle.c = generateP3("C", r, e, d, depth - 1); break; } case "Y": { const d = midpoint(q, p); const e = midpoint(q, r); triangle.x = generateP3("X", d, q, e, depth - 1); triangle.y = generateP3("Y", r, p, d, depth - 1); triangle.d = generateP3("D", e, r, d, depth - 1); break; } default: { console.log("Unexpected color."); break; } } } return triangle; } ``` ## [A Coordinate System](https://k-monk.org/blog/generating-the-p3-tiling/#a-coordinate-system) Using some clever mathematics, we can represent all of the vertices in a P3 tiling using only integer coordinates\. This will come in handy if we ever want to compare points for equality; it'll mean we don't have to worry about floating point imprecision\. The basic idea is that the set \{ζ3,ζ2,ζ,1\}withζ=eπi5\\Bigl\\\{ \\zeta^3 , \\zeta^2 , \\zeta , 1 \\Bigr\\\} \\qquad \\qquad \\text\{with\} \\qquad \\qquad \\zeta = e^\\frac\{\\pi i\}\{5\} forms a basis for the space of P3 coordinates\. We can represent any point in a P3 tiling as a linear combination \(with integer coefficients\) of those four vectors\. To prove this, we'll argue by structural induction on the subdivision rules\. First, notice that bothφ\\varphiandφ−1\\varphi^\{\-1\}have representations in this system: φ=1\+ζ2−ζ31φ=ζ2−ζ3\\varphi = 1 \+ \\zeta^2 \- \\zeta^3 \\qquad \\qquad \\frac\{1\}\{\\varphi\} = \\zeta^2 \- \\zeta^3 The starting coordinates \(i\.e\. the points of the outer𝐗\\textbf\{X\}triangle\) are representable: P=0Q=1R=ζφP = 0 \\qquad Q = 1 \\qquad R = \\frac\{\\zeta\}\{\\varphi\} The midpoint operation used in the subdivision rules is linear interpolation by1φ\\frac\{1\}\{\\varphi\}: p⇒q=p\+q−pφ=p\+φ−1\(q−p\)p \\Rightarrow q = p \+ \\frac\{q \- p\}\{\\varphi\} = p \+ \\varphi^\{\-1\} \(q \- p\) So all we need to show is that the span is closed under addition, subtraction, and multiplication; those are the operations needed to compute the midpoint\. Addition and subtraction are straightforward; they work component\-wise\. Multiplication is a bit more complicated, because distributing yields terms of up to degree six\.\.\. Consider the regular pentagon constructed by taking the alternating vertices of a regular decagon with radius one:  The vertices of any regular polygon around the origin sum to zero: 1\+ζ2\+ζ4\+ζ6\+ζ8=01 \+ \\zeta^2 \+ \\zeta^4 \+ \\zeta^6 \+ \\zeta^8 = 0 \\qquad Using the fact thatζ5=−1\\zeta^5 = \-1, we can rewrite this as ζ4=ζ3−ζ2\+ζ−1\\zeta^4 = \\zeta^3 \- \\zeta^2 \+ \\zeta \- 1 We can use this identity, which is related to what are called "cyclotomic polynomials", to reduce the degree of the term we get from multiplication back down to three\. Working out the details is a bit tedious, but here's the implementation I ended up with: ``` const phi = { a: -1, b: 1, c: 0, d: 1 }; const phiInverse = { a: -1, b: 1, c: 0, d: 0 }; // The ten points of the decahedron. const z0 = { a: 0, b: 0, c: 0, d: 1 }; const z1 = { a: 0, b: 0, c: 1, d: 0 }; const z2 = { a: 0, b: 1, c: 0, d: 0 }; const z3 = { a: 1, b: 0, c: 0, d: 0 }; const z4 = { a: 1, b: -1, c: 1, d: -1 }; const z5 = { a: 0, b: 0, c: 0, d: -1 }; const z6 = { a: 0, b: 0, c: -1, d: 0 }; const z7 = { a: 0, b: -1, c: 0, d: 0 }; const z8 = { a: -1, b: 0, c: 0, d: 0 }; const z9 = { a: -1, b: 1, c: -1, d: 1 }; function sum(x, y) { return { a: x.a + y.a, b: x.b + y.b, c: x.c + y.c, d: x.d + y.d, }; } function difference(x, y) { return { a: x.a - y.a, b: x.b - y.b, c: x.c - y.c, d: x.d - y.d, }; } function product(x, y) { return { a: x.a * y.d + x.b * y.c + x.c * y.b + x.d * y.a + x.a * y.c + x.b * y.b + x.c * y.a, b: x.b * y.d + x.c * y.c + x.d * y.b - (x.a * y.c + x.b * y.b + x.c * y.a), c: x.c * y.d + x.d * y.c - x.a * y.a + (x.a * y.c + x.b * y.b + x.c * y.a), d: x.d * y.d - x.a * y.b - x.b * y.a - (x.a * y.c + x.b * y.b + x.c * y.a), } } function shorten(p) { return product(phiInverse, p); } function midpoint(p, q) { const side = difference(q, p); return sum(p, shorten(side)); } ``` In JS, monstrous language that it is, we lack a real integer type\. So we don't actually get the nice benefit of exact equality comparison, as the code is written here\. But hey, that's what we're stuck with if we want to draw pictures in the browser, and you get the idea\. ## [Resources](https://k-monk.org/blog/generating-the-p3-tiling/#resources) You can inspect this page for the source code used to produce the images here\. Simon Tatham's excellent[article](https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/)on the same subject is part of what inspired me to write this\. The[Tilings Encyclopedia](https://tilings.math.uni-bielefeld.de/)is also a useful reference\. Please email me if you have questions or comments\!