A SURVEY ON TOPOLOGICAL PROPERTIES OF TILES RELATED TO
NUMBER SYSTEMSSHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER
Abstract. In the present paper we give an overview of topological properties of self-affine
tiles. After reviewing some basic results on self-affine tiles and their boundary we give criteria for their local connectivity and connectivity. Furthermore, we study the connectivityof the interior of a family of tiles associated to quadratic number systems and give resultson their fundamental group. If a self-affine tile tessellates the space the structure of the setof its “neighbors” is discussed.

1. Introduction and basic definitions
Let X be a complete metric space and let fi : X → X (1 ≤ i ≤ m) be injective
contractions. In [31] it is proved that there is a unique compact non-empty set K satisfying
K = f1 (K) ∪ . . . ∪ fm (K).
{fi }1≤i≤m is called iterated function system (IFS for short). K is called the attractor of thisIFS.
Let A be an expanding d × d matrix (i.e. a matrix each of whose eigenvalues is strictly
greater than 1) and suppose that | det(A)| = m for some integer m > 1. Let D :={a1 , . . . , am } ⊂ Rd be a finite set of vectors. Then the non-empty compact set T which
satisfies
m
[
(1.1)
T =
A−1 (T + aj )j=1

is the attractor of the IFS {A−1 (x + aj )}1≤i≤m . The union on the right hand side of (1.1)
will be denoted by F (T ). If the d-dimensional Lebesgue measure µd satisfies µd (T ) > 0 andµd ((T + ai ) ∩ (T + aj )) = 0 for i 6= j, we call T = T (A, D) a self-affine tile. D is often called
the digit set of T .
Let A be an expanding d × d integer matrix and D ⊂ Zd . Then we call T = T (A, D) an
integral self-affine tile. If D is even a complete set of coset representatives for Zd /AZd thenwe say that T = T (A, D) is an integral digit tile.
Fundamental properties of self-affine tiles have been proved for instance in [9, 25, 37, 42,
43, 44, 62]. We also mention the survey papers [65, 66] and the monograph [27].
Self-affine tiles have been studied from many viewpoints. There is a natural connection
to radix representations which has been explored for instance in [23, 32, 33, 34, 53] (hereespecially integral digit tiles play a role). Several authors study the fractal structure of theirDate: February 20, 2004.
1

2

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER
1.5
1

0.5

0.5
-1

-0.75 -0.5 -0.25

0.25

-3

-2

-1

1
-0.5

-0.5

-1
-1.5

-1

-2

Figure 1. Examples of CNS tiles
boundary ([19, 24, 56, 63, 65, 66]) and their dynamical properties (cf. [58]). Furthermore,their connection to wavelets has been studied for instance in [13, 26, 67].
The present paper is mainly devoted to topological properties of self-affine tiles. As
reviewed later, there are considerable results on the topology of a fixed self-affine tile. Our
main goal is to show topological results for families of tiles. Especially we study integral
digit tiles associated to quadratic canonical number systems (CNS for short). We recall thedefinition of quadratic CNS. Let p(x) = x2 +Ax+B ∈ Z[x] with B ≥ 2 and N = {0, . . . , B −1}. Then (p, N ) is a quadratic CNS if each q ∈ Z[x]/p(x)Z[x] admits a representation of
the shapenXq(x) =
c j xjj=0

with cj ∈ N . It was shown in [14, 22, 35, 36] that (p, N ) is a quadratic CNS if and only if−1 ≤ A ≤ B,

B ≥ 2.

To each quadratic CNS we can associate a self-affine tile. This tile is defined by T = T (A, D)
with
µ
¶
½µ ¶
µ
¶¾
0 −B
0
B−1
(1.2)
A=
and D =
,...,
1 −A
0
0
and can be interpreted as the set of all “α−1 -adic expansions” where α is a root of p(x). (cf.
for instance [6, 24, 34, 56]). In what follows we just call the tiles in (1.2) quadratic CNS
tiles. We shall show later that the quantity
½ ¹
º¾
B−1
(1.3)
J := max 1,
B−A+1
has great influence on the topological behavior of a quadratic CNS tile.
The choice A = B = 2 corresponds to Knuth’s well-known “twin-dragon” (cf. [39, p. 206]).
Pictures of the quadratic CNS tiles with parameters A = 2, B = 3 and A = 6, B = 7 areshown in Figure 1.
Of course it is possible to define CNS and their associated tiles of arbitrary degree in asimilar way. For further details on CNS and their associated tiles we refer the reader toTOPOLOGY OF TILES

3[2, 4, 52, 55, 56]. In higher dimensional cases, topological study of such a family of tiles will
be an interesting question.
2. Geometric properties of tiles and their boundary
An important tool for obtaining results on the topology of tiles is the so-called contact
matrix (cf. [25, p. 134]) which is associated to an integral digit tile T (A, D). Let {e1 , . . . , ed }be the canonical basis of the lattice Zd and set C0 := {0, ±e1 , . . . , ±ed }. Recursively define
the sets
Cn := {k ∈ Zd | (Ak + D) ∩ (l + D) 6= ∅ for some l ∈ Cn−1 }.
S
Set R := n≥0 Cn which is easily seen to be a finite set (cf. [25, Lemma 4.5]). Define the|R| × |R| matrix C, called the contact matrix, by
ckl := |(Ak + D) ∩ (l + D)| (k, l ∈ R).
To this matrix we associate the contact graph G(R). The vertices of G(R) are the elementsof the set R. There is a directed edge from k to l labeled by a|a0 (a, a0 ∈ D) if Ak +a0 = l +a.
The following theorem gives criteria which are equivalent to the fact that a given integral
digit tile “tiles” the space without overlap. Recall that a digit set of an integral digit tile iscalled primitive, if it is not contained in any proper A-invariant sublattice of Zd .
Theorem 2.1 (cf. [25, 42, 43, 44, 64, 65]). Let T = T (A, D) be an integral digit tile withprimitive digit set. Let T0 be the d-dimensional unit cube centered at the origin and set
Tn := F n (T0 ). Then the following statements are equivalent• {T + x | x ∈ Zd } is a tiling of Rd .
• µd (T ) = 1.
• limn→∞ ∂Tn = ∂T (Hausdorff metric).
• limn→∞ ∂Tn (Hausdorff metric) is not space filling.
• Let λ be the spectral radius of the contact matrix C. Then λ < | det(A)|.
We mention that the last criterion concerning the spectral radius of the contact matrix
can be checked algorithmically.
An integral digit tile which satisfies the equivalent statements of Theorem 2.1 will becalled a Zd -tile.
Let T = T (A, D) be a Zd -tile. We will derive a representation for ∂T (cf. [57, 60]). To
this matter we first define the “set of neighbors” of T , i.e.,
S := {k ∈ Zd \ {0} | T ∩ (T + k) 6= ∅}.
Since the Zd -translates of T tile Rd we have
∂T =

[

Bk

k∈S

where we set Bk := T ∩ (T + k) for convenience. By (1.1) we have ABk = (T + D) ∩ (T +D + Ak) and thus[
ABk :=(BAk+a0 −a + a) .
a,a0 ∈D

4

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER

In order to remove all elements Bk which are empty, define a graph G(S) with set of vertices
S. Furthermore, there is a label a|a0 from k to l if
Ak + a0 = l + a(2.1)
holds. It is now easy to see that
(2.2)

ABk =

[

(Bl + a)

a|a0

k−
−→l

(the union is extended over all edges in G(S) leading away from k). Thus the sets Bk (k ∈ S)
are the solutions of the graph directed construction in (2.2). It is known that they are evendefined uniquely by this construction (cf. [20, Chapter 3]). For general IFS attractors with
non-empty interior it is not so easy to get information on their boundary (cf. for instance[18, 45, 47, 61]).
In what follows, for each set M ⊂ Zd we will denote by G(M ) the graph with vertices
M and edges between these vertices defined by (2.1). In general, G(R \ {0}) ⊂ G(S) holds.
Also G(R) can be used instead of G(S) in order to describe the boundary. This is a bit moredifficult to show (cf. [57, Section 2]) but has the advantage that G(R) is in general easier todetermine than G(S). Both graphs have been used for instance in order to determine thedimension of the boundary of certain classes of tiles (cf. for instance [19, 56, 63, 65, 66]).
3. Connectivity and homeomorphy to a closed discIn [38, Theorem 4.3] the following criterion was given (cf. also [29, Theorem 4.6] wherea more general result is shown; also the local connectivity assertion is contained in [29,Theorem 4.6]; in [25, Theorem 2.5] a two-dimensional version can be found).
Theorem 3.1. Let T (A, D) be a self-affine tile. Define
E := {(ai , aj ) ∈ D × D | (T + ai ) ∩ (T + aj ) 6= ∅} .
Then T is a locally connected continuum if and only if for any two distinct ai , aj ∈ D there
exists a subset {ai1 , . . . , aik } ⊆ D such that ai1 = ai , aik = aj and (ai` , ai`+1 ) ∈ E for(1 ≤ ` ≤ k − 1).
Proof. The “only if” part is obvious. Thus we turn to the “if” part. By repeated use of (1.1)
and the application of the condition, we see that any two points in T are ε-chain connected.
As T is compact, this implies the result.
¤
Remark 3.2. Note that if an integral self-affine tile T is connected, it is even arcwise
connected and there exists a continuous mapping from [0, 1] onto T (cf. [29, Remark 2]).
We have the following consequence of Theorem 3.1. (cf. [6]).
Corollary 3.3. Each quadratic CNS tile T is a locally connected continuum.
µ ¶1
The only thing to show is that T and T +have non-empty intersection in order to0meet the conditions of Theorem 3.1. For tiles corresponding to CNS of degree three andTOPOLOGY OF TILES

5

four the connectivity has been shown in [3]. For tiles of degree higher than four it is notknown whether they are always connected.
We also mention that in [28] it was shown that any integral self-affine tile having |D| = 2
is connected (see also [38, Proposition 4.1]). Furthermore, in [38, Theorem 5.5] it was provedthat to any expanding 2 × 2 integer matrix A there exists a digit set D such that T (A, D)
is a connected integral self-affine tile.
A more difficult problem is to decide whether a self-affine tile T is homeomorphic to aclosed disc (disclike, for short). We start with a result which holds for arbitrary IFS in theplane satisfying the following condition (cf. [20, p. 35]): An IFS {fj }1≤j≤m is said to fulfill
the open set condition if there exists a non-empty bounded open set U such thatm[U⊃
fj (U )
j=1

where the union is disjoint.
Theorem 3.4 (cf. [48]). Let {fi }1≤i≤m with fi : R2 → R2 be an IFS satisfying the open set
condition. Let K be the attractor of this IFS. If int(K) is connected then K is homeomorphic
to a closed disc.
Sketch of the proof. We confine ourselves to prove the result for a connected Z2 -tile T having
connected interior. In the general case one has to use the fact that any plane IFS with open
set condition induces a “tiling” of R2 (cf. for instance [48] or [51, Lemma 2.3]).
Since T is the closure of its interior (cf. for instance [66, Theorem 2.1]) it is easy to
see that the connectivity of int(T ) implies that T has no cut point. Thus T is a locallyconnected continuum without cut points. From [41, Chap.10, §61 II, Theorem 4] that theboundary of each component of R2 \ T is a simple closed curve.
We will now prove that R2 \ T is connected. Suppose not. Then it has a bounded
component C. Since T is a Z2 -tile there has to exist at least one v ∈ Z2 such that C ∩int(T + v) 6= ∅ (note that C is open and T + v is the closure of its interior). Now there
are two possibilities: firstly, T + v is contained in C̄. By iterating this argumentation we
derive that there are infinitely many translates v 0 ∈ Z2 such that T + v 0 ⊂ C̄, which is
impossible because C is bounded. Secondly, T + v is not contained in C̄. This easily leads
to a contradiction to the fact that int(T ) + v is connected.
Thus R2 \ T is connected and, hence, the only component of R2 \ T . This implies that∂(R2 \ T ) = ∂T is a simple closed curve. This curve separates int(T ) and int(R2 \ T ). Since
T is bounded it is a closed disc by Jordan’s theorem.
¤
In general, it is not easy to decide whether int(K) is connected or not. In [5] connectivityof int(T ) is shown for a class of quadratic CNS tiles. This leads to the following result.
Theorem 3.5. Let T be a quadratic CNS tile. Then T is homeomorphic to a closed disc if
and only if J = 1, i.e. 2A < B + 3.
Rough sketch of the proof. It is easy to check that T fulfills the open set condition with
U = int(T ). Thus in view of Theorem 3.4 we only have to show that int(T ) is connected.
The proof of this claim is rather involved. One constructs a “skeleton”, which is a connected

6

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER

subset of int(T ) consisting of infinitely many line segments. This skeleton can be shown to
be dense in T which yields the connectivity of int(T ).
¤This result gives a definite answer to the topological structure of quadratic CNS tiles with
J = 1. Observe that the tile on the left hand side of Figure 1 belongs to this class.
Another approach for deciding whether T is homeomorphic to a closed disc is pursued in[10, 11]. In these papers criteria for disclikeness of self-affine tiles are established, which areeasier to check algorithmically. Let T be a Z2 -tile and let S be as in Section 2. Let k ∈ S.
If T ∩ (T + k) is a single point, we call T + k a vertex neighbor. If this set is uncountable,
we call it an edge neighbor.
The following result is a special case of [10, Lemma 5.1]. We give it in the form occurringin [11, Proposition 1.1].
Theorem 3.6. Let T be a Z2 -tile which is homeomorphic to a closed disc. Then one of thefollowing alternatives holds.
• T has no vertex neighbors and 6 edge neighbors T ± k, T ± l, T ± (k + l) with
Zk + Zl = Z2 .
• T has 4 edge neighbors T ±k, T ±l and 4 vertex neighbors T ±k±l with Zk+Zl = Z2 .
A partial converse of this result was shown in [11, Theorems 2.1 and 2.2]. Let F be a
finite subset of Zd . We say that a set M ⊂ Zd is F -connected if for any u, v ∈ M there
exists {u1 , u2 . . . , un } ⊂ M with u = u1 and v = un such that ui+1 − ui ∈ F .
Theorem 3.7. Let T = T (A, D) be a Z2 -tile. Then the following holds.
• If |S| ≤ 6 then T is homeomorphic to a disc if and only if D is S-connected.
• If S = {±k, ±l, ±k ± l} (|S| = 8) then T is homeomorphic to a disc if and only if T
is {±k, ±l}-connected.
Thus it remains to determine the set of neighbors of T in order to apply these criteria.
There exist algorithms which allow to determine the neighbors of a given tile (cf. [57, 60]).
We will discuss these algorithms in Section 6.
All the above theorems are valid only in the plane. In R3 neither Theorem 3.4 nor
Theorem 3.7 remains valid (cf. [51, Example 5.2] for a counterexample).
Let T = T (A, D) be a Z2 -tile. For |D| ≤ 4 up to affine conjugacy all disclike tiles havebeen characterized (cf. [10, 21, 59]). In fact, for |D| = 2 there are three, for |D| = 3 there
are seven and for |D| = 4 there are 29 conjugacy classes of disclike tiles.
We conclude this section by mentioning the sets which do not fit totally in our context:
the Rauzy Fractal and the Thurston tiling which has connection to substitutive dynamics
and Pisot number systems (cf. [1, 7, 54]). It can be defined with help of a graph directed construction. For the smallest Pisot number, the corresponding tile is shown to behomeomorphic to a closed disc in [46].
4. Tiles which are not homeomorphic to a discIn this section we deal with connected self-affine tiles whose interior is disconnected.
In this setting the situation becomes very complicated and only few general results exist.
However, many examples and even classes of tiles have been studied in some detail.

TOPOLOGY OF TILES

7

Figure 2. The Heighway dragon
We start with two results due to [51], where the structure of the components of int(T ) isinvestigated.
Theorem 4.1 (cf. [51, Theorem 1.1, Theorem 1.2 and Lemma 2.2]). Let K be the attractor
of an IFS in R2 satisfying the open set condition and assume that K is connected. Thenthe closure of each component of int(K) is a locally connected continuum. If the number ofcomponents is finite, then the closure of at least one component is homeomorphic to a closed
disc.
A remark on the proof. The proof is very complicated. When the number of components is
infinite, it relies on the following fact: Assume that Ui is not locally connected. Then Ui
contains a convergence continuum (cf. [41, §49, VI, Definition and Theorem I]). From thisfact one derives in a very tricky way, that also K is not locally connected. Because K isconnected, this is a contradiction to [29, Theorem 4.6].
¤
Under some additional conditions which look not so easy to check in general, in [51] it isshown that Ui is homeomorphic to a disc for each i.
Let T be a connected Z2 -tile and let U be a component of its interior. If U has a hole(i.e. its complement has a bounded component) then some neighbor T + k of T (k ∈ S) has
to fill this hole at least partially. In [50, Proposition 3.1] it is shown that this implies thatT + k, and hence also T , has a cut point. In other words, if T has no cut point then theclosure of each interior component is homeomorphic to a disc. A criterion for cut points isgiven in [50, Theorem 1.1].
In [5] the following result was shown.
Theorem 4.2. If T is a quadratic CNS tile with J > 1, i.e. 2A ≥ B + 3 then int(T ) is
disconnected. It even has infinitely many components.
From Theorem 4.1 and 4.2 we conclude that the closure of each component of the interiorof these quadratic CNS tiles is a locally connected continuum. (Observe that the right tilein Figure 1 belongs to this class of tiles.)For many examples and even classes of tiles more information on the topological structure
has been obtained.

8

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER

Example.(The Heighway Dragon) The Heighway dragon (see Figure 2) is the attractor of
the IFSµ ¶µ ¶3π
1 ³π ´10
f1 (x) := √ R
x, f2 (x) := √ R
x+
1
4
4
2
2
where R(θ) denotes the counterclockwise rotation by θ. References to this set are [12, 16,
17, 49].
Its topological structure was studied thoroughly in [49, Theorem 1.1]. In particular, it isproved that the Heighway dragon is the closure of a countable union of geometrically similar
sets each of which is homeomorphic to a closed disc. Any two of these sets intersect in at
most one point and for each three of them there are at least two with empty intersection.

Example. The quadratic CNS tile corresponding to the choice A = 4, B = 5 depicted in
Figure 3 has been studied in [50]. It has been shown that this tile has no cutpoint and thatthe closure of every component of its interior is homeomorphic to a closed disc.
Also for the Eisenstein set and the Lévy dragon several topological properties have been
deduced (cf. [8, 50, 51]).
Let T be a Z2 -tile. The next question we want to address is the shape of the components
of int(T ). To our knowledge there exists no general result in this direction. Apart from theabove-mentioned result on the Heighway dragon, for the Lévy dragon it has been shownthat the interior components have at least 16 different shapes (cf. [8]).
Concerning quadratic CNS tiles we announce the following result which will appear in aforthcoming paper.
Theorem 4.3. Let T be a quadratic CNS tile with J = 2. Let M be the closure of thecomponent of int(T ) containing zero. M is the attractor of a graph-directed construction
with affine functions which is defined by means of an explicit graph with 18 vertices.
This result is shown with help of a very lengthy but elementary calculation. In Figure 3
we depicted the quadratic CNS tile corresponding to the parameters A = 4, B = 5 together
with the component of its interior which contains the origin.
5. The fundamental group of a tile
In this section we are concerned with the fundamental group of a self-affine tile. The
fundamental group of a set K will be denoted by π1 (K). S1 and D2 denote the unit circle
and closed unit disc, respectively. Furthermore, S2 denotes the one point compactificationof R2 . For an open ball with radius r centered at x we will write Br (x). We will use freely
definitions from [40, 41] and [30].
First we prove the following theorem.
Theorem 5.1. Let T ⊂ S2 be a connected Z2 -tile.
• If S2 \ T is connected then π1 (T ) is trivial. If, moreover, T contains no cut points,
it is homeomorphic to a closed disc.

TOPOLOGY OF TILES

9

0.5

-1.5

-1

-0.5

0.5

-0.5

0.4
0.3
0.2
0.1

-1

0
-0.1
-0.2
-0.2-0.1 0 0.1 0.2

Figure 3. The quadratic CNS tile with A = 4, B = 5 and the component of
its interior containing the origin.
• If S2 \ T is disconnected then π1 (T ) is uncountable and not free. Furthermore, T is
not locally simply connected and has no universal cover.
In particular, the fundamental group of a Z2 -tile is either trivial or uncountable.
Proposition 5.2. Let K ⊂ S2 be a locally arcwise connected set. If S2 \ K is disconnected
then K contains a non-trivial loop.
Proof. Let U1 and U2 be two components of S2 \ K and select p ∈ U1 and q ∈ U2 . Then K
cuts S2 between p and q. By [41, §62, VI, Theorem 1] this implies the existence of a simple
closed curve C ⊂ K which also cuts S2 between p and q. From this follows by [41, §59, IV,
Theorem 4] that every set obtained from C by deformation in S2 \ {p, q} can not be a single
point. Since K ⊂ S2 \ {p, q} this holds also for each deformation of C in K. Thus C is a
non-trivial loop in K. This proves the result.
¤
Proposition 5.3. Let K ⊂ S2 be a connected, locally arcwise connected continuum. Supposethat S2 \ K has infinitely many components. Then the following assertions hold: (i) π1 (K)is not free, (ii) π1 (K) is uncountable, (iii) K is not locally simply connected and (iv) K has
no universal cover.
Proof. We show assertion (iii). Then [15, Theorem 3.1] yields the other assertions. Let{Ui }i≥0 be the components of S2 \ K and select xi ∈ Ui . Let x be an accumulation pointof the sequence xi and fix ε > 0. Since K is a locally connected continuum there exists an
η > 0 such that every pair of points with distance less than η can be connected by an arcof diameter ε (cf. [41, §50, II, Theorem 4]).
By a theorem of Schönflies (cf. [41, §61, II, Theorem 10]) we have limi→∞ diam(Ui ) = 0.
The definition of x implies that there is an m ∈ N such that Um ⊂ Bη/2 (x). Let Kr :=10

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER

K ∩ Br (y). Then Kη/2 is a locally arcwise connected set with disconnected complement.
Applying Proposition 5.2 yields a nontrivial loop Cη ⊂ Kη/2 . This loop can be connectedwith x by an arc contained in Kε . By [30, Proposition 1.5] this yields a nontrivial loop in
Kmax(ε,η) which is based in x. Thus K is not locally simply connected at x. This proves(iii).
¤
Lemma 5.4. Let T ⊂ S2 be a connected Z2 -tile with disconnected complement S2 \ T . ThenS2 \ T has infinitely many components.
Proof. This can be proved by imitating part (ii) of the proof of [5, Theorem 7.1].

¤

Proof of Theorem 5.1. Note that T is a locally arcwise connected continuum by Theorem 3.1
and the remark after it. Thus the first part follows from Kuratowski [41, §61, IV, Theorem 11], which implies that T is an absolute retract. Just note that for a set M which isan absolute retract we can extend each continuous function f : S1 → M to a continuousfunction f˜ : D2 → M . This implies that each loop in M is trivial. The second part follows
from Lemma 5.4 together with Proposition 5.3.
¤
In [57, Section 7] an easy example of a self-affine tile whose complement is connected andwhich is not homeomorphic to a disc is discussed.
It is not trivial to decide whether the complement of a given self-affine tile is connected
or not. We state the following result on quadratic CNS tiles.
Theorem 5.5. Let T be a quadratic CNS tile and let J > 1, i.e. 2A ≥ B + 3. Then S2 \ T
is not connected.
The proof of this result is rathor technical and will appear in a forthcoming paper. Theorem 5.5 and Theorem 5.1 imply the following result.
Theorem 5.6. Let T be a quadratic CNS tile. If J > 1 then π(T ) is not free has uncountably
many elements. Furthermore, T is not locally simply connected and and has no universal
cover.
6. Neighbors of tiles and points where many tiles coincide
Before we discuss algorithms which allow to determine the set of neighbors of a given tile,
we want to illustrate the connection between neighbors and the topology of T with help of
two figures (this connection can be seen for instance in Theorem 3.7).
In Figure 4 we see a tiling with tiles being homeomorphic to a disc. One can see thatthe tile in the center has six neighbors and that there are six points in which three different
tiles meet.
However, in Figure 5 things are totally different. The interior of the tile T is disconnectedin this case. So there are points in which the tile becomes very “thin”. In some of thesepoints two neighbors of T meet. On the other hand, because of these points T has neighbors
which it meets in points, where some of the other tiles are “thin”. This heuristic shows thatthe fact that the interior of a tile is disconnected increases the number of its neighbors.
The first algorithm for the determination of the neighbors of a Zd -tile T (A, D) was established in [60]. It starts from a large graph G which contains G(S). G(S) is constructedTOPOLOGY OF TILES

11

4

2

0

-2

-4

-1.5

-1

-0.5

0

1

0.5

1.5

Figure 4. A tiling with tiles being homeomorphic to a disc.

7.5
5
2.5
0
-2.5
-5
-7.5
-10

-2

-1

0

1

2

Figure 5. A tiling with tiles whose interiors have infinitely many components.

from G by successive pruning of vertices. This algorithm is easy to apply, however, if oneof the eigenvalues of A is close to one in modulus the graph G becomes large. It does noteasily apply to a family of tiles.

12

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER

In [57] another algorithm is presented. It starts from the contact graph G(R) which canbe shown to be a subgraph of G(S) (cf. [57, Corollary 4.3]). G(S) is calculated by a certain
graph product of G(R) with itself. We start with the definition of this graph product.
Definition 6.1. Let G1 and G01 be subgraphs of G(Zd ). The product G2 := G1 ⊗G01 is definedin the following way. Let r1 , s1 be vertices of G1 and r10 , s01 be vertices of G01 . Furthermore,let `1 , `01 , `2 ∈ D.
• r2 is a vertex of G2 if r2 = r1 + r10`1 |`2• There exists an edge r2 −−→ s2 in G2 if there exist`1 |`01
r1 −−→
s1 ∈ E(G1 ) and`0 |`2r10 −1−→ s01 ∈ E(G01 )with r1 + r10 = r2 and s1 + s01 = s2 or there exist`0 |`2

r1 −1−→ s1 ∈ E(G1 ) and`1 |`01
r10 −−→
s01 ∈ E(G01 )with r1 + r10 = r2 and s1 + s01 = s2 .
Before we give the algorithm, we introduce the following notation. Let G be a graph. We
denote by Red(G) the graph that emerges from G if all vertices of G, which are not thestarting point of a walk of infinite length, are removed.
Algorithm 6.2. The graph G(S), and with it the set S, can be determined by the following
algorithm starting from the graph G(R).
p := 1
A[1] := Red(G(R))
repeatp := p + 1
A[p] := Red(A[p − 1] ⊗ A[1])until A[p] = A[p − 1]
G(S) := A[p] \ {0}This algorithm always terminates after finitely many steps.
Since the contact matrix is of an easy shape, this algorithm turns out to be suitable inorder to get the set of neighbors even for a class of tiles. For each quadratic CNS tile thecontact graph has only |R| = 7 vertices. Thus it was possible to derive the following result(cf. [5]).
Theorem 6.3. Let T be a quadratic CNS tile (with A 6= 0 to avoid trivialities). If J is
defined as in (1.3) then the set of neighbors S of T has 2 + 4J elements, i.e. T has 2 + 4J
neighbors.
Using certain product graphs, it is also possible to characterize points of a tiling, in whichmore tiles coincide. Let T be a Zd -tile. We call a point v ∈ T an L-vertex, if v is contained

TOPOLOGY OF TILES

13

in at least L pairwise disjoint tiles different from T . More precisely, for pairwise disjoint
s1 , . . . , sL ∈ S we set
¯
(
)
L
¯
\
¯
VL (s1 , . . . , sL ) := x ∈ R2 ¯ x ∈ T ∩ (T + sj ) .
¯
j=1

The set of L-vertices of T is then defined by[
VL =VL (s1 , . . . , sL ){s1 ,...,sL }⊂S

where the union is extended over all subsets of S containing L elements. A 2-vertex issometimes simply called vertex.
For the set of vertices of a quadratic CNS tile T we have the following characterization(cf. [5]).
Theorem 6.4. Let T be a quadratic CNS tile (with A 6= 0 to avoid trivialities) and J be asin (1.3).
• If J = 1 thenV1 is uncountable infinite,
V2 contains six elements,
VL = ∅ (L ≥ 3).
• If J = 2 and 2A = B + 3 thenV1 is uncountable infinite,
V2 is countable infinite,
VL = ∅ (L ≥ 3).
• If J ≥ 2 and B − A + 1 does not divide B − 1 then
VL is uncountable infinite (1 ≤ L ≤ J),
VL = ∅ (L ≥ J + 1).
• If J > 2 and B − A + 1 divides B − 1 then
VL is uncountable infinite (1 ≤ L ≤ J − 1),
VJ finite,
VL = ∅ (L ≥ J + 1).
The proof mainly depends on Theorem 6.3 and a certain graph product.
Acknowledments. The authors are really grateful to the referee for giving us constructive advices on the first version of the paper.

14

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER

References[1] S. Akiyama. On the boundary of self affine tilings generated by Pisot numbers. J. Math. Soc. Japan,
54(2):283–308, 2002.
[2] S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, and J. M. Thuswaldner. Generalized radix representations and dynamical systems I. submitted.
[3] S. Akiyama and N. Gjini. Connectedness of number theoretic tilings. submitted.
[4] S. Akiyama and H. Rao. New criteria for canonical number systems. Acta Arith., 111(1):5–25, 2004.
[5] S. Akiyama and J. M. Thuswaldner. Topological structure of fractal tilings generated by quadratic
number systems. submitted.
[6] S. Akiyama and J. M. Thuswaldner. Topological properties of two-dimensional number systems. J.
Theor. Nomb. Bordx., 12:69–79, 2000.
[7] P. Arnoux and S. Ito. Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin,8(2):181–207, 2001. Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000).
[8] S. Bailey, T. Kim, and R. S. Strichartz. Inside the Lévy dragon. Amer. Math. Monthly, 109(8):689–703,
2002.
[9] C. Bandt. Self-similar sets 5. Proc. Amer. Math. Soc., 112:549–562, 1991.
[10] C. Bandt and G. Gelbrich. Classification of self-affine lattice tilings. J. London Math. Soc. (2), 50:581–
593, 1994.
[11] C. Bandt and Y. Wang. Disk-like self-affine tiles in R2 . Discrete Comput. Geom., 26:591–601, 2001.
[12] A. Benedek and R. Panzone. On some notable plane sets. II. Dragons. Rev. Un. Mat. Argentina, 39(12):76–89, 1994.
[13] O. Bratteli and P.E.T. Jorgensen. Iterated function systems and permutation representations of the
Cuntz algebra. Mem. Amer. Math. Soc., 139(663):x+89, 1999.
[14] H. Brunotte. On trinomial bases of radix representations of algebraic integers. Acta Sci. Math. (Szeged),67(3-4):521–527, 2001.
[15] G. R. Conner and J. W. Lamoreaux. On the existence of universal covering spaces for metric spaces
and subsets of the euclidean plane. preprint.
[16] C. Davis and D. Knuth. Number representations and dragon curves I. J. Recreational Math., 3:66–81,
1970.
[17] C. Davis and D. Knuth. Number representations and dragon curves II. J. Recreational Math., 3:133–149,
1970.
[18] F. M. Dekking and P. van der Wal. The boundary of the attractor of a recurrent iterated function
system. Fractals, 10:77–89, 2002.
[19] P. Duvall, J. Keesling, and A. Vince. The Hausdorff dimension of the boundary of a self-similar tile. J.
London Math. Soc. (2), 61:748–760, 2000.
[20] K. J. Falconer. Techniques in Fractal Geometry. John Wiley and Sons, Chichester, New York, Weinheim,
Brisbane, Singapore, Toronto, 1997.
[21] G. Gelbrich. Crystallographic reptiles. Geom. Dedicata, 51:235–256, 1994.
[22] W. J. Gilbert. Radix representations of quadratic fields. J. Math. Anal. Appl., 83:264–274, 1981.
[23] W. J. Gilbert. Complex numbers with three radix representations. Canadian J. Math., 34:1335–1348,
1982.
[24] W. J. Gilbert. Complex bases and fractal similarity. Ann. sc. math. Quebec, 11(1):65–77, 1987.
[25] K. Gröchenig and A. Haas. Self-similar lattice tilings. J. Fourier Anal. Appl., 1:131–170, 1994.
[26] K. Gröchenig and W. R. Madych. Multiresolution analysis, Haar bases, and self-similar tilings of Rn .
IEEE Trans. Inform. Theory, 38(2, part 2):556–568, 1992.
[27] B. Grünbaum and G. C. Shephard. Tilings and Patterns. W. H. Freeman and Company, New York,1987.
[28] D. Hacon, N. Saldanha, and J. J. P. Veerman. Remarks on self-affine tilings. Exp. Math., 3(4):317–327,
1994.
[29] M. Hata. On the sturcture of self-similar sets. Japan J. Appl. Math., 2:381–414, 1985.

TOPOLOGY OF TILES

15[30] A. Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002.
[31] J. E. Hutchinson. Fractals and self-similarity. Indiana Univ. Math. J., 30:713–747, 1981.
[32] K.-H. Indlekofer, I. Kátai, and P. Racsko. Some remarks on generalized number systems. Acta Sci.
Math. (Szeged), 57:543–553, 1993.
[33] I. Kátai. Number systems and fractal geometry. preprint.
[34] I. Kátai and I. Kőrnyei. On number systems in algebraic number fields. Publ. Math. Debrecen, 41(3–4):289–294, 1992.
[35] I. Kátai and B. Kovács. Kanonische Zahlensysteme in der Theorie der Quadratischen Zahlen. Acta Sci.
Math. (Szeged), 42:99–107, 1980.
[36] I. Kátai and B. Kovács. Canonical number systems in imaginary quadratic fields. Acta Math. Hungar.,
37:159–164, 1981.
[37] R. Kenyon. Self-replicating tilings. In Symbolic dynamics and its applications (New Haven, CT, 1991),
volume 135 of Contemp. Math., pages 239–263. Amer. Math. Soc., Providence, RI, 1992.
[38] I. Kirat and K.-S. Lau. On the connectedness of self-affine tiles. J. London Math. Soc. (2), 62:291–304,
2000.
[39] D. E. Knuth. The Art of Computer Programming, Vol 2: Seminumerical Algorithms. Addison Wesley,
London, 3rd edition, 1998.
[40] K. Kuratowski. Topology, volume I. Academic Press, Polish Scientific Publishers, New York, London,Warszawa, 1966.
[41] K. Kuratowski. Topology, volume II. Academic Press, Polish Scientific Publishers, New York, London,Warszawa, 1968.
[42] J. Lagarias and Y. Wang. Integral self-affine tiles in Rn I. standard and nonstandard digit sets. J.
London Math. Soc., 54(2):161–179, 1996.
[43] J. Lagarias and Y. Wang. Self-affine tiles in Rn . Adv. Math., 121:21–49, 1996.
[44] J. Lagarias and Y. Wang. Integral self-affine tiles in Rn II. lattice tilings. J. Fourier Anal. Appl.,
3:83–102, 1997.
[45] J. Luo. A connected tile has a locall connected boundary. preprint.
[46] J. Luo. A note on a self-similar tiling generated by the minimal Pisot number. Fractals, 10(3):335–339,
2002.
[47] J. Luo, S. Akiyama, and J. M. Thuswaldner. On the boundary connectedness of connected tiles. preprint.
[48] J. Luo, H. Rao, and B. Tan. Topological structure of self-similar sets. Fractals, 10:223–227, 2002.
[49] S.-M. Ngai and N. Nguyen. The Heighway dragon revisited. Discrete Comput. Geom., 29(4):603–623,
2003.
[50] S.-M. Ngai and T.-M. Tang. A technique in the topology of connected self-similar tiles. preprint.
[51] S.-M. Ngai and T.-M. Tang. Topology of connected self-similar tiles in the plane with disconnectedinteriors. preprint.
[52] A. Pethö. On a polynomial transformation and its application to the construction of a public key
cryptosystem. In Computational number theory (Debrecen, 1989), pages 31–43. de Gruyter, Berlin,
1991.
[53] B. Praggastis. Numeration systems and Markov partitions from self-similar tilings. Trans. Amer. Math.
Soc., 351(8):3315–3349, 1999.
[54] G. Rauzy. Nombres algébriques et substitutions. Bull. Soc. Math. France, 110(2):147–178, 1982.
[55] K. Scheicher and J. M. Thuswaldner. On the characterization of canonical number systems. Osaka
Math. J., to appear.
[56] K. Scheicher and J. M. Thuswaldner. Canonical number systems, counting automata and fractals.
Math. Proc. Cambridge Philos. Soc., 133(1):163–182, 2002.
[57] K. Scheicher and J. M. Thuswaldner. Neighbours of self-affine tiles in lattice tilings. In P. Grabner andW. Woess, editors, Proceedings of the Conference “Fractals in Graz”, pages 241–262, 2002.
[58] B. Solomyak. Dynamics of self-similar tilings. Ergodic Theory Dynam. Systems, 17(3):695–738, 1997.
[59] H. J. Song and B. S. Kang. Disclike lattice reptiles induced by exact polyominoes. Fractals, 7:9–22,
1998.

16

SHIGEKI AKIYAMA AND JÖRG M. THUSWALDNER[60] R. Strichartz and Y. Wang. Geometry of self-affine tiles I. Indiana Univ. Math. J., 48:1–23, 1999.
[61] T.-M. Tang. Arcwise connectedness of the boundaries of connected self-similar sets. preprint.
[62] W. Thurston. Groups, tilings and finite state automata. AMS Colloquium Lecture Notes, 1989.
[63] J. J. P. Veerman. Hausdorff dimension of boundaries of self-affine tiles in Rn . Bol. Mex. Mat., 3(4):1–24,
1998.
[64] A. Vince. Self-replicating tiles and their boundary. Discrete Comput. Geom., 21:463–476, 1999.
[65] A. Vince. Digit tiling of euclidean space. In Directions in Mathematical Quasicrystals, pages 329–370,
Providence, RI, 2000. Amer. Math. Soc.
[66] Y. Wang. Self-affine tiles. In K. S. Lau, editor, Advances in Wavelet, pages 261–285. Springer, 1998.
[67] Y. Wang. Wavelets, tiling, and spectral sets. Duke Math. J., 114(1):43–57, 2002.
Department of Mathematics, Faculty of Science, Niigata University, Ikarashi 2-8050,
Niigata 950-2181,Japan
E-mail address: akiyama@math.sc.niigata-u.ac.jp
Department of Mathematics and Statistics, Leoben University, Franz-Josef-Strasse 18,
A-8700 Leoben, AUSTRIA
E-mail address: joerg.thuswaldner@unileoben.ac.at