MULTIFRACTAL DECOMPOSITIONS

OF DIGRAPH RECURSIVE FRACTALS

G. A. Edgar and R. Daniel Mauldin

The Ohio State University and University of North Texas

November 25, 1991

Abstract. We prove that the multifractal decomposition behaves as expected for a family of sets K known as digraph recursive fractals, using measures μ of Markov type. For each value of a parameter α between a minimum α_{min} and maximum α_{max}, we define “multifractal components” K^{(α)} of K, and show that they are fractals in the sense of Taylor. The dimension f(α) of K^{(α)} is computed from the data of the problem. The typical concave “multifractal f(α)” dimension spectrum curve results. Under appropriate disjointness conditions, the multifractal components K^{(α)} are given by:

K^{(α)} = \{ x ∈ K : lim_{ε↓0} \frac{log μ(B_{ε}(x))}{log diam B_{ε}(x)} = α \} ,

i.e., K^{(α)} consists of those points where μ has pointwise dimension α.

Contents

Introduction

1. The Setting 1.1. The sets 1.2. The models 1.3. Measures of Markov type 1.4. Hausdorff and packing dimensions 1.5. Multifractal decomposition

2. An Example

3. Auxiliary Functions

4. Proof of the Dimension Theorem

1991 Mathematics Subject Classification. 28A80. Key words and phrases. Fractal, multifractal, Hausdorff dimension, packing dimension. Research supported in part by NSF grants DMS 87-01120 and DMS 90-007035

Typeset by AMS-TEX

5. Other Remarks References

Introduction

It has been argued in the physics literature (for example Halsey, et. al. [9]) that certain fractals carrying a natural measure may be analyzed in terms of the scaling properties of the measure. The fractal K should contain “singularities of strength α” for certain values of a parameter α; a fractal dimension f(α) describes how densely those singularities are distributed. Computations show a typical concave shape for this function f(α), sometimes known as a “dimension spectrum”.

Here we attempt to provide a mathematical setting for this sort of “multifractal deomposition”. We begin with a (possibly fractal) nonempty compact set K in Euclidean space ℝ^{n}, and a measure μ on K. For example, we might have a dynamical system where, in the limit, the trajectories approach a (strange) attractor K, and the ergodic time-averages along the process approach a corresponding measure μ. Or we might imagine an iterated function system, which approaches its attractor K as points are chosen according to the “random method” or the “chaos game”; the time-averages again converge to a natural measure on the attractor.

When a set K has fractal dimension d and supports a “natural” finite measure μ, we may expect “typically”, for x ∈ K and ε > 0, that the measure μ(B_{ε}(x)) of the ball of radius ε centered at x is roughly equal to (2ε)^{d}, the dth power of the diameter of the ball. This might mean that

0 < lim sup_{ε↓0} \frac{μ(B_{ε}(x))}{( diam B_{ε}(x))^{d}} < ∞

or, more generally, that

lim_{ε↓0} \frac{log μ(B_{ε}(x))}{log diam B_{ε}(x)} = d

for all x ∈ K. Multifractal decomposition will be interesting exactly when this does not happen—for many different values of the parameter α, the set

K^{(α)} = \{ x ∈ K : lim_{ε↓0} \frac{log μ(B_{ε}(x))}{log diam B_{ε}(x)} = α \}

is non-trivial. The sets K^{(α)} may be thought of as the multifractal components of K. (We use a slightly different definition below, however; it coincides with this when there is a disjointness property.) The Hausdorff dimension of K^{(α)} is called f(α); this function describes the dimension spectrum.

It is important to note that we are using the Hausdorff dimension of K^{(α)}, and not the box dimension. Typically, all the sets K^{(α)} are dense in K, so they all have box dimension equal to the box dimension of K itself. But the Hausdorff dimension f(α) varies with α.

There are some special cases (the “digraph recursive fractals”) when all of the Hausdorff dimension computations can be carried out explicitly. Those computations are carried out here. They do, indeed, show the characteristic convex multifractal dimension spectrum curve f(α). The packing dimension and the Hausdorff dimension of the multifractal component K^{(α)} agree, so it is a “fractal” in the sense of Taylor

4 G. A. EDGAR AND R. DANIEL MAULDIN

[16]. The work here extends the case computed by Cawley & Mauldin [4]. It was, in turn, suggested by the heuristics of Halsey, et. al. [9]. Some interesting digraph recursive fractals are found in [3].

1. The Setting

We will describe here: the fractals K_{u} to be investigated, the “string models” E_{u}^{(ω)} that will be used in the investigation, the measures μ̂_{u} of Markov type used to define multifractal components K_{u}^{(α)} of the K_{u}, and the functions β(q) and f(α) that describe the properties (such as the fractal dimension) of these components. [Note that β(q) is often called −τ(q).]

1.1. The sets. First, a directed multigraph (V, E) should be fixed. The elements v ∈ V are the vertices of the graph; the elements e ∈ E are the edges of the graph. For u, v ∈ V, there is a subset E_{uv} of E, known as the edges from u to v. Each edge belongs to exactly one of these subsets. We will sometimes write E_{u} = ⋃_{v} E_{uv}, the set of all edges leaving the vertex u.

We will often think of the set E as a set of “letters” that label the edges of the graph, so we will talk about “words” or “strings” made up of these letters. A path in the graph is a finite string γ = e_{1}e_{2} ⋯ e_{k} of edges, such that the terminal vertex of each edge e_{i} is the initial vertex of the next edge e_{i+1}. We write E_{uv}^{(k)} for the set of all paths of length k that begin at u and end at v; and E_{u}^{(k)} for the set of all paths of length k that begin at u; and E_{u}^{(∗)} for the set of all finite paths of any length that begin at u; and E^{(∗)} for the set of all finite paths.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 5

A path that begins and ends at the same node is called a cycle. A cycle with no repeated nodes is a simple cycle. A cycle consisting of a single edge (from a node back to itself) is a loop.

We will assume that the graph (V, E) is strongly connected, that is, there is a path from any vertex to any other, along the edges of the graph (taken in the proper directions). We will also assume that there are at least two edges leaving each node. [We explain this assumption more fully below.]

Next, a ratio r(e) should be specified for each edge e ∈ E. We will assume for simplicity that 0 < r(e) < 1. (In the terminology of [5], it is “strictly contracting”.) So if we write r_{min} = min_{e} r(e) and r_{max} = max_{e} r(e), then we have 0 < r_{min} ≤ r_{max} < 1. If γ = e_{1}e_{2} ⋯ e_{k} is a path, write r(γ) = r(e_{1})r(e_{2}) ⋯ r(e_{k}).

Let J_{u} be nonempty compact subsets of Euclidean space ℝ^{n} (one for each u ∈ V). The set J_{u} should be equal to the closure of its interior. We assume for simplicity that these seed sets have diameter 1. A digraph recursive fractal, or Mauldin-Williams fractal, based on seed sets J_{u} and ratios r(e) is one of the sets

K_{u} = ⋂_{k=0}^{∞} ⋃_{γ∈E_{u}^{(k)}} J(γ),

where the sets J(γ) are chosen recursively:

(i) J(Λ_{u}) = J_{u}, where Λ_{u} is the empty path from u to u.

(ii) For γ ∈ E^{(k)} with terminal vertex v, the set J(γ) is geometrically similar to

J_{v} with reduction ratio r(γ). (iii) For γ ∈ E^{(k)}, with terminal vertex v, the sets J(γe), e ∈ E_{v}, are nonoverlap-

ping subsets of J(γ).

6 G. A. EDGAR AND R. DANIEL MAULDIN

(Note the word “nonoverlapping”. This means that they intersect at most in their boundaries. Since the sets J(γ) are similar to the original sets J_{u}, they, too, are equal to the closures of their interiors. Thus we are postulating the “open set condition”, as in [12]: the interiors of the sets J(γ) are disjoint (for γ of a given length), and their closures are the J(γ).) Notice that there are many choices of how the sets J(γe) may be placed inside J(γ). For the “graph self similar” fractals (as in [5] or [10]), start with similarities θ_{e}: ℝ^{n} → ℝ^{n}, one for each edge e ∈ E, and let

J(γ) = θ_{e_{1}}θ_{e_{2}} ⋯ θ_{e_{k}} [J_{v}]

where γ = e_{1}e_{2} ⋯ e_{k} ∈ E_{uv}^{(k)}. The seed sets J_{u} must be chosen so that (iii) is satisfied. Another possibility (as in [8]) is a scheme that places the subsets J(γe) inside J(γ) at random.

The terminology “Mauldin-Williams fractal” was introduced by the first author in [5]; the second author first studied them as “graph-directed constructions” in [10].

We will assume that our directed multigraph (V, E) has the property that each node has at least two edges leaving it. We claim that this restriction does not change the fractals K_{u} that can be constructed. If the entire graph is a simple cycle, then the sets K_{u} are singletons; so to ensure the system is nontrivial, we assume there is some node with two edges leaving.

Now suppose in (V, E, r) there is some node u_{0} with only one edge e_{0} leaving. Since the graph is strongly connected, that edge goes to some node other than u_{0}. Define a new directed multigraph as follows: V′ = V \ {u_{0}}; the edges E′ are of two kinds: the edges e ∈ E that neither begin nor end at u_{0}, and the paths ee_{0}, where e is

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 7

an edge ending at u_{0}. The ratios r′ are given by r′(e) = r(e) in the first case, and r′(ee_{0}) = r(e)r(e_{0}) in the second case. The new system (V′, E′, r′) constructs the same sets as (V, E, r), but has u_{0} deleted. Continuing in this way, we never remove a node with two or more edges leaving, but (by the finiteness of V) the process eventually ends. When it does, we have a graph where every node has at least two edges leaving.

The Hausdorff dimension for digraph recursive fractals was computed in [10], see [5, Theorem 6.4.8]. This is done as follows: For each positive number s we define a square matrix A(s), with rows and columns indexed by the set V: the entry in row u and column v is

A_{uv}(s) = ∑_{e∈E_{uv}} r(e)^{s}.

The Hausdorff dimension d of all the sets K_{u} is the unique nonnegative number d such that the matrix A(d) has spectral radius 1.

1.2. The models. We will use some “string models” in our investigation of these fractals. Write E_{u}^{(ω)} for the set of all infinite strings, using symbols from E, where the initial vertex of the first edge is u and the terminal vertex of each edge is the initial vertex of the next edge. These sets are naturally compact metric spaces. For each γ ∈ E^{(∗)}, the cylinder [γ] is the set of all infinite strings σ ∈ E^{(ω)} that begin with γ. Then the set { [γ] : γ ∈ E_{u}^{(∗)} } is the base for the topology on E_{u}^{(ω)}. For σ ∈ E_{u}^{(ω)} and a positive integer k, the restriction σ↾k is the finite string made up of the first k letters of σ. The same notation γ↾k is used for finite strings γ when k is less than the length of γ. As a special case of this: if γ has length k, then the parent of γ is γ^{−} = γ↾(k − 1), obtained by omitting the last letter of γ.

8 G. A. EDGAR AND R. DANIEL MAULDIN

There is a model map h_{u}: E_{u}^{(ω)} → ℝ^{n} for each u, defined so that h_{u}(σ) is the unique element of the set

⋂_{k=1}^{∞} J(σ↾k).

Then clearly K_{u} = h_{u}[E_{u}^{(ω)}]. If h_{u}(σ) = x, then we say that the string σ is the address of the point x. In the case when the sets J(γe) that constitute J(γ) are actually disjoint (not merely nonoverlapping), the model maps h_{u} are one-to-one. That means each point has a unique address. 1.3. Measures of Markov type. We begin with positive numbers p(e), one for each edge e ∈ E. They are to be called transition probabilities. The probabilities of all edges leaving a given node u must sum to 1:

∑_{v∈V} ∑_{e∈E_{uv}} p(e) = 1.

(Since each node has at least two edges leaving it, this implies that p(e) < 1 for all edges e.) Then we define products, which are to be thought of as probabilities of paths: if γ ∈ E^{(∗)}, say γ = e_{1}e_{2} ⋯ e_{k}, then

p(γ) = p(e_{1})p(e_{2}) ⋯ p(e_{k}).

These numbers satisfy an additivity condition: if γ ∈ E_{uv}^{(∗)}, then

p(γ) = ∑_{e∈E_{v}} p(γe).

Therefore, for each u ∈ V, there is a unique measure μ̂_{u} on E_{u}^{(ω)} with

μ̂_{u}([γ]) = p(γ)

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 9

for all γ ∈ E_{u}^{(∗)}. Measures of this kind will be called measures of Markov type. Discussion of them can be found under the heading “Markov chains” in many probability books. For example [2, Section 1.8], [14, Chapter 4].

We may think of this in more “probabilistic” language. Imagine a particle moving (at random) on our graph. At each tick of the clock, it traverses one of the edges (in the direction of the arrow) from one vertex to another. The number p(e) gives the probability that the edge e will be chosen, among all the edges emanating from the vertex that is occupied at the present time. We have a sequence (X_{k})_{k=0}^{∞} of random variables with values in V. Given that X_{k} = u, the conditional probability that X_{k+1} = v is

∑_{e∈E_{uv}} p(e).

(We keep a bit more information than is conventional. There may be several edges from u to v; we will not combine them into a single edge, so that we know not only where X_{k} moved to, but also which edge it traversed to get there. If necessary, this can be thought of as a larger Markov chain, where E is the set of states. In [10] there is at most one edge from one node u to another v. But here we allow several edges from u to v as in [5].) So this means: If X_{0} = u, then the conditional probability that the process traverses edges e_{1}, e_{2}, ⋯, e_{k} in the first k steps is 0 unless the string γ = e_{1}e_{2} ⋯ e_{k} belongs to E_{u}^{(k)}, and in that case the conditional probability is

p(γ) = ∏_{i=1}^{k} p(e_{i}).

The measure μ̂_{u} on E_{u}^{(ω)} corresponds to a measure μ_{u} on K_{u} ⊆ ℝ^{n}: For F ⊆ ℝ^{n}, define μ_{u}(F) = μ̂_{u}(h_{u}^{−1}[F]). Another way to think of this measure involves the

10 G. A. EDGAR AND R. DANIEL MAULDIN

construction of K_{u} using the sets J(γ). We begin by assigning mass 1 to the set J_{u}. Then that mass is distributed among the subsets J(e), e ∈ E_{u}, so that J(e) has mass p(e). Once the mass for a set J(γ) has been assigned, then it is distributed among the subsets J(γe), according to the values of p(e). 1.4. Hausdorff and packing dimensions. The two fractal dimensions that we will be concerned with here are the Hausdorff dimension and the packing dimension. We briefly review their definitions.

Let F ⊆ ℝ^{n} be a set. Fix positive real numbers s and ε. Define

ℋ_{ε}^{s}(F) = inf ∑_{i}(diam A_{i})^{s},

where the infimum is over all countable families {A_{i}}_{i=1}^{∞} of sets with ⋃_{i} A_{i} ⊇ F and diam A_{i} < ε for all i. Define the s-dimensional Hausdorff outer measure of F by:

ℋ^{s}(F) = lim_{ε↓0} ℋ_{ε}^{s}(F) = sup_{ε>0} ℋ_{ε}^{s}(F).

There is a unique critical value d, with 0 ≤ d ≤ n, such that

ℋ^{s}(F) = \{ \begin{matrix}∞ & if s < d \\ 0 & if s > d. \end{matrix}

This critical value d is called the Hausdorff dimension of the set F; we will write d = dim F. For more complete discussions, see [1, Section 5.4], [5, Section 6.1], [6, Section 2.1]. We will need to know that ℋ^{s} is a countably-additive measure on the Borel sets of ℝ^{n}.

Let F ⊆ ℝ^{n} be a set. Fix positive real numbers s and ε. Define

𝒫̃_{ε}^{s}(F) = sup ∑_{i=1}^{∞}(2ε_{i})^{s},

where the supremum is over all countable disjoint families {B_{ε_{i}}(x_{i})}_{i=1}^{∞} of balls with ε_{i} < ε and x_{i} ∈ F. Define the s-dimensional packing pre-measure of F by:

𝒫̃^{s}(F) = lim_{ε↓0} 𝒫̃_{ε}^{s}(F) = inf_{ε>0} 𝒫̃_{ε}^{s}(F).

Then define the s-dimensional packing outer measure of F by:

𝒫^{s}(F) = inf ∑_{i=1}^{∞} 𝒫̃^{s}(F_{i}),

where the infimum is over all countable families {F_{i}}_{i=1}^{∞} of sets with ⋃_{i} F_{i} ⊇ F. There is a unique critical value d, with 0 ≤ d ≤ n, such that

𝒫^{s}(F) = \{ \begin{matrix}∞ & if s < d \\ 0 & if s > d. \end{matrix}

This critical value d is called the packing dimension of the set F; we will write d = Dim F. For more complete discussions, see [5, Section 6.5], [6, Section 3.4]. We will need to know that 𝒫^{s} is a countably-additive measure on the Borel sets of ℝ^{n}.

For any set F ⊆ ℝ^{n}, we have dim F ≤ Dim F. (For example, [5, Proposition 6.5.7].) Taylor [16] has proposed that the term “fractal” be used for a set F ⊆ ℝ^{n} with dim F = Dim F. We will prove that the “multifractal components” K_{u}^{(α)} of our digraph recursive fractals satisfy this criterion. 1.5. Multifractal decomposition. Now consider the digraph recursive fractals K_{u} defined above, and the measures μ̂_{u} on the model spaces E_{u}^{(ω)}. The “balls” in E_{u}^{(ω)} are the cylinders [γ]; the measure of a cylinder is μ̂_{u}([γ]) = p(γ); the diameter of a cylinder may be considered to be r(γ). (The diameter of the image h_{u}[[γ]] is ≤ r(γ) and ≥ c r(γ) for some constant c.) Given a real number α, we will be interested in the sets

K̂_{u}^{(α)} = \{ σ ∈ E_{u}^{(ω)} : lim_{k→∞} \frac{log p(σ↾k)}{log r(σ↾k)} = α \}
K_{u}^{(α)} = h_{u} \left[{ \atop K_{u}^{(α)}}\right] .

They will be called the multifractal components of K_{u} (with respect to μ̂_{u}.). Note that K̂_{u}^{(α)} is a Borel set (actually, an F_{σδ}-set). K_{u}^{(α)} is at least an analytic set.

At least in a special case, there is another (more natural) description of the multifractal components. Suppose the K_{u} exhibit “graph self-similarity”: there is a similarity θ_{e}: ℝ^{n} → ℝ^{n} for each edge e ∈ E, such that for γ = e_{1}e_{2} ⋯ e_{k} ∈ E_{uv}^{(k)},

J(γ) = θ_{e_{1}}θ_{e_{2}} ⋯ θ_{e_{k}}[J_{v}].

Suppose that, for each u ∈ V, the sets J(e) for e ∈ E_{u} are disjoint. Then the multifractal components K_{u}^{(α)} defined above satisfy

K_{u}^{(α)} = \{ x ∈ K_{u} : lim_{ε↓0} \frac{log μ(B_{ε}(x))}{log diam B_{ε}(x)} = α \} .

Indeed, two disjoint compact sets are separated by positive distance. Let

c = min { dist (J(e), J(e′)) : u ∈ V, e, e′ ∈ E_{u}, e ≠ e′ } .

Then, for σ, τ ∈ E_{u}^{(ω)} we have

c r(γ) ≤ |h_{u}(σ) − h_{u}(τ)| ≤ r(γ),

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 13

where γ is the longest common prefix of σ and τ. [This can be proved by induction on the length of γ.] Now if x = h_{u}(σ) ∈ K_{u} and ε > 0, then we have

K_{u} ∩ B_{ε}(x) ⊆ J(σ↾k_{1})

where k_{1} is the largest integer with ε < cr(σ↾k_{1}), and

B_{ε}(x) ⊇ K_{u} ∩ J(σ↾k_{0}),

where k_{0} is the least integer with ε > r(σ↾k_{0}). Writing r_{min} = min_{e} r(e), we may deduce that

\frac{log p(σ↾k_{0})}{log ((2/r_{min})r(σ↾k_{0}))} ≤ \frac{log μ_{u}(B_{ε}(x))}{log diam B_{ε}(x)} ≤ \frac{log p(σ↾k_{1})}{log (2cr_{min}r(σ↾k_{1}))}.

These inequalities show that

lim_{k→∞} \frac{log p(σ↾k)}{log r(σ↾k)} = lim_{ε→0} \frac{log μ_{u}(B_{ε}(x))}{log diam B_{ε}(x)}

whenever one of these limits exsits.

The Hausdorff dimensions of the multifractal components may be computed as follows. (Details are given below, in Section 3.) Let A(q, β) be a square matrix with rows and columns indexed by V. The entry in row u, column v, is

A_{uv}(q, β) = ∑_{e∈E_{uv}} p(e)^{q}r(e)^{β}.

For given q, there is a unique β so that A(q, β) has spectral radius 1. This defines β as an analytic function of q. Define α = −dβ/dq and f = qα + β. We note that in much of the literature, what we call β is known as −τ.

14 G. A. EDGAR AND R. DANIEL MAULDIN

1.6. Theorem. Let (V, E) be a strongly connected directed multigraph. Let r(e), 0 < r(e) < 1, be a system of ratios for the graph, and let p(e), 0 < p(e) < 1, be a system of transition probabilities for the graph, defining measures μ̂_{u} of Markov type on the string models E_{u}^{(ω)}. Let q, β, α, f be four numbers related as above. Then for each u ∈ V, the multifractal component K_{u}^{(α)} is a fractal with dimension f:

dim K_{u}^{(α)} = Dim K_{u}^{(α)} = f.

This theorem is proved below, in Section 4.

2. An Example

Let us consider a particular example, before we proceed to the general case. The “two-part dust” (Figure 1) is from [5, Section 6.4]. It is related to the graph shown in Figure 2. The set of vertices is {U, V}. The set of edges is {a, b, c, d}. The ratios are given by: r(a) = 1/2, r(b) = 1/4, r(c) = 1/2, and r(d) = 3/4. The two digraph recursive fractals K_{U} and K_{V} are fractals with dimension d = 1 (both Hausdorff and packing dimension).

Figure 1. The two-part dust. Figure 2. The directed graph.

Now consider the natural measures μ̂_{U}, μ̂_{V} of Markov type, obtained by assigning p(e) = 1/2 for all edges e; for our Markov chain, at each step, we use each of the two

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 15

possible edges leaving the present node with equal probability. Then the matrix A becomes

A(q, β) = [ \begin{matrix}(\frac{1}{2})q (\frac{1}{2})β & (\frac{1}{2})q (\frac{1}{4})β \\ (\frac{1}{2})q (\frac{1}{2})β & (\frac{1}{2})q (\frac{3}{4})β \end{matrix} ] .

We want the spectral radius to be equal to 1. So q and β must satisfy the equation det(A − I) = 0, or

(1)  2^{−2q−3β}3^{β} − 2^{−q−β} − 2^{−q−2β}3^{β} + 1 − 2^{−2q−3β} = 0.

This may be considered a quadratic equation for 2^{−q}. It may be solved for q. We have chosen the appropriate one of the two roots:

q = \frac{log (2^{−β−1} + 3^{β}2^{−2β−1} + 2^{−2β−1}\sqrt{2^{2β}−3^{β}2^{β+1} + 3^{2β} + 2^{β+2}})}{log 2}.

Figure 3. Graph of β(q). Figure 4. Graph of f(α).

16 G. A. EDGAR AND R. DANIEL MAULDIN

Then α = −dβ/dq, so (differentiating (1) implicitly) α =

\frac{(2^{−β−q} + 3^{β}2^{−2β−q} + 2^{−3β−2q+1}(−3^{β} + 1)) log 2}{(2^{−β−q} + 3^{β}2^{−2β−q+1} + 3 · 2^{−3β−2q}(−3^{β} + 1)) log 2 + 3^{β}(−2^{−2β−q} + 2^{−3β−2q}) log 3}.

As usual, f = qα + β.

Here are some special values: q = 0, β = 1, α = 6 log 2/(10 log 2 − 3 log 3) ≈ 1.1439 and f = 1. q = 1, β = 0, α = f = 4 log 2/(6 log 2 − log 3) ≈ 0.90599. q → ∞, β → −∞, α → α_{min} = 2/3 and f → 0. q → −∞, β → ∞, α → α_{max} = log 2/(2 log 2 − log 3) ≈ 2.4094 and f → 0.

The graph of β(q) shows that it is decreasing and convex, with oblique asymptotes at both ends. The graph of f(α) shows the typical concave “dimension spectrum” shape, with maximum value 1 = dim K_{U} = dim K_{V} at α = 1.1439 (and q = 0).

3. Auxiliary Functions

Now we consider more carefully how the auxiliary functions β and α behave. Let A(q, β) be as above. The entry in row u, column v, is

A_{uv}(q, β) = ∑_{e∈E_{uv}} p(e)^{q}r(e)^{β}.

Let Φ(q, β) be the spectral radius of A(q, β). The arguments dealing with Φ(q, β) rely on the theory of nonnegative matrices, known as Perron-Frobenius theory: see for example [7], [11], [14]. Here are the basic properties of the function Φ: 3.1. Proposition.

(i) Φ: ℝ × ℝ → (0, ∞) is continuous (in fact, analytic).

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 17

(ii) Φ is strictly decreasing in each variable separately; that is: if q_{1} < q_{2}, then

Φ(q_{1}, β) > Φ(q_{2}, β); and if β_{1} < β_{2}, then Φ(q, β_{1}) > Φ(q, β_{2}). (iii) For fixed q we have lim_{β→∞} Φ(q, β) = 0 and lim_{β→−∞} Φ(q, β) = ∞. For fixed

β we have lim_{q→∞} Φ(q, β) = 0 and lim_{q→−∞} Φ(q, β) = ∞. (iv) Φ is log-convex; that is: if q_{1}, q_{2}, β_{1}, β_{2} ∈ ℝ, a_{1}, a_{2} ≥ 0, a_{1} + a_{2} = 1, then

Φ(a_{1}q_{1} + a_{2}q_{2}, a_{1}β_{1} + a_{2}β_{2}) ≤ Φ(q_{1}, β_{1})^{a_{1}}Φ(q_{2}, β_{2})^{a_{2}}.

Proof. (i) Each entry A_{uv}(q, β) is continuous (analytic). The largest zero of a polynomial is an analytic function of the coefficients of the polynomial in the region where that zero is a simple zero. Since the graph is strongly connected, the matrix A(q, β) is irreducible, so the spectral radius Φ(q, β) is a simple zero of the characteristic polynomial.

(ii) Fix β, and let q_{1} < q_{2}. There is a positive Perron-Frobenius eigenvector (ρ_{v})_{v∈V} for the matrix A(q_{1}, β) with

∑_{v} ∑_{e∈E_{uv}} p(e)^{q_{1}}r(e)^{β}ρ_{v} = Φ(q_{1}, β) ρ_{u}

for all u ∈ V. Now p(e) < 1, so p(e)^{q_{1}} > p(e)^{q_{2}}. Therefore

∑_{v} ∑_{e∈E_{uv}} p(e)^{q_{2}}r(e)^{β}ρ_{v} < ∑_{v} ∑_{e∈E_{uv}} p(e)^{q_{1}}r(e)^{β}ρ_{v} = Φ(q_{1}, β) ρ_{u}.

This is a strict inequality since there is a nonzero entry in row u. Therefore (as in the Perron-Frobenius theorem), we conclude Φ(q_{2}, β) < Φ(q_{1}, β).

The proof that Φ(q, β) is strictly decreasing in β is the same.

18 G. A. EDGAR AND R. DANIEL MAULDIN

(iii) Fix q. When β → ∞, all of the entries of A(q, β) approach 0, so Φ(q, β) → 0. Similarly, when we let β → −∞, the nonzero entries of A(q, β) approach ∞; there is at least one nonzero entry in each row of A(q, β), so also Φ(q, β) → ∞.

The proof of the other case is the same.

(iv) Fix values q_{1}, q_{2}, β_{1}, β_{2} ∈ ℝ and a_{1}, a_{2} ≥ 0 with a_{1} + a_{2} = 1. There are positive eigenvectors (ρ_{1v}) and (ρ_{2v}) with

∑_{v} ∑_{e∈E_{uv}} p(e)^{q_{i}}r(e)^{β_{i}}ρ_{iv} = Φ(q_{i}, β_{i}) ρ_{iu}

for all u ∈ V, i = 1, 2. Write q = a_{1}q_{1} + a_{2}q_{2}, β = a_{1}β_{1} + a_{2}β_{2}. Let ρ_{u} = ρ_{1u}^{a_{1}}ρ_{2u}^{a_{2}} for u ∈ V. Then (using Hölder’s inequality):

∑_{v} ∑_{e∈E_{uv}} p(e)^{q}r(e)^{β}ρ_{v} = ∑ ∑ (p(e)^{q_{1}}r(e)^{β_{1}}ρ_{1v})^{a_{1}} (p(e)^{q_{2}}r(e)^{β_{2}}ρ_{2v})^{a_{2}}

≤ (∑ ∑ p(e)^{q_{1}}r(e)^{β_{1}}ρ_{1v})^{a_{1}} (∑ ∑ p(e)^{q_{2}}r(e)^{β_{2}}ρ_{2v})^{a_{2}}

= (Φ(q_{1}, β_{1}) ρ_{1u})^{a_{1}} (Φ(q_{2}, β_{2}) ρ_{2u})^{a_{2}}
= Φ(q_{1}, β_{1})^{a_{1}}Φ(q_{2}, β_{2})^{a_{2}}ρ_{u}.

Now the vector (ρ_{u}) is positive, so by Perron-Frobenius theory we conclude Φ(q, β) ≤ Φ(q_{1}, β_{1})^{a_{1}}Φ(q_{2}, β_{2})^{a_{2}}. □

Now for fixed q, the function Φ(q, β) is a continuous function of β. Its values range from 0 (when β → ∞) to ∞ (when β → −∞). Therefore by the intermediate value theorem there is a real number β such that

Φ(q, β) = 1.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 19

The solution β is unique, since Φ is a strictly decreasing function of β. This defines β implicitly as a function of q.

Here are a few useful properties of this function: 3.2. Proposition. Let β = β(q) be defined by Φ(q, β) = 1. Then

(i) β is an analytic function of the real variable q.

(ii) β is strictly decreasing; that is: if q_{1} < q_{2}, then β(q_{1}) > β(q_{2}).

(iii) lim_{q→−∞} β(q) = ∞ and lim_{q→∞} β(q) = −∞.

(iv) β is a convex function; that is: if a_{1}, a_{2} ≥ 0 and a_{1} + a_{2} = 1, then

β(a_{1}q_{1} + a_{2}q_{2}) ≤ a_{1}β(q_{1}) + a_{2}β(q_{2}).

Proof. (i) Φ is an analytic function of its two variables. Neither of its partial derivatives vanishes. Therefore by the implicit function theorem, β is an analytic function of q.

(ii) Let q_{1} < q_{2}. We must show that β(q_{1}) > β(q_{2}). Suppose not: β(q_{1}) ≤ β(q_{2}). Then 1 = Φ(q_{1}, β(q_{1})) > Φ(q_{2}, β(q_{1})) ≥ Φ(q_{2}, β(q_{2})) = 1, a contradiction.

(iii) follows from Proposition 3.1(ii).

(iv) Let q_{1}, q_{2}, a_{1}, a_{2} be given with a_{1}, a_{2} ≥ 0 and a_{1} + a_{2} = 1. Write β_{1} = β(q_{1}) and β_{2} = β(q_{2}). Then

Φ(a_{1}q_{1} + a_{2}q_{2}, a_{1}β_{1} + a_{2}β_{2}) ≤ Φ(q_{1}, β_{1})^{a_{1}}Φ(q_{2}, β_{2})^{a_{2}}
= 1^{a_{1}}1^{a_{2}} = 1
= Φ(a_{1}q_{1} + a_{2}q_{2}, β(a_{1}q_{1} + a_{2}q_{2})).

Therefore a_{1}β_{1} + a_{2}β_{2} ≥ β(a_{1}q_{1} + a_{2}q_{2}), as claimed. □

Note that the probabilities p(e) were postulated to satisfy

∑_{v∈V} ∑_{e∈E_{uv}} p(e) = 1

for all u ∈ V. So by the Perron-Frobenius theorem, the spectral radius of A(1, 0) is 1. So β(1) = 0. As noted above, the Haudorff (and packing) dimensions of the sets K_{u} are the number d with Φ(0, d) = 1. So β(0) = d.

Now let us consider the derivative β′(q). We know that q and β satisfy the equation Φ(q, β) = 1. The matrix is irreducible, so there is a one-dimensional eigenspace for eigenvalue 1 in the matrix A(q, β). We normalize to obtain a unique vector (ρ_{v})_{v∈V} satisfying

∑_{v∈V} ∑_{e∈E_{uv}} p(e)^{q}r(e)^{β}ρ_{v} = ρ_{u} for all u ∈ V;
∑_{v∈V} ρ_{v} = 1.

Cramer’s rule shows that the entries ρ_{v} are analytic functions of q. The graph is strongly connected, so the matrix is irreducible; so by the Perron-Frobenius theorem, ρ_{v} > 0 for all v. Similarly, there exists a left eigenvector λ_{u} for the matrix. This time we will normalize slightly differently:

∑_{u∈V} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β} = λ_{v} for all v ∈ V;
∑_{u∈V} λ_{u}ρ_{u} = 1.

Again, the entries λ_{u} are positive analytic functions of q.

To simplify the notation, we use a prime ′ for derivative with respect to q. First note

∑_{u∈V} λ_{u}ρ_{u} = 1
(∑_{u∈V} λ_{u}ρ_{u})′ = 0
∑_{u∈V} λ′_{u}ρ_{u} + ∑_{u∈V} λ_{u}ρ′_{u} = 0.

Consider the expression

S = ∑_{u} ∑_{v} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β}ρ_{v}.

Then, of course S = ∑_{v} λ_{v}ρ_{v} = 1. Differentiating, we obtain

0 = ∑_{u} ∑_{v} ∑_{e∈E_{uv}} λ′_{u}p(e)^{q}r(e)^{β}ρ_{v} + ∑_{u} ∑_{v} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}( log p(e))r(e)^{β}ρ_{v}

+ ∑_{u} ∑_{v} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β}( log r(e))β′ρ_{v} + ∑_{u} ∑_{v} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β}ρ′_{v}

= ∑_{u} λ′_{u}ρ_{u} + ∑_{u} ∑_{v} ∑_{e∈E_{uv}} (λ_{u}p(e)^{q}r(e)^{β}ρ_{v})( log p(e) + β′ log r(e)) + ∑_{v} λ_{v}ρ′_{v}
= ∑_{u} ∑_{v} ∑_{e∈E_{uv}} (λ_{u}p(e)^{q}r(e)^{β}ρ_{v})( log p(e) + β′ log r(e)).

Therefore

β′(q) = −\frac{∑_{u} ∑_{v} ∑_{e∈E_{uv}} (λ_{u}p(e)^{q}r(e)^{β}ρ_{v}) log p(e)}{∑_{u} ∑_{v} ∑_{e∈E_{uv}} (λ_{u}p(e)^{q}r(e)^{β}ρ_{v}) log r(e)}.

So we conclude that β′(q) < 0, agreeing with Proposition 3.2(ii). We will write α = −dβ/dq. Thus α > 0, and

(2)  α = \frac{∑_{u} ∑_{v} ∑_{e∈E_{uv}} (λ_{u}p(e)^{q}r(e)^{β}ρ_{v}) log p(e)}{∑_{u} ∑_{v} ∑_{e∈E_{uv}} (λ_{u}p(e)^{q}r(e)^{β}ρ_{v}) log r(e)}.

22 G. A. EDGAR AND R. DANIEL MAULDIN

Computations below will use some other numerical parameters. If γ = e_{1}e_{2} ⋯ e_{k} ∈ E^{(k)} is a path, let

η(γ) = \frac{log p(γ)}{log r(γ)} = \frac{log (p(e_{1})p(e_{2}) ⋯ p(e_{k}))}{log (r(e_{1})r(e_{2}) ⋯ r(e_{k}))}.

Write

η_{min} = min { η(ζ) : ζ is a simple cycle }
η_{max} = max { η(ζ) : ζ is a simple cycle } .

We will see below that α ranges from η_{min} to η_{max}.

The last auxiliary function is f = qα + β. Its behavior depends on the behavior of β. Now β is a convex function of q, so d^{2}β/dq^{2} ≥ 0, and therefore dα/dq ≤ 0. Actually, there are two rather different possibilities: β is a linear function or β is a strictly convex function. 3.3. Proposition. Let (x_{v})_{v∈V} be the “Perron numbers”: x_{v} > 0 and

∑_{v∈V} ∑_{e∈E_{uv}} r(e)^{d}x_{v}^{d} = x_{u}^{d}, for all u ∈ V.

(A) Suppose p(e) = (x_{u}^{−1}r(e)x_{v})^{d} for all u, v ∈ V and e ∈ E_{uv}. Then:

(i) β is a linear function: β(q) = d − dq.

(ii) α = d is constant.

(iii) f = d is constant.

(iv) K_{u}^{(d)} = K_{u} and K_{u}^{(α)} = ∅ for all α ≠ d. (B) Suppose p(e) ≠ (x_{u}^{−1}r(e)x_{v})^{d} for at least one edge e. Then:

(i) β is a strictly convex function of q.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 23

(ii) α is a strictly decreasing function of q, so we may consider q as a function of

α defined on an interval (α_{min}, α_{max}). (iii) f is a strictly concave function of α. (iv) K_{u}^{(α)} ≠ ∅ if and only if η_{min} ≤ α ≤ η_{max}.

(v) The function β(q) + η_{min}q is nonincreasing and has a limit ≥ 0 as q → ∞; the function β(q) + η_{max}q is nondecreasing and has a limit ≥ 0 as q → −∞. And α is a decreasing function of q, with α → η_{min} as q → ∞ and α → η_{max} as q → −∞. (So α_{min} = η_{min} and α_{max} = η_{max}.)

Proof. The Perron numbers x_{v} > 0 exist by the Perron-Frobenius theorem. So if we write x_{min} = min_{v} x_{v} and x_{max} = max_{v} x_{v}, then we have 0 < x_{min} ≤ x_{max} < ∞.

(A)(i) Let q be given. We claim that β(q) = d − dq. If we write ρ_{v} = x_{v}^{d−dq}, then we have

∑_{v} ∑_{e∈E_{uv}} p(e)^{q}r(e)^{d−dq}ρ_{v} = ∑ ∑ x_{u}^{−dq}r(e)^{dq}x_{v}^{dq}r(e)^{d−dq}x_{v}^{d−dq}
= x_{u}^{−dq} ∑ ∑ r(e)^{d}x_{v}^{d} = x_{u}^{d−dq} = ρ_{u}.

Therefore Φ(q, d − dq) = 1, so β(q) = d − dq.

(ii) Differentiate the result of (i): α = −dβ/dq = d. (iii) f = qα + β = d. (iv) Let γ = e_{1}e_{2} ⋯ e_{k} be a path in E_{uv}^{(k)}. Since the terminal vertex of each edge e_{i}

is the initial vertex of the following edge e_{i+1}, most of the x_{v}’s cancel in the product

p(γ) = (x_{u}^{−1}r(e_{1})r(e_{2}) ⋯ r(e_{k})x_{v})^{d} = (x_{u}^{−1}r(γ)x_{v})^{d} .

24 G. A. EDGAR AND R. DANIEL MAULDIN

so that

\frac{log p(γ)}{log r(γ)} = d (1 + \frac{log(x_{v}/x_{u})}{log r(γ)}) .

Note that log(x_{v}/x_{u}) is bounded above by log(x_{max}/x_{min}) and bounded below by log(x_{min}/x_{max}). Now let σ ∈ E_{u}^{(ω)}. If we write γ = σ↾k, we have

\frac{log p(σ↾k)}{log r(σ↾k)} = d (1 + \frac{C_{k}}{log r(σ↾k)}) ,

where C_{k} remains bounded as k → ∞, while log r(σ↾k) → −∞ as k → ∞. This shows that log p(σ↾k)/ log r(σ↾k) → d. Therefore E_{u}^{(ω)} = K̂_{u}^{(d)}, so K_{u} = K_{u}^{(d)}.

(B) On the other hand, suppose that p(e) ≠ (x_{u}^{−1}r(e)x_{v})^{d} for some edge e. We claim that β is a strictly convex function of q. Since β is real-analytic, if β is linear on some interval, then it is linear everywhere. That is, if equality holds in Proposition 3.2 (iv) for some q_{1} ≠ q_{2}, then it holds for all. So suppose equality holds for q_{1} = 0, q_{2} = 1. Now β(0) = d and β(1) = 0. The right eigenvectors ρ_{iv} are:

ρ_{1v} = x_{v}^{d},
ρ_{2v} = 1.

Equality in Proposition 3.2 (iv) means equality in Hölder’s inequality in the proof of Proposition 3.1 (iv); thus there are constants a_{u} with

p(e)^{0}r(e)^{d}x_{v}^{d} = a_{u}p(e)^{1}r(e)^{0}1 for e ∈ E_{uv}.

Summing over v ∈ V and e ∈ E_{uv}, we get x_{u}^{d} = a_{u}. Therefore

p(e) = (x_{u}^{−1}r(e)x_{v})^{d}

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 25

for all u, v ∈ V and e ∈ E_{uv}. So we are in case (A).

(i) Thus, in case (B), β is strictly convex. (ii) It follows that α is strictly decreasing. And (iii)

f′ = α + qα′ − α = qα′.

So df/dα = f′/α′ = q. In the graph of f as a function of α (as in Figure 4) the parameter q is the slope of the tangent line to the curve. At the endpoints, where q → ∞ and q → −∞, the graph has vertical tangent lines. Also,

\frac{d^{2}f}{dα^{2}} = \frac{dq}{dα} = \frac{1}{dα/dq} = \frac{−1}{d^{2}β/dq^{2}} < 0.

So f(α) is a strictly concave function.

(iv) Suppose α < η_{min}. We must show that K_{u}^{(α)} = ∅, or equivalently that

lim inf_{k→∞} \frac{log p(σ↾k)}{log r(σ↾k)} ≥ η_{min}

for all σ ∈ E_{u}^{(ω)}. Now for all simple cycles ζ we have log p(ζ)/ log r(ζ) ≥ η_{min}, so log p(ζ) ≤ η_{min} log r(ζ), and thus

p(ζ) ≤ r(ζ)^{η_{min}}.

Now any cycle may be partitioned into finitely many simple cycles. Indeed, if a cycle ζ is not simple, some node is repeated, so it contains a shorter cycle; the shortest cycle contained in ζ is a simple cycle. When this simple cycle is removed from ζ, what remains is a cycle shorter than ζ. Thus, if ζ = e_{1}e_{2} ⋯ e_{k}, then the indices 1, ⋯, k may be partitioned as a disjoint union

{1, 2, ⋯, k} = ⋃_{j=1}^{m} I_{j}

so that { e_{i} : i ∈ I_{j} } is a simple cycle ζ_{j} for each j.

Now if ζ is any cycle, partition it into simple cycles ζ_{1}, ζ_{2}, ⋯, ζ_{m}. Then

p(ζ) = p(ζ_{1}) ⋯ p(ζ_{m}) ≤ r(ζ_{1})^{η_{min}} ⋯ r(ζ_{m})^{η_{min}} = r(ζ)^{η_{min}}.

Therefore η(ζ) ≥ η_{min}.

There are only finitely many nodes in the graph; say there are N nodes. The same argument as above shows that any finite path γ may be partitioned into cycles plus at most N edges. Thus, if C = max { 1, p(e)/r(e)^{η_{min}} : e ∈ E }, then

p(γ) ≤ r(γ)^{η_{min}}C^{N}.

Now for given σ, we have r(σ↾k) → 0 and p(σ↾k) → 0, so the term N log C disappears in the limit, and

lim inf_{k→∞} \frac{log p(σ↾k)}{log r(σ↾k)} ≥ η_{min}

as required.

A similar argument shows that K_{u}^{(α)} = ∅ if α > η_{max}.

Now there is a cycle ζ_{0} with η(ζ_{0}) = η_{min} and a cycle ζ_{1} with η(ζ_{1}) = η_{max}. The infinite path σ = ζ_{0}ζ_{0} ⋯ obtained by repeating ζ_{0} achieves

lim_{k→∞} \frac{log p(σ↾k)}{log r(σ↾k)} = η_{min}.

The path obtained by repeating ζ_{1} achieves η_{max}. And any value of α between η_{min} and η_{max} is achieved by an infinite path that intersperses the two cycles ζ_{0} and ζ_{1} in the proper proportions. So K_{u}^{(α)} ≠ ∅ for such α.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 27

(v) Now we analyze the asymptotic properties of β(q): when q → ∞, and β → −∞, we claim that α decreases to η_{min} and β+η_{min}q is nonincreasing. (The other asymptote q → −∞ may be done similarly.)

Now if γ ∈ E^{(k)} is a path of length k, it may be partitioned into cycles ζ_{1}, ζ_{2}, ⋯, ζ_{m} plus at most N additional edges. Then, as before

log p(γ) ≤ η_{min} log r(γ) + N log C,
\frac{log p(γ)}{log r(γ)} ≥ η_{min} + \frac{N log C}{log r(γ)} ≥ η_{min} + \frac{N log C}{k log r_{max}} .

Now if we write for each k

η_{k} = min { η(γ) : γ ∈ E^{(k)} } ,

we may conclude

η_{k} ≥ η_{min} + \frac{N log C}{k log r_{max}} .

But k log r_{max} → −∞ as k → ∞, so we have

lim inf_{k→∞} η_{k} ≥ η_{min}.

On the other hand, for given large k, we may construct a path γ of length k by repeating the simple cycle ζ_{0} (which achieves η_{min}) many times, followed by the first few edges of ζ_{0}. Now if c = min { 1, p(e)/r(e)^{η_{min}} : e ∈ E }, we have

η(γ) ≤ η_{min} + \frac{N log c}{log r(γ)};

thus

η_{k} ≤ η_{min} + \frac{N log c}{log r(γ)}.

28 G. A. EDGAR AND R. DANIEL MAULDIN

This shows

lim_{k→∞} η_{k} = η_{min}.

For a given positive integer k, the power A(q, β(q))^{k} of the matrix also has spectral radius 1 with the same left and right eigenvectors. So for each node u,

(3)  ρ_{u} = ∑_{v} ∑_{γ∈E_{uv}^{(k)}} p(γ)^{q}r(γ)^{β}ρ_{v}.

Thus (as in the case k = 1) we have

1 = ∑_{u} λ_{u}ρ_{u} = ∑_{u} ∑_{v} ∑_{γ∈E_{uv}^{(k)}} λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v},

and may differentiate to conclude

β′(q) = −\frac{∑_{u} ∑_{v} ∑_{γ∈E_{uv}^{(k)}} (λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v}) log p(γ)}{∑_{u} ∑_{v} ∑_{γ∈E_{uv}^{(k)}} (λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v}) log r(γ)}.

But for all γ with length k, η(γ) ≥ η_{k}, so p(γ) = r(γ)^{η(γ)} ≤ r(γ)^{η_{k}}, and thus log p(γ) ≤ η_{k} log r(γ). Therefore we have

β′(q) ≤ −\frac{η_{k} ∑_{u} ∑_{v} ∑_{γ∈E_{uv}^{(k)}} (λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v}) log r(γ)}{∑_{u} ∑_{v} ∑_{γ∈E_{uv}^{(k)}} (λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v}) log r(γ)} = −η_{k}.

Take the limit as k → ∞ to obtain β′(q) ≤ −η_{min}. This implies that α ≥ η_{min}; and also β + η_{min}q is a nonincreasing function of q.

Next we claim that β(q) + η_{min}q converges to a finite nonnegative limit as q → ∞. If ζ ∈ E_{uu}^{(k)} is a simple cycle, then from (3) we have

ρ_{u} > p(ζ)^{q}r(ζ)^{β(q)}ρ_{u}.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 29

The inequality is strict since there is more to the graph than this single simple cycle. Therefore r(ζ)^{qη(ζ)+β(q)} < 1, so qη(ζ) + β(q) > 0. This holds for all simple cycles, so

qη_{min} + β(q) > 0.

Now since qη_{min} +β(q) converges to a finite limit, its graph has a horizontal asymptote. But its derivative η_{min} − α(q) is negative and increasing, so that derivative must converge to 0. Therefore α(q) → η_{min} as q → ∞. That is, α_{min} = η_{min}.

The asymptotic properties as q → −∞ are proved in the same way. □

4. Proof of the Dimension Theorem

We now come to the proof of Theorem 1.6. Fix a real number q. There are corresponding values β, α, f as above. For each u ∈ V we will prove that the set K_{u}^{(α)} is a fractal with dimension f:

dim K_{u}^{(α)} = Dim K_{u}^{(α)} = f.

The proof is divided into the “upper bound” Dim K_{u}^{(α)} ≤ f and the “lower bound” dim K_{u}^{(α)} ≥ f. Since the inequality dim F ≤ Dim F is true for any set F ⊆ ℝ^{n}, these two bounds suffice to prove the result.

Before we proceed with the proof, we will consider the auxiliary measures.

The matrix A(q, β) has spectral radius 1. So (as above) there exist positive right and left eigenvectors: ρ_{v}, λ_{v} with

∑_{v∈V} ∑_{e∈E_{uv}} p(e)^{q}r(e)^{β}ρ_{v} = ρ_{u} for all u ∈ V;
∑_{u∈V} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β} = λ_{v} for all v ∈ V .

30 G. A. EDGAR AND R. DANIEL MAULDIN

By the Perron-Frobenius theorem, λ_{v}, ρ_{v} > 0. So if we write ρ_{min} = min_{v} ρ_{v} and ρ_{max} = max_{v} ρ_{v}, then 0 < ρ_{min} ≤ ρ_{max}. If we let

P (e) = ρ_{u}^{−1}p(e)^{q}r(e)^{β}ρ_{v}

for all e ∈ E_{uv}, then we have

∑_{v∈V} ∑_{e∈E_{uv}} P (e) = 1

for all u ∈ V. These can be used as transition probabilities for some measure of Markov type, called μ̂_{u}^{(q)}. Equivalently, for γ ∈ E_{uv}^{(k)}, the cylinder [γ] is given measure

μ̂_{u}^{(q)}([γ]) = ρ_{u}^{−1}p(γ)^{q}r(γ)^{β}ρ_{v}.

There is a corresponding measure μ_{u}^{(q)} on K_{u} defined by μ_{u}^{(q)}(F) = μ̂_{u}^{(q)}(h_{u}^{−1}[F]). 4.1. Lemma. Let u ∈ V. The measure μ̂_{u}^{(q)} is concentrated on the set K̂_{u}^{(α)}; that is,

μ̂_{u}^{(q)} \binom{}{K_{u}^{(α)}} = 1.

Proof. Consider the Markov chain (X_{k}) with transition probabilities P (e), as above. In probabilistic language, we are required to prove that (conditioned on X_{0} = u) the “trajectory” of the Markov chain (that is, the string made up of the successive edges traversed by the process) almost surely belongs to K̂_{u}^{(α)}.

Now the numbers π_{u} = λ_{u}ρ_{u} constitute a “stationary distribution” for the Markov chain. That is, for every v ∈ V,

∑_{u∈V} ∑_{e∈E_{uv}} π_{u}P (e) = π_{v}.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 31

We next apply the ergodic theorem for Markov chains: [7, Theorem 11′, p. 95] or [14, Theorems 4.1, 4.2]. The graph (V, E) is strongly connected, so the Markov chain is ergodic; thus π_{u} is the unique stationary distribution, and it occurs as the long-run frequencies of the process. This means that, in the long run, each state v is visited a fraction π_{v} of the time. Consequently, for each edge e ∈ E_{v}, the fraction π_{v}P (e) of all edge traversals occur on the edge e. Precisely, if g: E → ℝ is any function, then for almost all σ ∈ E_{u}^{(ω)},

\frac{1}{k} ∑_{i=1}^{k} g(σ_{i}) → ∑_{u∈V} ∑_{v∈V} ∑_{e∈E_{uv}} π_{u}P (e)g(e) as k → ∞.

We have written σ_{i} for the ith letter of the string σ.

Now let us apply this with g(e) = log p(e). Then ∑_{i=1}^{k} log p(σ_{i}) = log ∏_{i=1}^{k} p(σ_{i}) = log p(σ↾k). We conclude: for almost all σ,

\frac{1}{k} log p(σ↾k) → ∑_{u∈V} ∑_{v∈V} ∑_{e∈E_{uv}} π_{u}P (e) log p(e)
= ∑_{u∈V} ∑_{v∈V} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β}ρ_{v} log p(e).

Similarly,

\frac{1}{k} log r(σ↾k) → ∑_{u∈V} ∑_{v∈V} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β}ρ_{v} log r(e).

Therefore, for almost all σ ∈ E_{u}^{(ω)}, we have the ratio limit

\frac{log p(σ↾k)}{log r(σ↾k)} → \frac{∑_{u∈V} ∑_{v∈V} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β}ρ_{v} log p(e)}{∑_{u∈V} ∑_{v∈V} ∑_{e∈E_{uv}} λ_{u}p(e)^{q}r(e)^{β}ρ_{v} log r(e)} = α

by (2). That is, σ ∈ K̂_{u}^{(α)}. □

32 G. A. EDGAR AND R. DANIEL MAULDIN

4.2. Proposition (upper bound). Let u ∈ V. The packing dimension inequality Dim K_{u}^{(α)} ≤ f holds. Proof. (i) First, in the case q = 0, we have f = β = d; this is the usual computation of the packing dimension of a digraph recursive fractal, for example [5, Theorem 6.5.10].

(ii) Next, consider the case q > 0. Fix δ > 0. Define

Ŝ_{u}^{(k)} = \{ σ ∈ E_{u}^{(ω)} : \frac{log p(σ↾k)}{log r(σ↾k)} ≤ α + \frac{δ}{q} \} ,
T̂_{u}^{(N)} = ⋂_{k=N}^{∞} Ŝ_{u}^{(k)},
T_{u}^{(N)} = h_{u} \left[{ \atop T_{u}^{(N)}}\right] .

Then we have

K̂_{u}^{(α)} ⊆ ⋃_{N=1}^{∞} T̂_{u}^{(N)}
K_{u}^{(α)} = h_{u} \left[{ \atop K_{u}^{(α)}}\right] ⊆ ⋃_{N=1}^{∞} T_{u}^{(N)}.

We will show Dim T_{u}^{(N)} ≤ f + δ. This is true for all N, so Dim K_{u}^{(α)} ≤ f + δ. And this is true for all δ > 0, so Dim K_{u}^{(α)} ≤ f, as claimed.

So fix N and consider the (f + δ)-dimensional packing measure of T_{u}^{(N)}. Let ε > 0 be so small that ε < r(γ) for all γ ∈ E_{u}^{(N)}. Let

B_{ε_{i}}(x_{i}), i = 1, 2, ⋯

be a countable disjoint collection of balls with x_{i} ∈ T_{u}^{(N)} and ε_{i} < ε. There exist σ_{i} ∈ T̂_{u}^{(N)} for i = 1, 2, ⋯ so that h_{u}(σ_{i}) = x_{i}. Let k_{i} ∈ ℕ be such that r(σ↾k_{i}) < ε_{i} ≤ r(σ↾(k_{i} − 1)). Then k_{i} ≥ N by the choice of ε. Now σ_{i} ∈ Ŝ_{u}^{(k_{i})}, so:

\frac{log p(σ_{i}↾k_{i})}{log r(σ_{i}↾k_{i})} ≤ α + \frac{δ}{q}
log p(σ_{i}↾k_{i}) ≥ (α + \frac{δ}{q} ) log r(σ_{i}↾k_{i})
p(σ_{i}↾k_{i}) ≥ r(σ_{i}↾k_{i})^{α+δ/q}
p(σ_{i}↾k_{i})^{q} ≥ r(σ_{i}↾k_{i})^{αq+δ}
p(σ_{i}↾k_{i})^{q}r(σ_{i}↾k_{i})^{β} ≥ r(σ_{i}↾k_{i})^{f+δ}.

By the choice of the k_{i}, the cylinders [σ_{i}↾k_{i}] are disjoint. Now

diam B_{ε_{i}}(x_{i}) = 2ε_{i} ≤ 2r(σ_{i}↾(k_{i} − 1)) ≤ (2/r_{min})r(σ_{i}↾k_{i}).

Thus

(\frac{r_{min}}{2} )^{f+δ} ∑_{i} (2ε_{i})^{f+δ} ≤ ∑_{i} r(σ_{i}↾k_{i})^{f+δ} ≤ ∑_{i} p(σ_{i}↾k_{i})^{q}r(σ_{i}↾k_{i})^{β}

≤ (\frac{ρ_{max}}{ρ_{min}} ) ∑_{i} μ̂_{u}^{(q)}( [σ_{i}↾k_{i}] )

= (\frac{ρ_{max}}{ρ_{min}} ) μ̂_{u}^{(q)} (⋃_{i} [σ_{i}↾k_{i}]) ≤ (\frac{ρ_{max}}{ρ_{min}} ) .

This shows

𝒫̃_{ε}^{f+δ}(T_{u}^{(N)}) ≤ (\frac{ρ_{max}}{ρ_{min}} ) (\frac{2}{r_{min}} )^{f+δ} .

Let ε → 0 to obtain 𝒫̃^{f+δ}(T_{u}^{(N)}) ≤ (ρ_{max}/ρ_{min})(2/r_{min})^{f+δ} < ∞ and 𝒫^{f+δ}(T_{u}^{(N)}) < ∞. So Dim T_{u}^{(N)} ≤ f + δ.

Therefore, as noted above, we have Dim K_{u}^{(α)} ≤ f.

(iii) Finally, consider the case q < 0. Fix δ > 0. (So δ/q < 0.) Define

Ŝ_{u}^{(k)} = \{ σ ∈ E_{u}^{(ω)} : \frac{log p(σ↾k)}{log r(σ↾k)} ≥ α + \frac{δ}{q} \} ,
T̂_{u}^{(N)} = ⋂_{k=N}^{∞} Ŝ_{u}^{(k)},
T_{u}^{(N)} = h_{u} \left[{ \atop T_{u}^{(N)}}\right] .

As in the previous case, K_{u}^{(α)} ⊆ ⋃_{N=1}^{∞} T_{u}^{(N)}. The rest of the proof proceeds as before. With the reversed inequality in the definition of Ŝ_{u}^{(k)} and q < 0, we again obtain the estimate

p(σ_{i}↾k_{i})^{q}r(σ_{i}↾k_{i})^{β} ≥ r(σ_{i}↾k_{i})^{f+δ}. □

4.3. Proposition (lower bound). Let u ∈ V. The Hausdorff dimension inequality dim K_{u}^{(α)} ≥ f holds.

Proof. (i) First, in the case q = 0, we have f = β = d. So the Hausdorff dimension inequality is essentially the computation of Mauldin and Williams. (Recall that we assume the open set condition.) See [5, Theorem 6.4.8] or [10, Theorem 3]. The measure μ̂_{u}^{(0)} is the measure used in these references, and the set K̂_{u}^{(α)} supports this measure, so the computation actually shows dim K_{u}^{(α)} ≥ d; indeed, ℋ^{d}(K_{u}^{(α)}) is positive and finite.

(ii) Next, consider the case q > 0. We must show that dim K_{u}^{(α)} ≥ f. More generally, let F be any (Borel) set in ℝ^{n} with μ_{u}^{(q)}(F) = a > 0. We will show that dim F ≥ f. [That is, in terminology discussed below, we show that dim μ_{u}^{(q)} ≥ f.] Let δ > 0 be given. We will investigate the (f − δ)-dimensional Hausdorff measure of

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 35

the set F. Write F̂ = h_{u}^{−1}[F]. Then let

Ŝ_{u}^{(k)} = \{ σ ∈ F̂ : \frac{log p(σ↾k)}{log r(σ↾k)} ≥ α − \frac{δ}{q} \} ,
T̂_{u}^{(N)} = ⋂_{k=N}^{∞} Ŝ_{u}^{(k)},
T_{u}^{(N)} = h_{u} \left[{ \atop T_{u}^{(N)}}\right] .

Now F̂ is contained in the increasing union ⋃_{N=1}^{∞} T̂_{u}^{(N)} and μ̂_{u}^{(q)}(F̂) = a > 0, so by the countable additivity of the measure,

lim_{N→∞} μ̂_{u}^{(q)}(T̂_{u}^{(N)}) = a.

Choose N so large that μ̂_{u}^{(q)}(T̂_{u}^{(N)}) > a/2, then choose ε > 0 so small that ε < r(γ) for all γ ∈ E_{u}^{(N)}.

Now suppose that {A_{i}} is a countable cover of F by sets with diam A_{i} < ε. For each i, let

H_{i} = { γ ∈ E_{u}^{(∗)} : r(γ) < diam A_{i} ≤ r(γ^{−}), h_{u}[[γ]] ∩ A_{i} ∩ F ≠ ∅ } .

There is a geometrical lemma ([10, Lemma V] or [5, pp. 172–3]) that shows there is a finite constant C such that each set H_{i} has at most C elements. If we write H = ⋃_{i=1}^{∞} H_{i}, then

∑_{γ∈H} r(γ)^{f−δ} ≤ C ∑_{i}(diam A_{i})^{f−δ}.

Now { [γ] : γ ∈ H } covers F̂ ⊇ T̂_{u}^{(N)}. We need to construct a cover of T̂_{u}^{(N)} more efficient than H. First, there is no need for the sets that do not meet T̂_{u}^{(N)}; let H′ = { γ ∈ H : [γ] ∩ T̂_{u}^{(N)} ≠ ∅ }. Also, we need to cover the set only once: if two

36 G. A. EDGAR AND R. DANIEL MAULDIN

cylinders [γ] are not disjoint then one of them is contained in the other, so we may discard the smaller one. So there is a set H′′ ⊆ H′ such that { [γ] : γ ∈ H′′ } is a disjoint cover of T̂_{u}^{(N)}.

Now for each γ ∈ H′′ there exists σ ∈ T̂_{u}^{(N)} and k ≥ N so that σ↾k = γ. Then σ ∈ Ŝ_{u}^{(k)}, so

\frac{log p(γ)}{log r(γ)} ≥ α − \frac{δ}{q}
log p(γ) ≤ (α − \frac{δ}{q} ) log r(γ)
p(γ) ≤ r(γ)^{α−δ/q}
p(γ)^{q} ≤ r(γ)^{αq−δ}
p(γ)^{q}r(γ)^{β} ≤ r(γ)^{f−δ}.

Thus, if γ ∈ H′′ and γ ∈ E_{uv}^{(k)}, then

μ̂_{u}^{(q)}([γ]) = ρ_{u}^{−1}p(γ)^{q}r(γ)^{β}ρ_{v} ≤ \frac{ρ_{max}}{ρ_{min}} r(γ)^{f−δ}.

Now

\frac{a}{2} ≤ μ̂_{u}^{(q)} \binom{}{T_{u}^{(N)}} ≤ μ̂_{u}^{(q)} ( ⋃_{γ∈H′′}[γ]) = ∑_{γ∈H′′} μ̂_{u}^{(q)}([γ])

≤ (\frac{ρ_{max}}{ρ_{min}} ) ∑_{γ∈H′′} r(γ)^{f−δ} ≤ (\frac{ρ_{max}}{ρ_{min}} ) ∑_{γ∈H} r(γ)^{f−δ}

≤ (\frac{Cρ_{max}}{ρ_{min}} ) ∑_{i}(diam A_{i})^{f−δ}.

Thus we have ℋ^{f−δ}(F̂) ≥ ρ_{min}a/2Cρ_{max} > 0. So dim F ≥ f − δ. This is true for all δ > 0, so we have dim F ≥ f, as required.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 37

(iii) Finally, consider the case q < 0. Let δ > 0 be given, so δ/q < 0. Define now

Ŝ_{u}^{(k)} = \{ σ ∈ F̂ : \frac{log p(σ↾k)}{log r(σ↾k)} ≤ α − \frac{δ}{q} \} ,
T̂_{u}^{(N)} = ⋂_{k=N}^{∞} Ŝ_{u}^{(k)},
T_{u}^{(N)} = h_{u} \left[{ \atop T_{u}^{(N)}}\right] .

Then proceed as in the previous case. The reversed inequality and q < 0 mean that the estimate

p(γ)^{q}r(γ)^{β} ≤ r(γ)^{f−δ}

remains correct. □

5. Other Remarks

5.1. Hausdorff dimension of a measure. Some of the proofs given here actually deal with the Hausdorff dimension of a measure in order to estimate the Hausdorff dimension of a set. The proof of Proposition 4.3 shows not only that dim K_{u}^{(α)} ≥ f, but that dim F ≥ f for any set F with μ_{u}^{(q)}(F) > 0. This may be interpreted as saying that the “Hausdorff dimension” of the measure μ_{u}^{(q)} is at least f.

There is more than one possible definition for the “Hausdorff dimension of a measure”. We will show here that two of them coincide.

Let S be a metric space, and let μ be a finite measure defined on the Borel subsets of S. The Hausdorff dimension of the measure μ is the minimum of the dimensions of the sets that support μ:

dim_{1} μ = inf { dim F : F ⊆ S, μ(S \ F) = 0 } .

38 G. A. EDGAR AND R. DANIEL MAULDIN

There is another natural definition. Fix positive real numbers s and ε. Define

ℋ_{ε}^{s}(μ) = inf ∑_{i}(diam A_{i})^{s},

where the infimum is over all countable families {A_{i}}_{i=1}^{∞} of sets with diam A_{i} < ε for all i that almost cover S in the sense that

μ (S \ ⋃_{i} A_{i}) = 0.

Define

ℋ^{s}(μ) = lim_{ε↓0} ℋ_{ε}^{s}(μ) = sup_{ε>0} ℋ_{ε}^{s}(μ).

There is a unique critical value s_{0} such that

ℋ^{s}(μ) = \{ \begin{matrix}∞ & if s < s_{0} \\ 0 & if s > s_{0}. \end{matrix}

This critical value s_{0} is called the Hausdorff dimension of the measure μ; we will write s_{0} = dim_{2} μ. Proposition. Let S be a metric space, and let μ be a finite measure defined on the Borel subsets of S. Then dim_{1} μ = dim_{2} μ. Proof. Let F ⊆ S with μ(S\F) = 0. To estimate the s-dimensional Hausdorff measure of F, cover F:

F ⊆ ⋃_{i} A_{i}, diam A_{i} < ε.

Then certainly {A_{i}} almost covers S. So ℋ_{ε}^{s}(μ) ≤ ∑ ( diam A_{i})^{s}. Therefore ℋ_{ε}^{s}(μ) ≤ ℋ_{ε}^{s}(F). Let ε → 0 to obtain ℋ^{s}(μ) ≤ ℋ^{s}(F). If s > dim F, then ℋ^{s}(F) = 0, so ℋ^{s}(μ) = 0. Thus dim_{2} μ ≤ dim F. This shows that dim_{2} μ ≤ dim_{1} μ.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 39

For the reverse inequality, let s > dim_{2} μ, so that ℋ^{s}(μ) = 0. Given n ∈ ℕ, find an almost cover {A_{ni}}_{i=1}^{∞} of S with diam A_{ni} < 2^{−n} and ∑_{i}(diam A_{ni})^{s} < 2^{−n}. Then the set

F = ⋂_{n} ⋃_{i} A_{ni}

satisfies μ(S \ F) = 0. But for each n, the family {A_{ni}}_{i=1}^{∞} covers F. So

ℋ_{2^{−n}}^{s}(F) ≤ 2^{−n},

so that ℋ^{s}(F) = 0. Therefore dim F ≤ s, so dim_{1} μ ≤ s. This is true for every s > dim_{2} μ, so we have dim_{1} μ ≤ dim_{2} μ. □

Use of measures such as μ_{u}^{(q)} in our proof of Theorem 1.6 is suggested in [4] by Cawley and Mauldin; they consider the case corresponding to a graph with one node. An independent calculation of the dimension of such a measure was done in [15] by Strichartz; he considers the case corresponding to a graph with one node, using a fixed family of similarity transformations, and the case q = 1, so that β = 0, and f = α is a ratio like (2). 5.2. Cross-cuts. Suppose C_{u} is a cross-cut of E_{u}^{(∗)}. That is, when E_{u}^{(∗)} is given the structure of a tree, C_{u} is a maximal antichain in E_{u}^{(∗)}. Or, the cylinders [γ] for γ ∈ C_{u} are disjoint and their union is dense in E_{u}^{(ω)}. If C_{u} is infinite, we assume also that

1 = ∑_{γ∈C_{u}} μ̂_{u}^{(q)}([γ]).

So if we write C_{uv} = C_{u} ∩ E_{uv}^{(∗)}, then

(4)  1 = ∑_{v∈V} ∑_{γ∈C_{uv}} ρ_{u}^{−1}p(γ)^{q}r(γ)^{β}ρ_{v}

40 G. A. EDGAR AND R. DANIEL MAULDIN

or

ρ_{u} = ∑_{v∈V} ∑_{γ∈C_{uv}} p(γ)^{q}r(γ)^{β}ρ_{v}.

Of course the sets E_{u}^{(k)} used for (3) are cross-cuts. We may deduce formulas from the general (4) in the same way as from (3); for example

1 = ∑_{u} ∑_{v} ∑_{γ∈C_{uv}} λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v}
α = \frac{∑_{u} ∑_{v} ∑_{γ∈C_{uv}} (λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v}) log p(γ)}{∑_{u} ∑_{v} ∑_{γ∈C_{uv}} (λ_{u}p(γ)^{q}r(γ)^{β}ρ_{v}) log r(γ)}.

Our graph (V, E) is strongly connected, so almost every σ ∈ E^{(ω)} returns eventually to its starting node. Thus

Z_{u} = { γ ∈ E_{uu}^{(∗)} : γ↾k ∉ E_{uu}^{(∗)} for 1 ≤ k < |γ| }

is a cross-cut consisting only of cycles. Then the eigenvectors drop out of (4): for all u

1 = ∑_{ζ∈Z_{u}} p(ζ)^{q}r(ζ)^{β}.

So we have

α = \frac{∑_{ζ∈Z_{u}} p(ζ)^{q}r(ζ)^{β} log p(ζ)}{∑_{ζ∈Z_{u}} p(ζ)^{q}r(ζ)^{β} log r(ζ)}.

Another example of a cross-cut: fix ε > 0, and let

C_{u} = { γ ∈ E_{u}^{(∗)} : r(γ) ≤ ε < r(γ^{−}) } .

This is useful for study of decomposition of K_{u} into sets of the same size.

MULTIFRACTAL DECOMPOSITIONS OF DIGRAPH RECURSIVE FRACTALS 41

5.3. Questions. There are several questions suggested by this work that we do not answer here. For example:

(a) When q → ∞, is there some sort of “limiting construction”, with dimension f(α_{min})? In [4], where the case of a graph with one node is considered, the limiting construction is composed of those edges e with equality η(e) = η_{min}. Perhaps in our case one should delete everything except the simple cycles ζ with η(ζ) = η_{min}. In particular, if there is a unique such cycle ζ_{0}, then the limiting construction consists only of that cycle, so its attractors are single points when u lies on ζ_{0}. How are these points related to the components K_{u}^{(α_{min})}?

(b) What happens when the graph is not strongly connected (so the matrix is reducible)? Reading [10] would suggest that we should analyze all of the the strongly connected components of the graph, and then take the maximum of these dimensions.

(c) Is there a completeness theorem? Does

⋃_{α_{min}≤α≤α_{max}} K_{u}^{(α)}

have measure 1?

(d) Under what (disjointness) conditions, on the sets J(γ) in the construction of the fractals K_{u}, can we replace the sets K_{u}^{(α)} = h_{u}[K̂_{u}^{(α)}] used in this paper with the more naturally defined sets

\{ x ∈ K_{u} : lim_{ε↓0} \frac{log μ(B_{ε}(x))}{log diam B_{ε}(x)} = α \} ?

We have seen above that this can be done when we use a fixed family θ_{e} of similarities and have a strong disjointness property. (It was shown to be true in [4] in the case corresponding to a graph with a single node.) Is the open set condition enough?

42 G. A. EDGAR AND R. DANIEL MAULDIN

(e) In Proposition 3.3, we see in case (B) that: β is a strictly convex function of q, α is a strictly decreasing function of q, f is a strictly concave function of α. Thus, we have strict inequalities:

\frac{d^{2}β}{dq^{2}} > 0,  \frac{dα}{dq} < 0,  \frac{d^{2}f}{dα^{2}} < 0

except possibly at isolated points where equality occurs. Do these strict inequalities in fact hold everywhere?

(f) It would be interesting to investigate the relations between the computations in this paper and the “thermodynamic formalism” for dimension spectra. For example, D. A. Rand [13] investigates the dimension spectrum for “cookie-cutter” Cantor set fractals.

Consider these two classes of fractals: the cookie-cutter fractals and the digraph recursive fractals. Neither class contains the other: The digraph recursive fractals utilize only affine transformations, while the cookie-cutter fractals allow non-affine transformations. The cookie-cutter fractals are constructed in the line ℝ, while digraph recursive fractals are in Euclidean space of any dimension. The graph directing the construction of a cookie-cutter fractal is the graph with one node and two loops; while digraph recursive fractals may be defined by more general graphs.

For sets that are both digraph recursive fractals and cookie-cutter fractals, Rand’s results agree with ours: Compare our Theorem 1.6 with Rand’s Theorem 1. This agreement should extend much farther. Can the spectral radius Φ(q, β) be considered (the logarithm of) a “pressure” for the general digraph recursive fractal?

References

1. M. F. Barnsley, Fractals Everywhere, Academic Press, 1988.

2. P. Billingsley, Probability and Measure, Wiley-Interscience, 1979.

3. K. M. Brucks, Hausdorff dimension and measure of basin boundaries, Advances in Math. 78 (1989), 168–191.

4. R. Cawley and R. D. Mauldin, Multifractal decompositions of Moran fractals, Advances in Math. (to appear).

5. G. A. Edgar, Measure, Topology, and Fractal Geometry, Undergraduate Texts in Mathematics, Springer-Verlag New York, 1990.

6. K. J. Falconer, Fractal Geometry: Mathematical Foundations and Applications, John Wiley & Sons, 1990.

7. F. R. Gantmacher, The Theory of Matrices, Volume 2, Chelsea, 1959, Chapter XIII: Matrices with non-negative elements.

8. S. Graf, R. D. Mauldin, and S. C. Williams, The exact Hausdorff dimension in random recursive constructions, Memoirs of the A. M. S. 381, American Mathematical Society, 1988.

9. T. Halsey, M. Jensen, L. Kadanoff, I. Procaccia, B. Shraiman, Fractal measures and their singularities: The characterization of strange sets, Phys. Rev. A 33 (1986), 1141–1151.

10. R. D. Mauldin and S. C. Williams, Hausdorff dimension in graph directed constructions, Trans. Amer. Math. Soc. 309 (1988), 811–829.

11. H. Minc, Nonnegative Matrices, Wiley, 1988.

12. P. A. P. Moran, Additive functions of intervals and Hausdorff measure, Proc. Cambridge Phil. Soc. 42 (1946), 15–23.

13. D. Rand, The singularity spectrum f(α) for cookie-cutters, Ergodic Theory and Dynamical Systems 9 (1989), 527–541.

14. E. Seneta, Non-Negative Matrices, Wiley, 1973.

15. R. Strichartz, Self-similar measures and their Fourier transforms, I, Indiana Univ. Math. J. 39 (1990), 797–817.

16. S. J. Taylor, The measure theory of random fractals, Math. Proc. Camb. Phil. Soc. 100 (1986), 383–406.

Department of Mathematics, The Ohio State University, Columbus, OH 43210-1174

E-mail address: edgar@mps.ohio-state.edu

Department of Mathematics, University of North Texas, Denton, TX 76203-3886

E-mail address: MAULDIN@UNTVAX