Regular Substitution Systems andTilings in the Hyperbolic Plane
C. Goodman-Strauss

strauss@uark.edu

comp.uark.edu/∼ straussAn advertisement for The Tiling Listserve
Contact:
Casey Mann, University of Texas at Tyler
cmann@uttyler.edu

In the hyperbolic plane (as well as in other settings) we must
distinguish between weakly and strongly aperiodic sets of tiles.
For example, ca. 1977, Penrose noted there are
aperiodic sets of tiles in the hyperbolic plane.

In the hyperbolic plane (as well as in other settings) we must
distinguish between weakly and strongly aperiodic sets of tiles.
For example, ca. 1977, Penrose noted there are
aperiodic sets of tiles in the hyperbolic plane.

In the hyperbolic plane (as well as in other settings) we must
distinguish between weakly and strongly aperiodic sets of tiles.
For example, ca. 1977, Penrose noted there are
weakly aperiodic sets of tiles in the hyperbolic plane.

This tile admits tilings with infinite cyclic symmetry, but none withfinite fundamental domain. The tile is weakly aperiodic.

In the hyperbolic plane, a set of tiles is weakly aperiodic if it does
admit tilings, but admits no tiling with a compact fundamental
domain. On the other hand, it may admit tilings with an infinite
cyclic symmetry.
A set of tiles in strongly aperiodic if it does admit tilings, butadmits no tiling with even an infinite cyclic symmetry.
Though the Domino Problem is tied to weak aperiodicity, somehow
strong aperiodicity seems to be a more significant condition.
And indeed, as we will see, weakly aperiodic sets of tiles arecommonplace.

Given substitution system on letters, we can construct, in fact, aweakly aperiodic set of tiles, based on the induced substitution
tiling of the line:
For example, based on the Morse-Thue substitution system
0 → 01,

1 → 10the horocyclic rows in the tiling correspond to bi-infinite words inthe system. A row is above another exactly when thecorresponding words are related by substitution.

The tilings admitted by these tiles exactly correspond to the orbitsof bi-infinite strings in the substitution system.
Though these tiles do not admit a tiling with compact fundamental
domain, they do admit a tiling invariant under an infinite cyclic
symmetry, since there are periodic orbits in the substitution system.
This pair of tiles is only weakly aperiodic.

We see that every primitive substitution system corresponds to a
weakly aperiodic set of tiles in H 2 in precisely this manner.

0→1
1 → 10√

5+11

We see that every primitive substitution system corresponds to a
weakly aperiodic set of tiles in H 2 in precisely this manner.

0→11 → 2002

We see that every primitive substitution system corresponds to a
weakly aperiodic set of tiles in H 2 in precisely this manner.

0 → 1101 → 101+√2

Note that the well-defined expansion rate of the substitution(arising as the lead eigenvalue of the substitution matrix) induces aparticular curvature on the tiles.

Note that the well-defined expansion rate of the substitution(arising as the lead eigenvalue of the substitution matrix) induces aparticular curvature on the tiles.
Also, as there are uncountably many orbits under the substitution,
there are uncountably many distinct tilings admitted by such tiles.

Note that the well-defined expansion rate of the substitution(arising as the lead eigenvalue of the substitution matrix) induces aparticular curvature on the tiles.
Also, as there are uncountably many orbits under the substitution,
there are uncountably many distinct tilings admitted by such tiles.
However, countably many of these orbits are periodic, andcountably many of the tilings have an infinite cyclic symmetry.
Consequently such tiles are weakly aperiodic.

An amusing phenomenon: If we horizontally shift the tiles of the”fibonacci-squared” substitution:

0 → 101 → 110
we obtain exactly a combinatorially regular tiling of heptagons
meeting three-to-a-vertex.

And so too the regular {7, 3} tiling can be shelled into roughly
horocyclic layers, arranged by the fibonacci-squared substitution
system:(Interestingly, there are uncountably many distinct ways to do this,corresponding to the uncountable set of orbits under in thesubstitution system.
The countably many periodic orbits correspond to the countably
many conjugacy classes of infinite cyclic subgroups of thesymmetry group of the regular tiling.
Does the set of all orbits correspond to the set of points at infinity,modulo the symmetry group?)This basic idea is quite general; a wide range of tilings can bemodeled by substitution sequences. Let’s sketch:Theorem(Poincaré) For any p, q ≥ 3 with p1 + q1 < 12 there is a tiling of H2
by regular p-gons meeting q-to-a-vertex.

At least locally, the construction is more or less trivial. With simple
trigonometry, one can construct a regular p-gon with vertex angles 2π/q,and thus construct an arrangement of q regular p-gons surroundinga single vertex. The question is, how to extend this to a globaltiling. Is it possible something might go wrong?

How to construct a tiling in H2{5,5}letters describe local configurations
XYwords describe configurations along a curve
locally sensible configurations are describedby words in a regular language
X YYXYXYYXYYXY

a relation on words in thisregular language describes
when two strips can fit together.
XY -> XYYXYXYYXYYXY

a bi-infinite orbit under this relation, on the bi-infinite words in the language
corresponds to an abstract complex with the correct local combinatorics.

We began with a local geometric realizationof the desired combinatorial structure.
We simply use this to chart a geometry onto
the complex.

Voila!
(the complex is connected, simplyconnected, unbounded, complete, andconstant curvature: hence a tiled
hyperbolic plane.

This basic technique is very powerful. For example, how can we
discuss the existence of this non-periodic archimedean tiling?

the alphabet, rules and language
a bit of the complex

These rules, and the existence of orbits under the substitution,
ensure that the tiling exists.

the alphabet, rules and language
a bit of the complex

These rules, and the existence of orbits under the substitution,
ensure that the tiling exists.

Danzer posed a curious question: Can the octagons in this tilingbe halved, consistently, to obtain a tiling by pentagons meeting infours?

Can the pentagons in this tiling be fused to obtain a tiling byoctagons meeting in threes?

Can the pentagons in this tiling be fused to obtain a tiling byoctagons meeting in threes?

The difficulty is that a local method can be found, but how canthis be extended globally?

The solution is to find rules that capture the desired combinatorics.

The solution is to find rules that capture the desired combinatorics.
By painting a different geometry on the complex, we obtain thedifferent desired tilings.

The solution is to find rules that capture the desired combinatorics.
By painting a different geometry on the complex, we obtain thedifferent desired tilings.

The solution is to find rules that capture the desired combinatorics.
By painting a different geometry on the complex, we obtain thedifferent desired tilings.

The solution is to find rules that capture the desired combinatorics.
By painting a different geometry on the complex, we obtain thedifferent desired tilings.

Another application: Triangle Tilings. ThmLet T be a triangle in
the hyperbolic plane with vertex angles a, b, c. Suppose there exist
unique integers r , s, t ≥ 0 with ra + sb + tc = 2π. Then T admits
a tiling iff r s t mod 2
This covers some pretty strange triangles! For example, no triangle
satisfying the hypotheses of the theorem admits a tiling with aco-compact symmetry. Those that admit tilings do in fact admit
tilings with an infinite cyclic symmetry however, and are thus
weakly aperiodic!

In particular, among all possible triangles (in S 2 , E 2 and H 2 ) it iseasy to see a measure 1 set do not admit any tiling.
This theorem states that among the rest, a measure 1 set of tiling
triangles are weakly aperiodic!
(The classical Poincaré triangles are only a measure 0 set alltogether.)In particular, among all possible triangles (in S 2 , E 2 and H 2 ) it iseasy to see a measure 1 set do not admit any tiling.
This theorem states that among the rest, a measure 1 set of tiling
triangles are weakly aperiodic!
(The classical Poincaré triangles are only a measure 0 set all
together.)In addition there are some interesting parametrizations:In particular, among all possible triangles (in S 2 , E 2 and H 2 ) it iseasy to see a measure 1 set do not admit any tiling.
This theorem states that among the rest, a measure 1 set of tiling
triangles are weakly aperiodic!
(The classical Poincaré triangles are only a measure 0 set all
together.)In addition there are some interesting parametrizations:In particular, among all possible triangles (in S 2 , E 2 and H 2 ) it iseasy to see a measure 1 set do not admit any tiling.
This theorem states that among the rest, a measure 1 set of tiling
triangles are weakly aperiodic!
(The classical Poincaré triangles are only a measure 0 set all
together.)In addition there are some interesting parametrizations:In particular, among all possible triangles (in S 2 , E 2 and H 2 ) it iseasy to see a measure 1 set do not admit any tiling.
This theorem states that among the rest, a measure 1 set of tiling
triangles are weakly aperiodic!
(The classical Poincaré triangles are only a measure 0 set all
together.)In addition there are some interesting parametrizations:

More generally tilings are far more subtle
In the constructions we just gave, we were able to find a classicalsymbolic substitution system within our construction.
Thus we were able to construct orbits, and indeed periodic orbits.
But in general, there may be no orbits, or there may be orbits butno periodic orbits.

Consider the following example, which more closely models thegeneric nature of tilings:
Consider a language L defined as paths in this graph:102
Now take as rules
0 7→ 12
1 7→ 12 1 7→ 21
2 7→ 01 2 7→ 20

10

20 7→ 12
1 7→ 12 1 7→ 21
2 7→ 01 2 7→ 20

For words w , v ∈ L write w 7→ v iff there is some choice of
replacements of the letters in w yielding v . Note that a given word
may map to no, one, or several other words.
For example:
012120 7→0120 7→1212 7→

1020 7→ 12
1 7→ 12 1 7→ 21
2 7→ 01 2 7→ 20

For words w , v ∈ L write w 7→ v iff there is some choice of
replacements of the letters in w yielding v . Note that a given word
may map to no, one, or several other words.
For example:
012120 7→ 12 12 01 21 20 12, only
0120 7→1212 7→

1
020 7→ 12
1 7→ 12 1 7→ 21
2 7→ 01 2 7→ 20

For words w , v ∈ L write w 7→ v iff there is some choice of
replacements of the letters in w yielding v . Note that a given word
may map to no, one, or several other words.
For example:
012120 7→ 12 12 01 21 20 12, only
0120 7→ nothing
1212 7→

1020 7→ 12
1 7→ 12 1 7→ 21
2 7→ 01 2 7→ 20

For words w , v ∈ L write w 7→ v iff there is some choice of
replacements of the letters in w yielding v . Note that a given word
may map to no, one, or several other words.
For example:
012120 7→ 12 12 01 21 20 12, only
0120 7→ nothing
1212 7→ 12012120, 21201201

As before this relation extends to a relation on the infinite strings
L∞ . Is there an orbit?

As before this relation extends to a relation on the infinite strings
L∞ . Is there an orbit?
(The restriction to a regular language reflects that tiles are subject
to local constraints: what fits with what. The possibility of choicesin the substitution reflects that more than one tile might fit withanother.)A “regular substitution system” (A, L, R) is specified by:a regular language L on an alphabet A; and a relation R, satisfying
certain axioms, on words in this language. The relation extends toa relation on L∞ .
In general, ask, given (A, L, R) are there orbits in L∞ ?
Are there periodic orbits?

Quite unlike the classical symbolic substitution dynamical case,this is quite subtle. Indeed, here is an example of an (A, L, R) for
which there is an orbit, yet there is no periodic orbit:

a, d → gghb, c → hhh

e, f → ggg

g → i, j, k, l, m, s, t, u, v

i, j, k, l, m, w, x, y, z → a, b, e

h → n, o, p, q, r, w, x, y, zn, o, p, q, r, s, t, u, v → c, d, f(This example can also be interpreted as a strongly aperiodic setof tiles in H2 ).

Decidability and regular production systems The existence oftilings admitted by a given set of tiles is equivalent to the existenceof orbits in a corresponding regular production system. Is thisexistence decidable? Is there an algorithmic way to answer whether
a given regular production system has orbits.
Berger’s celebrated result (1966), that the “Domino Problem” isundecidable in the Euclidean plane, can be interpreted as showingthat in fact whether a regular production system has orbits isundecidable, at least for systems with linear growth rates.
The Domino Problem has now been shown to be undecidable in
the hyperbolic plane (Margenstern 2007) (Kari, 2007) These
production systems are thus quite subtle– we cannot decide if they
admit orbits, nor periodic orbits.

Curvature and Production Systems Let us turn the construction
around, and beginning with an arbitrary production system—whichwe assume has orbits—ask whether the system corresponds to atiling with constant (or approximately constant) curvature.
As we saw earlier, symbolic substitution systems have awell-defined asymptotic growth rate. This rate in turn determinesat least something of the geometry of the corresponding tiles.
Roughly, if growth is exponential, we can endow the system with ahyperbolic geometry; if linear, the system is Euclidean; etc. If word
length is wildly erratic, no consistent geometry can be placed on
the system.

Conjecture
Given a regular production system which admits orbits, it isundecidable whether there is an asymptotic rate of growth.

A well-known problem can be interpreted as an example of thisphenomenon.
The Kolakoski sequence consists of 1’s and 2’s, occuring singly
or in pairs, and has the remarkable property that it “reads” its own
structure:
1 22 11 2 1 22 1 22 11 ...

A well-known problem can be interpreted as an example of thisphenomenon.
The Kolakoski sequence consists of 1’s and 2’s, occuring singly
or in pairs, and has the remarkable property that it “reads” its own
structure:
1 22 11 2 1 22 1 22 11 ...

1 2 2 1 1 2 1 2 2It is an well-known open question whether, in the limit, there are
as many 1’s as 2’s.

The construction of the Kolakoski sequence is captured by aparticular regular production system:
2

1
1
1

2
2

1 → 1.

2 → 11.

1 → 2.

2 → 22.
.→Q: Does this system have an asymptotic rate of growth, and if so
is this rate 3/2?