DISTRIBUTION OF FREQUENCIES OF DIGITS VIA MULTIFRACTAL ANALYSIS

L. BARREIRA, B. SAUSSOL, AND J. SCHMELING

Abstract. We study the Hausdorff dimension of a large class of sets in the real line defined in terms of the distribution of frequencies of digits for the representation in some integer base. In particular, our results unify and extend classical work of Borel, Besicovitch, Eggleston, and Billingsley in several directions. Our methods are based on recent results concerning the multifractal analysis of dynamical systems and often allow us to obtain explicit expressions for the Hausdorff dimension. This work is still another illustration of the role that the theory of dynamical systems can play in number theory.

1. Introduction

Instead of formulating general statements at this point, we want to discuss explicit examples (although already nontrivial), which illustrate well the nature of our work.

Given an integer m > 1, for each number x ∈ [0, 1] we shall denote by 0.x_{1}x_{2} ⋯ a base-m representation of x. It is easy to see that this representation is unique except for countably many points. We remark that since countable sets have zero Hausdorff dimension, the nonuniqueness of the representation does not interfere with our study.

For each k ∈ {0, …, m − 1}, x ∈ [0, 1], and n ∈ ℕ set

τ_{k}(x, n) = card{i ∈ {1, …, n} : x_{i} = k}.

Whenever there exists the limit

τ_{k}(x) = lim_{n→∞} \frac{τ_{k}(x, n)}{n}  (1)

it is called the frequency of the number k in the base-m representation of x. When we write the symbol τ_{k}(x) we are already assuming the existence of the limit in (1).

A classical result of Borel [6] says that for Lebesgue-almost every x ∈ [0, 1] we have τ_{k}(x) = 1/m for every k. Furthermore, for m = 2, Hardy and Littlewood [10] showed that for Lebesgue-almost every x ∈ [0, 1], k = 0, 1, and all sufficiently large n,

|τ_{k}(x, n) − \frac{1}{2}| < \sqrt{\frac{log n}{n}}.

2000 Mathematics Subject Classification. Primary: 11K55, 37C45.

Key words and phrases. frequencies of digits, Hausdorff dimension, multifractal analysis.

L. Barreira was partially supported by the Center for Mathematical Analysis, Geometry, and Dynamical Systems, through FCT’s Funding Program.

In particular, Lebesgue-almost all numbers are normal in every integer base. This remarkable result (even though it is today straightforward to prove in a variety of ways) does not mean that all numbers are normal. In fact we shall see that quite the opposite happens.

Consider now the set

F_{m}(α_{0}, …, α_{m−1}) = {x ∈ [0, 1] : τ_{k}(x) = α_{k} for k = 0, …, m − 1} , (2)

whenever α_{0} + ⋯ + α_{m−1} = 1 with α_{i} ∈ [0, 1] for each i. It is composed of the numbers in [0, 1] having a ratio α_{k} of digits equal to k in its base-m representation for each k. A precursor result concerning the size of these sets from the point of view of dimension theory is due to Besicovitch [4]. For m = 2, he showed that if α ∈ (0, \frac{1}{2}) then

dim_{H} \{x ∈ [0, 1] : lim sup_{n→∞} \frac{τ_{1}(x, n)}{n} ≤ α\} = −\frac{α log α + (1 − α) log(1 − α)}{log 2},

where dim_{H} Z denotes the Hausdorff dimension of the set Z. More detailed information was later obtained by Eggleston [8], who showed that

dim_{H} F_{m}(α_{0}, …, α_{m−1}) = −\frac{∑_{k=0}^{m−1} α_{k} log α_{k}}{log m} .  (3)

An immediate consequence is that if α_{i} ∈ (0, 1) for some i, then the set F_{m}(α_{0}, …, α_{m−1}) is nonempty (and thus dense in [0, 1]), with uncountable many points and even positive Hausdorff dimension. The work of Eggleston was further generalized by Billingsley (see his book [5] for details and references; see also Section 5.4).

We now consider sets of points for which the limit in (1) does not exist. For each k ∈ {0, …, m − 1} we define the set

M_{k} = \{x ∈ [0, 1] : lim inf_{n→∞} \frac{τ_{k}(x, n)}{n} < lim sup_{n→∞} \frac{τ_{k}(x, n)}{n}\} .  (4)

Notice that M_{k} has zero Lebesgue measure, due to the above-mentioned result of Borel. Clearly,

[0, 1] = ⋃_{(α_{0},... ,α_{m−1})∈L_{m}} F_{m}(α_{0}, …, α_{m−1}) ∪ ⋃_{k=0}^{m−1} M_{k},  (5)

where

L_{m} = {(α_{0}, …, α_{m−1}) ∈ [0, 1]^{m} : α_{0} + ⋯ + α_{m−1} = 1} .  (6)

In this paper we provide further nontrivial information about the decomposition in (5). In particular we prove the following statement.

Theorem 1. For each k ∈ {0, …, m − 1} the set M_{k} contains a dense G_{δ} set in [0, 1], and

dim_{H} ⋂_{k=0}^{m−1} M_{k} = 1.  (7)

Theorem 1 implies that ⋃_{k=0}^{m−1} M_{k} has Hausdorff dimension equal to 1, and thus, from the point of view of dimension theory, it is as large as the interval [0, 1]. On the other hand, the union ⋃_{k=0}^{m−1} M_{k} has not only zero Lebesgue measure but also zero measure with respect to any measure which is invariant under the map x ↦ mx (mod 1) (see Section 2 for details), and thus the set ⋃_{k=0}^{m−1} M_{k} is rather small from the point of view of measure theory.

We can also consider sets more complicated than those in (2), and in particular sets defined by linear or even nonlinear relations among the numbers τ_{k}(x). These generalizations are described in the remaining sections. Here we shall give a simple but nontrivial example. Let m = 4, and define the set

F = {x ∈ [0, 1] : τ_{1}(x) = 5τ_{0}(x)}.

This is the set of numbers in [0, 1] such that its base-4 representation has a ratio of ones which is five times the ratio of zeros. The ratios of twos and threes is arbitrary. Again, the nonuniqueness of the representation is not an issue in the study of Hausdorff dimension. It is easy to see that

F ⊃ ⋃_{α∈[0,1/6]} ⋃_{β∈[0,1−6α]} F_{4}(α, 5α, β, 1 − 6α − β).  (8)

We emphasize that the inclusion is proper since F contains points for which τ_{2}(x) and τ_{3}(x) are not well-defined (this fact substantially complicates the problem of computing dim_{H} F since a priori this dimension may not be entirely carried by the union in (8)). We shall prove that

dim_{H} F = \frac{log(2 + 6/5^{5/6})}{log 3} ≈ 0.91779 ⋯ (in base 10).  (9)

We first remark that it is easy to show that this last number is a lower bound for dim_{H} F. Namely, it follows from (3) and (8) that

dim_{H} F ≥ max_{α∈[0,1/6]} max_{β∈[0,1−6α]} dim_{H} F_{4}(α, 5α, β, 1 − 6α − β)

= max_{α∈[0,1/6]} −\frac{α log α + 5α log(5α) + (1 − 6α) log \frac{1−6α}{2}}{log 4}

(10)

The maximum is attained at α = 1/(2 · 5^{5/6} + 6) and it is a straightforward computation to show that it is equal to the constant in (9). This establishes the lower bound.

The corresponding upper bound is more delicate, since the union in (8) is composed of an uncountable number of nonempty pairwise disjoint sets. Moreover the inclusion in (8) is proper. This is where the theory of multifractal analysis comes into the play. Namely, using what is called a conditional variational principle we can show that although the inclusion is proper, the Hausdorff dimension of F is carried by exactly one set in the union in (8). We now formulate a particular case of the conditional variational principle that is sufficient for the purpose of the present example.

Theorem 2. For each k ≠ ℓ and β ≥ 0 we have

dim_{H}{x ∈ [0, 1] : τ_{k}(x) = βτ_{ℓ}(x)}

= max \{−\frac{∑_{j=0}^{m−1} α_{j} log α_{j}}{log m} : (α_{0}, …, α_{m−1}) ∈ L_{m} and α_{k} = βα_{ℓ}\}

= \frac{log(m − 2 + (β + 1)/β^{β/(β+1)})}{log m}.

An easy consequence of Theorem 2 and (3) is that for each k ≠ ℓ and β ≥ 0, there exists (α_{0}, …, α_{m−1}) ∈ L_{m} such that

F_{m}(α_{0}, …, α_{m−1}) ⊂ {x ∈ [0, 1] : τ_{k}(x) = βτ_{ℓ}(x)}

and

dim_{H} F_{m}(α_{0}, …, α_{m−1}) = dim_{H}{x ∈ [0, 1] : τ_{k}(x) = βτ_{ℓ}(x)}.

In particular, setting m = 4, k = 1, ℓ = 0, and β = 5, this observation implies that the inequality in (10) is in fact an identity, thus establishing the claim in (9).

The main advantage of our approach is that the classes of problems that we consider (which a priori could seem of very different nature) can be treated in a unified manner, as an application of the theory of multifractal analysis. Another advantage of this approach is that the value of the Hausdorff dimension does not need to be guessed a priori. In some works this a priori guess is crucial in order to construct auxiliary measures sitting on the set. These measures are then used to establish, rigorously, the value of the Hausdorff dimension.

The statements formulated above are consequences of more general statements established in this paper. As mentioned before, our results are based on recent work concerning the multifractal analysis of dynamical systems. On the other hand, we emphasize that the paper is self-contained. In particular, we assume no former knowledge of multifractal analysis.

The description of the state-of-the-art of multifractal analysis in 1997 can be found in the book by Pesin [12]. For some later developments (and in particular those concerning the results that we use here) the reader should look at the papers in the bibliography. In particular our approach requires a multidimensional version of the classical multifractal analysis. Such a version was first introduced by the authors in [2].

The structure of the paper is as follows. The necessary notions from ergodic theory are briefly recalled in Section 2. In Section 3 we establish Theorem 1 and several related results. In particular, we show that the set M_{k} can be further decomposed in a natural way into an uncountable union of pairwise disjoint sets with positive Hausdorff dimension. The above-mentioned conditional variational principle (of which Theorem 2 is a particular case) is described in Section 4. Further applications to number-theoretical problems are given in Section 5.

Acknowledgment. We would like to thank the referee for a number of good suggestions that helped us improve the exposition. We also would like to thank Christian Wolf for his comments.

2. Basic notions

Fix a positive integer m and consider the map g_{m}: [0, 1] → [0, 1] defined by g_{m}x = mx (mod 1). Observe that if 0.x_{1}x_{2} ⋯ is a base-m representation of x ∈ [0, 1], then g_{m}x = 0.x_{2}x_{3} · · ·.

Let μ be a g_{m}-invariant probability measure on [0, 1], i.e., a probability measure such that μ(g_{m}^{−1}A) = μ(A) for every measurable set A ⊂ [0, 1].

The entropy of g_{m} with respect to μ is defined by

h_{μ}(g_{m}) = inf_{n≥1} −\frac{1}{n} ∑_{i_{1}···i_{n}} μ(I_{i_{1}···i_{n}}) log μ(I_{i_{1}···i_{n}}),  (11)

where

I_{i_{1}···i_{n}} = [0.i_{1} ⋯ i_{n}, 0.i_{1} ⋯ i_{n} + m^{−n}).  (12)

We need the following basic result of ergodic theory (see for example [11, Chapters 1 and 2] for details).

Proposition 3. We have

h_{μ}(g_{m}) = inf_{n≥1} − ∑_{i_{1}···i_{n}} μ(I_{i_{1}···i_{n}}) log \frac{μ(I_{i_{1}···i_{n}})}{μ(I_{i_{2}···i_{n}})}

= ∫_{0}^{1} lim_{n→∞} \frac{log μ(I_{x_{1}···x_{n}})}{−n} dμ(x),

where the limit exists for μ-almost every x = 0.x_{1}x_{2} ⋯ ∈ [0, 1].

It follows from (11) that

h_{μ}(g_{m}) ≤ − ∑_{k=0}^{m−1} μ(I_{k}) log μ(I_{k}).  (13)

Given (α_{0}, …, α_{m−1}) ∈ L_{m} (see (6)), consider the g_{m}-invariant probability measure μ = μ_{α_{0},... ,α_{m−1}} such that μ(I_{i_{1}···i_{n}}) = α_{i_{1}} ⋯ α_{i_{n}} for each I_{i_{1}···i_{n}}. It is called a Bernoulli measure. It follows easily from the first formula for h_{μ}(g_{m}) in Proposition 3 that

h_{μ_{α_{0},... ,α_{m−1}}} (g_{m}) = − ∑_{k=0}^{m−1} α_{k} log α_{k}.  (14)

Let now ℳ be the family of g_{m}-invariant probability measures on [0, 1]. By (13) and (14) we obtain

max{h_{μ}(g_{m}) : μ ∈ ℳ and μ(I_{k}) = α_{k} for each k} = h_{μ_{α_{0},... ,α_{m−1}}} (g_{m}). (15)

Recall that a probability measure μ is ergodic if any g_{m}-invariant set has either zero or full μ-measure (a set A is g_{m}-invariant if g_{m}^{−1}A = A). For example, Bernoulli measures are ergodic. We define the Hausdorff dimension dim_{H} μ of the measure μ by

dim_{H} μ = inf{dim_{H} Z: μ(Z) = 1}.

We now consider the relation between entropy and Hausdorff dimension.

Proposition 4. For any measure μ ∈ ℳ we have

dim_{H} μ ≥ h_{μ}(g_{m})/log m,  (16)

with equality when μ is ergodic.

Proof. Assume first that μ is ergodic. In this case (see for example [12]) it is known that

dim_{H} μ = lim_{n→∞} \frac{log μ(I_{x_{1}···x_{n}})}{−n log m}

for μ-almost every x = 0.x_{1}x_{2} ⋯ ∈ [0, 1]. It follows from the second formula for h_{μ}(g_{m}) in Proposition 3 that dim_{H} μ = h_{μ}(g_{m})/ log m.

Consider now an arbitrary measure μ ∈ ℳ and an ergodic decomposition (μ_{α})_{α∈S} of μ (it always exists; see for example [14, Section 6.2]). This means that for each α ∈ S the measure μ_{α} is ergodic and there exists a measure ν on S such that μ(Z) = ∫_{S} μ_{α}(Z) dν(α) for every measurable set Z. If μ(Z) = 1 then μ_{α}(Z) = 1 for ν-almost every α ∈ S. Hence,

dim_{H} Z ≥ dim_{H} μ_{α} = h_{μ_{α}}(g_{m})/ log m.

Integrating over α we obtain (see for example [14, Theorem 8.4])

dim_{H} Z ≥ ∫_{S} h_{μ_{α}}(g_{m}) dν(α)/ log m = h_{μ}(g_{m})/ log m.

Taking the infimum over all the sets Z with μ(Z) = 1 we obtain (16).

We note that the inequality in (16) is in general strict in the case of nonergodic measures. Explicit examples can be readily obtained for instance from the following properties: if μ_{1} and μ_{2} are ergodic measures and μ = c_{1}μ_{1} + c_{2}μ_{2} with c_{1} + c_{2} = 1 and c_{1}, c_{2} > 0 then

dim_{H} μ = max{dim_{H} μ_{1}, dim_{H} μ_{2}}

and h_{μ}(g_{m}) = c_{1}h_{μ_{1}}(g_{m}) + c_{2}h_{μ_{2}}(g_{m}).

3. Irregular sets

In this section we establish Theorem 1 on the “size” of the sets M_{k} (see (4)) from the points of view of topology and dimension theory. It is in fact a particular case of stronger statements proved in this section.

For each \underline{α} < \overline{α} we consider the set

M_{k}^{\underline{α},\overline{α}} = \{x ∈ [0, 1] : lim inf_{n→∞} \frac{τ_{k}(x, n)}{n} = \underline{α} and lim sup_{n→∞} \frac{τ_{k}(x, n)}{n} = \overline{α}\} .

Notice that M_{k}^{\underline{α},\overline{α}} has zero measure with respect to any g_{m}-invariant probability measure. We have

M_{k} = ⋃_{0≤\underline{α}<\overline{α}≤1} M_{k}^{\underline{α},\overline{α}},  (17)

and hence, the interval [0, 1] can be decomposed into the disjoint union

[0, 1] = ⋃_{(α_{0},... ,α_{m−1})∈L_{m}} F_{m}(α_{0}, …, α_{m−1}) ∪ ⋃_{k=0}^{m−1} ⋃_{0≤\underline{α}<\overline{α}≤1} M_{k}^{\underline{α},\overline{α}}.

This type of decomposition is often called a multifractal decomposition. The theory of multifractal analysis has mainly been concerned with sets such as F_{m}(α_{0}, …, α_{m−1}) that consist of points for which certain limit or limits exist (see (1) and (2)). On the other hand, it was recently observed that the “irregular parts” of certain multifractal decompositions (of the type of those in (17)) may be (and often are, in a very precise sense) rather large from the points of view of topology and dimension theory. This allows us to have a much more detailed information about multifractal decompositions.

We are also interested in the irregular sets M_{k}^{\underline{α},\overline{α}}. We shall prove that even though they are rather small from the point of view of measure theory they have positive Hausdorff dimension. Furthermore, one of them is residual (i.e., it contains a dense G_{δ} set).

Proposition 5. For each k ∈ {0, …, m − 1} the set M_{k}^{0,1} is residual.

Proof. Choose ℓ ∈ {0, …, m−1} different from k. Let x = 0.x_{1}x_{2} ⋯ ∈ [0, 1] and fix an integer n ∈ ℕ. We consider the set U_{n}(x) of points y = 0.y_{1}y_{2} ⋯ ∈ [0, 1] such that

y_{i} = \begin{cases}x_{i} & if 1 ≤ i ≤ n \\ k & if n < i ≤ n^{2} \\ ℓ & if n^{2} < i ≤ n^{3} \end{cases} .

Observe that if y ∈ U_{n}(x) then

\frac{τ_{k}(y, n^{2})}{n^{2}} ≥ 1 − \frac{1}{n} and \frac{τ_{k}(y, n^{3})}{n^{3}} ≤ \frac{1}{n}.  (18)

Note that only the first n^{3} digits of y are specified. The open set

V_{m} = ⋃_{n>m} ⋃_{x∈[0,1]} int U_{n}(x)

is dense in [0, 1]. It follows from (18) that the dense G_{δ} set ⋂_{m=1}^{∞} V_{m} is contained in M_{k}^{0,1}. This completes the proof.

One can easily verify that the G_{δ} set ⋂_{m=1}^{∞} V_{m} constructed in the proof of Proposition 5 (and that is dense in M_{k}^{0,1}) has zero Hausdorff dimension. On the other hand we shall see below (see Theorem 7) that dim_{H} M_{k}^{\underline{α},\overline{α}} > 0 whenever 0 < \underline{α} < \overline{α} < 1 (and for each 0 ≤ \underline{α} < \overline{α} ≤ 1 whenever m > 2).

In view of (17), Proposition 5 implies that the set M_{k} is residual. Thus, in order to establish Theorem 1 it remains to prove the identity (7). This will be obtained as a consequence of a more general statement.

Given functions φ, ψ: [0, 1] → ℝ such that ψ > 0 we consider the set

K_{α}(φ, ψ) = \{x ∈ [0, 1] : lim_{n→∞} \frac{∑_{i=0}^{n} φ(g_{m}^{i}x)}{∑_{i=0}^{n} ψ(g_{m}^{i}x)} = α\} ,  (19)

where g_{m} is defined by g_{m}x = mx (mod 1). For example, if

φ_{k} = χ_{[k/m,(k+1)/m)} and ψ_{k} = 1 for k = 0, …, m − 1  (20)

then

⋂_{k=0}^{m−1} K_{α_{k}}(φ_{k}, ψ_{k}) = F_{m}(α_{0}, …, α_{m−1}).

We shall also consider some discontinuous functions. We call a function φ: [0, 1] → ℝ m-Hölder continuous if it is piecewise Hölder continuous with finitely many discontinuities and at most at negative powers of m.

Theorem 6. Let φ_{1}, …, φ_{d}, ψ_{1}, …, ψ_{d} be m-Hölder continuous functions with ψ_{i} > 0 for each i. We have

dim_{H} ([0, 1] \ ⋃_{i=1}^{d} ⋃_{α∈ℝ}K_{α}(φ_{i}, ψ_{i})) = 1

provided that K_{α}(φ_{i}, ψ_{i}) = [0, 1] for no i and no α.

Proof. We use the approach developed in [3] based on the notion of distinguishing family of measures. We recall that a family of invariant probability measures μ_{1}, …, μ_{ℓ} is a distinguishing family for the sequences of functions (f_{1n})_{n}, …, (f_{dn})_{n} provided that for i = 1, …, d there exist measures ν_{i1} and ν_{i2} in {μ_{1}, …, μ_{ℓ}} and constants a_{i1} ≠ a_{i2} such that for each j = 1, 2 and ν_{ij}-almost every x,

lim_{n→∞} f_{in}(x) = a_{ij}.

Set

Λ = {x ∈ [0, 1] : lim inf_{n→∞} f_{in}(x) < lim sup_{n→∞} f_{in}(x) for i = 1, …, d} . (21)

The following statement is a particular case of Theorem 7.6 in [3].

Lemma 1. If the ergodic g_{m}-invariant probability measures μ_{1}, …, μ_{ℓ} form a distinguishing family for the sequences of m-Hölder continuous functions (f_{1n})_{n}, …, (f_{dn})_{n} then

dim_{H} Λ ≥ min{dim_{H} μ_{1}, …, dim_{H} μ_{ℓ}}.

Consider the sequences

f_{in}(x) = \frac{∑_{j=0}^{n} φ_{i}(g_{m}^{j}x)}{∑_{j=0}^{n} ψ_{i}(g_{m}^{j}x)}

for i = 1, …, d. It is easy to verify that

Λ = [0, 1] \ ⋃_{i=1}^{d} ⋃_{α∈ℝ}K_{α}(φ_{i}, ψ_{i}).

By Theorem 7.3 in [3], for each i = 1, …, d and ε > 0 there exist ergodic g_{m}-invariant probability measures ν_{i1} and ν_{i2} satisfying

min{dim_{H} ν_{i1}, dim_{H} ν_{i2}} > 1 − ε

for each i, such that the family {ν_{i1}, ν_{i2} : i = 1, …, d} is a distinguishing family of measures for the sequences of functions (f_{1n})_{n}, …, (f_{dn})_{n}. More precisely, for j = 1, 2 and ν_{ij}-almost every x ∈ [0, 1] we have

lim_{n→∞} f_{in}(x) = \frac{∫_{0}^{1} φ_{i} dν_{ij}}{∫_{0}^{1} ψ_{i} dν_{ij}} .

Furthermore

\frac{∫_{0}^{1} φ_{i} dν_{i1}}{∫_{0}^{1} ψ_{i} dν_{i1}} ≠ \frac{∫_{0}^{1} φ_{i} dν_{i2}}{∫_{0}^{1} ψ_{i} dν_{i2}}

for each i, and Birkhoff’s ergodic theorem (see for example [11, Chapter 1]) shows that {ν_{i1}, ν_{i2} : i = 1, …, d} is a distinguishing family of measures for the sequences of functions (f_{1n})_{n}, …, (f_{dn})_{n}.

This allows us to apply Lemma 1 and conclude that

dim_{H} Λ ≥ min{dim_{H} ν_{i1}, dim_{H} ν_{i2} : i = 1, …, d} > 1 − ε.

The arbitrariness of ε yields the desired result.

One can show that in the case of m-Hölder continuous functions φ and ψ the following conditions are equivalent (see [1] and [3] for details):

1. K_{α}(φ, ψ) = [0, 1] for no α;

2. K_{α}(φ, ψ) is a nonempty proper subset of [0, 1] for some α;

3. K_{α}(φ, ψ) is a nonempty proper dense subset of [0, 1] for every α in some interval;

4. there exists no constant c ∈ ℝ such that φ − cψ = a − a ∘ g_{m} for some bounded function a: [0, 1] → ℝ.

We can now establish Theorem 1.

Proof of Theorem 1. The first statement follows from Proposition 5. Setting φ_{k} and ψ_{k} as in (20), one can easily verify that K_{α}(φ_{k}, ψ_{k}) = [0, 1] for no k and no α (note that one can explicitly determine a point in K_{α}(φ_{k}, ψ_{k}) for each α ∈ [0, 1]). Furthermore, since

⋂_{k=0}^{m−1} M_{k} = [0, 1] \ ⋃_{k=0}^{m−1} ⋃_{α∈ℝ}K_{α}(φ_{i}, ψ_{i}),

the second statement follows from Theorem 6.

We now study the Hausdorff dimension of the sets M_{k}^{\underline{α},\overline{α}} and more generally of intersections of these sets. Given a rectangle

R = [\underline{α}_{0}, \overline{α}_{0}] × ⋯ × [\underline{α}_{m−1}, \overline{α}_{m−1}] ⊂ [0, 1]^{m},

we consider the decomposition of ∂R into the m pairs \underline{R}_{k}, \overline{R}_{k} of closed faces of R, where \underline{R}_{k} corresponds to \underline{α}_{k} and \overline{R}_{k} corresponds to \overline{α}_{k}. For each k we define the numbers

\underline{d}_{k} = max\{dim_{H} F_{m}(z) : z ∈ \underline{R}_{k} ∩ L_{m}\}

and

\overline{d}_{k} = max\{dim_{H} F_{m}(z) : z ∈ \overline{R}_{k} ∩ L_{m}\}.

We also define the set

M_{R} = ⋂_{k=0}^{m−1} M_{k}^{\underline{α}_{k},\overline{α}_{k}}.

The following statement establishes an explicit formula for the Hausdorff dimension of the irregular set M_{R} in terms of the numbers \underline{d}_{k} and \overline{d}_{k}. In particular, although the set M_{R} is totally unrelated to the “regular” part of the multifractal decomposition, this formula indicates that the Hausdorff dimension of M_{R} is entirely carried by a single “regular” set F_{m}(z), where z is some vector in one of the faces of the rectangle R.

Theorem 7. If int R ≠ ∅ and R ∩ L_{m} ≠ ∅ then

dim_{H} M_{R} = min\{\underline{d}_{k}, \overline{d}_{k} : k = 0, …, m − 1\}.

Proof. Set φ_{k} and ψ_{k} as in (20). Let \underline{z}_{k} ∈ \underline{R}_{k} ∩ L_{m} and \overline{z}_{k} ∈ \overline{R}_{k} ∩ L_{m} be vectors such that

dim_{H} F_{m}(\underline{z}_{k}) = \underline{d}_{k} and dim_{H} F_{m}(\overline{z}_{k}) = \overline{d}_{k}.

Since \underline{z}_{k} ∈ \underline{R}_{k} ⊂ R and \overline{z}_{k} ∈ \overline{R}_{k} ⊂ R, the (ergodic) Bernoulli measures μ_{\underline{z}_{k}} and μ_{\overline{z}_{k}} satisfy

∫_{0}^{1} φ_{k} dμ_{\underline{z}_{k}} = \underline{α}_{k}, ∫_{0}^{1} φ_{k} dμ_{\overline{z}_{k}} = \overline{α}_{k},  (22)

and

∫_{0}^{1} φ_{ℓ} dμ_{\underline{z}_{k}} ∈ [\underline{α}_{ℓ}, \overline{α}_{ℓ}], ∫_{0}^{1} φ_{ℓ} dμ_{\overline{z}_{k}} ∈ [\underline{α}_{ℓ}, \overline{α}_{ℓ}]  (23)

for every k and ℓ. Furthermore, by Eggleston’s result, Proposition 4, and (14) we have

dim_{H} μ_{\underline{z}_{k}} = \underline{d}_{k} and dim_{H} μ_{\overline{z}_{k}} = \overline{d}_{k}.  (24)

It follows from Birkhoff’s ergodic theorem and (22) that the measures μ_{\underline{z}_{k}}, μ_{\overline{z}_{k}} for k = 0, …, m − 1 form a distinguishing family (see the proof of Theorem 6 for the definition) for the sequences

f_{kn} = ∑_{j=0}^{n} φ_{k} ∘ g_{m}^{j}  (25)

for k = 0, …, m − 1.

We now require a version of Lemma 1 for the set Γ_{R} defined by

\{x ∈ [0, 1] : lim inf_{n→∞} f_{in}(x) = \underline{α}_{i} and lim sup_{n→∞} f_{in}(x) = \overline{α}_{i} for i = 1, …, d\} .

(26)

Notice that if int R ≠ ∅ then Γ_{R} ⊂ Λ (see (21)). The following statement is obtained from a straightforward modification of the proof of Theorem 7.6 in [3] (see also the observations at the end of this section).

Lemma 2. Let μ_{1}, …, μ_{ℓ} be a distinguishing family of ergodic g_{m}-invariant probability measures for the sequences (f_{1n})_{n}, …, (f_{dn})_{n}. Assume that for each i, j = 1, …, d there exist measures ν_{i1} and ν_{i2} in {μ_{1}, …, μ_{ℓ}} and constants a_{ij} and b_{ij} such that for each i and j:

1. a_{ii} = \underline{α}_{i}, b_{ii} = \overline{α}_{i}, and a_{ij}, b_{ij} ∈ [\underline{α}_{i}, \overline{α}_{i}];

2.

lim_{n→∞} f_{in}(x) = a_{ij} for ν_{j1}-almost every x,
lim_{n→∞} f_{in}(x) = b_{ij} for ν_{j2}-almost every x.

If int R ≠ ∅ and R ∩ L_{m} ≠ ∅ then

dim_{H} Γ_{R} ≥ min{dim_{H} μ_{1}, …, dim_{H} μ_{ℓ}}.

Using (22) and (23), we can apply Lemma 2 to the sequences in (25) to conclude that

dim_{H} M_{R} ≥ κ =^{def} min\{\underline{d}_{k}, \overline{d}_{k} : k = 0, …, m − 1\}.

We now obtain an upper bound for dim_{H} M_{R}. Given x ∈ [0, 1] we denote by V (x) the set of accumulation points (in the weak-∗ topology) of the sequence of measures

\frac{1}{n} ∑_{j=0}^{n−1} δ_{g_{m}^{j}x},  (27)

where δ_{y} denotes the probability measure with δ_{y}({y}) = 1. We shall use the following statement.

Lemma 3. If

X_{t} = {x ∈ [0, 1] : dim_{H} μ ≤ t for some μ ∈ V (x)}

then dim_{H} X_{t} ≤ t.

Proof of the lemma. The lemma is a version of a statement of Bowen in [7] saying that (in our setup) if

Y_{t} = {x ∈ [0, 1] : h_{μ}(g_{m}) ≤ t for some μ ∈ V (x)}

then dim_{H} Y_{t} ≤ t/ log m. It should be noted that the number log m · dim_{H} Z coincides with the topological entropy of g_{m} on the set Y_{t} (and since this set may in general be noncompact we are referring to the notion of topological entropy for noncompact sets introduced by Bowen in [7]). We shall deduce the lemma from Bowen’s result. By Proposition 4, we have h_{μ}(g_{m})/ log m ≤ dim_{H} μ. Therefore, X_{t} ⊂ Y_{t log m} and hence, using Bowen’s result, dim_{H} X_{t} ≤ t.

When x ∈ M_{R}, for each k = 0, …, m − 1 the sequence of measures in (27) has accumulation points μ_{\underline{w}_{k}} and μ_{\overline{w}_{k}} for some \underline{w}_{k} ∈ \underline{R}_{k} and \overline{w}_{k} ∈ \overline{R}_{k}. It follows from (24) that

min\{dim_{H} μ_{\underline{w}_{k}}, dim_{H} μ_{\overline{w}_{k}} : k = 0, …, m − 1\} ≤ κ.

Therefore M_{R} ⊂ X_{κ} and Lemma 3 implies that dim_{H} M_{R} ≤ κ. This completes the proof.

The following is now an immediate consequence of Theorem 7.

Corollary 8. For each k ∈ \{0, …, m−1\} and \underline{α}, \overline{α} ∈ [0, 1] such that \underline{α} < \overline{α}, the set M_{k}^{\underline{α},\overline{α}} has positive Hausdorff dimension.

As we observed, Lemma 2 is obtained from a straightforward modification of the proof of Theorem 7.6 in [3]. Nevertheless, the proof itself (as is already the case in [3]) involves considerable technical difficulties, related to the study of the pointwise dimension of noninvariant measures (sitting on sets that have zero measure with respect to any invariant measure). On the other hand, it is easy to describe why the assumptions in Lemma 2 are crucial when compared to those in Lemma 1 and we shall do it now. Notice first that although the sets Λ and Γ_{R} (see (21) and (26)) satisfy Γ_{R} ⊂ Λ this inclusion is in general proper. The proof of Lemma 2 (that simply follows the proof of Theorem 7.6 in [3]) starts with the juxtaposition of cylinder sets at the level of symbolic dynamics which are successively typical with respect to ν_{i1} and ν_{i2} for i = 1, …, d, in this order. We recall that, for a point x ∈ [0, 1], the cylinder sets corresponding to the intervals C_{n}(x) = (x − m^{−n}, x + m^{−n}) ∩ [0, 1] are said to be typical with respect to the measure μ if

lim_{n→∞} −\frac{log μ(C_{n}(x))}{n log m} = dim_{H} μ.

Then we repeat the same procedure ad infinitum, choosing cylinder sets which are successively typical with respect to ν_{i1} and ν_{i2} for i = 1, …, d. Since int R ≠ ∅ we obtain with this construction a subset Λ′ of Λ (see (21)). When d = 1 one has Λ′ ⊂ Γ_{R} (see (26)) under the assumptions of Lemma 2, and in fact also under those of Lemma 1. However, when d > 1 the assumptions in Lemma 1 are in general not enough to construct a subset of Γ_{R} using this procedure. This is due to the fact that the cylinder sets juxtaposed between two pairs with the same fixed i (i.e., the pairs of cylinder sets corresponding to ν_{i1} and ν_{i2}, which occur infinitely often) may change the values of lim inf_{n→∞} f_{in}(x) and lim sup_{n→∞} f_{in}(x). More precisely, we can construct a set Λ′ ⊂ Λ such that for every x ∈ Λ′ and i = 1, …, d,

lim inf_{n→∞} f_{in}(x) ≤ \underline{α}_{i} and lim sup_{n→∞} f_{in}(x) ≥ \overline{α}_{i},

but a priori these inequalities may be strict (unless d = 1). On the other hand, under the additional assumptions of Lemma 2, we can construct Λ′ in such a way that for every x ∈ Λ′ and i = 1, …, d,

lim inf_{n→∞} f_{in}(x) = \underline{α}_{i} and lim sup_{n→∞} f_{in}(x) = \overline{α}_{i},

and thus Λ′ ⊂ Γ_{R}.

4. Conditional variational principle

In this section we describe the conditional variational principle mentioned in the introduction.

We first recall the concept of topological pressure. The topological pressure of a continuous function φ: [0, 1] → ℝ with respect to g_{m} is defined by

P (φ) = lim_{n→∞} \frac{1}{n} log ∑_{i_{1}···i_{n}} exp sup_{I_{i_{1}···in}} ∑_{k=0}^{n−1} φ ∘ g_{m}^{k}.  (28)

For an m-Hölder continuous φ (i.e., a piecewise Hölder continuous function with finitely many discontinuities and at most at negative powers of m) the limit in (28) also exists and we still call it topological pressure of φ. We are particularly interested in locally constant functions. More precisely, consider a function φ such that

φ(0.x_{1}x_{2} ⋯) = a_{x_{1}···x_{κ}}

for some constants a_{i_{1}···i_{κ}} ∈ ℝ for i_{1}, …, i_{κ} ∈ {0, …, m−1} and some fixed positive integer κ. These are called κ-locally constant functions. Note that they are m-Hölder continuous. In particular, it follows easily from (28) that if φ is 1-locally constant then

P (φ) = lim_{n→∞} \frac{1}{n} log ∑_{i_{1}···i_{n}} ∏_{j=1}^{n} exp a_{i_{j}} = log ∑_{k=0}^{m−1} exp a_{k}.  (29)

Given functions φ_{k}, ψ_{k}: [0, 1] → ℝ with ψ_{k} > 0 for k = 1, …, d, and a vector α = (α_{1}, …, α_{d}) ∈ ℝ^{d}, we write

K_{α} = ⋂_{k=1}^{d} K_{α_{k}}(φ_{k}, ψ_{k}),  (30)

where each set K_{α_{k}}(φ_{k}, ψ_{k}) is defined by (19). For each μ ∈ ℳ we set

𝒫(μ) = (\frac{∫_{0}^{1} φ_{1} dμ}{∫_{0}^{1} ψ_{1} dμ}, …, \frac{∫_{0}^{1} φ_{d} dμ}{∫_{0}^{1} ψ_{d} dμ}) .

Barreira, Saussol and Schmeling [2] established the following conditional variational principle.

Theorem 9. Let φ_{1}, …, φ_{d}, ψ_{1}, …, ψ_{d} be m-Hölder continuous functions with ψ_{i} > 0 for each i. If α ∈ int 𝒫(ℳ), then

dim_{H} K_{α} = \frac{1}{log m} max \{h_{μ}(g_{m}) : μ ∈ ℳ and 𝒫(μ) = α\}

= \frac{1}{log m} inf \{P (∑_{k=1}^{d} q_{k}(φ_{k} − α_{k}ψ_{k})) : (q_{1}, …, q_{d}) ∈ ℝ^{d}\} .

(31)

We emphasize that the identities in (31) express the dimension spectrum 𝒟(α) = dim_{H} K_{α} in two different ways. The first formula for 𝒟 in (31) is a maximum over the closed set of measures μ for which 𝒫(α) = μ (and thus the name “conditional variational principle”). This first formula was obtained independently by Fan, Feng and Wu [9]. Unfortunately it is in general not easily amenable to explicit computations due to the fact that we have to know h_{μ}(g_{m}) for all such measures. This is why we are especially interested in the second formula.

The second formula for 𝒟 in (31) is an infimum of a real valued function involving the topological pressure. In view of applications, and in particular those in this paper, it is crucial to have this formula. For example, to know an explicit expression for the dimension spectrum it is often enough to study the derivative of the function

q ↦ P (∑_{k=1}^{d} q_{k}(φ_{k} − α_{k}ψ_{k})) .

We emphasize that even when the infimum in (31) does not allow one to obtain an explicit formula it is still crucial in several respects. In particular, under the assumptions of Theorem 9, it can be used to show that 𝒟 is analytic (see [1, 2] for details). Furthermore, the first example of a nonconvex spectrum was given in [1] also as an application of this formula.

It was also shown in [2, Theorem 14] that for each fixed Hölder exponent θ and a residual vector (φ_{1}, …, φ_{d}, ψ_{1}, …, ψ_{d}) in the space of θ-Hölder continuous functions we have:

1. \overline{int 𝒫(ℳ)} = 𝒫(ℳ);

2. dim_{H} K_{α} = 0 for every α ∈ ∂𝒫(ℳ).

We now describe a generalization of the first identity in (31), or more precisely of the formula (replacing the maximum by a supremum in (31))

dim_{H} K_{α} = \frac{1}{log m} sup \{h_{μ}(g_{m}) : μ ∈ ℳ and 𝒫(μ) = α\} .

In order to describe this generalization, let us consider continuous functions ζ: [0, 1] → U ⊂ ℝ^{r} and η: U → ℝ^{p}. For each α ∈ ℝ^{p} we define the set

K_{α}^{(η,ζ)} = \{x ∈ [0, 1]: lim_{n→∞} η (\frac{1}{n} ∑_{j=0}^{n−1} ζ(g_{m}^{j}x)) = α\} .

When

ζ = (φ_{1}, …, φ_{d}, ψ_{1}, …, ψ_{d}) and η(r_{1}, …, r_{2d}) = (\frac{r_{1}}{r_{d+1}} , …, \frac{r_{d}}{r_{2d}} )

we obtain K_{α}^{(η,ζ)} = K_{α} (see (30)).

The following is an immediate consequence of work of Takens and Verbitskiy [13], where we make the convention that sup ∅ = 0.

Theorem 10. Let ζ: [0, 1] → U ⊂ ℝ^{r} and η: U → ℝ^{p} be piecewise continuous functions with finitely many discontinuities and at most at negative powers of m. For each α ∈ ℝ^{p} we have

dim_{H} K_{α}^{(η,ζ)} = \frac{1}{log m} sup \{h_{μ}(g_{m}) : μ ∈ ℳ and η (∫_{0}^{1} ζ dμ) = α\} .

We observe that the classes of dynamical systems for which the statements in Theorems 9 and 10 were respectively established in [2] and [13] are more general than the situation considered here. However, none of these two papers includes the class of dynamical systems considered in the other one.

The identity in Theorem 10 says that for each α with K_{α}^{(η,ζ)} ≠ ∅ and each ε > 0 there exists a measure μ_{α,ε} ∈ ℳ for which

η (∫_{0}^{1} ζ dμ_{α,ε}) = α and h_{μ_{α,ε}}(g_{m})/ log m > dim_{H} K_{α}^{(η,ζ)} − ε.

Unfortunately, in general the measure μ_{α,ε} may not sit on K_{α}^{(η,ζ)}. Such a property would be crucial for example as a departure point to obtain similar results to those in Section 3 in this situation. On the other hand, under the assumptions of Theorem 9 it is shown in [2] that there exists an ergodic measure μ_{α} ∈ ℳ such that 𝒫(μ_{α}) = α with the additional properties

μ_{α}(K_{α}) = 1 and h_{μ_{α}}(g_{m})/ log m = dim_{H} K_{α}.  (32)

5. Applications to frequencies of digits

In this section we show how the conditional variational principle can be used in a number of problems in the study of the Hausdorff dimension of sets defined in terms of frequencies of digits.

5.1. Linear relations. When dealing with frequencies of digits it suffices to consider 1-locally constant functions (sometimes called digit-functions). In this case we can combine Theorems 9 and 10 to obtain a more explicit statement. In this section we always take ψ_{i} = 1 for i = 1, …, d in Theorem 9, and thus for each α = (α_{1}, …, α_{d}) ∈ ℝ^{d} the set K_{α} in (30) is given by

K_{α} = {x ∈ [0, 1] : lim_{n→∞} ∑_{j=0}^{n} φ_{i}(g_{m}^{j}x) = α_{i} for i = 1, …, d} .

For each μ ∈ ℳ set

𝒬(μ) = (∫_{0}^{1} φ_{1} dμ, …, ∫_{0}^{1} φ_{d} dμ) .

For simplicity we shall also write φ_{ik} = φ_{i}([k/m, (k + 1)/m)).

Theorem 11. Let φ_{i}: [0, 1] → ℝ be 1-locally constant functions for i = 1, …, d. The following properties hold:

1. if α = (α_{1}, …, α_{d}) ∈ 𝒬(ℳ) then

dim_{H} K_{α} = \frac{1}{log m} max \{− ∑_{k=0}^{m−1} β_{k} log β_{k} : (β_{0}, …, β_{m−1}) ∈ Δ_{m}\} , (33)

where

Δ_{m} = {(β_{0}, …, β_{m−1}) ∈ L_{m} : ∑_{k=0}^{m−1} β_{k}φ_{ik} = α_{i} for i = 1, …, d};

2. if, in addition, α = (α_{1}, …, α_{d}) ∈ int 𝒬(ℳ) then

dim_{H} K_{α} = inf {log_{m} ∑_{k=0}^{m−1} exp ∑_{i=1}^{d} q_{i}(φ_{ik} − α_{i}) : (q_{1}, …, q_{d}) ∈ ℝ^{d}}; (34)

3. the function α ↦ dim_{H} K_{α} is continuous on 𝒬(ℳ).

Proof. Setting ζ = (φ_{1}, …, φ_{d}) and η = id it follows from Theorem 10 that

dim_{H} K_{α} = \frac{1}{log m} sup\{h_{μ}(g_{m}) : μ ∈ ℳ and 𝒬(μ) = α\}  (35)

for each α ∈ 𝒬(ℳ). Let μ be a g_{m}-invariant measure on [0, 1] and write β_{k} = μ(I_{k}) for each k. The condition 𝒬(μ) = α is equivalent to

(∑_{k=0}^{m−1} β_{k}φ_{1k}, …, ∑_{k=0}^{m−1} β_{k}φ_{dk}) = α.  (36)

Therefore, using (14) and (15) we can replace the supremum in (35) by the maximum in (33), and we obtain the first statement in the theorem.

By (29) we have

P (∑_{k=1}^{d} q_{k}(φ_{k} − α_{k}ψ_{k})) = log ∑_{k=0}^{m−1} exp ∑_{i=1}^{d} q_{i}(φ_{ik} − α_{i}).

Applying Theorem 9 we obtain the second statement in the theorem.

To complete the proof it is enough to show that the maximum in (33) varies continuously with α. Observe first that the condition in (36) defines a plane in ℝ^{m} varying continuously with α. The strict convexity of the function

(β_{0}, …, β_{m−1}) ↦ − ∑_{k=0}^{m−1} β_{k} log β_{k}

guarantees that the maximum in (33) also varies continuously with α. This completes the proof.

Theorem 11 offers two methods to compute the Hausdorff dimension of the set K_{α}, although of different nature. The first method involves the computation of the maximum in (33). Unfortunately it consists of a problem of conditional extrema. In applications we may try to use, for example, the method of Lagrange multipliers. This often leads to less explicit formulas. On the other hand, the second method to compute the Hausdorff dimension, based on the computation of the infimum in (34), should in general be more amenable to computation. Essentially it amounts to determine the extrema of a function involving the topological pressure, without any extra condition. Although the identity in (34) is only known to hold in int 𝒬(ℳ) (conjecturally it holds in 𝒬(ℳ)), the continuity of the function α ↦ dim_{H} K_{α} on 𝒬(ℳ) allows us to obtain dim_{H} K_{α} for α ∈ \overline{int 𝒬(ℳ)} from the knowledge of (34) on int 𝒬(ℳ). It is shown in [2] (see Section 4), that for each fixed Hölder exponent θ and a residual vector (φ_{1}, …, φ_{d}) in the space of θ-Hölder continuous functions (not necessarily 1-locally constant) we have \overline{int 𝒬(ℳ)} = 𝒬(ℳ).

Theorem 11 (and its straightforward generalization to κ-locally constant functions) allows us to provide a unified and simple approach to substantially complicated problems. Moreover, it follows from work in [2] that for each choice of functions φ_{i} one can explicitly exhibit a measure sitting on the level set K_{α}, in the sense that (32) holds. In the case of 1-locally constant functions these measures are always Bernoulli measures.

A first consequence of Theorem 11 is the classical result of Eggleston [8] described in the introduction.

Corollary 12. For every (α_{0}, …, α_{m−1}) ∈ L_{m},

dim_{H} F_{m}(α_{0}, …, α_{m−1}) = −\frac{∑_{k=0}^{m−1} α_{k} log α_{k}}{log m} .

Proof. Setting φ_{k} and ψ_{k} as in (20) for k = 0, …, m − 1, we obtain K_{α} = F_{m}(α_{0}, …, α_{m−1}). The statement follows immediately from Theorem 11.

Theorem 11 allows us to complete the proof of the results in the introduction.

Proof of Theorem 2. Set d = 1 and

φ_{1} = χ_{[k/m,(k+1)/m)} − βχ_{[ℓ/m,(ℓ+1)/m)}.

The first identity in the theorem follows from Theorem 11, (14), and (15). Furthermore, since 0 ∈ int 𝒬(ℳ) = (−β, 1), Theorem 11 shows that

dim_{H}\{x ∈ [0, 1] : τ_{k}(x) = βτ_{ℓ}(x)\} = inf_{q∈ℝ} \frac{log(e^{q} + e^{−βq} + m − 2)}{log m}.

It is straightforward to verify that the infimum is attained at q = \frac{log β}{1+β} and an easy computation yields the desired result.

For example, setting β = 1 in Theorem 2 we obtain

dim_{H}{x ∈ [0, 1] : τ_{k}(x) = τ_{ℓ}(x)} = 1,  (37)

independently of k, ℓ, and m. It is also interesting to observe that for a fixed β ≥ 0 the Hausdorff dimension in Theorem 2 tends to 1 when m → ∞. This corresponds to the fact that the disjoint union

⋃_{α_{k}=βα_{ℓ}} F_{m}(α_{0}, …, α_{m−1}) ⊂ {x ∈ [0, 1] : τ_{k}(x) = βτ_{ℓ}(x)}

contains sets with larger and larger Hausdorff dimension as m → ∞.

We emphasize that the formula with the maximum in (33) can also be used to obtain the explicit value of the Hausdorff dimension in Theorem 2. Although the computation is not as immediate as with the infimum in (34), in this special case it can be effected in a simple manner. This alternative approach reflects the fact that the entropy of an invariant measure is maximized by a mass distribution as uniform as possible (see (38) below).

We assume for simplicity that k = 0 and ℓ = 1 in Theorem 2. Set ρ = 1 − ∑_{j=2}^{m−1} α_{j}. We have α_{0} = ρ/(1 + β) and α_{1} = ρβ/(1 + β). One can easily verify that the function

(α_{2}, …, α_{m−1}) ↦ − ∑_{j=0}^{m−1} α_{j} log α_{j}

= −\frac{ρ}{1 + β} log \frac{ρ}{1 + β} − \frac{ρβ}{1 + β} log \frac{ρβ}{1 + β} − ∑_{j=2}^{m−1} α_{j} log α_{j}

attains its maximum when

α_{2} = ⋯ = α_{m−1} = \frac{1 − ρ}{m − 2}.  (38)

Therefore, the Hausdorff dimension in Theorem 2 is given by

max_{0≤α≤ \frac{1}{1+β}} −\frac{α log α + αβ log(αβ) + (1 − α − αβ) log \frac{1−α−αβ}{m−2}}{log m} .

One can verify that this maximum is attained at α = 1/(2β^{β/(β+1)} + β + 1), and hence obtain its explicit value.

A similar approach yields the following statement.

Corollary 13. Given integers i_{1} < ⋯ < i_{k} in {0, …, m − 1} and numbers β_{1}, …, β_{k} ∈ [0, 1] such that β =^{def} ∑_{j=1}^{k} β_{k} ≤ 1, we have

dim_{H}{x ∈ [0, 1] : (τ_{i_{1}}(x), …, τ_{i_{k}}(x)) = (β_{1}, …, β_{k})}

= −\frac{∑_{j=1}^{k} β_{j} log β_{j} + (1 − β) log \frac{1−β}{m−1}}{log m} .

For example, setting k = 1 we obtain

dim_{H}\{x ∈ [0, 1]: τ_{i}(x) = α\} = −\frac{α log α + (1 − α) log \frac{1−α}{m−1}}{log m} .

Note that this tends to 1 − α when m → ∞. In particular, the Hausdorff dimension of the set of numbers having 99.99% of zeros in their base-m representation is uniformly bounded away from zero as m → ∞. This should be contrasted with the behavior in Theorem 2 when m → ∞.

In view of the existence of nontrivial irregular sets with large Hausdorff dimension (see Section 3) the following is another nontrivial application of Theorem 11. Namely, we want to show that the set of points for which the frequency of some digits is zero and the set of points where the same digits do not occur have equal dimension.

Corollary 14. The Hausdorff dimension of the set of points for which the frequency of a number k of fixed digits in the base-m representation is zero equals the Hausdorff dimension of the set of points where the same digits do not appear in the base-m representation. The common value is log_{m}(m−k).

Proof. Let E be the set of points where the frequency of some digits in the base-m representation is zero. Without loss of generality we assume that the first k digits have frequency zero. Setting d = 1 and φ_{1} = χ_{[0,(k−1)/m)} it follows from Theorem 11 that dim_{H} E = log_{m}(m − k). Let now F ⊂ E be the set of points where the same digits do not appear in their base-m representation. Let μ be the (ergodic) Bernoulli measure on m − k symbols with equal probabilities. We have μ(F) = 1 (with the natural identification of a base-(m − k) representation with a base-m representation) and by Proposition 4, dim_{H} μ = log_{m}(m − k). Therefore dim_{H} F ≥ dim_{H} μ and dim_{H} E = dim_{H} F.

We can also consider more involved problems. Let A = (a_{ij}) be an d × m matrix and b = (b_{1}, …, b_{d}) ∈ ℝ^{d}. Consider the set K(A, b) of numbers x ∈ [0, 1] such that Aτ_{m}(x) = b, where τ_{m}(x) = (τ_{0}(x), …, τ_{m−1}(x)).

Corollary 15. If b ∈ int A(L_{m}) then

dim_{H} K(A, b) = max {− ∑_{k=0}^{m−1} α_{k} log_{m} α_{k} : (α_{0}, …, α_{m−1}) ∈ L_{m} ∩ A^{−1}b}

= inf {log_{m} ∑_{k=0}^{m−1} exp ∑_{i=1}^{d} q_{i}(a_{ik} − b_{i}) : (q_{1}, …, q_{d}) ∈ ℝ^{d}} .

Proof. For i = 1, …, d, set

φ_{i} = ∑_{j=0}^{m−1} a_{ij}χ_{[j/m,(j+1)/m)},

and note that 𝒬(ℳ) = A(L_{m}). The desired statement follows immediately from Theorem 11.

We remark that \overline{int A(L_{m})} = A(L_{m}) if and only if det(AA^{t}) ≠ 0, where A^{t} denotes the transpose of A.

We now give several nontrivial examples as applications of Corollary 15 (the computations are straightforward and are not reproduced here):

1. given integers a_{0}, …, a_{m−1}, not all zero, the set of points x ∈ [0, 1] such that

a_{0}τ_{0}(x) + ⋯ + a_{m−1}τ_{m−1}(x) = β

has Hausdorff dimension

log_{m} min {∑_{i=0}^{m−1} r^{a_{i}−β} : r > 0 and ∑_{i=0}^{m−1}(a_{i} − β)r^{a_{i}} = 0}

(note that this amounts to determine the positive real roots of the polynomial ∑_{i=0}^{m−1}(a_{i} − β)r^{a_{i}−min_{i} a_{i}});

2. the set of points x ∈ [0, 1] such that τ_{0}(x) + 2τ_{1}(x) = β has Hausdorff dimension

log_{m} [\frac{r^{1−β} + 2r^{−β}}{2 − β} ] ,

where

r = \frac{β − 1 + \sqrt{(β − 1)^{2} + 4β(β − 2)(m − 2)}}{4 − 2β};

3. the set of points x ∈ [0, 1] such that τ_{0}(x)+⋯+τ_{j−1}(x) = jβ (i.e., the average of the frequencies of the first j digits equals β) has Hausdorff dimension

log_{m} [j (\frac{(m − j)β}{1 − jβ} )^{1−jβ} + (m − j) (\frac{1 − jβ}{(m − j)β} )^{jβ}];

4. given γ ≥ 0, the set of points x ∈ [0, 1] such that τ_{0}(x)+τ_{1}(x) = γτ_{2}(x) has Hausdorff dimension

log_{m} [2 (\frac{γ}{2} )^{1/(γ+1)} + (\frac{2}{γ} )^{γ/(γ+1)} + m − 3]

(for example, this is log_{m}(2\sqrt{2} + m − 3) when γ = 1). Using results in [2] we can also compute the Hausdorff dimension of sets

that are obtained from the intersection of irregular sets (see Section 3) with those in this section. In particular, we can consider sets of points for which some fixed frequencies are not well-defined and for which the remaining ones satisfy some linear relations.

5.2. Nonlinear relations. Theorem 10 allows us to study continuous nonlinear relations between frequencies of digits. In this case there is in general no appropriate generalization of the formula given by Theorem 9 in terms of the topological pressure, and thus we have to use the variational principle in Theorem 10. This often makes the computations much harder when we study nonlinear relations between frequencies of digits. We shall concentrate here on nontrivial examples.

Fix m > 2. For each b > 0, we set

F_{b} = {x ∈ [0, 1] : τ_{1}(x) = e^{1−bτ_{0}(x)}/b}.

Corollary 16. If b > 2 then

dim_{H} F_{b} = log_{m} b + \frac{b − 2}{b} log_{m} (\frac{m − 2}{b − 2}) .

Proof. Define f(x) = e^{1−bx}/b. It follows from Theorem 10 that dim_{H} F_{b} is equal to the supremum of

−α_{0} log_{m} α_{0} − f(α_{0}) log_{m} f(α_{0}) − ∑_{i=2}^{m−1} α_{i} log_{m} α_{i}

under the assumption that α_{0} + f(α_{0}) + α_{2} + ⋯ + α_{m−1} = 1 and α_{i} ∈ [0, 1]. It is thus enough to determine the infimum of the function

G(α) = α log α + f(α) log f(α) + (1 − α − f(α)) log \frac{1 − α − f(α)}{m − 2} (39)

over all α ∈ [0, 1] such that α + f(α) ≤ 1. The derivative is

G′(α) = log α + f′(α) log f(α) − (1 + f′(α)) log \frac{1 − α − f(α)}{m − 2}.  (40)

For α = 1/b we have f(α) = α and f′(α) = −1, and hence, G′(α) = 0. Some elementary calculus shows that 1/b is indeed a global minimum of G. We conclude that dim_{H} F_{b} = −G(1/b)/ log m and the desired statement amounts now to an elementary computation.

The approach used in the proof of the corollary applies in a similar way to other types of sets. In particular, given a continuous function f: ℝ → ℝ the set

F_{f} = {x ∈ [0, 1] : τ_{1}(x) = f(τ_{0}(x))}

has Hausdorff dimension

dim_{H} F_{f} = −\frac{1}{log m} inf\{G(α) : α ∈ [0, 1] and α + f(α) ≤ 1\},  (41)

where G is the function defined by (39). In particular, when f is differentiable, if α ∈ (0, \frac{1}{2}) is such that f(α) = α and f′(α) = −1 it follows from (40) that G′(α) = 0 and we should verify if it is a global minimum.

The formula (41) allows us to determine how the dimension is affected by small perturbations of f. For example, let f_{ε}(x) = x + εx^{2} (and m > 2). With similar arguments to those in [1, 2] one can show that the map ε ↦ dim_{H} F_{f_{ε}} is analytic. Furthermore, one can look for an analytic function α = α(ε) such that dim_{H} F_{f_{ε}} = −G(α(ε))/ log m. Setting α(ε) = α_{0} + α_{1}ε + o(ε) we obtain

\begin{matrix}G′(α(ε)) = & 2 log \frac{α_{0}(m − 2)}{1 − 2α_{0}} + (2α_{0} log \frac{α_{0}(m − 2)}{1 − 2α_{0}}) ε \\ + (α_{0} + \frac{2α_{0}^{2}(m − 2)}{1 − 2α_{0}} + α_{1} (\frac{1}{α_{0}} + \frac{4(m − 2)}{1 − 2α_{0}})) ε + o(ε) \end{matrix}

and thus, solving G′(α(ε)) = 0,

α(ε) = \frac{1}{m} − \frac{3ε}{5m^{2}} + o(ε).

Therefore

dim_{H} F_{f_{ε}} = −\frac{G(α(ε))}{log m} = 1 + \frac{(m − 1)ε}{5m^{3} log m} + o(ε).  (42)

Note that the term 1 in (42) could have also been obtained from (37), which corresponds to the case ε = 0.

5.3. Forbidden blocks. We now consider frequencies of digits on sets for which some fixed blocks of digits are forbidden. These can be modeled by topological Markov chains.

Let A = (a_{ij}) with i, j = 0, …, m − 1 be an m × m matrix with each entry either 0 or 1. Using base-m representations, we define

X_{A} = {0.x_{1}x_{2} ⋯ ∈ [0, 1] : a_{x_{n}x_{n+1}} = 1 for all n ∈ ℕ}.

Recall that the nonuniqueness of the representation does not affect the study of the Hausdorff dimension.

Denote by ρ(B) the spectral radius of the matrix B, and by Λ_{a_{0},... ,a_{m−1}} the diagonal matrix with entries a_{0}, …, a_{m−1}. Consider a 1-locally constant function φ: X_{A} → ℝ with φ(0.x_{1}x_{2} ⋯) = a_{x_{1}}. It is well known that

P (φ) = log ρ(Λ_{a_{0},... ,a_{m−1}}A).

Consider an m × m stochastic matrix Π = (π_{ij}), with i, j = 0, …, m − 1, i.e., a matrix with nonnegative entries such that ∑_{j=0}^{m−1} π_{ij} = 1 for every i. Given a probability vector p = (p_{0}, …, p_{m−1}) ∈ L_{m} such that pΠ = p we define a g_{m}-invariant probability measure μ_{Π,p} by

μ_{Π,p}(I_{i_{1}···i_{n}}) = p_{i_{1}} ∏_{k=1}^{n−1} π_{i_{k}i_{k+1}}.

If A satisfies a_{ij} = 0 if and only if π_{ij} = 0, then the support of μ_{Π,p} is X_{A}. We have

h_{μ_{Π,p}}(g_{m}) = − ∑_{i=0}^{m−1} ∑_{j=0}^{m−1} p_{i}π_{ij} log π_{ij}.  (43)

Using similar arguments to those in the proof of Theorem 11 one can establish the following statement.

Theorem 17. Assume that some power of A has only positive entries and let φ_{i}: X_{A} → ℝ be 1-locally constant functions for i = 1, …, d. The following properties hold:

1. if α = (α_{1}, …, α_{d}) ∈ 𝒬(ℳ) then

dim_{H} K_{α} = \frac{1}{log m} max h_{μ_{Π,p}}(g_{m}),

where the maximum is taken over all measures μ_{Π,p} such that

(∑_{k=0}^{m−1} p_{k}φ_{1k}, …, ∑_{k=0}^{m−1} p_{k}φ_{dk}) = α;

2. if α = (α_{1}, …, α_{d}) ∈ int 𝒬(ℳ) then

dim_{H} K_{α} = inf{log_{m} ρ(Λ_{a_{0}(q),... ,a_{m−1}(q)}A) : q ∈ ℝ^{d}},

where

a_{k}(q_{1}, …, q_{d}) = exp ∑_{i=1}^{d} q_{i}(φ_{ik} − α_{i}) for k = 0, …, m − 1.

One can also consider κ-locally constant functions with an arbitrary κ. In this case the most convenient approach consists in reducing the problem to the study of 1-locally constant functions. This can be done by considering a topological Markov chain in an appropriate larger space composed of blocks with a certain fixed length. This idea is used in the following section.

5.4. Frequencies of blocks. We now discuss how to obtain versions of the above results for frequencies of blocks. This is related to the study of κ-locally constant functions for an arbitrary κ. In this case (29) and (15) have to be replaced by less explicit formulas. This makes it often difficult to compute the Hausdorff dimension explicitly.

Consider the interval I_{i_{1}···i_{n}} in (12) for a fixed integer m. Whenever there exists the limit

τ_{[i_{1}···i_{n}]}(x) = lim_{m→∞} \frac{card\{j ∈ \{1, …, m\} : (x_{j+1} ⋯ x_{j+n}) = (i_{1} ⋯ i_{n})\}}{m} (44)

it is called the frequency of the block [i_{1} ⋯ i_{n}] in the base-m representation of x. When we write the symbol τ_{[i_{1}···i_{n}]}(x) we are already assuming the existence of the limit in (44).

We first consider a particular case in which one is able to obtain an explicit value for the Hausdorff dimension. Given a nonnegative m × m matrix P = (p_{ij}) we define the set

F_{m}(P) = {x ∈ [0, 1] : τ_{[ij]}(x) = p_{ij} for every i, j = 0, …, m − 1}.

Write p_{i} = ∑_{j=0}^{m−1} p_{ij}. We shall assume that

∑_{i=0}^{m−1} p_{i} = 1 and p_{j} = ∑_{i=0}^{m−1} p_{ij}  (45)

(otherwise the set F_{m}(P) would be empty). Then the matrix Π = (π_{ij}) with entries π_{ij} = p_{ij}/p_{i} is a stochastic matrix (see Section 5.3).

Theorem 18. If P = (p_{ij}) is a nonnegative matrix satisfying (45) for which some power has only positive entries, then

dim_{H} F_{m}(P) = −\frac{1}{log m} ∑_{i=0}^{m−1} ∑_{j=0}^{m−1} p_{i}π_{ij} log π_{ij}.

Proof. Consider the functions φ_{ij} = χ_{I_{ij}} for i, j = 0, …, m − 1. It follows from Theorems 9 and 10 that

dim_{H} F_{m}(P) = \frac{1}{log m} max_{μ} h_{μ}(g_{m}),

where the maximum is taken over all g_{m}-invariant probability measures μ on [0, 1] such that ∫_{0}^{1} φ_{ij} dμ = μ(I_{ij}) = p_{ij} for every i and j. By the first formula for h_{μ}(g_{m}) in Proposition 3, we have

h_{μ}(g_{m}) ≤ − ∑_{i=0}^{m−1} ∑_{j=0}^{m−1} μ(I_{ij}) log \frac{μ(I_{ij})}{μ(I_{j})} = − ∑_{i=0}^{m−1} ∑_{j=0}^{m−1} p_{i}π_{ij} log \frac{p_{i}π_{ij}}{p_{j}} . (46)

Note that

∑_{i=0}^{m−1} ∑_{j=0}^{m−1} p_{i}π_{ij} log \frac{p_{i}}{p_{j}} = ∑_{i=0}^{m−1} ∑_{j=0}^{m−1} p_{i}π_{ij} log p_{i} − ∑_{i=0}^{m−1} ∑_{j=0}^{m−1} p_{i}π_{ij} log p_{j}

= ∑_{i=0}^{m−1} p_{i} log p_{i} − ∑_{j=0}^{m−1} p_{j} log p_{j} = 0.

It follows from (46) and (43) that h_{μ}(g_{m}) ≤ h_{μ_{Π,p}}(g_{m}). This implies that the Hausdorff dimension of F_{m}(P) is given by h_{μ_{Π,p}}(g_{m})/ log m.

The identity in Theorem 18 is obtained by Billingsley in [5] in the special case when all entries of the matrix P are positive. On the other hand, using the techniques that we develop in this paper one can consider much more involved problems. In particular we can study sets of points for which not all frequencies of blocks are known. Furthermore, we can consider sets defined in terms of frequencies of blocks of different length. We emphasize that the technique developed by Billingsley cannot be applied to these situations without further changes. This is due to the fact that it is not known, at least a priori, whether the dimension of each of these sets is carried by a single subset for which all frequencies are known. It turns out, as a consequence of the theory that we develop in [2], that this special subset always exists, but to show that this happens amounts to compute the Hausdorff dimension of the initial set and thus it is a problem of similar difficulty.

For example, consider the set of points

F_{α} = {x ∈ [0, 1]: τ_{[00]}(x) = α}.

In a similar way to that in Section 5.1 in the case of 1-locally constant functions one can show that the entropy of g_{m}-invariant probability measures satisfying p_{00} = μ(I_{00}) = α is maximized by the measure μ_{Π,p} obtained from the matrix P with entries p_{ij} = (1 − α)/(m^{2} − 1) for each (ij) ≠ (00). This occurs precisely when the ratio 1 − p_{00} is equally distributed over the remaining entries. In this case we have p_{0} = (mα + 1)/(m + 1) and p_{i} = m(1 − α)/(m^{2} − 1) for each i ≠ 0. Applying Theorems 9 and 10, a straightforward computation allows one to conclude that

dim_{H} F_{α} = −\frac{1}{log m} ∑_{i=0}^{m−1} ∑_{j=0}^{m−1} p_{i}π_{ij} log π_{ij}

= −\frac{1}{log m} (p_{00} log π_{00} + ∑_{j=1}^{m−1} p_{0j} log π_{0j} + ∑_{i=1}^{m−1} ∑_{j=0}^{m−1} p_{ij} log π_{ij})

= α log_{m} \frac{m + 1}{mα + 1} + \frac{1 − α}{m + 1} log_{m} \frac{(m − 1)(mα + 1)}{1 − α} + \frac{m(1 − α)}{m + 1}.

Note that dim_{H} F_{α} → 1 − α when m → ∞. Therefore, the Hausdorff dimension of the set of numbers having 99.99% of pairs of zeros in their base-m representation is uniformly bounded away from zero as m → ∞.

We also want to consider sets defined in terms of frequencies of blocks of different length. Instead of presenting the general theory, which would hide the principles behind our approach, we choose to consider a specific example. Consider the set

F = {x ∈ [0, 1]: τ_{[000]}(x) = τ_{[11]}(x)},

with respect to the base-2 representation of x. To compute the Hausdorff dimension of F it is convenient to transform the related 3-locally constant functions into 1-locally constant functions on a new space and then apply the results of the former sections. We consider an extended representation of each number (sometimes called higher block representation). When x = 0.x_{1}x_{2} ⋯ is a base-2 representation, we substitute the digit x_{k} by the block b_{k} = [x_{k}x_{k+1}x_{k+2}]. In this way each number is now represented by an infinite sequence x = 0.b_{1}b_{2} ⋯ on 8 symbols. The original representation can be recovered from this one by simply looking at the first symbol of each block b_{k}.

There is however a strong contrast between the original representation and the new one: not all sequences of blocks of 3 symbols are allowed in the new representation. For example, the symbol [011] cannot follow [000]. This relation is encoded in the transition matrix:

A = (a_{ij}) = (\begin{matrix}1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix}) ,

where a_{ij} = 1 if and only if the jth block in the lexicographic order can follow the ith one, i.e.,

a_{[x_{1}x_{2}x_{3}][y_{1}y_{2}y_{3}]} = 1 if and only if x_{2} = y_{1} and x_{3} = y_{2}.

Any function that is 3-locally constant with respect to the original representation becomes 1-locally constant in the new representation. By Theorem 17, log 2 · dim_{H} F is equal to the infimum over q ∈ ℝ of

P (q(χ_{[000]} − χ_{[11]})) = log ρ ((\begin{matrix}e^{q} & e^{q} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & e^{−q} & e^{−q} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & e^{−q} & e^{−q} \end{matrix})) .

The characteristic polynomial of the matrix is x^{5}(x^{3} −(e^{q} +e^{−q})x^{2} +(e^{q} −1)) and one can deduce that

dim_{H} F = \frac{1}{log 2} log inf_{y>0} (\frac{1 + y^{2}}{3y} + \frac{(1 + y^{2})^{2}}{3y\sqrt[3]{p(y)/2}} + \frac{\sqrt[3]{p(y)/2}}{3y}) ,

where

\begin{matrix}p(y) = & 2y^{6} − 21y^{4} + 27y^{3} + 6y^{2} + 2 \\ + \sqrt{−27y^{3}(4y^{7} − 4y^{6} − 15y^{5} + 42y^{4} − 15y^{3} − 12y^{2} + 4y − 4)}. \end{matrix}

After the acceptance of this paper we noticed that the numerical value announced for dim_{H} F in [2] was unfortunately obtained implementing incorrectly the formulas in the computer (and thus it should be revised).

A similar approach allows us to consider any other set defined in terms of linear relations between frequencies of blocks with an arbitrary length.

References

1. L. Barreira and B. Saussol, Variational principles and mixed multifractal spectra, Trans. Amer. Math. Soc. 353 (2001), 3919–3944.

2. L. Barreira, B. Saussol and J. Schmeling, Higher-dimensional multifractal analysis, J. Math. Pures Appl. 81 (2002), 67–91.

3. L. Barreira and J. Schmeling, Sets of “non-typical” points have full topological entropy and full Hausdorff dimension, Israel J. Math. 116 (2000), 29–70.

4. A. Besicovitch, On the sum of digits of real numbers represented in the dyadic system, Math. Ann. 110 (1934), 321–330.

5. P. Billingsley, Ergodic theory and information, Wiley and Sons, 1965.

6. E. Borel, Sur les probabilités dénombrables et leurs applications arithmétiques, Rend. Circ. Mat. Palermo 26 (1909), 247–271.

7. R. Bowen, Topological entropy for noncompact sets, Trans. Amer. Math. Soc. 184 (1973), 125–136.

8. H. Eggleston, The fractional dimension of a set defined by decimal properties, Quart. J. Math. Oxford Ser. 20 (1949), 31–36.

9. A. Fan, D. Feng and J. Wu, Recurrence, dimension and entropy, J. London Math. Soc. 64 (2001), 229–244.

10. G. Hardy and J. Littlewood, Some problems on Diophantine approximations, Acta Math. 37 (1914), 155–190.

11. W. Parry, Topics in ergodic theory, Cambridge Tracts in Mathematics 75, Cambridge University Press, 1981.

12. Ya. Pesin, Dimension theory in dynamical systems: contemporary views and applications, Chicago Lectures in Mathematics, Chicago University Press, 1997.

13. F. Takens and E. Verbitskiy, On the variational principle for the topological entropy of certain non-compact sets, preprint.

14. P. Walters, An introduction to ergodic theory, Graduate Texts in Mathematics 79, Springer, 1981.

Departamento de Matemática, Instituto Superior Técnico, 1049-001 Lisboa, Portugal

E-mail address: luis.barreira@math.ist.utl.pt
URL: http://www.math.ist.utl.pt/~barreira/

LAMFA/CNRS FRE 2270, Université de Picardie Jules Verne, 33 rue Saint Leu, 80039 Amiens, France

E-mail address: benoit.saussol@mathinfo.u-picardie.fr
URL: http://www.mathinfo.u-picardie.fr/saussol/

Centre for Mathematical Sciences, LTH, Lund University, Box 118, SE-221 00 Lund, Sweden

E-mail address: joerg@maths.lth.se