The Mysteries ofAperiodic Tiles

Edmund Harriss, University of Leicester
www.mathematicians.org.uk/eohmaxwelldemon.com@gelada on twitter
Saturday, 26 June 2010

This can tile, periodically...
What about another, acircle...

Saturday, 26 June 2010

Hole that cannot
be filled

This clearly cannot tile,
but maybe we have asimple algorithm...

Saturday, 26 June 2010

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

SET N to 1

Find allPatches withN Tiles

Are therePatches?
Add1To N

Yes

ShapesTile
PeriodicallyYes
PeriodicPatches?
NoSaturday, 26 June 2010

NoShapes
Don’TTile

Saturday, 26 June 2010

Saturday, 26 June 2010

Saturday, 26 June 2010

Saturday, 26 June 2010

Saturday, 26 June 2010

Saturday, 26 June 2010

Saturday, 26 June 2010

What about the third
set...

Saturday, 26 June 2010

Penrose Tiling

Saturday, 26 June 2010

What happens when weapply this to our shapes...

SET N to 1

Find allPatches withN Tiles

Are therePatches?
Add1To NYes

ShapesTile
Periodically

Yes
Periodic
Patches?
No

Saturday, 26 June 2010

NoShapes
Don’TTile

What happens when weapply this to our shapes...

SET N to 1

Find allPatches withN Tiles

Are therePatches?
Add1
To N

Yes

ShapesTile
Periodically

Yes
Periodic
Patches?
NoSaturday, 26 June 2010

NoShapes
Don’T
Tile

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: simple questions about
Robert Berger, The undecidability of the domino problem, tilings will always yield interesting new ideas:

Memoirs of the AMS 66, 1966

Like Aperiodicity...

Raphael Robinson, Undecidability and nonperiodicity for tilings of the plane,
Inventiones Mathematicae 12, 1971, pp. 177-209
Nicolas Ollinger: Tiling the Plane with a Fixed Number of Polyominoes. Proceedings ofLATA 2009, Lecture Notes in Computer Science 5457, Springer 2009, pp.
638-647.

Saturday, 26 June 2010

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

Saturday, 26 June 2010

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

Saturday, 26 June 2010

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

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

Saturday, 26 June 2010

Saturday, 26 June 2010

Saturday, 26 June 2010

Replace
FatThinSaturday, 26 June 2010

ExpandSubstituteSubstitute

Saturday, 26 June 2010

My work has been in creating and attempting
to characterize substitution tilings.
The process of taking a substitution tiling
EG Penrose rhombs
and changing the edges to give a set of aperiodictiles became known as matching rules...
Saturday, 26 June 2010

Raphael Robinson, Undecidability and nonperiodicity 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
A series of papers leading to a result that shows that we can get anaperiodic set of shapes from any substitution tiling...
Q: How?
This is an important result, but not well understood. So now...

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

Saturday, 26 June 2010

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

Saturday, 26 June 2010

We can look at thehierarchy of the tiling.
Every edge ends up withina tileSaturday, 26 June 2010

We can look at thehierarchy of the tiling.
Every edge ends up withina tileSaturday, 26 June 2010

We can look at thehierarchy of the tiling.
Every edge ends up withina tileSaturday, 26 June 2010

We can look at thehierarchy of the tiling.
Every edge ends up withina tileSaturday, 26 June 2010

We can look at thehierarchy of the tiling.
Every edge ends up withina tileSaturday, 26 June 2010

We can look at thehierarchy of the tiling.
Every edge ends up withina tileSaturday, 26 June 2010

Some vertices will end up
at the centre of a tile...
Others at the edge...

Saturday, 26 June 2010

Some vertices will end up
at the centre of a tile...
Others at the edge...

Saturday, 26 June 2010

Some vertices will end up
at the centre of a tile...
Others at the edge...

Saturday, 26 June 2010

We can build a graph toshow the possible roles
that a vertex can take.

Saturday, 26 June 2010

The tiles can be cut up to
give the edges andvertices shape

Saturday, 26 June 2010

The tiles can be cut up to
give the edges andvertices shape

Saturday, 26 June 2010

The tiles can be cut up to
give the edges andvertices shape

Saturday, 26 June 2010

Every Tile knows:
Its tile typeWe want this information on the objects. The
key is edges, they can grow transporting theinformation around the tiling.
NowThe eventual type of it special vertex
Every Edge knows:
Its eventual type
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
Saturday, 26 June 2010

We can start with the tiles. Eachknows its type and the type of its
special vertex.
The edges of the supertile will alsoneed to know the type of the specialvertex, so the information is passed up
to the internal edges.

Saturday, 26 June 2010

Tile special vertext type
Edge TypeSupertile
Type
Saturday, 26 June 2010

Now look at edges. Eachedge has three channels
for the information itcarries. There are also
edges that plug into tiles.

Special vertex
TypeVertex
TypeSaturday, 26 June 2010

EdgeInformation

Information
passed on

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finiteinformation so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

Lets build up a patch of tiling...
Note how the special vertex type iscommunicated up the hierarchy.
Thus each eleemnt can have finite
information so there are a finite
number of tiles...
but...
there are quite a few choices so...

Saturday, 26 June 2010

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 totravel arbitarily far. Something I at least find amazing.
Saturday, 26 June 2010