Aperiodic
Tiles

Edmund Harriss, Universityof Leicester
www.mathematicians.org.uk/eohMathematics anddisaster relief: The
hexayurt

Vinay Gupta
www.hexayurt.com

This can tile,
periodically...
What about another,a circle...

Hole that cannot
be filled

This clearly cannot
tile, but maybe wehave a simple
algorithm...

Consider what
happens for the tiles
we have...

SET N to 1

Find allPatches with
N Tiles

Are there
Patches?
Add1
To N

No

Shapes
Don’T
Tile

Yes

ShapesTile
Periodically

Yes
Periodic
Patches?
NoWhat about the thirdset...

This will run around the loop forever.
It gets worse. The question is undecidable
Whatever algorithm you find, there is always
a set of shapes that will cause it to run
forever without giving an answer...

SET N to 1

Find allPatches withN Tiles

Are there
Patches?
Add1
To N

No

Shapes
Don’T
Tile

Yes

ShapesTile
PeriodicallyYes
Periodic
Patches?
NoBerger PhD Thesis
Simpler Proof: Robinson
Current state of the art:
5 Tiles Ollinger
This is a reminder of how deep
undeciability cuts into mathematics.
(of course it is also exciting: simplequestions about tilings will always yieldinteresting new ideas:
Like Aperiodicity...

Robert Berger, The undecidability of thedomino problem,
Memoirs of the AMS 66, 1966
Raphael Robinson, Undecidability andnonperiodicity for tilings of the plane,
Inventiones Mathematicae 12, 1971, pp.
177-209
Nicolas Ollinger: Tiling the Plane with a Fixed
Number of Polyominoes. Proceedings of LATA
2009, Lecture Notes in Computer Science
5457, Springer 2009, pp. 638-647.

Joshua Socolar and Joan Taylor,
An aperiodic hexagonal tile,
preprint: arXiv:1003.4279v1
Joan Taylor,
Aperiodicity of a Functional Monotile,
preprint:
www.math.uni-bielefeld.de/sfb701/preprints/sfb10015.pdf

3d version, 1 periodic direction
Mentioned in New Scientist
How can you tell if these shapes tile atall?
The answer is a substitution rule.

Replace
Fat
Thin

ExpandSubstituteSubstituteMy work has been in creating andattempting to characterize substitution
tilings.
The process of taking a substitution tiling
EG Penrose rhombs
and changing the edges to give a set ofaperiodic tiles became known as matchingrules...

A series of papers leading to a result that shows that we
can get an aperiodic set of shapes from any substitution
tiling...
Q: How?
This is an important result, but not well understood. So
now...

Raphael Robinson, Undecidability andnonperiodicity for tilings of the plane,
Inventiones Mathematicae 12, 1971, pp.
177-209
Sharhar Mozes, Tilings, substitution systems
and dynamical systems generated by them, J.
D’Analyse Math. 53, 1989, pp.139-186
Chaim Goodman-Strauss, Matching rules
and substitution tilings,Annals of Mathematics 147 No. 1, 1998, pp.
181-223

Start with the simplest possible substitution
rule...
Label some features:Edges, Vertices, Tiles

We can look at thehierarchy of thetiling.
Every edge ends up
within a tileSome vertices will
end up at the centreof a tile...
Others at the edge...

We can build a graph to show the possibleroles that a vertex can take.

Every Tile knows:
Its tile typeThe eventual type of its special vertex
Every Edge knows:
Its eventual typeWe want this information on theobjects. The key is edges, they can growtransporting the information aroundthe tiling.
Now

What supertile it lies in:
The tile typeThe eventual type of its special vertex
Every Vertex knows
Its eventual type
What edges join it
What supertile it lies in:
The tile typeThe eventual type of its special vertex

The tiles can be cut
up to give the edges
and vertices shapeWe can start with the tiles. Each knows its type and the type of its
special vertex.
The edges of the supertile will also need to know the type of thespecial vertex, so the information is passed up to the internal edges.

Now look at edges. Each edge has threechannels for the information it carries. Thereare also edges that plug into tiles.

Tile special vertext type
Edge TypeSupertileTypeSpecial vertex
TypeVertex
TypeEdgeInformation

Information
passed onLets build up a patch of tiling...
Note how the special vertex type is communicated up the hierarchy.
Thus each eleemnt can have finite information so there are a finite number oftiles...
but...
there are quite a few choices so...

We end up with a lot of tiles!
The nice thing is that the information that travels round is explicit.
All the interactions are local, yet some information is forced to travel
arbitarily far. Something I at least find amazing.