RECURRENCE, DIMENSIONS AND LYAPUNOV EXPONENTS

B. SAUSSOL, S. TROUBETZKOY, AND S. VAIENTI

Abstract. We show that the Poincaré return time of a typical cylinder is at least its length. For one dimensional maps we express the Lyapunov exponent and dimension via return times.

1. Introduction

The statistical description of dynamical system has recently been enriched by the study of recurrence and return times. For example the Poisson distribution for the return and entrance time into a given set has been investigated (see [11] and references therein), and the dimension like characterstics of invariant sets have been investigated by means of recurrence [1],[16]. In these two contexts a local quantity plays a fundamental role: the first return of a set into itself, sometimes also called the Poincaré recurrence of the set. If A ⊂ X is a measurable set of a measurable (probability) dynamical systems {X, β, μ, T }, the first return of the set A is simply defined as:

τ(A) = min{n > 0 : T^{n}A ∩ A ≠ ∅}.

We will suppose in the following that A is either the cylinder of order n around the point x ∈ X with respect to a measurable partition U, i.e. A = U_{n}^{x} ∈ ⋁_{i=0}^{n−1} T^{−i}U, x ∈ U_{n}^{x}, or A is a ball of radius r around x, A = B_{r}(x). It has been shown in [11] that the limits:

\underline{lim}_{n→∞} \frac{τ(U_{n}^{x})}{n}  and  \overline{lim}_{n→∞} \frac{τ(U_{n}^{x})}{n}  (1)

define μ–almost everywhere invariant (subadditive) functions that control the asymptotic short returns into the sets U_{n}^{x}. It is therefore important to have information on the value(s) of (1). The first result of this article is to show that for a measurable dynamical system with positive metric entropy, the \underline{lim} in (1) is μ–a.e. bigger or equal to 1. This estimate is a key bound need in proving the exponential and Poisson statistics for return times, as pointed out in [11] and [7].

2000 Mathematics Subject Classification. Primary: 37B20.

Key words and phrases. return time.

For systems with zero metric entropy, examples are known where \underline{lim} is positive and strictly smaller than one, for instance in the case of Fibonacci rotations [6] and where the \underline{lim} is identically equal to zero [2]. Our proof of the lower bound (Theorem 1) is surprisingly easy. It uses the concept of Kolmogorov complexity, which we recall briefly in the Appendix.

Besides the interest in the asymptotic distribution of return and entrance times, the limits in (1) can be exploited in another direction, which, in [14], we proposed to call the “thermodynamics of return times”. We prove (Theorem 2) that for a large class of ergodic onedimensional maps, the Lyapunov exponent can be estimated from the behavior of the first return times of a ball as the radius vanishes.

We turn to computing the Hausdorff dimension of the measure for the same class of one-dimensional maps. The first return of a set will be now replaced by another quantity which will denote with τ_{r}(x) and that is the first return of the point x into its neighborhood B_{r}(x).

lim_{r→0^{+}} \frac{log τ_{r}(x)}{− log r}  (2)

In our final result (Theorem 3) we show that the limit in (2) exists μ-a.e. and is equal to the local dimension:

d_{μ}(x) := lim_{r→0^{+}} \frac{log μ(B_{r}(x))}{log r}  (3)

For the class of one-dimensional maps considered is known that the local dimension is almost everywhere constant and equal to the Hausdorff dimension of the measure and is also equal to the ratio between the metric entropy and the μ–Lyapunov exponent [8]. A similar result in a multidimensional setting has been proved by Barreira and Saussol [3, 4], namely for the basic sets of Axiom-A diffeomorphisms. Our proof is relatively simple and uses sharp comparison between balls and cylinders provided by Hofbauer [8]; nevertheless it is quite general since it covers maps with critical and parabolic points.

In conclusion these results are one of the first steps in establishing what we have already called thermodynamics of return times. In this context a major role is played by the first returns of sets and points which often play the role of the measure of balls and cylinders according to the old suggestion given by Kac’s theorem. This approach could be even more advantageous in numerical and experimental investigations of dynamical systems as we showed in [14]; further theoretical developments in this direction appeared quite recently in [7] and [2].

We will systematically use the same letter and underscore (overscore) the names of pairs of functions defined via a \underline{lim} (\overline{lim}). Because of this convention we will only write the one of the definitions of such pairs of functions.

2. No small returns

In this section we provide sharp lower bounds for the first return time, for cylinders of measurable partitions. These estimates are essential to compute the speed of convergence to the exponential law of the first return time. To prove this theorem we will use White’s sharpening [18, 19] of a remarkable theorem by Brudno [5] which links Kolmogorov complexity to entropy. We state this theorem and give a quick introduction to Kolmogorov complexity in the appendix.

Theorem 1. Let (T, X, μ) be an ergodic measure preserving dynamical system. If ζ is a finite or countable measurable partition with entropy h_{μ}(T |ζ) strictly positive and ζ_{n}^{x} is the cylinder of length n containing x, then the lower rate of return for cylinders is almost surely bigger or equal to 1, i.e.

\underline{R}_{ζ}(x) := \underline{lim}_{n→∞} \frac{1}{n}τ(ζ_{n}^{x}) ≥ 1

for μ-a.e. x ∈ X.

Remark: It is an easy exercise to show that if additionally (T, X) satisfies the specification property [12] then

\overline{R}_{ζ}(x) ≤ 1

for μ-a.e. x ∈ X and thus

R_{ζ}(x) := lim_{n→∞} \frac{1}{n}τ(ζ_{n}^{x}) = 1

for μ-a.e. x ∈ X. Afraimovich et. al. have shown that there are specific examples of zero entropy maps for which the conclusion of Theorem 1 is not true [2].

Proof. It is sufficient to prove the theorem for finite partitions, the case of countable ζ will follow easily. More precisely, if ζ = {B_{1}, B_{2}, … } is a countable partition, then for some m < ∞ the partition ζ̂ = {B_{1}, B_{2}, …, B_{m}, ∪_{l>m}B_{l}} will have positive entropy. In addition, ζ is finer than ζ̂, hence τ(ζ_{n}^{x}) ≥ τ(ζ̂_{n}^{x}).

Thus we assume that ζ is finite. We claim that a cylinder ζ_{n}^{x} is completely determined by its first τ := τ(ζ_{n}^{x}) symbols. To see this suppose that ζ_{n}^{x} = [x_{0}, …, x_{n−1}] and that y ∈ ζ_{n}^{x} satisfies T^{τ}y ∈ ζ_{n}^{x}. Let j be the integer defined by jτ < n ≤ (j + 1)τ. Since T^{τ}y ∈ ζ_{n}^{x} we have x_{iτ}, …, x_{(i+1)τ−1} = x_{0}, …, x_{τ−1} for i = 0, 1, …, j, proving the claim.

We will use the notion of Kolmogorov complexity to prove the theorem. All the notations used here are defined in the appendix, more details can be found in the references [5, 18]. Let N = #ζ and let K(w) be the Kolmogorov complexity of a finite word w with entries from the alphabet {0, 1, …, N − 1}. The partition ζ gives rise to the symbolic space Σ_{ζ} and a map φ : X → Σ_{ζ} which is a semiconjugacy σφ = φT. Let ζ_{n}^{x} be the word consisting of the first n–symbols of the sequence φ(x). We use the notation K_{ζ}(ζ_{n}^{x}) for the complexity of ζ_{n}^{x} and define K_{ζ}(x, T) = \underline{lim}_{n→0} \frac{1}{n}K(ζ_{n}^{x}).

Since ζ_{n}^{x} is determined by its first τ symbols the complexity of the sequence ζ_{n}^{x} is bounded by the complexity of defining the first τ symbols plus the complexity of repeating these symbols up to the size n of the cylinder. In other words

K_{ζ}(ζ_{n}^{x}) ≤ K_{ζ}(ζ_{τ(ζ_{n}^{x})}^{x}) + log n.

From which follows

\underline{K}_{ζ}(x, T) ≤ \underline{lim}_{n→∞}[K_{ζ}(ζ_{τ(ζ_{n}^{x})}^{x}) + log n]/n
= \underline{lim}_{n→∞} \frac{K_{ζ}(ζ_{τ(ζ_{n}^{x})}^{x})}{τ(ζ_{n}^{x})} × \frac{τ(ζ_{n}^{x})}{n}
≤ \overline{K}_{ζ}(x, T)\underline{R}_{ζ}(x).

White’s improvement of Brudno’s theorem [18, 5] gives for μ-a.e. x ∈ X

\underline{K}_{ζ}(x, T) = \overline{K}_{ζ}(x, T) = h_{μ}(T |ζ) > 0,

hence \underline{R}_{ζ}(x) ≥ 1. After we discovered this proof of Theorem 1 Saussol gave an alternate proof using the Shannon McMillan Breiman theorem instead of Brudno’s result [2].

3. Dimension and Lyapunov exponent via return times

3.1. Preliminaries. We can apply the results of the previous section to a very general case of one-dimensional piecewise monotonic maps. For a function f : [0, 1] → ℝ and p > 0 we define the p–variation of f by

var_{p}(f) := sup {∑_{i=1}^{N−1} |f(x_{i+1}) − f(x_{i})|^{p}} ,

where the supremum is taken along all finite ordered sequences of points 0 ≤ x_{1} < x_{2} < ⋯ < x_{N} ≤ 1 and integers N.

Throughout this section T: [0, 1] → [0, 1] is a piecewise monotonic transformation which preserves the ergodic invariant measure μ, and Z denotes the finite μ-partition (i.e. partition modulo μ) of the interval into monotonic pieces. We say that a measurable function T′ : [0, 1] → ℝ is a derivative of T if

∫_{a}^{b}T′(x) dx = T (b) − T (a)

for any interval [a, b] contained in some element of Z. We then denote the Lyapunov exponent of an invariant measure μ by

λ_{μ} = ∫ log |T′|dμ.

Let φ = log |T′| and set S_{n}φ = ∑_{i=0}^{n−1} φ ∘ T^{i}. Given a μ-partition Y we denote by Y_{n} = ∨_{i=0}^{n−1}T^{−i}Y its refinement and we denote by Y_{n}^{x} the unique element of Y_{n} containing x. Notice that such an element exists and is unique for μ-a.e. x.

3.2. Balls and cylinder sets. In this section we slightly adapt the results by Hofbauer and Raith [10] (see also [8]) in order to get a good comparison between balls and cylinders. We denote by |J| the length of an interval J ⊂ [0, 1].

Proposition 3.1 ([10]). Let T be a piecewise monotonic transformation with a derivative of bounded p-variation for some p > 0. Let μ be an ergodic T -invariant measure with Lyapunov exponent λ_{μ} > 0. Then for any ε > 0 we have

a) there exists a finite or countable μ-partition Y with finite entropy into intervals which refines Z;

b) the partition Y is a generator, in particular h_{μ}(T, Y) = h_{μ}(T); c) for any n and x we have

|S_{n}φ(x) − log \frac{1}{|Y_{n}^{x}|} ∫_{Y_{n}^{x}} exp(S_{n}φ(y))dy| ≤ nε;

d) for μ-almost every x we have

lim_{n→∞} \frac{1}{n} log d(T^{n}x, ∂T^{n}Y_{n}^{x}) = 0.

We can use this proposition and the technique described in [8, 10] to prove the following

Lemma 1. Let Y be the partition given by Proposition 3.1. For μ-a.e. x the set of accumulation points of the sequence −\frac{1}{n} log |Y_{n}^{x}| lies in the interval [λ_{μ} − ε, λ_{μ} + ε].

Proof. We have |T^{n}Y_{n}^{x}| = ∫_{Y_{n}^{x}} exp(S_{n}φ(y))dy, hence Proposition 3.1.c gives

|S_{n}φ(x) − log |T^{n}Y_{n}^{x}| + log |Y_{n}^{x}|| ≤ nε.  (4)

Since d(T^{n}x, ∂T^{n}Y_{n}^{x}) ≤ |T^{n}Y_{n}^{x}| ≤ 1 Proposition 3.1.d also implies that lim_{n→∞} \frac{1}{n} log |T^{n}Y_{n}^{x}| = 0 for μ-a.e. x. Furthermore the Birkhoff ergodic theorem gives that lim_{n} \frac{1}{n}S_{n}φ = λ_{μ} for μ-a.e. x, thus using (4) we get the result.

Lemma 2. Let Y be the partition given by Proposition 3.1. For μ-a.e. x the set of accumulation points of the sequence −\frac{1}{n} log d(x, ∂Y_{n}^{x}) lies in the interval [λ_{μ} − 2ε, λ_{μ} + 2ε].

Proof. By the mean value theorem we have

d(x, ∂Y_{n}^{x}) inf_{Y_{n}^{x}} |(T^{n})′| ≤ d(T^{n}x, ∂T^{n}Y_{n}^{x}) ≤ d(x, ∂Y_{n}^{x}) sup_{Y_{n}^{x}} |(T^{n})′|.

Since the logarithm is increasing this implies

inf_{Y_{n}^{x}} log |(T^{n})′| ≤ log \frac{d(T^{n}x, ∂T^{n}Y_{n}^{x})}{d(x, ∂Y_{n}^{x})} ≤ sup_{Y_{n}^{x}} log |(T^{n})′|

Using (4) this yields

\begin{aligned}|log \frac{d(x, ∂Y_{n}^{x})}{d(T^{n}x, ∂T^{n}Y_{n}^{x})} + S_{n}φ(x)| & ≤ 2 sup_{y∈Y_{n}^{x}} |φ(y) − φ(x)| \\ & ≤ 2nε, \end{aligned}  (5)

by Proposition 3.1.c. In addition, by the Birkhoff ergodic theorem we have lim_{n→∞} \frac{1}{n}S_{n}φ(x) = λ_{μ} for μ a.e. x. The conclusion follows then from Proposition 3.1.d and inequality 5.

3.3. A lower bound for the Lyapunov exponent. We are now ready to state and prove the following result.

Theorem 2. Let T be a piecewise monotonic transformation with a derivative of bounded p-variation for some p > 0. If μ is an ergodic T -invariant measure with non-zero entropy, then

λ_{μ} ≥ (\underline{lim}_{r→0} \frac{τ(B_{r}(x))}{− log r})^{−1}  (6)

for μ-almost every x.

Remark: 1) Notice that each C^{1+ε} piecewise monotonic map with finitely many pieces has a derivative of bounded p-variation, for p ≥ 1/ε, hence C^{1+ε} multimodal maps with non-zero entropy satisfies hypotheses of Theorem 2.

Proof. By Ruelle’s inequality, the assumption that the entropy is positive implies that the Lyapunov exponent is positive as well [9]. Let ε > 0 and Y be the partition given by Proposition 3.1.

Let x ∈ [0, 1] be fixed. We set d_{n} = d(x, ∂Y_{n}^{x}) and D_{n} = |Y_{n}^{x}|. Observe that since Y is generating we have lim_{n} D_{n} = 0, hence d_{n} converges monotonically to zero. Thus given r > 0 we can define n(r) to be the smallest integer n such that d_{n+1} < r ≤ d_{n}. Note that we have B_{r}(x) ⊂ Y_{n(r)}^{x}, which implies that τ(B_{r}(x)) ≥ τ(Y_{n(r)}^{x}). Since r ≥ d_{n(r)+1} and n(r) → ∞ as r → 0 we get

\underline{lim}_{r→0} \frac{τ(B_{r}(x))}{− log r} ≥ \underline{lim}_{r→0} (\frac{τ(Y_{n(r)}^{x})}{n(r)} × \frac{1}{−\frac{1}{n(r)} log d_{n(r)+1}} )

≥ ( \underline{lim}_{n→∞} \frac{τ(Y_{n}^{x})}{n}) × ( \overline{lim}_{n→∞} −\frac{1}{n} log d_{n})^{−1} .

Since h_{μ}(T, Y) = h_{μ}(T) > 0 by Proposition 3.1.b we can apply Theorem 1, hence there exists a set X_{ε}^{1} of full μ-measure such that \underline{lim}_{n→∞} \frac{τ(Y_{n}^{x})}{n} ≥ 1 for any x ∈ X_{ε}^{1}. By Lemma 2 there exists a set of full μ-measure X_{ε}^{2} such that \overline{lim}_{n→∞} −\frac{1}{n} log d_{n} ≤ λ_{μ} + 2ε for any x ∈ X_{ε}^{2}. Thus for any x ∈ X_{ε}^{1} ∩ X_{ε}^{2} we get

\underline{lim}_{r→0} \frac{τ(B_{r}(x))}{− log r} ≥ \frac{1}{λ_{μ} + 2ε}.

We conclude that the inequality (6) holds on the set of full measure ∩_{i≥1}(X_{1/i}^{1} ∩ X_{1/i}^{2}). This proves the theorem.

In the case of Markov expanding maps we get a stronger result

Corollary 1. Under the hypotheses of Theorem 2, if in addition T is piecewise expanding Markov then

lim_{r→0} \frac{τ(B_{r}(x))}{− log r} = \frac{1}{λ_{μ}} .

Proof. Without loss of generality we assume that T is topologically mixing. We only sketch the proof. If Z is a Markov partition for T then it is easy to see that for any ε > 0 the partition Y = Z_{p} = ∨_{i=0}^{p−1}Z will have all the properties mentioned in Proposition 3.1, provided p is chosen sufficiently large. Furthermore, Z_{p} is still a Markov partition, hence it has the specification property. Taking into account Remark 2, and proceeding as in the second part of the proof of Theorem 3 yields to the conclusion.

3.4. Dimension via return time. Give a map T : X → X on the metric space (X, d) we define the first return of a point x ∈ X into its r-ball B_{r}(x) by

τ_{r}(x) := min {k > 0 : T^{k}x ∈ B_{r}(x)} = min {k > 0 : d(T^{k}x, x) < r}

Given a measurable μ-partition Y we denote by

R_{n}(x, Y) = inf{k > 0 : T^{k}x ∈ Y_{n}^{x}}

the repetition time of the first n symbols of x. Ornstein and Weiss have proven [15] that, whenever Y is a finite measurable μ-partition we have

lim_{n→∞} \frac{log R_{n}(x, Y)}{n} = h_{μ}(T, Y),  (7)

for μ-almost every x. See also [13, 17] for the generalization to the case of a countable partition Y. This result will be essential to prove the following.

Theorem 3. Let T be a piecewise monotonic transformation with a derivative of bounded p-variation for some p > 0. If μ is an ergodic T -invariant measure with non-zero entropy, then

d_{μ}(x) = lim_{r→0} \frac{log τ_{r}(x)}{− log r}  (8)

for μ-almost every x.

Proof. By Ruelle’s inequality, the assumption that the entropy is positive implies that the Lyapunov exponent is positive as well [9]. Let ε ∈ (0, λ_{μ}) and Y be the partition given by Proposition 3.1.

We proceed as in the proof of Theorem 2, and keep the same notations. Observe that for any x and r > 0 we have B_{r}(x) ⊂ Y_{n(r)}^{x}, from which follows τ_{r}(x) ≥ R_{n(r)}(x, Y). Thus

\underline{lim}_{r→0} \frac{log τ_{r}(x)}{− log r} ≥ \underline{lim}_{r→0} (\frac{log R_{n(r)}(x, Y)}{n(r)} × \frac{1}{−\frac{1}{n(r)} log d_{n(r)+1}} )

≥ ( \underline{lim}_{n→∞} \frac{log R_{n}(x, Y)}{n}) × ( \overline{lim}_{n→∞} −\frac{1}{n} log d_{n})^{−1} .

Since h_{μ}(T, Y) = h_{μ} > 0 by Proposition 3.1.b we can apply the countable alphabet version of Ornstein and Weiss return times theorem [15, 13, 17], hence there exists a set X_{ε}^{1} of full μ-measure such that (7) holds for any x ∈ X_{ε}^{1}. By Lemma 2 there exists a set of full μmeasure X_{ε}^{2} such that \overline{lim}_{n→∞} −\frac{1}{n} log d_{n} ≤ λ_{μ} + 2ε for any x ∈ X_{ε}^{2}. Thus for any x ∈ X_{ε_{i}}^{1} ∩ X_{ε_{i}}^{2} we get

\underline{lim}_{r→0} \frac{log τ_{r}(x)}{− log r} ≥ \frac{h_{μ}}{λ_{μ} + 2ε}.  (9)

Next we want to find an upper bound for the \overline{lim} of the same quantity. If m(r) denotes the smallest integer m such that D_{m} < r ≤ D_{m−1}, then we have B_{r}(x) ⊃ Y_{m(r)}^{x}. Thus

\overline{lim}_{r→0} \frac{log τ_{r}(x)}{− log r} ≤ \overline{lim}_{r→0} (\frac{log R_{m(r)}(x, Y)}{m(r)} × \frac{1}{−\frac{1}{m(r)} log D_{m(r)−1}} )

≤ ( \overline{lim}_{m→∞} \frac{log R_{m}(x, Y)}{m}) × ( \underline{lim}_{m→∞} −\frac{1}{m} log D_{m})^{−1} .

By Lemma 1 there exists a set of full μ-measure X_{ε}^{3} such that for any x ∈ X_{ε}^{3} we have \underline{lim}_{m→∞} −\frac{1}{m} log D_{m} ≥ λ_{μ} − ε. This together with (7) implies that for any x ∈ X_{ε}^{1} ∩ X_{ε}^{3} we have

\overline{lim}_{r→0} \frac{log τ_{r}(x)}{− log r} ≤ \frac{h_{μ}}{λ_{μ} − ε}.  (10)

In addition, Hofbauer [8] has shown in this setting that

d_{μ}(x) = \frac{h_{μ}}{λ_{μ}} ,

hence we conclude by (9) and (10) that the equality (8) holds on the set of full measure ∩_{i≥1}(X_{1/i}^{1} ∩ X_{1/i}^{2} ∩ X_{1/i}^{3}). This finishes the proof.

4. Appendix: Kolmogorov complexity and Brudno’s theorem

The idea of Kolmogorov complexity is that a finite 0–1 word is only as complicated as the algorithm that produces it.^{1} To run an algorithm we need to fix a computer (with infinite storage capacity). The Kolmogorov complexity K_{M}(x) of a word x with respect to a fixed computer M is the length of the shortest algorithm which outputs x given the length of x as an input. Kolmogorov proved that there exist universal computers U such that

K_{U}(x) ≤ K_{M}(x) + C  (11)

where C is a constant depending only on U and M. Here the word universal is used to indicate that U can simulate any other computer M.

More formally, a computer M is a Turing machine while an algorithm which produces a finite 0–1 string s is a 0–1 string p such that M(p) = s. If there is no p with M(p) = s we say that the length l(p) of the algorithm is not defined while if there is more than one such p we choose the first in the lexicographical order.

If p is a finite word of length n then we denote by p̂ the string

p(0)p(0)p(1)p(1) ⋯ p(n − 1)p(n − 1)01.

If we input the concatenated word p̂q into a suitably programmed Turing machine it will recognize two distinct inputs: p and q. Also, if n ∈ N let [n] be the n binary string in the lexicographical order given by

0, 1, 00, 01, 10, 11, 000, …

i.e. [3] = 00. Notice that l([n]) ≤ log_{2} n.

There are countably many Turing machines, which may be computable enumerated as A_{1}, A_{2}, . . .. We say that a Turing machine is universal if, for any m and any finite word p : U( ˆ[m]p) = A_{m}(p). Thus a universal Turing machine simulates any given machine on any given input.

1The generalization to arbitrary finite alphabets is straightforward.

For x an infinite 0–1 sequence one defines the average complexity by looking at the first n–bits x(n) and defining

\overline{K}(x) := \overline{lim}_{n→∞} \frac{K_{U}(x(n))}{n}.

Note that by equation (11) the average complexity does not depend which universal computer U is chosen. The function \underline{K}(x) is defined in an analogous way with the \overline{lim} replaced by a \underline{lim}.

Brudno’s theorem shows the linkage between complexity and entropy. Suppose that μ is an ergodic invariant measure for the map f and ζ is a finite measurable partition. The partition ζ gives rise to the symbolic space Σ_{ζ} and a map φ : X → Σ_{ζ} which is a semiconjugacy σφ = φT. Let ζ_{n}^{x} be the word consisting of the first n–symbols of the sequence φ(x) and define \underline{\overline{K}}_{ζ}(x, T) = \underline{\overline{K}}((ζ_{n}^{x})_{n}). Brudno has shown:

Theorem 4. (Brudno [5]) \overline{K}_{ζ}(x) = h_{μ}(f|ζ) for μ–almost every point x

White has improved this theorem, he has shown:

Theorem 5. (White [18, 19]) \underline{K}_{ζ}(x) = \overline{K}_{ζ}(x) = h_{μ}(f|ζ) for μ– a.e. x.

References

[1] Afraimovich, V. Pesin’s dimension for Poincaré recurrence, Chaos 7 (1997) 12–20.

[2] Afraimovich, V., Chazottes, J.-R., and Saussol, B. Pointwise dimensions for Poincaré recurrence associated with maps and special flows, preprint 2000.

[3] Barreira,L. and Saussol, B. Hausdorff dimension of measures via Poincaré recurrence, Comm. Math. Phys. 219 (2001) 443-464.

[4] Barreira,L. and Saussol, B. Product structure of Poincaré recurrence, to appear in ETDS.

[5] Brudno, A. Entropy and the complexity of the trajectories of a dynamical system, Russ. Math. Surv. 2 (1983) 127–51 (Engl. Trans.).

[6] Cassaigne, J., Hubert, P. and Vaienti, S. in preparation.

[7] Haydn, N. and Vaienti, S. The limiting distributions and error terms for return times of dynamical systems, preprint (2001).

[8] Hofbauer, F. Local dimension for piecewise monotonic maps on the interval, Erg. Th. Dyn. Sys. 15 (1995) 1119–1142.

[9] Hofbauer, F. An inequality for the Ljapunov exponent of an ergodic invariant measure for a piecewise monotonic map on the interval, in: Lyapunov exponents, Proceedings, Oberwolfach, 1990 (Eds.: L. Arnold, H. Crauel, J.-P. Eckmann), Lecture Notes in Mathematics 1486, Springer, Berlin, 1991, pp. 227-231.

[10] Hofbauer, F. and Raith, P. The Hausdorff dimension of an ergodic invariant measure for a piecewise monotonic map of the interval, Canad. Math. Bull. 35 (1992) 84–98.

[11] Hirata, M., Saussol, B. and Vaienti, S. Statistics of return times: a general framework and new applications, Comm. Math. Phys. 206 (1999) 33–55.

[12] Katok, T. and Hasselblatt, B. Introduction to the modern theory of dynamical systems, Cambridge Univ. Press (1995).

[13] Kontoyiannis, I., Algoet, P., Suhov, Yu. and Wyner, A. Nonparametric entropy esitmation for stationary processes and random fileds, with applications to English text, IEEE Tras. Inf. Th. 44 (1998) 1319–1327. 1988

[14] Haydn, N., Luevano, J., Mantica, G. and Vaienti, S. Multifracatal properties of return time statistics, submitted to Phys Rev Letters, 2001

[15] Ornstein, D. and Weiss, B. Entropy and data compression, IEEE Trans. Inf. Th. 39 (1993) 78–83.

[16] Penné, V., Saussol, B. and Vaienti, S. Dimensions for recurrence times: topological and dynamical properties, Disc. Cont. Dyn. Sys. 4 (1998) 783–798.

[17] Quas, A. An entropy esitmator for a class of infinite alphabet processes, Theor. Veroyatnost. i Primenen. 43 (1998) 61—621.

[18] White, H. Algorithmic complexity of points in a dynamical system, Erg. Th. Dyn. Sys. 13 (1993) 807–30.

[19] White, H. On the algorithmic complexity of trajectories of points in dynamical systems, Ph.D. dissertation Univ. of North Carolina at Chapel Hill 1991.

LAMFA / CNRS fre 2270, Université de Picardie Jules Verne, 33, rue St Leu, F-80039 Amiens cedex 1, France

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

Centre de physique théorique, Institut de mathématiques de Luminy et Federation de Recherches des Unites de Mathematique de Marseille, CNRS Luminy, Case 907, F-13288 Marseille Cedex 9, France.

E-mail address: serge@cpt.univ-mrs.fr
E-mail address: troubetz@iml.univ-mrs.fr
URL: http://iml.univ-mrs.fr/~troubetz/

Phymat, Université de Toulon et du Var, Centre de physique théorique et Federation de Recherches des Unites de Mathematique de Marseille, CNRS Luminy, Case 907, F-13288 Marseille Cedex 9, France

E-mail address: vaienti@cpt.univ-mrs.fr
URL: http://www.cpt.univ-mrs.fr/