Aperiodic Tilings
Chaim Goodman-Strauss
Univ Arkansas
strauss@uark.edu

Black and white squares can tile the plane non-periodically, but
can also tile periodically. They are not, then aperiodic.

Aperiodicity would be a truly amazing condition! Somehow, at
all scales, periodicity has to be disrupted.
The mere non-periodicity of a tiling is not particularly special
from this point of view.

Aperiodicity would be a truly amazing condition! Somehow, at
all scales, periodicity has to be disrupted.
The mere non-periodicity of a tiling is not particularly special
from this point of view.
In particular, in the Euclidean plane, a set of tiles is aperiodic if
it admits only non-periodic tilings.

In yesterday’s lecture, we saw that, in a particular setting, saytilings in the Euclidean plane, if the Domino Problem isundecidable, then there must exist an aperiodic set of tiles.
And Robert Berger gave the first such set ca. 1966, as a kind ofscaffold for his proof that the Domino Problem is in fact
undecidable in E2 .
His set of tiles force a particular kind of hierarchical structure in
every tiling they admit, and still today, most known aperiodic
sets of tiles have this property.

Berger’s construction was highly complex; within a few years,
R. Robinson produced a greatly simplified aperiodic set of justsix tiles:

Berger’s construction was highly complex; within a few years,
R. Robinson produced a greatly simplified aperiodic set of justsix tiles: Not only does the set admit non-periodic tilings, it only
does so and is thus aperiodic.

1) Every tile is either a2) Can't have:or incident to

Only:

Hence:

3) So eachis part of:Hence, up to rotation,
every tile is in or next to:4) These 3x3 blocks act like large's& up to rotation,
every tile is in or next toa 7x7 block:& up to rotation, every tile is in or next to a 15x15 block, a 31x31 block, etc...
Consider a tiling by the Robinson tiles. Any translation has a finite magnitude andwill translate some giant block onto itself. But this will not leave the tiling invariant.
Hence every tiling by the Robinson tiles is non-periodic and the tiles themselves
are aperiodic.

Even today, this remains the most common style of proof that a
set of tiles is aperiodic:

Even today, this remains the most common style of proof that a
set of tiles is aperiodic:• Begin with some non-periodic, hierarchical structure

Even today, this remains the most common style of proof that a
set of tiles is aperiodic:• Begin with some non-periodic, hierarchical structure• somehow (magic?) produce tiles

Even today, this remains the most common style of proof that a
set of tiles is aperiodic:• Begin with some non-periodic, hierarchical structure• somehow (magic?) produce tiles• that fit together to form, in effect, larger tiles with the samecombinatorial properties

Even today, this remains the most common style of proof that a
set of tiles is aperiodic:• Begin with some non-periodic, hierarchical structure• somehow (magic?) produce tiles• that fit together to form, in effect, larger tiles with the samecombinatorial properties• giving an inductive proof: Every tile must lie in a uniqueinfinite hierarchy of larger and larger “supertiles"

Even today, this remains the most common style of proof that a
set of tiles is aperiodic:• Begin with some non-periodic, hierarchical structure• somehow (magic?) produce tiles• that fit together to form, in effect, larger tiles with the samecombinatorial properties• giving an inductive proof: Every tile must lie in a uniqueinfinite hierarchy of larger and larger “supertiles"• Thus the tiles do admit a tiling, and only non-periodic tilings.

Other interesting small sets of tiles include:
The Penrose (-Ammann-Conway) tiles (1972-78):

Other interesting small sets of tiles include:
Ammann gave several examples (ca. 1978), including:Other interesting small sets of tiles include:
The trilobite and crab (GS, 1994):

Other interesting small sets of tiles include:
The Penrose (-Socolar-GS) tiles (1994-96):

But each of these is somewhat by magic.
Remarkably, forty-five years after Berger’s construction, very
few aperiodic sets of tiles are known– and only a handful oftechniques for their construction!

Substitutions on tiles give hierarchical tilings:

We substitute, producing larger and large supertiles

Substitutions on tiles give hierarchical tilings:

We substitute, producing larger and large supertiles, andultimately, tilings of the plane.

These substitution tilings are non-periodic but the L-tiles
themselves are not aperiodic. They can tile non-periodically,
but they also admit periodic tilings.

Thus we have globally defined, non-periodic hierarchical tilings

...

and

locallydefinedmatching

ruletilings.

...

and

locallydefinedmatching

ruletilings.

These tiles enforce the hierarchical substitution structure: any∗of the matching rule tilings they admit is locally reducible to a
substitution tiling. And so the tiles are themselves aperiodic.

...

and

locallydefinedmatching

ruletilings.

These tiles enforce the hierarchical substitution structure: any∗of the matching rule tilings they admit is locally reducible to a
substitution tiling. And so the tiles are themselves aperiodic.
The game is: Given a substitution, produce a set of tiles thatenforces it

There are a bewildering array of substitution tilings

There are a bewildering array of substitution tilings

There are a bewildering array of substitution tilingsWhich substitution tilings can be enforced by matching rules?
Is there a general method for their construction?

Theorem (GS, 1998) Every substitution tiling (*) can be
enforced by matching rules.
All the tile sets produced by this theorem are aperiodic.

Theorem (GS, 1998) Every substitution tiling (*) can be
enforced by matching rules.
All the tile sets produced by this theorem are aperiodic.
(*) Our tiles must have well-defined vertices, edges, etc, andthe substitution must be “sibling-vertex-to-vertex" and have“hereditary vertices".

But the result holds:

But the result holds:• in any dimension

But the result holds:• in any dimension• for generalized substitutions

But the result holds:• in any dimension• for generalized substitutions• for fractal tiles

But the result holds:• in any dimension• for generalized substitutions• for fractal tiles• for non-finite local complexity substitutions

But the result holds:• in any dimension• for generalized substitutions• for fractal tiles• for non-finite local complexity substitutions• for non-affine substitutions

But the result holds:• in any dimension• for generalized substitutions• for fractal tiles• for non-finite local complexity substitutions• for non-affine substitutions• even for substitutions with periodic substitution tilings(non-unique hierarchy).

How can we accomplish this? In some manner, this seems
paradoxical:• information must be locally finite (how is the full hierarchy to
be stored/encoded?)• information must be transmitted arbitrarily far (overself-organizing transmission lines!)• and just what is the desired structure anyway??

How can we accomplish this? In some manner, this seems
paradoxical:• information must be locally finite (how is the full hierarchy to
be stored/encoded?)• information must be transmitted arbitrarily far (overself-organizing transmission lines!)• and just what is the desired structure anyway??
The key, of course, is the self-similar nature of the construction.
Each “piece" only needs to know its role in the hierarchy.

That is:a) Each supertile will “know" its type and position relative to its
parent.
bacdThat is:a) Each supertile will “know" its type and position relative to its
parent.
b) The edges of the tiling will be partitioned into “skeletons";
each skeleton holds information for a particular supertile.

That is:a) Each supertile will “know" its type and position relative to its
parent.
b) The edges of the tiling will be partitioned into “skeletons";
each skeleton holds information for a particular supertile.

That is:a) Each supertile will “know" its type and position relative to its
parent.
b) The edges of the tiling will be partitioned into “skeletons";
each skeleton holds information for a particular supertile.
c) The vertices of the tiling will mediate between skeletons ofparent and child.

That is:a) Each supertile will “know" its type and position relative to its
parent.
b) The edges of the tiling will be partitioned into “skeletons";
each skeleton holds information for a particular supertile.
c) The vertices of the tiling will mediate between skeletons ofparent and child.
d) Structures at any scale will be combinatorially the same as
those at any other scale.

We name every bit of structure in the hierarchy we might needto refer to. For example, we give individual names to each edgein the skeletons:

We name every bit of structure in the hierarchy we might needto refer to. For example, we give individual names to each edgein the skeletons:
Our new tiles will thus be individual vertices, edges, and tileinteriors.

Each piece will have a “fantasy" of where it belongs in somesupertile at some level of the hierarchy.
For example, a typical edge tile might fantasize:
I believe I am
somewhere along
this edge of a skeleton,

in some supertile ofthis typeA typical vertex tile might believe:

I believe I am at this position in a skeleton of a supertile of this type. Consequently, I believe that theseedges are respectively the following edges of its skeleton, and that these edges are the following edges of
the children supertiles.

The matching rules are simple: tiles are marked by these
fantasies and neighbors must agree.

We proceed by induction, defining “well-marked supertiles": ourmarked tiles, knowing their position relative to their parent are
well-marked. Assume every 1st level tile lies in a kth level
well-marked supertile. Show it lies in well-marked (k + 1)stlevel supertile:

We proceed by induction, defining “well-marked supertiles": ourmarked tiles, knowing their position relative to their parent are
well-marked. Assume every 1st level tile lies in a kth level
well-marked supertile. Show it lies in well-marked (k + 1)stlevel supertile:

We proceed by induction, defining “well-marked supertiles": ourmarked tiles, knowing their position relative to their parent are
well-marked. Assume every 1st level tile lies in a kth level
well-marked supertile. Show it lies in well-marked (k + 1)stlevel supertile:

We proceed by induction, defining “well-marked supertiles": ourmarked tiles, knowing their position relative to their parent are
well-marked. Assume every 1st level tile lies in a kth level
well-marked supertile. Show it lies in well-marked (k + 1)stlevel supertile:

We proceed by induction, defining “well-marked supertiles": ourmarked tiles, knowing their position relative to their parent are
well-marked. Assume every 1st level tile lies in a kth level
well-marked supertile. Show it lies in well-marked (k + 1)stlevel supertile:

We proceed by induction, defining “well-marked supertiles": ourmarked tiles, knowing their position relative to their parent are
well-marked. Assume every 1st level tile lies in a kth level
well-marked supertile. Show it lies in well-marked (k + 1)stlevel supertile:

We proceed by induction, defining “well-marked supertiles": ourmarked tiles, knowing their position relative to their parent are
well-marked. Assume every 1st level tile lies in a kth level
well-marked supertile. Show it lies in well-marked (k + 1)stlevel supertile:?

This subtlety is handled by one additional set of markings,“vertex wires": successive supertiles fantasize that a particularvertex will lie at a particular point on the skeleton of some giant
supertile:

This subtlety is handled by one additional set of markings,“vertex wires": successive supertiles fantasize that a particularvertex will lie at a particular point on the skeleton of some giant
supertile:

This subtlety is handled by one additional set of markings,“vertex wires": successive supertiles fantasize that a particularvertex will lie at a particular point on the skeleton of some giant
supertile:

This subtlety is handled by one additional set of markings,“vertex wires": successive supertiles fantasize that a particularvertex will lie at a particular point on the skeleton of some giant
supertile:

This subtlety is handled by one additional set of markings,“vertex wires": successive supertiles fantasize that a particularvertex will lie at a particular point on the skeleton of some giant
supertile:

Of course this gives atrocious tile sets!

An Example: The Sphinx

We name the four positions of child within parent (with colors)and orient and name all of the edges.

Each edge contains information about its position within askeleton, the type of the supertile, and, possibly, the supertiles
position in a vertex wire.
(orientation is implicit)
edge typesupertile typevertex wire info

Vertices connect the skeletons of the children to skeletons of
the parents.

The arrangements of markings on the vertices mediate theseconnections.

ensures skeleton isassembled correctly

ensures skeleton
has consistent
information

ensures correct
child, meeting correctly,
at this location

Three different vertex wires are needed; each supertile will lie
in at most one such wire, delivering a “stop" signal to somehigher level skeletal edge.

The full set of tiles

Every 1st level supertile looks like this one.
Combinatorially, the sphinx-like tiles are justlittle supertiles

An Aside: Remarkably, forty-five years after Berger’s
construction, very few aperiodic sets of tiles are known– andonly a handful of techniques for their construction!

An Aside: Remarkably, forty-five years after Berger’s
construction, very few aperiodic sets of tiles are known– andonly a handful of techniques for their construction!
• Berger, Knuth, Läuchli, Robinson, Penrose, Amman, Socolar,
Danzer, Mozes, Radin and GS have each produced tiles that
use the hierarchical structures we will discuss today.

An Aside: Remarkably, forty-five years after Berger’s
construction, very few aperiodic sets of tiles are known– andonly a handful of techniques for their construction!
• Berger, Knuth, Läuchli, Robinson, Penrose, Amman, Socolar,
Danzer, Mozes, Radin and GS have each produced tiles that
use the hierarchical structures we will discuss today.
• In 1981, De Bruin opened another avenue, noting that
Penrose tilings arise via a cut-and-project method; ultimately Le
T.T.Q. gave sharp conditions for the construction of suchaperiodic tiles.

An Aside: Remarkably, forty-five years after Berger’s
construction, very few aperiodic sets of tiles are known– andonly a handful of techniques for their construction!
• Berger, Knuth, Läuchli, Robinson, Penrose, Amman, Socolar,
Danzer, Mozes, Radin and GS have each produced tiles that
use the hierarchical structures we will discuss today.
• In 1981, De Bruin opened another avenue, noting that
Penrose tilings arise via a cut-and-project method; ultimately Le
T.T.Q. gave sharp conditions for the construction of suchaperiodic tiles.
• Kari-Culik and Hanf each gave unique constructions.

An Aside: Remarkably, forty-five years after Berger’s
construction, very few aperiodic sets of tiles are known– andonly a handful of techniques for their construction!
• Berger, Knuth, Läuchli, Robinson, Penrose, Amman, Socolar,
Danzer, Mozes, Radin and GS have each produced tiles that
use the hierarchical structures we will discuss today.
• In 1981, De Bruin opened another avenue, noting that
Penrose tilings arise via a cut-and-project method; ultimately Le
T.T.Q. gave sharp conditions for the construction of suchaperiodic tiles.
• Kari-Culik and Hanf each gave unique constructions.
• And in more exotic settings, Mozes, GS, Margenstern andKari have given some techniques.

An Aside: Remarkably, forty-five years after Berger’s
construction, very few aperiodic sets of tiles are known– andonly a handful of techniques for their construction!
• Berger, Knuth, Läuchli, Robinson, Penrose, Amman, Socolar,
Danzer, Mozes, Radin and GS have each produced tiles that
use the hierarchical structures we will discuss today.
• In 1981, De Bruin opened another avenue, noting that
Penrose tilings arise via a cut-and-project method; ultimately Le
T.T.Q. gave sharp conditions for the construction of suchaperiodic tiles.
• Kari-Culik and Hanf each gave unique constructions.
• And in more exotic settings, Mozes, GS, Margenstern andKari have given some techniques.
But that’s it! Basically— very little is known, still.

An Aside:
Interestingly, the undecidability of the Domino Problem tells usthat our understanding of aperiodic sets of tiles must inherently
be “measure-zero"— given any list of checkable or provableconditions, such as

An Aside:
Interestingly, the undecidability of the Domino Problem tells usthat our understanding of aperiodic sets of tiles must inherently
be “measure-zero"— given any list of checkable or provableconditions, such as“not tiling"An Aside:
Interestingly, the undecidability of the Domino Problem tells usthat our understanding of aperiodic sets of tiles must inherently
be “measure-zero"— given any list of checkable or provableconditions, such as“not tiling"“tiling periodically"An Aside:
Interestingly, the undecidability of the Domino Problem tells usthat our understanding of aperiodic sets of tiles must inherently
be “measure-zero"— given any list of checkable or provableconditions, such as“not tiling"“tiling periodically"“tiling in a hierarchical manner"

An Aside:
Interestingly, the undecidability of the Domino Problem tells usthat our understanding of aperiodic sets of tiles must inherently
be “measure-zero"— given any list of checkable or provableconditions, such as“not tiling"“tiling periodically"“tiling in a hierarchical manner"
there must be infinitely many tile sets that satisfy none of theconditions. So any understanding we have is intrinsically
incomplete.

An Aside:
Interestingly, the undecidability of the Domino Problem tells usthat our understanding of aperiodic sets of tiles must inherently
be “measure-zero"— given any list of checkable or provableconditions, such as“not tiling"“tiling periodically"“tiling in a hierarchical manner"
there must be infinitely many tile sets that satisfy none of theconditions. So any understanding we have is intrinsically
incomplete. What great job security!

An Aside:
As many participants here are fully aware, there is a large andgrowing body of theory constructing and classifying substitution
tilings, in somewhat broader settings. This is a very excitingarea:
Ultimately, will we have a fully complete theory, along thefollowing lines?

An Aside:
As many participants here are fully aware, there is a large andgrowing body of theory constructing and classifying substitution
tilings, in somewhat broader settings. This is a very excitingarea:
Ultimately, will we have a fully complete theory, along thefollowing lines?
A description of the possible combinatorial structures andAn Aside:
As many participants here are fully aware, there is a large andgrowing body of theory constructing and classifying substitution
tilings, in somewhat broader settings. This is a very excitingarea:
Ultimately, will we have a fully complete theory, along thefollowing lines?
A description of the possible combinatorial structures andGiven a combinatorial structure, a description of how to
produce geometric rules.

An Aside:
As many participants here are fully aware, there is a large andgrowing body of theory constructing and classifying substitution
tilings, in somewhat broader settings. This is a very excitingarea:
Ultimately, will we have a fully complete theory, along thefollowing lines?
A description of the possible combinatorial structures andGiven a combinatorial structure, a description of how to
produce geometric rules.
Or could the geometric satisfiability of such a combinatorial
structure be undecidable?
The progress of recent years is extremely encouraging!