Dimensions of the Boundaries of Self-Similar Sets

Dimensions of the Boundaries of Self-Similar Sets

Ka-Sing Lau and Sze-Man Ngai

CONTENTS 1. Introduction

2. Boundary and Interior of F

3. The Finite Boundary Type Condition 4. Proof of Theorems 1.2 and 1.3 5. Examples on Computing Dimensions Acknowledgments

References

2000 AMS Subject Classification: Primary 28A78; Secondary 28A80

Keywords: Self-similar set, self-similar tile, self-affine tile,

finite type condition,finite boundary type condition, Hausdorff

dimension, box dimension.

We introduce a finite boundary type condition on iterated func- tion systems of contractive similitudes onR^d. Under this con- dition, we compute the Hausdorff dimension of the boundary of the attractor in terms of the spectral radius of some finite off- spring matrix. We describe how to construct such a matrix. We also show that, in this case, the box dimension equals the Haus- dorff dimension. In particular, this allows us to compute the Hausdorff dimension of the boundary of a class of self-similar sets defined by expansion matrices with noninteger entries.

1. INTRODUCTION

Let{φi}^qi=1 be an iterated function system (IFS) of con- tractive similitudes onR^d defined as

φ_i(x) =ρ_iR_ix+b_i, i= 1, . . . , q, (1—1) where 0<ρi<1 is the contraction ratio,Riis an orthog- onal transformation, andb_i ∈R^d. LetF be the unique self-similar set(orattractor) defined by{φi}^qi=1. Then

F =

q

i=1

φ_i(F) (1—2)

(see, e.g., [Hutchinson 81], [Falconer 90]).

For a subsetE⊆R^d, letE^◦,∂E, and diam(E) denote, respectively, the interior, boundary, and diameter ofE.

Let dimH(E), dimB(E), andH^s(E) be, respectively, the Hausdorffdimension, box dimension, and s-dimensional Hausdorff measure of E. We refer the reader to [Fal- coner 90] for these definitions. We also let #A denote the cardinality of a setA.

Much work has been done in computing the Hausdorff dimension of both the setFand the boundary ofF. The computation of the dimension of ∂F is of particular in- terest in connection with self-affine and self-similar tiles.

Suppose

φ_i(x) =A⁻¹(x+d_i), d_i∈D, (1—3) whereAis an expanding matrix (i.e., all eigenvalues are in modulus greater than 1) with integer entries and D

c A K Peters, Ltd.

1058-6458/2001$0.50 per page Experimental Mathematics12:1, page 13

is a finite set of vectors in Z^d, called the digit set. Un- der the assumption that A is conjugate to a similitude and{φi}^qi=1satisfies theopen set condition(see [Hutchin- son 81], [Falconer 90]), algorithms have been obtained to compute the dimensions of ∂F (see [Veerman 98], [Strichartz and Wang 99], [Kenyon et al. 99], and [Duvall et al. 00]). In this case, it is known that

dimH(∂F) = dimB(∂F) and H^s(∂F)>0, (1—4) where s = dimH(∂F) (see [Strichartz and Wang 99]).

Recently, He, Lau, and Rao have extended the compu- tations to allow #D>|det(A)| (see [He et al. 03]). A major difference in this case is that the open set condi- tion fails. Their method also includes an algorithm to determine whetherF has a nonempty interior. [Dekking and van der Wal 02] have studied such an extension for a class of recurrent iterated function systems.

The main purpose of this paper is to extend the results on the dimensions of the boundary of a self-similar set to more general IFSs that do not necessarily satisfy (1—3), nor the open set condition. Our basic framework is the

finite boundary type conditionto be introduced in Section

3. The φ_is in our setting can have different contraction ratios and (ρiRi)⁻¹ need not have integer entries. The finite boundary type condition is satisfied by afinite type IFS that possesses afinite type condition set containing the attractor. This allows us to include many interesting examples of IFSs with overlaps, in particular, the classes of examples in [Ngai and Wang 01, Theorems 2.7 and 2.9].

There are also IFSs that are offinite boundary type, but not offinite type. Our algorithm differs from the one in [He et al. 03] in that we do not make use of an auxiliary IFS, which is crucial there, but does not seem to exist for the IFSs in which we are mainly interested. An example of such an IFS isS₁(x) =ρx,S₂(x) =ρx+ (1−ρ), where 1/2<ρ<(√

5−1)/2 (see Example 5.2).

We need some standard notation. Let Σⁿ_q = {1,2, . . . , q}ⁿ and Σ^∗_q = ∪ⁿ≥0Σⁿ_q be the set of all finite words inΣq, whereΣⁿ_q is the set of all words of lengthn andΣ⁰_q contains only the empty word ∅. LetΣ^N_q denote the set of all infinite sequences (i1, i2, . . .) with ik ∈Σq. Forj∈Σⁿ_q, let|j|=ndenote thelengthofj. Fori∈Σ^m_q and j ∈ Σⁿ_q, let ij ∈ Σ^m+n_q be the concatenation of i withj. Forj= (j₁, . . . , j_n)∈Σⁿ_q, we use the convenient notation

φj:=φj1◦· · ·◦φjn, ρj:=ρj1· · ·ρjn, Rj:=Rj1◦· · ·◦Rjn, with ρ_∅ = 1 andφ_∅ =R_∅ := identity. Letρ= min{ρi: 1≤i≤q}and for allk≥0 define

Λ_k := j= (j₁, . . . , j_n)∈Σ^∗_q :ρ_j≤ρ^k<ρ_{(j1,...,jn−1)}

V^k := (φj, k) :j∈Λk

V :=

∞ k=0

V^k.

We call eachv= (φj, k)∈V^kavertex. Note that in [Ngai and Wang 01], a vertex (φ_j, k) is denoted equivalently by (ρjRj,φj(0), k). For v = (φj, k) ∈ V^k, we use the convenient notationφv:=φj. Note also thatΛ0contains only the empty word∅ andV0 contains only the vertex v= (φ_∅,0), with φ_∅(E) = φv(E) :=E for any E ⊆R^d. v= (φ_∅,0) is call theroot vertexand is denoted byv_root. Now let{φi}^qi=1 be defined as in (1—1). The following partition ofVk andV is similar to that in [He et al. 03].

But instead of utilizing an auxiliary system, we make use of a bounded open setΩcontainingF and invariant under {φ_i}^qi=1, i.e., ^q_i=1φ_i(Ω)⊆Ω. Note that such an Ωalways exists.

Fork≥0, define

Vk^◦ := v∈Vk:∃ ∈Nsuch that φv

u∈V

φu(Ω) ⊆

v∈Vk

φv(Ω)∀k ≥k ,

Vk^∂ := Vk\ Vk^◦, (1—5)

V^◦ :=

∞ k=0

Vk^◦, V^∂ :=

∞ k=0

Vk^∂.

We remark thatVk^◦, Vk^∂, V^◦, and V^∂ depend on Ω and we will fix such an Ω. Our first main result recovers a similar one in [He et al. 03].

Theorem 1.1. Suppose{φi}^qi=1 is an IFS of contractive similitudes on R^d as in (1—1). Let Ω be any invariant bounded open set containing F, and let Vk^◦ and Vk^∂ be defined with respect to Ωas in (1—5). Then

(a) F^◦=∅ if and only ifV^◦=∅;

(b) F^◦=

∞ k=0v∈Vk^◦

φ_v(F);

(c) ∂F =

∞ k=0v∈Vk^∂

φ_v(∂F) =

∞ k=0v∈Vk^∂

φ_v(F) =

∞ k=0v∈Vk^∂

φv(Ω).

To compute the Hausdorffdimension of∂F, we will in- troduce the notion offinite boundary type IFSs. Detailed

definitions will be given in Section 3. Examples offinite boundary type IFSs will be provided in Sections 3 and 5.

Under the finite boundary type condition, we can com- pute dim_H(∂F) by constructing afinite matrixB, called theboundary offspring matrix, to count #Vk^∂. Details of the construction ofB will be described in Section 4.

We remark here that in the construction ofB, the def- initions in (1—5) do not provide an effective algorithm for determining whether a given vertex belongs toV^◦orV^∂. Propositions 2.2 and 2.3 provide a geometric criterion, but it is difficult to implement unless the geometry ofF is simple. Some other partial results to overcome this difficulty will be discussed in Section 5. It would be very useful if an effective algebraic criterion can be found.

The main theorem below recovers all properties in (1—4). Moreover, in the caseF^◦=∅, the algorithm com- putes dimH(F), as in [He et al. 03].

Theorem 1.2. Assume that the IFS{φi}^qi=1in (1—1) is of

finite boundary type. LetB be a corresponding boundary

offspring matrix. Then

(a) dimH(∂F) = dimB(∂F) = lnλ_B

−lnρ, where λB is the spectral radius of B.

(b) H^s(∂F)>0 wheres= dim_H(∂F).

Theorem 1.2 is proved by first obtaining the box di- mension of∂F in terms of the spectral radius of B. To obtain the result for the Hausdorff dimension, we use an argument in [Ngai and Wang 01] to define a mass distribution on ∂F and prove Theorem 1.2(b), namely, H^s(∂F)>0 wheres= dimB(∂F). From this, we deduce that dimH(∂F) = dimB(∂F).

The problem of whether the Hausdorff dimension of

∂F is strictly less thand has been studied by Lagarias and Wang [1996] for self-affine tiles, by Keesling [1999]

for self-similar sets, and by Lau and Xu [2000] for attrac- tors of more general IFSs. For an IFS {φ}^qi=1 as defined in (1—1), it is proved in [Keesling 99, Theorem 2.1] and [Lau and Xu 00, Corollary 1.3] that if F^◦ =∅ and the similarity dimensionof{φ}^qi=1 isd, i.e.,

q

i=1

ρ^d_i = 1, (1—6)

then dimH(∂F) < d. In general, afinite type IFS does not satisfy (1—6). Nevertheless, the following result shows that the same conclusion holds.

Theorem 1.3. Let {φi}^qi=1 be a finite boundary type IFS of contractive similitudes on R^d with attractor F. Then dimH(∂F)< d.

Under the assumption of Theorem 1.3, dimH(F) =d implies that F^◦ = ∅. In some of our calculations, this serves as a criterion to determine whetherF^◦ is empty.

In Section 2, we partition the vertices inV intoV^◦and V^∂and prove Theorem 1.1. In Section 3, we introduce the finite boundary type condition and provide examples of IFSs satisfying this condition. In Section 4, we describe the construction of the boundary offspring matrixB. The rest of Section 4 is devoted to the proof of Theorems 1.2 and 1.3. In Section 5, we illustrate the algorithm by some examples.

2. BOUNDARY AND INTERIOR OFF

Throughout this section, we fix a bounded open set Ω containing the attractorF and invariant under{φi}^qi=1, i.e., ^q_i=1φi(Ω)⊆Ω. LetVk^◦, Vk^∂, V^◦ and V^∂ be defined with respect to thisfixedΩas in (1—5).

Proposition 2.1. Let {φ_i}^qi=1 be an IFS of contractive similitudes onR^das defined in (1—1). LetΩbe a bounded open set containingF and invariant under{φ_i}^qi=1. Then

(a) _v∈V

kφ_v(Ω), where k= 0,1,2, . . ., is a decreasing sequence.

(b) F =

∞ k=0|i|=k

φi(F) =

∞ k=0v∈Vk

φv(F)

=

∞ k=0v∈V^k

φv(Ω).

Proof: Part (a) follows easily from the invariance of Ω under {φi}^qi=1. The first two equalities in part (b) are well known. In fact, it follows by iterating (1—2) that

F =

|i|=k

φi(F) =

v∈Vk

φv(F) for allk≥0. (2—1)

To see the third equality, we letx∈ ^∞k=0 v∈V^kφ_v(Ω).

Then for each k ≥ 0, there exists some vk ∈ Vk such that x ∈ φvk(Ω). But limk→∞dH(φvk(Ω),φvk(F)) = 0, where d_H is the Hausdorff metric. Hence, x∈ F =

∞

k=0 v∈Vkφv(F). Thus

∞ k=0v∈Vk

φv(F)⊇

∞ k=0v∈Vk

φv(Ω).

The reverse inclusion is obvious and the proof is com- plete.

Proposition 2.2. Assume the same hypotheses of Propo- sition 2.1 and let v∈V. Then

v∈V^◦ ⇔ φv(F)⊆F^◦.

Proof: Let v ∈ Vk^◦. Using the definition of Vk^◦, there exists some such that

φv(F)⊆φv u∈V

φu(Ω) ⊆

v∈Vk

φv(Ω) for allk ≥k.

By Proposition 2.1(a), _v∈V

k φ_v(Ω), k = 0,1,2, . . ., is decreasing and hence, by using Proposition 2.1(b), we get

φv u∈V

φu(Ω) ⊆

∞ k=0v∈Vk

φv(Ω) =F.

Now, since φ_v(∪u∈Vφ_u(Ω)) is open, we have φv(∪^u∈V φu(Ω))⊆F^◦. Consequently,φv(F)⊆F^◦.

For the converse, suppose φv(F) ⊆ F^◦. Then by Proposition 2.1(b), we have

φv(F) =φv

∞ k=0u∈Vk

φu(Ω)

=

∞ k=0

φv u∈V^k

φu(Ω) ⊆F^◦.

Since φv(F) is compact and φv(∪^u∈Vkφu(Ω)), k = 0,1,2, . . ., is decreasing to φv(F), there exists some such that

φ_v

u∈V

φ_u(Ω) ⊆F^◦⊆

∞ k=0v∈Vk

φ_v(Ω).

This implies thatv∈V^◦.

Proposition 2.3. Assume the same hypotheses of Propo- sition 2.1 and let v∈V. Then

v∈V^∂ ⇔ φv(F)∩∂F =∅.

Proof: Using Proposition 2.2 and the fact thatφ_v(F)⊆ F, we obtain the following equivalences:

v∈V^∂ ⇔ v∈/V^◦

⇔ φv(F)⊆F^◦ ⇔ φv(F)∩∂F =∅. This proves the proposition.

By combining Propositions 2.1, 2.2, and 2.3, we can now prove Theorem 1.1.

Proof of Theorem 1.1: (a) If F^◦ = ∅, then it follows from Proposition 2.1(b) that there exists some k ≥ 0 andv∈Vk such thatφ_v(F)⊆F^◦. Proposition 2.2 now implies thatv∈Vk^◦and thus, V^◦=∅.

Conversely, assume V^◦ = ∅ and let v ∈ Vk^◦ for some k≥0. Then by Proposition 2.2 again,φ_v(F)⊆F^◦ and therefore,F^◦=∅.

(b) It follows directly from Proposition 2.2 that

∞ k=0v∈Vk^◦

φv(F)⊆F^◦.

It remains to show the reverse inclusion. Let x ∈ F^◦. Then by Proposition 2.1(b), for eachksufficiently large, there exists some v ∈ Vk such that x ∈ φ_v(F) ⊆ F^◦. Proposition 2.2 now implies thatv ∈Vk^◦ and therefore, x∈ ^∞k=0 v∈Vk^◦φv(F). This proves part (b).

(c) We first claim that

∂F ⊆

∞ k=0v∈Vk^∂

φv(∂F)⊆

∞ k=0v∈Vk^∂

φv(F)

⊆

∞ k=0v∈Vk^∂

φ_v(Ω). (2—2)

It suffices to prove the first inclusion. To see this, we notice from (2—1) and Proposition 2.2 that for allk≥0, F=

v∈Vk^◦

φ_v(F) ∪

v∈Vk^∂

φ_v(F) ⊆F^◦∪

v∈Vk^∂

φ_v(F) .

This implies that ∂F ⊆ v∈Vk^∂φv(F) for all k ≥ 0.

Hence, forx∈∂F, there exists somev∈Vk^∂ andy ∈F such thatx =φv(y). Obviously, y must belong to ∂F. Thus,x∈ ∪v∈Vk^∂φ_v(∂F) and thefirst inclusion in (2—2) follows. It remains to show

∞ k=0v∈Vk^∂

φ_v(Ω)⊆∂F.

Letxbelong to the set on the left of the inclusion. Then for eachk ≥0, there exists some v ∈Vk^∂ such that x∈ φ_v(Ω). By Proposition 2.3, φ_v(Ω)∩∂F =∅. Let y_k ∈ φ_v(Ω)∩∂F. Then for eachk≥0, we have

|x−y_k|≤ρ^kdiam(Ω).

Consequently,{y_k}is a sequence of points in∂F converg- ing tox. Thus x∈∂F. This proves (c) and completes the proof of Theorem 1.1.

3. THE FINITE BOUNDARY TYPE CONDITION In this section, we define thefinite boundary type con- dition and provide some examples. We continue to use the notation introduced in Section 1.. For the reader’s convenience, we willfirst recall the definition of thefinite type condition (see [Ngai and Wang 01]).

Fix any nonempty bounded open set Ω which is in- variant under {φi}^qi=1 (Ω need not contain F). Two vertices v,v ∈ Vk are neighbors (with respect to Ω) if φv(Ω)∩φv(Ω) =∅. The set of vertices

Ω(v) :={v :v is a neighbor ofv}

is called theneighborhoodofv(with respect toΩ). Define an equivalence relation onV. Two verticesv ∈Vk and v ∈ V^k are equivalent, denoted by v ∼ v (or more precisely by v ∼τ v), if there exists a similitude τ : R^d → R^d (depending onv and v) of the form τ(x) = ρ^k−kU x+c, where U is orthogonal and c ∈ R^d, such that

φv =τ◦φvand φu :u ∈Ω(v) = τ◦φu :u∈Ω(v) . We denote the equivalence class containing v by [v] :=

[v]_Ω and call it theneighborhood typeofv(with respect to Ω). (Note that in [Ngai and Wang 01], v ∼τ v is denoted byΩ(v)∼^τ Ω(v) and [v]Ωis denoted by [Ω(v)]

instead.)

Recall that an IFS of the form (1—1) is said to be of

finite typeif there exists a nonempty bounded invariant

open set Ωsuch thatN :={[v] :v∈V} is afinite set.

Ωis called afinite type condition set(or simplyFT-set).

To describe thefinite boundary type condition, we will fix a bounded open invariant set Ω for {φi}^qi=1 and as- sume in addition thatF ⊆Ω. Note that such anΩalways exists. LetVk^◦,Vk^∂,V^◦,V^∂ be defined with respect to this

fixedΩas in (1—5). It is a key property that if v∼τ v,

then v ∈ V^∂ if and only if v ∈ V^∂ (Proposition 3.3).

This is proved by using Proposition 2.3 and by analyzing the image ofφ_v(F)∩F underτ. Forv∈V, define Ω^e(v) := u∈Ω(v)\ {v}:φu(∂F)∩φv(∂F)∩F^◦ =∅ . Also, foru∈Ω^e(v), define

∂Fu,v:= x∈∂F :φu(x)∈φv(∂F)∩F^◦ . Then we have the following useful identity:

Proposition 3.1. LetF be the attractor of an IFS{φi}^qi=1

of contractive similitudes onR^d, and letΩ be a bounded open invariant set containingF. Then for anyv∈V,

φv(F)∩∂F = φ_v(∂F)\

u∈Ω(v)

φ_u(F^◦)∪

u∈Ω^e(v)

φ_u(∂F_u,v) . (3—1) Proof: Let x ∈ φv(F) ∩ ∂F. Then x ∈ φv(∂F) because φ_v(F^◦) ⊆ F^◦. Since _u∈Ω(v)φ_u(F^◦) ∪

u∈Ω^e(v)φu(∂Fu,v) ⊆F^◦, x must belong to the set on the right side of (3—1).

Conversely, letxbelong to the set on the right side of (3—1). Thenx∈φv(∂F)⊆φv(F). To show thatx∈∂F, letx=φ_v(y) wherey∈∂F. Consider the following two cases.

Case 1. x ∈ u∈Ω(v)\{v}φ_u(F). In this case, x ∈ ∪u∈Ω(v)\{v}φu(∂F) since x ∈ ∪u∈Ω(v)\{v}φu(F^◦).

Hence, x = φ_u(w) for some u ∈ Ω(v)\ {v} and some w ∈ ∂F. But x ∈ u∈Ω^e(v)φu(∂Fu,v) implies that {x}∩F^◦=∅. Consequently,x∈∂F.

Case 2. x∈ u∈Ω(v)\{v}φ_u(F). In this case, x∈ ∂F because y ∈ ∂F, φv is a similitude, and there are no overlapping φ_u(F) in a sufficiently small neighborhood ofx.

Proposition 3.2. Let {φi}^qi=1 be an IFS of contrac- tive similitudes on R^d with attractor F, and let Ω be a bounded open invariant set containing F. Assume v ∈ V^k, v ∈ V^k, and v ∼^τ v. Let u ∈ Ω(v) and u ∈Ω(v)satisfyφ_u =τ◦φ_u. Then

(a) u∈Ω^e(v)if and only ifu ∈Ω^e(v).

(b) ∂Fu,v=∂Fu,v.

Proof: (a) Letu∈Ω^e(v). Thenφu(∂F)∩φv(∂F)∩F^◦ =

∅. Hence, there exist somez ∈φ_u(∂F)∩φ_v(∂F) and a ballBδ(z) such that

B_δ(z)⊆

w∈Ω(v)

φ_w(F)⊆F. (3—2)

Writez=φ_u(x) =φ_v(y) withx, y ∈∂F. Then φ_u(x)∈φ_u(∂F)∩φ_v(∂F)

⇒ τ◦φ_u(x)∈τ◦φ_u(∂F)∩τ◦φ_v(∂F).

Moreover, by (3—2), we have B_δ φ_u(x) =B_δ φ_v(y) ⊆

w∈Ω(v)

φ_w(F)⊆F.

Letrbe the similarity ratio ofτ. Then we haveφu(x)∈ φ_u(∂F)∩φ_v(∂F) and

Brδ φu(x) =Brδ φv (y) ⊆

w∈Ω(v)

φw(F)⊆F.

(The first inclusion above is because w ∈ Ω(v) if and

only ifw ∈Ω(v) whereφ_w =τ◦φ_w.) This implies that φu(x)∈φu(∂F)∩φv(∂F)∩F^◦and thereforeφu(∂F)∩ φ_v(∂F)∩F^◦ = ∅. Hence, u ∈ Ω^e(v). The converse follows by symmetry.

(b) Again let r denote the similarity ratio of τ. Let x∈∂Fu,v. Then

x∈∂F andφu(x)∈φv(∂F)∩F^◦

⇒ x∈∂F, φu(x)∈φv(∂F) and there is a ball Bδ φu(x) ⊆

w∈Ω(v)

φw(F)⊆F

⇒ x∈∂F, τ◦φu(x)∈τ◦φv(∂F) and τ Bδ φu(x) ⊆

w∈Ω(v)

τ◦φw(F)

⇒ x∈∂F, φ_u(x)∈φ_v(∂F) and Brδ φu(x) ⊆

w∈Ω(v)

φw(F)⊆F

⇒ x∈∂F andφu(x)∈φv(∂F)∩F^◦

⇒ x∈∂Fu,v.

Thus, ∂Fu,v ⊆∂Fu,v. The reverse inclusion follows by symmetry and this completes the proof of the proposi- tion.

Proposition 3.3. Assume the same hypotheses of Propo- sition 3.2. Then

τ φv(F)∩∂F =φv (F)∩∂F.

Consequently,v∈V^∂ if and only if v ∈V^∂. Proof: Equality (3—1) implies that

τ φ_v(F)∩∂F = τ◦φ_v(∂F)\

u∈Ω(v)

τ◦φ_u(F^◦)∪

u∈Ω^e(v)

τ◦φ_u(∂F_u,v) . (3—3) Since u ∈ Ω(v) if and only if u ∈ Ω(v) where φu = τ◦φ_u, we have

u∈Ω(v)

τ◦φ_u(F^◦) =

u∈Ω(v)

φ_u(F^◦). (3—4)

Next, by using Proposition 3.2, we have

u∈Ω^e(v)

τ◦φu(∂Fu,v) =

u∈Ω^e(v)

φu (∂Fu,v). (3—5) Lastly, combining Equations (3—3), (3—4), (3—5), and Proposition 3.1 yields

τ φv(F)∩∂F = φv(∂F)\

u∈Ω(v)

φu(F^◦)∪

u∈Ω^e(v)

φu(∂Fu,v)

=φ_v(F)∩∂F.

This proves the stated equality. The last assertion of the proposition follows by combining this result with Propo- sition 2.3.

We call

N^◦:= [v] :v∈V^◦ and N^∂ := [v] :v∈V^∂ the collections of all interior neighborhood types and boundary neighborhood types, respectively. According to Proposition 3.3,N =N^◦∪N^∂ andN^◦∩N^∂ =∅.

Let G and G^R be the infinite graphs defined in [Ngai and Wang 01] as follows. Both G and G^R have V as the set of all vertices. The edges in G are defined as follows. Letv∈V^k and v ∈V^k+1. Suppose there exist j∈Λ_k, j ∈Λ_k+1, andk∈Σ^∗_q such that

v= (φj, k), v = (φj, k+ 1), and j =jk.

Then we connect a directed edgek:v→v. We call v aparentofv andv anoffspring(ordescendant) ofv.

Thereduced graphGR is obtained fromGby removing all but the smallest (in the lexicographical order) directed edge going to a vertex.

We introduce the graphs G^∂ and G^∂R. The vertex set for both graphs isV^∂and the directed edges inG^∂ andGR^∂

are the restrictions of the edges inGandGR, respectively, toV^∂.

The following proposition says that equivalent bound- ary vertices generate the same number of offspring of each boundary neighborhood type.

Proposition 3.4. Let v ∈ Vk^∂ and v ∈ Vk^∂ such that [v] = [v]. Let u₁, . . . ,u_m ∈ Vk+1^∂ be the offspring of v and let u₁, . . . ,u ∈Vk^∂+1 be the offspring of v in GR^∂. Then

[ui] : 1≤i≤m = [u_i] : 1≤i≤ counting multiplicity. In particular,m= .

Proof: Let u1, . . . ,um,um+1, . . . ,us be all the offspring ofv in GR, withu1, . . . ,um∈Vk+1^∂ andum+1, . . . ,us∈ Vk+1^◦ . Similarly, let u₁, . . . ,u ,u₊₁, . . . ,u_s be all the offspring of v in GR, with u₁, . . . ,u ∈ Vk^∂+1 and u₊₁, . . . ,u_s∈Vk^◦+1. Letv∼^τ v withτ◦φui=φu_i for all 1≤i≤s. Then by [Ngai and Wang 01, Proposition 2.2],

[ui] = [u_i] for all 1≤i≤s.

By Proposition 3.3,

ui∈Vk+1^∂ if and only if u_i∈Vk^∂+1. Consequently,m= . This proves the proposition.

Definition 3.5. An IFS {φi}^qi=1 of contractive simili- tudes onR^dwith attractorF is said to be offinite bound- ary type if there exists a bounded invariant open set Ω containing F such that N^∂ is a finite set. In this case, we say thatΩis afinite boundary type condition set (or simply anFBT-set).

The following proposition follows easily from defini- tions.

Proposition 3.6. Let {φ_i}^qi=1 be afinite type IFS of con- tractive similitudes on R^d. Assume that there exists an FT-setΩcontainingF. Then{φi}^qi=1 is offinite bound- ary type.

Remark 3.7. Afinite boundary type IFS is not necessarily

offinite type. We will illustrate this in Example 5.2. We

do not know whether each finite type IFS is of finite boundary type.

Combining Proposition 3.6 and [Ngai and Wang 01, Theorems 2.7 and 2.9], we obtain the following classes of finite boundary type IFSs.

LetMd(R) andMd(Z) be the sets of alld×dmatrices with entries inRandZ, respectively.

Example 3.8. Let{φi}^qi=1 be an IFS of contractive simil- itudes onR^d of the form

φi(x) =Aⁿⁱx+bi, 1≤i≤q,

where A is a contractive similitude in Md(R) and ni ∈ N. Assume that A⁻¹ ∈ M_d(Z) and all b_i ∈ Z^d. Then {φi}^qi=1is offinite boundary type and any bounded open invariant set containingF is an FBT-set.

Example 3.8 generalizes the IFSs studied in [Veerman 98], [Kenyon et al. 99], [Strichartz and Wang 99], and

[Duvall et al. 00], as well as the self-similar ones in [He et al. 03]. The following example allows us to include another interesting family offinite boundary type IFSs.

Recall that aPisotnumber is an algebraic integer greater than 1 whose algebraic conjugates are all in modulus less than one. Let Z[x] denote the ring of polynomials over the integersZ.

Example 3.9. Let{φ_i}^qi=1be an IFS of contractive simil- itudes onR^d of the form

φi(x) =rⁿⁱRix+bi, 1≤i≤q,

wherer⁻¹ is a Pisot number and for 1≤i≤q, n_i ∈N andRi is orthogonal. Assume that {Ri}^qi=1 generates a

finite groupG, and

G{b_i: 1≤i≤q}⊆c₁Z[r⁻¹]× · · · ×c_dZ[r⁻¹] for somec₁, . . . , c_d∈R. Then{φ_i}^qi=1 is offinite bound- ary type and any bounded open invariant set containing F is an FBT-set.

4. PROOF OF THEOREMS 1.2 and 1.3

We begin by stating two lemmas without proof. The following lemma can be obtained as [Ngai and Wang 01, Lemma 3.1].

Lemma 4.1. Suppose {φi}^qi=1 is a finite boundary type IFS of contractive similitudes on R^d and let V^∂ be de-

fined with respect to an FBT-set Ω. Then for any posi-

tive constantsK₁, K₂, there exists a positive integerM = M(K1, K2)such that for any integerk≥0 and any sub- setsU, E ⊆R^d with diam(U)≤K1ρ^k andE ⊆BK2(0), we have

# v∈Vk^∂ :φ_v(E)∩U =∅ ≤M.

Using Lemma 4.1 and a similar argument as in [Ngai and Wang 01, Lemma 3.2], we have

Lemma 4.2. Assume that {φi}^qi=1 as given in (1—1) is a

finite boundary type IFS of contractive similitudes onR^d

with attractor F. Let Vk^∂ be defined with respect to an FBT-setΩ. Then

lim inf

k→∞

ln #Vk^∂

−klnρ ≤dim_B(∂F)

≤dim_B(∂F)≤lim sup

k→∞

ln #Vk^∂

−klnρ.

In view of Lemma 4.2, we need to evaluate #Vk^∂. We achieve this by using a matrix B. The matrix B has rows and columns indexed by the boundary neigh- borhood types. Suppose that the IFS (1—1) is of fi- nite boundary type and let Ω be an FBT-set. We la- bel the boundary neighborhood types as {T1^∂, . . . ,TN^∂}. The entries of B = {b_ij} are defined as follows. For any 1 ≤ i ≤N, take a vertex v ∈ V^∂ of GR^∂ such that [v] = Ti^∂. Let u₁, . . . ,u_n be the offspring of v in GR^∂. Then

b_ij= # : 1≤ ≤n, [u ] =Tj^∂ .

By Proposition 3.4, b_ij is independent of the choice of the vertexv.

Definition 4.3. We call the matrixB the boundary off- spring matrixof thefinite boundary type IFS (1—1) with respect toΩ.

We label the boundary neighborhood type of [v_root] as T1^∂. Then

#Vk^∂ =e^T₁B^k1, (4—1) where 1= [1, . . . ,1]^T and e1= [1,0, . . . ,0]^T are vectors in R^N.

Theorem 4.4. Let {φi}^qi=1 be a finite boundary type IFS of contractive similitudes on R^d with attractorF. Then

dim_B(∂F) = dimB(∂F) = dimB(∂F) = lnλB

−lnρ, whereλB is the spectral radius of the boundary offspring matrixB (with respect to Ω).

Proof: The proof is standard; we only include a brief sketch. Since all vertices inGR^∂ are descendants ofv_root, we have

klim→∞(e^T₁B^k1)^1/k =λ_B.

Hence, for allδ >0 sufficiently small and all integers k sufficiently large, we have

(λB−δ)^k<e^T₁B^k1<(λB+δ)^k. Combining this with (4—1) and Lemma 4.2, we get

ln(λB−δ)

−lnρ ≤dim_B(∂F)≤dim_B(∂F)≤ ln(λB+δ)

−lnρ . The result follows by lettingδ→0.

Theorem 4.4 shows that lnλB/(−lnρ) is an upper bound for dim_H(∂F). We will show that it is also a

lower bound. Define a path in GR^∂ to be an infinite se- quence (v₀ = vroot,v1,v2, . . .) such that vj ∈ Vj^∂ for all j ≥ 0 and vj+1 is an offspring of vj in GR^∂. Let P^∂ denote the set of all paths in GR^∂. For given vertices v0 =vroot,v1, . . . ,vk such that vj+1 is an offspring of v_j inGR^∂, we call the set

Iv0,v1,...,vk := (u₀,u₁, . . .)∈P^∂ :u_j =v_j for 0≤j≤k a branch. It follows from the definition of GR^∂ that the path fromv0 tovk is unique. We can therefore denote

I^vk :=I^v0,v1,...,vk.

Theorem 4.5. Let {φi}^qi=1 be a finite boundary type IFS of contractive similitudes on R^d and let s = dim_B(∂F).

ThenH^s(∂F)>0.

Proof: The proof is similar to that of [Ngai and Wang 01, Theorem 1.2]; we outline it here for completeness.

We first construct a mass distribution µonP^∂ using

the branches. LetT1^∂, . . . ,TN^∂ be the set of all the dis- tinct boundary neighborhood types with T1^∂ being the neighborhood type of [vroot]. LetB be the correspond- ing boundary offspring matrix with respect to Ω. By Theorem 4.4, we have

s= lnλB

−lnρ,

where λB is the spectral radius of B. Since all vertices in GR^∂ are descendants of v_root and all boundary neigh- borhood types are generated byT1^∂, we mayfind aλB- eigenvectorx= [c₁, . . . , c_N]^T ofB such that c₁>0 and c_j ≥0 for all 2≤j ≤N. Letx^∗= [a₁, . . . , a_N]^T where aj=cj/c1. Then we have

Bx^∗=λx^∗, aj ≥0, and a1= 1.

We now define a mass distribution on P^∂. For each branchI^vk where vk∈Vk^∂ such that [vk] =Ti^∂ we let

µ(I^vk) :=λ^−kai.

(Note that µ(I^vroot) = λ⁰a1 = 1.) We leave it as an exercise to show thatµis indeed a mass distribution on P^∂.

Next, we transport µ to a mass distribution on ∂F. Recall from Theorem 1.1(c) that

∂F =

∞ k=0v∈Vk^∂

φ_v(F). (4—2)

Notice thatφv(F)⊆φv(F) ifv ∈Vk+1^∂ is an offspring, in GR^∂, of v ∈Vk^∂. The expression in (4—2) implies that each path (v0 = vroot,v1,v2, . . .) ∈ P^∂ corresponds to a point x∈∂F, which is the unique point _k≥0φ_vk(F).

We call (v0,v1, . . .)∈P^∂ anaddress ofx. For a subset U ⊆R^d, letC(U) be the set of all addresses of points in

∂F∩U, and define

µ^∗(U) :=µ C(U) .

Thenµ^∗ is a mass distribution supported on∂F. Finally, we apply the mass distribution principle by using µ^∗. Let 0 < δ < ρ. For any set U ⊆ R^d with diam(U) ≤ δ, assume that ρ^k+1 ≤ diam(U) < ρ^k. Lemma 4.1 implies that U can intersect no more than M of the φv(F) with v ∈ Vk^∂, where M is a fixed con- stant independent of k. Let v₁, . . . ,v , ≤ M, be the vertices inVk^∂ such thatU∩φvj(F) =∅. Then, by (4—2) and the definition ofµ^∗, we have

µ^∗(U) =µ^∗(U∩∂F)≤

j=1

µ^∗ U∩φvj(F)

≤

j=1

µ(I^vj)≤Mλ^−k max

1≤i≤N{ai}.

Nowλ⁻¹=ρ^s implies that

λ^−k=ρ^ks=ρ^−sρ^(k+1)s≤ρ^−s diam(U) ^s. It follows that

µ^∗(U)≤C diam(U) ^s,

whereC=Mρ^−smax1≤i≤N{ai}. The mass distribution principle implies that

H^s(∂F)≥µ^∗(∂F)/C >0, proving the theorem.

Proof of Theorem 1.2: Theorem 4.4 implies that dim_H(∂F)≤dim_B(∂F) =s= lnλ_B

−lnρ.

Theorem 4.5 implies that dim_H(∂F) ≥ s. This proves part (a). Part (b) is proved in Theorem 4.5.

The proof of Theorem 1.3 uses a technique in [Ngai and Wang 01, Theorem 1.3].

Proof of Theorem 1.3: Suppose that dimH(∂F) = d.

Then by Theorem 1.2(b), H^d(∂F) > 0. Hence, there exists a Lebesgue pointx^∗∈∂F and

ck :=H^d(∂F∩B_ρ^k(x^∗))

H^d(B_ρ^k(x^∗)) →1 as k→ ∞, (4—3)

whereρ= min{ρi : 1≤i≤q}. By Theorem 1.1(c),

∂F=

∞ k=0v∈Vk^∂

φ_v(∂F). (4—4) Define Uk := {v ∈ Vk^∂ : φ_v(∂F)∩B_ρk(x^∗) = ∅}. By Lemma 4.1, #U^k ≤M for someM independent ofk. For eachk≥0, define an expansive similitude τ_k :R^d→R^d byτk(x) :=ρ^−kx−ρ^−kx^∗. Then

U^k = v∈Vk^∂ :τk◦φv(∂F)∩B1(0) =∅ . (4—5) Moreover, by (4—4), τ_k(∂F ∩ B_ρk(x^∗)) ⊆ ∪v∈Uk(τ_k ◦ φv(∂F)∩B1(0)).DefineEk :=∪^v∈Ukτk◦φv(∂F). Then τ_k(∂F∩B_ρk(x^∗))⊆E_k∩B₁(0) and by (4—3),

H^d(E_k∩B₁(0))≥c_kH^d(B₁(0)).

Choose a subsequence{Ekj}of{Ek}which converges to a compact setEin the Hausdorffmetric. Then, by using the fact thatE=∩^∞n=0∪^j≥nEkj, we have

H^d E∩B1(0) ≥ lim

j→∞H^d Ekj∩B1(0)

≥ lim

j→∞ckjH^d B1(0) =H^d B1(0) . Hence,E∩B₁(0) =B₁(0). Now, E_kj is a union of no more thanM setsτkj ◦φv(∂F), withv∈Ukj and each τkj ◦φv being a similitude with ratio between ρ and 1.

Moreover, (4—5) implies that theseτ_kj ◦φ_v(∂F) are uni- formly bounded. By compactness, we haveE=∪^L=1H , whereL≤M and eachH is the limit of some sequence {τkj ◦φv(∂F) :v∈U^kj}. Hence, eachH =σ(∂F) for some similitudeσ onR^d. SinceE^◦=∅, we haveH^◦=∅ for some . Therefore, (∂F)^◦ = ∅. This contradiction completes the proof.

5. EXAMPLES ON COMPUTING DIMENSIONS In this section, we illustrate the algorithm by some ex- amples. In actual computations, it is often difficult to determine whether a neighborhood type belongs to N^◦ orN^∂. Proposition 5.1 provides some partial results. Let F be the attractor of an IFS {φi}^qi=1 on R^d as defined in (1—1) and letΩ⊇F be a bounded open invariant set.

Wefirst define a partial order≤onN. Letu,v∈Vwith

Ω(u) ={u0,u1, . . . ,um} and Ω(v) ={v0,v1, . . . ,vn}, whereu0=u,v0=v, andm≤n. We say thatu≤vif there exists a similitudeσ(x) =ρ^kU x+c, where k∈Z, U is orthogonal andc∈R^d, such that

σ◦φu0 =φv0 and

{σ◦φui:i= 0,1, . . . , m}⊆{φvi:i= 0,1, . . . , n}.

≤is a partial order on V. Also,≤extends naturally to N. We say that a neighborhood type [v]∈N ismaximal if

[u]≤[v] for all u∈[v].

Proposition 5.1. Assume the above conditions and let T,T1,T2∈N. The following hold.

(a) T ∈ N^◦ if and only if all offspring of T belong to N^◦. Equivalently, T ∈N^∂ if and only if some off- spring of T belongs toN^∂.

(b) If T1≤T2 andT2∈N^∂, thenT1∈N^∂. (c) If T1≤T2 andT1∈N^◦, thenT2∈N^◦.

(d) Assume thatρ_i,i= 1, . . . , q, are exponentially com- mensurable. If F^◦ = ∅ and T is maximal, then T ∈N^◦.

Proof: (a), (b), and (c) follow from Propositions 2.2 and 2.3. To prove (d), it suffices to show that ifT = [v]∈N^∂, thenT is not maximal. Let

v= (φ_j, k) andΩ(v) ={v_i:i= 0,1, . . . , n}withv₀:=v.

Since F^◦ = ∅ and the ρi are exponentially commensu- rable, there exists some index i and some ∈ N such that

ρ_i=ρ and φ_i(Ω)⊆F^◦.

Note that forj = 0,1, . . . , n, φi◦φvj ∈V^+k, and (φi◦ φvj, +k) are neighbors of (φi◦φv0, +k). Let u = (φij, +k). ThenT = [v]≤[u]. Since [u]∈N^◦,T = [u]

and thereforeT is not maximal.

We remark that [vroot]∈N^∂ and that the converse of Proposition 5.1(d) is false (see Example 5.3).

Let{φ}^qi=1 be afinite boundary type IFS of contrac- tive similitudes onR^d andfix an FBT-setΩ. Letv∈Vk^∂

with [v] =T^∂. Supposevgeneratesnjoffspring inVk+1^∂

of boundary neighborhood types Tj^∂, 1≤j ≤m. Then we denote this by

T^∂ →n1T1^∂ +n2T2^∂+· · ·+nmTm^∂.

By Proposition 3.4, this relation is independent of the choice of the representativev.

The following simple example illustrates the fact that

afinite boundary type IFS need not be offinite type.

Example 5.2. Consider the IFS

φ₁(x) =ρx, φ₂(x) =ρx+ (1−ρ), where 1/2<ρ<(√

5−1)/2≈0.618. . . . Then{φ1,φ2} is offinite boundary type.

Proof: Note that{φ1,φ2}is not necessarily offinite type.

In fact, it is not offinite type if ρis transcendental. To see this, wefirst observe that ifρis transcendental, then the iteratesφ_v(0),v∈Vk, do not overlap. Consequently, for eachk, there are 2^k distinct iterates. Now, by the pi- geonhole principle, some subinterval of {0,1} of length ρ^k must contain at least (2ρ)^k distinct iterates. Equiva- lently, some neighborhood Ω(v) withv ∈V^k must con- tain at least (2ρ)^k distinct vertices in Vk. Therefore, {φ1,φ2} cannot be of finite type. In fact, it does not have the weak separation property (see [Lau and Ngai 99]).

Obviously, the attractor F = [0,1]. Also, for any

>0, Ω = (− ,1 + ) is a bounded open invariant set containing F. We will choose > 0 to be sufficiently small, say,

0< <(1−ρ−ρ²)/2. (5—1) Let T1^∂ := [v_root]. v_root generates two offspring inGR^∂, namely,

v₁= (φ₁,1) and v₂= (φ₂,1).

Denote [v1] and [v2] byT2^∂ and T3^∂, respectively. Then T1^∂ →T2^∂+T3^∂.

Iterating one more time and using assumption (5—1), we easily get

T2^∂ →T2^∂ and T3^∂ →T3^∂.

Since no new boundary neighborhood types can be gen- erated, we conclude that {φ1,φ2} is of finite boundary type. Moreover, the boundary offspring matrix is

B =



0 1 1 0 1 0 0 0 1





with λB = 1. Hence, dimH(∂F) = dimB(∂F) = ln 1/(−lnρ) = 0,as expected.

The common contraction ratio of the similitudes in the following example is the reciprocal of a Pisot number.

Example 5.3. LetF be the attractor of the IFS{φi}⁴i=1

defined by

φ1(x) =r²x, φ2(x) =r²x+r², φ3(x) =r²x+r, φ4(x) =r²x+ 1

r², wherer= (√

5−1)/2 is the reciprocal of the golden ratio (see Figure 1). Then

dimH(∂F) = dimB(∂F) = logλB

−log(r²) = 0.6007712354. . . ,

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 k=0

k=1

k=2

k=3

. . . F

FIGURE 1. Thefirst three iterations of the interval [0, r⁻³] under the IFS in Example 5.3, wherer= (√

5−1)/2 is the reciprocal of the golden ratio. Vertices are represented by intervals and are slightly separated vertically. The attractorF is shown at the bottom of thefigure.

whereλ_Bis the largest real zero of the polynomialp(x) = x⁷−x⁶−2x⁵+x⁴+x−1.

Proof: By Example 3.9, {φi}⁴i=1 is of finite boundary type. It can be checked directly that the attractor of the subsystem{φ₁,φ₂,φ₃}is the interval [0,1] and therefore, (0,1)⊆F; moreover,F ⊆[0, r⁻³]. We letΩ= (− , r⁻³+ ) be an FBT-set with = 10⁻⁵. We use Mathematica

tofind all the neighborhood types inN. There are 62 of

them. Using Propositions 2.2 and 2.3, we can partition N into N^◦∪N^∂.

First, we use Proposition 2.2 tofind as many interior neighborhood types as possible. Note that if E ⊆ F^◦, then ∪⁴i=1φi(E) ⊆ F^◦. Using this and the fact that (0,1) ⊆ F^◦, we can enlarge the known subset of F^◦. Unfortunately, the largest subinterval ofF^◦ that can be found by using this method alone is (0, a), whereacan be taken to be 1.236. In fact,a <1+r³= 1.2360679775. . . .

To enlarge this known subinterval of F^◦, we will prove the following claim

Claim 5.4. (a) 1 + r³ ∈ F^◦. (b) 1 + r³ + r⁵(=

1.3262379212. . .)∈F^◦.

Proof: We will prove (a); the proof for (b) is similar. It follows from iterating the φ_is that 1 +r³ = φ_v0(0) for somev0∈V³. Hence, there exists some 0>0 such that (1 +r³, ₀)∈F^◦. To show that 1 +r³∈F^◦, we will show that there exists an increasing sequence{Rk} such that (0, Rk)⊆F^◦and limk→∞Rk = 1 +r³.

First, a direct iteration shows that 1 +r³=φv1(0) for some v1∈ V⁵. Let T = [v1]. Upon one more iteration, we notice thatv1 generates an offspringv2which is also of neighborhood typeT, and moreover, φv2(0) = 1 +r³ (see Figure 2). v₂has four left neighborsu₁,u₂,u₃,u₄∈ V⁶, with