text:
# Orbit complexity, initial data sensitivity and weakly chaotic dynamical systems

## 1 Introduction

When we think about a chaotic system there are two things that we expect to happen:

* the behavior of the system is unpredictable and complex to be described
* small differences on initial conditions leads to big differences in the evolution of the system.

A rigorous measure of initial conditions sensitivity is not difficult to formalize, it leads to the definition of Lyapunov exponents (see e.g. ) or to the more general Brin-Katok  local entropy.

A measure of the complexity of the behavior of a system is less simple to formalize and in the case of dynamical systems it was given by Brudno . A set of strings is associated by a certain construction to the orbit of a point and then the complexity of the orbit is defined by the Algorithmic Information Content (section 2 ) of the associated strings. The complexity of an orbit is then a measure of the amount of information that is necessary to describe the orbit.

If dynamics are ergodic and lie on a compact space, it can be proved that the entropy of the system is almost everywhere equal to the orbit complexity. In other words, if such a system has positive entropy, then for a.e. $`x`$ the algorithmic information that is necessary to describe $`n`$ steps of the orbit of $`x`$ increases linearly with $`n`$ and the proportionality factor is the entropy of the system. This also implies that if a system has an invariant measure $`\mu `$, its entropy is equal to the mean value of the orbit complexity with respect to $`\mu `$ .

It is known that if a system has positive entropy the typical speed of separation of nearby starting orbits is exponential (roughly speaking $`\mathrm{\Delta }x(t)\mathrm{\Delta }x(0)2^{\lambda t}`$). The speed of separation of exponentially divergent orbits is characterized by the number $`\lambda `$. Lyapunov exponents and Brin-Katok  local entropy are real valued indicators of the speed of exponential separation of the orbits (the number $`\lambda `$ on the exponent of the above formula). The work of Ruelle-Pesin  and Brin-Katok shows (under some assumption on the dynamical system) that their indicators are almost everywhere equal to the entropy of the system. In other words: in an ergodic, compact dynamical system the indicator of (exponential) initial data sensitivity is a.e. equal to the entropy which is a.e. equal to the orbit complexity. Thus there is a relation between initial data sensitivity and orbit complexity.

This implies that in the compact case orbit complexity and instability are both faces of the same coin. In the case of compact dynamical systems this motivates the general Ford’s claim  that orbit complexity was a synonym of chaos. We remark that if the space is not compact there are examples (, ) of systems with no sensitivity to initial conditions and hight orbit complexity.

In  another definition of orbit complexity is given by the use of computable structures, the definition is given by a different approach involving some constructivity concept. This definition is equivalent to Brudno’s one if the dynamics lie on a compact space. Replacing compactness with constructivity allows a more powerful investigation of the relation between orbit complexity and chaos in the non compact case.

In many examples of dynamical systems however the entropy could be 0, the speed of separation of nearby starting trajectories could be less than exponential and the increasing of the information contained in $`n`$ step of the orbit could be less than linear. This is the case of the so called Weakly Chaotic Dynamics.

The study of weakly chaotic dynamics was discovered to be important for application purposes. There are connections with many physical and economic phenomena: self organized criticality, the so called chaos threshold, the sporadic dynamics, the anomalous diffusion processes and many others (see for example ,,,,). In these examples of weakly chaotic dynamics the traditional indicators of chaos (K.S. entropy, Lyapunov exponents, Brudno’s orbit complexity) vanishes. These indicators are not able to distinguish between all the various cases of weakly chaotic dynamics. They see all them as trivial dynamical systems.

Some definitions of generalized entropy have been already proposed in literature (see e.g. ,, for definitions about dynamical systems). One of the most fruitful was the one given by Tsallis that found a great variety of applications: long range interacting systems, self gravitating systems, quantum mechanics, social phenomena and many others (see

http://tsallis.cat.cbpf.br/biblio.htm for an updated bibliography of related topics). In the literature relations between Tsallis entropy and initial data sensitivity have been proved (,), indicating that the main field of application of Tsallis entropy in dynamical systems is the case of power law initial data sensitivity (if two points starts at distance $`\mathrm{\Delta }x(0)`$ then $`\mathrm{\Delta }x(t)\mathrm{\Delta }x(0)t^\alpha `$).

The aim of this work is to give a very general definition of indicators of initial data sensitivity and orbit complexity and to prove a relation between them that generalizes the above stated “orbit complexity=sensitivity to initial conditions”. This will have some interesting corollary as a consequence (Theorem 42) and finally we will see some applications of our formulas to some example of weakly chaotic dynamics.

The indicators we will define will have values in a totally ordered set $``$ which is constructed in section 3 by the use of the non standard analysis. In section 2 we add an elementary introduction to non standard analysis, so that the paper is self contained. The ordered space $``$ will contain (in some way) a representative of all the asymptotic behaviors for $`n\mathrm{}`$ of sequences of reals $`a_n:𝐍𝐑`$ (for example the various orders of infinity and infinitesimal will correspond to some element of $``$). In this way we include in one definition all the possible asymptotic behaviors of initial data sensitivity, orbit complexity or entropy, and so on.

We clarify this by an example. Let us consider the classical definition of topological entropy for a compact dynamical system $`(X,T)`$. We recall and comment the original definition. If $`x,yX`$ let us say that $`x,y`$ are $`(n,ϵ)`$ separated if $`d(T^k(x),T^k(y))>ϵ`$ for some $`k\{0,\mathrm{},n1\}`$. If $`d(T^k(x),T^k(y))ϵ`$ for each $`k\{0,\mathrm{},n1\}`$ then $`x,y`$ are said to be $`(n,ϵ)`$ near. That is: two points are separated if they give rise to substantially different orbits. A set $`EX`$ is called $`(n,ϵ)`$ separated if $`x,yE,xy`$ then $`x,y`$ are $`(n,ϵ)`$ separated. Let us consider

$$s(n,ϵ)=max\{card(E):EXis(n,ϵ)separated\}$$

The number $`s(n,ϵ)`$ measures the number of substantially different $`n`$ steps orbits that appear in $`(X,T)`$.

A chaotic D.S. will have more and more possible different orbits as $`n`$ increases. The idea of the definition is that in the more chaotic D.S. (where the entropy will be higher) the cardinality $`s(n,ϵ)`$ increases more quickly as $`n`$ increases.

The remaining part of the definition is a way to output a real number from this idea. The number will be a measure of the speed of exponential increasing of the cardinality $`s(n,ϵ)`$ as $`n`$ increases. We define

$$h(T,ϵ)=\underset{n\mathrm{}}{limsup}\frac{\mathrm{log}s(n,ϵ)}{n}$$

and then the topological entropy of $`T`$ is defined as

$$h_{top}(T)=\underset{ϵ0}{lim}h_K(T,ϵ).$$

The logarithm in the definition is taken because $`s(n,ϵ)`$ is expected to increase exponentially $`(s(n,ϵ)2^{h(T,ϵ)n})`$. This is a very important case; the case of strongly chaotic dynamic. However, it is worth remarking that there are examples of chaotic topological dynamical systems with $`0`$ entropy (see  for example).

When $`s(n,ϵ)`$ increases less than exponentially the value of $`h(T,ϵ)`$ will be zero. If we want to state a definition of generalized topological entropy that is sensitive to the cases when $`s(n,ϵ)`$ increases as a power law we could define (“a la Tsallis” to some extent)

$$h_q(T,ϵ)=\underset{n\mathrm{}}{limsup}\frac{S_q(s(n,ϵ))}{n}$$

where $`S_q:RR`$ is

$$S_q(W)=\frac{W^{\frac{1}{1q}}1}{1q}.$$

In this definition the parameter $`q`$ plays a role similar to the Hausdorff dimension. Each dynamical system will have a special value of $`q`$ such that $`S_q(s(n,ϵ))`$ increases linearly and allows a nontrivial value of $`h_q`$. The special $`q`$ of each D.S. will be an indicator of the type of chaotic behavior of the system under consideration.This definition will classify the various cases of power law increasing of $`s(n,ϵ)`$ and the exponential one (when $`q=1`$) but it makes no difference between exponential and stretched exponential111 $`s(n,ϵ)2^{cn^\alpha }.`$ (both $`q=1`$) and between constant and logarithm ($`q=0`$).

We shall see later with the help of examples that the asymptotic behavior of the measures under study exhibit a large variety of different cases. So we need the more possible general definition. This will be done with a definition with values in $``$. Moreover in this general setting we can prove very general theorems that will have nontrivial meaning in all this variety of examples. We want to remark that the use of the language of the non standard analysis comes about naturally when we want to consider the asymptotic behavior of a sequence of reals. On the other hand, Benci  gives an elementary but rigorous approach to the nonstandard analysis which we summarize in a page in section 2.3. This approach is very simple and does not require any deep tool of logic. So we think that our definitions can be easily understood by readers with no experience in this subject.

In section 3 we define the notions of generalized initial data sensitivity at a point $`x`$ and the notion of generalized complexity of the orbit of $`x`$. For the definition of constructivity and orbit complexity we introduce the notion of computable structure on a metric space (Section 2.2). Then, under the assumption that the system is constructive we prove a relation (Theorem 40) between sensitivity and orbit complexity that is a quantitative and rigorous version of the following statement: the asymptotic behavior of the quantity of information that is necessary to reconstruct the orbit of $`x`$ depends on the initial data sensitivity at $`x`$ and on the ’complexity’ of the point $`x`$ in $`X`$. We remark that theorem 40 is general, it holds even in infinite dimensional spaces, provided that the maps we consider are constructive.

This relation will have as a consequence that the points with upper initial data sensitivity ($`R(x)`$ in Section 3.1) strictly greater than the exponential one are a $`0`$ dimensional set (Theorem 42).

We remark that our relations are pointwise. We make no use of invariant measures that in many cases of weakly chaotic dynamics are trivial or very complicated (with multifractal support). Instead sometime we make use of the natural measure that can be defined on the metric space $`X`$: the Hausdorff measure.

In section 4 we apply the the main results of section 3 to give a rigorous estimation of the orbit complexity in an important example of weakly chaotic dynamic: the Manneville maps.

## 2 AIC, computable structures and non standard analysis

### 2.1 Algorithmic Information Theory

In this section we give an introduction to algorithmic information theory. The introduction will be informal, to help the reader that is not familiar with recursion theory to understand the paper. A more detailed exposition of algorithmic information theory can be found in  or .

Let us consider the set $`\mathrm{\Sigma }=\{0,1\}^{}`$ of finite (possibly empty) binary strings. If $`s`$ is a string we define $`|s|`$ as the length of $`s`$.

Let us consider a Turing machine (a computer) $`C`$: by writing $`C(p)=s`$ we mean that $`C`$ starting with input $`p`$ (the program) stops with output $`s`$ ($`C`$ defines a partial recursive function $`C:\mathrm{\Sigma }\mathrm{\Sigma }`$). If the input gives a never ending computation the output (the value of the recursive function) is not defined. If $`C:\mathrm{\Sigma }\mathrm{\Sigma }`$ is recursive and its value is defined for all the input strings in $`\mathrm{\Sigma }`$ (the computation stops for each input) then we say that $`C`$ is a total recursive function from $`\mathrm{\Sigma }`$ to $`\mathrm{\Sigma }`$. The algorithmic information content of a string will be the length of the shortest program that outputs the string.

###### Definition 1

The Kolmogorov complexity or algorithmic information content of a string $`s`$ given $`C`$ is the length of the smallest program $`p`$ giving $`s`$ as the output:

$$K_C(s)=\underset{C(p)=s}{min}|p|$$

if $`s`$ is not a possible output for the computer $`C`$ then $`K_C(s)=\mathrm{}`$ .

For example by this definition we see that the algorithmic information content (A.I.C.) of a $`2n`$ bits long periodic string

$$s=^{\prime \prime }1010101010101010101010\mathrm{}^{\prime \prime }$$

is small because the string is output of a shortest program:

repeat $`n`$ times (write (“10”))

the AIC of the string $`s`$ is then less or equal than $`log(n)+Constant`$ where $`log(n)`$ bits are sufficient to code “$`n`$” and the constant represents the length of the code for the computer $`C`$ representing the instructions “repeat…”. As it is intuitive the information content of a periodic string is very poor. On the other hand each $`n`$ bits long string

$$s^{}=^{\prime \prime }1010110101010010110\mathrm{}^{\prime \prime }$$

is output of the trivial program

$$write(^{\prime \prime }1010110101010010110\mathrm{}^{\prime \prime })$$

this is of length $`n+constant`$ this implies that the AIC of each string is (modulo a constant which depends on the chosen computer $`C`$) less or equal than its length.

Until this point the algorithmic information content of a string depends on the choice of the computer $`C`$. We will see that there is a class of computers that allows an “almost” universal definition of algorithmic information content of a string: if we consider computers from this class the A.I.C. of a string will be defined independently of the computer up to a constant. In order to define such a class of universal computers we give some notations that are necessary to work with strings: there is a correspondence $`c:\mathrm{\Sigma }𝐍`$ from the set $`\mathrm{\Sigma }`$ and the set $`𝐍`$ of natural numbers

$$\mathrm{}0,01,12,003,014,105,\mathrm{}$$

This correspondence allows us to interpret natural numbers as strings and vice-versa when it is needed. We remark that $`|s|log(c(s))+1`$. 222 In this paper all the logarithms are in base two.

If $`s`$ is a string with $`|s|=n`$ we denote by $`s\widehat{}`$ the string $`s_0s_0s_1s_1\mathrm{}s_{n1}s_{n1}01.`$ If $`a=a_1\mathrm{}a_n`$ and $`b=b_1\mathrm{}b_m`$ are strings then $`ab`$ is defined as the string $`a_1\mathrm{}a_nb_1\mathrm{}b_m`$. If $`a`$ and $`b`$ are strings then $`a\widehat{}b`$ is an encoding of the couple $`(a,b)`$. There is an algorithm that getting the string $`a\widehat{}b`$ is able to recover both the strings $`a`$ and $`b`$. An universal Turing machine intuitively is a machine that can emulate any other Turing machine if an appropriate input is given. We recall that there is a recursive enumeration $`A_1,A_2\mathrm{}`$ of all the Turing machines.

###### Definition 2

A Turing machine $`𝒰`$ is said to be universal if for all $`m𝐍`$ and $`p\mathrm{\Sigma }`$ then $`𝒰(c^1(m)\widehat{}p)=A_m(p)`$.

In the last definition the machine $`𝒰`$ is universal because $`𝒰`$ is able to emulate each other machine $`A_m`$ when in its input we specify the number $`m`$ identificating $`A_m`$ and the program to be runned by $`A_m`$. It can be proved that an universal Turing machine exists.

###### Definition 3

A Turing machine $`F`$ is said to be asymptotically optimal if for each Turing machine $`C`$ and each binary string $`s`$ we have $`K_F(s)K_C(s)+c`$ where the constant $`c`$ depends on $`C`$ and not on $`s`$.

The following proposition can be proved from the definitions

###### Proposition 4

If $`𝒰`$ is an universal Turing machine then $`𝒰`$ is asimptotically optimal.

This tells us that choosing an universal Turing machine the complexity of a string is defined independently of the given Turing machine up to a constant. For the remaining part of the paper we will suppose that an universal Turing machine $`𝒰(p)`$ is chosen once forever.

### 2.2 Computable Structures, Constructivity

A computable structure on a separable metric space $`(X,d)`$ is a class of dense immersions ($`I:\mathrm{\Sigma }X`$) of the space of finite strings $`\mathrm{\Sigma }`$ in the metric space. The immersions are such that the distance $`d`$ restricted to the points that are images of strings ($`x=I(s):xX,s\mathrm{\Sigma }`$) is a “computable” function. Many concrete metric spaces used in analysis or in geometry have a natural choice of a computable structure. The use of computable structures allows to consider algorithms acting over metric spaces and to define constructive functions between metric spaces, that is, functions such that we can work with by using a finite amount of information. In the following we often will assume that the dynamical systems under our consideration are constructive. All the dynamical system that we can construct explicitely are construcive. From the philosophical point of wiew we think that the assumption of constructivity is not unnatural because even if the maps coming from physical reality were not constructive, the models used to describe such a reality should be constructive (to allow calculations). On the other hand, to add constructivity allows to prove stronger theorems, avoiding pathologies coming from random maps.

An interpretation function is a way to interpret a string as a point of the metric space.

###### Definition 5

An interpretation function on $`(X,d)`$ is a function $`I:\mathrm{\Sigma }X`$ such that $`I(\mathrm{\Sigma })`$ is dense in $`X`$.

A point $`xX`$ is said to be ideal if it is the image of some string $`x=I(s),s\mathrm{\Sigma }`$. An interpretation is said to be computable if the distance between ideal points is computable with arbitrary precision:

###### Definition 6

A computable interpretation function on $`(X,d)`$ is a function $`I:\mathrm{\Sigma }X`$ such that $`I(\mathrm{\Sigma })`$ is dense in $`X`$ and there exists a total recursive function $`D:\mathrm{\Sigma }\times \mathrm{\Sigma }\times 𝐍𝐐`$ such that $`s_1,s_2\mathrm{\Sigma },n𝐍`$:

$$|d(I(s_1),I(s_2))D(s_1,s_2,n)|\frac{1}{2^n}.$$

Two interpretations are said to be equivalent if the distance from an ideal point from the first and a point from the second is computable up to arbitrary precision. For example, the finite binary strings $`s\mathrm{\Sigma }`$ can be interpreted as rational numbers by interpreting the string as the binary expansion of a number. Another interpretation can be given by interpreting a string as an encoding of a couple of integers whose ratio gives the rational number. If the last encoding is recursive, the two interpretation are equivalent.

###### Definition 7

Let $`I_1`$ and $`I_2`$ be two computable interpretations in $`(X,d)`$; we say that $`I_1`$ and $`I_2`$ are equivalent if there exists a total recursive function $`D^{}:\mathrm{\Sigma }\times \mathrm{\Sigma }\times 𝐍𝐐`$, such that $`s_1,s_2\mathrm{\Sigma },n𝐍`$:

$$|d(I_1(s_1),I_2(s_2))D^{}(s_1,s_2,n)|\frac{1}{2^n}.$$

###### Proposition 8

The relation defined by definition 7 is an equivalence relation.

For the proof of this proposition see .

###### Definition 9

A computable structure $``$ on $`X`$ is an equivalence class of computable interpretations in $`X`$.

For example if $`X=𝐑`$ we can consider the interpretation $`I:\mathrm{\Sigma }𝐑`$ defined in the following way: if $`s=s_1\mathrm{}s_n\mathrm{\Sigma }`$ then

$$I(s)=\underset{1in}{}s_i2^{[n/2]i}.$$
(1)
This is an interpretation of a string as a binary expansion of a number. $`I`$ is a computable interpretation, the computable structure on $`𝐑`$ containing $`I`$ will be called standard computable structure. If $`r=r_1r_2\mathrm{}`$ is an infinite string such that $`lim\frac{K_C(r_1\mathrm{}r_n)}{n}=1`$333such a string exist, see for example  theorem 13. then the interpretation $`I_r`$ defined as $`I_r(s)=I(s)+r(i)2^i`$ is computable but not equivalent to $`I`$. $`I`$ and $`I_r`$ belongs to different computable structures.

In a similar way it is easy to construct computable structures in $`𝐑^n`$ or in separable function spaces codifying a dense subset (for example the set of step functions) with finite strings. We remark as a property of the computable structures that if $`B_r(I(s))`$ is an open ball with center in an ideal point $`I(s)`$ and rational radius $`r`$ and $`I(t)`$ is another point then there is an algorithm that verifies if $`I(t)B_r(I(s))`$. If $`I(t)B_r(I(s))`$ then the algorithm outputs “yes”, if $`I(t)B_r(I(s))`$ the algorithm outputs “no” or does not stop. The algorithm calculates $`D(s,t,n)`$ for each $`n`$ until it finds that $`D(s,t,n)+2^n<r`$ or $`D(s,t,n)2^n>r`$, in the first case it outputs “yes” and in the second it outputs “no”, if $`d(I(s),I(t))r`$ the algorithm will stop and output an answer.

We give a definition of morphism of metric spaces with computable structures, a morphism is heuristically a computable function between computable metric spaces.

###### Definition 10

If $`(X,d,)`$ and $`(Y,d^{},𝒥)`$ are spaces with computable structures; a function $`\mathrm{\Psi }:XY`$ is said to be a morphism of computable structures if $`\mathrm{\Psi }`$ is uniformly continuous and for each pair $`I,J𝒥`$ there exists a total recursive function $`D^{}:\mathrm{\Sigma }\times \mathrm{\Sigma }\times 𝐍𝐐`$, such that $`s_1,s_2\mathrm{\Sigma },n𝐍`$:

$$|d^{}(\mathrm{\Psi }(I(s_1)),J(s_2))D^{}(s_1,s_2,n)|\frac{1}{2^n}.$$

We remark that $`\mathrm{\Psi }`$ is not required to have dense image and then $`\mathrm{\Psi }(I())`$ is not necessarily an interpretation function equivalent to $`J`$.

###### Remark 11

As an example of the properties of the morphisms, we remark that if a map $`\mathrm{\Psi }:XY`$ is a morphism then given a point $`xI(\mathrm{\Sigma })X`$ it is possible to find by an algorithm a point $`yJ(\mathrm{\Sigma })Y`$ as near as we want to $`\mathrm{\Psi }(x)`$.

The procedure is simple: if $`x=I(s)`$ and we want to find a point $`y=J(z_0)`$ such that $`d^{}(\mathrm{\Psi }(I(s)),y)2^m`$ then we calculate $`D^{}(s,z,m+2)`$ for each $`z\mathrm{\Sigma }`$ until we find $`z_0`$ such that $`D^{}(s,z_0,m+2)<2^{m1}`$. Clearly $`y=J(z_0)`$ is such that $`d^{}(\mathrm{\Psi }(x),y)2^m`$. The existence of such a $`z_0`$ is assured by the density of $`J`$ in $`Y`$. In particular the identity is a morphism. Remark 11 applied to the identity will be used in the proof of lemma 13.

A constructive map is a morphism for which the continuity relation between $`ϵ`$ and $`\delta `$ is given by a recursive function. The following is in some sense a generalization of the definition of Grzegorczyk, Lacombe (see e.g. ) of constructive function.

###### Definition 12

A function $`\mathrm{\Psi }:(X,d,)(Y,d^{},𝒥)`$ between spaces with computable structure $`(X,),(Y,𝒥)`$ is said to be constructive if $`\mathrm{\Psi }`$ is a morphism between the computable structures and it is effectively uniformly continuous, i.e. there is a total recursive function $`f:𝐍𝐍`$ such that for all $`x,yX`$ $`d(x,y)<2^{f(n)}`$ implies $`d^{}(\mathrm{\Psi }(x),\mathrm{\Psi }(y))<2^n`$.

If $`f(n)`$ is recursive and satisfies the hypothesis that, $`d(x,y)<2^{f(n)}`$ implies $`d(T(x),T(y))<2^n`$ then $`max(f(n),n)`$ is recursive and still satisfies the hypothesis. Then we can suppose that if $`f(n)`$ is a function of effective continuity then $`f(n)n`$.

If a map between spaces with a computable structure is constructive then there is an algorithm to follow the orbit each ideal point $`x=I(s_0)`$.

###### Lemma 13

If $`T:(X,)(X,)`$ is constructive, $`I`$ then there is an algorithm (a total recursive function) $`A:\mathrm{\Sigma }\times 𝐍\times 𝐍\mathrm{\Sigma }`$ such that $`k,m𝐍,s_0\mathrm{\Sigma }`$ $`d(T^k(I(s_0)),I(A(s_0,k,m)))<2^m`$.

Proof. Since $`T`$ is effectively uniformly continuous we define the function $`g_k(m)`$ inductively as $`g_1(m)=f(m)+1`$, $`g_i(m)=f(g_{i1}(m)+1)`$ where $`f`$ is the function of effective uniform continuity of $`T`$ (definition 12). If $`d(x,y)<2^{g_k(m)}`$ then $`d(T^i(y),T^i(x))<2^m`$ for $`i\{1,\mathrm{},k\}`$. Let us choose $`I`$. We recall that the assumption that $`T`$ is a morphism implies that there is a recursive function $`D^{}(s_1,s_2,n)`$ such that

$$|D^{}(s_1,s_2,n)d(I(s_1),T(I(s_2)))|<2^n.$$

Let us suppose that $`x=I(s_0)`$. Now let us describe the algorithm $`A`$: using the function $`D^{}`$ and the function $`f`$, $`A`$ calculates $`g_k(m)`$ and finds a string $`s_1`$ such that $`d(I(s_1),T(I(s_0)))<2^{g_k(m)}`$ as described in remark 11. This is the first step of the algorithm. Now $`d(T(I(s_1)),T^2(x))2^{(g_{k1}+1)}`$. We can use $`D^{}`$ to find a string $`s_2`$ such that $`d(I(s_2),T(I(s_1)))<2^{(g_{k1}+1)}`$. By this $`d(I(s_2),T^2(x))2^{g_{k1}}`$. This implies that $`d(T(I(s_2)),T^3(x))2^{(g_{k2}+1)}`$, then we find $`s_3`$ such that $`d(I(s_3),T(s_2))2^{(g_{k2}+1)}`$ and so on for $`k`$ steps. At the end we find a string $`s_k`$ such that $`d(I(s_k),T^k(x))2^m`$. $`\mathrm{}`$

### 2.3 Non standard analysis

We define the extended real line $`𝐑^{}`$ to be an ordered field satisfying suitable axioms. The existence of such a field is proved in . $`𝐑^{}`$ will contain the standard real numbers and other elements representing infinite and the infinitesimal numbers.

We call Hyperreal Line a field satisfying the following axioms:

###### Axiom 14

The set of the hyperreal numbers $`𝐑^{}`$ is an ordered field which contains $`𝐑`$ as a subfield.

###### Axiom 15

There is a surjective ring homomorphism

$`J:𝐑^𝐍𝐑^{}`$

associating to each real sequence an hyperreal number.

Intuitively the homomorphism $`J`$ associates to a sequence of reals its asymptotic behavior. For example if $`\underset{n\mathrm{}}{lim}a_n=0`$ then $`J(a_n)`$ will be an infinitesimal number. Moreover if $`a=(a_i)`$ and $`b=(b_i)`$ are two sequences we would like that if $`a_ib_i`$ for all $`i𝐍`$ then $`J(a)J(b)`$. For this reason $`J`$ is required to satisfy the following monotonicity property

###### Axiom 16

If there exists $`k𝐍^+`$ such that

$`n𝐍^+,\varphi _{kn}a`$

with $`a𝐑`$, then

$`J(\varphi )a`$ .

From axiom 16 it follows for example that if $`a_i=2^i`$ and $`b_i=\frac{1}{i}`$ then $`0J(a_i)J(b_i)`$. Another consequence of axiom 16 is that for each real sequence $`x_i`$ $`liminf(x_i)J(x_i)limsup(x_i)`$.

A field satisfying our axioms exists. As the reader could imagine, it can be constructed from the set of real sequences modulo a suitable equivalence relation ().

#### 2.3.1 Extension of functions, infinite and infinitesimal numbers.

Given any function $`f:𝐑𝐑`$ we extend it to a function $`f^{}:𝐑^{}𝐑^{}`$ as follows: if $`a_i`$ is a real sequence and $`x=J(a_i)𝐑^{}`$ we define

$`f^{}(x)=f^{}(J(a_i))=J(f(a_i)).`$

###### Proposition 17

the definition is well posed i.e. $`J(a_i)=J(b_i)`$ implies that $`J(f(a_i))=J(f(b_i)).`$

The proof of proposition 17 can be found in .

As we stated before, in $`𝐑^{}`$ there are some elements representing the infinite and infinitesimal numbers:

###### Definition 18

An hyperreal number $`\xi `$ is called infinite if $`k𝐍`$ we have $`|\xi |>k`$. A number $`\xi `$ is called infinitesimal if $`k𝐍,|\xi |<\frac{1}{k}`$. A number $`\xi `$ is called bounded if $`k𝐍,|\xi |<k`$.

For example the reader could verify directly from the axioms that if $`a_i:𝐍𝐑`$ is the identity: $`a_i=i`$ then $`J(a_i)`$ is infinite and $`J(\frac{1}{a_i})`$ is infinitesimal.

## 3 sensitivity and orbit complexity

Now we construct the space $``$ in which our indicators of orbit complexity and initial data sensitivity will have value.

###### Definition 19

If $`a,b𝐑^{}`$ we say that $`a`$ and $`b`$ have the same order and write $`ab`$ if and only if both $`\frac{a}{b}`$ and $`\frac{b}{a}`$ are bounded.

$``$ it is clearly an equivalence relation. In the following by $`[\alpha ]`$ we will indicate the equivalence class of $`\alpha `$.

We now define an ordering relation on the quotient space $`\frac{𝐑^{}}{}`$. We say that $`[a][b]`$444By an abuse of notations we use the symbol $``$ for this ordering relation, this will cause no ambiguity with the ordering relation defined on $`𝐑^{}`$.  if $`x[a],y[b]`$ then or $`xy`$ or $`x<y`$. We remark that the order relation on $`𝐑^{}`$ is compatible with the equivalence relation $``$, if $`ab`$ in $`𝐑^{}`$ then $`[a][b]`$ in $`\frac{𝐑^{}}{}`$ . And thus $`\frac{𝐑^{}}{}`$ is totally ordered. The relation $`<`$ is then defined in the obviuos way as $`[a]<[b][a][b],[a][b]`$.

$`\frac{𝐑^{}}{}`$ contains a representative of all the infinite (infinitesimal) asymptotic behaviors of real sequences. $`\frac{𝐑^{}}{}`$ is sometime called the group of orders. The natural projection from $`𝐑^{}`$ to $`\frac{𝐑^{}}{}`$ $`:a[a]`$ allows to forget all the lower order terms in the hyperreal number $`a`$: for example if $`a_i=i`$ as above $`J(a_{i}^{}{}_{}{}^{2}+a_i)`$ and $`J(a_{i}^{}{}_{}{}^{2}+\sqrt{a_i})`$ belongs to the same class as $`J(a_{i}^{}{}_{}{}^{2})`$, in other words $`[J(a_{i}^{}{}_{}{}^{2}+a_i)]=[J(a_{i}^{}{}_{}{}^{2}+\sqrt{a_i})]=[J(a_{i}^{}{}_{}{}^{2})]`$.

Unfortunately $`\frac{𝐑^{}}{}`$ is not complete (as $`𝐑^{}`$ is not complete). The supremum or the infimum of a sequence in $`\frac{𝐑^{}}{}`$ may not exist in $`\frac{𝐑^{}}{}`$. For this reason we will consider a space $``$ which is a completion of $`\frac{𝐑^{}}{}`$, the sup and inf of each sequence in $`\frac{𝐑^{}}{}`$ is in $``$. We now outline a possible construction of a completition of $`\frac{𝐑^{}}{}`$, there are other possible costructions. Another possible completition of $`\frac{𝐑^{}}{}`$ can be constructed for example by Dedekind sections. We construct $``$ by quotienting the set of monotone sequences in $`\frac{𝐑^{}}{}`$ by a suitable equivalence relation. This will add the supremum to each countable sequence.

###### Proposition 20

There is an ordered space $``$ such that $`\frac{𝐑^{}}{}`$ in a natural and order preserving way and if $`a_i\frac{𝐑^{}}{}`$ is a monotone sequence then $`inf(a_i)`$ and $`sup(a_i)`$ are in $``$.

Proof. Let us consider the set of monotone sequences in $`\frac{(𝐑^{})}{}`$:

$$𝒜=\{(a_i):𝐍\frac{𝐑^{}}{}s.t.a_iismonotone\}$$

in $`𝒜`$ the set $`\frac{𝐑^{}}{}`$ will be identified with the subset of constant sequences.

We define the ordering relation on $`𝒜`$ in the following way $`(a_i)<(b_j)`$ $``$ $`M`$ such that $`n,m`$ with $`n>M,m>M`$ then $`a_n<b_m`$ .

We define the relation $``$ in the following way: $`(a_i)(b_j)`$ if neither $`(a_i)<(b_j)`$ nor $`(b_j)<(a_i)`$. $``$ is an equivalence relation: $``$ is trivially symmetric and reflexive. The transitivity follows from the remark that if $`a_i`$ is not $`<b_j`$ then $`Mn,ms.t.n>M,m>M,a_nb_m`$. As it is easy to verify this is a transitive relation (because the sequences in $`𝒜`$ are monotone).

The set of equivalence classes $`=\frac{𝒜}{}`$ is then totally ordered in the same way as before and contains $`\frac{𝐑^{}}{}`$ as a subset. Moreover each monotone sequence in $`\frac{𝐑^{}}{}`$ has its $`sup`$ and $`inf`$ in $``$: let us indicate with $`p`$ the natural projection associating to each element in $`𝒜`$ its equivalence class. If for example $`a=(a_i)`$ is a nondecreasing sequence then $`inf(a)`$ is the equivalence class of the constant sequence $`b=(b_j)`$ such that $`jb_j=a_0`$ and $`sup(a)=p(a)`$ ($`p`$ is the natural projection map as defined above). It is easy to verify that $`p(a)>a_j`$ for each $`j𝐍`$ and for each $`xs.t.`$ $`j𝐍,x>a_j`$ we have $`x>p(a)`$ or $`xp(a)`$ .$`\mathrm{}`$

The set $``$ may look in some way mysterious and not practical to be used. The reader will see in the examples that the elements of $``$ we will have as value of our invariants will be classes that can be expressed in an explicit way. For example a possible value of $`r(x)`$ (definition 24) could be $`[J(n^{\frac{1}{2}})]`$ (the class in $`\frac{R^{}}{}`$ containing the asymptotic behavior of the sequence $`a_n=n^{\frac{1}{2}}`$). Since $`\frac{R^{}}{}`$ is immersed in $``$ in a natural way we can consider an element of $`\frac{R^{}}{}`$ as an element of $``$ without ambiguity. Another possible value of $`r(x)`$ could be $`[J(n^{\frac{1}{3}})]`$ and it is clear that $`[J(n^{\frac{1}{2}})][J(n^{\frac{1}{3}})]`$ so we can easily compare the values.

The notion of infinite and infinitesimal numbers can be extended to the elements of $``$: if $`v𝐑,v>0`$ then $`c=[J(v)]`$ is the element of $``$ corresponding to the class of bounded and not infinitesimal numbers. Moreover: an element $`ϵ`$ is said to be infinitesimal if $`ϵ<c`$ and an element $`\gamma `$ is said to be infinite if $`ϵ>c`$.

Finally we remark that $``$ is closed by countable $`inf`$ and $`sup`$ and the projection $`p`$ (defined in the proof of the above proposition) can be extended to a function from the set of monotone sequences in $``$ to $``$, associating to a sequence its supremum or infimum according that the sequence is increasing or decreasing.

###### Proposition 21

If $`(a_i)`$ is a monotone sequence in $``$, then

$$sup(a_i),inf(a_i)$$

.

Proof. Let us suppose that $`(a_i)`$ is a non decreasing sequence, the case where $`(a_i)`$ is non increasing is analogous. We show that $`sup(a_i)`$. If $`(a_i)`$ is eventually constant the proposition is obvious. If $`(a_i)`$ is not eventually constant let us consider a subsequence $`a_{i_k}`$ that is strictly increasing ($`k`$ $`a_{i_k}>a_{i_{k1}}`$). The elements $`a_{i_k},a_{i_{k1}}`$ are equivalence classes of monotone sequences with values in $`\frac{R^{}}{}`$. Let use consider two of this sequences $`(\alpha _n^{k1})_{n𝐍}:𝐍\frac{R^{}}{}`$ such that $`p((\alpha _n^{k1})_{n𝐍})=(a_{i_{k1}})`$ and $`(\alpha _n^k)_{n𝐍}:𝐍\frac{R^{}}{}`$ such that $`p((\alpha _n^k)_{n𝐍})=(a_{i_{k1}})`$. Since $`(\alpha _n^{k1})<(\alpha _n^k)`$ then $`M_k𝐍s.t.n\alpha _n^{k1}<\alpha _{M_k}^k`$. This is true for each choice of the sequences $`\alpha ^k,\alpha ^{k1}`$ in the classes $`a_k,a_{k1}`$, hence what follows does not depends on the choice of $`\alpha ^k`$ and $`\alpha ^{k1}`$. Let us now consider the sequence $`(\alpha _{M_k}^k)_{k𝐍}:𝐍\frac{R^{}}{}`$ this is an increasing sequence and $`j<k,a_{i_j}<\alpha _{M_k}^k`$, then $`i𝐍,p(\alpha _{M_k}^k)>a_i`$. Now it is easy to see that if $`b`$ is such that $`i_kb>a_{i_k}`$ then $`bp(\alpha _{M_k}^k)`$ or $`b>p(\alpha _{M_k}^k)`$, then $`p(\alpha _{M_k}^k)`$ is $`sup(a_i)`$. $`\mathrm{}`$

By the above result we also see that the function $`p:𝒜`$ can be extended to a function $`\overline{p}:\{(a_i):𝐍s.t.a_iismonotone\}`$ by associating to each sequence its $`sup`$ of $`inf`$ according that the sequence is increasing or decreasing.

### 3.1 Initial data sensitivity

Let $`X`$ be a separable metric space and $`T`$ a function $`XX`$. 555We remark that in this and in the following subsection we do not require that $`T`$ is continuous. Let us consider the following set:

$$B(n,x,ϵ)=\{yX:d(T^i(y),T^i(x))ϵis.t\mathrm{.\; 0}in\}.$$

$`B(n,x,ϵ)`$ is the set of points “following” the orbit of $`x`$ for $`n`$ steps at a distance less than $`ϵ`$. When the orbits of $`(X,T)`$ diverges the set $`B(n,x,ϵ)`$ will be smaller and smaller as $`n`$ increases. The speed of decreasing of the size of this set considered as a function of $`n`$ will be a measure of the sensitivity of the system to changes on initial conditions.

Brin and Katok used the set $`B(n,x,ϵ)`$ for their definition of local entropy . In their paper the measure of the size of $`B(n,x,ϵ)`$ was the invariant measure of the set.

If we are interested to approximate the orbit of $`x`$ for $`n`$ steps we are interested to know how close we must approach the initial condition $`x`$ to ensure that the resulting approximate orbit is close to the orbit of $`x`$; another possible measure of the size of $`B(n,x,ϵ)`$ is then the radius of the biggest ball with center $`x`$ contained in $`B(n,x,ϵ)`$.

$$r(x,n,ϵ)=\underset{B_r(x)B(n,x,ϵ)}{supr}.$$

Or the radius of the smaller ball that contains $`B(n,x,ϵ)`$

$$R(x,n,ϵ)=\underset{B_R(x)B(n,x,ϵ)}{infR}.$$

As said before the generalized initial data sensitivity will be a function associating to a point of $`X`$ a class in $``$ indicating how faster orbits coming from a neighborhood of $`x`$ will diverge. For this purpose we measure how faster $`r(x,n,ϵ)`$ decreases as $`n`$ increases, i.e. we consider the asymptotic behavior of the sequence $`r(x,n,ϵ)`$ as $`n`$ increases. First we define

###### Definition 22

We define $`r_ϵ:X\frac{R^{}}{}`$ as

$$r_ϵ(x)=[J(r(x,n,ϵ))]$$

and

$`R_ϵ:X\frac{R^{}}{}`$ as

$$R_ϵ(x)=[J(R(x,n,ϵ))]$$

The following lemma implies that $`r_ϵ(x)`$ and $`R_ϵ(x)`$ are monotone functions with respect to $`ϵ`$.

###### Lemma 23

If $`ϵ>\theta `$ then $`r_ϵ(x)r_\theta (x)`$, $`R_ϵ(x)R_\theta (x)`$.

Proof. Obvious $`\mathrm{}`$

For the previous lemma we define the indicator of initial data sensitivity at $`x`$ by letting $`ϵ`$ go to $`0`$ as the infimum of the $`r_ϵ(x)`$ for $`ϵ𝐑,ϵ>0`$. This infimum will be in $``$.

###### Definition 24

We define the indicator of initial data sensitivity at $`x`$ as

$`r(x):X`$

$$r(x)=\underset{ϵ𝐑^+}{inf}r_ϵ(x)$$

In the same way we define

$`R(x):X`$

$$R(x)=\underset{ϵ𝐑^+}{inf}R_ϵ(x).$$

The classical definition of dynamical system sensitive to initial conditions is related to our last definition. To say that a system is sensitive to initial conditions is equivalent to say that there is a $`\delta `$ such that $`r_\delta (x)`$ is infinitesimal for all the $`xX`$:

###### Definition 25

A dynamical system $`(X,T)`$ is said to have sensitive dependence on initial conditions if there is a $`\delta `$ such that for each $`xX`$ and every neighborhood $`U`$ of $`x`$ there is $`yU`$ and $`k𝐍`$ such that $`d(T^k(x),T^k(y))>\delta `$.

###### Proposition 26

A system has sensitive dependence on initial conditions if and only if there is a $`\delta `$ such that $`xX`$ $`r_\delta (x)`$ is infinitesimal.

The proof follows directly from the definition of $`r_\delta (x)`$.

We give some example of different behaviors of $`r(x)`$ and $`R(x)`$ in dynamical system over the interval $`[0,1].`$ The identity map $`T(x)=x`$. In this map $`n`$ $`B(n,x,ϵ)=\{y[0,1],s.t.|yx|<ϵ\}`$ then if we choose for example $`x=\frac{1}{2}`$ we have $`R(\frac{1}{2},n,ϵ)=r(\frac{1}{2},n,ϵ)=ϵ`$ i.e. the constant sequence with value $`ϵ.`$ Then $`R_ϵ(\frac{1}{2})=r_ϵ(\frac{1}{2})=[J(ϵ)]`$ where $`J(ϵ)`$ is the number in $`R^{}`$ corresponding to the constant sequence with value $`ϵ`$ and $`R(\frac{1}{2})=r(\frac{1}{2})=[J(ϵ)]=\{xR^{}s.t.xisbounded\}`$ i.e. the class containing the numbers in $`R^{}`$ corresponding to the constant sequences. The same arguments can be applied to the irrational translation on $`[0,1]`$: $`T(x)=x+t(mod1)`$ where $`t𝐐`$ obtaining the same kind of initial data sensitivity as the identity (in effect both the maps are not sensitive to initial conditions).

The one dimensional baker’s map $`T:[0,1][0,1],T(x)=2x(mod1).`$ If we choose for example $`x=0`$ , we have $`B(n,0,ϵ)=\{y[0,1],0y2^nϵ\},`$ $`R_ϵ(0)=r_ϵ(0)=[J(ϵ2^n)]`$ and $`R(0)=r(0)=[J(2^n)]`$ i.e. the class containing all the bounded multiples of the exponential infinitesimal number.

The piecewise linear map $`T:[0,1][0,1]`$

$`T(x)=\{\begin{array}{cc}\frac{\xi _{k2}\xi _{k1}}{\xi _{k1}\xi _k}(x\xi _k)+\xi _{k1}& \xi _kx<\xi _{k1}\\ \frac{xa}{1a}& ax1\end{array}`$ with $`\xi _k=\frac{a}{(k+1)^{\frac{1}{z1}}}`$ ,$`kN,z𝐑,z2`$. This is a P.L. version of the Manneville map $`T(x)=x+x^z(mod1)`$ (see fig 1), this example will be discussed more deeply in Section 4. In this example any neighborhood of the origin $`B_ϵ=`$ $`[0,ϵ)`$ is subdivided in a sequence of intervals $`A_k=(\xi _k,\xi _{k1}]`$ and if $`k>1`$ then $`T(A_k)=A_{k1}`$. Let us choose $`x=0,`$ then $`B(n,0,\xi _k)=[0,\xi _{k+n}).`$ By this we find $`r(0)=[J\left(\frac{a}{(n+k+1)^{\frac{1}{z1}}}\right)]`$ that is a class of infinitesimals corresponding to power law decreasing sequences whit exponent $`\frac{1}{z1}`$. In other words the map $`T(x)`$ has power law sensitivity to initial condition at the origin. In Section 4 we will see that while the sensitivity to initial condition at the origin is a power law, for almost all other points in $`[0,1]`$ we have a stretched exponential sensitivity. This example is important in the applications and will be studied more deeply in section 4.

### 3.2 orbit complexity

Now we define our indicator of orbit complexity. In the philosophy of the algorithmic information content we define the complexity of the orbit of $`x`$ as the asymptotic behavior of the quantity of information that is necessary to reconstruct the orbit, i.e. the asymptotic behavior (with respect to the variable $`n`$) of the length of the smallest program that can approximate $`n`$ steps of the orbit with its output (at accuracy $`ϵ`$). As before we consider the behavior when $`n`$ goes to $`\mathrm{}`$ and the accuracy parameter goes to 0 .

To interpret the output of a calculation which is a finite string as a finite sequence in $`X`$ let us consider an interpretation function $`I`$ and a total recursive surjective function.

$$𝒬:\mathrm{\Sigma }\mathrm{\Sigma }^{}$$

where $`\mathrm{\Sigma }^{}`$ is the set of finite sequences in $`\mathrm{\Sigma }`$. Now let us consider an universal Turing machine $`𝒰`$, for each program $`p`$ we define $`U(p)X^{}`$ (the set of finite sequences in $`X`$) as

$$U(p)=I(𝒬(𝒰(p)))$$

where $`I`$ is extended obviously to a map from the space $`\mathrm{\Sigma }^{}`$ to $`X^{}`$. $`U_i(p)X`$ is defined as the $`i`$th point of $`U(p)`$ . With this definition we can interpret the output of a calculation as a finite sequence in $`X`$. We remark that given $`𝒬`$ and a sequence of strings $`s_1,\mathrm{},s_n`$ it is possible by an algorithm to find a single string $`s`$ such that $`𝒬(s)=(s_1,\mathrm{},s_n)`$.

###### Definition 27

We define the algorithmic information content of the sequence $`x,T(x),\mathrm{},T^n(x)X^{}`$ at accuracy $`ϵ`$ and with respect to the interpretation $`I`$ as:

$$^I(x,n,ϵ)=\mathrm{min}\{|p|s.t.U(p)X^{n+1},\underset{0in}{max}(d(U_i(p),T^i(x)))<ϵ\}.$$

As before we consider the behavior for $`n\mathrm{}`$ and define $`^I(x,ϵ):X\times 𝐑\frac{𝐑^{}}{}`$ as:

$$^I(x,ϵ)=[J(^I(x,n,ϵ))].$$

###### Remark 28

$`^I(x,ϵ)`$ is a non increasing function with respect $`ϵ`$.

Finally, like in the definitions of initial data sensitivity we consider the behavior when $`ϵ`$ goes to $`0`$ and we define $`^I(x):X`$ as

###### Definition 29

The orbit complexity of $`x`$ with respect to the interpretation $`I`$ is defined as:

$$^I(x)=\underset{ϵ𝐑^+}{sup}^I(x,ϵ).$$

We now give some example of different behaviors of $`^I(x)`$. If $`x`$ is a periodic point it is easy to see that $`^I(x)[J(log(n))]`$. By the results of  and  it follows (see also Section 1) that if a system is compact, ergodic and has positive Kolmogorov entropy then for almost all points we have $`^I(x)=[J(n)]`$. We also remark that (when the space is compact) this is the maximum over all the possible behaviors. Indeed if $`X`$ is compact, for each $`ϵ`$ there is a finite cover made of balls with ideal center and radius $`ϵ`$, then a program that follows $`n`$ steps of the orbit of any point with the accuracy $`ϵ`$ can be simply made by listing $`n`$ centers of the cover, then, if $`X`$ is compact $`^I(x)[J(n)]`$. In section 4 we will study the complexity of the orbits of another, less trivial example.

###### Lemma 30

If $`I,J`$ are computable interpretation functions from the same computable structure: $`I,J`$ then $`^I(x)=^J(x)`$. So the orbit complexity does not depend on the choice of the interpretation $`I`$ in the computable structure $``$ and we can define $`^{}(x)=^I(x)`$ for some $`I`$.

Proof. Let us consider equivalent interpretations $`I_1,I_2`$ and

$`U=I_1(𝒬(𝒰()))`$ as in the definition of orbit complexity. Let us suppose that we have a minimal length program $`p_k`$ for the interpretation $`I_1`$ such that $`i<(k)`$ we have $`d(U_i(p_k),T^i(x))<2^{\lambda 1}`$, then there is a program $`p_k^{}`$ for $`I_2`$ approximating the orbit of $`x`$ with accuracy $`2^\lambda `$ and $`|p_k^{}|<|p_k|+c`$. The program $`p_k^{}`$ runs $`p_k`$ finding strings $`s_i`$ such that $`I_1(s_i)=U_i(p_k)`$, then using the equivalence between $`I_1`$ and $`I_2`$ it finds strings $`z_i`$ such that $`d(I_2(z_i),I_1(s_i))<2^{\lambda 1}`$ (Remark 11) by these strings it is easy to see how $`p_k^{}`$ can approximate the orbit of $`x`$ with accuracy $`2^\lambda `$. It follows that $`^{I_2}(x,2^\lambda )<^{I_1}(x,2^{\lambda +1})`$, then we have $`^{I_2}(x)^{I_1}(x)`$ and exchanging $`I_1`$ with $`I_2`$ we obtain the opposite inequality. $`\mathrm{}`$

If $`X`$ is compact then the orbit complexity does not depend not even on the computable structure.

###### Theorem 31

If $`X`$ is compact, if $`I`$ is a computable interprepretation and $`J`$ is another interpretation function (not necessarily computable) then $`^I(x)^J(x)`$.

Proof. Let $`ϵ>0`$, $`s_1,\mathrm{},s_k\mathrm{\Sigma }`$ be a finite set of strings such that $`B_ϵ(I(s_1)),\mathrm{},B_ϵ(I(s_k))`$ is a cover of $`X`$. The set of strings is finite because $`X`$ is compact. It is easy to see that there is an algorithm $`A:𝐍\times \mathrm{\Sigma }\{1,\mathrm{},k\}`$ such that $`A(i,s)=m`$ implies that the $`ith`$ point of $`I(𝒬(s))B_ϵ(I(s_m))`$. That is: the algorithm gets a string and a natural number and outputs a set $`B_ϵ(I(s_m))`$ of the cover in which the $`i`$-th point of the interpretation of the string as a sequence in $`X`$ is contained. The algorithm calculates the distance between the $`ith`$ point of $`I(𝒬(s))B_ϵ(I(s_m))`$ and $`I(s_z)`$ for all $`z\{1,\mathrm{},k\}`$ with accuracy $`\frac{ϵ}{2}`$, until it finds an $`s_m`$ such that $`d(U_i(s),I(s_m))<\frac{ϵ}{2}`$ this is possible because $`I`$ is a computable interpretation.

Now let us consider the interpretation $`J`$. Even for the interpretation $`J`$ there is a finite set $`\{s_1^{},\mathrm{}s_k^{}^{}\}`$ such that $`B_ϵ(J(s_1^{})),\mathrm{},B_ϵ(J(s_k^{}^{}))`$ is a cover of $`X`$. Now let us consider a function $`G:\{1,\mathrm{},k\}\{1,\mathrm{},k^{}\}`$ such that $`G(i)=j`$ if $`I(s_i)B_ϵ(J(s_j^{}))`$. Being a function between finite sets $`G`$ is a recursive function.

Now let $`p`$ be a minimal length program that allows to follow the orbit of $`x`$ for $`n`$ steps with accuracy $`ϵ`$ and interpretation $`I`$, that is

$$\underset{0in}{max}(d(U_i(p),T^i(x)))<ϵ,|p|=^I(x,n,ϵ).$$

For each $`i`$ by calculating $`A(i,𝒰(p))`$ we can find an $`m`$ such that $`T^i(x)B_{2ϵ}(I(s_m))`$ and then by function $`G`$ we can find a $`j`$ such that $`T^i(x)B_{3ϵ}(J(s_j))`$.

Summarizing, this procedure allows (given the program $`p`$) to calculate a sequence of strings $`s_{j_1},\mathrm{},s_{j_n}`$ such that we can follow the orbit of $`x`$ with the interpretation $`J`$, for $`n`$ steps and accuracy $`3ϵ`$. This implies that $`|p|+c^J(x,n,3ϵ)`$ where $`c`$ is the length of the above procedure and does not depend on $`n`$. From this we have $`^I(x,ϵ)^J(x,3ϵ)`$ and $`^J(x)^I(x)`$. $`\mathrm{}`$

From the above theorem we see the curious fact that in the compact case the orbit complexity reaches its maximum over all interpretations at a computable interptetation (a sort of Kolmogorov-Sinai theorem if we keep in mind the parallelism between orbit complexity and entropy) and the orbit complexity with respect to a computable structure does not depend on the choice of the computable structure ( if some computable structure exists on the space). Moreover, all this is true independently of the properties of $`T`$.

###### Corollary 32

If $`X`$ is compact, if $`I`$ and $`J`$ are computable interpretations (not necessarily from the same computable structure) then $`^I(x)=^J(x)`$.

The orbit complexity is invariant for constructive isomorphisms of dynamical systems over non compact spaces, it stated in the following propositions. As before we remark that if the space is compact constructivity is not required. We omit the proofs that are similar to the previous ones.

###### Theorem 33

If $`(X,d,T)`$, $`(Y,d^{},T^{})`$ are topological dynamical systems over metric spaces with computable structures $`,𝒥`$ and $`f`$ is onto and it is a morphism between $`(X,d,)`$ and $`(Y,d^{},𝒥)`$ such that the following diagram

$$\begin{array}{ccccc}& & f& & \\ & X& & Y& \\ \hfill T& & & & T^{}\hfill \\ & X& & Y& \\ & & f& & \end{array}$$
(2)
commutes,if $`xX`$ and $`y=f(x)Y`$ then $`^I(x)^J(y).`$

###### Theorem 34

If $`(X,d,T)`$, $`(Y,d^{},T^{})`$ are topological dynamical systems over compact metric spaces with computable structures $`,𝒥`$, if $`f`$ is an homeomorphism $`XY`$ such that the diagram 2 commutes and $`xX`$ and $`y=f(x)Y`$ then $`^I(x)=^J(y).`$

### 3.3 Complexity of points

Now we define a function $`S^I(x,ϵ):X\times 𝐑𝐑`$, the function is a measure of the complexity of the points of $`X`$. The function is non increasing and measures how much information is necessary to approximate a given point of $`X`$ with accuracy $`ϵ`$. Thus it is a function that does not depend on the dynamics. In  a definition of local entropy for points of metric spaces was based on this idea and connections between $`S`$ and the concept of dimension are shown. In particular $`S(x,ϵ)`$ is related to the local dimension of $`X`$ at $`x`$.

###### Definition 35

If $`I`$ is an interpretation function, $`𝒰`$ an universal computer we define the information contained in the point $`x`$ with respect to the accuracy $`ϵ`$ as:

$$S^I(x,ϵ)=\mathrm{min}\{|p|s.t.d(I(𝒰(p)),x)<ϵ\}.$$
(3)
The function $`S`$ depends on the interpretation $`I`$. In the following we will avoid to mention explicitly the superscript $`I`$ when it is clear from the context. The function $`S`$ depends also on the choice of $`𝒰`$. As stated in section 2.3 this function can be extended to a function $`S^{}:X\times 𝐑^{}𝐑^{}`$. Unfortunately $`S^{}`$ may be not compatible with the relation $``$, for this reason we define $`\overline{S^{}}:X\times 𝐑^{}/`$ as follows:

$$\overline{S}^{}(x,\alpha )=\underset{a\alpha }{sup}[S^{}(x,a)].$$

If $`\alpha `$ is an equivalence class then $`\overline{S}^{}(\alpha )`$ is the equivalence class of the supremum value of $`S^{}(a)`$ where $`a`$ ranges in the class $`\alpha `$. Since an equivalence class in $`R^{}/`$ does not change by the adding of a constant, then the function $`S^{}`$ does not depends more on the choice of the universal computer $`𝒰`$ in the definition of $`S`$. In the same way we define $`\underset{¯}{S^{}}:X\times 𝐑^{}/`$ as:

$$\underset{¯}{S^{}}(x,\alpha )=\underset{a\alpha }{inf}[S^{}(x,a)].$$

Finally we extend $`\overline{S^{}}`$ and $`\underset{¯}{S^{}}`$ to functions $`\overline{S},\underset{¯}{S}:X\times `$ as follows: if $`a`$ and $`a=p(a_i)`$ (the $`a_i`$ are in $`R^{}/`$ ) then we define

$$\overline{S}(x,a)=\overline{p}(\overline{S^{}}(x,a_i)),\underset{¯}{S}(x,a)=\overline{p}(\underset{¯}{S^{}}(x,a_i))$$

this is well defined because $``$ is closed by countable $`inf`$ and $`sup`$ and it does not depend on the choice of $`a_i`$ in the class $`a`$. Because $`S`$ is monotonic and then $`(a_i)(a_i^{})`$ implies $`S^{}(x,a_i)S^{}(x,a_i^{})`$.

If $`I`$ and $`J`$ are in the same computable structure $``$ then the functions $`\overline{S}^I`$ and $`\overline{S}^J`$ are equal. $`\overline{S}^I`$ does not depend on the choice of the interpretation in the computable structure.

###### Lemma 36

$`\overline{S}`$ and $`\underset{¯}{S}`$ are independent of the choice of $`I`$, in other words $`I,J`$ implies $`\overline{S}^I(x,ϵ)=\overline{S}^J(x,ϵ)`$ and $`\underset{¯}{S}^I(x,ϵ)=\underset{¯}{S}^J(x,ϵ)`$.

Proof. The proof is very similar to the proof of Lemma 30 and we omit it. $`\mathrm{}`$

We remark that if $`X=𝐑^n`$ or $`X`$ is a finite dimensional manifold then $`\overline{S}=\underset{¯}{S}`$.

###### Remark 37

If $`(X,d,)`$ is a metric space with computable structure $``$ and the lower box counting dimension 666See e.g. . of $`X`$ is finite : $`dim`$$`{}_{B}{}^{}(X)=d`$ then $`S(x,\delta )d\mathrm{log}\delta +C`$ where $`C`$ is a constant not depending on $`x`$ and $`\delta `$. Hence $`\overline{S}`$ and $`S`$ coincides for all the points of $`X.`$

The proof follows from the observation that if $`X`$ is finite dimensional, then the minimum number $`n_ϵ`$ of balls in a cover of $`X`$ with radius $`ϵ`$ is such that $`n_ϵϵ^d`$. By the computable structure we can construct the centers of a suitable cover with $`n_ϵϵ^d`$ and obtain that each point of $`X`$ is approximated with accuracy $`ϵ`$ by indicating a particular center of the cover, which costs $`log(n_ϵ)+cd\mathrm{log}(ϵ)+C`$ bits, where $`c`$ represents the length of the procedure that construct the centers of the suitable $`ϵ`$cover.

###### Lemma 38

If $`x𝐑^n`$, $`\mu `$ is the Lesbegue measure on $`𝐑^n`$, if $`ϵ0`$ then for $`\mu `$-almost all $`x𝐑^n`$, $`S^I(x,ϵ)=nlog(ϵ)+o(log(ϵ))`$ and if $`a=\underset{ϵ}{inf}[J(a_{n,ϵ})]`$ then $`\underset{¯}{S}(x,a)=\overline{S}(x,a)=\underset{ϵ}{inf}[J(log(a_{n,ϵ}))]`$.

Proof. We prove that for almost all $`x𝐑^n`$ $`\underset{ϵ0}{lim}\frac{S^{}(x,ϵ)}{nlog(ϵ)}=1`$. Theorem 12 of  states that the set

$$W^d=\{x𝐑^ns.t.\underset{i\mathrm{}}{liminf}\frac{S^{}(x,2^i)}{i}d\}$$
(4)
has Hausdorff dimension less or equal than $`d`$. This implies that if $`ϵ=2^\gamma `$ then $`\underset{ϵ0}{liminf}\frac{S^I(x,ϵ)}{nlog(ϵ)}=\underset{\gamma \mathrm{}}{liminf}\frac{S^I(x,2^\gamma )}{n\gamma }`$. If $`\underset{ϵ0}{liminf}\frac{S^I(x,ϵ)}{nlog(ϵ)}1`$ then $`xW^n`$ because $`S(x,2^{\gamma 1})S(x,2^{int(\gamma )})S(x,2^{\gamma +1})`$777$`int(r)`$ denotes the integer part of $`r`$. This implies that the set of the $`x`$ s.t. $`\underset{ϵ0}{liminf}\frac{S^I(x,ϵ)}{nlog(ϵ)}<1`$ is included in the set $`\underset{d<n}{}W^d`$ that is a $`0`$ measure set. To prove the other inequality it is enough to remark that each $`x𝐑`$ can be approximated with accuracy $`ϵ`$ by specifying its first $`int(log(ϵ))`$ digits, if $`x𝐑^n`$ we need $`nlog(ϵ)`$ digits to explicit the $`n`$ coordinates.$`\mathrm{}`$

### 3.4 Initial data sensitivity and orbit complexity

Now we are ready to state the first proposition linking orbit complexity to initial data sensitivity.

###### Proposition 39

If $`(X,T)`$ is a dynamical system on a space with a computable structure $``$, $`I`$ and $`T`$ is constructive. There are constants $`c_1`$ and $`c_2`$ such that For all $`xX,n𝐍,ϵ𝐑^+`$

$$^I(x,n,2ϵ)<S^I(x,r(x,n,ϵ))+log(n)+c_1$$
(5)
$$S^I(x,R(x,n,3ϵ))^I(n,x,ϵ)+c_2.$$
(6)
Proof of 5. We will see that there is a program $`p`$ such that $`d(U_i(p),T^i(x))<2ϵ,in`$ and $`|p|S(x,r(x,n,ϵ))+\mathrm{log}(n)+c`$. If we have a program $`p_0`$ such that $`d(I(𝒰(p_0)),x)r(x,k,ϵ)`$ then $`ikd(T^i(x),T^i(I(𝒰(p_0)))<ϵ.`$

The idea is that by constructivity if we have the string $`s_0=𝒰(p_0)`$ we can follow the orbit of $`I(s_0)`$ by an algorithm $`A(s_0,k,ϵ)`$ (see Lemma 13). The program $`p`$ will codify the following procedure:

1) run the program $`p_0`$ and compute $`s_0=𝒰(p_0)`$

2) compute $`s_i=`$ $`A(s_0,i,ϵ),1ik`$

3) compute the single string $`s`$ such that $`Q(s)=(s_0,\mathrm{},s_k).`$

The length of this program will be a constant (the above stated procedure) plus $`\mathrm{log}(k)`$ (the length of a binary representation of $`k`$) plus the length of $`p_0`$. If $`p_0`$ was supposed to be the shortest program such that $`d(I(U(p_0)),x)<r(x,k,ϵ)`$ then its length is the value of $`S(x,r(x,n,ϵ))`$ and the first part of the statement is proved.

Proof of 6. Let $`e𝐍`$ such that $`2^e<ϵ`$. If we have a program $`p`$ such that $`d(T^i(x),U_i(p_0))<ϵ`$ for $`0<i<k`$ we can find a string $`s`$ s.t. $`I(s)B(x,n,3ϵ)`$ with the following procedure:

1) By $`p_0`$ compute the number $`k`$ and the strings $`s_0,\mathrm{},s_k`$ such that $`(s_{0,\mathrm{},}s_k)=Q(𝒰(p_0))`$

2) for each $`c\mathrm{\Sigma }`$ do the following things: { compute $`A(c,i,2^e)`$ for each $`0ik`$ , if for all $`0ik`$ $`D(A(c,i,2^e),s_i,e+2)<2^e`$ then $`s=c`$ and stop the procedure. }

The procedure must stop because of the density of the image of $`I`$. At some time the step 2) will be computed with a $`c`$ such that $`I(c)B(x,n,2^{e1})`$ and this string will verify 2). On the other hand if we find a $`c`$ that stops the procedure then it is easy to see that $`I(c)B(x,n,3ϵ).`$ This will implies that $`d(x,I(c))<R(x,k,3ϵ)`$. Summarizing we have described a procedure that starting from a program $`p_0`$ outputs a string $`s`$ such that $`d(I(s),x)<R(x,k,3ϵ)`$. The code for this procedure will be a program containing $`p_0`$ and its length will be $`p_0+C`$ where $`C`$ represents the length of the code for the above procedure which does not depend on $`x`$ and $`k`$, and the statement is proved.$`\mathrm{}`$

From the previous statement we obtain a relation between the indicators of orbit complexity and sensitivity.

###### Theorem 40

If $`(X,T)`$ is a dynamical system on a space with a computable structure $``$ and $`T`$ is constructive. For all $`xX`$

$$^{}(x)max(\overline{S}^{}(x,r(x)),[J(log(n))])$$
(7)
$$\underset{¯}{S}^{}(x,R(x))^{}(x).$$
(8)
Proof. If we apply the homomorphism $`J`$ to equation 5 we obtain

$$J(^I(x,n,2ϵ))J(S^I(x,r(x,n,ϵ)))+J(log(n))$$

, then $`J(^I(x,n,2ϵ))S_{}^{}{}_{}{}^{I}(x,J(r(x,n,ϵ)))+J(log(n))`$, and considering the equivalence classes:

$$^I(x,2ϵ)max(\overline{S^{}}^I(x,r_ϵ(x)),[J(log(n))]).$$

This is true for each $`ϵ`$, then $`^I(x)max(\overline{S}^I(x,r(x))+[J(log(n))])`$. As proved before all this equivalence classes does not depend on the choice of $`I`$ and we have Equation 7. In the same way we can obtain equation 8.$`\mathrm{}`$

By Lemma 38 for almost all points in $`𝐑^n`$ the function $`S`$ is the logarithm, this, combined with proposition 39 implies the following formulas:

###### Theorem 41

If $`T:𝐑^n𝐑^n`$ is constructive on $`𝐑^n`$ with the standard computable structure, for almost all $`xX`$

$$^{}(x)max(\underset{ϵ𝐑^+}{inf}([J(log(r(x,n,ϵ))]),[J(log(n))])$$
(9)
$$\underset{ϵ𝐑^+}{inf}[J(log(R(x,n,ϵ)))](x)$$
(10)
As a corollary of Theorem 40 we can obtain the following interesting result: the set where the sensitivity to initial conditions is more than exponential in all directions has $`0`$ Hausdorff dimension.

###### Theorem 42

If $`(X,T)`$ is a dynamical system on a compact metric space with a computable structure $``$ and $`T`$ is constructive. Then the set

$$\overline{exp}=\{xXs.t.h𝐑^+R(x)<[J(2^{hn})]\}$$

has zero Hausdorff dimension.

Proof.  Let us consider a point $`x`$ such that $`R(x)<[J(2^{hn})]`$ by theorem 40 we know that $`\underset{¯}{S}^{}(x,R(x))^{}(x)`$ since $`X`$ is compact we have $`^{}(x)[J(n)]`$. Then $`\underset{¯}{S}^{}(x,R(x))[J(n)]`$. Since $`\underset{¯}{S}`$ is a non increasing function then $`\underset{¯}{S}^{}(x,[J(2^{hn})])\underset{¯}{S}^{}(x,R(x))[J(n)]`$. Then by definition $`\underset{¯}{S}^{}(x,[J(2^{hn})])=\underset{\alpha [J(2^{hn})]}{inf}[S^{}(x,\alpha )][S^{}(x,J(2^{(hϵ)n}))]`$ for some small $`ϵ`$ and then $`[S^{}(x,J(2^{(hϵ)n}))][J(n)]`$, by this, setting $`h^{}=hϵ`$ it follows that there is a bounded constant $`c_10`$ such that $`S^{}(x,J(2^{h^{}n}))c_1J(n)`$.

Let us consider the following set $`A^d=\{xX|J(\frac{S(x,2^i)}{i})d\}`$ , since for each sequence $`b_i`$ we have $`J(b_i)liminf(b_i)`$ then $`A^dW^d`$ where $`W^d`$ is the set defined in eq. 4. Since the Hausdorff dimension of $`W^d`$ is greater or equal than $`d`$ then also $`dim_H(A^d)d`$ . Now let us consider the set

$$A^{d,h^{}}=\{xX|J(\frac{S(x,2^{h^{}i})}{i})d\}$$

.

If $`xA^{d,h^{}}`$ , let us set $`k=h^{}i`$ and let us consider $`\frac{S(x,2^k)}{\frac{k}{h^{}}}`$, if $`J(\frac{S(x,2^{h^{}i})}{i})d`$ then $`\underset{k\mathrm{}}{liminf}(\frac{S(x,2^k)}{\frac{k}{h^{}}})J(\frac{S(x,2^{h^{}i})}{i})d`$ because $`\frac{S(x,2^{h^{}i})}{i}`$ is a subsequence of $`\frac{S(x,2^k)}{\frac{k}{h^{}}}`$ (Axiom 16). Then $`xW^{\frac{d}{h^{}}}.`$ This implies that if $`x\overline{exp}`$ then $`x\underset{h^{}}{}W^{\frac{d}{h^{}}}`$ which has $`0`$ Hausdorff dimension (again by  Theorem 12). $`\mathrm{}`$

## 4 Applications to the Mannevile maps.

In this section, in order to give a non trivial example of application of the theory exposed in the previous sections we present some example of weakly chaotic dynamics. We construct a class of examples of dynamical systems over the unit interval with stretched exponential sensitivity to initial conditions and information content of the orbits that increases as a power law. We precise that the maps $`T_z`$ we are going to study are not weakly chaotic in the sense of  (zero topological entropy), conversely they have positive topological entropy. In this examples however for almost all the points (for the Lesbegue measure) the dynamics are weakly chaotic (low orbit complexity, low initial data sensitivity). Then we can say that the system is weakly chaotic with respect to the Lesbegue measure.

The examples are piecewise linear version of the Manneville map $`T:[0,1][0,1]`$ defined as $`T_z(x)=x+x^z(mod1),z(1,\mathrm{})`$. The so called Manneville map comes from the theory of turbulence. It was introduced in  as an extremely simplified model of intermittent behavior in fluid dynamics, then the map was studied and applied in other areas of the physics (for example ,,).

The first study of the mathematical features of the Manneville map was done by Gaspard and Wang in . However in our opinion In their paper some steps of the proofs were difficult to understand and some others were not rigorously formalized. In the following we outline the construction done in  for the study of the complexity of the piecewise linear Manneville maps by the theory of recurrent events . Then we prove the main features of this important class of dynamical systems by the theory exposed in the previous sections. Another study of the Manneville map was done by C. Bonanno in  where the dynamics was studied also from a topological point of view. Notations: if $`(a_i),(b_j):𝐍𝐑`$ are real sequences, in the following we will write $`(a_i)\underset{¯}{}(b_j)`$ if and only if $`\frac{a_i}{b_i}`$ is bounded, we also write $`(a_i)(b_j)`$ if and only if $`\underset{i}{lim}\frac{a_i}{b_i}=1.`$

Let $`ϵ=(ϵ_k):N[0,1]`$ be a monotone sequence, such that $`\underset{k\mathrm{}}{lim}ϵ_k`$$`=0.`$ Let $`T_ϵ:[0,1]`$$`[0,1]`$ be defined by:

$`T_ϵ(x)=\{\begin{array}{cc}\frac{ϵ_{k2}ϵ_{k1}}{ϵ_{k1}ϵ_k}(xϵ_k)+ϵ_{k1}& k>0,ϵ_k<xϵ_{k1}\\ \frac{xϵ_0}{1ϵ_0}& ϵ_0<x1\end{array}`$

To each sequence $`ϵ_i`$ is then associated a piecewise linear map $`T_ϵ`$ (see fig. 1) and a dynamical system $`([0,1],T_ϵ)`$.

In order to apply the theory of recurrent events, we associate to our dynamical system $`([0,1],T_ϵ)`$ a stochastic process $`X_i`$.The process is defined on the probability space $`(\mathrm{\Omega },\mu ),`$ where $`\mathrm{\Omega }=[0,1]`$ and $`\mu `$ is the Lesbegue measure as follows. Let us consider the sets $`A_i,i𝐍`$: $`A_0=(ϵ_0,1],\mathrm{},A_i=(ϵ_i,ϵ_{i1}]`$. Let $`f:𝐑𝐍`$ be given by $`f(x)=nxA_n`$ ($`f`$ associates to each point $`x`$ the index of the set $`A_i`$ in which $`x`$ is included). The associated stochastic process is given by the random variables $`X_i:\mathrm{\Omega }𝐑`$ , given by $`X_i(\omega )=f(T_ϵ^i(\omega ))`$. As it was remarked in  the process $`X_i`$ is a Markov chain with transition matrix

$`\left(\begin{array}{ccccc}p_0& p_1& p_2& p_3& \mathrm{}\\ 1& 0& 0& 0& \mathrm{}\\ 0& 1& 0& 0& \mathrm{}\\ 0& 0& 1& 0& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\end{array}\right)`$ where $`p_i=\mu (A_i)=\mu (X_k=i|X_{k1}=0).`$

Summarizing: we constructed a family of dynamical systems (one for each infinitesimal sequence). To each one of them it is associated a Markov chain. The statistic behavior of the Markov chain can be studied by the theory of recurrent events  and will give information on the dynamics. The family $`([0,1],T_ϵ)`$ is a large family of dynamical systems with different chaotic behavior. In the following we will study the systems in which $`ϵ_i\frac{1}{i^\alpha }`$. Such dynamical systems give rise to stretched exponential initial data sensitivity and power law orbit complexity. However if $`ϵ_i`$ decreases slower than a power law ($`ϵ_i\frac{1}{log(i)}`$ e.g.) we will have a variety of other possible behaviors of orbit complexity and initial data sensitivity that will be not studied here.

Now we consider a subset of the above family of systems, which we consider as P.L. versions of the Manneville map. Let $`z(2,\mathrm{})`$, let us consider the map $`T_z`$ associated by the above construction to the sequence

$$ϵ_k=1\underset{ik}{}\frac{1}{(i+1)^{\frac{z}{z1}}}.$$

The map $`T_z`$ is then associated to a Markov chain with transition probabilities $`p_0=1ϵ_0,p_i=\frac{1}{(i+1)^{\frac{z}{z1}}}i>1`$.

The theory of recurrent events can now give us information on the dynamics of the Markov chain. Let us consider the random variable $`N_n(x)`$ that is, the number of times that the event $`A_0`$ occurs until the time $`n`$: $`N_n(x)=\mathrm{\#}\{i|X_i(x)=0\}=\mathrm{\#}\{i|T^i(x)A_0\}`$. Theorem 10 of  applied to our Markov chain says that if $`1_{ik}p_iAk^\alpha `$ then $`E(N_n)Cn^\alpha `$. Since for the Markov chain associated to $`T_z`$ we have $`1\underset{ik}{}p_i\frac{1}{z1}k^{\frac{1}{z1}}`$ then $`E(N_n)Cn^{\frac{1}{z1}}`$.

Since the function $`T_z`$ is not continuous at $`ϵ_0`$ our theory is not directly applicable to the dynamical system $`([0,1],T_z)`$. The following lemma and its proof shows how to extend our theory to discontinuous dynamical systems. A real number is constructive if it can be approximated at any accuracy by an algorithm.

###### Definition 43

A number $`z𝐑`$ is said to be constructive if there is an algorithm $`A_z(n):𝐍𝐐`$ such that $`A_z(n)=q`$ implies $`|qz|<2^n`$.

The rational numbers, the algebraic numbers are constructive, and so are all the numbers that can be explicitly used for numerical purposes, for example $`\pi `$ and $`e`$ are constructive.

###### Lemma 44

If $`z`$ is constructive. For the dynamical system $`([0,1],T_z)`$, for all $`x[0,1]`$ equation 5 and 6 holds.

proof. Let us consider the set $`X=[0,1]\{x|k𝐍,T_z^k(x)=ϵ_0\}`$. Let us consider an interpretation function $`I^{}`$ on $`X`$ as follows: if $`I`$ is defined as in equation 1 then $`I^{}:\mathrm{\Sigma }X`$ is given by $`I^{}(s)=I(s)+\pi `$. $`I^{}`$ is a computable interpretation because $`\pi `$ is constructive and its image is in $`X`$ because $`\pi `$ is transcendent. If $`z`$ is constructive then it is easy to see that $`T_z`$ is constructive on $`(X,d,)`$ where $`I^{}`$ then we can apply Proposition 39 to $`(X,T_z,)`$. On the other hand, since the inclusion $`i:X[0,1]`$ is isometric the complexity of an orbit in $`X`$ is equal to the complexity of the corresponding orbit in $`[0,1]`$: $`xX`$ $`^I^{}(([0,1],T_z),x,n,ϵ)=^I^{}((X,T_z),x,n,ϵ)`$. If conversely $`x[0,1]X`$ then $`^I^{}(([0,1],T_z),x)=[J(log(n))]`$ because the orbit of $`x`$ converges to a fixed point. Then eq. 5 and 6 holds for all points of $`[0,1]`$ for the interpretation $`I^{}`$. Now, since $`[0,1]`$ is compact (see theorem 31) we have that the orbit complexity does not depend on $`I^{}`$ and the statement is proved. $`\mathrm{}`$

Now let us give an estimation of the initial data sensitivity of the map $`T_z`$ by the behaviour of $`N_n`$. Let $`x,y[0,1],d(x,y)=\mathrm{\Delta }x(0)=ϵ_0`$. Since the derivative of $`T_z`$ exists for almost all points and it is greater than $`1`$, if $`ϵ_0`$ is small enough (e.g. is such that $`ϵ_0\frac{p_0}{4}`$) then $`d(T_z(x),T_z(y))ϵ_0`$. If $`ϵ_0`$ is small enough (e.g. $`ϵ_0`$ is such that $`in,d(T_z^i(x),T_z^i(y))\frac{p_0}{4}`$) , then $`d(T_z^n(x),T_z^n(y))=\mathrm{\Delta }x(n)ϵ_02^{cN_n}`$ where $`c`$ is a constant that depends on the derivative of $`T_z`$ in $`A_0`$ and $`A_1`$.

If $`d(x,y)=ϵ_0=ϵ2^{cN_n}`$ then $`\mathrm{\Delta }x(n)ϵ_02^{cN_n(x)}ϵ.`$ This implies that $`yB(n,x,ϵ)=\{yX:d(T^i(y),T^i(x))ϵ0in\}`$ (as defined in section 3.1) and symmetrically $`y^{}=2xyB(n,x,ϵ)`$, then $`ϵ_0=ϵ2^{cN_n(x)}R(n,ϵ,x)`$ (and then $`R(x)[J(2^{cN_n(x)})]`$).

By this we can give an estimation of the complexity of the orbits of the Manneville maps. In analogy with the results of  we are ready to state the following proposition about the asymptotic behavior of the average orbit complexity in the Manneville map.

###### Proposition 45

If $`z`$ is constructive. The average asymptotic behavior of the complexity of the orbits of $`T_z`$ is for each $`ϵ`$

$$E(^I(x,n,ϵ))\underset{¯}{}n^\alpha $$

where $`\alpha =\frac{1}{z1}.`$

Proof. Since we have $`R(n,ϵ,x)ϵ2^{cN_n(x)}`$ by proposition 39 and proposition 38 $`log(R(x,n,3ϵ))+o(log(R(x,n,3ϵ)))^I(x,n,ϵ)+c_1`$ for almost all $`x[0,1]`$, then $`^I(x,n,ϵ)cN_n(x)+o(N_n(x))+const+log(ϵ)`$ and $`E(^I(x,n,ϵ))cE(N_n(x))+E(o(N_n(x)))+const+log(ϵ)`$. But since $`E(N_n(x))n^\alpha `$ by the theory of recurrent events, we have that for all $`ϵ`$, $`n^\alpha =O(E(^I(x,n,ϵ)))`$ (that implies $`[J(E(^I(x,n,x,ϵ)))][J(n^\alpha )]`$ with our notations).

Now let us give an estimation from above of the average orbit complexity in the Manneville maps. As before we see that the number $`N_n(x)`$ will give the main part of the complexity of the orbit of $`x`$.

Let us consider an interpretation $`I`$ for the standard computable structure in $`[0,1]`$ and a minimal cover $`B_ϵ(I(s_0)),\mathrm{},B_ϵ(I(s_l))`$ of $`[0,1]`$ (i.e. a cover of $`[0,1]`$ such that each its proper subset does not cover $`[0,1]`$). The number $`l`$ of balls in this cover is then bounded by $`l\frac{1}{ϵ}`$. Now let us consider the sets $`A_i`$ defined above. We remark that if $`1_{ik}\frac{1}{(i+1)^{\frac{z}{z1}}}<ϵ`$ then $`A_kB_ϵ(I(s_0))`$. Now we remark that the symbolic dynamics of the point $`x`$ with respect to $`\{A_i\}_{i𝐍}`$ i.e. the sequence of $`A_{i_0},\mathrm{},A_{i_n}`$ such that $`T_z^n(x)A_{i_n}`$ it is determined by the recurrence times of the set $`A_0`$. The sequence $`(A_{i_n})=A_{i_0},\mathrm{},A_{i_k}`$ must be such that if $`i_n>0`$ then $`A_{i_{n+1}}=A_{i_n1}`$ and if $`i_n=0`$ then $`A_{i_{n+1}}`$ can be any one of the $`A_i`$ (see fig 1). For example a possible sequence is $`A_0,A_1,A_0,A_3,A_2,A_1,A_0,A_0,A_2,\mathrm{}`$ such a string is determined by the sequence $`P`$ of numbers representing the recurrence times of $`A_0`$, i.e. for the above example $`P=(0,1,3,0,2,\mathrm{})`$. We remark that the string $`P_n(x)=(t_1,\mathrm{},t_{N_n(x)})`$ representing the recurrence times of $`A_0`$ for $`n`$ steps of the orbit of $`x`$ contains $`N_n(x)`$ numbers. Then the binary length of $`P_n(x)`$ is about $`_{i=1}^{N_n}log(t_i)`$.

An algorithm $`A_ϵ(n,m)`$ to follow the orbit of $`x`$ with accuracy $`ϵ`$ (i.e. such that if $`nm`$ and $`A_ϵ(n,m)=b`$ then $`T_z^n(x)B_ϵ(I(s_b))`$ ) can be constructed in the following way. The algorithm contains a string $`P_m(x)`$ of the recurrence times with respect to $`A_0`$, with this string we can reconstruct the symbolic orbit of $`x`$ with respect to $`\{A_i\}_{i𝐍}`$ for $`m`$ steps, as described above. Moreover the program contains another string $`Q_m(x)`$ containing at most $`(l1)N_n(x)`$ numbers, each one is less or equal than $`l`$. The meaning of $`Q_m(x)`$ will be explained below.

The algorithm starts with a pointer to the first number of $`Q_m(x)`$. By $`P_m`$ it calculates the set $`A_{i_n}`$ such that $`T_z^n(x)A_{i_n}`$, if $`i_n`$ is such that $`1_{ji_n}\frac{1}{(j+1)^{\frac{z}{z1}}}ϵ`$ then $`A_ϵ(n,m)=0`$ because then $`T_z^n(x)B_ϵ(s_0)`$. Else the algorithm outputs the number of $`Q_m(x)`$ indicated by the pointer and then set the pointer on the next number. In other words, when $`T_z^n(x)`$ may not be in $`B_ϵ(s_0)`$ then the algorithm gets the number $`q`$ such that $`T_z^n(x)B_ϵ(s_q)`$ from the list $`Q_m(x)`$. This can not be too expensive because the point can be out of $`B_ϵ(s_0)`$ at most $`(l1)N_n(x)`$ times. The total length of the program implementing $`A_ϵ(n,m)`$ for $`m`$ steps of the orbit is then less or equal than $`_{i=1}^{N_n}log(t_i)+(l1)N_n(x)log(l)+C`$ where $`C`$ is constant with respect to $`m`$, $`l`$ depends on $`ϵ`$ but not on $`m`$.

The term $`_{i=1}^{N_n}log(t_i)`$ can be estimated as follows: we remark that while the random variables $`t_i`$ are independent and identically distributed they have no finite expectation when $`p_i\frac{1}{i^\alpha }`$, $`1<\alpha <2`$ ($`E(t_i)=ip_i`$) instead the random variable $`log(t_i)`$ has finite expectation, let us say $`E(log(t_i))=\overline{t}`$. Then $`_{i=1}^{N_n}log(t_i)=N_n(\frac{_{i=1}^{N_n}log(t_i)}{N_n})`$, by the law of large numbers we have that for each $`\delta >1`$, for almost each $`x`$, eventually with respect to $`i`$ we have $`\frac{_{i=1}^{N_n}log(t_i)}{N_n}<\delta \overline{t}`$.

This implies that for almost each $`x`$, eventually with respect to $`n`$ $`^I(x,n,ϵ)cN_n(x)\delta \overline{t}+const`$ and then $`E(^I(x,n,x,ϵ))CE(N_n(x))+const`$. But since $`E(N_n(x))n^\alpha `$ we have that for all $`ϵ`$, $`E(^I(x,n,ϵ))=O(n^\alpha )`$. $`\mathrm{}`$

The above Theorem is an estimation of the average orbit complexity of the map $`T_z`$, to show how our theory can be applied to prove rigorously the statements of , however stronger results can be proved. By  page 4592 eq. 2.9 (which follows from  theorem 7, page 106) we have that there exists a constant $`A`$ such that

$$\mu (\{N_n\frac{n^\alpha }{Ax^\alpha }\})G_\alpha (x)$$

where $`\alpha =\frac{1}{z1}`$ and $`G_\alpha `$ is the Levi stable distribution law with parameter $`\alpha `$. It follows that $`N_n(x)\underset{¯}{}Cn^\alpha `$ for almost all points in the interval. From this, by the same proof as above it follows the pointwise estimation:

###### Theorem 46

With the same notations as above, For almost all $`x[0,1]`$, $`(x,n,ϵ))\underset{¯}{}n^\alpha `$.

Similar results are obtained by  using different techniques.

## 5 Numerical experiments

We want to remark that while the information content of an orbit (as it is defined in this work) is not computable (the algorithmic information content of a string is not a computable function) there is the possibility to have an empirical estimation of the quantity of information by the use of data compression algorithms. If instead to measure the information contained in a string by its algorithmic information content we consider as ’approximate’ measure of the information content of the string the length of the string after it is compressed by a suitable coding procedure we obtain a computable notion of orbit complexity. In the positive entropy case the computable orbit complexity is a.e. equivalent to the previous one . Such a definition of computable orbit complexity allows numerical investigations about the complexity of unknown systems. Unknown systems underlying for example some given time series or experimental datas.

The existence of a computable version of the orbit complexity motivates from the applicative point of view the study of the orbit complexity itself and its relations between the other measures of the chaotic behavior of a system.

In  and  such numerical investigations are performed by directly measuring the complexity of the orbits of the Manneville map and of the logistic map at the chaos threshold. The results agree with theoretical predictions and some interesting conjecture arises.

## 6 References