{'fraction_non_alphanumeric': 0.052065794586193495, 'fraction_numerical': 0.014829685273928247, 'mean_word_length': 3.612604540023895, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recurrence, dimensions and Lyapunov exponents

We show that the Poincar\'e 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.


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 x n ∈ n−1 i=0 T −i U, x ∈ U x n , or A is a ball of radius r around x, A = B r (x). It has been shown in [11] that the limits: define µ-almost everywhere invariant (subadditive) functions that control the asymptotic short returns into the sets U x n . 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 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].
For systems with zero metric entropy, examples are known where lim is positive and strictly smaller than one, for instance in the case of Fibonacci rotations [6] and where the 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).
In our final result (Theorem 3) we show that the limit in (2) exists µ-a.e. and is equal to the local dimension: 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 lim (lim). Because of this convention we will only write the one of the definitions of such pairs of functions.

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 ζ x n 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.
Remark: It is an easy exercise to show that if additionally (T, X) satisfies the specification property [12] then for µ-a.e. x ∈ X and thus 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 τ (ζ x n ) ≥ τ (ζ x n ). Thus we assume that ζ is finite. We claim that a cylinder ζ x n is completely determined by its first τ := τ (ζ x n ) symbols. To see this suppose that ζ x n = [x 0 , . . . , x n−1 ] and that y ∈ ζ x n satisfies T τ y ∈ ζ x n . Let j be the integer defined by jτ < n ≤ (j + 1)τ. Since T τ y ∈ ζ x n we have 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 ζ x n be the word consisting of the first n-symbols of the sequence ϕ(x). We use the notation K ζ (ζ x n ) for the complexity of ζ x n and define Since ζ x n is determined by its first τ symbols the complexity of the sequence ζ x n 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 White's improvement of Brudno's theorem [18,5] gives for µ-a.e. x ∈ X 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] → R and p > 0 we define the p-variation of f by 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 ′ : 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 ϕ = n−1 i=0 ϕ • T i . Given a µ-partition Y we denote by Y n = ∨ n−1 i=0 T −i Y its refinement and we denote by Y x n 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]. 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 − 1 n log |Y x n | lies in the interval [λ µ − ε, λ µ + ε].
Proof. We have |T n Y x n | = Y x n exp(S n ϕ(y))dy, hence Proposition 3.1.c gives Since d(T n x, ∂T n Y x n ) ≤ |T n Y x n | ≤ 1 Proposition 3.1.d also implies that lim n→∞ 1 n log |T n Y x n | = 0 for µ-a.e. x. Furthermore the Birkhoff ergodic theorem gives that lim n 1 n S n ϕ = λ µ for µ-a.e. x, thus using (4) we get the result. Proof. By the mean value theorem we have Since the logarithm is increasing this implies by Proposition 3.1.c. In addition, by the Birkhoff ergodic theorem we have lim n→∞ 1 n S n ϕ(x) = λ µ for µ a.e. x. The conclusion follows then from Proposition 3.1.d and inequality 5.

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 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 x n ) and D n = |Y x n |. 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 x n(r) , which implies that τ (B r (x)) ≥ τ (Y x n(r) ). Since r ≥ d n(r)+1 and n(r) → ∞ as r → 0 we get 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 lim n→∞ τ (Y x n ) n ≥ 1 for any x ∈ X 1 ε . By Lemma 2 there exists a set of full µ-measure X 2 ε such that lim n→∞ − 1 n log d n ≤ λ µ + 2ε for any x ∈ X 2 ε . Thus for any We conclude that the inequality (6) holds on the set of full measure ∩ i≥1 (X 1 1/i ∩ X 2 1/i ). 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 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 = ∨ p−1 i=0 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.

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 n } 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 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 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 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 lim n→∞ − 1 n log d n ≤ λ µ + 2ε for any x ∈ X 2 ε . Thus for any Next we want to find an upper bound for the lim of the same quantity. If m(r) denotes the smallest integer m such that D m < r ≤ D m−1 , then By Lemma 1 there exists a set of full µ-measure X 3 ε such that for any This together with (7) implies that for any In addition, Hofbauer [8] has shown in this setting that hence we conclude by (9) and (10) that the equality (8) holds on the set of full measure ∩ i≥1 (X 1 1/i ∩ X 2 1/i ∩ X 3 1/i ). This finishes the proof.

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 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 we input the concatenated wordpq 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, . . .
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.
For x an infinite 0-1 sequence one defines the average complexity by looking at the first n-bits x(n) and defining K(x) := lim n→∞ K U (x(n)) n .
Note that by equation (11) the average complexity does not depend which universal computer U is chosen. The function K(x) is defined in an analogous way with the lim replaced by a 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.