The Jeandel-Rao Aperiodic Wang Tilings of the Plane

Roger Thompson

​

Open University, 16^th November 2022

Wang Tiles

Squares of size 1 with coloured edges

​

An 11 tile tileset and part of a tiling built from it

A tileset is a finite set T of Wang tiles with distinct colorations

​

With unlimited copies of tiles from T available, we try to tile the entire plane, subject to the following:

1. All adjacent edges must match
2. Rotations and reflections are forbidden

​

Types of tilesets

Aperiodic: Allows tilings of the plane, but does not allow periodic tilings

​

​

Finite: No tiling of the entire plane can be made

Periodic: A periodic tiling of the plane can be made - a shifted copy can be made to coincide with the original

Hao Wang’s conjecture (1961): Wang tilesets are finite or periodic

​

Berger(1966) disproved the conjecture, finding a 20426 tile aperiodic tileset (later reduced to 104 tiles)

​

Robinson (1971): 56 tiles, greatly simplifying Berger’s proof

​

Mozes (1989): Virtually any aperiodic inflation tileset can be transformed into an aperiodic Wang tileset e.g. Penrose kite and dart tileset transformed into a 32 tile aperiodic Wang tileset

​

Ammann (1992): 16 tiles

​

​

​

​

​

​

Some history (1)

Kari and Culik (1996) Used Beatty sequences to construct aperiodic tilesets of 14, then 13 tiles. These have arithmetic properties,

so fundamentally different from inflation tilings

​

Jeandel and Rao (2015) Proved by brute force computer search that no tileset with less than 11 tiles is aperiodic, and found two 11 tile aperiodic tilesets

​

​

​

​

​

​

​

Some history (2)

Jeandel and Rao’s use of Transducers

On receiving input s in state w, output n and move to state e

A loop and its equivalent in tiles

A tiling of the plane must be represented entirely by loops, i.e. no sources or sinks

Transducers are a component of finite automata theory

Used here because of availability of algorithms to simplify complex networks of directed graphs

Tiles correspond to state transitions

Jeandel and Rao pan for gold

• They searched for possible aperiodic 10 tile tilesets using transducers. From 3×10⁹ directed graphs, each with up to 1.8×10⁷ transitions, they found one possible candidate, and proved it to be finite:

• They also searched for possible aperiodic 11 tile tilesets, also using transducers. From 10¹¹ directed graphs, each with even more transitions, they found 25 possible candidates. We will look at five of them:

​

T_X

T_Z

T_A

Structure recently discovered

N,S labels

W,E labels

Trivial bijection

Intriguing!

T_JR

T_JR2

The proven aperiodic 11 tile tilesets, whose structure is known

Only possible to have T₄ = T₁T₀T₀T₀

​

or T₅ = T₁T₀T₀T₀T₀

T₄

Red states are sources or sinks, so excluded.

Beige states can be combined, since their inputs and outputs are identical

Top and bottom colours are red or white, so T₄ rows may tile with themselves

(they actually can’t)

T₅

Green states and transitions are excluded because the two columns B and M force a finite tiling

Number of T₅ rows / number of T₄ rows → φ as the number of rows → ∞, where φ = (√5 + 1)/ 2

Top and bottom colours are also red or white, so T₅ rows may tile with themselves or with T₄ rows

T_JR2 tileset and sample

T_JR tileset and sample

T_JR : key points from Jeandel and Rao’s proof

• Number of T₅ rows / number of T₄ rows → φ as the number of rows → ∞, where φ = (√5 + 1)/ 2

• Then if F_n is the nth Fibonacci number (F₀ = 0, F₁ = 1, F_n = F_n+1 + F_n), and u(n) is the string of length F_n+2 starting at position F_n+3 of the fixed point of the Fibonacci substitution using the alphabet {5,4}, then the bi-infinite rows T_u(n), T_u(n+1), T_u(n+2) can be made for any n

• Denote the sequence of rows T_a, T_b, T_c, … in ascending y order by T_abc

• Intricate proof of aperiodicity involves tracking of 000 and 100 in the transducer outputs from T_u(n) which are input into T_u(n+1)

The Fibonacci substitution and u_n

The Fibonacci substitution: 5↦54, 4↦5

Start with 5 and apply repeatedly:

5

54

545

54554

54554545

5455454554554

545545455455454554545

5 4 55 454 55455 45455454 5….

u_-1 u₀ u₁ u₂ u₃ u₄

​

​

T_JR : Labbé’s discovery of structure

• Construction of a Markov partition

• Rauzy induction maps particular non-rectangular patches in T_JR to T_u - a new 19 tile tileset proven to be self-similar and aperiodic

• Properties of T_u prove that an infinite number of T_JR tilings can be made which cannot be generated from the Markov partition. These are conjectured to be of zero measure in the set of all possible tilings

• Very recent discovery of Conway worms, first seen in cartwheel tiling using Penrose kite and dart tiles

Markov partitions for T_JR, T_JR2

Fundamental rectangles at (mφ + n, n(φ + 3))

Fundamental rectangles at (mφ ‒ n, n(φ + 3))

0 1 1 1 0 0 0 1

5 6 6 6 7 4 5 6

7 5 7 4 3 10 5 7

8 7 3 10 3 8 7 3

9 9 9 9 9 9 9 9

0 0 0 0 0 0 0 0

5 7 5 7 4 5 7 5

2 8 7 3 10 2 6 7

Overlay with unit grid,

read off tile numbers at intersections

Edge colours and the Markov partition

Choices on Markov partition boundary of slope φ²

T_JR Conway worms

​

​

​

​

​

​

​

​

From Labbé, S., Mann, C. and McCloud-Mann, J. (2022) Nonexpansive directions in the Jeandel-Rao Wang shift. Preprint arXiv:2206.02414

T₄ and T₅ on the fundamental rectangle

Tiles from the two sets interleave

This is the start point for Rauzy induction

Overlapping rectangles method (1)

• Start with all M × N patches
• Discard those that cannot be tiled with another rectangle
• For each rectangle a, find neighbours (sets of rectangles {a_NW}, {a_NE}, {a_SE}, {a_SW} offset by one tile such that the grey areas match)

• Discard a if any of {a_NW}, {a_NE}, {a_SE}, {a_SW} are empty

Overlapping rectangles method (2)

• Use the surviving rectangles to build (M+1) × N, M × (N+1) patches, then repeat
• Refinement:

• Discard a if any of the intersecting sets is empty

Overlapping rectangles method (3)

• For some tilesets, many rectangles have unique neighbours, some with unique neighbourhoods of tens of tiles
• This is true of T_X, so we exploit this to build a large patch, choosing rectangles where necessary

​

• Use the surviving rectangles to build (M+1) × N, M × (N+1) patches, then repeat
• For Jeandel-Rao’s 10 tile tileset T_h, no 7 × 7 overlapping rectangles can be built – much easier proof of finiteness than Jeandel and Rao’s

Overlapping rectangles method (4)

Numbers in angle brackets are the number of available rectangles

The patch fails if this is zero anywhere

Numbers without angle brackets are rectangle numbers

T_X tileset and sample patch

Created using about 40000 18 × 20 rectangles

We see white and red regions broadly repeating every 5 or 6 columns

CreatingT_X supertiles

Guess how the columns are divided, and build supertiles with colours corresponding to edges, for example:

Build rectangles using the new tileset, and try to build a large patch

Sample patch using T_X supertiles

Part of an 8000 tile patch using about 70000 27 × 7 rectangles, corresponding to about 45000 T_X tiles

T_X : Deduction of structure

• Number of columns of width 6 / number of columns of width 5 ≈ φ, strongly suggesting similarities to T_JR

​

• Using Labbé’s analysis, we might expect to construct a Markov partition with fundamental rectangle width φ + 4, height φ, lattice offset to be determined (guess ±1)

• The result:

Markov partition for T_X

Fundamental rectangles at (n(φ + 4), mφ ‒ n)

Create tileset T_Y by rotating T_x tiles clockwise 90°

T_Y

T_x

The bijection between T_JR and T_Y

N,S labels

W,E labels

Further thoughts

• From the self-similarility of Labbé’s T_U and Rauzy induction on T_JR , it can be shown that T_JR tilings exist with a bi-infinite row of (tile 0).

• This has two different mappings in T_Y

• There should be a T_X or T_Y analogue of T_JR2 in Jeandel and Rao’s candidate list

T_A tileset and sample

Columns largely of or at intervals of 5 or 7

More complicated structure

Limited runs of repetitions within column separators in groups of 9

Part of a 13800 tile T_A patch

The answer is 42 43

T_A notes (1) (work in progress)

• Needed 1.3 million rectangles to get idea of larger structure

• can only be tiled below by another ,

so are excluded from rectangles

• The sets of a given size are identical

• The pattern 7, 5, 7, 5, 7, 5, 7 is strongly suggested by counting the distinct rows of tiles in each set of columns. Using 7, 5, 7, 5, 7, 5, 7 gives 53, 40, 53, 40, 53, 40, 106, whereas 5, 7, 7, 5, 7, 5, 7 gives 36, 106, 53, 40, 53, 40, 106.

T_A notes (2) (work in progress)

• In a seven tile row, the left hand two tiles are all either

• Next steps: Work on vertical structure

or this sequence