Xavier Bressaud
email: bressaud@math.univ-toulouse.fr

Pierre Tisseur
email: pierre.tisseur@ufabc.edu.br

On a zero speed sensitive cellular automaton *

Using an unusual, yet natural invariant measure we show that there exists a sensitive cellular automaton whose perturbations propagate at asymptotically null speed for almost all configurations. More specifically, we prove that Lyapunov Exponents measuring pointwise or average linear speeds of the faster perturbations are equal to zero. We show that this implies the nullity of the measurable entropy. The measure µ we consider gives the µ-expansiveness property to the automaton. It is constructed with respect to a factor dynamical system based on simple "counter dynamics". As a counterpart, we prove that in the case of positively expansive automata, the perturbations move at positive linear speed over all the configurations.

Introduction

A one-dimensional cellular automaton is a discrete mathematical idealization of a space-time physical system. The space A Z on which it acts is the set of doubly infinite sequences of elements of a finite set A; it is called the configuration space. The discrete time is represented by the action of a cellular automaton F on this space. Cellular automata are a class of dynamical 1 systems on which two different kinds of measurable entropy can be considered: the entropy with respect to the shift σ (which we call spatial) and the entropy with respect to F (which we call temporal). The temporal entropy depends on the way the automaton "moves" the spatial entropy using a local rule on each site of the configuration space. The propagation speed of the different one-sided configurations, also called perturbations in this case, can be defined on a specific infinite configuration, or as an average value on the configuration space endowed with a probability measure. We can consider perturbations moving from the left to the right or from the right to the left side of the two sided sequences. Here we prove that the perturbations (going to the left or to the right) move at a positive speed on all the configurations for a positively expansive cellular automata and that in the sensitive case, there exist automata with the property that for almost all the configurations, the perturbations can move to infinity but at asymptotically null speed.

Cellular automata can be roughly divided into two classes: the class of automata which have equicontinuous points and the class of sensitive cellular automata (Kůrka introduces a more precise classification in [START_REF] Kůrka | Languages, equicontinuity and attractors in linear cellular automata[END_REF]). This partition of CA into ordered ones and disordered ones also corresponds to the cases where the perturbations cannot move to infinity (equicontinuous class) and to the cases where there always exist perturbations that propagate to infinity.

The existence of equicontinuity points is equivalent to the existence of a so-called "blocking word" (see [START_REF] Kůrka | Languages, equicontinuity and attractors in linear cellular automata[END_REF], [START_REF] Tisseur | Cellular automata and Lyapunov Exponents[END_REF]). Such a word stops the propagation of perturbations so roughly speaking in the non sensitive case, the speed of propagation is equal to zero for all the points which contains infinitely many occurrences of "blocking words". For a sensitive automaton there is no such word, so that perturbations may go to infinity. However, there are few results about the speed of propagation of perturbations in sensitive cellular automata except for the positively expansive subclass.

In [START_REF] Shereshevsky | Lyapunov Exponents for One-Dimensional Cellular Automata[END_REF], Shereshevsky gave a first formal definition of these speeds of propagation (for each point and for almost all points) and called them Lyapunov exponents because of the analogy (using an appropriate metric) with the well known exponents of the differentiable dynamical systems.

Here we use a second definition of these discrete Lyapunov exponents given by Tisseur [START_REF] Tisseur | Cellular automata and Lyapunov Exponents[END_REF]. The two definitions are quite similar, but for each point, the Shereshevsky's one uses a maximum value on the shift orbit. For this reason the Shereshevsky's exponents (pointwise or global) can not see the "blocking words" of the equicontinuous points and could give a positive value (for almost all points) to the speed on these points. Furthemore, in our sensitive example (see Section 5), for almost all infinite configurations, there always exists some increasing (in size) sequences of finite configurations where the speed of propagation is not asymptoticaly null which implies that the initial definition gives a positive value to the speed and does not take into account a part of the dynamic of the measurable dynamical systems.

Using the initial definition of Lyapunov exponents due to Shereshevsky [START_REF] Shereshevsky | Lyapunov Exponents for One-Dimensional Cellular Automata[END_REF], Finelli, Manzini, Margara ( [START_REF] Finelli | Lyapunov exponents versus expansivity and sensivity in cellular automata[END_REF]) have shown that positive expansiveness implies positivity of the Shereshevski pointwise Lyapunov exponents at all points.

Here we show that the statement of Finelli, Manzini, Margara still holds for our definition of pointwise exponents and the main difference between the two results is that we obtain that the exponents are positive for all points using a liminf rather that a limsup.

Proposition 1 For a positively expansive cellular automaton F acting on

A Z , there is a constant Λ > 0 such that, for all x ∈ X, λ + (x) ≥ Λ and λ -(x) ≥ Λ,
where λ + (x) and λ -(x) are respectively the right and left pointwise Lyapunov exponents.

The first part of the proof uses standard compactness arguments. The result is stronger and the proof is completely different from the one in [START_REF] Finelli | Lyapunov exponents versus expansivity and sensivity in cellular automata[END_REF]. This result is called Proposition 2 in Section 3 and it is stated for all F -invariant subshifts X.

Our main result concerns sensitive automata and average Lyapunov exponents (I + µ and I - µ ). We construct a sensitive cellular automaton F and a (σ, F )-invariant measure µ F such that the average Lyapunov exponents I ± µ F are equal to zero.

By showing (see Proposition 3) that the nullity of the average Lyapunov exponents implies that the measurable entropy is equal to zero, we obtain that our particular automaton have null measurable entropy h µ F (F ) = 0.

We also prove that this automaton is not only sensitive but µ F -expansive which is a measurable equivalent to positive expansiveness introduced by Gilman in [START_REF] Gilman | Classes of linear automata[END_REF]. So even if this automaton is very close to positive expansiveness (in the measurable sense), its pointwise Lyapunov exponents are equal to zero almost everywhere (using Fatou's lemma) for a "natural" measure µ F with positive entropy under the shift. The µ F -expansiveness means that "almost all perturbations" move to infinity and the Lyapunov exponents represent the speed of the faster perturbation, so in our example almost all perturbations move to infinity at asymptoticaly null speed. In view of this example, Lyapunov exponents or average speed of perturbations appear a useful tool for proving that a cellular automata has zero measure-theoretic entropy.

The next statement gathers the conclusions of Proposition 3, Proposition 5, Lemma 3 , Proposition 6, Proposition 7, Corollary 1, Remark 6.

Theorem 1 There exists a sensitive cellular automaton F with the following properties: there exists a (σ, F )-invariant measure µ F such that h µ F (σ) > 0 and the Lyapunov exponents are equal to zero, i.e., I ± µ F = 0, which implies that h µ F (F ) = 0. Furthemore this automaton F has the µ F -expansiveness property.

Let us describe the dynamics of the cellular automaton F and the related "natural" invariant measure µ F that we consider.

In order to have a perturbation moving to infinity but at a sublinear speed, we define a cellular automaton with an underlying "counters dynamics", i.e. with a factor dynamical system based on "counters dynamics".

Consider this factor dynamical system of F and call a "counter" of size L a set {0, . . . , L -1} ⊂ N. A trivial dynamic on this finite set is addition of 1 modulo L. Consider a bi-infinite sequence of counters (indexed by Z). The sizes of the counters will be chosen randomly and unboundly. If at each time step every counter is increased by one, all counters count at their own rythm, independently. Now we introduce a (left to right) interaction between them. Assume that each time a counter reaches the top (or passes through 0; or is at 0), it gives an overflow to its right neighbour. That is, at each time, a counter increases by 1 unless its left neighbour reaches the top, in which case it increases by 2. This object is not a cellular automaton because its state space is unbounded. However, this rough definition should be enough to suggest the idea.

• The dynamics is sensitive. Choose a configuration, if we change the counters to the left of some coordinate -s, we change the frequency of apparition of overflows in the counter at position -s (for example this happens if we put larger and larger counters). Then the perturbation eventually appears at the coordinate 0.

• The speed at which this perturbation propagates is controlled by the sizes of the counters. The time it takes to get through a counter is more or less proportional to the size of this counter (more precisely, of the remaining time before it reaches 0 without an overflow). So a good choice of the law of the sizes of the counters allows us to control this mean time. More specifically, we prove that that with high probability, information will move slowly. If the size of the counters were bounded the speed would remain linear.

In the cellular automaton F , we "put up the counters" horizontally: we replace a counter of size L = 2 l by a sequence of l digits and we separate sequences of digits by a special symbol, say E. Between two Es the dynamics of a counter is replaced by an odometer with overflow transmission to the right. More precisely, at each step the leftmost digit is increased by 1 and overflow is transmitted.

Note that to model the action of a cellular automaton we need to introduce in the factor dynamics a countdown which starts when the counter reaches the top. The end of the countdown corresponds to the transmission of the overflow. When the countdown is running, the time remaining before the emission of the overflow does not depend on a possible overflow emmited by a neighbouring counter. Nevertheless the effect of this overflow will affect the start of the next countdown.

Finally, we construct an invariant measure based on Cesaro means of the sequence (µ•F n ) where µ is a measure defined thanks to the counter dynamic of the factor dynamical system .

Definitions and notations 2.1 Symbolic systems and cellular automata

Let A be a finite set or alphabet. Denote by A * the set of all concatenations of letters in A. A Z is the set of bi-infinite sequences x = (x i ) i∈Z also called configuration space. For i ≤ j in Z, we denote by x(i, j) the word x i . . . x j and by x(p, ∞) the infinite sequence (v i ) i∈N with v i = x p+i . For t ∈ N and a word u we call cylinder the set [u] t = {x ∈ A Z : x(t, t + |u|) = u}. The configuration set A Z endowed with the product topology is a compact metric space. A metric compatible with this topology can be defined by the distance d(x, y) = 2 -i , where i = min{|j| : x(j) = y(j)}.

The shift σ:

A Z → A Z is defined by σ(x i ) i∈Z = (x i+1 ) i∈Z . The dynamical system (A Z , σ) is called the full shift. A subshift X is a closed shift-invariant subset X of A Z endowed with the shift σ. It is possible to identify (X, σ) with the set X.
Consider a probability measure µ on the Borel sigma-algebra B of A Z . When µ is σ-invariant the topological support of µ is a subshift denoted by S(µ). We shall say that the topological support is trivial if it is countable. If α = (A 1 , . . . , A n ) and β = (B 1 , . . . , B m ) are two partitions of X, we denote by α∨β the partition {A i ∩B j , i = 1, . . . , n, j = 1, . . . , m}. Let T : X → X be a measurable continuous map on a compact set X. The metric entropy h µ (T ) of T is an isomorphism invariant between two µ-preserving transformations. Let

H µ (α) = A∈α µ(A) log µ(A)
, where α is a finite partition of X. The entropy of the finite partition α is defined as h µ (T, α) = lim n→∞ 1/nH µ (∨ n-1 i=0 T -i α) and the entropy of (X, T, µ) as h µ (T ) = sup α h µ (T, α).

A cellular automaton is a continuous self-map F on A Z commuting with the shift. The Curtis-Hedlund-Lyndon theorem [START_REF] Hedlund | Endomorphisms and Automorphisms of the Shifts Dynamical System[END_REF] states that for every cellular automaton F there exist an integer r and a block map f : A 2r+1 → A such that F (x) i = f (x i-r , . . . , x i , . . . , x i+r ). The integer r is called the radius of the cellular automaton. If X is a subshift of A Z and F (X) ⊂ X, then the restriction of F to X determines a dynamical system (X, F ) called a cellular automaton on X.

Equicontinuity, sensitivity and expansiveness

Let F be a cellular automaton on A Z . Definition 1 (Equicontinuity) A point x ∈ A Z is called an equicontinuous point (or Lyapunov stable) if for all ǫ > 0, there exists η > 0 such that

d(x, y) ≤ η =⇒ ∀i > 0, d(T i (x), T i (y)) ≤ ǫ.
Definition 2 (Sensitivity) The automaton (A Z , F ) is sensitive to initial conditions (or sensitive) if there exists a real number ǫ > 0 such that

∀x ∈ A Z , ∀δ > 0, ∃y ∈ A Z , d(x, y) ≤ δ, ∃n ∈ N, d(F n (x), F n (y)) ≥ ǫ.
The next definition appears in [START_REF] Gilman | Classes of linear automata[END_REF] for a Bernouilli measure.

Definition 3 (µ-Expansiveness) The automaton (A Z , F ) is µ-expansive if there exists a real number ǫ > 0 such that for all x in A Z one has

µ {y ∈ X : ∀i ∈ N, d(F i (x), F i (y)) ≤ ǫ} = 0.
Notice that in [START_REF] Gilman | Classes of linear automata[END_REF] Gilman gives a classification of cellular automata based on the µ-expansiveness and the µ-equicontinuity classes.

Definition 4 (Positive Expansiveness)

The automaton (A Z , F ) is positively expansive if there exists a real number ǫ > 0 such that,

∀(x, y) ∈ (A Z ) 2 , x = y , ∃n ∈ N such that d(F n (x), F n (y)) ≥ ǫ.
Kůrka [START_REF] Kůrka | Languages, equicontinuity and attractors in linear cellular automata[END_REF] shows that, for cellular automata, sensitivity is equivalent to the absence of equicontinuous points.

Lyapunov exponents

For all x ∈ A Z , the sets For all integer n, consider the smallest "distance" in terms of configurations at which a perturbation will not be able to influence the n first iterations of the automaton:

W + s (x) = {y ∈ A Z : ∀i ≥ s, y i = x i }, W - s (x) = {y ∈ A Z : ∀i ≤ s, y i = x i },
I - n (x) = min{s ∈ N : ∀1 ≤ i ≤ n, F i (W - s (x)) ⊂ W - 0 (F i (x))}, (1) I + n (x) = min{s ∈ N : ∀1 ≤ i ≤ n, F i (W + -s (x)) ⊂ W + 0 (F i (x))}.
We can now define the pointwise Lyapunov exponents by

λ + (x) = lim n→∞ inf I + n (x) n , λ -(x) = lim n→∞ inf I - n (x) n .
For a given configuration x, λ + (x) and λ -(x) represent the speed to which the left and right faster perturbations propagate.

Definition 5 (Lyapunov Exponents) For a µ shift-invariant measure on A Z , we call average Lyapunov exponents of the automaton (A Z , F, µ), the constants

I + µ = lim inf n→∞ I + n,µ n , I - µ = lim inf n→∞ I - n,µ n , (2)
where

I + n,µ = X I + n (x)dµ(x), I - n,µ = X I - n (x)dµ(x).
Remark 1 The sensitivity of the automaton (A Z , F, µ) implies that for all x ∈ A Z , (I + n (x) + I - n (x)) n∈N goes to infinity.

Lyapunov exponents of positively expansive cellular automata

Similar versions of the next lemma appear in [START_REF] Blanchard | Ergodic properties of expansive one-sided cellular automata[END_REF] and [START_REF] Kůrka | Languages, equicontinuity and attractors in linear cellular automata[END_REF]. The proof of similar results in [START_REF] Finelli | Lyapunov exponents versus expansivity and sensivity in cellular automata[END_REF] using limsup is based on completely different arguments.

Lemma 1 Let F be a positively expansive CA with radius r acting on a F -invariant subshift X ⊂ A Z . There exists a positive integer N + such that for all x and y in X that verify x(-∞, -r -1) = y(-∞, -r -1) and F m (x)(-r, r) = F m (y)(-r, r) for all integers 0 < m ≤ N + , we have x(r, 2r) = y(r, 2r).

Proof Let B n be the subset of (x, y) ∈ X × X such that x(-∞, -r -1) = y(-∞, -r -1), x(r, 2r) = y(r, 2r) and F m (x)(-r, r) = F m (y)(-r, r) for all m < n. Each B n is closed and B n+1 ⊂ B n . Positive expansiveness of F implies lim n→∞ B n = ∅ (see [START_REF] Blanchard | Ergodic properties of expansive one-sided cellular automata[END_REF]). Since X is a compact set, there is a positive integer N + such that B N + = ∅. ✷ Proposition 2 For a positively expansive CA acting on a bilateral subshift X, there is a constant Λ > 0 such that for all x ∈ X, λ ± (x) ≥ Λ.

Proof We give the proof for λ -(x) only, the proof for λ + (x) being similar.

Let r be the radius of the automaton. According to Lemma 1, for any point x ∈ X we obtain that if

y ∈ W - -1 (x) is such that F i (y)(-r, r) = F i (x)(-r, r) (∀ 1 ≤ i ≤ N + ) then y must be in W - r (x) ⊂ W - 0 (x). From the definition of I - N + (x) in (1), this implies that I - N + (x) ≥ 2r. Lemma 1 ap- plied N + times implies that for each 0 ≤ i ≤ N + , F n (F i (x)) (-r, r) = F n (F i (y)) (-r, r) for all 0 ≤ n ≤ N + . It follows that F i (x)(r, 2r) = F i (y)(r, 2r) (∀ 0 ≤ i ≤ N + ).
Using Lemma 1 once more and shifting r coordinates of x and y yields σ r (x)(r, 2r) = σ r (y)(r, 2r) ⇒ x(2r, 3r) = y(2r, 3r) so that I - 2N + (x) ≥ 3r. Hence, for each integer t ≥ 1, using Lemma 1, N + (t -1)! + 1 times yields x (tr, (t + 1)r) = y (tr, (t + 1)r) and therefore I tN + (x) ≥ (t + 1)r. Hence for all n ≥ N + and all x ∈ X, I - n (x) ≥ ( n N + + 1)r, so that

λ -(x) = lim n→∞ inf I - n (x) n ≥ r N + . ✷

Lyapunov Exponents and Entropy

Let F be a cellular automaton acting on a shift space A Z and let µ be a σ-ergodic and F -invariant probability measure. According to the inequality

h µ (F ) ≤ h µ (σ)(I + µ + I - µ )
proved in [8, Theorem 5.1], one has

I + µ + I - µ = 0 ⇒ h µ (F ) = 0.
Here we extend this result to the case of a σ and F -invariant measure on a sensitive cellular automaton.

Proposition 3 If F is a sensitive cellular automaton and µ a shift and Finvariant measure,

I + µ + I - µ = 0 ⇒ h µ (F ) = 0.
Proof Let α be a finite partition of A Z and α m n (x) be the element of the partition α ∨ σ -1 α ∨ . . . σ -n+1 α ∨ σ 1 α . . . ∨ σ m α which contains x. Using [8, Eq. ( 8)] we see that, for all finite partitions α,

h µ (F, α) ≤ A Z lim inf n→∞ -log µ(α I + n (x) I - n (x) (x)) I + n (x) + I - n (x) × I + n (x) + I - n (x) n dµ(x). (3)
Suppose that

I + µ + I - µ = lim inf n→∞ X n -1 (I + n (x) + I - n (x))dµ(x) = 0. From Fatou's lemma we have X lim inf n→∞ n -1 (I + n (x) + I - n (x))dµ(x) = 0. Since n -1 (I + n (x)+I - n (x)
) is always a positive or null rational, there exists a set S ⊂ A Z of full measure such that ∀x ∈ S we have lim inf n→∞ n -1 (I + n (x)+I - n (x)) = 0. Since F is sensitive, for all points x ∈ A Z , we have lim n→∞ I + n (x)+I - n (x) = +∞ (see [START_REF] Tisseur | Cellular automata and Lyapunov Exponents[END_REF]) and the Shannon-McMillan-Breiman theorem (in the extended case of Z actions see [START_REF] Kieffer | A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space[END_REF]) tells us that

A Z lim inf n→∞ - log µ(α I + n (x) I - n (x) (x)) I + n (x) + I - n (x) dµ = h µ (σ, α).
Since for all n and x,log µ(α

I + n (x) I - n (x) (x)
) > 0, we deduce that for all ǫ > 0 there is an integer M ǫ > 0 and a set S ǫ ⊂ S with µ(S ǫ ) > 1ǫ such that for all x ∈ S ǫ , 0 ≤ lim inf n→∞ log µ(α

I + n (x) I - n (x) (x)) I + n (x) + I - n (x) ≤ M ǫ .
For all x ∈ S ǫ we obtain φ(x) := lim inf n→∞ log µ(α

I + n (x) I - n (x) (x)) I + n (x) + I - n (x) × I + n (x) + I - n (x) n = 0,
which implies Sǫ φ(x)dµ(x) = 0. Using the monotone convergence theorem we deduce

A Z φ(x)dµ(x) = 0. It then follows from (3) that h µ (F ) = sup α h µ (F, α) = 0. ✷ 5
The cellular automaton and its natural factor

We define a cellular automaton for which the dynamic on a set of full measure is similar to the "counters dynamic" described in the introduction. The unbounded size counters are "simulated" by the finite configurations in the interval between two special letters "E". We will refer to these special symbols as "emitters". Between two E's, the dynamic of a counter is replaced by an odometer with overflow transmission to the right. We add "2" and "3" to {0; 1} in the set of digits in order to have the sensitive dynamic of counters with overflows transmission. The states 2 and 3 are interpreted as "0 + an overflow to be sent", and "1 + an overflow to be sent". Using this trick, we let overflow move only one site per time unit. Notice that 3 is necessary because it may happen that a counter is increased by 2 units in one time unit.

The cellular automaton

We define a cellular automaton F from A Z to A Z with A = {0; 1; 2; 3; E}. This automaton is the composition F = F d • F p of two cellular automata F d and F p . The main automaton F d is defined by the local rule

f d f d (x i-2 x i-1 x i ) = 1 E (x i )x i + 1 E (x i ) x i -2 × 1 {2,3} (x i ) + 1 {2,3} (x i-1 ) + 1 E (x i )1 E (x i-1 ) 1 + 1 {2} (x i-2 ) , (4)
where E = A \ {E} and,

1 S (x i ) = 1 if x i ∈ S, 0 otherwise.
The automaton F p is a "projection" on the subshift of finite type made of sequences having at least three digits between two "E" which is left invariant by F d . Its role is simply to restrict the dynamics to this subshift. It can be defined by the local rule f p

f p (x i-3 , . . . , x i , . . . x i+3 ) = 1 E (x i )x i + 1 E (x i )x i × 3 j=-3 j =0 1 E (x i+j ). (5)
The dynamic of F is illustrated in Figure 1 for a particular configuration. The projection f p prevents the dynamic of F to have equicontinuous points (points with "blocking words"EE") and simplifies the relationship between the cellular automaton and the model. The non-surjective cellular automaton acts surjectively on its ω-limit space X which is a non finite type subshift with a minimal distance of 3 digits between two "E". By definition, we have X = lim n→∞ ∩ n i=1 F i (A Z ). The set X is rather complicated. We do not want to give a complete description. Some basic remarks may be useful for a better understanding of the results. Note that the Es do not change after the first iteration and that x i = 3 implies x i-1 = E. We can show that the word

x = . . . 0 E 1 1 0 E 0 2 2 2 E . . . F (x) = . . . 0 E 2 1 0 E 1 0 1 1 E . . . F 2 (x) = . . . 0 E 1 2 0 E 2 0 1 1 E . . . F 3 (x) = . . . 0 E 2 0 1 E 1 1 1 1 E . . . F 4 (x) = . . . 0 E 1 1 1 E 2 1 1 1 E . . . F 5 (x) = . . . 0 E 2 1 1 E 1 2 1 1 E . . . F 6 (x) = . . . 0 E 1 2 1 E 2 0 2 1 E . . . F 7 (x) = . . . 0 E 2 0 2 E 1 1 0 2 E . . . F 8 (x) = . . . 0 E 1 1 0 E 3 1 0 0 E . . . F 9 (x) = . . . 0 E 2 1 0 E 2 2 0 0 E . . . (6)
Figure 1: An illustration of the dynamic of F defined by 5-4 on the configuration x, assuming that x is preceded by enough 0.

222 does not appear after the second iteration and that

F i (x)(k, k + 1) = 22 only if F i-1 (x)(k -2: k + 1) ∈ {2E21, 0E31, 1E31, 2E31}.
According to the definition (4), the evolution of finite configurations without emitter "E" leads to sequences which contains only the digits "1" and "0". This is the dynamic of the emitter "E" with the overflows crossing the "Es" that maintain and move the letters "2" and "3". There is at most two letters "2" between two consecutive letters "E". A typical word between two "E" is of the form E3uE, E2uE, E3u 1 2u 2 E or E2u 1 2u 2 E, where u, u 1 and u 2 are finite sequences of letters "0" and "1" (the words u 1 and u 2 can be empty). Notice that all possible words u, u 1 , u 2 do not appear in X. For example, the word E200E does not belong to the language of X.

As we want to study the dynamic on finite (but unbounded) counters, we define the set Ω ⊂ X of configurations with infinitely many E in both directions. This non compact set is obviously invariant by the dynamics. We are going to define a semi conjugacy between (Ω, F ) and the model in the next section.

The natural factor

In order to make more intuitive the study of the dynamic of F and to define (see Section 7) a natural measure, we introduce the projection of this CA which is a continuous dynamical system that commutes with an infinite state 1-dimensional shift.

The word between two consecutive Es can be seen as a "counter" that overflows onto its right neighbour when it is full. At each time step E "emits" 1 on its right except when the counter on its left overflows: in this case there is a carry of 1 so the E "emits" 2 on its right.

x = . . .

0 emitter i E 0 0 2 emitter i + 1 E 1 1 0 0 emitter i + 2 E . . . F (x) = . . . 0 E 1 0 0 counter i E 3 1 0 0 counter i + 1 E . . .
In what follows we call counter a triple (l, c, r), where l is the number of digits of the counter, c is its state and r is the overflow position in the counter. In Figure 1, in the first counter the countdown starts in F 5 (x) when the "2" is followed by "11". This "2" can propagate at speed one to the next emitter "E". Recall that Ω ⊂ X is a set of configurations with infinitely many Es in both directions and has at least three digits between two Es. Define the sequence (s j ) j∈Z of the positions of the Es in x ∈ Ω as follows:

s 0 (x) = sup {i ≤ 0 : x i = E}, s j+1 (x) = inf {i > s j (x) : x i = E} for j ≥ 0, s j (x) = sup {i < s j+1 (x) : x i = E} for j < 0.
Denote by u = (u i ) i∈Z = (l i , c i , r i ) i∈Z a bi-infinite sequence of counters. Let B = N 3 and σ B be the shift on B Z . We are going to define a function ϕ from Ω → B Z . We set for all i ∈ Z, l i (x) = s i+1 (x)s i (x) -1 and define d i (x) = s i+1 -1 j=s i +1 x j 2 j-s i -1 . We denote by c i = 2 l i the period of the counter (l i , c i , r i ).

For each x ∈ Ω and i ∈ Z we set c i (x) = d i (x) modulo c i (x) and we write

r i (x) = l i + 1 -max {j ∈ {s i + 1, . . . , s i+1 -1} : x j > 1} + s i if d i (x) ≥ c i (x) 0 otherwise. For each x ∈ Ω we can define ϕ(x) = (l i (x), c i (x), r i (x)) i∈Z . Remark that since r i (x) ≤ l i (x) and c i (x) ≤ 2 l i (x) , the set ϕ(Ω) is a strict subset (N 3 ) Z .
On ϕ(Ω), we define a dynamic on the counters through a local function. First we give a rule for incrementation of the counters. For a = 1 or 2, we set We define the local map h on

   (l i , c i , 0) + a = (l i , c i + a, 0) if c i < c i -a (R1) (l i , c i , 0) + a = (l i , c i + a -c i , l i ) if c i + a ≥ c i (R2) (l i , c i , r i ) + a = (l i , c i + a, r i -1) if r i > 0 (R3).
N 3 × N 3 by h(u i-1 u i ) = u i + (1 + 1 {r i-1 =1} (u i-1 )),
where the addition must be understood following the incrementation procedure above, with a = 1 + 1 {r i-1 =1} (u i-1 ). Let H be the global function on (N 3 ) Z . This is a "cellular automaton on a countable alphabet".

Note that, the (l i ) i∈Z do not move under iterations. At each step, the counter c i is increased by a modulo c i (a = 1 in general, while a = 2 if counter i -1 "emits" an overflow). When c i has made a complete turn r i starts to count down l i , l i -1 . . . 1, 0 ; after l i steps r i reaches 0, indicating that (in the automaton) the overflow has reached its position.

Remark 2 Notice that if 2l < 2 l , we cannot have c i = 2 la and r i > 0 since r i is back to 0 before c i-1 completes a new turn. This technical detail is the reason why we impose a minimal distance 3 (more than the distance one required for the sensitivity condition) between two successive E.

Semi conjugacy Proposition 4

We have the following semi conjugacy,

F Ω -→ Ω ↓ ϕ ↓ ϕ H ϕ(Ω) -→ ϕ(Ω) with ϕ • F = H • ϕ. Proof Let x ∈ Ω. Denote ϕ(x) = (l i , c i , r i ) i∈Z , x ′ = F (x) and ϕ(x ′ ) = (l ′ i , c ′ i , r ′ i ) i∈Z .
We have to prove that (l i , c i , r i ) + 1 +

1 {r i-1 =1} = (l ′ i , c ′ i , r ′ i )
where the addition satisfies the rules R 1 , R 2 , R 3 .

First, we recall that the Es do not move so that l ′ i = l i . Consider the first digit after the ith emitter

E :x ′ s i +1 = x s i +1 -2 × 1 {2,3} (x s i +1 )+1+1 {2} (x s i -1
). Clearly we have r i-1 = 1 if and only if

x s i -1 = 2 so x ′ s i +1 = x s i +1 +1+1 {r i-1 =1} -2×1 {2,3} (x s i +1 ). For all s i +2 ≤ j ≤ s i+1 -1, x ′ j = x j -2 × 1 {2} (x j ) + 1 {2,3} (x j-1 ). Since d i (x) = s i+1 -1 j=s i +1 x j 2 j-s i -1 , if x s i+1 -1 = 2 then d i (x ′ ) = d i (x) + 1 + 1 {r i-1 =1} and if x s i+1 -1 = 2 then d i (x ′ ) = d i (x) + 1 + 1 {r i-1 =1} -2 × 2 -l i = d i (x) + 1 + 1 {r i-1 =1} -c i . As c ′ i = d i (x ′ ) mod c i then for all x ∈ Ω one has c ′ i = c i + 1 + 1 {r i-1 =1} mod c i . It remains to understand the evolution of the overflow r i . First, notice that if d i (x ′ ) = c i = 2 l i then x ′ (s i , s i+1 ) = E21 (l i -1) E and if d i (x ′ ) = c i + 1 = 2 l i +1 then x ′ (s i , s i+1 ) = E31 (l i -1) E. After l i iteration of F , the configurations E21 (l i -1) E and E31 (l i -1) E have the form Ew2E. The maximum value taken by d i (x) is when x(s i , s i+1 ) = Eu2E where d i (z) < 2l i if z(s i , s i+1 ) = Eu0E.
As noted in Remark 2, the counters, which have at least a size of 3, have not the time to make a complete turn during the countdown (2l i < c i ) which implies that d i (x) ≤ c i + 2l i < 2c i . Since each counters can not receive an overflow at each iteration then d i (x) < 2c i -2 (when l i ≥ 3, l i-1 ≥ 3, θ × l i < c i -2 = 2 l i -2 where θ < 2 ). Clearly r i = 0 if and only if

d i = c i < c i (addition rule R 1 ). As d i < 2c i -2, if c i = c i -2 = d i (x) and x s i -1 = 2 or c i = c i -1 = d i (x) (r i = 0) then x ′ (s i , s i+1 ) = E21 (l i -1) E or x ′ (s i , s i+1 ) = E31 (l i -1) E which implies that r ′ i = l i (addition rule R 2 ). Now remark that if r i > 0 then x(s i , s i+1 ) = Eu21 k E with 0 ≤ k ≤ l i -1
and u is a finite sequence of letters "0", "1", "2" or "3". Using the local rule of F , we obtain that the letter "2" move to the right of one coordinate which implies that r ′ i = r i -1 (addition rule R 3 ). ✷

Remark 3

We remark that ϕ is not injective. Consider the subset of X defined by

Ω * = Ω ∩ {x ∈ {0, 1, E} Z : x 0 = E}.
It is clear that ϕ is one to one between Ω * and ϕ(Ω) since the origin is fixed and there is only one way to write the counters with 0 and 1. We will use this set, keeping in mind that it is not invariant for the cellular automaton F .

Remark 4 If x ∈ A Z , we use c i (x) to denote c i (ϕ(x)) and l i (x) instead of l i (ϕ(x)). This should not yield any confusion. To take the dynamics into account, we write

c t i (x) = c i (ϕ(F t (x))) = c i (H t (ϕ(x)
)) and similarly for l i (x) and r i (x). Note that l t i (x) = l i (x) for all t.

Limit periods

The natural period of the counter i, is its number of states, say c i . We introduce the notion of real period or asymptotic period of a counter which is, roughly speaking, the time mean of the successive observed periods. It can be formally defined as the inverse of the number of overflow emitted by the counter (to the right) per unit time. More precisely, we define N i (x), the inverse of the real period p i (x) for the counter number i in x by

N i (x) = lim t→+∞ 1 t t k=0 1 {1} (r t i (x)).
Lemma 2 The real period p i (x) exists and, N i (x) =

1 p i (x) = -∞ k=i 2 -k j=i l j (x) .
Proof Let n t i be the number of overflows emitted by the counter i in x before time t.

n t i (x) = t k=0 1 {1} (r t i (x)).
The number of turns per unit time is the limit when t → +∞ of n t i /t if it exists. We can always consider the limsup N + i and the liminf N - i of these sequences.

After t iterations, the counter indexed by i has been incremented by t (one at each time step) plus the number of overflow "received" from the counter (i-1). We are looking for a recursive relationship between n t i and n t i-1 . Some information is missing about the delays in the "overflow transmission", but we can give upper and lower bounds.

The number of overflows emitted by counter i at time t is essentially given by its initial position + its "effective increase" -the number of overflows delayed, divided by the size c i of the counter. The delay in the overflow transmission is at least l i . The initial state is at most c i . Hence, we have,

n t i (x) < c i (x) + t + n t i-1 (x) c i (x)
and,

n t i (x) > t + n t i-1 (x) -l i (x) c i (x) .
So for the limsup N + i and liminf N - i , we obtain

N ± i = 1 c i (1 + N ± i-1
). Remark that for all t ∈ N we have

N + i -N - i = 1 c i (N + i-1 -N - i-1 ) = ( 1 c i )(N + i-t - N - i-t ). Since 1 c i ≤ N - i ≤ N + i ≤ 2 c
i , the limit called N i exists and finally we have

N i (x) = -∞ k=i k j=i c -1 j (x) = -∞ k=i 2 -k j=i l j (x) . (7)
✷ Remark 5 The series above are lesser than the convergent geometric series ( n k=1 2 -3k ) n∈N since l i is always greater than 3. Note that in the constant case, l i = L, the limit confirm the intuition because the period is

p = 1 N i = 1 +∞ k=1 2 -kL = 2 L -1.

Sensitivity

For the special cellular automata F , we say that a measure µ satisfies conditions (*) if for all l ∈ (N) Z one has µ(A Z \ Ω) = 0 and µ({x ∈ Ω : (l i (x)) i∈Z = l}) = 0. These "natural" conditions are satisfied by the invariant measure µ F we consider (see Section 7, Remark 6).

Proposition 5

The automaton F is sensitive to initial conditions. Moreover, it is µ-expansive if µ satisfies condition (*).

Proof Fix ǫ = 2 -2 = 1 4 as the sensitive and µ-expansive constant. When x ∈ Ω, it is possible to define l(x) which is the sequence of the size of the counters for x and to use the model (H, ϕ(Ω)) to understand the dynamic.

We can use Lemma 2 to prove that for the model, if we modify the negative coordinates of the sequence l i we also modify the asymptotic behaviour of the counter at 0. Such a change in the asymptotic behaviour implies that at one moment, the configuration at 0 must be different. From the cellular automaton side, we will show that a change of the real period of the "central counter" will affect the sequences (F t (x)(-1, 1)) t∈N which is enough to prove the sensitivity and µ-expansiveness conditions.

For each x ∈ Ω with x 0 = E, consider the sequence l [0,-∞] (x) = l 0 (x)l -1 (x) . . . l -k (x) . . .. We claim that if l [0,-∞] (x) = l [0,-∞] (y) then N 0 (x) = N 0 (y). Let j be the first negative or null integer such that l j (x) = l j (y). By Lemma 2, there exists a positive real

K 1 = j-1 k=0 2 -k i=0 l i (x)
such that

N 0 (x) = K 1 + K 1 2 -l j (x) + K 1 2 -l j (x) ( ∞ k=j+1 2 -k i=j+1 l i (x) )
and

N 0 (y) = K 1 + K 1 2 -l j (y) + K 1 2 -l j (y) ( ∞ k=j+1 2 -k i=j+1 l i (y) ).
So writing K 2 = K 1 2 -l j (x) we obtain

N 0 (x) -N 0 (y) > K 2 2 - K 2 2 ( ∞ k=j+1 2 -k i=j+1 l i (y) ).
As ∞ k=i+1 2 -k j=i+1 l j (y) is less than the geometric series ∞ k=0 2 -3k = 1 7 we prove the claim.

If x 0 = E, using the shift commutativity of F we obtain that if

l [-1,-∞] (x) = l [-1,-∞] (y) then N -1 (x) = N -1 (y).
Remark that for each x ∈ Ω and δ = 2 -n > 0, there exists y ∈ Ω such that y i = x i for i ≥ -n and l(x) = l(y) (sensitivity conditions). We are going to show that if l i (x) = l i (y) (i < 0; x ∈ Ω) then there exist some t ∈ N such that F t (x)(-1, 1) = F t (y)(-1, 1).

First, we consider the case where x 0 = E. In this case, since N -1 (x) = N -1 (y), there is t such that n t -1 (x) = n t -1 (y). At least for the first such t, r t -1 (x) = r t -1 (y) since r t -1 (x) = 1 and r t -1 (y) = 1. But this exactly means that x t -1 = 2 and y t -1 = 2. Hence x t -1 = y t -1 . Next assume that x 0 = E. We have N 0 (x) > N 0 (y). This implies that n t 0 (x)n t 0 (y) goes to infinity. Hence the difference c t 0 (x)c t 0 (y) (which can move by 0, 1 or -1 at each step) must take (modulo c 0 ) all values between 0 and c 0 -1. In particular, at one time t, the difference must be equal to 2 -T 0 -1 . If x -1 = E, then T 0 = -1 which implies that x t 0 = y t 0 . Otherwise, in view of the conjugacy, it means that

T 1 -1 i=T 0 +1 x t i 2 i-T 0 -1 - T 1 -1 i=T 0 +1 y t i 2 i-T 0 -1 = 2 -T 0 -1 (modulo c 0 ),
that is, either x t 0 = y t 0 or x t 0 = y t 0 and x t -1 = y t -1 . We have proved the sensitivity of F for x ∈ Ω.

To show that x ∈ Ω satisfies the µ-expansiveness condition, we need to prove that the set of points which have the same asymptotic period for the central counter is a set a measure zero. For each point x the set of all points y such that F t (x)(-1, 1) = F t (y)(-1, 1) or d(F t (x), F t (y)) ≤ 1 4 (t ∈ N), is denoted by D(x, 1 4 ). Following the arguments of the proof of the sensitivity condition above, we see that every change in the sequence of letters "Es" in the left coordinates will affect the central coordinates after a while, so we obtain that D(x, 1 4 ) ⊂ {y : l i (y) = l i (x) : i < 0}. Since µ satisfies condition (*), we have µ(D(x, 1 4 )) = 0 which is the condition required for the µ-expansiveness. Now suppose that x ∈ {0, 1, 2, 3, E} Z \ Ω. First notice that if there is at least one letter E in the left coordinates, the sequence F t (x)(-1, 1) does not depend on the position or even the existence of a letter E in the right coordinates. Recall that after one iteration, the word 22 appears only directly after a letter E. So when there is at least one letter E in the negative coordinates of x, the arguments and the proof given for x ∈ Ω still work.

If there is no letter E in the negative coordinates of x, for any δ = 2 -n , we can consider any y ∈ Ω such that y i = x i if -n ≤ i ≤ n. For x ∈ {0, 1, 2} Z , the dynamic is only given by the letter 2 which move on sequences of 1 (see Figure 1). The sequence F t (x)(-1, 1) can not behave like a counter because it is an ultimately stationary sequence (after a letter "2" pass over a "1" it remains a "0" that can not be changed) and the real period of the central counter of y is obviously strictly greater than 1. Then in this case again, the sequences F t (x)(-1, 1) and F t (y)(-1, 1) will be different after a while which satisfies the sensitivity condition. Since the only points z such that F t (z)(-1, 1) = F t (x)(-1, 1) belong to the set of null measure {0, 1, 2, 3} Z (as µ satisfies conditions (*)), we obtain the µ-expansiveness condition. ✷

7 Invariant measures 7.1 Invariant measure for the model

We construct an invariant measure for the dynamics of the counters. Firstly, let ν * denote a measure on N\{0, 1, 2} and secondly, let ν = ν ⊗Z * be the product measure. To fix ideas, we take ν * to be the geometric law of paramater ν = 2 3 on N conditionned to be larger than 3, i.e.,

ν * (k) = ν k j>2 ν j if k ≥ 3 0 if k < 3.
Notice that the expectation of l 0 is finite : l 0 >2 ν * (l 0 ) × l 0 < +∞. We denote by m L the uniform measure on the finite set {0, . . . , L -1}. Given

Lyapunov exponents

Recall that no information can cross a counter before it reaches the top, that is, before time 1 2 (c ic i ) since at each step the counter is incremented by 1 or 2. When the information reaches the next counter, it has to wait more than 1 2 (c i+1c i+1 ), where this quantity is estimated at the arrival time of the information, and so on.

But each counter is uniformly distributed among its possible values. So expectation of these times is bounded below by 1 4 E[c i ] = E[2 l i -2 ]. A good choice of the measure ν can make the expectation of the l i finite so that we can define the invariant measure µ F . But E[2 l i ] is infinite so that expectation of time needed to cross a counter is infinite and hence the sum of these times divided by the sum of the length of the binary counters tends to infinity.

Instead of being so specific, we use a rougher argument. Taking ν * to be geometric, we show that there exists a counter large enough to slow the speed of transmission of information. That is, for given n, there is a counter of length larger than 2 ln n, information needs a time of order n δ , with δ > 1 to cross. This is enough to conclude.

Proposition 7

We have

I + µ F + I - µ F = 0.
Proof We just have to show that I + µ F = 0 since I - µ F is clearly zero. Recall that I + n (x) is the minimal number of coordinates that we have to fix to ensure that for all y such that as soon as y(-I + n (x), ∞) = x(-I + n (x), ∞), we have F k (y)(0, ∞) = F k (x)(0, ∞) for all 0 ≤ k ≤ n. Let t F (n)(x) = min{s : ∃y, y(-n, ∞) = x(-n, ∞) and F s (x)(0, ∞) = F s (y)(0, ∞)} be the time needed for a perturbation to cross n coordinates. Note that t F (n) and I + n are related by t F (s)(x) ≥ n ⇔ I + n (x) ≤ s. We now define an analog of t F (n) for the model. For all x ∈ ϕ(Ω), let M n (x) be the smallest negative integer m such that 0 i=m l i (x) ≤ n. Define t H (n)(x) = min s ≥ 0 : ∃y ∈ Ω, y(M n (x), ∞) = x(M n (x), ∞), H s (x)(0, ∞) = H s (y)(0, ∞) .

Define for all large enough positive integer, the subset of Ω

Questions

We end this paper with a few open questions and conjectures.

Conjecture 1

The measure µ F is shift-ergodic.

The measure µ F is clearly not F -ergodic since the Es do not move. It is still not clear to us whether or not it is possible to construct a sensitive automaton with null Lyapunov exponents for a F -ergodic measure. 10 References

  are called right and left set of all the perturbations of x, respectively.

u

  = . . . (3, 3, 0) (4, 0, 0) . . . H(u) = . . . (3, 4, 0) (4, 1, 0) . . . H 2 (u) = . . . (3, 5, 0) (4, 2, 0) . . . H 3 (u) = . . . (3, 6, 0) (4, 3, 0) . . . H 4 (u) = . . . (3, 7, 0) (4, 4, 0) . . . H 5 (u) = . . . (3, 0, 3) (4, 5, 0) . . . H 6 (u) = . . . (3, 1, 2) (4, 6, 0) . . . H 7 (u) = . . . (3, 2, 1) (4, 7, 0) . . . H 8 (u) = . . . (3, 3, 0) (4, 9, 0) . . . H 9 (u) = . . . (3, 4, 0) (4, 10, 0) . . .

Figure 2 :

 2 Figure 2: The dynamic in Figure 1 for the natural factor.

  x) ≤ 2 ln(n), ∃i ∈ {M n (x), . . . , -1}, l i (x) ≥ 2 ln(n), c i (x) ≤ 2 l i (x) -2 1.5 ln(n)

Conjecture 2 AConjecture 3

 23 sensitive cellular automaton acting surjectively on an irreducible subshift of finite type has average positive Lyapunov exponents if the invariant measure we consider is the Parry measure on this subshift. If a cellular automaton has no equicontinuous points (i.e. it is sensitive), then there exists a point x such that lim inf I + n (x) n

a two-sided sequence l = (l i ) i∈Z , we define a measure on N Z supported on i∈Z {0, . . . , 2 l i -1}, defining m l = ⊗ i∈Z m 2 l i , so that for all k 0 , . . . , k m integers, m l ({c i = k 0 , . . . , c i+m = k m }) = 2 -i+m j=i l j if, ∀i ≤ j ≤ i + m, c j < 2 l j 0 otherwise.

We want this property for the counters to be preserved by the dynamics. But, for the overflow, we do not know a priori how the measure will behave.

Next we construct an initial measure and iterate the sliding block code on the counters H. For all l = (l i ) i∈Z , we set ν l = ⊗ i∈Z δ l i , and, η = ⊗ i∈Z δ 0 , where δ k denotes the Dirac mass at integer k. We consider the measures µ H l = ν l ⊗ m l ⊗ η, which give mass 1 to the event {∀i ∈ Z, r i = 0}. Then, we define, μH =

The sequence

μH • H -k has convergent subsequences. We choose one of these subsequences, (n i ), and write

Invariant measure for F

Now we construct a shift and F -invariant measure for the cellular automaton space.

Recall that Ω * = Ω ∩ {x ∈ {0, 1, E} Z : x 0 = E} (see Remark 3). We write, for all integer k, Ω * k = σ k Ω * . Let us define, for all measurable subsets

This measure distributes the mass on the l 0 points with the same image (in the model) corresponding to the l 0 possible shifts of origin. The total mass of this measure is l 0 . Since the expectation of

The measure μF is shift-invariant (see further) but it is supported on a non F -invariant set. In order to have a F -invariant measure we take an adherence value of the Cesaro mean. We choose a convergent subsequence (n i j ) of the sequence (n i ) defining µ H and write

Remark 6 Since for the measure µ F , the length between two "Es" follows a geometric law, the measure µ F satisfies the conditions (*) defined in Section 6, and from Proposition 5, the automaton F is µ F -expansive.

Lemma 3

The measure µ H is σ B and H-invariant. The measure µ F is σ and F -invariant. For all measurable subsets U of ϕ(Ω) such that l 0 is constant on U,

Proof The shift invariance of µ H follows from the fact that ν is a product measure and that the dynamic commutes with the shift so the Cesaro mean does not arm. H and F invariance of µ H and µ F follow from the standard argument on Cesaro means.

Shift invariance of µ F comes from a classical argument of Kakutani towers because µ H is essentially the induced measure of µ F for the shift on the set Ω * . We give some details. We choose a measurable set I such that l 0 is constant on

) . Now we integrate with respect to l and use the σ -1 B -invariance of μH to conclude that μF (σ -1 I) = μF (I).

For a measurable set I, we decompose I = ∪ L∈N (I ∩ {x ∈ Ω : l 0 (x) = L}). Since F commutes with σ, the Cesaro mean does not affect the shift invariance. Hence, µ F is shift invariant. Now, we make explicit the relationship between µ H and µ F . Let V ⊂ Ω be an event measurable with respect to the σ-algebra generated by (l i , c i ; i ∈ Z). There is an event

Integrating with respect to l gives

If l 0 is constant on U then L = l 0 and we get

Proof Let F be the σ-algebra generated by {(c j , r j )|j < 0} and {l j , j ∈ Z}. We claim that, almost surely,

Remark that the last claim implies µ

We prove the claim by taking the Cesaro mean and by going to the limit. We extend the result to all integer i using the shift invariance and the independence of c i with respect to l j when j > i. We conclude by applying Lemma 3:

otherwise.

Proposition 6

The shift measurable entropy of h µ F (σ) is positive.

Proof Let α be the partition of Ω by the coordinate 0 and denote by α n -n (x) the element of the partition α ∨ σ -1 α... ∨ σ -n+1 ∨ σ 1 ... ∨ σ n α which contains x. It follows from the definition of µ F , that µ F (α n -n (x)) ≤ ν l(y) ∈ N Z : y ∈ α n -n (x) . For all x ∈ Ω there exist sequences of positive integers (-

Since

By the probabilistic version of the Shannon-McMillan-Breiman theorem for a Z-action [START_REF] Kieffer | A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space[END_REF], the left side of the previous inequality is equal to h F µ (σ), so we can conclude. ✷

We claim that

Choose and fix an integer n large. Note that if ∀i ∈ {M n (x), . . . , 0}, l i ≤ 2 ln(n), we have

Note that on {l 0 ≤ 2 ln n}, existence of i ≥ M with l i ≥ 2 ln n yields existence of i ≥ M n (x) ≥ M with l i ≥ 2 ln n (the same i).

Given a L = (L M , . . . , L 0 ) in the complementary of V n denoted by V c n , we denote V Ω L = {x ∈ Ω : (l M (x), . . . , l 0 (x)) = L} and we denote i(L) the larger index

According to Lemma 4, given the l i 's, for M ≤ i ≤ 0, the random variable c i is uniformly distributed. Hence for all L ∈ V c * n , 2) , so that

, and the l i 's are independent, it is straightforward to prove the existence of constants c 1 , c 2 and c 3 independent on n, such that,

We conclude that

Since ν = 2 3 , 2 ln(ν) < 1, this bound converges to 0 and the claim follows.

Now, we claim that there is a constant c > 0 and a constant δ > 1 such that on U n , we have

Notice that i < 0 because x ∈ U n . For all s ≤ 1 2 2 1.5 ln(n) , we have r s i (x) = r s i (y) = 0, since c s i (x) < 2 l i (x) . Hence, for all j > i (and in particular for j = 0), c s j (x) = c s j (y). For j = 0, this implies that t H (n)(x) ≥ 1 2 n 1.5 ln 2 . As 1.5 ln(2) > 1 the claim holds.

There is no y with y(-n, ∞) = x(-n, ∞) and F s (x)(0, ∞) = F (y)(0, ∞) if s < t H (n)(x) because y(-n, ∞) = x(-n, ∞) ⇒ ϕ(y)(-M(x, n), ∞) = ϕ(x)(-M(x, n), ∞). This implies that t F (n)(x) ≥ t H (n)(x). It follows that t F (n)(x) ≥ cn δ on U n .

Setting s = n 1 δ , we see that t F ( n

. We deduce that there is a constant c such that, on U n ,

is bounded (by r = 2, radius of the automaton), the conclusion follows from the inequality

That is, I + µ F = 0. ✷ Using Proposition 3 we obtain Corollary 1 The measurable entropy h µ F (F ) is equal to zero.


Guillaume Holley
email: guillaumeholley@gmail.com

Pierre Peterlongo
email: pierre.peterlongo@inria.fr

BlastGraph: intensive approximate pattern matching in string graphs and de-Bruijn graphs

Keywords: string graph, de-Bruijn graph, string matching, high throughput sequencing, next generation sequencing, sequence assembly, Viterbi algorithm

Many de novo assembly tools have been created these last few years to assemble short reads generated by high throughput sequencing platforms. The core of almost all these assemblers is a string graph data structure that links reads together. This motivates our work: BlastGraph, a new algorithm performing intensive approximate string matching between a set of query sequences and a string graph. Our approach is similar to blast-like algorithms and additionally presents specificity due to the matching on the graph data structure. Our results show that BlastGraph performances permit its usage on large graphs in reasonable time. We propose a Cytoscape plug-in for visualizing results as well as a command line program. These programs are available at http://alcovna.genouest.org/blastree/.

Introduction

Compared to traditional Sanger technologies High Throughput Sequencing (HTS) technologies enable sequencing of biological material (DNA and RNA) at much higher throughput and a cost that is now affordable by most academic labs. They have revolutionized the field of genomics and medical research [START_REF] Feature | Next-generation sequencing transforms todays biology[END_REF]. Sequencing became in a few years accessible to almost all biological labs while being able to produce sequences of full complex genomes in a few days.

HTS technologies do not output the entire sequence of a DNA or RNA molecule. Instead, they return small sequence fragments, called reads, whose length is ranging between 100 to 700 characters. HTS produce overlapping reads, thus making possible to reconstruct the original sequence by assembling them. Over the last few years, many assemblers were created, such as Euler [START_REF] Chaisson | De novo fragment assembly with short mate-paired reads: Does the read length matter[END_REF][START_REF] Chaisson | Short read fragment assembly of bacterial genomes[END_REF], Velvet [START_REF] Zerbino | Velvet: Algorithms for de novo short read assembly using de bruijn graphs[END_REF] or Soapnovo [START_REF] Li | De novo assembly of human genomes with massively parallel short read sequencing[END_REF] to cite a few among the most famous ones. They present different capacities and drawbacks, but all of them make use of a string graph (SG) for organizing the reads. For assembly, the most used graph is the de-Bruijn graph (DBG), first proposed for assembly purposes by Pevzner, Tang and Waterman [START_REF] Pevzner | An Eulerian path approach to DNA fragment assembly[END_REF]. In a DBG a node represents a length-k substring (called a insertions, deletions and substitutions to transform one into the other. The length of s is denoted by |s|. We denote by s[i, j] the substring s[i]s[i + 1] . . . s[j] of s. In this case, we say that the substring s[i, j] occurs at position i in s. We call k-mer a sequence of length k. If s = u.v for u and v ∈ Σ * , we say that v is a suffix of s and that u is a prefix of s, the symbol "." designating the concatenation between two sequences. Let s[i..] denote the suffix of s starting at position i (i.e.

s[i..] = s[i, |s| -1]).
The symbol " k" designates the concatenation of two sequences, removing the first k symbols of the second. Formally, u kv = u.v[k..]. In the DNA context, Σ = {A, C, G, T }, and, given s ∈ Σ * , s designates the reverse complement of s, that is s, read from right to left, switching characters A and T , and C and G.

Directed string graph (SG)

In a directed string graph G, each node N stores a sequence s, denoted by S(N ). A node N 1 linked to a node N 2 denotes the fact that the sequence S(N 1 ).S(N 2 ) is stored in G. Example of a directed string graph is given Figure 1a.

De-Bruijn Graphs (DBG)

DBGs were first used in the context of genome assembly in 2001 by Pevzner et al. [START_REF] Pevzner | An Eulerian path approach to DNA fragment assembly[END_REF]. In 2007, Medvedev et al. [START_REF] Medvedev | Computability of models for sequence assembly[END_REF] modified the definition to better model DNA as a double stranded molecule. In this context, given a fixed k value, a DBG is a bi-directed multigraph, each node N storing a k-mer s and its reverse complement s. The sequence s, denoted by F (N ), is the forward sequence of N , while s, denoted by R(N ), is the reverse complement sequence of N . An arc exists from node N 1 to node N 2 if the suffix of length k -1 of F (N 1 ) or R(N 1 ) overlaps perfectly with the prefix of F (N 2 ) or R(N 2 ). Each arc is labelled with a string in {F F, RR, F R, RF }. The first letter of the arc label indicates which of F (N 1 ) or R(N 1 ) overlaps F (N 2 ) or R(N 2 ), this latter choice being indicated by the second letter. Because of reverse complements, there is an even number of arcs in the DBG: if there is an arc from N 1 to N 2 then, necessarily, there is an arc from N 2 to N 1 (e.g. if the first arc has label F F then the second has label RR).

A DBG can be compressed without loss of information by merging simple nodes. A simple node denotes a node linked to at most two other nodes. Two adjacent simple nodes are merged into one by removing the redundant information. A valid path (see Definition 2) composed by i > 1 simple nodes is compressed into one node storing a sequence of length k + (i -1) as each node adds one new character to the first node. Figure 1b represents a DBG (upper) and the corresponding compressed DBG (lower). In the remainder of the paper, we denote by cDBG a compressed DBG. Definition 1 (Active strand of a node in a DBG) The active strand of a node N in a DBG denotes which strand of the node, forward or reverse, is considered while traversing N .

Definition 2 (Valid path)

The traversal of a node N is said to be valid if the rightmost label (F or R) of the arc used for entering the node is equal to the leftmost label of the arc used for leaving the node.

A path in the graph is valid if for each node involved in the path, its traversal is valid, that is, each pair of adjacent arcs in the path are labelled, respectively, XY and Y Z with X, Y, Z ∈ {R, F }. Definition 3 (Sequence stored in a cDBG) A valid path in a cDBG composed by ordered nodes N 0 , N 1 , . . . , N l , stores two sequences as following:

1. s = F/R(N 0 ) kF /R(N 1 ) k . . . k F/R(N l ), the choice between R or F for node N 0
is equal the first label of the edge going from N 0 to N 1 , while for i ∈ [1, l], the choice between R or F for node N i is equal the second label of the edge going from N i-1 to N i .

s.

For instance, the arrowed path on the cDBG presented Figure 1b, stores the sequences

s = CAT CT kAT CT CCGCA kC GCAG = CAT CT.CCGCA.G = CAT

The BlastGraph algorithm

Blast like seed-based heuristics rest on the idea that if two sequences share some similarities, then there exists (at least) a common word (a seed) between these two sequences. Such algorithms consist in, first, anchoring the detection of similarities by exact matching of short sub-sequences, the seeds, and then, performing the similarity distance computation once sequences are anchored. The algorithm we propose applies these ideas between a graph (the bank) and a string (the query).

It is divided into four main stages:

1. Index all seeds present in the graph G.

2. Anchor query sequences to nodes of G using seeds. In the case of genomic data, reverse complement of query sequences may also be used as queries. 3. Align anchored query sequences on the left and right of the matched seeds. 4. Merge left and right alignments. In the four following sections, we provide some more details for each of these four stages simply considering the graph as a SG. Then, in Section 4, we describe the modifications needed for applying the algorithm on a cDBG.

Stage 1: Indexing the seeds

Let n denote the length of the seeds. Each word of length n of the sequence of each node of G as well as those spread over several linked nodes are indexed using a hash table. The index contains for each seed a set of its occurrence positions.

Occurrence position in a graph: An occurrence position in the graph is defined as a couple (node identifier N , position on S(N )) indicating the starting position of the occurrence.

Seeds spread over more than one node: Any seed starting at less than n positions to the end of the sequence of a node is spread over more than one node. For instance, the seed T CT ACGC starting at position 2 on the leftmost node of Figure 1a, is spread over two distinct nodes. Seeds spread over more than one node are detected thanks to a depth first algorithm recursive approach.

In order to make a light index, the BlastGraph algorithm only stores the starting position of a seed (node identifier N , position on S(N )) and not all possible nodes over which the seed is spread. For each query sequence Q, all overlapping words of length n (seeds) are read. Let s be such a seed occurring at position p on Q, also having at least one occurrence in the graph. Then the index provides a set of couples (node N , position on S(N )). For each such couple, the query Q is anchored on the sequence S(N ), giving a relative position rel(Q, N ) of Q on S(N ). More precisely, rel(Q, N ) = p-position on S(N ) (see Figure 2) is the position where Q aligns to S(N ). Note that rel(Q, N ) could be < 0 if a prefix of S(N ) is not aligned to Q. This is the case of S(Q, L 1 ) in the example presented Figure 3.

Stage 2: Anchoring query sequences to sequences of the graph

Computing an alignment only once: If a node N and a sequence Q share more than one seed for the same alignment, each of them generate the same value {rel(Q, N )}. As this is a very usual case, in order to avoid computing several times the same alignments, while aligning sequence Q, the values {rel(Q, N )} is stored in memory. Thus, the same alignment anchored at position {rel(Q, N )} is computed only once.

Stage 3: Alignment between query sequence and string graph nodes

Given a query sequence Q anchored at position {rel(Q, N )} to a node N of the graph, this stage computes all possible alignments (based on edit distance) between Q and all paths readable from node N (see Figure 3 for an example).

Computing the edit distance between two strings is a dynamic programming procedure that involves the usage of a matrix of size the product of the string .] and S(B 1 ), and so on. In this example, path using node A 1 presents an edit distance higher than the threshold; its children are not explored. Left Alignment: the same procedure is applied on the sequence on the left of the seed (left dotted square in node N ), then on parents L 0 , L 1 of node N , and so on . . . lengths. However, in the particular case of this work, the user restricts the maximal edit distance for having a match. Consequently, the matrix computation is limited to a diagonal (see Figure 4

Right alignments

The alignment is done between Q and S(N ) on the right of the matched seed. Additionally, as shown Figure 3, right extremity of the query sequence may finish after S(N ). In such a case the alignment has to be done on children A 0 , A 1 , . . . , A n of node N . On each child A i , the right extremity of the query sequence may finish after the S(A i ), in this case, alignment continues on its children B 0 , B 1 , . . . , B n ′ , and so on. Thus, right part of sequence Q (starting after the anchored seed), may be aligned to S(N.A i .B j ....). This is done via a recursive depth-first traversal of the graph, starting from N as long as the full right part of S is not aligned. An alignment between the sequence of a node and Q is never computed twice. For instance (Figure 3), if the alignment between Q and S(N.A 0 .B 0 ) was computed, the computation between Q and S(N.A 0 .B 1 ) starts from the last full line of the alignment of Q with S(N.A 0 ). Thus the alignment between Q and S(N ) and S(A 0 ) is never recomputed.

Left alignments Aligning the part of the sequence Q on the left of the seed to the graph is done using almost the same approach as the one previously described for right alignments. However, there are two main differences: 1) Sequences both from Q and from the nodes are reversed (read from right to left); 2) when the reversed query sequence is longer than the reversed sequence of a node N , the parents L 0 , L 1 , ... of N are explored in depth first search approach (see Figure 3 for an example).

Joining left and right alignments

For a given aligned query sequence, each left alignment is compared to each right alignment. For each such couple whose sum of the cost of the alignments is below or equal the user defined maximal edit distance, the full alignment is reported.

BlastGraph on compressed de-Bruijn graphs

The three main differences between the SG and the cDBG are: 1. In the cDBG, the sequences of two connected nodes overlaps over k -1 characters. Thus, whatever the stage, the concatenation of the sequences of two nodes of the cDBG, has to be done removing the k -1 overlapping characters using the " k" concatenation instead of the classical "." one. 2. In the cDBG, each node N stores a sequence (F (N )) and its reverse complement (R(N )). 3. Label of edges have to be considered while traversing the graph. Thus, in the cDBG, the general rule is the following: a node N is always traversed either as forward (F (N )) or as reverse complement (R(N )), with F or R being its "active strand" (see Definition 1).

In the first case (resp. second case), accessing the children of the node is done following edges starting with the letter F (resp. R).

While following an edge, the active strand of the targeted node F (resp. R) is the second letter of the label of the edge.

Seeding in a DBG: The seeding approach is the same than the one applied on the SG. By convention, all seeds start on forward sequence of each node. This is done without loss of information as each query is considered both in its forward and its reverse complement directions.

Right extension in a DBG: The right extension in a DBG is the same as the one described for a SG. However, the algorithm takes into account some DBG specificities:

query sequence is mapped on F (N ) (seeds are indexed only on forward strands); -children of a node N are reached using only outgoing edges whose label first character corresponds to the active strand of N , and, once a child is reached, its active strand is the one corresponding to the second character of this label; -concatenation of sequences of two linked nodes is done pruning the overlapping k -1 characters.

Left extension in a DBG: Left extensions in the DBG are done by right extending the reverse complement Q of the sequence Q to the DBG, starting from the reverse strand of the node N : R(N ).

Results

Two prototype versions of this algorithm are implemented. Under the CeCILL License, they can be downloaded here: http://alcovna.genouest.org/blastree. A Java version is implemented in a Cytoscape plug-in. Cytoscape [START_REF] Smoot | Cytoscape 2.8: new features for data integration and network visualization[END_REF] is an opensource platform for visualization and interaction with complex graph, especially in bioinformatics. The second version is implemented in C and can be run under Unix platforms. In the two prototypes, while working on nucleotides, characters are coded on two bits. The next section proposes a use case of the Java version, while section 5.2 proposes some results over the C prototype.

Use case

We present in this section a use case, on a toy example. We created a string graph containing five nodes (Figure 5). We searched for the sequence ggcgT tcagac/cT atacgcatacgcagcagact/agCctacg, spreads over 3 nodes of this graph and containing two mismatches and one insertion. To help the reader, we indicated here substitutions and indel with an upper case letter and we indicated separations between nodes with a '/' character. Of course the practical query sequence is a raw un-annotated sequence. We fixed the cost of a mismatch to 1, the cost of an indel to 2 and the maximal edit distance to 4. BlastGraph (Cytoscape plug-in version)) found the correct path, as presented Figure 5 where selected nodes are those in which alignment in found between the query and the graph.

Performances on DBG

We present results obtained in a typical use case while applying BlastGraph on a DBG graph. Results were obtained on a 64 bit 2x2.5 GHz dual-core computer with 3 MB cache and 4 GB RAM memory. From the NCBI Sequence Read Archive (SRA, http://www.ncbi.nlm.nih.gov/Traces/sra), we downloaded the DRR000096 Illumina run containing approximately 4 million reads and approximately 150 millions of nucleotides.

Increasing graph sizes Subsets of different sizes were generated by randomly sampling DRR000096 reads. For each subset, we constructed the de-Bruijn graph using k=31. On each graph, we applied the C version of BlastGraph, aligning a set of 10000 query sequences derived from the initial read set. We used seeds of length 19, a mismatch cost equal to 1 and an indel cost equal to 2 and a maximal edit distance equal to 5. We report Figure 6 time and memory needed both for constructing the index and for performing the 10000 queries.

We can observe that memory footprint and both indexation and query execution times increase linearly with the quantity of information contained in the Increasing number of queries In order to measure the impact of the number of queries on the execution time, we used the graph composed of 100000 reads from the DRR000096 data set using k = 31. We ran BlastGraph using queries dataset composed of 500, 1000, . . . 10000 reads taken from the 100000 reads used for creating the graph. We report the query time (not including the indexation time) Figure 7. We note that, as expected, the query time increases slowly and linearly with the number of queries.

Conclusion

We presented BlastGraph, a new algorithm for performing intensive approximate string matching between a set of query sequences and a string graph including the application to de-Bruijn graphs. This blast-like algorithm presents novelties with respect to classical blast-like approaches as seeds and alignments may be spread over several nodes and as the algorithm takes into account double stranded de-Bruijn graph features. Results showed that BlastGraph performances permit its usage on quite large graphs in reasonable time.

The main bottleneck of the approach comes from the memory footprint. Storing in memory graphs containing hundreds of millions of nucleotides together with seed index is challenging. Future work will include a non indexed version of the algorithm, for instance based on KMP [START_REF] Knuth | Fast pattern matching in strings[END_REF] algorithm. This will increase the query time, while decreasing the memory usage. Such a version would fit a unique or a limited number of query sequences. On the other hand, future work will also consist in modelling and implementing new data structures storing the graph together with their associated index. Possible applications will exceed the frontiers of the current work as this problem is central in many algorithms associated to high throughput sequencing problems.

Figure 1 :

 1 Figure 1: (a) Directed string graph. (b) Uncompressed (upper) and compressed (lower) de-Bruijn Graphs with k = 5. For each node, lower text is the reverse complement of the upper text, it should be read from right to left. Boxes both on (a) and (b): example of a seed of length 7 (TCTACGC) spread over 2 nodes. In the de-Bruijn Graph, the k -1 first characters of the second node are pruned due to overlap, and the reverse part of the second node is considered as the edge between the first (left) and the second (central) node is FR.

Figure 2 :

 2 Figure 2: Value rel(Q, N ) while anchoring a query sequence Q on a node N with a seed.

Figure 3 :

 3 Figure 3: Overview of the alignment process. Anchoring: Using a seed, a query sequence Q is anchored to the node N . Right alignment: edit distance is computed between Q[rel(Q, N ) + i + k..] and S(N )[i + k..] (right dotted square in node N ), then between Q[rel(Q, A 0 )..] and S(A 0 ), between Q[rel(Q, B 0 )..] and S(B 0 ), between Q[rel(Q, B 1 )..] and S(B 1 ), and so on. In this example, path using node A 1 presents an edit distance higher than the threshold; its children are not explored. Left Alignment: the same procedure is applied on the sequence on the left of the seed (left dotted square in node N ), then on parents L 0 , L 1 of node N , and so on . . .

  for an example) of width maximal edit distance cost indel × 2. Outside the diagonal, number of insertions or deletions becomes bigger than maximal number of insertions or deletions accepted equal to maximal edit distance cost indel . Thus during this stage, the time and memory complexity for aligning query Q to one path of the graph is in O (|Q|) considering maximal edit distance and cost indel as fixed parameters.

Figure 4 :

 4 Figure 4: Dynamic programming matrix. Only the shadowed diagonal is computed. (a) distance computed between the query sequence S and S(N.A i ). (b) distance computed between S and S(N.A i+1 ). Lighter lines are not recomputed for computing matrix (b) if matrix (a) was already computed.

Figure 5 :

 5 Figure 5: Cytoscape view of the selected nodes (green) in the string graph after the research of query sequence.

Figure 6 :

 6 Figure 6: Time and memory consumption with respect to the number of nucleotides stored in the graph

Figure 7 :

 7 Figure 7: Query time with respect to the number of queries. Note that reported time do not include the indexation time equal to 22 seconds independently of the number of queries.

  CT CCGCAG and s = CT GCGGAGAT G 2.3 Approximate pattern matching in a graph (SG or cDBG) Definition 4 (Approximate pattern matching in a graph) Given a query Q, a graph G (SG or cDBG), and a parameter d, approximate pattern matching consists in finding all occurrences of Q in sequences stored in G within an edit distance of at most d.

Table 1 :

 1 Table1reports the total number of nodes and nucleotides stored in some of these graphs. Total number of nodes and nucleotides stored in the graph with respect to the number of reads.

	Nb Reads Nb Nodes Nb nucleotides
	10K	59K	1833K
	100K	573K	17774K
	150K	849K	26306K

Acknowledgements

Authors warmly thank Vincent Lacroix and François Coste for their participation to discussions. This work was born from and supported by the Inria "action de recherche collaborative" ARC Alcovna http://alcovna.genouest.org/.