Ben Firas

Ramdhane

Pierre Guillon

Cellular automata and substitutions in topological spaces defined via edit distances

The Besicovitch pseudo-metric is a shift-invariant pseudo-metric on the set of infinite sequences, that enjoys interesting properties and is suitable for studying the dynamics of cellular automata. They correspond to the asymptotic behavior of the Hamming distance on longer and longer prefixes. Though dynamics of cellular automata were already studied in the literature, we propose the first study of the dynamics of substitutions. We characterize those that yield a well-defined dynamical system as essentially the uniform ones. We also explore a variant of this pseudo-metric, the Feldman pseudo-metric, where the Hamming distance is replaced by the Levenshtein distance. Like in the Besicovitch space, cellular automata are Lipschitz in this space, but here also all substitutions are Lipschitz. In both spaces, we discuss equicontinuity of these systems, and give a number of examples, and generalize our results to the class of the dill maps, that embed both cellular automata and substitutions.

Introduction

In [START_REF] Blanchard | Cellular automata in the Cantor, Besicovitch, and Weyl topological spaces[END_REF] were studied the dynamics of cellular automata in the spaces of sequences endowed with the Besicovitch pseudo-metric, which is defined as the asymptotics of the Hamming distance over prefixes of the sequences. This corresponds to the d-metric defined for ergodic purposes in [START_REF] Ornstein | Ergodic theory, Randomness, and Dynamical Systems[END_REF]. [START_REF] Feldman | New K-automorphisms and a problem of Kakutani[END_REF], and independently [START_REF] Katok | Monotone Equivalence in Ergodic Theory[END_REF], proposed to replace the Hamming distance by the Levenshtein distance from [START_REF] Vladimir I Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF], and get the f -metric, which is useful in Kakutani equivalence theory. The Levenshtein distance depends on the minimum number of the edit operations (deletion, insertion, substitution) required to change one word into an other word. It used extensively for information theory, linguistics, word algorithmics, statistics. . . . One can read some properties of the pseudo-metric in [ORW82a, Chapter 2], and a nice history of this notion in [START_REF] Kwietniak | Feldman-Katok pseudometric and the GIKN construction of nonhyperbolic ergodic measures[END_REF].

The recent [START_REF] García-Ramos | On topological models of zero entropy loosely Bernoulli systems[END_REF] can be seen as presenting a nice picture of those systems for which the identity map from the Cantor space into the Feldman space is a topological factor map, after a similar task has been achieved for the Besicovitsh space in [START_REF] García-Ramos | Weak forms of topological and measure theoretical equicontinuity: relationships with discrete spectrum and sequence entropy[END_REF]. Here, we adopt a complementary point of view, by considering the dynamics within the space itself. Though the work on the Besicovitch space concerned mainly cellular automata so far, relaxing the pseudometric to edit space allows to naturally consider a larger class of systems, that also includes substitutions : the so-called dill maps.

In Section 2, we will introduce some basic vocabulary of symbolic dynamical systems, including dill maps, and define the Besicovitch and Feldman spaces. In Section 3, we study dill maps over the Besicovitch space, give a sufficient and necessary conditions for them to induce a well-defined dynamical system over this space, and give some examples of behaviours. In Section 4, we do the same within the Feldman space.

Definitions and basic results

The aim of this section is to introduce some concepts and basic notations in symbolic dynamics, that will be used throughout this paper, and to introduce some symbolic dynamical objects and topological spaces.

We start with some terminology in word combinatorics. We fix once and for all an alphabet A of finitely many letters (it will be precised in each example, but general in our statements). A finite word over A is a finite sequence of letters in A; it is convenient to write a word as u = u 0,|u| to express u as the concatenation of the letters u 0 , u 1 , . . . , u |u|-1 , with |u| representing the length of u, that is, the number of letters appearing in u and 0, |u| = {0, ..., |u| -1}. The unique word of length 0 is the empty word denoted by λ . The number of occurrences of a letter a ∈ A in a finite word u is denoted by |u| a . An infinite word x = x 0 x 1 x 2 . . . over A is the concatenation of infinitely many letters from A. The set of all finite (resp. infinite) words over A is denoted by A * (resp. A N ), and A n is the set of words of length n ∈ N over A.

Symbolic dynamics

Let us now introduce some basic notions in symbolic dynamics. First we equip the set A N with the product topology on each copy of A. The topology defined on A N is equivalent to the topology defined by the Cantor distance denoted by d C and defined as follows:

∀x = y ∈ A N , d C (x, y) = 2 -min{ n∈N|x n =y n } , ∀x = y ∈ A N , and d C (x, x) = 0, ∀x ∈ A N .
This space, called the Cantor space, is compact, totally disconnected and perfect.

A (topological) dynamical system is a pair (X d , F) where F is a continuous map from a compact metric space X d = (X, d) to itself. When X d is understood from the context, we may omit it. In particular, the shift dynamical system is the couple (A N , σ ), where σ is the shift defined for all x ∈ A N by σ (x) i = x i+1 , for i ∈ N.

We can now introduce some topological properties of a dynamical system (X d , F). We say that x ∈ X is a fixed point if F(x) = x; it is periodic if F n (x) = x for some n > 0. The map F is M-Lipschitz, for M > 0, if d(F(x), F(y)) ≤ Md(x, y) for all x, y ∈ X.

A point x ∈ X is an equicontinuous point of (X d , F) if:

∀ε > 0, ∃δ > 0, ∀y ∈ X, d(x, y) < δ =⇒ ∀t ∈ N, d(F t (x), F t (y)) < ε.

The following property is a strong form of non-equicontinuity.

A point x ∈ X is 1 --unstable if: ∀ε > 0, ∀δ > 0, ∃y ∈ X, d(x, y) < δ but ∃t ∈ N, d(F t (x), F t (y)) > 1 -ε. A dynamical system (X d , F) is equicontinuous if: ∀ε > 0, ∃δ > 0, ∀x ∈ X, ∀y ∈ B(x, δ ), ∀t ∈ N, d(F t (x), F t (y)) < ε. Note that if F is M-Lipschitz, then F t is M t -Lipschitz. It is then clear that if F is 1-Lipschitz, then F
is equicontinuous (and it is actually an equivalence, up to equivalent distance, as seen for instance in [Kůr03, Proposition 2.41]). A dynamical system (X d , F) is sensitive if:

∃ε > 0, ∀x ∈ X, ∀δ > 0, ∃y ∈ X, d(x, y) < δ but ∃t ∈ N, d(F t (x), F t (y)) > ε. A dynamical system (X d , F) is expansive if: ∃ε > 0, ∀x = y ∈ X, ∃t ∈ N, d(F t (x), F t (y)) > ε.
As examples of dynamical systems, we will be interested in this paper by cellular automata, substitutions, and in general dill maps, which are defined from the Cantor space X = A N to itself. For more details, we can refer to [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF], [START_REF] Berthé | Combinatorics, Automata, and Number Theory[END_REF] and [START_REF] Kůrka | Topological and symbolic dynamics[END_REF].

Cellular automata

Definition 1. A cellular automaton (CA) with diameter θ is a map F : A N → A N , such that there exists a map called local rule f :

A θ → A such that for all x ∈ A N , i ∈ N: F(x) i = f (x i,i+θ ).
Example 2.

1. The shift which is a CA with diameter θ = 2 and local rule f such that f (ab) = b.

2. Let A = {0, 1}. The XOr is the CA with diameter θ = 2 and local rule defined as follows:

f (ab) = a + b mod 2, for every a, b ∈ {0, 1}.
3. Let A = {0, 1}. The Min CA with diameter θ = 2 and local rule f defined as follows:

f (ab) = min{a, b}, ∀a, b ∈ A.
In the Cantor space, an elegant characterization of cellular automata was was given by Hedlund in [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF] as follows: A function F : A N → A N is a cellular automaton if and only if it is a continuous function with respect to the metric Cantor space and shift-invariant (i.e. ∀x ∈ A N , F(σ (x)) = σ (F(x))).

Substitutions Definition 3.

1. A substitution τ is a nonerasing homomorphism of monoid A * , (i.e. τ -1 (λ ) = {λ } and τ(uv) = τ(u)τ(v), for all u, v ∈ A * ).

2. Substitution τ yields a dynamical system, denoted by τ, and defined over A N by:

τ(z) = τ(z 0 )τ(z 1 )τ(z 2 )τ(z 3 ) . . . , ∀z ∈ A N .
3. The lower norm |τ| and upper norm τ of τ are defined by:

|τ| = min { |τ(a)| | a ∈ A} and τ = max { |τ(a)| | a ∈ A} .
We say that τ is uniform if |τ| = τ . A letter a ∈ A can reach a component A if some b ∈ A appears in τ t (a), for some t ∈ N. A component A can reach another one A if some a ∈ A can reach it. A component is terminal if it cannot reach any distinct component. A component is maximum if the spectral radius of the corresponding submatrix is maximal, among all components. We will denote A + τ ⊂ A the union of all components which can reach a maximal component. τ is irreducible if there is only one irreducible component. A classical object of study si the primitive substitutions, which are irreducible, as well as all their powers (equivalently its matrix M(τ) is primitive, i.e. ∃n ∈ N, ∀a, b ∈ A we have M n (τ) ab > 0). 1. The Thue-Morse substitution defined over A by:

τ : 0 → 01 1 → 10 M(τ) = 1 1 1 1
This is an primitive uniform substitution.

2. The Fibonacci substitution defined over A by:

τ : 0 → 01 1 → 0 M τ = 0 1 1 1 M 2 τ = 1 1 1 2
This is an primitive nonuniform substitution:

|τ| = 1 < 2 = τ .
3. The doubling substitution defined over A by:

τ : 0 → 00 1 → 11
This is a uniform reducible substitution: {0} and {1} are two disjoint invariant subalphabets.

4. A uniform substitution τ is Toeplitz if ∃i ∈ 0, τ , ∀a, b ∈ A, τ(a) i = τ(b) i .
An example is the Cantor substitution, defined over A by:

τ : 0 → 010 1 → 111
This is a reducible uniform substitution: {1} is an invariant subalphabet.

The following is folklore, direct consequence from Perron-Frobenius theory (see for example [Kůr03, Theorem A.72]).

Remark 5. Let τ be a substitution and t ∈ N. Clearly, M(τ) t a,b is the number of occurrences of b in τ t (a), and ∑ b∈ 0,n M(τ) t a,b = |τ t (a)|. Let τ be a substitution, a ∈ A, and ρ a the maximal spectral radius of the irreducible components that a can reach. Then there exist α a ∈ R * + such that |τ t (a)| = ∑ b∈A M(τ) t a,b ∼ t→∞ α a ρ t a . In particular, A + τ is exactly the set of letters a ∈ A such that ρ a is the spectral radius ρ + of the matrix, i.e. the letters that grow the fastest.

Dill maps

The dill maps were defined in [START_REF] Salo | Block maps between primitive uniform and Pisot substitutions[END_REF], and generelize both substitutions and CA. Here we give a simple definition, which is equivalent to [ST15, Definition 2]. Definition 6.

• A dill map F with diameter θ ∈ N \ {0} is a dynamical system over the set of infinite words such that there exists a local rule f : A θ → A + satisfying:

∀x ∈ A N , F(x) = f (x 0,θ ) f (x 1,θ +1 ) f (x 2,θ +2 ) • • • .
• The lower norm | f | and the upper norm f of a dill map F with diameter θ and local rule f are defined by:

| f | = min | f (u)| u ∈ A θ and f = max | f (u)| u ∈ A θ .
• We extend the local rule into a self-map f * : A * → A * by:

f * (u) = f (u 0,θ ) f (u 1,1+θ ) . . . f (u l,l+θ ),
for u such that |u| ≥ θ and f * (u) = λ if |u| < θ .

• We also consider the cocycle s n x = ∑ j≤n f (x j, j+θ ) = f * (x 0,n+θ ) for n ∈ N and x ∈ A N , which represents the position in which one can read the image at offset n.

• If f = | f |, then we say that F is uniform. In that case, the cocycle s n

x does not depend on the infinite word x, and we note it s n .

When it is clear from the context, we may identify a dill map with its local rule.

Remark 7.

1. The substitutions are the dill maps with diameter θ = 1.

The cellular automata are the uniform dill maps with

| f | = f = 1.
3. The composition of a substitution τ and a cellular automaton local rule f with diameter θ is a dill map local rule τ • f with diameter θ . Actually, every dill map is the compositions of a substitution and a shift homomorphism (which is like a cellular automaton, but allowing to change the alphabet).

Example 8. Let f be the local rule of the XOr CA and τ be the Fibonacci substitution. Then τ • f is a local rule of a dill map with diameter 2 and defined as follows:

τ • f : 00, 11 → 01 10, 01 → 0 Remark 9. For all x ∈ A N , n → s n x is a one-to-one function.

Proof. For n ≤ m ∈ N such that s n x = s m x we have:

∑ i≤m f (x i,i+s ) -∑ i≤n f (x i,i+s ) = ∑ n<i≤m f (x i,i+s ) = 0
Then for all n < i ≤ m we have f (x i,i+s ) = 0. Since f is nonerasing then n = m.

Similarly to the case of cellular automata, we give a characterization of dill maps à la Hedlund.

Theorem 10. A function F : A N → A N is a dill map if and only if it is continuous over the Cantor space and there exists a continuous map s :

A N → N; x → s x such that for all x ∈ A N : F(σ (x)) = σ s x (F(x)).
Proof.

" ⇒ " Let F be a dill map with diameter θ and local rule f . For x ∈ A N , ε = 2 -p for p ∈ N * we take m = min i ∈ N s i x ≥ p . For δ = 2 -m and y ∈ A N such that d C (x, y) ≤ δ we have x 0,m = y 0,m . Then f * (x 0,m ) = f * (y 0,m ). Hence F(x) 0,p = F(y) 0,p . So, d C (F(x), F(y)) ≤ 2 -p = ε. In conclusion, F is continuous. Now let us define s(x) = s x = f (x 0,θ ) for all x ∈ A N . Let x ∈ A N and ε > 0. For y ∈ A N such that d C (x, y) < 2 -θ we have x 0,θ = y 0,θ . Then f (x 0,θ ) = f (y 0,θ ) and hence f (x 0,θ ) = f (y 0,θ ) . So d(s x , s y ) = 0. In conclusion, s is continuous, and it satisfies F(σ (x)) = σ s x (F(x)).

" ⇐ " We suppose now that there exists a continuous map s : A N → N. We can write A N = n∈N s -1 ({n}).

Since {n} is clopen set for all n ∈ N and s is continuous, then s -1 ({n}) is open for all n ∈ N. On the other hand, (A N , d C ) is compact, so that there exists a finite set I ⊂ N such that A N = i∈I s -1 ({i}). Let x ∈ A N ; then there exists i ∈ I such that x ∈ s -1 (n i ). Since F is continuous, for ε = 2 -n i , there exists r i such that for all y ∈ A N verifying d C (x, y) < 2 -r i we have d C (F(x), F(y)) < ε. Then for all x ∈ A N , there exists i ∈ {1, • • • , p} and r i such that for all

y ∈ A N verifying d C (x, y) < 2 -r i we have d C (F(x), F(y)) < 2 -n i . Let θ = max { r i | i ∈ {1, • • • , p}}.
Hence for all x ∈ A N , there exists i ∈ {1, • • • , p} such that for all y ∈ A N with x 0,θ = y 0,θ , we have F(x) 0,n i = F(y) 0,n i with n i = s x . So there exists a map f :

A θ → A * such that f (x 0,θ ) = F(x) 0,n i , for all x ∈ A N .
On the other hand, for x ∈ A N and j ∈ N we have:

f (x j, j+θ ) = f (σ j (x) 0,θ ) = F(σ j (x)) 0,n i , with n i = s σ j (x) .
Hence, by induction we find:

F(σ j (x)) = F(σ (σ j-1 (x))) = σ s σ j-1 (x) F(σ j-1 (x)) = σ m F(x), with m = j-1 ∑ h=0 s σ h (x)
.

Then : f (x j, j+θ ) = σ m F(x) 0,n i = F(x) m,m+n i . Finally, we find that F(x) = f (x 0,θ ) f (x 1,1+θ ) f (x 2,2+θ ) • • • . In conclusion, F is a dill map.
Corollary 11. Let F be a dill map with local rule f . Then for all x ∈ A N , all n ∈ N we have:

F • σ n (x) = σ s n x • F(x).
Proof. Let F be a dill map with diameter θ and local rule f . Then according to Theorem 10 there exists a continuous map s : A N → N such that for all x ∈ A N : F(σ (x)) = σ s x (F(x)). We aim to prove by induction that for all x ∈ A N , for all n ∈ N there exists s n x ∈ N such that:

F • σ n = σ s n x • F. Let x ∈ A N . For k = 1 we have F(σ (x)) = σ s x (F(x)
). We suppose that our statement is true for k = n, so there exists s n x ∈ N such that Fσ n (x) = σ s n x F(x). Now, for k = n + 1 we have:

F • σ n+1 (x) = F(σ (σ n (x))) = σ s σ n (x) (F(σ n (x))) = σ s σ n (x) (σ s n x (F(x))) = σ s n+1 x (F(x)).
Which is the next step of the induction hypothesis.

Hence, for all x ∈ A N , all n ∈ N and for s n x = ∑ n-1 k=0 s σ k (x) we have:

F(σ n (x)) = σ s n x (F(x)).

The Besicovitch space

In this subsection, we recall the definition and topological properties of Besicovitch space.

Recall that a distance is an application over A * × A * to R + satisfying: separation, symmetry, and the triangle inequality. We can endow the set A n for n ∈ N with distance. The prototypical example is the Hamming distance denoted by d H . It is usually defined as the number of differences between two finite words of the same length. Let us present a definition in terms of edit distance, that is a number of operations from a specific kind to transfor a word into another one.

Definition 12.

• The substitution operations S a j at position j ∈ 0, |u| , for a ∈ A, are defined over finite word u ∈ A * as follows: S a j (u

) = u 0 • • • u j-1 au j+1 • • • u |u|-1 .
• Between two finite words with the same length u, v, we define the Hamming distance:

d H (u, v) = min m ∈ 0, |u| ∃ j 1 < j 2 < • • • < j m , (a j ) j≤m ⊂ A m , S a 1 j 1 • • • • S a n j m (u) = v .
Of course, the definition would be completely equivalent by allowing substitutions to be performed on both u and v, and is simply the number of differences, letterwise.

Remark 13. Note that this distance is an additive distance i.e. for all u, u , v, v such that |u| = |u | and

|v| = |v |, d H (uv, u v ) = d H (u, u ) + d H (v, v ).
Definition 14. The Besicovitch pseudo-metric, denoted by d H , is defined as follows:

∀x, y ∈ A N , d H (x, y) = lim sup l→∞ d H (x 0,l , y 0,l ) l .
It is easy to verify that this is a pseudo-metric: it is symmetric, zero over diagonal pairs, and satisfies the triangular inequality. On the other hand, it is not a distance since we can find two different infinite words where the pseudo-metric is worth zero (for instance, we can take two infinite words with finitely many of differences). Hence, it is relevant to quotient the space of infinite words by the equivalence of zero distance, in order to get a separated topological space, as mentioned in the following definition:

Definition 15. • The relation x ∼ d H y ⇐⇒ d H (x, y) = 0, is an equivalence relation. • The quotient space A N /∼ d H
is a topological space, called the Besicovitch space denoted by X d H .

• We denote by x d H the equivalence class of x ∈ A N in the quotient space.

• Any map F :

A N → A N such that d H (x, y) = 0 =⇒ d H (F(x), F(y)) induces a well-defined map F d H : X d H → X d H over Besicovitch space.
According to [START_REF] Blanchard | Cellular automata in the Cantor, Besicovitch, and Weyl topological spaces[END_REF], the Besicovitch space is pathwise-connected, infinite-dimensional and complete, but, it is neither separable nor locally compact.

The Feldman space

Another classical edition distance is the Levenshtein distance [START_REF] Vladimir I Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF]. Instead of allowing to edit finite words only via substitution operations (like for the Hamming distance), we now allow to edit using deletions.

Definition 16.

• The deletion operation D j at position j ∈ 0, |u| is defined over word u ∈ A * as follows: D j (u) = u 0 u 1 . . . u j-1 u j+1 . . . u |u|-1 , for all u ∈ A * .

• The Levenshtein distance d L is defined over u, v ∈ A * as follows:

d L (u, v) = 1 2 min m + m ∃ j 1 < • • • < j m , j 1 < • • • < j m , D j 1 • . . . • D j m (u) = D j 1 • . . . • D j m (v) .
Most frequently, we will consider the distance between two words of the same length, so that the result is an integer, and can be defined as the minimal m such that there exist two sequences D j 1 . . . D j m and D j 1 . . .

D j m such that D j 1 • . . . • D j m (u) = D j 1 • . . . • D j m (v).
The pseudo-metric d L (u, v) can also be defined as |u|+|v| 2 l, where l is the length of the longest common subword between u and v.

Several variants exist in the literature:

• One may want to remove factor 1 2 in the definition, to make the definition look more natural. Nevertheless, the two points above, as well as the next two remarks, motivate our definition. Anyway, the two pseudo-metric d L and 2d L are equivalent.

• If one allows two edition operations, insertion and deletion, the purpose could be that it can be defined by performing all operations only on one of the two words. The two pseudo-metrics are here exactly equal because an insertion on one side corresponds to a deletion on the other side.

Manipulations are a little more technical because one has to deal with as many insertion operations as there are letters in the alphabet.

• If one additionnally allows the substitution operation from Definition 12, with weight 1, then again the two obtained pseudo-metrics are equal, because a substitution corresponds to a sequence of an insertion and a deletion.

• If one gives the same weights to the substition and deletion operations, then one gets an equivalent pseudo-metric (bounded between d L and 2d L ).

Example 17. Let A = {0, 1}.

1. For u = 010101 and v = 101010, we have :

d L (u, v) = 1.
Indeed, D 0 (u) = 10101 (we delete the letter of index 0 in u), then we delete the last letter in the end of the word v and we find D 0 (u) = 10101 = D 5 (v). For the sake of comparison, note that d H (u, v) = 5.

2. For u = 0000 and v = 00001, we have d L (u, v) = 1 2 since it is enough to delete the last lettre of v. Remark 18. For every u, v ∈ A * , we have:

|u| -|v| 2 ≤ d L (u, v) ≤ |u| + |v| 2 .
Proof. The upper bound comes from the trivial edition sequence producing:

D 1 • D 2 • • • D |u| = λ = D 1 • . . . D |v| .
On the other hand, if

D j 1 • D j 2 • • • • • D j m (u) = D j 1 • D j 2 • • • • • D j m (v), then D j 1 • D j 2 • • • • • D j m (u) = D j 1 • D j 2 • • • • • D j m (v) .
Hence, |u|m = |v|m . Then we can conclude that

|u| -|v| 2 = m -m 2 ≤ m + m 2 = d L (u, v).
Remark 19. The Hamming distance is an upper bound for the Levenshtein distance, i.e. for all words u, v

∈ A * such that |u| = |v|, d L (u, v) ≤ d H (u, v). Proof. Let d H (u, v) = m, then there exists j 1 < • • • < j m such that for all h ∈ 1, m , u j h = v j h . If we delete u j h and v j h for all h ∈ 1, m , then we find D j 1 • . . . • D j m (u) = D j 1 • . . . • D j m (v). Hence: d L (u, v) ≤ 2m 2 = n = d H (u, v).
Proposition 20. The Levenshtein distance is subadditive, i.e. for all words u, v, u , v ,

d L (uu , vv ) ≤ d L (u, v) + d L (u , v ).
Proof. Consider words u, u , v, v , and m, m , n, n such that:

D j 1 • • • • • D j m (u) = D j 1 • • • • • D j m (v) and D j m+1 • • • • • D j m+n (u ) = D j m +1 • • • • • D j m +n (v ),
for some minimal edition sequences

j 1 < • • • < j m < |u|, j 1 < • • • < j m < |u |, j m+1 < • • • < j m+n |v| and j m +1 < • • • < j m +n < |v |, so that d L (u, u ) = m+m 2 and d L (v, v ) = n+n 2 .
By concatenating the two previous edited words, we obtain:

D j 1 • • • • • D j m+n (uu ) = D j 1 • • • • • D j m +n (vv ). Therefore d L (uu , vv ) ≤ m+n+m +n 2 = d L (u, v) + d L (u , v ).
Following the idea behind the Besicovitch pseudo-metric, we define a pseudo-metric associated to the Levenshtein distance as follows:

Definition 21. The Feldman pseudo-metric associated to the Levenshtein distance is:

d L (x, y) = lim sup l→∞ d L (x 0,l , y 0,l ) l , ∀x, y ∈ A N .
Like the Besicovith pseudo-metric, it is a pseudo-metric but not a distance. Actually all pairs at Besicovitch pseudo-metric 0 are at Feldman pseudo-metric 0. More generally, Remark 19 gives the following.

Remark 22. For all x, y ∈ A N we have :

d L (x, y) ≤ d H (x, y).
Here too, it is natural to quotient the space of infinite words by the equivalence of zero distance; we obtain a metric space, called the Feldman space denoted by X d L .

3 Dill maps in the Besicovitch space

Lipschitz property of dill maps

It is known since [START_REF] Blanchard | Cellular automata in the Cantor, Besicovitch, and Weyl topological spaces[END_REF] that every cellular automaton induces a (well-defined) Lipshitz function over Besicovitch space. [MS09, Theorem 13] goes further, by establishing a characterization à la Curtis-Hedlund-Lyndon of cellular automata in the Besicovitch space by three conditions: shift invariance, a condition in terms of uniform continuity and a condition in terms of periodic infinite words. Some dill maps, on the contrary are not well-defined.

Example 23. The Fibonacci substitution is not well-defined over the Besicovitch space X d H .

Even worse, for every x ∈ {0, 1} N such that x = 1 ∞ , altering simply the first letter will induce a shift in the substitution. Indeed, if x 0 = 1, then:

d H (τ(S 0 0 (x)), τ(x)) = d H (0τ(x), τ(x)). Symmetrically, if x 0 = 0, then d H (τ(S 1 0 (x)), τ(x)) = d H (σ (τ(x)), τ(x)
). In both cases, the pseudo-metric is at least half of the frequence d H (1 ∞ , x) of 0s in x. For example,

d H (0 ∞ , 10 ∞ ) = 0 but d H (τ(0 ∞ ), τ(10 ∞ )) = d H ((01) ∞ , (10) ∞ ) = 1. On the other hand, for all x ∈ {0, 1} N , d H (τ(x), τ(1 ∞ )) ≤ d H (x, 1 ∞ ) (frequence of 0s in x)
. This is still a quite poor continuity set.

In this section, we characterize dill maps which induce a well-defined function over this space. Let us note

d + f = max d H ( f (u), f (v)) u, v ∈ A θ , and d - f = min d H ( f (u), f (v)) u = v ∈ A θ . Proposition 24.
Let F be any uniform dill map with diameter θ and local rule f . Then:

∀x, y ∈ A N , θ d - f | f | × d H (x, y) ≤ d H (F(x), F(y)) ≤ θ d + f | f | × d H (x, y). Proof. Let x, y ∈ A N and l ∈ N. It is clear that we can write l = | f |m + r such that m ∈ N and r < | f |, then : F(x) 0,l = f (x 0,θ ) f (x 1,1+θ ) . . . f (x m,m+θ ) 0,r , and
F(y) 0,l = f (y 0,θ ) f (y 1,1+θ ) . . . f (y m,m+θ ) 0,r .
Hence if we note d = d H (F(x) 0,l , F(y) 0,l ), then:

m ∑ i=0 d H ( f (x i,i+θ ), f (y i,i+θ )) -r ≤ d ≤ m ∑ i=0 d H ( f (x i,i+θ ), f (y i,i+θ )) m ∑ i=0 x i,i+θ =y i,i+θ d H ( f (x i,i+θ ), f (y i,i+θ )) -| f | < d ≤ m ∑ i=0 x i,i+θ =y i,i+θ d H ( f (x i,i+θ ), f (y i,i+θ )) m ∑ i=0 ∃ j∈ i,i+θ ,x j =y j d - f -| f | < d ≤ m ∑ i=0 ∃ j∈ i,i+θ ,x j =y j d + f ∑ j∈ θ ,m+θ x j =y j ∑ i∈ j-θ , j d - f -| f | < d ≤ ∑ j∈ 0,m+θ x j =y j ∑ i∈ j-θ , j d + f ∑ j∈ δ ,m+θ x j =y j θ d - f -| f | < d ≤ ∑ j∈ 0,m+θ x j =y j θ d + f d H (x θ ,m+θ , y θ ,m+θ )θ d - f -| f | < d ≤ d H (x 0,m+θ , y 0,m+θ )θ d + f d H (x 0,m , y 0,m )θ d - f -θ 2 d - f -| f | < d ≤ d H (x 0,m , y 0,m )θ d + f + θ 2 d + f . Hence: d H (x 0,m , y 0,m )θ d - f -θ 2 d - f -| f | l < d l ≤ d H (x 0,m , y 0,m )θ d + f + θ 2 d + f l θ d - f | f | × d H (x 0,m , y 0,m ) -θ 2 d - f -| f | m + 1 < d l ≤ θ d + f | f | × d H (x 0,m , y 0,m ) + θ 2 d + f m θ d - f | f | × d H (x 0,m+1 , y 0,m+1 ) -θ 2 d - f -| f | -1 m + 1 < d l ≤ θ d + f | f | × d H (x 0,m , y 0,m ) + θ 2 d + f m .
Finaly, since m → ∞ when l → ∞, then we find:

θ d - f | f | × d H (x, y) ≤ d H (F(x), F(y)) ≤ θ d + f | f | × d H (x, y).
In particular, the Cantor and Thue-Morse substitutions are well-defined over this space (we will discuss them in the next subsection).

We now reach necessary and sufficient conditions for dill maps to induce well-defined dynamical systems over this space.

Theorem 25. Let F be a dill map with diameter θ and local rule f . Then the following statements are equivalents:

1. F d H is well-defined.

F is

θ d + f | f | -Lipschitz with respect to d H .
3. F is either constant or uniform.

Proof.

3 =⇒ 2 It is clear from Proposition 24.

2 =⇒ 1 It is clear from the definition of Lipschitz function.

1 =⇒ 3 Assume that τ is nonuniform, i.e. there are two words u and v such that -First assume that there exist w ∈ A * and i ∈ N such that f * (w) i = f * (w) i+k . By our previous assumption, we know that

| f * (u)| = | f * (v)|. One can assume that their longest common suffix has length δ -1. Indeed, otherwise let a ∈ A, u = u |u|-θ +1,|u| a θ -1 and v = v |u|-θ +1,|v|-1 a θ -1-l ; one can note that f * (ua θ -1 ) = f * (u) f * (u ) and f * (va θ -1 ) = f * (v) f * (v ), so that either f * (ua θ -1 ) = f * (va θ -1 ) , or | f * (u )| = f * (ua θ -1 ) - | f * (u)| = f * (va θ -1 ) -| f * (v)| = | f * (v )|,
w = u |u|-θ ,|u| w ∞ 0,θ = v |v|-θ ,|v|-1 w ∞ 0,θ . F(uw ∞ ) = f * (u) f * (w )F(w ∞ ), so that for every j ∈ N, F(uw ∞ ) | f * (u)|+| f * (w )|+ j f * (w ∞ 0,|w|+θ ) +i = w i . On the other hand, F(vw ∞ ) | f * (u)|+| f * (w )|+ j w ∞ 0,|w|+θ +i = F(vw ∞ ) | f * (v)|+k+| f * (w )|+ j w ∞ 0,|w|+θ +i = w i+k = w i . We deduce that d H (F(uw ∞ ), F(vw ∞ )) ≥ 1 w ∞ 0,|w|+θ . Since |u| = |v|, we know d H (uw ∞ , vw ∞ ) = 0,
so that F is not well-defined over the quotient space.

-Otherwise, for all w ∈ A * , i ∈ 0, |w| , we have f * (w) i = f * (w) i+k . Let w ∈ A * , such that |w | ≥ k and let w ∈ A * . Then:

∀ j ∈ N, f * (w) j = f * (w w) j+| f * (w )| = f * (w w) j+| f * (w )| mod k = f * (w ) j+| f * (w )| mod k .
Hence for all x ∈ A N , j ∈ N, we have F(x) j = f * (w ) j+| f * (w )| mod k . So, F is constant.

Corollary 26. A substitution τ yields a well-defined dynamical system τ over X d H if and only if is 1-Lipschitz with respect to d H .

Equicontinuity

The following derives directly from Proposition 24 (and completeness of the Besicovitch space).

Corollary 27. Let F be a uniform dill map with diameter θ and local rule f .

1. If θ d + f ≤ | f |, then F d H is equicontinuous.
For example, for every substitution τ, τ is equicontinuous.

2. If θ d + f < | f |, then F d H
is contracting: every orbit converges to a unique fixed point. For example, for every substitution τ such that d + τ < |τ|, τ is contracting.

3. If θ d - f = | f |, then F d H is
an isometry. For example, for every substitution τ such that d - τ = |τ| (which means that the substitution is everywhere marked: any two images have no letter in common), τ is an isometry.

Example 28. Let τ be a Toeplitz substitution. By definition and by Corollary 27, τ is contracting, so that all orbits converge towards a unique fixed point: the class for ∼ d H of the usual fixed points of the substitution (which is unique if ∀a, b ∈ A, τ(a) 0 = τ(b) 0 , but may not be otherwise, like for the Cantor substitution).

Example 29. On the contrary, the Thue-Morse substitution is an isometry, thanks to Corollary 27. In particular, if Σ τ is the orbit closure of the two fixed points, then for every x / ∈ Σ τ , the pseudo-metric d H (τ t (x), Σ τ ) is constantly positive, so that our intuition that orbits converge towards Σ τ , though justified in the Cantor space, is completely false in the Besicovitch space.

Remark 30. The behaviors from Example 28 and 29 give an essentially full picture of what can occur. Indeed, if there exists p ∈ N such that d + τ p < |τ| p , then τ p is contracting; consequently, for every t ∈ N the diameter of τ t (A N ) is bounded by that of τ p t p (A N ), which is bounded by

d + τ p |τ| p t p
; so all orbits of τ converge towards a unique fixed point. If, on the other hand, for every t ∈ N, d + τ t = |τ|, this means that there exists a subalphabet A t ∈ A containing at least two letters, such that a, b ∈ A t =⇒ d H (τ t (a), τ t (b)) = |τ| t . It is not difficult to see that A t ⊂ A t+1 , and since it is finite, the subalphabet A = t∈N A t contains at least two letters. Then the restriction of τ to A N is an isometry (because Proposition 24 remains true when the minimum and maximum are taken over a subalphabet).

The links between dynamical properties in the Cantor space and in the Besicovitch space appeared for cellular automata in [START_REF] Blanchard | Cellular automata in the Cantor, Besicovitch, and Weyl topological spaces[END_REF], [START_REF] Formenti | Dynamics of cellular automata in non-compact spaces[END_REF]: in particular, sensitivity in the Besicovitch space implies sensitivity in the Cantor space, or equicontinuity in the Cantor space implies equicontinuity in the Besicovitch space. Nevertheless, unlike for cellular automata, there exist dill maps which are equicontinuous in the Cantor space but not in the Besicovitch space.

Example 31. Consider the dill map F with diameter 2 defined as the composition of the doubling substitution and of the Min CA, or equivalently by the following local rule: f : 00, 01, 10 → 00 11 → 11. This dill map is 1-Lipschitz in the Cantor space, but F d H is not equicontinuous. We can even prove that

1 ∞ is 1 --unstable. For p ∈ N \ {0}, let y = (1 p-1 0) ∞ . Remark that d H (x, y) = 1 p . On the other hand, F p-1 (y) = 0 ∞ , so that d H (F p-1 (1 ∞ ), F p-1 (y)) = d H (1 ∞ , 0 ∞ ) = 1.
Some weak robustness properties of cellular automata from [START_REF] Formenti | Dynamics of cellular automata in non-compact spaces[END_REF], though, can be generalized to dill maps, like in the following statement.

Proposition 32. Let F be a uniform dill map and m ∈ N. Then we have the following:

1. If F d H is sensitive, then σ m d H • F d H is sensitive, too.
2. If x is an equicontinuous point for F d H , then it is an equicontinuous point for

σ m d H • F d H , too. 3. If F d H is equicontinnuous, then σ m d H • F d H is equicontinuous, too.
Proof. The key to proof the three statements is the following:

∀n ∈ N, (σ m • F) n = σ ∑ n-1 k=0 m| f | k • F n .
Let us prove this by induction on n ∈ N. The case n = 0 is obvious. Suppose that for it is true for some n.

(σ m • F) k = (σ m • F) • (σ m • F) n = σ m • F • (σ ∑ n-1 k=0 m| f | k • F n ) = σ m • σ | f | ∑ n-1 k=0 m| f | k • F • F n ,
which is the next step of the induction hypothesis. The last equality comes from the fact that F is uniform, so that s n x = | f | = f . Now we can deduce the proof of the statement: for all x, y ∈ A N and for all n, m ∈ N:

d H ((σ m • F) n (x), (σ m • F) n (y)) = d H (σ ∑ n-1 k=0 m| f | k (F n (x)), σ ∑ n-1 k=0 m| f | k (F n (y))) = d H (F n (x), F n (y)) (since d H is shift-invariant)
It was known that the cellular automata suit well in the Besicovitch pseudo-metric, and we have seen in this section that it is also the case of uniform substitutions. But we proved that this is not true for non-uniform substitutions. In the next section, we consider another topological space, in which both cellular automata and substitutions are well-defined over this space.

4 Dill maps in the Feldman space

Shift

One of the motivation to study the Besicovitch space is that the shift is an isometry over this space. In the Feldman space, this is still true, but even more than this: the shift is exactly the indentity.

Proposition 33. The shift over the Feldman space is the identity map.

Proof. Let x ∈ X d L . If x ∈ x, then d L (x 0,l , σ (x) 0,l ) = d L (x 0,l , x 1,1+l
) ≤ 1: simply delete the first letter of x 0,l and the last letter of σ (x) 0,l , to obtain x 1,l in both cases. Hence :

d L (x, σ (x)) = lim sup l→∞ d L (x 0,l , x 1,1+l ) l ≤ lim sup l→∞ 1 l = 0.
Since every equivalence class is invariant by shift, dynamical systems over this space can be considered as acting on shift orbits.

Lemma 34. For every x, y ∈ A N , if d L (x, y) = 0 then for all p ∈ N, there exists i, j ∈ N such that :

x i,i+p = y j, j+p .

Proof. Let x, y ∈ A N such that d L (x, y) = 0 and p ∈ N. Then :

∀ε > 0, ∃N > 0, ∀n > N, d L (x 0,n , y 0,n ) < n × ε.
Hence, for ε = 1 p + 1 , there exists N 1 > 0 such that for all n > N 1 we have d L (x 0,n , y 0,n ) < n p + 1 . Then

for ε = 1 p + 1
, there exists N = max{p + 1, N 1 } such that for all n > N we have d L (x 0,n , y 0,n ) < n p + 1 .

Hence, there exists u ∈ A p such that u x 0,n and u y 0,n . So, there exists i, j ∈ 0, np such that :

u = x i,i+p = y j, j+p .
Lemma 35. Let F be a CA with diameter θ and local rule f . For every u

∈ A θ , if d L (u ∞ , F(u ∞ )) = 0 then there exists k ∈ 0, θ such that F(u ∞ ) = σ k (u ∞ ). Proof. Let u ∈ A θ be such that d L (u ∞ , F(u ∞ )) = 0. According to Lemma 34, there exist i, j ∈ N such that F(u ∞ ) i,i+θ = (u ∞ ) j, j+θ .
Since both u ∞ and F(u ∞ ) are θ -periodic for the shift, one can write, for every k ∈ N,

F(u ∞ ) k = F(u ∞ ) k-i mod θ +i = (u ∞ ) k-i mod θ + j = (u ∞ ) j-i+k mod θ . Hence F(u ∞ ) = σ j-i+k mod θ (u ∞ ).
Theorem 36. For every CA F we have, F ∈ id ⇐⇒ ∃k ∈ N, F = σ k .

Proof.

" ⇐ " Proposition 33 proves that if F = σ k then F ∈ ĩ d.
" ⇒ " Let F be a CA with diameter θ ∈ N \ {0} and local rule f such that F ∈ ĩ d. Then for all x ∈ A N we have d L (F(x), x) = 0. In particular, for all u ∈ A θ we have d L (F(u ∞ ), u ∞ ) = 0. So according to Lemma 35, we deduce that for all u ∈ A θ , there exists

k u ∈ 0, θ such that f (u) = F(u ∞ ) 0 = σ k u (u ∞ ) 0 .
Defining k to be any common multiple of all the k u , for u ∈ A θ , we have:

∀u ∈ A θ , f (u) = σ k (u ∞ ) 0 = u k mod θ .
This is exactly the local rule of σ k mod θ .

Lipschitz property of dill maps

Now, we aim at proving that, unlike in the Besicovitch space, all dill maps are well-defined in the Feldman space.

Lemma 37. Let F be a dill map and M, M ∈ N such that for every u ∈ A * and every j ∈ 0, |u| ,

d L ( f * (D j (u)), f * (u)) ≤ M + | f * (u)| -f * D j (u) 2 d L ( f * (D j (u)), f * (u)) ≤ M - | f * (u)| -f * D j (u) 2 .
Then for all l ∈ N and u, v ∈ A l , we have:

d L ( f * (u), f * (v)) ≤ (M + M )d L (u, v) - | f * (u)| -| f * (v)| 2 .
Proof. Consider words u, v, and m such that:

D j 1 • • • • • D j m (u) = D j 1 • • • • • D j m (v),
for some minimal edition sequences

j 1 < • • • < j m < |u| and j 1 < • • • < j m < |v|, so that d L (u, v) = m.
By the triangular inequality, one gets:

d L ( f * (u), f * (v)) ≤ m ∑ k=1 d L ( f * (D j k+1 • • • • • D j m (u)), f * (D j k • • • • • D j m (u)))+ + d L ( f * (D j 1 • • • • • D j m (u)), f * (D j 1 • • • • • D j m (v)))+ + m ∑ k=1 d L ( f * (D j k • • • • • D j m (v)), f * (D j k+1 • • • • • D j m (v))).
Now our two assumptions allow to write:

d L ( f * (u), f * (v)) ≤ m ∑ k=1 M + f * (D j k+1 • • • • • D j m (u)) -f * (D j k • • • • • D j m (u)) 2 + 0+ + m ∑ k=1   M + f * (D j k • • • • • D j m (v)) -f * (D j k+1 • • • • • D j m (v)) 2   ≤ Mm + | f * (u)| -f * (D j 1 • • • • • D j m (u)) 2 + M m + f * (D j 1 • • • • • D j m (v)) -| f * (v)| 2 ≤ (M + M )m + | f * (u)| -| f * (v)| 2 .
Lemma 38. Let F be a dill map and M, M ∈ N such that for every u ∈ A * and every j ∈ 0, |u| ,

d L ( f * (D j (u)), f * (u)) ≤ M + | f * (u)| -f * D j (u) 2 d L ( f * (D j (u)), f * (u)) ≤ M - | f * (u)| -f * D j (u) 2 .
Let x be such that for every i ∈ N, f (x i,i+θ ) ≥ L. Then for every y ∈ A N ,

d L (F(x), F(y)) ≤ M + M L d L (x, y).
Proof. Let x, y ∈ A N and l ∈ N. Consider the largest k ∈ N such that f (x 0,k ) ≤ l. Then F(x) 0,l can be written f (x 0,k )w for some w of length less than f . Note that l = ∑ k-θ i=0 f (x i,i+θ ) ≥ (kθ + 1)L. Proposition 20 gives the following:

d L (F(x) 0,l , F(y) 0,l ) ≤ d L ( f * (x 0,k ), f * (y 0,k )) + d L (w, F(y) | f * (y 0,k )|,l ).

Note that the previous inequality still holds if

f * (x 0,k ) ≥ l, in which case the second term is d L (w, λ ) = |w| 2 . Otherwise, d L (w, F(y) | f * (x 0,k )|,l ) ≤ |w| + F(y) | f * (x 0,k )|,l 2 ≤ |w| + (l -f * (y 0,k ) ) + ( f * (y 0,k ) -f * (x 0,k ) ) 2 . < ( f * (y 0,k ) -f * (x 0,k ) ) 2 + f -1.
We can use Lemma 37 to get:

d L (F(x) 0,l , F(y) 0,l ) < (M + M )d L (x 0,k , y 0,k ) - f * (x 0,k ) -f * (y 0,k ) 2 + + ( f * (y 0,k ) -f * (x 0,k ) ) 2 + f -1 < (M + M )d L (x 0,k , y 0,k ) + f -1
Since l ≥ (kθ + 1)L, one can write:

d L (F(x) 0,l , F(y) 0,l ) l < (M + M )d L (x 0,k , y 0,k ) + f -1 (k -θ + 1)L ∼ k→∞ M + M L d L (x 0,k , y 0,k ) k
Finally since k tends to infinity when l tends to infinity, we have:

d L (F(x), F(y)) = lim sup l→∞ d L (F(x) 0,l , F(y) 0,l ) l ≤ lim sup k→∞ M + M L d L (x 0,k , y 0,k ) k ≤ M + M L d L (x, y).
Corollary 39.

1. Let F be a dill map and M, M ∈ N such that for every u ∈ A * and every j ∈ 0, |u| ,

d L ( f * (D j (u)), f * (u)) ≤ M + | f * (u)| -f * D j (u) 2 d L ( f * (D j (u)), f * (u)) ≤ M - | f * (u)| -f * D j (u) 2 . Then F is M+M | f | -Lipschitz.
2. Let F be any dill map with diameter θ , and x be such that for every i ∈ N, f (x i,i+θ ) ≥ L. Then, for every y ∈ A N ,

d L (F(x), F(y)) ≤ (2θ -1) f L d L (x, y).
For example, if f is a substitution τ and x is such that for every i ∈ N, |τ(x i )| ≥ L, then for every y ∈ A N ,

d L (τ(x), τ(y)) ≤ τ L d L (x, y).
3. In particular, any dill map with diameter θ and lower norm

| f | is (2θ -1) f | f | -Lipschitz.
For example, any substitution τ yields a τ |τ| -Lipschitz dynamical system.

Proof.

1. Since, for all x ∈ A N , all i ∈ N, we have f (x i,i+θ ) ≥ | f |, then according to Lemma 38, we find that

F is M+M | f | -Lipschitz.
2. Let u ∈ A 2θ -1 . Then according to Remark 18 we have:

d L ( f * (u), f * (D j (u))) ≤ | f * (u)| + f * (D j (u)) 2 .
Hence,

d L ( f * (u), f * (D j (u))) ≤ | f * (u)| - | f * (u)| -f * (D j (u)) 2 ≤ θ - | f * (u)| -f * (D j (u)) 2 .
Also,

d L ( f * (u), f * (D j (u))) ≤ f * (D j (u)) - f * (D j (u)) -| f * (u)| 2 ≤ (θ -1) + | f * (u)| -f * (D j (u)) 2 .
The result follows from Lemma 38.

3. Since, for all x ∈ A N we have f (x i,i+θ ) ≥ | f |, then we deduce the result from 2.

Equicontinuity

Finally, we study some dynamical properties since the study of some other properties brings us to some unsolved problems of word algorithmics and other with exponential complexity. We can already derive from Corollary 27 (since the Besicovitch topology is less fine) that all uniform substitutions yield equicontinuous dynamical systems in the Feldman space. The following theorem generalizes the result by establishing a characterization of equicontinuous substitutions.

Theorem 40. Let τ be any substitution. Consider the dynamical system τ over the Besicovitch space. Then:

1. The infinite words of A + τ N are equicontinuous.

2. The infinite words of (A + τ C ) N are not equicontinuous.

The following corollary can directly be derived from the theorem, by noting that A + τ is never empty. Corollary 41.

1. A substitution is equicontinuous if and only if all of its terminal components are maximum.

2. This is the case for irreducible substitutions, and uniform substitutions.

Every substitution admits at least one equicontinuous infinite word.

Proof of Theorem 40. Let τ be a substitution, M(τ) its matrix and ρ + its spectral radius. In particular, τ t ≤ αρ t + for some α > 0.

1. Let x ∈ A + τ N , i.e. there exists β > 0 such that for every i ∈ N and t ∈ N, |τ t (x i )| > β ρ t + . From Point 2 of Corollary 39, for every y ∈ A N ,

d L (τ t (x), τ t (y)) ≤ τ t β ρ t + d L (x, y) ≤ α β d L (x, y).
So all iterates τ t are Lipschitz with a uniform coefficient: τ is equicontinuous.

2. Consider any infinite word x ∈ (A + τ C ) N . By definition of A + τ , ρ -= max i∈N ρ x i is strictly smaller than the spectral radius ρ + of M(τ). Let k ∈ N \ {0}, and y defined by y i = x i for every i / ∈ kN, and y i be any letter from a terminal maximal component, if i ∈ kN. Note that d

L (x, y) ≤ d H (x, y) ≤ 1 k . Besides, if u ∈ (A + τ C ) * , then for every v ∈ A * of the same length, d L (u, v) ≥ |{ i| 0, |v| } v i ∈ A +
τ |, because every edition sequence must delete at least all letters of A + τ from v, and as many letters from u. Also remark that if a is from a terminal maximal component, then τ t (a) contains no letter from A + τ C , by definition. By combining the previous two arguments, we get that for every

u ∈ (A + τ C ) * and v ∈ A * such that |u| = |τ t (v)|, d L (u, τ t (v)
) is at least the sum, for all v i that come from a terminal maximal component, of the |τ t (v i )|. In particular, for every m ∈ N,

d L τ t (x) 0,|τ t (y 0,km )| , τ t (y 0,km ) ≥ m-1 ∑ i=0 τ t (y ki ) ≥ τ t (y 0,km ) - m-1 ∑ i=0 τ t (y ki,(k+1)i ) ≥ τ t (y 0,km )   1 - 1 1 + ∑ m-1 i=0 |τ t (y ki )| ∑ m-1 i=0 |τ t (y ki,(k+1)i )|    . Now there exist α, β > 0 such that, for t ∈ N large enough, we have |τ t (a)| < αρ t -for every a ∈ (A + τ C ) N and |τ t (a)| > β ρ t + for every a ∈ A + τ N .
After renormalizing, we get:

d L τ t (x) 0,|τ t (y 0,km )| , τ t (y) 0,|τ t (y 0,km )| τ t (y 0,km ) ≥ 1 - 1 1 + β (k-1)α ρ + ρ - t
Overall, we obtain:

d L (x, y) ≥ lim sup m→∞ d L τ t (x) 0,|τ(y 0,km )| , τ t (y) 0,|τ t (y 0,km )| τ(y 0,km ) = 1.
Since k was taken arbitrary, y is arbitrarily close to x, so that x is 1 --unstable.

Apart from the subalphabet argument from Point 2 of Theorem 40, it is usually quite hard to prove lower bounds for the Feldman pseudo-metric. In particular, we have no example of a dill map without equicontinuous infinite word.

Example 42. The Fibonacci substitution τ is primitive, so τ is equicontinuous in the Feldman space, though almost no point is equicontinuous in the Besicovitch space (see Example 23).

Example 43. Let F be the Xor CA. Then neither

F d L nor F d H is equicontinuous. Indeed, let us prove that 0 ∞ is 1 --unstable. Let k ∈ N, and y = 0 2k-1 1. Then d L (x, y) ≤ d H (x, y) ≤ 1 2 k . A classical induction on k gives that F 2 k -1 (y) = 1 ∞ (for more details see [Kůr03, Example 5.6]). Hence: d H (F p (x), F p (y)) = d L (F p (x), F p (y)) = 1.
Figure 1 illustrates that 1 ∞ is also a nonequicontinuous point. Example 44. Let τ be a substitution defined as follows :

τ : 0 → 1 1 → 00.
Then, M(τ) = 0 1 2 0 and M(τ) 2 = 2 0 0 2 . Hence, M(τ) is irreducible. So, according to Corollary 41, we deduce that τ d L is equicontinuous. More precisely, τ 2 is actually the doubling substitution, proven to be 1-Lipschitz by Corollary 39. Besides, it can be shown that the latter is even an isometry: the longest common subword of τ 2 (u) and τ 2 (v) is always obtained from doubling a common subword of u and v.

Though primitive or uniform substitutions behave smoothly in our paces, other substitutions may be more pathological.

Example 45. Let τ be a substitution defined over A = {0, 1} N as follows :

τ : 0 → 0 1 → 11.
We can remark that, M(τ) = 1 0 0 2 , and, M n (τ) = 1 0 0 2 n . Hence there are two compenents, {0} and {1}, the latter being the the maximal compenent, so A + τ = {1}. Then, according to Theorem 40, 1 ∞ is an equicontinuous point of τ d L and 0 ∞ is not, as illustrated in Figures 45 and45 (where 1 is represented in black, and 0 in red). We have seen in the Besicovitch space (see 29) that the orbits a dill map may not converge towards its classical limit set. We conjecture that this does not occur in the Feldman space. [GRK20, ORW82b], prove together, among other results, that the limit set of a primitive substitution is a singleton in the Feldman space. The tools involved may be useful to understand our question.

Expansiveness

For the case of Besicovitch space, it is already proved in [START_REF] Blanchard | Cellular automata in the Cantor, Besicovitch, and Weyl topological spaces[END_REF] that there is no expansive CA over this space. By the same method, we prove that there is no expansive CA over the Feldman space. Note that it does not derive directly from the corresponding result in the Besicovitch space, because some infinite words could be in the same Feldman class, hence not concerned by the expansiveness property, but not in the same Besicovitch class.

Theorem 46. There is no expansive CA in the Feldman space.

Proof. Let F be a CA with diameter θ and local rule f . Let ε > 0 and p ∈ N such that 1 1+p < ε. To prove that F is not expansive it is enough to find two infinite words at nonzero Feldman pseudo-metric such that d L (F n (z), F n (z )) < ε, ∀n ∈ N. From the proof of the case of Besicovitch space [START_REF] Blanchard | Cellular automata in the Cantor, Besicovitch, and Weyl topological spaces[END_REF] we can take x, y ∈ A N such that :

x = 0 n 1 1 n 0 0 n 3 1 n 2 • • • . y = 1 n 1 0 n 0 1 n 3 0 n 2 • • • .
We now distinguish four cases, depending on the image of 0 θ and 1 θ .

1. The first case is when f (0 θ ) = f (1 θ ) = 0. We find d L (F(x), 0 ∞ ) ≤ d H (F(x), 0 ∞ ) = 0, then we take z = 0 ∞ and z = x, since :

d L (F t (0 ∞ ), F t (x)) ≤ d H (F t (0 ∞ ), F t (x)) < ε, ∀t ∈ N.
2. If f (0 θ ) = 0 and f (1 θ ) = 1 we find d L (F(x), x) ≤ d H (F(x), x) = 0, then:

d L (F t (0 ∞ ), F t (x)) ≤ d H (F t (0 ∞ ), F t (x)) = 1 n + 1 < ε, ∀t ∈ N.
3. If f (0 θ ) = 1 and f (1 θ ) = 1 we find d L (F(y), 1 ∞ )d H (F(y), 1 ∞ ) = 0, then:

d L (F t (1 ∞ ), F t (y)) ≤ d H (F t (1 ∞ ), F t (y)) < ε, ∀t ∈ N.
4. If f (0 θ ) = 1 and f (1 θ ) = 0 then :

• d L (1 ∞ , F(0 ∞ )) ≤ d H (1 ∞ , F(0 ∞ )) = 0 and d L (F(1 ∞ ), 0 ∞ ) ≤ d H (F(1 ∞ ), 0 ∞ ) = 0.
• d L (F(x), y) ≤ d H (F(x), y) = 0 and d L (x, F(y)) ≤ d L (x, F(y)) = 0.

Hence: d L (F t (0 ∞ ), F t (x)) ≤ d H (F t (0 ∞ ), F t (x)) = 1 n + 1 < ε, ∀t ∈ N.

Then we found two pairs of infinite words (x, 0 ∞ ) and (y, 1 ∞ ) such that:

d L (F t (0 ∞ ), F t (x)) ≤ ε, and d L (F t (1 ∞ ), F t (y)) ≤ ε.

On the other hand, we can remark that d L (x, 0 ∞ ) > 0 and d L (y, 1 ∞ ) > 0. Hence, F is not expansive.

Conclusion and perspective

In this paper, we study CA, substitutions and in general dill maps over two non trivial topological spaces (Besicovitch space and Feldman space). Those spaces were constructed using two pseudo-metrics depending on two different edit distances over finite words (Hamming distance and Levenshtein distance). Over the Feldman space, the shift is equal to the identity, there are no expansive CA, every substitution is well-defined and admits at least one equicontinuous point. This topology turns out to be a suitable playground for the study of the dynamical behavior of dill maps. The construction of the Feldman pseudo-metric was made only by changing the Hamming distance with another edit distance. This makes it natural to suggest global definition, using any distance d over the set of finite words:

Definition 47. We define the centred pseudo-metric, denoted by C d , as follows: The Weyl space shares many properties with the Besicovitch space; one of the main differences is that it is not complete, according to [START_REF] Downarowicz | Quasi-uniform convergence in compact dynamical systems[END_REF]; in terms of dynamics an open question is whether there exists an expansive cellular automaton over the Weyl space. A relevant question is now the following: Which properties of distance d make dill map well-defined in the corresponding pseudometrics?

Generalizations exist of Besicovitch pseudometrics over groups (see for instance [START_REF] Ła | Quasi-uniform Convergence in Dynamical Systems Generated by an Amenable Group Action[END_REF][START_REF] Capobianco | A Characterization of Amenable Groups by Besicovitch Pseudodistances[END_REF]). An interesting work would be to generalize more of these metrics to this setting. Let us replace (N, +), generated by 1, by a monoid (M, •) generated by a finite set G , that we assume without torsion element: for every g ∈ M, g k k ∈ N is infinite. A pattern with finite support U ⊂ M is u ∈ A U . If U = g • V , then the translate by g ∈ M of a pattern u is the pattern σ g (u) defined over support V such that σ g (u) i = u g•i . The deletion D g j at position j ∈ M with respect to generator g ∈ G is the function mapping any pattern u with some support U into the pattern v defined over support V = U \ jg k jg k+1 / ∈ U ∪ jg k jg k+1 ∈ U by v jg k = u jg k+1 , v i = u i otherwise. By torsion-freeness, |V | = |U \ {i}|. Now one can consider, as a variant of the Levenshtein, the following: the distance d M (u, v) between patterns u and v is the minimal number m + m of deletions such that D g 1 j 1 • D g 2 j 2 • • • • D g m j m (u) and D

g 1 j 1 • D g 2 j 2 • • • • D g m j m (u)
have a common translate. The Feldman-like pseudo-metric over configurations of A M , endowed with a spanning sequence (F n ) n∈N of finite sets of M, would then be:

d M = lim sup n→∞ d M (x F n , y F n |F n | .
It is not clear exactly when this pseudo-metric would not behave pathologically, but probably Føolner conditions should be assumed (see [START_REF] Capobianco | A Characterization of Amenable Groups by Besicovitch Pseudodistances[END_REF]).

4.

  The matrix M(τ) = (M(τ) ab ) a,b∈A is defined such that M(τ) ab is the number |τ(a)| b of occurrences of b in τ(a). M τ can be written in block-triangular form. An irreducible component (or matrix block) is a maximal subalphabet A such that for all a, b ∈ A , b appears in τ t (a), for some t ∈ N.

Example 4 .

 4 Let A = {0, 1}.

  and both these pairs of words share a common suffix of length at least θ -1. Assume without loss of generality that k = | f * (u)| -| f * (v)| > 0.

Figure 1 :

 1 Figure 1: A non-equicontinuous point with respect to d L and d H .

Figure 2 :

 2 Figure 2: 1 ∞ is equicontinuous point for τ.

Figure 3 :

 3 Figure 3: 0 ∞ is a non-equicontinuous point for τ.

C

  d (x, y) = lim sup l→∞ d(x 0,l , y 0,l ) max u,v∈A l d(u, v), ∀x, y ∈ A N .On the other hand, a similar pseudo-metric known as Weyl pseudo-metric, also based on d H , measures the density of differences between two given sequences in arbitrary segments of given length. A general definition, based on any distance d over finite words, would become: Definition 48. We define the sliding pseudo-metric, denoted by S d , as follows:S d (x, y) = lim sup l→∞ max k∈N d(x k,k+l , y k,k+l ) max u,v∈A l d(u, v), ∀x, y ∈ A N .


Marie-Laure Viaud

Aventures et mésaventures d'un projet : l'histoire d'un Déclic

Depuis bientôt trois ans, une équipe d'enseignants et de parents demande la création en région parisienne d'un collège-lycée innovant, dans l'Education Nationale, où des enseignants volontaires pourraient élaborer, appliquer et évaluer un projet pédagogique fondé sur la pédagogie Freinet ( 1 ).

La pédagogie Freinet est une pédagogie centrée sur l'enfant qui apporte des réponses théoriques et pratiques à ce qu'il est convenu d'appeler l'échec scolaire. Il s'agit d'accorder, dès le plus jeune âge des responsabilités aux élèves, en leur faisant découvrir, par la pratique, la nécessité de lois pour la vie en groupe, et donc en société. Il s'agit également de les faire participer activement à leurs apprentissages, à travers une pédagogie basée sur l'expression et la communication (Correspondance -papier, télécopie, vidéo, internet-, journaux scolaires, conférences, débats, comptes rendus...), et en suscitant l'esprit de recherche et le tâtonnement expérimental, dans des situations vraies. Il s'agit enfin de mettre en place des structures qui favorisent la coopération et non la compétition (entraide, travail en groupes de besoin, évaluation sous forme de brevets...) et d'individualiser les parcours de formation pour s'adapter au besoin et au rythme de chacun (fichiers autocorrectifs, Réseaux d'Echanges de Savoirs...).

L'association « D.E.C.L.I.C » (Développement Expérimental d'un Collège-Lycée d'Initiative Citoyenne), à l'origine de ce projet, doit constater aujourd'hui que l'ouverture de l'établissement qu'ils demandent n'a toujours pas pu avoir lieu.

Les promoteurs du projet sont singulièrement isolés : le noyau dur des parents sympathisants « déclic » s'est fort peu étoffé au fil des années ; et à notre connaissance, il n'existe pas et n'a pas existé en France depuis plus de vingt ans de mouvement associatif analogue ( 2 ). On est alors conduit à s'interroger : alors que les symptômes du mal-être dans les établissements scolaires sont nombreux -multiplication des actes de violence, absentéisme des élèves, désarroi des enseignants, pourquoi n'existe pas de demande sociale forte, ni de la part des enseignants, ni de la part des parents, en faveur de l'ouverture de collèges et de lycées différents ?

Par ailleurs, bien que ce projet, en tous points conforme à la loi d'orientation de 1989, ait reçu des centaines de pré-inscription et le soutien d'élus, de mouvements pédagogiques, de nombreuses personnalités comme Ph. Meirieu, P.G. De Gennes, J.P. Rosenczweig, il rencontre d'incompréhensibles barrages administratifs dans l'Education Nationale et a déjà été remis par deux fois. Comment expliquer que l'administration de l'E.N. n'autorise toujours pas l'ouverture de ce collège-lycée ?

Pour éclairer ces interrogations, je propose une série de questions et de réflexions suscitées par l'expérience de trois ans de travail associatif avec des parents et enseignants, et par de multiples contacts avec différents acteurs de l'administration de l'E.N. Bien évidemment, il ne s'agit que du point de vue d'un des acteurs de ce mouvement.

Les parents et enseignants que nous avons rencontrés, ce qu'ils nous ont dit d'eux-mêmes et de leurs collègues ou de leurs amis, montrent d'abord que même plongés dans le plus vif désarroi, ils ne sont pas massivement demandeurs d'une pédagogie différente.

S'agissant tout d'abord des enseignants à qui nous avons présenté le projet depuis trois ans, la question qui se pose est la suivante : n'ont-ils pas du mal à imaginer un système radicalement différent de celui qu'ils connaissent ? Cela tiendrait à plusieurs causes. Tout d'abord, la plupart des enseignants n'ont jamais quitté l'univers des salles de classe et il est très difficile de modifier des pratiques qui semblent avoir toujours existé (notation, 18 h/ semaine, statuts, emplois du temps découpés en tranches de 55 minutes, totale liberté pédagogique...). Les enseignants ont également souvent été, dans le passé, de bons élèves : ils ont du mal à remettre en cause un système qui leur a permis de réussir. Enfin, la majorité d'entre eux ne connaît pas ni les grands courants pédagogiques, ni les classes Freinet, P.I., ou l'existence des établissements expérimentaux. Korczak, Freinet, Montessori, Deligny, Oury... restent pour eux des noms creux : ils n'en ont pas entendu parler dans les IUFM et ne cherchent pas à s'informer dans les domaines qui relèvent du champ de leur activité professionnelle (3 ). Ainsi, on ne leur donne pas -et ils ne se donnent pas-les moyens d'imaginer comment des pédagogies différentes pourraient fonctionner.

Les militants pédagogiques, eux, sont de plus en plus rares dans le second degré -ainsi, le secteur 2d degré de l'ICEM-Freinet, qui était très actif dans les années 70, a quasiment cessé ses activités aujourd'hui. Peut-on penser que le métier d'enseignant engendre une fatigue nerveuse telle que, le soir et le week-end, les enseignants n'ont plus envie d'entendre parler de pédagogie... ce qui, de façon assez paradoxale, pourrait peut-être expliquer qu'ils ne luttent pas pour modifier les conditions d'exercice de leur métier.

Si les enseignants n'arrivent pas à imaginer « autre chose », pourquoi les parents, eux, ne l'exigent-ils pas ? L'expérience de DECLIC amène à se demander s'il n'existerait pas chez certains d'entre eux du moins une sorte de culture du secret : « quand on a une information, on la garde pour soi » ? Ainsi, ils épuisent une énergie considérable à trouver d'abord « le bon établissement », puis les options rares qui permettent d'être dans « la bonne classe »... et ils gardent jalousement ces informations. Ils restent assez isolés, « mon enfant d'abord » étant un mot d'ordre bien peu fédérateur pour qui voudrait susciter un combat commun. Et quand ils trouvent une école « différente » ou une pédagogie alternative, ils semble que les parents raisonnent à nouveau, même s'ils n'en sont pas conscients, sur le mode « il n'y en aura pas pour tout le monde » : la plupart des parents qui ont rejoint le projet DECLIC l'avaient connu par les médias et non par le bouche à oreille... et à leur tour, beaucoup n'en ont pas parlé autour d'eux . Le nombre de parents pré-inscrits et impliqués ne se n'est accru que très lentement alors que l'inverse aurait été beaucoup plus profitable au projet.

A contrario, l'exemple de la création de la « Calandreta », le seul collège-lycée à pédagogie Freinet créé dans l'Education Nationale... en langue occitane (4 ), montre que lorsque les parents se rencontrent et coopèrent -ici dans le cadre de la défense d'une langue régionale-, ils peuvent tout à fait obtenir de l'Education Nationale l'ouverture d'un établissement innovant.

Par ailleurs, beaucoup de parents connaissent mal les écoles différentes et ils ont souvent l'impression qu'ils ne donneraient pas toutes les chances à leur enfant en choisissant un de ces établissements : ils préfèrent souvent attendre la « dernière extrémité » (redoublement, triplement, renvoi...) pour chercher alors, dans l'urgence et la panique du mois de juin, un établissement différent. Chaque année, au printemps, nombre de ces parents contactent Déclic sur le thème « mon enfant triple, au secours, prenez-le ». Ils veulent consommer une « autre école » tout de suite, pas la créer.

Au delà de ces essais d'explication des comportements des uns et des autres, le rapport entre individu et société est peut-être en cause. Dans une période où « les gens ne se prennent pas en main », vouloir créer un établissement différent dans l'E.N., n'est-ce pas une initiative aux antipodes de ce que l'on vit ? Ce qui expliquerait que parents et enseignants soient si peu nombreux à s'investir dans une démarche militante ?

Il semble tout d'abord que demander l'ouverture d'une école différente dans l'E.N. soit une démarche bien inhabituelle en France. Ainsi, au sein de l'association, certains des parents et des enseignants, même adhérents, se contentent... d'attendre l'ouverture ! A l'école, ils n'ont jamais appris à prendre des initiatives, « à se lancer, à mener un projet dans la durée, à se confronter aux difficultés, à se casser la figure, à persévérer malgré tout » (5 ). Et leurs propos amènent à penser qu'ils sont habitués à ce que le service public prenne tout en charge, comme si dans la culture française où l'Etat décide de tout, les citoyens ne se sentaient pas le droit de prendre des initiatives. Créer une école, cette démarche semble particulièrement contre nature et contre culture chez les fonctionnaires que sont les enseignants : c'est la négation de l'esprit de la fonction publique. On ne voit pas des postiers dire « on voudrait un bureau de poste ici, et qui fonctionne comme ci et comme ça »... Parmi ceux qui militent, rares sont d'ailleurs sont qui sont prêts à consacrer une fraction importante de leur temps et de leur énergie à DECLIC. L'image des pionniers des premiers établissements expérimentaux -40 heures de travail par semaine et les joies du ménage ou de la comptabilité-agit plutôt comme un repoussoir. Finalement, pour certains, le mouvement DECLIC ne joue-t-il pas le rôle d'un rêve collectif qui permettrait de mieux supporter le quotidien ?

Enfin, il faut prendre en compte le fait que les parents du mouvement DECLIC sont des parents des classes moyennes... alors que les praticiens des méthodes actives, eux, se sont toujours données pour « mission» de donner accès à la culture aux enfants du peuple : ce sont des pédagogies populaires et émancipatrices. L'association DECLIC n'a-t-elle pas rencontré le bon public ? Ou bien n'y a-t-il pas aujourd'hui d'interlocuteur dans le milieu populaire ? Peut-on penser que s'il y avait, aujourd'hui, des mouvements sociaux perceptibles, la demande pour la création d'établissements différents serait plus forte ?

Reste la question de l'administration de l'Education Nationale. En effet, même s'il n'y a pas eu une forte mobilisation des enseignants ou des parents, des centaines de citoyens ont tout de même demandé l'ouverture du projet DECLIC. Pourtant, depuis trois ans, l'E.N. n'a pas permis l'ouverture de cet projet.

On peut d'abord noter l'étrange façon dont le projet a été reçu. Les responsables du projet ont eu à faire à près d'une dizaine d'interlocuteurs différents, Recteurs, Inspecteurs d'Académie, Conseillers du Ministre, qui se sont renvoyés la responsabilité : le blocage vient d'un peu tout le monde et de personne en particulier. Par ailleurs, il n'y a jamais eu de refus officiel, comme si l'E.N. ne pouvait ni refuser un tel projet (dont les grandes lignes recoupent les déclarations ministérielles récentes) ni dévoiler la véritable raison de son refus. Les différents interlocuteurs de DECLIC ont souvent commencé par dire tout le bien qu'ils pensaient du projet (« on a besoin de gens comme vous »), puis par évoquer différents prétextes (« ce n'est pas la priorité... ») avant de multiplier les obstacles pour empêcher l'ouverture, décourager ses promoteurs, repousser les ouvertures promises.

L'attitude de l'administration amène à avancer une nouvelle hypothèse : peut-être peut-on penser que le système est aujourd'hui prêt à exploser, et qu'il ne tient que parce que, par ci par là, dans les établissements, différentes équipes temporisent avec les gamins les plus durs, servent de tampon avec les familles qui ruent dans les brancards ? Parce que, par ci par là, un « Freinétique » en fait un peu plus ou un peu autrement, parle un peu aux parents, dédramatise un conseil de discipline ?... Les établissements les plus durs survivent parfois grâce à un ou deux enseignants particulièrement dynamiques qui « portent tout à bout de bras », et quelques parents élus au conseil d'administration et au conseil de discipline jouent le même rôle. Que deviendraient ces établissements si ces parents et ces enseignants se regroupaient dans un établissement expérimental ou innovant ? L'administration de l'E.N. semble en être parfaitement consciente et tout faire pour que les parents et les enseignants motivés restent éparpillés.

Peut-être peut-on également penser que si un établissement à pédagogie Freinet était ouvert et fonctionnait correctement, cela signifierait que la réponse aux difficultés actuelles du système est d'ordre pédagogique, et non d'ordre quantitatif, et que c'est donc la structure traditionnelle qu'il faut changer. Qui y aurait intérêt ...?

Nos interlocuteurs de l'E.N., eux, ont souvent évoqué le « poids des lobbies » : syndicats ou éditeurs de manuels scolaires défendent des privilèges, ils disparaîtraient si le système était bouleversé, et s'opposent donc à tout changement. Il n'y a pas lieu ici de se prononcer, mais de noter que l'administration de l'E.N. évoque cet argument, et surtout la crainte d'affrontements avec les syndicats, pour justifier son immobilisme.

Finalement, au delà de toutes les raisons « raisonnables » énumérées ci-dessus, pourquoi estil si difficile pour les Français de changer l'école ? Les blocages ne tiennent-ils pas aussi à un comportement collectif dépourvu de fondements rationnels ? En effet les rapports entre les Français et l'école sont si passionnés, les débats à ce sujet si peu étayés par des arguments rigoureux ( 6), que les explications devraient, peut-être, être recherchées du côté des mythes et de l'imaginaire collectif (7 ).

On peut prendre l'exemple de l'attachement à l'égalité, qui trouve ses racines dans l'histoire et marque profondément l'inconscient collectif. Considérant presque comme sacrée toute phrase qui contient le mot « égalité », beaucoup de Français s'imaginent qu'il y a « égalité des chances » quand « tous les élèves entendent le même discours dans des classes considérées comme égales » (8 ). Ce qui les conduit bien souvent à s'opposer aux pédagogies qui prennent en compte la diversité des élèves... et à l'existence de structures pédagogiques « différentes ».

Par ailleurs, peut-être, dans leur inconscient collectif, les Français ont-ils peur de toute nouveauté et/ou innovation dans le domaine éducatif ?On peut se poser la question en voyant le succès des « républicains » qui s'opposent à toutes les réformes, ou en remarquant que « l'expression « méthodes modernes » qui, dans tous les champs de l'activité humaine, revêt un caractère positif, passe abruptement d'une acceptation méliorative à un signifié péjoratif lorsqu'on entre dans le domaine scolaire (9 ) ».

Bien d'autres comportements posent question : on ne peut pas tous les citer ici, mais simplement s'interroger sur la part de l'inconscient collectif dans les rapports entre les Français et l'école... part qui est bien souvent un frein aux innovations.

Tout ceci peut-il, doit-il décourager les partisans d'un collège-lycée différent ? A l'heure actuelle, les animateurs de l'association DECLIC se trouvent face à plusieurs perspectives. Certains sont tentés par l'ouverture d'un établissement privé dans un cadre associatif. D'autres proposent de s'implanter beaucoup plus fortement dans un quartier, d'y ouvrir un local, afin de donner au projet une véritable assise populaire et de créer un véritable mouvement social demandeur d'un autre type d'établissements. Dans tous les cas, l'Education Nationale gagnerait à rattraper des parents et des enseignants qui risquent de s'éloigner d'elle.

Projet DECLIC, 152 bd. Vincent Auriol, 75013 Paris (declic93@hotmail.com).

R. Auffrand, Annuaire des écoles différentes, Agence-Information-Enfance, Paris,1999.

0,3 à 1 % des enseignants lisent des revues spécialisées (Cahiers Pédagogiques, la Revue française de pédagogie, Pratiques...) cf C.ETEVE et C.GAMBART, Ce que lisent les enseignants, INRP, Paris, 1992.

La fédération Calandretas Midi-Pyrénées (56 rue Tour, 31000 Toulouse) regroupe de nombreuses écoles primaires et depuis trois ans un collège-lycée. L'enseignement est bilingue français/occitan et fondé sur la pédagogie institutionnelle, très proche de la pédagogie Freinet.

M.D. Pierrelée, Pourquoi vos enfants s'ennuient en classe, Syros 1999, p.155.

Voir l'article de Ph. Meirieu sur les « républicains », Libération, 8 septembre 1999, où il qualifie leurs discours de « dénonciations incantatoires » dépourvues d'argumentations solidement étayées et d'analyses précises.

R.Barthes, Mythologies, Paris, Seuil, 1957 et R.Girardet, Mythes et mythologies politiques, Paris, Seuil, 1986.

M.D. Pierrelée, op.cit., p.189.

Jean Desoli, Boulet rouge pour tableau noir, Syros 1997, page 42.