format: text

text:
# Dynamical systems and computable information

## 1 Introduction

In this paper, we present some results on the connections between information theory and dynamical systems. We analyse the asymptotic behavior of the quantity of information necessary to describe an orbit of a dynamical system with a given accuracy. This analysis gives some indicators of complexity of the orbit itself.

These results have the following features and motivations:

* the complexity indicators are defined for a single orbit and can be estimated numerically; hence they can be used in simulations and in the analysis of experimental time series;
* when the system is ergodic, the orbit complexity equals the Kolmogorov-Sinai entropy almost surely; thus our method provides a new characterization of the entropy and an alternative way to compute it;
* if the entropy is 0, the asymptotic behavior of the information provides a measure of the unpredictability of the system and allows to classify various kind of weak chaos. Actually this is the main motivation of this work.

In recent papers (,,,) tools from algorithmic information theory have been used to define and study some indicators of orbit complexity. These indicators are invariant up to topological conjugacy. In same special cases the theory allows to calculate them explicitly and gives a characterization of various kinds of 0-entropy dynamics. Moreover it has been proved that there are quantitative relations between these indicators and the initial condition sensitivity of the system. This fact shows that information is strongly related to chaos even in the 0-entropy case. The approach of  makes use of the Algorithmic Information Content (Kolmogorov complexity) as measure of the information. Unfortunately the Algorithmic Information Content (AIC) is not a computable function (see section 2.3) and the related complexity indicators cannot be used in computer simulations nor in the analysis of experimental time series.

The aim of this paper is to overcome these difficulties defining orbit complexity indicators which are suitable for computer experiments. The main idea consists in replacing the AIC by a Computable Information Content (CIC) which is measured using suitable compression algorithms. We prove theorems which support the use of this method in the experimental setting. In particular, we prove that our method gives the same asymptotic behaviour of the quantity of information when it is measured with AIC in two important cases: the positive entropy case and the Manneville map which is an paradigmatic example of intermittent dynamical systems.

Moreover, even when it is not possible to give theoretical estimates, we have performed some numerical experiments to investigate how the method works in practice.

The paper is organised as follows.

In Section 2, we recall the main notions of information content for finite strings and introduce the notion of Computable Information Content whose definition is based on Compression Algorithms.

In Section 3, we consider infinite strings and we define their complexity as the time average information content; we prove that the complexity of almost every string generated by an ergodic information source equals the Shannon entropy of the source itself.

In Section 4, we consider dynamical systems and, via the symbolic dynamics method, we apply the results of the previous sections. In particolar, we prove that the complexity of almost every orbit equals the Kolmogorov-Sinai entropy, provided that the system is ergodic.

In Section 5, we consider the 0-entropy case (weak chaos) and we introduce some indicators which are able to detect different kinds of weakly chaotic dynamics.

In Section 6, we analyse two compression algoritms (LZ77 and CAStoRe) and we prove some theorem reltive to them which provide a bridge between the abstract theory and concrete computetions. In particolar we prove that in the case of the Manneville map the CIC (based on LZ77) provides the same asymptotic beheaviour than the AIC.

In the final Section (Section 7), we show the results of some numerical experiment. In the case in which the theory is able to estimate the various invariants, our empirical results agree with the theoretical ones. In the other cases, we just show how our method can be applied and we obtain also an empirical result which, as far as we know, does not have any theoretical explanation (Casati-Prosen map, § 7.4).

## 2 Entropy, information and complexity of finite strings

The intuitive meaning of quantity of information $`I(s)`$ contained in $`s`$ is the following one:

$`I(s)`$ is the length of the smallest binary message from which you can reconstruct $`s`$.

Thus, formally

$$I:𝒜^{}$$

$`I`$ is a function from the set of finite strings on a finite alphabet $`𝒜`$ which takes values in the set of natural numbers. There are different notions of information and some of them will be discussed here. The first one is due to Shannon.

In his pioneering work, Shannon defined the quantity of information as a statistical notion using the tools of probability theory. Thus in Shannon framework, the quantity of information which is contained in a string depends on its context (). For example the string $`{}_{}{}^{}pane^{}`$ contains a certain information when it is considered as a string coming from a given language. For example this word contains a certain amount of information in English; the same string $`{}_{}{}^{}pane^{}`$ contains much less Shannon information when it is considered as a string coming from the Italian language because it is much more common (in fact it means ”bread”). Roughly speaking, the Shannon information of a string $`s`$ is given by

$$I(s)=\mathrm{log}_2\frac{1}{p(s)}.$$
(1)
where $`p(s)`$ denotes the probability of $`s`$ in a given context. The logarithm is taken in base two so that the information can be measured in binary digits (bits).222 From now on, we will use the symbol ”$`\mathrm{log}\mathrm{"}`$ just for the base 2 logarithm ”$`\mathrm{log}_2\mathrm{"}`$ and we will denote the natural logarithm by ”$`\mathrm{ln}\mathrm{"}.`$

If in a language the occurrences of the letters are independent of each other, the information carried by each letter is given by

$$I(a_i)=\mathrm{log}\frac{1}{p_i}.$$

where $`p_i`$ is the probability of the letter $`a_i.`$ Then the average information of each letter is given by

$$h=\underset{i}{}p_i\mathrm{log}\frac{1}{p_i}.$$
(2)
Shannon called the quantity $`h`$ entropy for its formal similarity with Boltzmann’s entropy.

We are interested in giving a definition of quantity of information of a single string independent of the context and of any probability measure. Of course we will require this definition to be strictly related to the Shannon entropy when we equip the space of all the strings with a suitable probability measure.

In order to be more precise it is necessary to give some notations and definitions.

Let us consider a finite alphabet $`𝒜`$ and the set $`𝒜^{}`$ of finite strings on $`𝒜`$, that is $`𝒜^{}=_{n=1}^{\mathrm{}}𝒜^n`$.

Now let

$$F:𝒜^{}\{0,1\}^{}$$

be an injective function, and set

$`I_F(s)`$ $`=`$ $`\left|F(s)\right|`$
$`K_F(s)`$ $`=`$ $`{\displaystyle \frac{\left|F(s)\right|}{\left|s\right|}}`$
where $`\left|s\right|`$ is the length of the string $`s.`$

Let us consider the usual shift map $`\sigma :𝒜^{}𝒜^{}`$ defined by

$$\left(\sigma (s)\right)_i=s_{i+1}.$$

For a probability measure $`\mu `$ on $`𝒜^{}`$, which is invariant with respect to the shift, we denote by $`h(\mu )`$ the well-known Shannon entropy of the measure.

Given a string $`\omega 𝒜^{}`$, we will denote by $`\omega ^n𝒜^n`$ the string which consists of the first $`n`$ digits of $`\omega .`$

Now we can give the following definition of information and complexity

###### Definition 1 (Information measure).

If for any ergodic measure $`\mu `$ on $`𝒜^{}`$ we have that for $`\mu `$-almost every $`\omega 𝒜^{}`$

$$\underset{n+\mathrm{}}{lim\; sup}K_F(\omega ^n)=h(\mu ),$$
(3)
then,

* $`F`$ is called *ideal coding*
* $`I_F(s)`$ is called *information content* of $`s`$ (with respect to $`F`$)
* $`K_F(s)`$ is called *complexity* (or compression ratio) of $`s`$ (with respect to $`F`$).

Later we will see that ideal codings exist; by condition (3) they are asymptotically equivalent to each other.

This definition is given without assuming recursivity for $`F`$. Later on, when we consider $`F`$ as a coding procedure, we will mean that $`F`$ is a recursive function.

In the following we will also see that choosing $`F`$ in a suitable way, it is possible to investigate interesting properties of dynamical systems with null Kolmogorov-Sinai entropy.

### 2.1 Empirical entropy

The empirical entropy is a quantity that can be thought to be in the middle between Shannon entropy and the pointwise definition of complexity. The empirical entropy of a given string is a sequence of numbers $`\widehat{H}_l`$ giving statistical measures of the average information content of the digits of the string $`s`$.

Let $`s`$ be a finite string of length $`n`$. We now define $`\widehat{H}_l(s)`$, $`l1`$, the $`l^{th}`$ empirical entropy of $`s`$. We first introduce the empirical frequencies of a word in the string $`s`$: let us consider $`w𝒜^l`$, a string on the alphabet $`𝒜`$ with length $`l`$; let $`s^{(m_1,m_2)}𝒜^{m_2m_1}`$ be the string containing the segment of $`s`$ starting from the $`m_1`$-th digit up to the $`m_2`$-th digit; let

$$\delta (s^{(i+1,i+l)},w)=\{\begin{array}{cc}1& ifs^{(i+1,i+l)}=w\\ 0& otherwise\end{array}(0inl).$$

The relative frequency of $`w`$ (the number of occurrences of the word $`w`$ divided by the total number of $`l`$-digit sub words) in $`s`$ is then

$$P(s,w)=\frac{1}{nl+1}\underset{i=0}{\overset{nl}{}}\delta (s^{(i+1,i+l)},w).$$

This can be interpreted as the “empirical” probability of $`w`$ relative to the string $`s`$. Then the $`l`$-empirical entropy is defined by

$$\widehat{H}_l(s)=\frac{1}{l}\underset{wA^l}{}P(s,w)\mathrm{log}P(s,w).$$
(4)
The quantity $`l\widehat{H}_l(s)`$ is a statistical measure of the average information content of the $`l`$digit long substrings of $`s`$.

### 2.2 Computable Information Content

Let us suppose to have some recursive lossless (reversible) coding procedure $`Z:𝒜^{}\{0,1\}^{}`$ (for example, the data compression algorithms that are in any personal computer). Since the coded string contains all the information that is necessary to reconstruct the original string, we can consider the length of the coded string as an approximate measure of the quantity of information that is contained in the original string.

If $`Z`$ is an ideal coding (according to defintion 1 then, as before, the information content of $`s`$ with respect to $`Z`$ is defined as $`I_Z(s)=|Z(s)|.`$

Of course not all the coding procedures are equivalent and give the same performances, so some care is necessary in the definition of information content. For this reason we introduce the notion of *optimality* of an algorithm $`Z`$, defined by comparing its compression ratio with the empirical entropy.

An algorithm $`Z`$ is considered optimal if its compression ratio $`|Z(s)|/|s|`$ is asymptotically less than or equal to $`\widehat{H}_k(s)`$ for each $`k`$.

###### Definition 2.

(Optimality) A reversible coding algorithm $`Z`$ is optimal if $`k𝐍`$ there is a function $`f_k`$, with $`f_k(n)=o(n)`$, such that for all finite strings $`s`$

$$\frac{|Z(s)|}{|s|}\widehat{H}_k(s)+\frac{f_k(|s|)}{|s|}.$$

Many data compression algorithms that are used in applications are proved to be optimal.

###### Remark 3.

The universal coding algorithms $`LZ77`$ and $`LZ78`$ (,) satisfy Definition 2. For the proof see .

Using the definition above, we are able to define the Computable Information Content of a string:

###### Definition 4.

The Computable Information Content of a string $`s`$ is an information measure (in the sense of Def. 1) where the ideal coding $`F`$ is an optimal compression algorithm.

The notion of optimality is not enough if we ask a coding algorithm to be able to reproduce the rate of convergence of the sequence $`\widehat{H}_k(s)`$ as $`|s|\mathrm{}`$ for strings generated by weakly chaotic dynamical systems, for which $`lim_{|s|\mathrm{}}\widehat{H}_k(s)=0`$. Indeed, if in the positive entropy systems optimality implies that asymptotically $`\frac{|Z(s)|}{|s|}`$ is equivalent to $`\widehat{H}_k(s)`$, in the weakly chaotic systems it may happen that the asymptotic behavior dominant in the right hand side of equation (2) is that of the function $`\frac{f_k(|s|)}{|s|}`$.

For example let us consider the string $`0^n1`$ and the $`LZ78`$ algorithm, then $`\widehat{H}_k(0^n1)`$ goes like $`log(n)/n`$ while $`LZ78(0^n1)/n`$ goes like $`\frac{n^{1/2}log(n)}{n}`$ (see also ). This implies that optimality is not sufficient to have a coding algorithm able to characterize $`0`$entropy strings according to the rate of convergence of their entropy to $`0`$. For this aim we need an algorithm having the same asymptotic behavior of the empirical entropy. In this way even in the 0-entropy case our algorithm will provide a meaningful measure of the information. The following definition (from ) is an approach to define optimality of a compression algorithm for the 0-entropy case.

###### Definition 5 (Asymptotic Optimality).

A compression algorithm $`Z`$ is called *asymptotically optimal* with respect to $`\widehat{H}_k`$ if it is optimal and there is a function $`g_k`$ with $`g_k(n)=o(n)`$ and $`\lambda >0`$ such that $`s`$ with $`\widehat{H}_k(s)0`$

$$|Z(s)|\lambda |s|\widehat{H}_k(s)+g_k(|Z(s)|).$$

It is not trivial to construct an asymptotically optimal algorithm. For instance the well known Lempel-Ziv compression algorithms are not asymptotically optimal. $`LZ78`$ is not asymptotically optimal even with respect to $`\widehat{H}_1`$ (). In  some examples are described of algorithms (LZ78 with RLE and LZ77) which are asymptotically optimal with respect to $`\widehat{H}_1`$. But these examples are not asymptotically optimal for each $`\widehat{H}_k`$ with $`k2`$. The asymptotic optimality of LZ77 with respect to $`\widehat{H}_1`$ (Theorem 31) however is enough to prove (see Section 6.2, Theorem 34) that LZ77 can estimate correctly the information coming from an important example of weak chaos: the Manneville map.

The set of asymptotically optimal compression algorithms with respect to each $`\widehat{H}_k`$ is not empty. In  an example is given of a compression algorithm that is asymptotically optimal for each $`\widehat{H}_k`$. The algorithm is similar to the Kolmogorov frequency coding algorithm which is also used in . This compression algorithm is not of practical use because of its computational complexity.

To our knowledge the problem of finding a fast asymptotically optimal compression algorithm is still open.

### 2.3 Algorithmic Information Content

One of the most important information function is the Algorithmic Information Content ($`AIC`$). In order to define it, it is necessary to define the notion of partial recursive function. We limit ourselves to give an intuitive idea which is very close to the formal definition. We can consider a partial recursive function as a computer $`C`$ which takes a program $`P`$ (namely a binary string) as an input, performs some computations and gives a string $`s=C(P)`$, written in the given alphabet $`𝒜`$, as an output. The $`AIC`$ of a string $`s`$ is defined as the shortest binary program $`P`$ which gives $`s`$ as its output, namely

$$AIC(s,C)=\mathrm{min}\{|P|:C(P)=s\}$$

We require that our computer is a universal computing machine. Roughly speaking, a computing machine is called *universal* if it can simulate any other machine. In particular every real computer is a universal computing machine, provided that we assume that it has virtually infinite memory. For a precise definition see e.g.  or . We have the following theorem due to Kolmogorov (,).

###### Theorem 6.

If $`C`$ and $`C^{}`$ are universal computing machines then

$$\left|AIC(s,C)AIC(s,C^{})\right|K(C,C^{})$$

where $`K(C,C^{})`$ is a constant which depends only on $`C`$ and $`C^{}`$ but not on $`s`$.

This theorem implies that the information content $`AIC`$ of $`s`$ with respect to $`C`$ depends only on $`s`$ up to a fixed constant, then its asymptotic behavior does not depend on the choice of $`C`$. For this reason from now on we will write $`AIC(s)`$ instead of $`AIC(s,C).`$ The shortest program which gives a string as its output is a sort of encoding of the string. The information which is necessary to reconstruct the string is contained in the program.

We have the following result (for a proof see for example  Lemma 6) :

###### Theorem 7.

Let

$$Z_C:𝒜^{}\{0,1\}^{}$$

be the function which associates to a string $`s`$ the shortest program whose output is $`s`$ itself333It two programs of the same length produce the same string, we choose the program which comes first in lexicographic order. (namely, $`AIC(s)=I_{Z_C}(s)`$). If $`Z`$ is any reversible coding, there exists a constant $`M`$ which depends only on $`C`$ such that

$$\left|Z_C\left(s\right)\right|\left|Z\left(s\right)\right|+M$$
(5)
The inequality (5) says that $`Z_C`$in some sense is optimal. Unfortunately this coding procedure cannot be performed by any algorithm (Chaitin Theorem)444Actually, the Chaitin theorem states a weaker statement: a procedure (computer program) which states that a string $`\sigma `$ of length $`n`$ can be produced by a program shorter than $`n,`$ must be longer than $`n.`$. This is a very deep statement and, in some sense, it is equivalent to the Turing halting problem or to the Gödel incompleteness theorem. Then the Algorithmic Information Content is not computable by any algorithm.

This fact has very deep consequences for our discussion as we will see later. For the moment we can say that the $`AIC`$ cannot be used as a reasonable physical quantity since it cannot be measured, however it is very useful in proving general theorems.

## 3 Information sources

### 3.1 Infinite strings and complexity

A symbolic dynamical system is given by $`(\mathrm{\Omega },𝒞,\mu ,\sigma )`$. The space $`\mathrm{\Omega }`$ is the space $`𝒜^{}`$ of the infinite sequences $`\omega =(\omega _i)_i`$ of symbols in $`𝒜`$. $`𝒞`$ is the $`\sigma `$-algebra generated by the cylinders555We remark that $`𝒞`$ corresponds to the Borel $`\sigma `$-algebra when $`\mathrm{\Omega }`$ is equipped with the product topology, that is the topology induced by the metric $`d(\omega ,\overline{\omega })=_i\frac{\delta (\omega _i,\overline{\omega }_i)}{2^i}`$, where $`\delta (,)`$ is the Kronecker delta.,

$$C(\omega ^{(k,n)})=\{\overline{\omega }\mathrm{\Omega }:\overline{\omega }_i=\omega _iforkin1\},$$

where $`\omega ^{(k,n)}=(\omega _i)_{kin1}=(\omega _k,\omega _{k+1},\mathrm{},\omega _{n1})`$, the map $`\sigma `$ is the shift map

$$\sigma ((\omega _i)_i)=(\omega _{i+1})_i$$

and $`\mu `$ is a $`\sigma `$-invariant probability measure on $`\mathrm{\Omega }`$. A symbolic dynamical system can be also viewed as an information source. For the purposes of this work the two notions can be considered equivalent.

We give now different measures of complexity for infinite strings generated by the symbolic dynamical system according to Definition 1, using the different information measures defined above. However each definition of complexity of an infinite string $`\omega `$ can be thought of as a measure of the average quantity of information which is contained in a single digit of $`\omega `$.

###### Definition 8 (Complexity of infinite strings).

If $`\omega \mathrm{\Omega }`$, $`Z:𝒜^{}\{0,1\}^{}`$ is a reversible universal coding procedure we define the computable complexity of $`\omega `$ with respect to $`Z`$ as

$$K_Z(\omega )=\underset{n\mathrm{}}{limsup}K_Z(\omega ^n),$$

where $`\omega ^n=\omega ^{(0,n)}`$. In the same way, using the $`AIC`$, we define

$$K(\omega )=\underset{n\mathrm{}}{limsup}\frac{AIC(\omega ^n)}{n}.$$

We also define the quantity $`\widehat{H}(\omega )`$. If $`\omega `$ is an infinite string, $`\widehat{H}(\omega )`$ is a sort of Shannon entropy of the single string.

###### Definition 9.

By the definition of empirical entropy of finite strings we define:

$$\widehat{H}_l(\omega )=\underset{n\mathrm{}}{limsup}\widehat{H}_l(\omega ^n)$$

and

$$\widehat{H}(\omega )=\underset{l\mathrm{}}{lim}\widehat{H}_l(\omega ).$$

The existence of this limit is proved in . The following proposition is a direct consequence of ergodicity (for the proof see again ).

###### Proposition 10.

If $`(\mathrm{\Omega },\mu ,\sigma )`$ is ergodic then $`\widehat{H}(\omega )=h_\mu (\sigma )`$ (where $`h_\mu `$ is the Kolmogorov-Sinai entropy of $`\sigma `$) for $`\mu `$-almost each $`\omega `$.

Moreover from the definition of optimality it directly follows that:

###### Remark 11.

If $`Z`$ is optimal then for each $`\omega `$ and for all $`l`$

$$K_Z(\omega )\widehat{H}_l(\omega ),$$

so that

$$K_Z(\omega )\widehat{H}(\omega ).$$

###### Remark 12.

As it is intuitive, the compression ratio of $`Z`$ cannot be less than the average information per digit as it is measured by the algorithmic information content (Theorem 7), thus for all $`\omega `$, we have

$$K_Z(\omega )K(\omega ).$$

This remark and the following Lemma are useful for the proof of the next theorem

###### Lemma 13 (Brudno ).

If $`\mu `$ is ergodic then $`K(\omega )=h_\mu (\sigma )`$ for almost each $`\omega `$.

Then we have the following

###### Theorem 14.

If $`(\mathrm{\Omega },\mu ,\sigma )`$ is a symbolic dynamical system, $`Z`$ is optimal and $`\mu `$ is ergodic, then for $`\mu `$-almost each $`\omega `$

$$K_Z(\omega )=\widehat{H}(\omega )=K(\omega )=h_\mu (\sigma ),$$

in particular optimality implies that the algorithm is an ideal coding and $`I_Z`$ and $`AIC`$ are information measures (see Definition 1).

###### Proof.

$`\widehat{H}(\omega )=K(\omega )=h_\mu (\sigma )`$ for almost each $`\omega `$ using Proposition 10 and Brudno’s Lemma above. Moreover we have that $`K_Z(\omega )K(\omega )`$ (Remark 12) and then $`K_Z(\omega )h_\mu (\sigma )`$ for $`\mu `$-almost each $`\omega `$.

On the other hand, $`K_Z(\omega )\widehat{H}(\omega )`$ (Remark 11) and then $`K_Z(\omega )=h_\mu (\sigma )`$ for almost each $`\omega `$. ∎

This theorem shows that all the various information measures we have defined in section 2 agrees when we study the long time asymptotical behavior of the information necessary to describe a generic orbit of a positive entropy source.

If the measure $`\mu `$ is not ergodic we can replace the a.e. above result with an average result: the average complexity is equal to the entropy.

###### Theorem 15.

Let $`(\mathrm{\Omega },𝒞,\sigma )`$ be a symbolic dynamical system, with a $`\sigma `$-invariant probability measure $`\mu `$. Then if $`Z`$ is optimal,

$$h_\mu (\sigma )=_\mathrm{\Omega }K_Z(\omega )𝑑\mu =_\mathrm{\Omega }\widehat{H}(\omega )𝑑\mu =_\mathrm{\Omega }K(\omega )𝑑\mu .$$

###### Proof.

First of all, we show that all the quantities to be integrated are actually measurable. We show how to prove measurability for $`K(\omega )`$. The argument applies unchanged to the others (one more limit has to be considered for $`\widehat{H}`$). This argument is due to Brudno ().

For any $`t`$, let $`T=\{\omega \mathrm{\Omega }/K(\omega )<t\}`$. The set $`T`$ can be written as

$$T=\underset{k=1}{\overset{\mathrm{}}{}}\underset{N=1}{\overset{\mathrm{}}{}}\underset{n>N}{}\{\omega /AIC(\omega ^n)<n(t1/k)\},$$

and since all the sets in curly brackets are finite union of cylinders, measurability of the set $`T`$ and of $`K(\omega )`$ follows from classical theorems of measure theory.

To obtain the thesis of the theorem, we use the ergodic decomposition theorem and its application to Kolmogorov-Sinai entropy $`h_\mu (\sigma )`$ (see Katok-Hasselblatt, chapter 4, ). Let $`(\mathrm{\Omega }_j,𝒞_j,\mu _j)_{jJ}`$ be an ergodic decomposition of $`(\mathrm{\Omega },𝒞,\sigma )`$, that is $`\mathrm{\Omega }_j`$ are invariant subsets of $`\mathrm{\Omega }`$, $`\mu _j`$ are ergodic measures with support on $`\mathrm{\Omega }_j`$, and $`J`$ is a Lebesgue space with probability measure $`P`$. Then we have that

$$_\mathrm{\Omega }K(\omega )𝑑\mu =_J\left(_{\mathrm{\Omega }_j}K(\omega )𝑑\mu _j\right)𝑑P=_Jh_{\mu _j}(\sigma )𝑑P=h_\mu (\sigma ).$$

The first and last equalities come from the ergodic decomposition theorem, and the second one from Theorem 14. The same argument applies to $`K_Z(\omega )`$, $`\widehat{H}(\omega )`$. ∎

## 4 Dynamical systems

In this Section we apply the features of coding algorithms and the results of the previous section to define a notion of complexity for orbits of dynamical systems and prove some relations with the Kolmogorov-Sinai entropy.

The relations we can prove will be useful as a theoretical support for the interpretation of the experimental and numerical results. The results which we will explain in this section are meaningful in the positive entropy case. The null entropy cases are harder to deal with, and we present some results in the next section.

### 4.1 Dynamical systems and partitions

Now we consider a dynamical system $`(X,\mu ,T)`$, where $`X`$ is a compact metric space, $`T`$ is a continuous map $`T:XX`$ and $`\mu `$ is a Borel probability measure on $`X`$ invariant for $`T`$. If $`\alpha =\{A_1,\mathrm{},A_n\}`$ is a measurable partition of $`X`$ (a partition of $`X`$ where the sets are measurable) then we can associate to $`(X,\mu ,T)`$ a symbolic dynamical system $`(\mathrm{\Omega }_\alpha ,\mu _\alpha )`$ ( called a symbolic model of $`(X,T)`$). By this association many results about symbolic dynamical systems will be translated to dynamical systems over metric spaces where the choice of a partition has been made.

The set $`\mathrm{\Omega }_\alpha `$ is a subset of $`\{1,\mathrm{},n\}^{}`$ (the space of infinite strings made of symbols from the alphabet $`\{1,\mathrm{},n\}`$). To a point $`xX`$ it is associated a string $`\omega =(\omega _i)_i=\phi _\alpha (x)`$ defined as

$$\phi _\alpha (x)=\omega j,T^j(x)A_{\omega _j}.$$

Since $`\alpha `$ is a partition the set $`\phi _\alpha (x)`$ will contain only one element and defines a function associating an infinite string to a point $`xX`$. The measure $`\mu `$ on $`X`$ induces a measure $`\mu _\alpha `$ on the associated symbolic dynamical system. The measure is first defined on the cylinders666 We recall that $`\omega ^{(k,n)}=(\omega _i)_{kin}=(\omega _k,\omega _{k+1},\mathrm{},\omega _n)`$.

$$C(\omega ^{(k,n)})=\{\overline{\omega }\mathrm{\Omega }_\alpha :\overline{\omega }_i=\omega _iforkin1\}$$

by

$$\mu _\alpha (C(\omega ^{(k,n)}))=\mu (_k^{n1}T^i(A_{\omega _i}))$$

and then extended by the classical Kolmogorov theorem about product measures to a measure $`\mu _\alpha `$ on $`\mathrm{\Omega }_\alpha `$. Moreover if $`(X,\mu ,T)`$ is ergodic then $`(\mathrm{\Omega }_\alpha ,\mu _\alpha ,\sigma )`$ is ergodic and $`h_\mu (T,\alpha )`$ (the Kolmogorov-Sinai entropy relative to the partition $`\alpha `$) on $`X`$ equals $`h_{\mu _\alpha }(\sigma )`$ on $`\mathrm{\Omega }_\alpha `$ (see also ).

We now define the complexity of an orbit with respect to a partition. The above considerations will allow us to apply the results on symbolic dynamical systems to general dynamical systems with a partition.

###### Definition 16.

Let $`\omega =\phi _\alpha (x)`$ for a given partition $`\alpha `$. We define the complexity of the orbit of a point $`xX`$, with respect to the partition $`\alpha `$, as

$$AIC(x,\alpha ,n)=AIC(\omega ^n)$$

$$K(x,\alpha )=K(\omega ),$$

where the information is measured by the AIC. We also define

$$I_Z(x,\alpha ,n)=I_Z(\omega ^n)$$

$$K_Z(x,\alpha )=K_Z(\omega ),$$

where the information is measured by $`Z`$. Also the definition of empirical entropy can be extended for $`(x,\alpha )`$, defining

$$\widehat{H}(x,\alpha )=\widehat{H}(\omega ).$$

###### Theorem 17.

If $`Z`$ is an optimal coding, and $`(X,\mu ,T)`$ is an ergodic dynamical system and $`\alpha `$ is a measurable partition of $`X`$, then for $`\mu `$-almost all $`x`$

$$K_Z(x,\alpha )=h_\mu (T,\alpha )$$

where $`h_\mu (T,\alpha )`$ is the Kolmogorov entropy of $`(X,\mu ,T)`$ with respect to the measurable partition $`\alpha `$.

The proof of the above Theorem follows easily from the following lemmas.

###### Lemma 18.

If $`(X,T,\mu )`$ is ergodic, then for almost each point $`xX`$, $`K(x,\alpha )=h_\mu (T,\alpha )`$.

This Lemma was already proved by Brudno. See  Lemma 2.6 page 137.

###### Lemma 19.

If $`(X,T,\mu )`$ is ergodic, for almost each point $`xX`$

$$\widehat{H}(x,\alpha )=h_\mu (T,\alpha ).$$

###### Proof.

In the associated symbolic system $`h_\mu (T,\alpha )=h_{\mu _\alpha }(\sigma )`$. Moreover, for almost each $`\omega \mathrm{\Omega }_\alpha `$, it holds $`\widehat{H}(x,\alpha )=\widehat{H}(\omega )=h_{\mu _\alpha }(\sigma )`$ where $`x=\phi _{\alpha }^{}{}_{}{}^{1}(\omega )`$ (Prop. 10). If we consider $`Q_{\mathrm{\Omega }_\alpha }:=\{\omega \mathrm{\Omega }_\alpha :\widehat{H}(\omega )=h_{\mu _\alpha }(\sigma )\}`$ and $`Q:=\phi _\alpha ^1(Q_{\mathrm{\Omega }_\alpha })`$ we have

$$xQ\widehat{H}(x,\alpha )=\widehat{H}(\phi _\alpha (x))=h_{\mu _\alpha }(\sigma )=h_\mu (T,\alpha ).$$

According to the way in which the measure $`\mu _\alpha `$ is constructed we have $`\mu (Q)=\mu _\alpha (Q_{\mathrm{\Omega }_\alpha })=1`$. ∎

Proof of Theorem 17. The proof of Theorem 17 follows as before from the remark that $`K(x,\alpha )K_Z(x,\alpha )\widehat{H}(x,\alpha )`$ (Remarks 11 and 12) and Lemmata 18 and 19.$`\mathrm{}`$

As before we show the corresponding result in the non ergodic case

###### Theorem 20.

If for the dynamical system $`(X,T,\mu )`$ the measure $`\mu `$ is only $`T`$-invariant, then, if $`Z`$ is an optimal compression algorithm, for any measurable partition $`\alpha `$ it holds

$$h_\mu (T,\alpha )=_XK_Z(x,\alpha )𝑑\mu =_X\widehat{H}(x,\alpha )𝑑\mu =_XK(x,\alpha )𝑑\mu .$$

###### Proof.

The proof follows that of Theorem 15, using the definition of the complexity of infinite orbits of a dynamical system through the complexity of the associated infinite symbolic orbit, and previous lemmata. The measurability of the partition $`\alpha `$ is essential to obtain the measurability of the function $`\phi _\alpha :X\mathrm{\Omega }_\alpha `$. ∎

###### Corollary 21.

Under the assumption of the previous Theorem 20, if moreover $`\alpha `$ is a generating partition

$$h_\mu (T)=_XK_Z(x,\alpha )𝑑\mu =_X\widehat{H}(x,\alpha )𝑑\mu =_XK(x,\alpha )𝑑\mu .$$

Remarks. This theorem shows that all the various information measures we have defined in section 2 agrees when we study the long time asymptotical behavior of the information necessary to describe a generic orbit of a positive entropy system. Theorem 20 shows that if a system has an invariant measure, its entropy with respect to a given partition can be found by averaging the complexity of its orbits over the invariant measure. Then, the entropy may be alternatively defined as the average orbit complexity. However if we fix a single point, its orbit complexity is not yet well defined because it depends on the choice of a partition. It is not possible to get rid of this dependence by taking the supremum over all partitions (as in the construction of Kolmogorov-Sinai entropy), because this supremum goes to infinity for each orbit that is not eventually periodic (see  Assertion 2.8).

We sketch how this difficulty may be overcome in two ways:

1) by considering open covers instead of partitions as in ,  and in . We recall that since the sets in an open cover can have non empty intersection, a step of the orbit of $`x`$ can be contained at the same time in more than one open set of the cover. This implies that an orbit may have an infinite family of possible symbolic codings, among which we choose the “simplest one”. Then we can define the complexity of the orbit of a point as the supremum of the complexities obtained with respect to all possible open covers. This definition has the very nice property to be invariant up to topological equivalence of dynamical systems. This definition of orbit complexity equals the entropy for almost each point of a compact ergodic system.

2) by considering only a particular class of partitions and define the orbit complexity of a point as the supremum of the orbit complexity over that class. This can be easily done if the space is $`R^n`$ by considering partitions generated by intersections of half spaces with rational coordinates (polyedric partitions). By the following Lemma 22 it easily follows that the corresponding notion of orbit complexity equals the entropy for almost each point of a compact ergodic system.

Let $`\beta _i`$ be a family of measurable partitions such that $`\underset{i\mathrm{}}{lim}diam(\beta _i)=0`$. If we consider $`\underset{i\mathrm{}}{limsup}K_Z(x,\beta _i)`$ we have the following

###### Lemma 22.

If $`(X,\mu ,T)`$ is compact and ergodic, $`Z`$ is optimal, then for $`\mu `$-almost all points $`xX`$, $`\underset{i\mathrm{}}{lim\; sup}K_Z(x,\beta _i)=\underset{i\mathrm{}}{limsup}K(x,\beta _i)=h_\mu (T)`$.

###### Proof.

The points for which $`K_Z(x,\beta _i)h_\mu (T,\beta _i)`$ are a set of null measure for each $`i`$ (Theorem 17). When excluding all these points, we exclude (for each $`i`$) a zero-measure set. For all the other points we have $`K_Z(x,\beta _i)=h_\mu (T,\beta _i)`$ and then $`\underset{i\mathrm{}}{limsup}K_Z(x,\beta _i)=\underset{i\mathrm{}}{limsup}h_\mu (T,\beta _i)`$. Since $`X`$ is compact and the diameter of the partitions $`\beta _i`$ tends to 0, we have that $`\underset{i\mathrm{}}{limsup}h_\mu (T,\beta _i)=h_\mu (T)`$ (see e.g.  page 170). The same arguments holds for $`K(x,\beta _i)`$, and the statement is proved. ∎

The previous lemma makes possible the following definition. If $`(X,\mu ,T)`$ is compact and ergodic and $`Z`$ is optimal, then for $`\mu `$-almost all points $`xX`$ and for countable families of measurable partitions $`\{\beta _i\}_i`$ such that $`\underset{i\mathrm{}}{lim}diam(\beta _i)=0`$, the complexity of the orbit of a point $`xX`$ is

$$K_Z(x)=\underset{i\mathrm{}}{limsup}K_Z(x,\beta _i).$$

## 5 Weakly chaotic dynamical systems

A weakly chaotic dynamical system is a system whose all physically relevant invariant measures have null Kolmogorov-Sinai entropy, but it has a not ordered dynamics. Thus, the complexity defined in Def. 1 always gives a null value and it is not a good observable to characterize these systems.

The first thing to do to have a meaningful observable would be to look directly at the asymptotic behavior of the information necessary to describe the orbit of a point777We recall that we do this with respect to a fixed partition (see the remarks of the previous section). One of the main tools in the proof of Brudno’s main theorem, which states the equality between the complexity for almost any initial condition and the Kolmogorov-Sinai entropy, is the Birkhoff ergodic theorem, which gives a relation between spatial and temporal averages for measurable functions defined on the state space. Then our pointwise approach to the asymptotic behavior of the complexity corresponds to the pointwise results of the ergodic theorem.

From this point of view, the pointwise approach in weakly chaotic dynamical systems should be based on general ergodic theorems, in which the temporal average should be done with non linear weights. This is, to our knowledge, a very delicate point in ergodic theory, and actually there are some negative results, for example in case of dynamical systems defined on a space $`X`$ with an invariant measure $`\mu `$ such that $`\mu (X)=+\mathrm{}`$. Let $`(X,T,\mu )`$ be such a dynamical system; it is impossible to define a sequence $`\{a(n)\}`$ of integer numbers, monotonically converging to infinity and with $`\frac{a(n)}{n}0`$ as $`n\mathrm{}`$, such that for all functions $`fL^1(X,\mu )`$

$$\underset{n+\mathrm{}}{lim}\frac{1}{a(n)}\underset{i=0}{\overset{n1}{}}f(T^i(x))=C$$

for almost any $`xX`$, where $`C`$ is a positive finite constant (). This result is applicable, for example, to the family of Manneville maps with parameter $`z2`$ (see Sections 6.2 and 7.1 for the description of the maps and references , ,) where the physically relevant invariant measure is infinite. Hence this is an indication that a pointwise approach for the complexity of the orbits of the Manneville maps could not give a consistent result.

We remark that we are just looking at the behavior of ergodic averages of a single function, so the generality of the ergodic theorems could be too much for our aims. Nevertheless using the results of  and  for the Manneville map with $`z=2`$, we expect that for almost any point $`xX`$ it is impossible to find a sequence $`a(n)`$ of integer numbers, converging to infinity and with $`\frac{a(n)}{n}0`$ as $`n\mathrm{}`$, such that the limit

$$\underset{n\mathrm{}}{lim}\frac{AIC(\omega ^n)}{a(n)}$$

exists and it is strictly positive, where $`\omega ^n`$ denotes the first $`n`$ digits of the symbolic string associated to the point $`x`$ using a fixed partition. Moreover we expect the superior limit to be infinity and the inferior limit to be zero for almost any initial condition, when the two limits are not both either zero or infinity. We believe that this result can be extended to the cases $`z>2`$.

Hence, for this reason, we will suggest a slight modification of Definition 1 and we will show that in the case of the Manneville-type maps this new index gives a classification for the maps of the family.

First, we will sketch the landscape in the case of general symbolic dynamical systems.

### 5.1 Symbolic dynamical systems

The following definitions are inspired by the example of the Manneville maps with $`z>2`$, for which there is not a physically relevant invariant probability measure, but for which there are results about the Lebesgue measure which is physically relevant but not invariant.

Hence in the following we will consider dynamical systems with a not necessarily invariant reference probability measure $`\mu `$. Let $`(\mathrm{\Omega },\sigma )`$ be a dynamical system and assume that there is a physically relevant measure $`\mu `$ which is not necessarily invariant. For instance, if the space $`X`$ is the unit interval $`[0,1]`$, then we will consider $`\mu `$ to be the Lebesgue measure on $`[0,1]`$. We consider the following index:

###### Definition 23 (q-entropy).

Let $`I:𝒜^{}`$ be an information measure. Let $`q`$ be a positive real number. We call q-entropy

$$h^q(\mathrm{\Omega })=\underset{n+\mathrm{}}{lim\; sup}_\mathrm{\Omega }\frac{I(\omega ^n)}{n^q}𝑑\mu .$$
(6)
If $`I=AIC`$, then we denote $`h^q(\mathrm{\Omega })`$ with $`h_{AIC}^q(\mathrm{\Omega })`$. If $`I=I_Z`$, with $`Z`$ a recursive coding procedure, then we denote $`h^q(\mathrm{\Omega })`$ with $`h_Z^q(\mathrm{\Omega })`$.

###### Theorem 24.

For all recursive coding procedures $`Z`$ and all $`q>0`$, we have

$$h_Z^q(\mathrm{\Omega })h_{AIC}^q(\mathrm{\Omega }).$$

###### Proof.

From inequality (5), we have that there exists a constant $`M`$ not depending on $`Z`$ such that

$$\frac{AIC(\omega ^n)}{n^q}\frac{I_Z(\omega ^n)}{n^q}+\frac{M}{n^q}.$$

From this the theorem easily follows. ∎

###### Definition 25 (Chaos index).

We call chaos index of the symbolic dynamical system $`(\mathrm{\Omega },𝒞,\mu ,\sigma )`$ the number $`q(\mathrm{\Omega })=inf\{p>0|h^p(\mathrm{\Omega })=0\}[0,1]`$. The indexes $`q_{_{AIC}}`$ and $`q__Z`$ are defined as above.

###### Corollary 26.

For all recursive coding procedures $`Z`$,

$$q__Z(\mathrm{\Omega })q_{_{AIC}}(\mathrm{\Omega }).$$

### 5.2 General dynamical systems

Let $`(X,T)`$ be a dynamical system amnd let $`\mu `$ be a reference probability measure as above, which is not supposed to be invariant. Let $`(\mathrm{\Omega }_\alpha ,\mu _\alpha )`$ be a symbolic model of $`(X,T)`$, relative to the partition $`\alpha `$ of the space $`X`$ and $`\phi _\alpha (x)`$ the symbolic string associated to any point $`xX`$.

###### Definition 27 (q-entropy relative to a partition).

As above let $`I:𝒜^{}`$ be an information measure, either $`AIC`$ or $`I_Z`$. Let $`\alpha `$ be a partition of $`X`$ and $`I(x,\alpha ,n)=I(\omega ^n)`$, where $`\omega =\phi _\alpha (x)`$. Then we call q-entropy relative to the partition $`\alpha `$

$$h^q(X,\alpha )=\underset{n+\mathrm{}}{lim\; sup}_{\mathrm{\Omega }_\alpha }\frac{I(x,\alpha ,n)}{n^q}𝑑\mu _\alpha .$$
(7)
In the example of the family of Manneville maps, that is the simplest model of intermittent weak chaos, the average with respect to the Lebesgue measure of the information plays a crucial role in the classification of the maps in the family. Following this example, we believe that the following index is a particularly meaningful indicator in the study of intermittent weakly chaotic dynamical systems.

###### Definition 28 (Intermittent Chaos index).

We call intermittent chaos index of the dynamical system $`(X,T,\mu )`$ with respect to a partition $`\alpha `$ the number

$$q(X,T,\alpha )=inf\{p>0|h^p(X,\alpha )=0\}[0,1].$$

The indexes $`q_{_{AIC}}`$ and $`q__Z`$ are defined as above.

###### Corollary 29.

For all compression algorithms $`Z`$,

$$q__Z(X,T,\alpha )q_{_{AIC}}(X,T,\alpha ).$$

In the next section we will apply these definitions to the family Manneville maps (for the definition see the next section) choosing the $`LZ77`$ compression algorithm (, ) and a generating partition $`\alpha `$. As a result it holds that in the weakly chaotic case (for $`z>2`$),

$$q_{_{LZ77}}(X,T,\alpha )=q_{_{AIC}}(X,T,\alpha )=\frac{1}{z1}.$$

## 6 Compression algorithms

### 6.1 The algorithm $`LZ77`$

The Ziv-Lempel compression scheme LZ77 with infinite window () is the one from which almost all practical adaptive dictionary encoders derived (). A dictionary of an input string is the set of words (i.e. group of consecutive symbols) in which the algorithm parses the input string.

The essence is that phrases (i.e. sets of consecutive words in the string to be encoded) are replaced with a pointer to where they have occurred earlier in the input string. Novel words and phrases can also be constructed from parts of earlier words.

In the $`LZ77`$ compression algorithm, the new word is defined as a pair (pointer,symbol). The pointer is referred to a phrase contained in the part of the input string which precedes the current position of the front end. As an example, let the alphabet $`𝒜`$ be the set $`\{a_1,\mathrm{},a_r\}`$ and consider an input string $`\omega 𝒜^{}`$. As usual, $`\omega ^n=(\omega _1\mathrm{}\omega _n)`$ is the substring of $`\omega `$ of length $`n`$ and containing its first $`n`$ symbols.
Consider some step $`h`$ of the coding procedure.

Suppose the first $`p`$ symbols $`(\omega _1\mathrm{}\omega _p)`$ have already been encoded. The dictionary now contains $`h`$ words $`\{e_1,\mathrm{},e_h\}`$. Thus, the current position of the front end is the $`(p+1)`$th site in the input string and the next word in the dictionary will be labelled as the $`(h+1)`$th word $`e_{h+1}`$.

The algorithm selects this new word as the longest word which can be obtained by adding a single character $`\stackrel{~}{a}`$ chosen in the alphabet $`𝒜`$ to a phrase $`\rho `$ contained in the substring $`(\omega _1\mathrm{}\omega _{p2})`$. Hence, the word $`e_{h+1}`$ has as a prefix the phrase $`\rho `$ followed by $`\stackrel{~}{a}`$ as an ending symbol ($`e_{h+1}=\rho \stackrel{~}{a}`$).

Once the new word $`e_{h+1}`$ has been found, the algorithm outputs a binary encoding of the triplet $`(s_{h+1},l_{h+1},\stackrel{~}{a})`$ where $`s_{h+1}`$ is the starting position of the prefix $`\rho `$ of the new word in the string $`(\omega _1\mathrm{}\omega _p)`$, $`l_{h+1}`$ is the length of the new word $`e_{h+1}`$ and the symbol $`\stackrel{~}{a}`$ from the alphabet is the last character of $`e_{h+1}`$.

The following example shows how the algorithm $`LZ77`$ encodes the input stream

$$\omega =(aababbbbaababba\mathrm{}).$$

Let $`𝒜=\{a,b\}`$ be the source alphabet.

The output is the binary encoding of the following triplets. The first column is the dictionary index number of the codeword whose triplet is showed in the same line, second column. For an easier reading, we add a third column which shows each encoded word in the original stream $`s`$, but we remark that it is not contained in the output file:

$$\begin{array}{ccc}1\hfill & (1,1,^{}a^{})\hfill & [a]\hfill \\ 2\hfill & (1,2,^{}b^{})\hfill & [ab]\hfill \\ 3\hfill & (2,3,^{}b^{})\hfill & [abb]\hfill \\ 4\hfill & (5,3,^{}a^{})\hfill & [bba]\hfill \\ 5\hfill & (2,5,^{}a^{})\hfill & [ababba]\hfill \end{array}$$

and so on.

Now we will recall some results from , concerning the optimality of the $`LZ77`$ algorithm.

###### Lemma 30.

Let $`t`$ denote the number of words in which the algorithm $`LZ77`$ parses the string $`\omega ^n`$. Set $`m=nN`$ where $`N=\mathrm{max}_{i=1,\mathrm{},r}n_i`$, where $`n_i`$ is the number of occurrences of the symbol $`a_i𝒜`$. Then $`t2(m+1)`$.

###### Theorem 31.

Let $`t`$ denote the number of words in which the algorithm $`LZ77`$ parses the string $`\omega ^n`$.

(i) For all $`k1`$ it holds

$$\begin{array}{cc}I_{LZ77}(\omega ^n)=|LZ77(\omega ^n)|\hfill & n\widehat{H}_k(\omega ^n)+3t\mathrm{log}_2\left(\frac{n}{t}\right)+\hfill \\ & +O\left((k1)t+t\mathrm{log}_2\mathrm{log}_2\left(\frac{n}{t}\right)\right).\hfill \end{array}$$
(8)
(ii) The algorithm $`LZ77`$ is optimal and for all $`n1`$, for all $`\omega ^n𝒜^n`$ and for all $`k1`$ it holds

$$\frac{I_{LZ77}(\omega ^n)}{n}\widehat{H}_k(\omega ^n)+O\left(\frac{\mathrm{log}_2\mathrm{log}_2(n)}{\mathrm{log}_2(n)}+\frac{k1}{\mathrm{log}_2(n)}\right).$$
(9)
(iii) The algorithm $`LZ77`$ is 8-asymptotically optimal with respect to $`\widehat{H}_1`$ and for any string $`\omega ^n`$ such that $`\widehat{H}_1(\omega ^n)0`$ it holds

$$I_{LZ77}(\omega ^n)8n\widehat{H}_1(\omega ^n)+O\left(t\mathrm{log}_2\mathrm{log}_2\left(\frac{n}{t}\right)\right).$$
(10)
### 6.2 $`LZ77`$ on the Manneville map

Now we are ready to prove the following theorem, which links the Information Content obtained via the algorithm $`LZ77`$ to the $`AIC`$ on the symbolic orbits of the Manneville map. We will study the dynamical system $`([0,1],𝒯_z)`$ where $`𝒯_z(x)=x+x^z(mod1)`$ and $`z>1`$. The reference measure is the Lebesgue measure on the unit interval.

The Manneville map was introduced by P. Manneville in  as an example of a discrete dissipative dynamical system with intermittency: there is an alternation between long regular phases, called laminar, and short irregular phases, called turbulent. This behavior has been observed in fluid dynamics experiments and in chemical reactions.

In order to state and prove our results, we recall some useful lemmas coming from probability theory.

###### Lemma 32.

(Jensen’s Inequality) Let $`\mathrm{I}`$ be a closed interval in $``$ and$`\mathrm{u}:\mathrm{I}`$ be convex and continuous at the endpoints of $`\mathrm{I}`$. If $`\mathrm{X}`$ is a random variable which takes its values in $`\mathrm{I}`$, then $`𝔼[\mathrm{u}\mathrm{X}]\mathrm{u}(𝔼[\mathrm{X}]).`$

###### Lemma 33.

If $`X`$ and $`Y`$ are two real random variables s.t. $`X0`$ and $`Y0`$, then

$$𝔼[\mathrm{max}\{X,Y\}]\mathrm{max}\{𝔼[X],𝔼[Y]\}.$$

###### Theorem 34.

Consider the dynamical system $`([0,1],𝒯_z)`$ driven by the Manneville map $`𝒯_z(x)=x+x^z(mod1)`$, with $`z>1`$. Let $`\stackrel{~}{x}(0,1)`$ be such that $`𝒯_z(\stackrel{~}{x})=1`$. Consider the partition $`\alpha =\{[0,\stackrel{~}{x}],(\stackrel{~}{x},1]\}`$ of the unit interval $`[0,1]`$. If $`\omega `$ is a symbolic orbit drawn from the Manneville map, with respect to the partition $`\alpha `$, then

$$\begin{array}{cc}𝔼[I_{LZ77}(\omega ^n)]n& \hfill \text{if }z<2\\ O(n^p)𝔼[I_{LZ77}(\omega ^n)]O(n^p\mathrm{log}_2(n))& \hfill \text{if }z>2\end{array}$$
(11)
where $`p=\frac{1}{z1}`$ and the measure is the usual Lebesgue measure on the interval.

###### Proof.

We will study the two cases separately.

If $`z<2`$: a result of  shows that for the expectation value of the $`AIC`$ of a symbolic orbit of the Manneville map with $`z<2`$, with respect to the Lebesgue measure on the interval, it holds that

$$𝔼[AIC(\omega ^n)]n.$$

Since it is $`AIC(\omega ^n)I_{LZ77}(\omega ^n)O(n)`$, then in this case we have that $`𝔼[I_{LZ77}(\omega ^n)]n`$.

If $`z>2`$: From Theorem 31 $`(iii)`$, we know that the algorithm $`LZ77`$ is asymptotically optimal with respect to $`\widehat{H}_1`$, that is

$$I_{LZ77}(\omega ^n)8n\widehat{H}_1(\omega ^n)+O\left(t\mathrm{log}_2\mathrm{log}_2\left(\frac{n}{t}\right)\right),$$
(12)
where $`t`$ is the number of words in the $`LZ77`$ parsing of $`\omega ^n`$. Thus, for any sequence $`\omega ^n`$, it holds

$$𝔼[I_{LZ77}(\omega ^n)]8n𝔼[\widehat{H}_1(\omega ^n)]+𝔼\left[t\mathrm{log}_2\mathrm{log}_2\left(\frac{n}{t}\right)\right].$$
(13)
First, we will prove that $`n𝔼[\widehat{H}_1(\omega ^n)]`$ is bounded by $`O(n^p\mathrm{log}_2(n))`$ with $`p=\frac{1}{z1}`$. Then, we will give an estimate for $`𝔼[t\mathrm{log}_2\mathrm{log}_2(\frac{n}{t})]`$, so completing the proof.

By definition, $`\widehat{H}_1(\omega ^n)=(\frac{N_n}{n}\mathrm{log}_2(\frac{N_n}{n})+(1\frac{N_n}{n})\mathrm{log}_2(1\frac{N_n}{n}))`$ where $`N_n`$ is the number of occurrences of the event $`=\{passagethrough(\stackrel{~}{x},1]\}`$.

In  it has been proved that if $`z>2`$ then $`𝔼[N_n]n^p`$ .

Therefore, for the first order empirical entropy of a symbolic orbit drawn by the Manneville map with respect to the Lebesgue measure, we can apply Jensen’s inequality and obtain:

$$\begin{array}{cc}𝔼[\widehat{H}_1(\omega ^n)]\hfill & \left(𝔼\left[\frac{N_n}{n}\mathrm{log}_2\left(\frac{N_n}{n}\right)\right]+𝔼\left[\left(1\frac{N_n}{n}\right)\mathrm{log}_2\left(1\frac{N_n}{n}\right)\right]\right)\hfill \\ & (𝔼\left[\frac{N_n}{n}\right]\mathrm{log}_2\left(𝔼\left[\frac{N_n}{n}\right]\right)+\hfill \\ & +(1𝔼\left[\frac{N_n}{n}\right])\mathrm{log}_2(1𝔼\left[\frac{N_n}{n}\right]))\hfill \\ & \left(n^{p1}\mathrm{log}_2\left(n^{p1}\right)+\left(1n^{p1}\right)\mathrm{log}_2\left(1n^{p1}\right)\right).\hfill \end{array}$$

Consequently, we can easily verify that

$$\begin{array}{cc}8n𝔼[\widehat{H}_1(\omega ^n)]\hfill & 8n^p\mathrm{log}_2\left(n^{p1}\right)8\left(nn^p\right)\mathrm{log}_2(1n^{p1})=\hfill \\ & =8n^p\mathrm{log}_2\left(n^{1p}1\right)8n\mathrm{log}_2\left(1n^{p1}\right).\hfill \end{array}$$

For the fact that $`p<1`$, it holds

$$\begin{array}{c}8n^p\mathrm{log}_2\left(n^{1p}1\right)8n\mathrm{log}_2\left(1n^{p1}\right)\hfill \\ n^p\left((1p)\mathrm{log}_2(n)1\right)=\hfill \\ =O(n^p\mathrm{log}_2(n)).\hfill \end{array}$$
(14)
Now we will prove that, for $`\omega ^n`$ a symbolic orbit of the Manneville map with $`z>2`$, if $`t`$ is the number of words in the $`LZ77`$ parsing of $`\omega ^n`$, it holds

$$𝔼\left[t\mathrm{log}_2\mathrm{log}_2\left(\frac{n}{t}\right)\right]O(n^p\mathrm{log}_2(n)).$$
(15)
We apply Lemma 30, with alphabet $`𝒜=\{0,1\}`$ where $`1`$ is the symbol associated to the event $`=\{passagethrough[\stackrel{~}{x},1]\}`$, which appears in $`\omega ^n`$ with mean probability $`\frac{N_n}{n}=n^{p1}`$ and $`0`$ is the symbol associated to the event $`not`$.

Thus, $`m=n\mathrm{max}\{n_0,n_1\}`$ and $`t2(m+1)=2(n\mathrm{max}\{n_0,n_1\}+1).`$

Thanks to Lemma 33, we obtain the following estimates:

$$\begin{array}{cc}𝔼[t]\hfill & 2𝔼[r]+1=\hfill \\ & =2n+12𝔼[\mathrm{max}\{n_0,n_1\}]\hfill \\ & 2n+12\mathrm{max}\{𝔼[n_0],𝔼[n_1]\}=\hfill \\ & =2n+12\mathrm{max}\{nn^p,n^p\}=\hfill \\ & =2n^p+1.\hfill \end{array}$$
(16)
Eventually, the inequality (15) can be easily verified.

From the estimates (14) and (15) together with (13), it follows that

$$𝔼[I_{LZ77}(\omega ^n)]O(n^p\mathrm{log}_2(n)).$$

Finally, since the $`AIC`$ is the ideal information content of a string, it is $`I_{LZ77}(\omega ^n)AIC(\omega ^n)`$ and the same inequality relates the expectation values.

In  and , it has been proved that $`𝔼[AIC(\omega ^n)]O(n^p)`$. This completes the proof.

### 6.3 The algorithm CASToRe

We have created and implemented a particular compression algorithm we called CASToRe which is a modification of the well known LZ78 algorithm (). Its theoretical advantages with respect to LZ78 are shown in , : it is a sensitive measure of the Information content of low entropy sequences. That’s why is called CASToRe: Compression Algorithm,  Sensitive To Regularity.

As it has been proved in Theorem 4.1 in , the Information $`I_Z`$ of a constant sequence $`s^n`$, originally with length $`n`$, is $`4+2\mathrm{log}(n+1)[\mathrm{log}(\mathrm{log}(n+1))1]`$, if the algorithm $`Z`$ is CASToRe. The theory predicts that the best possible information for a constant sequence of length $`n`$ is $`AIC(s^n)=\mathrm{log}(n)+`$const. In , it is shown that the algorithm $`LZ78`$ encodes a constant $`n`$ digits long sequence to a string with length about $`const+n^{\frac{1}{2}}`$ bits; so, we cannot expect that $`LZ78`$ is able to distinguish a sequence whose information grows like $`n^\alpha `$ ($`\alpha <\frac{1}{2}`$) from a constant or periodic one. This motivates the choice of using CASToRe.

Now we briefly describe the internal running of CASToRe.

As the algorithm LZ77, the algorithm CASToRe is based on an adaptive dictionary (). One of the basic differences in the coding procedure is that the algorithm LZ77 splits the input strings in overlapping words, while the algorithm CASToRe (as already the algorithm LZ78) parses the input string in non-overlapping words.

At the beginning of encoding procedure, the dictionary is contains only the alphabet. In order to explain the principle of encoding, let’s consider a step $`h`$ within the encoding process, when the dictionary already contains $`h`$ words $`\{e_1,\mathrm{},e_h\}`$.

The new word is defined as a pair (prefix pointer,suffix pointer). The two pointers are referred to two (not necessarily different) words $`\rho _p`$ and $`\rho _s`$ chosen among the ones contained in the current dictionary as follows. First, the algorithm reads the input stream starting from the current position of the front end, looking for the longest word $`\rho _p`$ matching the stream. Then, we look for the longest word $`\rho _s`$ such that the joint word $`\rho _p\rho _s`$ matches the stream. The new word $`e_{h+1}`$ which will be added to the dictionary is then $`e_{h+1}=\rho _p\rho _s`$.

The output file contains an ordered sequence of the binary encoding of the pairs $`(i_p,i_s)`$ such that $`i_p`$ and $`i_s`$ are the dictionary index numbers corresponding to the prefix word $`\rho _p`$ and to the suffix word $`\rho _s`$, respectively. The pair $`(i_p,i_s)`$ is referred to the new encoded word $`e_{h+1}`$ and has its own index number $`i_{h+1}`$.

The following example shows how the algorithm CASToRe encodes the input stream

$$\omega =(abcababccabb\mathrm{}).$$

Let the source alphabet be $`𝒜=\{a,b,c\}`$.

The output is the binary encoding of the following pairs contained in the second column. The first column is the dictionary index number of the encoded word in the dictionary which is showed in the same line, second column. For an easier reading, we add a third column which shows each encoded word in the original stream $`\omega `$, but it is not contained in the output file:

$$\begin{array}{ccc}& \text{First, the dictionary is being loaded}\hfill & \\ 1\hfill & (0,^{}a^{})\hfill & [a]\hfill \\ 2\hfill & (0,^{}b^{})\hfill & [b]\hfill \\ 3\hfill & (0,^{}c^{})\hfill & [c]\hfill \\ & \text{Then, the encoding procedure starts}\hfill & \\ 4\hfill & (1,2)\hfill & [ab]\hfill \\ 5\hfill & (3,4)\hfill & [cab]\hfill \\ 6\hfill & (4,3)\hfill & [abc]\hfill \\ 7\hfill & (5,3)\hfill & [cabc]\hfill \end{array}$$

and so on.

We remark that this coding procedure, which pairs words already in the dictionary to create a new word, is similar to the procedure that can be found in the recent work , which seems to be able to give a very precise entropy estimation, detecting very long range correlations in the English language.

## 7 Numerical experiments

In this section we show some numerical experiments supported by the theory of the previous sections. We consider some examples of fully chaotic and weakly chaotic dynamical systems and we measure the information content of the generated symbolic orbits with respect to some partition.

We measure the information content with the two different data compression algorithms LZ77 with infinite window and CASToRe, whose internal running has been presented above. These two algorithms seems to be suitable for the compression of 0-entropy strings (see  and Proposition 31) and they are fast enough to allow the compression of long strings (we could manage to compress trajectories of $`O(10^7)`$ symbols). From the computational point of view, whereas LZ77 requires a big amount of RAM (Random Access Memory), since it needs to retain the entire string already encoded and the entire dictionary built, the algorithm CASToRe only remembers the dictionary which is implemented in a tree structure. Hence, the computation time is a distinguishing feature between the two algorithms: CASToRe can compress a $`O(10^7)`$-symbols string in few seconds.

As we will see the results agree with theoretical predictions when they are available or with other numerical results which can be found in the literature.

It is worth to remark that, even if the two compression schemes are basically different, the two algorithms give a behavior of the information content of the same order in all the numerical experiments we performed.

### 7.1 The Manneville map

We measure the information content of symbolic orbits drawn from the Manneville map.

Let us consider again the Manneville map $`𝒯_z(x)=x+x^z(mod1)`$ as it has been presented in Section 6.2.

Let us consider the partitions $`\alpha _1,\alpha _2`$ obtained by dividing $`[0,1]`$ in 2 or 4 subintervals. The partition $`\alpha _1`$ is the same described in Section 6.2 and $`\alpha _2`$ is a refinement of $`\alpha _1`$: $`\alpha _2`$ is obtained splitting in two equal parts each interval of $`\alpha _1`$. We denote by $`K(x,\alpha _i,n),i\{1,2\}`$ the Algorithmic Information Content of a $`n`$-long symbolic orbit of the Manneville map with initial condition $`x`$, with respect to the partition $`\alpha _i`$.

By the results exposed in (,, ) we have that the mean value of $`K(x,\alpha _i,n)`$, with respect to the Lebesgue measure, on the initial conditions of the orbit is expected to be $`𝔼[K(x,\alpha _i,n)]n^p`$, with $`p=\frac{1}{z1}`$ for $`z>2`$, and $`𝔼[K(x,\alpha _i,n)]n`$ for $`z<2`$. Moreover (by the results of section 6.2) the same result holds for the information as it is measured by the algorithm LZ77. We verified numerically this statement, and the result is shown in figure 1.

If we use the information content as it is measured by CASToRe the numerical result is also close to the previous one. This confirms the theoretical results and proves that the methods relative to the Computable Information Content are experimentally reliable.

We considered a set of one hundred initial points, then we generated the relative $`10^7`$-long orbits and we applied the compression algorithms to the associated symbolic strings $`s`$ (with respect both to the partition $`\alpha _1`$ and $`\alpha _2`$).

In Table 1 we show the results. The first column indicates the partition to which the results are referred. The second column is the value of the parameter $`z`$ which drives the dynamics of the system. The last column gives the results of the theory for the exponent $`p`$ of the asymptotic behavior of $`K(x,\alpha _i,n)n^p`$. The third and the fourth columns show the experimental results. The shown number is the average $`\overline{p}`$ of the exponents of one hundred different orbits. The initial conditions of the orbits are chosen randomly with respect to the Lebesgue measure.

In Figure 1 are plotted several examples of the behavior of the Information Content $`I_Z`$ when $`Z=`$LZ77 (on the right) or $`Z=`$CASToRe (on the left) and for different values of the parameter $`z`$. The scale is bilogarithmic, so that the power laws become straight lines and the exponent $`p`$ of the expected power law is the slope of the correspondent straight line.

### 7.2 The logistic map

In this section we study the logistic map at the chaos threshold from an experimental point of view. We recall that the logistic map is defined by

$$f(x)=\lambda x(1x),x[0,1],1\lambda 4.$$
(17)
The logistic map has been used to simulate the behavior of biological species not in competition with other species. Later the logistic map has also been presented as the first example of a relatively simple map with an extremely rich dynamics (,). If we let the parameter $`\lambda `$ vary from $`1`$ to $`4`$, we find a sequence of bifurcations of different kinds. For values of $`\lambda <\lambda _{\mathrm{}}=3.56994567187\mathrm{}`$, the dynamics is periodic and there is a sequence of period doubling bifurcations which leads to the chaos threshold for $`\lambda =\lambda _{\mathrm{}}`$.

Numerical experiments and heuristics considerations from the physical literature indicate that at the chaos threshold there is a power-law “sensitivity” to initial conditions (here the sensitivity to initial conditions was measured with a generalized Lyapunov exponent). These facts justified the application of generalized entropies to the map ().

Moreover by the more recent results of  we know that if we consider the Lebesgue measure, then for almost any initial condition the Algorithmic Information Content of an orbit will increase as the logarithm of the number of steps.

In the following, we will show how we have experimentally confirmed this result measuring the information with LZ77 and CASToRe.

In figure 2 the main plot is in bilog scale, while the inset is in log-linear scale and the same graphs as in the main plot are pictured. On the left, the experiments performed via CASToRe, on the right via LZ77. The analysis of results is the same for both pictures.

The solid line in the main plot represents the information behavior at the chaos threshold. This graph already indicates that at the chaos threshold $`\lambda _{\mathrm{}}`$ the information increases below any power law (any power law becomes a straight line when plotted in bilog scale and our graph is evidently concave), as predicted by the theory. A more accurate quantitative analysis was done in . The upper lines are referred to values of $`\lambda >\lambda _{\mathrm{}}`$ for which the map is chaotic (the information increases linearly with time). The lower lines represents the information behavior when $`\lambda `$ tends to $`\lambda _{\mathrm{}}`$ from below (along the period doubling cascade), hence when we are in the periodic regime (where the Algorithmic Information Content is expected to behave logarithmically).

### 7.3 Tirnakli, Tsallis, Lyra (TTL)-circular like maps

These maps have been introduced in , where they are studied numerically, as modifications of the classical standard map. These maps are one-dimensional maps and varying the parameters they show a transition to chaos. They are defined by

$$T_z(x)=\mathrm{\Omega }_z+(x\frac{1}{2\pi }\mathrm{sin}(2\pi x))^{\frac{z}{3}}(mod1)$$

and we study the maps with parameters values $`z=3,z=4,z=5`$ with $`\mathrm{\Omega }_3=0.606661063469`$, $`\mathrm{\Omega }_4=0.648669091983`$, $`\mathrm{\Omega }_5=0.6788311756505`$, for which values the maps are at the onset of chaos.

We recall that for $`z=3`$ we obtain the classical the standard map

$$T(x)=\mathrm{\Omega }+(x\frac{K}{2\pi }\mathrm{sin}(2\pi x))(mod1)$$

with $`K=1`$ (at the edge of a quasiperiodic transition to chaos).

For these maps results in  show a numerical evidence of power law initial data sensitivity, as it was shown in  for the logistic map at the edge of chaos. Also, by the results of 888In the cited paper, quantitative results are proved between initial condition sensitivity and complexity., this would correspond to a logarithmic increase of the algorithmic information. We measured the information coming from these maps, obtaining a behavior that is also similar to the logistic map at the edge of chaos and fits with the cited numerical results (Figure 3).

### 7.4 Casati-Prosen map

This area-preserving map has been proposed in  as a model of quantum chaos. The map is defined on $`T^2=[1,1)\times [1,1)`$ by $`T\left(\begin{array}{c}x_n\\ y_n\end{array}\right)=\left(\begin{array}{c}x_{n+1}\\ y_{n+1}\end{array}\right)`$ where

$$\begin{array}{cc}x_{n+1}=& x_n+y_{n+1}\hfill \\ y_{n+1}=& y_n+\alpha \text{ sgn}(x_n)+\beta \hfill \end{array}$$

and $`\alpha =\frac{(\frac{1}{2}(\sqrt{5}1)\frac{1}{e})}{2}`$, $`\beta =\frac{(\frac{1}{2}(\sqrt{5}1)+\frac{1}{e})}{2}`$. Results in  provide numerical evidences that the map is ergodic and mixing, with linear speed of separation of nearby starting orbits.

We studied the complexity of some trajectory of the system, obtaining that the computable information seems to increase as a power law $`n^p`$ with exponent $`p`$ approximately equal to $`0.75\mathrm{}`$ ($`p=0.742`$ when estimated by LZ77 and $`p=0.755`$ when estimated by CASToRe). This result is quite unexpected from the connection between sensitivity to initial conditions and the asymptotic behavior of the information content (). From the cited results, to a linear initial condition sensitivity would correspond a logarithmic increase of the AIC. However, the rigorous proof of all the properties of the map remains an open problem.

### 7.5 The Arnold cat map

The Arnold cat map is an example of a two-dimensional hyperbolic toral automorphism, that is the projection on the two-torus $`^2/^2`$ of a linear map of $`^2`$, represented by a matrix $`M`$ with integer elements and determinant one and real eigenvalues $`\lambda `$ and $`1/\lambda `$, different from 1. The Arnold cat map is specified by the matrix

$$M=\left(\begin{array}{cc}1& 1\\ 1& 2\end{array}\right)$$

with $`\lambda =(3+\sqrt{2})/2`$. From a theorem of  it follows that the Kolmogorov-Sinai entropy with respect to the Lebesgue measure of a two-dimensional hyperbolic toral automorphism is given by the logarithm of the modulus of the eigenvalue bigger than 1. Hence, in this case

$$h=\mathrm{log}_2\frac{3+\sqrt{2}}{2}1.388\mathrm{}$$

Our computations give the same result. We only show the results for the compression algorithm CASToRe, since in this case no evident differences can be appreciated. Studying the behavior of the information content with respect to the length of the compressed string, we expect to find a straight line with angular coefficient equal to the entropy of the dynamical system, when working with a generating partition. In figure 5 it is represented the information function for three different choices of the partition. The dotted line is obtained with a partition of the square $`[0,1)\times [0,1)`$ in two horizontal strips. The solid line is obtained with a partition in four equal squares along the axis, and the dashed line is obtained with a partition in four squares along the eigen-directions associated to the matrix $`M`$. The angular coefficients of the lines are 0.98 for the dotted line, 1.56 for the solid line and 1.37 for the dashed line, showing that the first two partitions considered are not able to simulate the whole complexity of the system, whereas the last one can be considered to be a generating partition.

### 7.6 The Froeschlé map

This map was studied in  as an example of a symplectic map for which it is possible to find the integrable and non-integrable initial conditions. The map is defined on the two-torus $`^2/(2\pi )^2`$ by

$$\begin{array}{cc}x_{n+1}=\hfill & x_n+a\mathrm{sin}y_n\hfill \\ y_{n+1}=\hfill & x_n+y_n+a\mathrm{sin}y_n\hfill \end{array}$$

with $`a=1.3`$. We studied the behavior of the information content for orbits generated by two different initial conditions, one corresponding to the regular zone, and the other to the irregular zone. Both orbits have been studied with CASToRe and with LZ77. In the regular zone, the initial condition is given by the point $`(0,2.5)`$. From the results in figure 6 (dotted curves), one can see that both the compression algorithms give indication of regularity by an increasing of the information content of the order of a logarithm (this behavior is visible clearly in the inset in the two figures, where the information content is plotted on a log-linear scale). The two compression algorithms also give a strong indication of full chaos for the irregular orbit, generated by the initial condition $`(2,0)`$. In figure 6, the information content is a straight line (solid and dotted lines, with partitions in two vertical strips and in four equal squares) whose angular coefficients give an indication of the value 0.40 and 0.44, respectively, of the Kolmogorov-Sinai entropy with respect to the measure associated to the initial point. These results are in agreement with those of .