Notes on Tiling Iterated Function Systems

Michael F. Barnsley, Louisa F. Barnsley, and Andrew Vince

Abstract. These notes are background for a lecture at the University of New-
castle, November 2019. They relate to a new and unified theory of self-similar
tilings and iterated function systems.

1. Introduction
These notes are taken from a paper in preparation on the same topic. They
serve for now as background for a new theory of fractal tilings. This theory uses
graph iterated function systems (graph IFS) and centers on underlying symbolic
shift spaces, in a way that hopefully will be made clear in the Newcastle lecture.
The approach provides a zero dimensional representation of the intricate rela-
tionship between shift dynamics on fractals and renormalization dynamics on spaces
of tilings. The ideas I will describe unify, simplify, and substantially extend key
concepts in foundational papers by Solomyak, Anderson and Putnam, and others.
In effect, IFS theory and self-similar tiling theory are unified. These notes and
latter ideas are largely new and have not been submitted for publication.
These notes will be supported by illustrations in preparation.
See [26] for formal background on iterated function systems (IFS). We are
concerned with graph IFS as defined here, but see also [5, 9, 19, 23, 22, 28, 40].

2. Foundations
2.1. Graph iterated function systems. Let F be a finite set of invertible
contraction mappings f : RM → RM each with contraction factor 0 < λ < 1, that
is kf (x) − f (y)k ≤ λ kx − yk for all x, y ∈ RM . We suppose
F = {f1 , f2 , ..., fN } , N > 1
Let G = (E, V) be a strongly connected aperiodic directed graph with edges E and
vertices V with
E = {e1 , e2 , ..., eN } , V = {υ1 , υ2 , ..., υV } , 1 ≤ V < N
G is strongly connected means there is a path, a sequence of consecutive directed
edges, from any vertex to any vertex. G is aperiodic means that if W is the V × V
matrix whose ij th entry is the number of edges directed from vertex j to vertex i,
then there is some power of W whose entries are all strictly positive.
1
2 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

We call (F, G) a graph IFS. The directed graph G provides the orders in
which functions of F may be composed. The sequence of successive directed edges
eσ1 eσ2 · · · eσk is associated with the composite function
fσ1 fσ2 · · · fσk := fσ1 ◦ fσ2 ◦ · · · ◦ fσk
The edges may be referred to by their indices {1, 2, ..., N } and the vertices by
{1, 2, ..., V }.

2.2. Paths in G. Let N be the strictly positive integers and N0 = N ∪ {0}.

For N ∈ N, [N ] := {1, 2, . . . , N }.
Σ is the set of directed paths in G, each with an initial vertex. A path σ ∈ Σ
is written σ = σ1 σ2 · · · corresponding to the sequence of successive directed edges
eσ1 eσ2 · · · in G. The length of σ is |σ| ∈ N0 ∪ {∞} . A metric dΣ on Σ is
dΣ (σ, ω) := 2− min{k∈N:σ̃k 6=ω̃k } for σ 6= ω,
where σ̃k = σk for all k ≤ |σ|, σ̃k = 0 for all k > |σ|. Then (Σ, dΣ ) is a compact
metric space.
The set Σ∗ ⊂ Σ is the directed paths of finite lengths, and Σ∞ ⊂ Σ is the
directed paths of infinite length. For σ ∈ Σ, let σ − ∈ V be the initial vertex and, if
σ ∈ Σ∗ , let σ + ∈ V be the terminal vertex; and for v ∈ V let
Σv := {σ ∈ Σ∞ : σ − = v}
For σ ∈ Σ, k ∈ N,

σ1 σ2 ...σk if |σ| > k
σ|k :=
σ1+ if |σ| ≤ k

fσ1 fσ2 · · · fσk if |σ| > k
fσ|k := , fv := χAv
fσ+ if |σ| ≤ k
1

where I is the identity on RM and χAv is the characteristic function of Av ⊂ RM ,

see Definition 1(iii).
G † = (E † , V) is the graph G modified so that the directions of all edges are
reversed. The superscript † means that the superscripted object relates to G † . For
example, Σ†∗ is the set of directed paths in G † of finite length, Σ†∞ is the set of
directed paths in G † , each of which starts at a vertex and is of infinite length, and
Σ† = Σ†∗ ∪ Σ†∞ . While G is associated with compositions of functions in F, in this
paper G † is associated with compositions of their inverses.

2.3. Addresses and Attractors. Let H be the nonempty compact subsets

of RM and let dH be the Hausdorff metric. Singletons in H are identified with points
in RM .
Definition 1. The attractor A of the graph IFS (F, G), its components
Av , and the address map π : Σ ∪ V →H, are defined as follows.
(i) π(σ) := lim fσ|k (x) for σ ∈ Σ∞ , fixed x ∈ RM
k→∞
(ii) A := π(Σ∞ )
(iii) π(v) := Av := π(Σv ) for all v ∈ V
(iv) π(σ) := fσ (Aσ+ ) for all σ ∈ Σ∗
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 3

Theorem 1. Let (F, G) be a graph IFS.

(1) π : Σ ∪ V →H is well-defined
(2) π : Σ ∪ V →H is continuous
|σ|
T
(3) π(σ) = π(σ|k) for all σ ∈ Σ
k=1
(4) fσ (Aσ+ ) ⊂ Aσ− for all σ ∈ Σ∗
Proof. (1) For all σ ∈ Σ∞ , π(σ) is well-defined by (i), independently of x,
because F is strictly contractive, [26]. It follows that A is well-defined by (ii). Also
it follows that Av and π(v) are well-defined by (iii), for all v ∈ V . In turn, π(σ) is
well-defined for all σ ∈ Σ∗ by Definition 1(iv).
(2) π is continuous because for all σ ∈ Σ∞
dH (π(σ|k), π(σ|l)) ≤ λmin{k,l} max dH (Av , Aw )
v,w

(3) and (4) follow from Definition 1(iv). 

Definition 2. Define σ ∈ Σ∞ to be disjunctive if, given any k ∈ N and
θ ∈ Σ†k , there is p ∈ N so that θ = σp σp+1 ...σp+k .
Likewise, θ ∈ Σ†∞ is disjunctive if, given any k ∈ N and σ ∈ Σk , there is p ∈ N
so that σ = θp θp+1 ...θp+k .
Theorem 2. Let (F, G) be a graph IFS. Let θ ∈ Σ†∞ , x0 ∈ RM , and xn =
fθn (xn−1 ) for all n ∈ N. Then
\ [∞
( xn ) ⊆ A
k∈N n=k

with equality when θ ∈ Σ†∞ is disjunctive.

∞
[
T
Proof. Ω({xn : n ∈ N} ) := ( xn ) is an Ω−limit set. Specifically it is
k∈N n=k
the set of accumulation points of {xn : n ∈ N} in RM . Since π is continuous


Ω ({xn : n ∈ N}) = Ω fθn θn−1 ···θ1 (x0 ) : n ∈ N
= π(Ω ({θn θn−1 · · · θ1 : n ∈ N}))
The Ω−limit set of {θn θn−1 · · · θ1 : n ∈ N} is contained in or equal to Σ∞ , with
equality when θ ∈ Σ†∞ is disjunctive. 
The identity in Theorem 2 underlies the Chaos Game algorithm for calculating
pictures of attractors, see [12].
2.4. Shift maps.
Definition 3. The shift map S : Σ ∪ V → Σ ∪ V is defined by S(σ1 σ2 · · · ) =
σ2 σ3 · · · for all σ ∈ Σ, Sv = v for all v ∈ V, with the conventions
S k σ = σ|k = σ1+ when k ≥ |σ|
Theorem 3. Let (F, G) be a graph IFS.
(1) S : Σ ∪ V → Σ ∪ V is well-defined
(2) S(Σ ∪ V) = Σ ∪ V
(3) S : Σ ∪ V → Σ ∪ V continuous
(4) fσ|k ◦ π ◦ S k (σ) = π (σ) for all σ ∈ Σ, for all k ∈ N0
4 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

Proof. (1) and (2) can be checked.

(3) S is continuous at every point in Σ∗ ∪ V because this subset of Σ ∪ V is
discrete and it is mapped onto itself by S. A calculation using the metric dΣ proves
that S is continuous at every point in Σ∞ .
(4) If σ = σ1 and k = 0 then
fσ|k ◦ π ◦ S k (σ) = χAσ+ ◦ π σ1+ = χAσ+ (Aσ+ ) = π (σ1 )


1 1 1

If σ = σ1 and k = 1, then
fσ|k ◦ π ◦ S k (σ) = fσ1 ◦ π σ1+ = fσ1 (Aσ+ ) = π (σ1 )


1

If σ ∈ Σ∞ and k ∈ N, then
fσ|k ◦ π ◦ S k (σ) = fσ1 σ2 ···σk (π(σk+1 σk+2 · · · ))
= fσ1 σ2 ···σk ( lim π(σk+1 σk+2 · · · σm ))
m→∞
= lim π(σ1 σ2 · · · σm ) = π(σ)
m→∞

The remaining cases follow similarly. 

2.5. Disjunctive orbits, ergodicity, subshifts of finite type. Let T =
S|Σ∞ . The dynamical system T : Σ∞ → Σ∞ is chaotic in the purely topological
sense of Devaney [24]: it has a dense set of periodic points, it is sensitively depen-
dent on initial conditions, and it is topologically transitive. Topologically transitive
means that if Q and R are open subsets of Σ∞ , then there is K ∈ N so that
Q ∩ T K R 6= ∅
This is true because the set of disjunctive points in Σ∞ is dense in Σ∞ and the
orbit under T of a disjunctive point passes arbitrarily close to any given point in
Σ∞ .
However, T : Σ∞ → Σ∞ also possesses many invariant normalized Borel mea-
sures, each having support Σ∞ and such that T is ergodic with respect to each. An
example of such a measure µP may be constructed by defining P a Markov process
on Σ∞ using G and probabilities P = {pe > 0 : e ∈ E} where pd = 1 for all
d+ =e+
d∈E
e ∈ E. Then µP is the unique normalized measure on the Borel subsets B of Σ∞
such that X
µP (b) = pe µP (eb ∩ Σ∞ ) for all b ∈ B
e∈E
where eb := {σ ∈ Σ∞ : σ1 = e, Sσ ∈ b}. In particular, µP is invariant under T,
that is
µP (b) = µP (T −1 b) for all b ∈ B
The key point (1) in Theorem 4 is well known: T is ergodic with respect to µ.
That is, if T b = T −1 b for some b ∈ B, then either µP (b) = 0 or µP (b) = 1. As a
consequence, the set of disjunctive points has full measure, independent of P.
Theorem 4. Let (F, G) be a graph IFS. Let (Σ∞ , B, T, µP ) be the dynamical
system described above. Let D be the disjunctive points in Σ∞ . Then
(1) Parry [30] (Σ∞ , B, T, µP ) is ergodic
(2) D = T D = T −1 D ∈ B
(3) µP (D) = 1, and µP (Σ∞ \D) = 0
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 5

Proof. (1) This is a standard result in ergodic theory, see for example [30].
(2) It is readily checked that D ∈ B and that T −1 D = D = T D.
(3) Since (Σ∞ , B, T, µ) is ergodic and D = T −1 D, it follows that µ (D) ∈ {0, 1} .
Also we have
1 = µ (Σ∞ ) = µ (D) + µ (Σ∞ \D)
So either µ (D) = 1 and µ (Σ∞ \D) = 0 or vice-versa. Now notice that
[
Σ∞ \D ⊂ Dx
x∈Σ∗ \∅

where Dx = {σ ∈ Σ∞ : S n σ ∈
/ c[x]∀n ∈ N0 } where c[x] is the cylinder set
c[x] := {z ∈ Σ∞ : z = xy, y ∈ Σ∞ } .
In particular
X
µ (Σ∞ \D) ≤ µ(Dx )
x∈Σ∗

But µ(Dx ) = 0 as proved next, so µ (Σ∞ \D) = 0.

Proof that µ(Dx ) = 0: Let f : Σ∞ → R be defined by f (σ) = 0 if σ ∈ c[x] and
f (σ) = 1 if σ ∈ Σ∞ \c[x]. Since f ∈ L1 (µ), by the ergodic theorem we have
Z n−1
1X
f dµ = lim f (T k σ) for µ-almost all σ ∈ Σ∞ .
n→∞ n
Σ∞ k=0
R
But f dµ = 1 − µ(c[x]) > 0 because the support of µ is Σ∞ , and Σ∞ contains a
cylinder set disjoint from c[x] because |E| ≥ 2, and all cylinder sets have strictly
positive measure. Also f (T k σ) = 0 for all x ∈ Dx so
n−1
1X
lim f (T k σ) = 0 for all x ∈ Dx
n→∞ n
k=0

n−1
1
f (T k σ) for all x ∈ Dx , so µ(Dx ) = 0.
R P
so f dµ 6= limn→∞ n 
Σ∞ k=0

3. Tilings
3.1. Similitudes. A similitude is an affine transformation f : RM → RM of
the form f (x) = λ O(x)+q, where O is an orthogonal transformation and q ∈ RM is
the translational part of f (x). The real number λ > 0, a measure of the expansion or
contraction of the similitude, is called its scaling ratio. An isometry is a similitude
of unit scaling ratio and we say that two sets are isometric if they are related by
an isometry.

3.2. Tiling iterated function systems.

Definition 4. The graph IFS (F, G) is said to obey the open set condition
(OSC) if there are non-empty bounded open sets {Ov : v ∈ V} such that for all
d, e ∈ E we have fe (Oe+ ) ⊂ Oe− and fe (Oe+ ) ∩ fd (Od+ ) = ∅ whenever e− = d− .
The OSC for graph IFS is discussed in [10] and [22].
6 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

Definition 5. Let F = {RM ; f1 , f2 , · · · , fN }, with N ≥ 2, be an IFS of

contractive similitudes where the scaling factor of fn is λn = san where an ∈ N and
gcd{a1 , a2 , · · · , aN } = 1. Let the graph IFS (F, G) obeys the OSC. Let
(3.1) Av ∩ Aw = ∅
for all v 6= w, and let Av span RM . Then (F, G) is called a tiling iterated
function system (tiling IFS).
The requirement Av ∩ Aw = ∅ whenever v 6= w is without loss of generality
in the following sense. By means of changes of coordinates applied to some of the
maps of the IFS, we can move Av to Tυ Av , where Tυ : RM → RM is a translation,
while holding Aw fixed for all w 6= v. To do this, let
Tv fe Tv−1 if e+ = v and e− = v


if e+ 6= v and e− = v

Tv fe

fee = −1
 fe Tυ if e+ = v and e− 6= v
if e+ 6= v and e− 6= v

fe

n o
and let Fe = {fe : e ∈ E}. Then the components of the attractor of F, e G are
Aew = Aw for w 6= v and A ev = Tv Av . By repeating this process for each vertex,
we can modify the IFS so that different components of the attractor have empty
intersections. Only the relative positions of the components are changed, while their
geometries are unaltered, and (3.1) holds. This being the case, the OSC is simply
”there are non-empty open sets {Ov : v ∈ V} such that fe (Oe+ ) ∩ fd (Od+ ) = ∅ for
all d, e ∈ V with d 6= e”.
Definition 6. The critical set of the tiling IFS (F, G) is
[
C:= fd (Ad+ ) ∩ fe (Ae+ )
d6=e
d,e∈E

The following theorem tells us that the critical set of a tiling IFS is small, both
topologically and measure theoretically, compared to the attractor.
Theorem 5. Let (F, G) be a tiling IFS, let C be the critical set and let D be
the disjunctive points in Σ∞ .
(1)Mauldin & Williams [28] and Bedford [18] The Hausdorff dimension
DH (A) of the attractor A of (F, G) is the unique t ∈ [0, M ] such that the spectral
radius of the matrix X
Ww,v (t) = stae
{e∈E:e+ =v,e− =w}

equals one. Also 0 < µH (A) < ∞ where µH is, up to a strictly positive constant
factor, the Hausdorff measure on A.
(2) C ⊂ π(Σ∞ \D)
(3) C∩A◦ = ∅ where A◦ is the interior of A
(4) µPP (π −1 (C)) = 0 for all P.
(5) If Ww,v (t) = 1 then µH = µP ◦π −1 where µP is the stationary measure on
v
Σ∞ obtained when pe = sDH (A)ae in the Markov process described before Theorem
4. In this case
µH (C) =0
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 7

Proof. (1) To apply [28] there must be exactly one edge of G incoming to
each vertex, but this can always be contrived, without changing the dimension, (or
the geometries of the components of the attractor,) as we describe here. If v ∈ V

1 > 1, then introduce new vertices v (1) , v (2) , ..., v (d) and new
P
is such that d =
d+ =v
d∈E
components of the attractor Av(1) = Av(2) = ... = Av(d) = Av , and replace the d
incoming edges to v, by one incoming edge to each of the new vertices, and one
outgoing map from each of the new components of the attractor. Then translate the
coincident attractors so that they have empty intersections and modify the maps
accordingly, as above, and introducing additional maps (related to the original ones
by changes of coordinates but with the same scaling rations). This ensure that there
is exactly one inward pointing edge at each vertex of G. This reduces the present
situation to that in [28], who makes this assumption. Clearly the dimension of the
attractor is unaltered.
We also have 0 < µH (A) < ∞ by [28, Theorem 3]. Note that [28, Theorem
3] requires a different separation condition than the OSC, but both [10, Theorem
2.1] and [22] refer to [28, Theorem 3] as though the two conditions are equivalent,
and we have assumed that this is true.
(2) This is the generalization to the graph-directed case of the definitions and
argument in [7, Proposition 2.2]. We need the dynamical boundary ∂A of the
attractor A of (F, G), namely
∞
[
∂A := F|−n
G (C)∩A
n=1

F|−n fσ−1 fσ−1 ...fσ−1

S
where G (C) = 1 2 n
(C∩Aσn− ). We present the proof in parts (a) and
σ∈G
(b) for the case V = 1. The arguments are assumed to carry over to the tiling IFS
case. S
(a) The OSC implies, for similitudes, the open set O = Ov can be chosen
v∈V
so that O ∩ A 6= ∅ [35], which implies A\∂A 6= ∅ because in this case O∩∂A = ∅
by [29, Theorem 2.3 via (iii) implies (i) implies (ii)].
(b) A\∂A 6= ∅ implies ∂A ∩ π(D) = ∅ because if x = π(σ) ∈ C with σ ∈ D
then ∂A = A as in [7, Proposition 2.2] Prop 2.2. It follows that C ⊂ π(Σ∞ \D).
(3) This is [7, Proposition 2.1] carried over to the tiling IFS case, using the
non-overlappingness of A, namely A\∂A 6= ∅.
(4) We have
µA (C) ≤ µA (π(Σ∞ \D)) by (2)
= µH (π −1 π(Σ∞ \D)) since µA = µH ◦ π −1
= µH (Σ∞ \D) = 0 by Theorem 4 (3)
(5) Using the thermodynamic formalism [18, **find exact reference or use
MAGIC01] and the assumption that Ww,v (t) = 1 , we find that µH = µP ◦ π −1
P
v
is, up to a positive multiplicative constant, the Hausdorff measure obtained when
X
pe = sDH (A)ae / sDH (A)ad
d+ =e+
8 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE


3.3. Tilings in this paper. According to Grunbaum and Sheppard [25] a
tiling is a partition of R2 by closed sets. Here we consider tilings of subsets of
RM such as fractal blow-ups where tiles are components of attractors of IFSs. In
this case tiles may have empty interiors and the question of what it means for
tiles to be non-overlapping has to be answered. Here we simply say that two tiles
t1 and t2 that belong to a tiling are non-overlapping if their intersection is small
both topologically and measure theoretrically, relative to the tiles themselves. This
matches the customary situation: in a tiling of R2 such as a partition into triangles,
tiles have positive two-dimensional Lebesgue measure, intersections of distinct tiles
have zero two-dimensional Lebesgue measure, and are subsets of their topological
boundaries.

3.4. The tiling map. Define subsets of Σ∗ as follows:

Ωk = {σ ∈ Σ∗ : ξ − (σ) ≤ k < ξ(σ)}, Ω0 = [N ]
Ωvk = {σ ∈ Ωk : σ − = v}, Ωv0 = {σ1 ∈ [N ] : σ1− = v}
for all k ∈ N, v ∈ V. Here ξ : Σ∗ → N0 is defined for all σ ∈ Σ∗ by
|σ| |σ|−1
X X
−
ξ(σ) = aσk , ξ (σ) = aσk , ξ(∅) = ξ − (∅) = 0
k=1 k=1

Tilings are associated with θ ∈ Σ† . Edges in Σ† are directed oppositely to those

in Σ. For all θ ∈ Σ† , k ∈ N, k ≤ |θ|,
θ|k := θ1 θ2 · · · θk , θ|0 := θ1−
f−θ|k := fθ−1
1
fθ−1
2
· · · fθ−1
k
−1
, f∅ := I
M
Definition 7. The tiling map Π from Σ† to collections of subsets of H(R )
defined as follows. For θ ∈ Σ†∗ ,
 +   −
Π(θ) = f−θ π Ωθξ(θ) , Π(θ|0) = π Ωθ0

and for θ ∈ Σ†∞ ,

[
Π(θ) = Π(θ|k)
k∈N
+
θ
For σ ∈ Ωξ(θ) and θ ∈ Σ† , the set f−θ π (σ) is called a tile and Π(θ) is called a
tiling. The support of the tiling Π(θ) is the union of its tiles, and Π(θ) is said to
tile its support.
Theorem 6. Let (F, G) be a tiling IFS.
(1) For all θ ∈ Σ†∞ , if t1 , t2 ∈ Π(θ) with t1 6= t2 , then t1 ∩ t2 is small both
topologically and measure theoretically, compared to t1 . That is, µP (t1 ∩
t2 ) = 0 and t◦1 ∩ t2 = ∅ where t◦ is the interior of t.
∞
(2) For all θ ∈ Σ†∞ the sequence of tilings {Π(θ|k)}k=1 obeys
(3.2) Π(θ|0) ⊂ Π(θ|1) ⊂ Π(θ|2) ⊂ · · ·
(3) Π(θ) is a tiling of a subset of RM that is bounded when θ ∈ Σ†∗ and
unbounded when θ ∈ Σ†∞ .
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 9

(4) For all θ ∈ Σ†∞

(3.3) Π(θ) = lim f−θ|k ({π (σ) : σ ∈ Ωξ(θ|k) , σ − = θ+ })
k→∞

(5) Any tile t ∈ Π(θ) can be written t = si U Av for some isometry U ∈ U,

i ∈ {1, 2, ..., max ae } and v ∈ V.

 Proof.
 (1) Π(θ|0) is a tiling in the sense described in Section 3.3. Π(θ|0) =
−
π Ωθ0 = π ({e ∈ [N ] : e− = θ− }) = {fe (Ae+ ) : e− = θ− } has support Ae− and
its tiles are supposed to be {fe (Ae+ ) : e− = θ− }. We need to check (i) that they are
components of attractors of tiling IFSs and (ii) that their intersections are relatively
small. (i) is true because for each e ∈ [N ], the set fe (Ae+ ) is a component of the
attractor of the tiling IFS (fe Ffe−1 , G). (ii) This follows from Theorem 5 parts (3)
and (4).
Similarly, Π(θ|k) and Π(θ) are tilings as in Section 3.3: the tiles are components
of attractors of appropriately shifted versions of the original tiling IFS and their
intersections are isometric to subsets of the critical set of the original tiling IFS.
(2) The proof is algebraic, idependent of topology, essentially the same as for
the case where Av has nonempty interior [17], and similar to the case where V = 1
[16]. Briefly,
Π(θ|k + 1) = {fθ−1
1
...fθ−1
k+1
fσ1 ..fσ|σ| (Aσ+ ) : ξ(σ1 ..σ|σ|−1 ) ≤ ξ(θ1 ..θ|σ| ) < ξ(σ1 ..σ|σ| )}
|σ|

⊃ {fθ−1
1
...fθ−1
k
fσ2 ..fσ|σ| (Aσ+ ) : ξ(σ2 ..σ|σ|−1 ) ≤ ξ(θ2 ..θ|σ| ) < ξ(σ2 ..σ|σ| )}
|σ|

= {fθ−1
1
...fθ−1
k
fσ1 ..fσ|σ|−1 (Aσ+ ) : ξ(σ1 ..σ|σ|−2 ) ≤ ξ(θ1 ..θ|σ|−1 ) < ξ(σ1 ..σ|σ|−1 )}
|σ|−1

= Π(θ|k)
 + 
(3) For θ ∈ Σ†∗ , Π(θ) = f−θ π Ωθξ(θ) so the support of Π(θ) is f−θ ( {π(σ) :
S
+ −ξ(θ)
σ ∈ Ωθξ(θ) ) = f−θ Aθ+ . Here f−θ is a similitude of expansion factor |s| which
diverges with |θ| , and Aθ+ spans RM .
(4) This follows from (3).
(5) For t ∈ Π(θ) we have t = f−(θ|k) fσ (Av ) for some k, θ, σ and v, with
ξ − (σ) ≤ ξ(θ|k) < ξ(σ). Here f−(θ|k) fσ = s−m U where m = ξ(θ|k) − ξ(σ) is an
integer that lies between 1 and max ae and U ∈ U is an isometry of the form
sm f−(θ|k) fσ for some m. 

4. Continuity properties of Π : Σ† → T.
4.1. A convenient compact tiling space. Let
T = Π(θ) : θ ∈ Σ†


Let ρ : RM → SM be the usual M -dimensional stereographic projection to the

M
M -sphere, obtained by positioning SM tangent to RM at the origin. Let H(S )
M M
be the non-empty closed (w.r.t. the usual topology on S ) subsets of S . Let
dH(SM ) be the Hausdorff distance with respect to the round metric on SM , so that
M M
(H(S ), dH(SM ) ) is a compact metric space. Let H(H(S )) be the nonempty com-
M
pact subsets of (H(S ), dH(SM ) ), and let dH(H(SM )) be the associated Hausdorff
10 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

M
metric. Then (H(H(S )), dH(H(SM )) ) is a compact metric space. Finally, define a
metric dT on T by
dT (T1 , T2 ) = dH(H(SM )) (ρ (T1 ) , ρ (T2 ))
for all T1 , T2 ∈ T.
Theorem 7. (T, dT ) is a compact metric space.
Proof. Straightfoward and omitted. 

See also for example [1, 20, 34, 36, 39] where related metrics and topologies
are defined.

4.2. Continuity. The following definition generalizes a related concept for

the case where A is a topological disk and |V| = 1, see [14]. For θ ∈ Σ†∞ define
I(θ) ⊂ Σ∞ to be the set of limit points of {θl+m θl+m−1 ...θm+1 : l, m ∈ N}. Define
Hv = ∪{fσ−1 fω (Av ) : π(σ), π(ω) ∈ Av , σ, ω ∈ Σ, σ1 6= ω1 }.
This is the union of all images of Av under its neighbor maps and is a generalization
of the same definition in the case V = 1, [2, 3, 4]. Define the central open sets to
be
Ov = {x ∈ RM : d(x, Av ) < d(x, Hv )}
It appears that ”(F, G) obeys the OSC” if and only if ”Av is not contained in Hv
for all v ∈ V ”, see [2, 3, 4].
Call θ ∈ Σ†∞ reversible if
Σ†rev := I(θ) ∩ {σ ∈ Σ∞ : π(σ) ⊂ ∪v Ov } =
6 ∅.
Equivalently, θ ∈ Σ†rev if the following holds: there exists σ ∈ Σ∞ with π(σ) ∈ ∪v Ov
such that, for all L, M ∈ N there is m ≥ M so that
σ1 σ2 ...σL = θm+L θm+L−1 ...θ1
Equivalently, in terms of the notion of ”full” words, see [14], θ ∈ Σ†rev if there
is a nonempty compact set A0 ⊂ ∪v Ov such that for any positive integer M there
exists n > m ≥ M so that
fθn fθn−1 ...fθm+1 (Aθ+ ) ⊂ A0 .
m+1

Theorem 8. Let (F, G) be a tiling IFS. Then

Π|Σ†rev : Σ†rev ⊂ Σ†∞ → T
is continuous and
Π : Σ†∞ → T
is upper semi-continuous in this sense: if Π(θ(n) ) is a sequence of tilings that con-
verges to a tiling T ∈ T as θ(n) converges to θ ∈ Σ†∞ , then Π(θ) ⊂ T .
Proof. Proof of upper semi-continuity: let {θ(n) } be a sequence of points
in Σ†∞ that converges to θ and such that lim Π(θ(n) ) = T with respect to the
tiling metric. Let m be given. Then there is lm so that for all n ≥ lm we have
θ|m = θ(n) |m and hence Π(θ|m) = Π(θ(n) |m) ⊂ Π(θ(n) ). Hence we have Π(θ|m) ⊂
lim Π(θ(n) ) and hence, since this is true for all m, Π(θ) ⊂ lim Π(θ(n) ).
n→∞ n→∞
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 11

Proof that Π|Σ†rev : Σ†rev → T is continuous involves blow-ups of central opens

sets. Analogously to the definition of Π, define a mapping Ξ from Σ† into to
collections of subsets of H(R ) as follows. For θ ∈ Σ†∗ , θ 6= ∅,
M

Ξ(θ1 θ2 ...θk ) := {f−θ1 θ2 ...θk fσ (Oσ+ ) : σ ∈ Ωξ(θ1 θ2 ...θk ) , θk− = σ1− },

and for θ ∈ Σ†∞
[
Ξ(θ) := Ξ(θ|k).
k∈N
As is the case for Π, increasing families of sets are obtained: each collection Ξ(θ)
comprises a covering by compact sets of a subset of RM , the subset being bounded
when θ ∈ Σ†∗ and unbounded when θ ∈ Σ†∞ . For all θ ∈ Σ†∞ the sequence of sets
∞
{Ξ(θ|k)}k=1 is nested according to
Ξ(θ|1) ⊂ Ξ(θ|2) ⊂ Ξ(θ|3) ⊂ · · · .
and we have {Ξ(θ|k)} converges to Ξ(θ) in the metric introduced in Section 4.1.
In particular, when reversible, the new tiles, those in Ξ(θ|k + 1) that are not in
Ξ(θ|k), are located further and further away from the origin as k increases. The
result follows. 

5. Symbolic structure : canonical symbolic tilings and symbolic

inflation and deflation
(v) (v)
Write Ωk to mean any of Ωvk or Ωk . The following lemma tells us that Ωk+1
(v)
can be obtained from Ωk
by adding symbols to the right-hand end of some strings
(v)
in Ωk and leaving the other strings unaltered.
Lemma 1. (Symbolic Splitting) For all k ∈ N and v ∈ V the following
relations hold:
n o n o
(v) (v) (v) (v)
Ωk+1 = σ ∈ Ωk : k + 1 < ξ (σ) ∪ σj ∈ Σ∗ : σ ∈ Ωk , k + 1 = ξ (σ) .
(v)
Proof. Follows at once from definition of Ωk . 
(v)
(v)
Define αs−1 : Ωk → 2Ωk+1 by
αs−1 σ = σ if k + 1 < ξ(σ)
αs−1 σ = {σe : σ|σ|
+
= e− , e ∈ E} if k + 1 = ξ(σ)
Then
αs−1 (Ωvk ) = Ωvk+1
(v)
This defines symbolic inflation or ”splitting and expansion” of Ωk , some words in
(v) (v)
Ωk+1 being the same as in Ωk while all the others are split. The inverse operation
is symbolic deflation or ”amalgamation and shrinking”, described by a function
(v) (v) (v) (v)
αs : Ωk+1 → Ωk , αs (Ωk+1 ) = Ωk
(v)
where αs (σ) is the unique ω ∈ Ωk such that σ = ωβ for some β ∈ Σ∗ . Note that
β may be the empty string.
(v) (v) (v)
We can use Ωk to define a partition of Ωm for m ≥ k. The partition of Ωk+j
(v)
is Ωk+j / ∼ where x ∼ y if αsj (x) = αsj (y).
12 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

(v)
Corollary 1. (Symbolic Partitions) For all m ≥ k ≥ 0, the set Ωk defines
(v) (v) (v)
a partition Pm,k of Ωm according to p ∈ Pm,k if and only if there is ω ∈ Σ∗ such
that
(v)
p = {ωβ ∈ Ω(v)
m : β ∈ Ωk }.
(v) (v)
Proof. This follows from Lemma 1: for any θ ∈ Ωm there is a unique ω ∈ Ωk
(v)
such that θ = ωβ for some β ∈ Σ∗ . Each word in Ωm is associated with a unique
(v) (v) (v)
word in Ωk . Each word in Ωk is associated with a set of words in Ωm . 
(v)
According to Lemma 1, Ωk+1 may be calculated by tacking words (some of
(v)
which may be empty) onto the right-hand end of the words in Ωk . We can invert
(v) (v)
this description by expressing Ωk as a union of predecessors (Ωj s with j < k) of
(v)
Ωk with words tacked onto their other ends, that is, their left-hand ends.
Corollary 2. (Symbolic Predecessors) For all k ≥ amax + l, for all v ∈ V,
for all l ∈ N0 ,
(v)
G +
Ωk = ωΩωk−ξ(ω)
(v)
ω∈Ωl

Proof. It is easy to check that the r.h.s. is contained in the l.h.s.

(v) (v)
Conversely, if σ ∈ Ωk then there is unique ω ∈ Ωl such that σ = ωβ for
some β ∈ Σ∗ by Corollary 1. Because ωβ ∈ Σ∗ it follows that β1 is an edge that
starts where the last edge in ω is directed, namely the vertex ω + . Finally, since
+
ξ (ωβ) = ξ (ω) + ξ(β) it follows that β ∈ Ωω
k−ξ(ω) . 

6. Canonical tilings and their relationship to Π(θ)

Definition 8. We define the canonical tilings of the tiling IFS (F, G) to be
Tk = s−k π(Ωk ), Tkv := s−k π(Ωvk )
k ∈ N, v ∈ V.
A canonical tiling may be written as a disjoint union of isometries applied of
other canonical tilings as described in Lemma 2.
Lemma 2. For all k ≥ amax + l, for all l ∈ N0 , for all v ∈ V
ω+ ω+
G G
Tkv = Ek,ω Tk−ξ(ω) and Tk = Ek,ω Tk−ξ(ω)
ω∈Ωv
l ω∈Ωl

where Ek,ω = s−k fω sk−ξ(ω) ∈ U is an isometry.

Proof. Direct calculation using Corollary 2. 
Theorem 9. For all θ ∈ Σ†∗ ,
|θ|
θ−
Π(θ) = Eθ Tξ(θ) ,
where Eθ = f−θ sξ(θ) . Also if l ∈ N0 , and ξ(θ) ≥ amax + l, then
+
G ω|ω|
Π(θ) = Eθ,ω Tξ(θ)−ξ(ω)
+
ω∈Ωθl

where Eθ,ω = f−θ fω sξ(θ)−ξ(ω) is an isometry.

 NOTES ON TILING ITERATED FUNCTION SYSTEMS 13

Proof. Writing θ = θ1 θ2 ...θk so that |θ| = k, we have from the definitions

θ−
Π(θ1 θ2 ...θk ) = f−θ1 θ2 ...θk {π (σ) : σ ∈ Ωξ(θ
k
1 θ2 ...θk )
}
θ−
= f−θ1 θ2 ...θk sξ(θ1 θ2 ...θk ) s−ξ(θ1 θ2 ...θk ) {π(σ) : σ ∈ Ωξ(θ
k
1 θ2 ...θk )
}
θ−
= Eθ1 θ2 ...θk Tξ(θ
k
1 θ2 ...θk )

θ−
|θ|
which demonstrates that Π(θ) = Eθ Tξ(θ) where Eθ = f−θ sξ(θ) .
The last statement of the theorem follows similarly from Lemma 2. 

7. All tilings in T∞ are quasiperiodic

We recall from [16] the following definitions. A subset P of a tiling T is called
a patch of T if it is contained in a ball of finite radius. A tiling T is quasiperiodic
if, for any patch P , there is a number R > 0 such that any disk centered at a point
in the support of T and is of radius R contains an isometric copy of P . Two tilings
are locally isomorphic if any patch in either tiling also appears in the other tiling.
A tiling T is self-similar if there is a similitude ψ such that ψ(t) is a union of tiles
in T for all t ∈ T . Such a map ψ is called a self-similarity.
Theorem 10. Let (F, G) be a tiling IFS.
(1) Each tiling in T∞ is quasiperiodic.
(2) If (F, G) is coprime, then each pair of tilings in T∞ are locally isomorphic.
(3) If θ ∈ Σ†∞ is eventually periodic, then Π(θ) is self-similar. In fact, if
−1
θ = αβ for some α, β ∈ Σ†∗ then f−α f−β (f−α ) Π(θ) is a self-similarity.
Proof. This uses Theorem 9, and follows similar lines to [16, proof of Theorem
2]. 

8. Addresses
Addresses, both relative and absolute, are described in [16] for the case |V| = 1.
See also [6]. Here we add information and generalize. The relationship between
these two types of addresses is subtle and used in the proof of later Theorems.
(v)
8.1. Relative addresses. Write Tk to mean any of Tkv or Tk .
(v)
Definition 9. The relative address of t ∈ Tk is defined to be ∅.π −1 sk (t) ∈
(v)
∅.Ωk . The relative address of a tile t ∈ Tk depends on its context, its location
relative to Tk , and depends in particular on k ∈ N0 . Relative addresses also apply
θ−
to the tiles of Π(θ) for each θ ∈ Σ†∗ because Π(θ) = Eθ Tξ(θ)|θ|
where Eθ = f−θ sξ(θ)
(by Theorem 9) is a known isometry applied to Tξ(θ) . Thus, the relative address of
−1
t ∈ Π(θ) (relative to Π(θ)) is ∅.π −1 f−θ (t), for θ ∈ Σ†∗ .
Lemma 3. The tiles of Tk are in bijective correspondence with the set of relative
addresses ∅.Ωk . The tiles of Tkv are in bijective correspondence with the set of
relative addresses ∅.Ωvk .
Proof. We have Tk = s−k π(Ωk ) so s−k π maps Ωk onto Tk . Also the map
−k
s π : Ωk → Tk is one-to-one: if β 6= γ, for β, γ ∈ Σ∗ then fβ (A) 6= fγ (A) because
t = s−k π(β) = s−k π(γ)with β, γ ∈ Tk implies β = γ. 
14 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

For precision we should write ”the relative address of t relative to Tk ” or equiv-

alent: however, when the context t ∈ Tk is clear, we may simply refer to ”the
relative address of t”.
Example 1. (Standard 1D binary tiling) For the IFS F0 = {R; f1 , f2 } with
f1 (x) = 0.5x, f2 (x) = 0.5x + 0.5 we have Π(θ) for θ ∈ Σ†∗ is a tiling by copies of the
tile t = [0, 0.5] whose union is an interval of length 2|θ| and is isometric to T|θ| and
represented by tttt....t with relative addresses in order from left to right
∅.111...11, ∅.111...12, ∅.111...21, ...., ∅.222...22,
the length of each string (address) being |θ|+1. Notice that here Tk contains 2|θ| −1
copies of T0 (namely tt) where a copy is ET0 where E ∈ TF0 , the group of isometries
generated by the functions of F0 .
Example 2. (Fibonacci 1D tilings) F1 = {ax, a2 x + 1 − a2 , a + a2 = 1, a > 0},
T = T F1 is the largest group of isometries generated by F1 . The tiles of Π(θ) for
θ ∈ Σ†∗ are isometries that belong to TF1 (the group of isometries generated by the
IFS) applied to the tiling of [0,1] provided by the IFS, writing the tiling T0 as ls
where l is a copy of [0, a] and (here) s is a copy of [0, a2 ] we have:
T0 = ls has relative addresses ∅.1, ∅.2 (i.e. the address of l is 1 and of s is 2)
T1 = lsl has relative addresses ∅.11, ∅.12, ∅.2
T2 = lslls has relative addresses ∅.111, ∅.112, ∅.12, ∅.21, ∅.22
T3 = lsllslsl has relative addresses ∅.1111, ∅.1112, ∅.112, ∅.121, ...
We remark that Tk comprises Fk+1 distinct tiles and contains exactly Fk copies
(under maps of TF1 ) of T0 , where {Fk : k ∈ N0 } is a sequence of Fibonacci numbers
{1, 2, 3, 5, 8, 13, 21, ...}.
Note that T4 = lsllslsllslls contains two ”overlapping” copies of T2 .
8.2. Absolute addresses. The set of absolute addresses associated with (F, G)
is
θ−
A := {θ.ω : θ ∈ Σ†∗ , ω ∈ Ωξ(θ)
|θ|
, θ|θ| 6= ω1 }.
b : A → {t ∈ T : T ∈ T} by
Define Π
Π(θ.ω)
b = f−θ .fω (A).
The condition θ|θ| 6= ω1 is imposed. We say that θ.ω is an absolute address of the
tile f−θ .fω (A). It follows from Definition 5 that the map Π
b is surjective: every tile
of {t ∈ T : T ∈ T} possesses at least one absolute address.
In general a tile may have many different absolute addresses. The tile [1, 1.5]
of Example 1 has the two absolute addresses 1.21 and 21.211, and many others.

8.3. The Relationship between Relative and Absolute addresses.

Theorem 11. If t ∈ Π(θ)\Π(∅) with θ ∈ Σ†∗ has relative address ω relative to
Π(θ), then an absolute address of t is θ1 θ2 ...θl .S |θ|−l ω where l ∈ N is the unique
index such that
(8.1) t ∈ Π(θ1 θ2 ...θl ) and t ∈
/ Π(θ1 θ2 ...θl−1 )
Proof. Recalling that
Π(θ|0) ⊂ Π(θ1 ) ⊂ Π(θ1 θ2 ) ⊂ ... ⊂ Π(θ1 θ2 ...θ|θ|−1 ) ⊂ Π(θ),
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 15

we have disjoint union

Π(θ) = Π(θ|0) ∪ (Π(θ1 )\Π(∅)) ∪ (Π(θ1 θ2 )\Π(θ1 )) ∪ ... ∪ Π(θ)\Π(θ1 θ2 ...θ|θ|−1 ) .
So there is a unique l such that Equation (8.1) is true. Since t ∈ Π(θ) has relative
address ω relative to Π(θ) we have
−1
ω = ∅.π −1 f−θ (t)
and so an absolute adddress of t is
−1
θ.ω|cancel = θ.π −1 f−θ (t)|cancel
where |cancel means equal symbols on either side of ”.” are removed until there is a
different symbol on either side. Since t ∈ Π(θ1 θ2 ...θl ) the terms θl+1 θl+2 ...θ|θ| must
cancel yielding the absolute address
θ.ω|cancel = θ1 θ2 ...θl .ω|θ|−l+1 ...ω|ω|


9. Rigid tilings
9.1. Definitions. Let U be the group of all isometries on RM .
Definition 10. The family of tilings T := Π(θ) : θ ∈ Σ† and the tiling IFS


(F, G) are each said to be rigid when the following two statements are true: (i)
if E1 , E2 ∈ U and k ∈ {0, 1, ..., amax − 1} are such that E1 T0v ∩ E2 sk T0w tiles
E1 Av ∩ E2 sk Aw then E1 = E2 , k = 0, and v = w; (ii) if E ∈ U and EAv = Aw
then E = I and v = w.
A different notion of a rigid for the case |V| = 1 is in [16].
9.2. Inflation and deflation. We restrict attention to rigid tiling IFSs (F, G).
Definition 11.
+
T0v = {Π(e|0) := fe (Ae ) : e− = v}
Q := {ET : E ∈ U, T ∈ T}
Q0 := {ET : E ∈ U, T ∈ T, T 6= T0v , v ∈ V}
Definition 12. Let (F, G) be a rigid tiling IFS. Deflation α : Q0 → Q is
defined by α(T ) = {α(t) : t ∈ T } where
sEAv if t ∈ ET0v ⊂ T for some E ∈ U,v ∈ V

α(t) :=
st otherwise
for all T ∈ Q0 . ET0v is called the set of partners of t ∈ ET0v . If t1 and t2 are
partners of t, then α(t1 ) = α(t2 ). Inflation α−1 : Q → Q0 is defined by
α−1 T = {s−1 t : t ∈ T, t is not congruent to sAv for any v}∪{t ∈ sET0v : E ∈ U, sEAv ∈ T }
 −1
s if t 6= EsAv for any E ∈ U,v ∈ V
α−1 (t) :=
ET0v if t = EsAv
for all T ∈ Q. In particular, αTk = Tk−1 and α−1 Tk−1 = Tk for all k ∈ N.
It is straightfoward to show that inflation and deflation are well-defined on
rigid tilings. See also [16, Lemmas 6 and 7]. It should be clear that rigidity is
largely equivalent to recognizability [1] and to the unique composition property
[37]. Rigidity extends these concepts to tiling IFSs.
16 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

Lemma 4. Let (F,G) be a rigid tiling IFS. If θ, ϕ ∈ Σ†∗ , Π(θ) ∩ EΠ(ϕ) 6= ∅ and
Π(θ) ∩ EΠ(ϕ) tiles the intersection of the supports of Π(θ) and EΠ(ϕ), then
either Π(θ) ⊂ EΠ(ϕ) or EΠ(ϕ) ⊂ Π(θ)
Proof. Follows at once from rigidity. 
9.3. Hierarchies of tilings.
Theorem 12. Let (F, G) be a rigid tiling IFS. Let Tk be given.
(i) The following hierarchy of σ ∈ Σ∗ obtains:
σ+ σ+ σ+ σ+ σ+
(9.1) ET0 |σ| ⊂ F1 Tξ(S
|σ| |σ| |σ| |σ|
|σ|−1 σ) ⊂ F2 Tξ(S |σ|−2 σ) ⊂ ... ⊂ F|σ|−1 Tξ(Sσ) ⊂ Tk=ξ(σ)

|σ|−j |σ|−j
where Fj = s−ξ(S σ) −1
Eσ|σ|−j ...σ1 sξ(S σ)
and Eθ is the isometry f−θ sξ(θ||θ|) .
Application of αξ(σ|σ| ) to the hierarchy of σ1 ...σ|σ| minus the leftmost inclusion
yields the heirarchy of σ1 ...σ|σ|−1 .
(ii) For all θ ∈ Σ†∞ , n ∈ [N ] , k ∈ N0 ,
−1
αξ(θ|k) Eθ|k Π(θ) = Π(S k θ) and α−an Π(θ) = s−an fn Π(nθ)
where Eθ|k = f−θ|k sξ(θ|k) .
Proof. (i) Equation 9.1 is the result of applying Eσ−1
|σ| σ|σ|−1 ...σ1
to the chain
of inclusions
Π(σ|σ| |0) ⊂ Π(σ|σ| ) ⊂ Π(σ|σ| σ|σ|−1 ) ⊂ ... ⊂ Π(σ|σ| σ|σ|−1 ...σ2 ) ⊂ Π(σ|σ| σ|σ|−1 ...σ1 )
θ−
|θ|
where we recall that Π(θ) = Eθ Tξ(θ) (Theorem 9) for all θ ∈ Σ†∗ , where Eθ :=
f−θ sξ(θ) .
θ−
|θ|
(ii) This follows from Π(θ) = Eθ Tξ(θ) and αT = sT s−1 α for any T : RM → RM .
Taking k = 1 in (ii) we have
(9.2) αaθ1 Π(θ) = saθ1 fθ−1
1
Π(Sθ) and α−an Π(θ) = s−an fn Π(nθ).

Define for convenience:
Λvk = {σ ∈ Σ∗ : ξ(σ) = k, σ1− = v} ⊂ Ωvk−1
Λk = ∪v Λvk ⊂ Ωk−1
Theorem 13. Let (F, G) be a rigid tiling IFS. Let Tk be given.
(i) There is a bijective correspondence between Λvk and the set of copies ET0v ⊂
Tk with E ∈ T .
(ii) If ET0v ⊂ Tk for some E ∈ T , then there is unique σ ∈ Λvk such that
E = Eσ−1
|σ| σ|σ|−1 ...σ1
= (f−σ|σ| σ|σ|−1 ...σ1 sk )−1 = s−k fσ
Proof. (i) If (F, G) is rigid, then given either of the tilings ETk or ETkv for
some v and E ∈ T we can identify E uniquely.
The relative addresses of tiles in ETk = ∪ET0v may be calculated in tandem
by repeated application of α−1 (see Section 9.2). Each tile in ET0 = ∪ET0v is
associated with a unique relative address in Ω0 = [N ]. Now assume that, for all
l = 0, 1, ..., k, v ∈ V, we have identified the tiles of ETl with their relative addresses
(relative to Tl ). These lie in Ωl = ∪Ωvl . Then the relative addresses of the tiles
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 17

of ETk+1 (relative to Tk+1 ) may be calculated from those of ETk by constructing

the set of sets s−1 ETk , and then splitting the images of large tiles, namely those
that are of the form s−1 F Av for some v ∈ V and F ∈ U , to form nonintersecting
+
sets of partners of the form {F fi (Ai ) : i− = v}, assigning to these ”children of
the split” the relative addresses of their parents (relative to Tk ) together with an
additional symbol i ∈ [N ] added on the right-hand end according to its relative
address relative to the copy of T0 to which it belongs. By rigidity, this can be done
uniquely. The relative addresses (relative to Tk+1 ) of the tiles in s−1 ETk that are
not split and so are simply s−1 times as large as their predecessors, are the same
as the relative addresses of their predecessors relative to Tk .
(ii) It follows in particular that if F is locally rigid and E 0 T0v ⊂ Tk , then the
relative addresses of the tiles of E 0 T0v must be {∅.σ1 ...σ|σ| i : i ∈ [N ]} for some
σ1 ...σ|σ| ∈ Σv∗ with ξ(σ1 ...σ|σ| ) = k. In this case we say that the relative address of
E 0 T0v (relative to Tk or Tkv ) is ∅.σ1 ...σ|σ| . 

9.4. A Key Theorem.

Theorem 14. Let (F, G) be a rigid tiling IFS. Then (i) Π : Σ† → T is invert-
ible; (ii) Π(θ) = EΠ(ψ) for E ∈ U, and θ, ψ ∈ Σ†∗ , if and only if are p, q ∈ N0 such
that S p θ = S q θ and E = f−θ|p (f−ψ|q )−1 .

Proof. Uses Lemma 4 and Theorem 13. See also [17], where the same result
is proved for the case where the tiles have nonempty interiors. 

10. The big picture

General symbolic theory
Explanation of how tiling theory and study of fractal attractors are unified by
IFS theory.
Explanation of the following diagram and associated figures.
S
Σ × Σ† ←→ Σ × Σ†
l π×Π l
α
A×T ←→ A×T

measure theory too, and how to envisage and analyze spectral properties of S
Pisot properties in the general (fractal) case

11. Relationship to Solomyak [36, 37]

unique composition property: combination of rotations as well as translations.
Pisot number theorems via ergodic theorem applied to the big picture.

12. Relationship to Anderson&Putnam [1]

clarifies and generalizes the picture of the action of various euclidean groups
and groupoids on e.g. T, showing clearly what is actually going on
18 M. F. BARNSLEY, L. F. BARNSLEY, AND A. VINCE

13. Relationship to Fast Basins, Fractal manifolds and Fractal

Continuation
Commentary on relationships with earlier key structures identified by Barnsley
and Vince. Π(θ) is a continuation of A while ∪Π(θ) is the fast basin. Examples
and references. Fractal manifolds are made by gluing tilings together where they
agree!

References
[1] J. E. Anderson and I. F. Putnam, Topological invariants for substitution tilings and their
associated C∗ -algebras, Ergod. Th. & Dynam. Sys. 18 (1998) 509-537.
[2] C. Bandt, S.Graf, Self-similar sets VII. A characterization of self-similar fractals with positive
Hausdorff measure, Proc. Amer. Math. Soc. 114 (1992) 995-1001.
[3] C. Bandt, N. V. Hung, H. Rao, On the open set condition for self-similar fractals with positive
Hausdorff measure, Proc. Amer. Math. Soc 134 (2005)1369-1374.
[4] C. Bandt, M. Mesing, Self-affine fractals of finite type, Convex and Fractal Geometry, Banach
Center Publications, (Polish Acad. Sci. Inst. Math, Warsaw) 84 (2009) 138-148.
[5] C. Bandt, P. Gummelt, Fractal Penrose tilings I: Construction and matching rules, Aequ.
math. 53 (1997) 295-307.
[6] C. Bandt, Self-similar tilings and patterns described by mappings, Mathematics of Aperiodic
Order (ed. R. Moody) Proc. NATO Advanced Study Institute C489, Kluwer, (1997) 45-83.
[7] C. Bandt, M. F. Barnsley, M. Hegland, A. Vince, Old wine in fractal bottles I: Orthogonal
expansions on self-referential spaces via fractal transformations, Chaos, Solitons and Fractals,
91 (2016) 478-489.
[8] M. F. Barnsley, J. H. Elton, D. P. Hardin, Recurrent iterated function systems, Constructive
Approximation, 5 (1989) 3-31.
[9] M. F. Barnsley, Fractals Everywhere, 2nd edition
[10] G. C. Boore, K. J. Falconer, Attractors of graph IFSs that are not standard IFS attractors
and their Hausdorff measure, arX:1108.2418v1 [math.MG] April 30, 2018.
[11] M. F. Barnsley, A. Jacquin, Application of recurrent iterated function systems to images,
Visual Communications and Image Processing ’88: Third in a Series, 122-131
[12] M. F. Barnsley, A. Vince, The chaos game on a general iterated function system, Ergod. Th.
& Dynam. Sys. 31 (2011), 1073-1079.
[13] M. F. Barnsley, A. Vince, Fast basins and branched fractal manifolds of attractors of iterated
function systems, SIGMA 11 (2015), 084, 21 pages.
[14] M. F. Barnsley, A. Vince, Fractal tilings from iterated function systems, Discrete and Com-
putational Geometry, 51 (2014), 729-752.
[15] M. F. Barnsley, A. Vince, Self-similar polygonal tilings, Amer. Math. Monthly, 124 (2017),
905-921.
[16] M. F. Barnsley, A. Vince, Self-similar tilings of fractal blow-ups, Contemporary Mathematics
731 (2019), 41-62.
[17] M. F. Barnsley, A. Vince, Tilings from graph-directed iterated function systems, submitted
for publication
[18] T. Bedford, Hausdorff dimension and box dimension in self-similar sets, Proc. of Topology
and Measure V (Ernst-Moritz-Arndt Universität Greifswald) ** (1988).
[19] T. Bedford, Dimension and dynamics for fractal recurrent sets, J. London Math. Soc. (2) 33
(1986) 89-100.
[20] T. Bedford, A. M. Fisher, Ratio geometry, rigidity and the scenery process for hyperbolic
Cantor sets, Ergod. Th. & Dynam. Sys. 17 (1997) 531-564.
[21] J. Bellissard, A. Julien, J. Savinien, Tiling groupoids and Bratteli diagrams, Ann. Henri
Poincaré 11 (2010), 69-99.
[22] M. Das, G. A. Edgar, Separation properties for graph-directed self-similar fractals, Topology
and its Applications 152 (2005) 138-156.
[23] F. M. Dekking, Recurrent sets, Advances in Mathematics, 44 (1982) 78-104.
[24] R. L. Devaney, An Introduction to Chaotic Dynamical Systems, Addison-Wesley, 1989.
[25] B. Grünbaum and G. S. Shephard, Tilings and Patterns, Freeman, New York (1987).
[26] J. Hutchinson, Fractals and self-similarity, Indiana Univ. Math. J. 30 (1981) 713-747.
 NOTES ON TILING ITERATED FUNCTION SYSTEMS 19

[27] R. Kenyon, The construction of self-similar tilings, Geom. Funct. Anal. 6 (1996) 471-488.
[28] R.D. Mauldin, R.F. Williams, Hausdorff dimension in graph directed constructions, Trans.
Am. Math. Soc. 309 (1988) 811-829
[29] M. Morán,Dynamical boundary of a self-similar set, Fundamenta Mathematicae 160 (1999)
1-14.
[30] W. Parry, Topics in Ergodic Theory, C.U.P., Cambridge, 1981.
[31] R. Penrose, Pentaplexity, Math Intelligencer 12 (1965) 247-248.
[32] K. Scherer, A Puzzling Journey To The Reptiles And Related Animals, privately published,
Auckland, New Zealand, 1987.
[33] J. H. Schmerl, Dividing a polygon into two similar polygons, Discrete Math., 311 (2011)
220-231.
[34] L. Sadun, Tiling spaces are inverse limits, J. Math. Phys., 44 (2003) 5410-5414.
[35] A. Shief, Separation properties for self-similar sets, Proc Am Math Soc 122 (1994) 111-115.
[36] Boris Solomyak, Dynamics of self-similar tilings, Ergodic Theory & Dyn. Syst., 17 (1997)
695-738.
[37] Boris Solomyak, Non-periodicity implies unique composition for self-similar translationally
finite tilings, Discrete and Computaional Geometry, 20 (1998) 265-279.
[38] R. S. Strichartz, Fractals in the large, Canad. J. Math., 50 (1998) 638-657.
[39] Keith R. Wicks, Fractals and Hyperspaces, Springer-Verlag (Berlin, Heidelberg) (1991).
[40] I. Werner, Contractive Markov systems, J. Lond Math Soc., 71 (2005), 236-258.s

Australian National University, Canberra, ACT, Australia

Australian National University, Canberra, ACT, Australia

University of Florida, Gainesville, FL, USA,