Guillaume Theyssier
email: guillaume.theyssier@cnrs.fr

A Gajardo
email: angajardo@udec.cl

V Nesme

Pre-Expansivity in Cellular Automata

Keywords: cellular automata, linear cellular automata, 2-dimensional cellular automata, expansivity, chaos, directional dynamics 2010 MSC: 68Q80, 37B15

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The model of cellular automata is at the crossroads of several domains and is often the source of surprisingly complex objects in several senses (computationally, dynamically, etc).

From the point of view of dynamical systems and symbolic dynamics, the theory of cellular automata is very rich [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Kůrka | Topological and symbolic dynamics[END_REF][START_REF] Pivato | The ergodic theory of cellular automata[END_REF][START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF] and tells us, on the one hand, that CA are natural examples of chaotic systems that can perfectly fit the standard notions developed in a general context, and, on the other hand, that they have special properties allowing and justifying the development of a refined and dedicated theory. For instance, the structure of the space of configurations allows to define the notion of an asymptotic pair of configurations: two configurations that differ only on finitely many positions of the lattice. The Garden of Eden theorem, which has a long history [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Moore | Machine models of self-reproduction[END_REF][START_REF] Myhill | The Converse of Moore's Garden-of-Eden Theorem[END_REF][START_REF] Ceccherini-Silberstein | Amenable groups and cellular automata[END_REF][START_REF] Bartholdi | Gardens of eden and amenability on cellular automata[END_REF][START_REF] Bartholdi | Amenability of groups is characterized by myhill's theorem[END_REF][START_REF] Machi | Garden of eden configurations for cellular automata on Cayley graphs of groups[END_REF][START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF] and is emblematic of this CA specific theoretical development, then says that surjectivity is equivalent to pre-injectivity (injectivity on asymptotic pairs) if and only if the lattice is given by an amenable group.

Two important lines of questioning have been particularly developed and provide some of the major open problems of the field [START_REF] Boyle | Open problems in symbolic dynamics[END_REF]:

• surjective CA and their dynamics;

• how does CA theory changes when changing the lattice.

In particular, the classical notion of (positive) expansivity has been applied to CA giving both a rich theory in the one-dimensional case [START_REF] Blanchard | Dynamical properties of expansive one-sided cellular automata[END_REF][START_REF] Kůrka | Topological and symbolic dynamics[END_REF][START_REF] Nasu | Nondegenerate q-biresolving textile systems and expansive cellular automata of onesided full shifts[END_REF] and a general inexistence result in essentially any other setting [START_REF] Shereshevsky | Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms[END_REF][START_REF] Pivato | Positive expansiveness versus network dimension in symbolic dynamical systems[END_REF]. Even in the one-dimensional case where positive expansivity is equivalent to being conjugated to a one-sided subshift of finite type [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF], it is interesting to note that outside the linear and bi-permutative examples, few construction techniques are known to produce positively expansive CA [START_REF] Jadur | On the dynamics of cellular automata induced from a prefix code[END_REF]. On the other hand, it is still unknown whether positive expansivity is a decidable property, although it is indeed decidable for some algebraic cellular automata [START_REF] Lena | Decidable properties for regular cellular automata[END_REF][START_REF] Lukkarila | On undecidable dynamical properties of reversible onedimensional cellular automata[END_REF].

In this paper, we introduce a new dynamical property called pre-expansivity that both generalizes positive expansivity and refines pre-injectivity: it is the property of being positively expansive on asymptotic pairs. Our motivation is to better understand surjective CA and expansive-like dynamics, in particular in the higher-dimensional case or in lattices where the classical notion of positive expansivity cannot be satisfied by any CA [START_REF] Shereshevsky | Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms[END_REF][START_REF] Pivato | Positive expansiveness versus network dimension in symbolic dynamical systems[END_REF]. Pre-expansivity is weaker than positive expansivity. We show examples of pre-expansive CAs which are not positively expansive. In such CA, some perturbations on infinitely many cells does not propagate at all, while every finite perturbation will be eventually seen in the neighborhood of every cell: it is the finiteness of the perturbation that allows the propagation on every direction.

Pre-expansivity is interesting in that:

1. a reversible CA can be pre-expansive (see section 5), while none can be positively expansive [START_REF] Coven | Every compact metric space that supports a positively expansive homeomorphism is finite[END_REF]; 2. pre-expansivity implies sensitivity in all directions (see Proposition 5.9), while some expansive CA (like the shift map) have equicontinuous directions.

This shows that the notion is useful in the classical setting of one-dimensional cellular automata. For other settings, the situation is left open: on one hand, we show an impossibility result for Abelian CA in dimension d ≥ 2 (see Theorem 7.1). This means that for every Abelian CA and every finite window, there will be a finite configuration that will preserve the window in state 0 forever. On the other hand, we give several examples of k-expansive CA in this setting and on the free group, where k-expansivity means positive expansivity over pairs of configurations with exactly k differences.

The paper is organized as follows. In Section 2 we give the main definitions and results we need to work on cellular automata on groups. In section 3, we focus on Abelian cellular automata and develop a toolbox for this class that is used later in different sections. As an aside, we prove that such CA are always predictable in logarithmic space complexity. In Section 4, we introduce preexpansivity and k-expansivity, and we give some preliminary results which do not depend on the group defining the space. In Section 5, we restrict to the group Z and give various examples of cellular automata which are pre-expansive but not positively expansive, including a characterization for a particular family of non-linear CA, namely multiplication CA. In Section 6, we consider the free group and show that k-expansivity is possible for infinitely many values of k although positive expansivity is impossible. Finally, in Section 7, we restrict to the group Z 2 and we study some k-expansive examples for particular values of k but also show that there is no pre-expansive Abelian cellular automaton.

Formal Setting and Classical Definitions

We will work on cellular automata defined over a finitely generated group G. We will consider Abelian and non-Abelian groups, but since most of our examples are given for Abelian groups, we will prefer the additive notation for G.

Fixing a generator set G, that is closed under inversion, a norm can be defined in G: given z ∈ G, ||z|| is the length of the shortest sequence g 1 g 2 ...g n of elements in G such that z = g 1 + g 2 + ... + g n . This norm induces a metric in G naturally, and given a non-negative integer r we can define also the ball of radius r and center z as the set B r (z) = {x ∈ G | || -z + x|| ≤ r}. Given a point z ∈ G and two sets X, Y ⊆ G, we accept the following notation.

z + S = {z + x | x ∈ S}, and X + Y = {x + y | x ∈ X, y ∈ Y }
Cellular automata are functions defined on the symbolic space Q G = {c : G → Q | c is a function}. An element c, called configuration, assigns a symbol of Q to each element of the group G, sometimes called cells. We will use both c(z) and c z to denote the value of c at the cell z. A natural G-action on Q G is the shift: given z ∈ G, the function: A cellular automaton (CA) is an endomorphism of Q G , compatible with the shift G-action and continuous for the Cantor distance. From Curtis-Hedlund theorem [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF], every cellular automaton F is characterized by a local function f : Q V → Q, where V ⊂ G is finite and called neighborhood of F , as follows.

σ z : Q G → Q G is
∀c ∈ Q G , ∀z ∈ G, F (c)(z) = f (σ z (c)| V )
Every function defined in this way is a cellular automaton. Basic properties of F such as surjectivity and injectivity have been considered and played an important role in CA theory because they were proved to be efficiently decidable in dimension 1 but undecidable in higher dimensions [START_REF] Kari | Reversibility and surjectivity problems of cellular automata[END_REF][START_REF] Amoroso | Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures[END_REF]. The weaker notion of pre-injectivity says that, for every pair of different asymptotic configurations c and d, their image by F are different:

c ∞ = d and c = d ⇒ F (c) = F (d).
The so-called Garden-of-Eden theorem establishes that surjectivity is equivalent to pre-injectivity, which in particular implies that injective CAs are also bijective (equivalently reversible by Curtis-Hedlund Theorem, i.e. having an inverse which is also a CA). It was first proved in particular cases [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Moore | Machine models of self-reproduction[END_REF][START_REF] Myhill | The Converse of Moore's Garden-of-Eden Theorem[END_REF] and later it was shown that it holds exactly when the group G is amenable, i.e. when it admits a finitely additive measure which is invariant under its action [START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF].

The pair (Q G , F ) is a dynamical system and can be studied from the point of view of topological dynamics. The present work proposes a new particular kind of topological unpredictability. Weaker and stronger notions in this area are the following.

A CA F is sensitive if there exists a number δ > 0, called sensitivity constant, such that for every c and every there exists an instant t ∈ N and a configuration

d ∈ B (c) such that ∆(F t (c), F t (d)) ≥ δ.
A stronger notion is expansivity, which can be of two kinds, and depends on whether the CA is reversible or not. Given T be equal to either N or Z, a CA F is called T-expansive if there exists a number δ > 0, called expansivity constant, such that for every c = d there exists an instant t ∈ T such that ∆(F t (c), F t (d)) ≥ δ. In this work we will almost always consider positive times only (i.e. T = N) and refer to N-expansivity as positive expansivity. Accordingly we will stick to positive times in the definition of pre-expansivity below. This choice is particularly relevant for one-dimensional reversible CA, since they all possess a direction of Z-expansivity 3 , none has a direction of N-expansivity, but having directions of pre-expansivity is a non-trivial property illustrated for instance by Proposition 5.9.

Denote by T m : Q G → (Q Bm(0) ) N the trace function which to any configuration associates its orbit restricted to B m (0):

T m (c) = t → F t (c) | Bm .
A CA F is positively expansive if and only if T m is injective for some m, in which case we get a conjugacy between F acting on Q G and the one-sided shift acting on T m Q G [START_REF] Kůrka | Topological and symbolic dynamics[END_REF].

If G = Z, given a one-dimensional CA with local rule f : Q [-l,r] → Q with l, r > 0, we say that it is LR-permutive when for any q -l , . . . , q r ∈ Q the two following maps are bijective.

a → f (a, q -l+1 , . . . , q r ) a → f (q -l , . . . , q r-1 , a) LR-permutive are always positively expansive.

Abelian CA: Definitions and Toolbox

The class of Abelian CA will be an important source of examples in the sequel. This section establishes a number of properties used later on for both positive and negative results. These properties are essentially folklore knowledge or extensions of already published results, mainly in [START_REF] Gütschow | The fractal structure of cellular automata on abelian groups[END_REF]. We however give detailed proofs below because our setting is more general than the usual one. In particular, as far as we know, Corollary 3.6 was never written in this level of generality, and Lemma 3.8 is new. The reader can skip this section in a first read: the following definition is used everywhere, but the main results established below are only used in section 7. Definition 3.1. Let (Q, ⊕ ) be a finite group and denote by ⊕ the componentwise extension of ⊕ to Q G and by 0 the configuration identically equal to 0

. A CA F over Q G is linear if ∀c, d ∈ Q G : F (c ⊕ d) = F (c) ⊕ F (d).
When (Q, ⊕ ) is an Abelian group we say that F is Abelian, which is equivalent to the fact that F verifies an equation of the form:

F (c) z = i∈V h i (c z+i )
for any configuration c, where the sum corresponds to the ⊕ law and where V is the neighborhood of F and h i are endomorphisms of (Q, ⊕ ).

Given a ∈ Q, we denote by c a the configuration that is equal to e (identity of the group Q) everywhere except at cell 0 where its value is a. Any space time diagram of a linear CA is a sum of translated copies of space-time diagrams with initial configuration of the form c a .

The case where (Q, ⊕ ) is a cyclic group has received much more attention in the literature than the general Abelian case. We would like to stress the importance of considering the general case. First, it was already established that some dynamical behaviors related to randomization are possible in the general case but not in the cyclic case [START_REF] Hellouin De Menibus | Characterizing asymptotic randomization in abelian cellular automata[END_REF]Thms 3 and 4]. Second, we will show in section 5 below (Proposition 5.10 and Theorem 5.15) that pre-expansivity is equivalent to positive expansivity in the cyclic case while there are reversible (therefore not positively expansive) pre-expansive CA in the general Abelian case.

The following lemma shows that Abelian CA can be decomposed according to the structure of the group. It is a folklore knowledge that appears often in the particular case of cyclic groups [START_REF] Itô | Linear cellular automata over Zm[END_REF][START_REF] Manzini | A complete and efficiently computable topological classification of d-dimensional linear cellular automata over Zm[END_REF], and also in the more general Abelian case [START_REF] Gütschow | The fractal structure of cellular automata on abelian groups[END_REF].

Recall that the product F × G of two CA F and G is the CA defined on the product alphabet and applying F and G on each component independently. Lemma 3.2. Let Q = Q p × Q be an Abelian group (law + and neutral element (0, 0)) where Q p is a p-group (the order of every element is a power of p) for some prime p and the order of Q is relatively prime with p.

Then, any Abelian CA F over Q is isomorphic to F p × F where F p is an Abelian CA over Q p and F is an Abelian CA over Q .

Proof. By linearity of

F , if c satisfies that n • c = n c + • • • + c = (0, 0), then F (c)
must satisfy the same: n • F (c) = (0, 0). We deduce that the subset of states

Q 1 = Q p × {0 Q } induces a subautomaton F 1 of F because any configuration c ∈ Q G 1 is such that p k • c = (0, 0) for some k and no configuration in Q \ Q 1 G has this property. Moreover if n • c = (0, 0) for n relatively prime with p, it implies that c ∈ Q G 2 = {0 Qp } × Q G (
because the order of an element must divide the order of the group it belongs to). Therefore

Q 2 induces a subautomaton F 2 of F . Now, any c ∈ Q G can be written c = c 1 + c 2 where c 1 ∈ Q G 1 and c 2 ∈ Q G 2
through cellwise and componentwise decomposition, and

F (c) = F 1 (c 1 ) + F 2 (c 2 ). F 1 is isomorphic to a linear CA F p over Q p and F 2 to a linear CA F over Q , and then F is isomorphic to F p × F .
Given an Abelian CA F , spot configurations (i.e. configurations c everywhere 0 except in one cell) form a basis of the whole set of configurations and we get the orbit of any configuration by summing the orbits of corresponding spot configurations. The main point of this section is the existence of a substitutive structure describing the space time diagram of spot configurations in an Abelian CA over p-groups when the underlying spatial structure is Z d . This in turns comes from the fact that such CA verify multiscale additive identities. Intuitively, a multiscale additive identity is the generalization to the Abelian setting of a linear dependency present in any space-time diagram between a finite set of cells whose relative positions correspond to a basic shape or a blowup of it of factor α p for some given α.

These facts were established in [START_REF] Gütschow | The fractal structure of cellular automata on abelian groups[END_REF] in the one-dimensional setting. We give below a proof in any dimension d using essentially the same approach. Definition 3.3. Let F be a d-dimensional Abelian CA over (Q, ⊕). We say that F has a multi-scale additive identity if there is some scale factor α ≥ 2, M > 0, a finite set X = {( z 1 , t 1 ), . . . , ( z k , t k )} with 0 ≤ t i < M for all 1 ≤ i ≤ k and endomorphisms (h i : Q → Q) 1≤i≤k such that for any n ∈ N and any configuration c it holds:

F M α n (c) = 1≤i≤k h i • F tiα n • σ α n zi (c)
where the sum correspond to law ⊕ over configurations and h i is the componentwise extension of

h i to Q G . Example 3.4. Consider the CA F : Z Z 2 → Z Z 2 , defined by F (c) = c+σ(c). It is straightforward to check that F 2 n (c) = c+σ 2 n (c)
for all n. In this case k = 2, M = 1, X = {(0, 0), (1, 0)}, α = 2 and h 1 = h 2 = id.

Similar multi-scale additive identities where no F appears on the right hand side can be derived using the binomial formula as soon as the Abelian CA

F (c) z = i∈V h i (c z+i )
is such that the h i are commuting endomorphisms. The situation is a bit more complex in the general case when the h i do not commute. However, we have the following lemma. Lemma 3.5. Any d-dimensional Abelian CA is a Cartesian product of Abelian CA admitting multi-scale additive identities.

Proof. First, it is sufficient to prove that Abelian CA over p-groups (p prime) admit multi-scale additive identities since any Abelian CA is a Cartesian product of such CA (Lemma 3.2). Second, it is sufficient to consider Q a p-group of the form Q = Z D p l because any Abelian CA on a p-group is a subautomaton of some Abelian CA on a group of this form (Proposition 1 of [START_REF] Gütschow | The fractal structure of cellular automata on abelian groups[END_REF]), and a multi-scale additive identity in some CA holds in any of its subautomata. Then, an Abelian CA of dimension d over the group Q = Z D p l can be viewed as a D × D matrix whose coefficients are Laurent polynomials with d variables u 1 , . . . , u d and coefficients in Z p l (see for instance [START_REF] Kari | Linear cellular automata with multiple state variables[END_REF] for more details on this representation).

Formally, we denote by Z p l [u i , u -1 i ] 1≤i≤d the ring of Laurent polynomials with variables u 1 , . . . , u d , i.e. the ring of linear combinations of monomials made with positive or negative powers of the variables and coefficients in Z p l . A monomial corresponds to a vector of Z d , hence we use the notation u i for any

i = (i 1 , . . . , i d ) ∈ Z d to denote the monomial u i1 1 • • • u i d d . A linear cellular automaton is identified with some T ∈ M D Z p l [u i , u -1 i ] 1≤i≤d
where the coefficient a z ∈ Z p l of the monomial u z of the coefficient T i,j of the matrix T means that, when applying the CA, the layer j of cell z 0 receives a z times the content of the layer i of cell z + z 0 , and all these individual contributions are summed-up. This matrix representation is correct in the sense that F n is represented by T n .

By the Cayley-Hamilton theorem (Laurent polynomials form a commutative ring), the characteristic polynomial of T gives a relation of the form:

T m = m-1 j=0 i∈I λ i,j u i T j
for some m ≤ |D|, some finite I ⊆ Z d , and where λ i,j ∈ Z p l .

By standard techniques (binomial theorem and Kummer's theorem), we have the following identity on any commutative ring of characteristic p l (this is done explicitly in Lemma 10 of [START_REF] Hellouin De Menibus | Characterizing asymptotic randomization in abelian cellular automata[END_REF]):

i X i p n+l-1 = i X p n i p l-1
for any positive n. Then, applying this to the expression of T m obtained above we get:

T m•p n+l-1 =   m-1 j=0 i∈I λ p n i,j u p n • i T p n •j   p l-1
.

Noting that the sequence (λ p n i,j ) n is ultimately periodic, we can choose a large enough common period N so that for all i, j and all n ≥ 1:

λ p nN i,j = λ p N i,j .
Denoting α = p N and expanding the right-hand side of the above equality, we have for some M large enough, some finite I ⊆ Z d , and µ i,j ∈ Z p l (0 ≤ j < M and i ∈ I ):

T M α n = M -1 j=0 i∈I µ i,j u α n i T jα n
for any n ≥ 1. This is exactly a multi-scale additive identity of scale α expressed in the matrix representation of F and the lemma follows.

The following corollary shows that Abelian CA are computationally "easy" to predict. Particular cases of this statement is folklore knowledge (see [START_REF] Moore | Predicting non-linear cellular automata quickly by decomposing them into linear ones[END_REF]) and it is mentioned in the generality of Abelian CA in [START_REF] Gütschow | The fractal structure of cellular automata on abelian groups[END_REF] (based on Lemma 3.7 bellow). We give here a simple proof of this fact using existence of multi-scale additive identities.

Corollary 3.6. For any d-dimensional Abelian CA F with alphabet Q and radius r, the following prediction problem is computable in LOGSPACE:

• input : a finite pattern u ∈ Q Brn(0) and q ∈ Q,

• question : do we have F n (u) = q, i.e. F n (c) = q for any c with c |Brn(0) = u? Proof. Using Lemma 3.5 it is sufficient to give a LOGSPACE algorithm for Abelian CA with multi-scale additive identities (the Cartesian product is handled by sequentially computing each component which doesn't change the LOGSPACE complexity). Therefore let's suppose that F has the following multi-scale additive identity (using notation of definition 3.3):

F M α n (c) = 1≤i≤k h i • F tiα n • σ α n zi (c).
An algorithm to evaluate F t (c) z is a recursive application of the above identity with the maximal possible value for n at each application and until reaching terms corresponding to time steps strictly less than M α (which can be evaluated in constant time). Concretely if n is the largest integer with M α n ≤ t we get

F t (c) z = 1≤i≤k h i • F α n ti+t-M α n (c) α n zi+ z and α n t i + t -M α n ≤ t (M -1)α n +t-M α n t ≤ t M α-1
M α since t < M α n+1 by hypothesis on n and the ratio (M -1)α n +t-M α n t is increasing with t. This shows that the depth of recursive calls in the algorithm is logarithmic in t (at most log M α M α-1 (t) ) and since the recursive branching width is constant (exactly k) it is actually doable in LOGSPACE. More precisely, it can be done in the following way:

• m ← log M α M α-1 (t) ; • sum ← 0 (identity of group (Q, ⊕));
• for each b ∈ {1, . . . , k} m do:

-h ← Id ∈ Q Q ; -t ← t; -z ← z;
for each i from 1 to m and while t ≥ M α do:

The algorithm explores successively each branch of the tree of recursive calls (variable b) and for each of them (which is of depth at most m) it does a descent from the root to the leaf (variable i) and accumulate the sequence of endomorphisms to be applied at each level (variable h) while computing the new current position of space-time (variables t and z ). For the prediction problem of checking whether F n (u) = q for some u ∈ Q Brn(0) , we apply the above algorithm with t = n and z = 0 so m is logarithmic in the input size and all variables used have a logarithmic size. Lemma 3.7. Let F be any d-dimensional Abelian CA with a multi-scale additive identity. Then there exists a substitution of factor α describing space-time dependency, that is to say, there exists:

• α ≥ 2, • a finite set E, • e : Z d × N → E, • Ψ : E → (Q → Q),
• T ∈ N and, for any 0 ≤ t 0 < α and z 0 ∈ Z d with z 0 ∞ < α, a function Φ t0 z0 : E → E such that, for any t ≥ T e(α z + z 0 , αt + t 0 ) = Φ t0 z0 e( z, t)

• Γ t z = Ψ(e( z, t))
where Γ t z is the space-time dependency function given by:

Γ t z : q → σ z • F t (c q ).
Proof. Taking the notations of Definition 3.3 we suppose that for any n ∈ N and any configuration c it holds:

F M α n (c) = 1≤i≤k h i • F tiα n • σ α n zi (c)
where the sum correspond to law ⊕ over configurations. This identity extends to the space-time dependency function by choosing c = c q and composing both sides by a common translation and a common power of F , so that for any n ∈ N and any r ∈ N and any z ∈ Z d we have:

Γ α n M +r z (c) = 1≤i≤k h i • Γ α n ti+r α n zi+ z . (1)
Applying this identity recursively, we can reduce any Γ t z to a sum of terms of the form h • Γ t z where t < M α. More precisely, we define the labeled k-regular DAG D F whose vertex set is Z d × N and such that each vertex ( z, t)

• is a leaf if t < M α;

• has the following k children:

χ i ( z, t) = (α n z i + z, α n t i + r) for 1 ≤ i ≤ k where n = max{m : M α m ≤ t} and r = t -M α n , and the edge e = ( z, t), χ i ( z, t) is labeled by λ(e) = h i .
The multi-scale property of Equation 1 translates into D F as follows. Consider any z 0 ∈ Z d and any t 0 < α.

If we denote by τ z0,t0 : Z d × N → Z d × N the transformation such that τ z0,t0 ( z, t) = (α z + z 0 , αt + t 0 ), then we have:

• χ i (τ z0,t0 ( z, t)) = τ z0,t0 (χ i ( z, t)) when ( z, t) is not a leaf; • if e = ( z, t), χ i ( z, t) and e = τ z0,t0 ( z, t), τ z0,t0 χ i ( z, t) then λ(e) = λ(e ).
Indeed, as soon as t ≥ αM , if n = max{m : M α m ≤ t}, we have that n + 1 = max{m : M α m ≤ αt + t 0 } and αr + t 0 = αt + t 0 -M α n+1 , where r = t -M α n . From this we deduce that to any path from ( z, t) to a leaf l ∈ Z d × N corresponds a path from τ z0,t0 ( z, t) to τ z0,t0 (l) with same labels. Conversely any path from τ z0,t0 ( z, t) to some leaf admits as prefix a path from τ z0,t0 ( z, t) to τ z0,t0 (l) where l is a leaf. Formally, if P z,t z ,t denotes the set of path from ( z, t) to ( z , t ) in D F and L the set of leaves we have

l∈L P τ z 0 ,t 0 ( z,t) l = l∈L P τ z 0 ,t 0 ( z,t) τ z 0 ,t 0 (l) • l ∈L P τ z 0 ,t 0 (l) l
where '•' denotes the concatenation of paths.

For any

M ∈ N, let Y M = {( z, t) : t < M α and z ∞ ≤ M }.
For any z 0 with z 0 ∞ < α and t 0 < α the (Euclidean) distance between ( z, t) and τ z0,t0 ( z, t) goes to infinity as z ∞ grows. On the other hand, when t < M α, the set of positions ( z , t ) reachable from ( z, t) in D F is finite and they are all at bounded (Euclidean) distance from ( z, t). This implies that for any large enough M , we have the following property: if there is a path in D F from some τ z0,t0 (l) to Y M with l ∈ L and z 0 ∞ < α and t 0 < α, then l ∈ Y M . Let now choose X = Y M with M large enough to have the above property and also such that any ( z, t) ∈ L with Γ t z = 0 (i.e. is not the constant map equal to 0) belongs to Y M . From Equation 1 and by definition of D F and X, we have for any z ∈ Z d and any t ∈ N:

Γ t z = ( z ,t )∈X ρ∈P z,t z ,t ρ=e1,••• ,em λ(e 1 ) • • • • • λ(e m ) • Γ t z . (2)
We define

E = Q Q X and e : Z d × N → E by e( z, t) =          ( z , t ) → id if ( z , t ) = ( z, t), 0 else. if ( z, t) is a leaf, ( z , t ) → ρ∈P z,t z ,t ρ=e1,••• ,em λ(e 1 ) • • • • • λ(e m ) else.
Then the map Ψ :

E → (Q → Q) defined for any f ∈ Q Q X by Ψ(f ) = ( z,t)∈X f ( z, t) • Γ t z is such that Ψ e( z, t) = Γ t
z by definition of e and Equation 2. Finally, for any ( z, t) ∈ L and any z 0 with z 0 ∞ < α and t 0 < α, we have:

e(τ z0,t0 ( z, t)) = ( z , t ) → ρ∈P τ z 0 ,t 0 ( z,t) z ,t ρ=e1,••• ,em λ(e 1 ) • • • • • λ(e m ). (3)
But, as said above, any path ρ ∈ P

τ z 0 ,t 0 ( z,t) z ,t
decomposes as a concatenation of

a path ρ 1 ∈ P τ z 0 ,t 0 ( z,t) τ z 0 ,t 0 (l)
followed by a path ρ 2 ∈ P

τ z 0 ,t 0 (l) z ,t
. Since ( z , t ) ∈ X and by choice of X then l ∈ X. So ρ 1 is just the transformation under τ z0,t0 of a path from ( z, t) to l ∈ X and this transformation doesn't change the labels λ. We can then rewrite Equation 3 as:

e(τ z0,t0 ( z, t)) = ( z , t ) → y∈Y ρ∈P z,t y ρ ∈P τ z 0 ,t 0 (y) z ,t λ(ρ) • λ(ρ )
or equivalently

e(τ z0,t0 ( z, t)) = ( z , t ) → y∈Y e( z, t)(y) ρ ∈P τ z 0 ,t 0 (y) z ,t λ(ρ ).
This shows that there is a map Φ t0 z0 not depending on z or t which satisfies e(τ z0,t0 ( z, t)) = Φ t0 z0 (e( z, t)). The lemma follows by letting T = αM . The existence of this substitution has strong consequences on the structure of traces: the trace of a finite configuration is determined by a prefix of linear size in the distance of the farthest non-zero cell. Let us first define some notation. The size of a configuration c • the size of c i is less than or equal to n,

∞ = 0 is the smallest n ∈ N such that c(z) = 0 imply z ∞ ≤ n.
• T m (c 1 )(t) = T m (c 2 )(t) for any t ≤ λ(n), then T m (c 1 ) = T m (c 2 ).
Proof. First F fulfills the hypothesis of Lemma 3.7 so we have the existence of the substitution and adopt the notations of the lemma.

Let's focus on the substitution given by the function e and consider k ≥ 0, t ≥ α k T , and z ∈ Z d with z ∞ ≤ α k . By k -1 applications of the substitution we get the following expression for e( z, t):

e( z, t) = Φ t mod α z mod α • • • • • Φ t/α k-1 mod α z/α k-1 mod α e(ρ( z), t/α k )
where ρ( z) ∞ ≤ α, and where the division/modulus correspond to the standard Euclidean division on Z d . The sequence of superscripts in this expression only depends on t mod α k . The sequence of subscripts depends only on z. Therefore we can write this functional dependency of e( z, t) on e(ρ( z), t/α k ) in the following way:

e( z, t) = χ t mod α k z e(ρ( z), t/α k ) . (4)
Now consider a time t 0 sufficiently large to see before time t 0 any possible vector of the form (e( z 0 , t)) z0 ∞≤α that occur after time T , precisely:

∀t ≥ T, ∃t , T ≤ t ≤ t 0 , ∀ z 0 , z 0 ∞ ≤ α : e( z 0 , t) = e( z 0 , t ).
Given an index set I, consider any tuple ( z i ) i∈I , with z i ∞ ≤ α k , and any P ⊆ E I . For any time t, we can define the property P I (t) by: P I (t) ⇔ e( z i , t) i∈I ∈ P.

Claim: if P I (t) holds for every t ≤ (t 0 + 1) • α k then P I (t) holds for every t ∈ N.

Indeed, take some time t > (t 0 + 1) • α k . Then by choice of t 0 there exists t ≤ t 0 such that:

∀ z 0 , z 0 ∞ ≤ α : e( z 0 , t/α k ) = e( z 0 , t ). Now we can choose t ≤ (t 0 + 1) • α k with t /α k = t and t mod α k = t mod α k
and equation 4 yields the equalities:

e( z i , t) = χ t mod α k z e(ρ( z i ), t/α k ) = χ t mod α k z e(ρ( z i ), t ) = e( z i , t ).
It shows that P I (t) ⇔ P I (t ) and the claim follows.

Since the space-time dependency function is completely determined by the substitution e (Lemma 3.7), the fact that the trace of a finite configuration at time t is null can be expressed by a property of the form P I (t). More precisely, for any configuration c of size α k , we can define

D = {z ∈ Z d : c(z) = 0}, I = z∈D B m (z), P = {f ∈ E I : ∀x ∈ B m (0), z∈D Ψ(f z+x )(c(z)) = 0}.
We then have that

P I (t) ⇔ ∀x ∈ B m (0), z∈D Ψ(e(z + x, t))(c(z)) = 0 ⇔ ∀x ∈ B m (0), z∈D Γ t z+x (c(z)) = 0 ⇔ z∈D T m (σ -z (c c(z) )) t = 0 ⇔ T m (c) t = 0.
We deduce that if F t (c) is null on B m (0) until time (t 0 + 1) • α k then it is null forever. By linearity of F , equality of two traces is equivalent to nullity of their difference. We have thus shown the lemma for m ≥ 0 by choosing

λ(n) = (t 0 + 1) • α k for k = log α (n) .

Pre-expansivity

Pre-expansivity is the property of positive expansivity restricted to asymptotic pairs of configurations.

Definition 4.1. Let F be a cellular automaton over Q G . F is pre-expansive if: ∃δ > 0 : ∀c, d ∈ Q G , c = d and c ∞ = d ⇒ ∃t ∈ N, ∆(F t (c), F t (d)) > δ.
The value δ is the pre-expansivity constant. Remark 4.2.

• Cellular automata can be seen as examples of two continuous commuting actions on a metric space: the spatial action S (the G-shift) and the temporal action F (the cellular automaton itself ). The definition of preexpansivity can be adapted to this general settings by requiring that F be expansive on pairs of S-asymptotic configurations. This goes far beyond the scope of the present paper which focuses on cellular automata.

• Pre-expansivity is a conjugacy invariant: if a cellular automata F and F on Q G are conjugated via φ (i.e. φ is an automorphism of the fullshift

Q G with F • φ = φ • F ), then F is pre-expansive if and only if F is. Indeed, c ∞ = d is equivalent to φ(c) ∞ = φ(d)
and for all there is δ such that ∆(φ(c), φ(d)) > implies ∆(c, d) > δ.

The notion of pre-expansivity can be further refined by considering only pairs of configurations with a fixed finite number of differences. Given c, d

∈ Q G , we denote c = k d if # z ∈ G : c(z) = d(z) = k, i.e. if c and d differ in exactly k positions. Definition 4.3. Let F be a cellular automaton over Q G and let k > 0. F is k-expansive if: ∃δ > 0 : ∀c, d ∈ Q G , c = k d ⇒ ∃t ∈ N, ∆(F t (c), F t (d)) > δ. Proposition 4.4. Let F be any CA over Q G , it holds: 1. F is pre-expansive ⇒ ∀k > 0 F is k-expansive, 2. F is k-expansive ⇒ F is sensitive to initial configurations, 3. F is pre-expansive ⇔ T m is pre-injective for some m. 4. If L is a CA over QG , then F × L is k -expansive for every k ≤ k if and only if L and F are k -expansive for every k ≤ k. 5. F positively expansive ⇒ F pre-expansive ⇒ F pre-injective, moreover if G is amenable then F pre-expansive ⇒ F surjective.
Proof.

1. It follows directly from definitions. 2. It is enough to note that for any configuration c, any δ > 0 and any k ≥ 1 there always exist a configuration c with c = k c and ∆(c, c ) ≤ δ. 3. For the third item, it is sufficient to note that the existence of some time t such that ∆ F t (c),

F t (c ) > δ is equivalent to T m (c) = T m (c ) for a suit- able choice of m. 4. If F × L is k -expansive,
it is enough to take two configurations with their differences in only one of their components, since both automata act independently, k -expansivity of F ×L imply that the perturbations will arrive to the center at the same component, proving the k -expansivity of the corresponding automaton.

If now L and F are k -expansive for every k ≤ k, we take two configurations with k differences. They may lay in one or both of their components, in any case there will be 0 < k ≤ k differences in one of the components of F × L. By the k -expansivity of the corresponding automaton, we show the k -expansivity of F × L. 5. It is clear that positive expansivity implies pre-expansivity (restriction of the universal quantification). Then pre-expansivity implies pre-injectivity because if there is a pair of configurations c, c with c ∞ = c and F (c) = F (c ) then, eventually applying a translation, we can also suppose them such that ∆(c, c ) is arbitrarily small. Finally, if G is amenable we also have that pre-injectivity implies surjectivity by Garden of Eden Theorem [START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF].

Note however that k-expansivity does not generally imply pre-injectivity or surjectivity as shown by the following example. Proposition 4.5. For any k ≥ 1 there exists a one-dimensional CA which is not surjective but k -expansive for any k ≤ k.

Proof. Consider any pre-expansive one-dimensional CA F of radius 1 over state set Q = {0, 1} (for instance a bi-permutative CA), and define a CA Ψ over state set Q k+1 as follows. It has k +1 "layers" and to any configuration c we associate its projection π i (c) on the ith layer. Intuitively it behaves on the k first layers as k independent copies of F , except that the (k + 1)th layer induce a state flip in the image in the following way: if it has a 1 at position z then, in the image, layer i is flipped at position z + 3i. Moreover, (k + 1)th layer is uniformly reset to 0 after one step. Formally, Ψ is defined by:

Ψ(c) z = F (π 1 (c)) z + π k+1 (c) z-3 mod 2, . . . , F (π k (c)) z + π k+1 (c) z-3k mod 2, 0
First it is clear from the definition that it is not surjective since the image of any configuration is always 0 on layer k + 1. Note also that, when reduced to state set {0, 1} k × {0}, Ψ is isomorphic to F k which is pre-expansive. Therefore, to show that Ψ is k -expansive for any 1 ≤ k ≤ k, it is sufficient to show that for any pair of configurations c and d with c = k d we have Ψ(c) = Ψ(d).

So consider such a pair (c, d). Ψ was defined such that, if c and d differ on the (k + 1)th layer at position z, then, on the ith layer, F (c) and F (d) will differ at position z + 3i as soon as c and d are the same on the ith layer at positions z + 3i -1, z + 3i and z + 3i + 1. Therefore, supposing that c and d indeed differ on the (k + 1)th layer at position z, it implies that F (c) and F (d) differ because c and d having only k ≤ k differences, they can not differ at z and at one of the positions z + 3i -1, z + 3i or z + 3i + 1 for each 1 ≤ i ≤ k.

Finally, suppose that c and d are equal on the (k + 1)th layer. Then they must differ on some layer i with 1 ≤ i ≤ k. Therefore, we must have F (π i (c)) = F (π i (d)). We deduce that Ψ(c) = Ψ(d) because their respective ith layers are F (π i (c)) and F (π i (d)) up to some modification by the (k + 1)th layer which are identical in c and d.

The next lemma talks about linear CA. When F is supposed to be linear (for law ⊕ ), then T m is also linear, i.e.

T m (c ⊕ d) = T m (c) ⊕ T m (d) where ⊕ denotes the component-wise application of ⊕ either on Q G or on Q Bm N .
Proposition 4.6. Let F be a linear CA for law ⊕ and neutral element 0. Let I be the set

I = {k ∈ N : F is not k-expansive} • if k 1 , k 2 ∈ I then k 1 + k 2 ∈ I,
• F is pre-expansive if and only if for some m > 0 there is no finite sequence (g 1 , . . . , g n ) of different cells in G and states (q 1 , . . . , q n ) in Q such that From what we said above, for any m 1 there is c 1 such that c 1 = k1 0 and T m1 (c 1 ) = T m1 (0). Now choose m 2 large enough so that any non-zero state of c 1 appears at distance at most m 2 from the center. Let us remark that the differences between c 1 and 0 are outside B m1 , otherwise T m1 (c 1 ) = T m1 (0), thus m 2 > m 1 . Since k 2 ∈ I we deduce from what we said earlier that there is c 2 such that c 2 = k2 0 and T m2 (c 2 ) = T m2 (0). By our choice of m 2 , this implies that T m1 (c 1 ⊕ c 2 ) = T m1 (0). Moreover c 1 ⊕ c 2 = k1+k2 0. Since m 1 was arbitrary, we deduce that F is not (k 1 + k 2 )-expansive.

T m (σ g1 (c q1 )) ⊕ • • • ⊕ T m (σ gn (c qn )) = 0.

1-dimensional Cellular Automata

The 1-dimensional setting is particular in our study since it allows examples of all properties considered in this paper, and gives additional structure to analyze them.

The first goal of this section is to show that the notion of k-expansivity, pre-expansivity and positive expansivity all differ and interact differently with properties of bijectivity and surjectivity. More precisely we will show the following existential result.

Theorem 5.1. Let B and S denote the set of bijective and surjective CA respectively. Let X 1 , X pre and X pos denote the set of 1-expansive, pre-expansive and positively expansive CA respectively. It holds:

• X pre ∩ (B \ X pos ) = ∅, • X pre \ (B ∪ X pos ) = ∅, • X 1 ∩ (B \ X pre ) = ∅, • X 1 \ (X pre ∪ B) = ∅, • X 1 \ S = ∅.
We therefore have the following situation:

∩ B S \ B S c X 1 \ X pre ∃ ∃ ∃ X pre \ X pos ∃ ∃ ∅ X pos ∅ ∃ ∅
For this purpose it will be sufficient to focus on linear cellular automata. At the end of the section, we consider a well-known class of non-linear bijective CA where pre-expansivity is a relevant property. But before the study of examples, we give some additional results which hold in dimension 1.

Left/right propagation and directional dynamics

The pre-expansivity constant can be fixed canonically as we will prove in Lemma 5.4. The next lemma is direct and it expresses the locality of CAs.

Lemma 5.2. Let F be a CA in Z with neighborhood [-l, r] the next assertions hold.

• If c ]-∞,n] = d ]-∞,n]
and there exists an iteration t such that

F t (c) ]-∞,n] = F t (d) ]-∞,n] , then there is an iteration t ≤ t such that F t (c) [n-r,n] = F t (d) [n-r,n] . • If c [n,∞[ = d [n,∞[
and there exists an iteration t such that

F t (c) [n,∞[ = F t (d) [n,∞[ , then there is an iteration t ≤ t such that F t (c) [n,n+l] = F t (d) [n,n+l] .
Proof. We will only prove the first assertion, the second one is completely analogous. Let t be the first time such that

F t (c) ]-∞,n] = F t (d) ]-∞,n] , and let i ∈] -∞, n] be a position such that F t (c) i = F t (d) i . Since F t -1 (c) ]-∞,n] = F t -1 (d) ]-∞,n]
, and only the cells in ]n -r, n] depend on cells in ]n, ∞[, i ≥ n -r.

This lemma shows a particularity of dimension 1: expansivity properties can be understood through left/right propagation of information. Let us precise this notion.

Definition 5.3. Given two configurations c = d, and a CA F , we define the left and right propagation sequences as follows. (l d t (c)) t∈N is not lower bounded and (r d t (c)) t∈N is not upper bounded, then F is k-expansive with pre-expansivity constant 2 -max{l,r} . Proof.

l d t (c) = inf{z ∈ Z : F t (c) (z) = F t (d) (z)} r d t (c) = sup{z ∈ Z : F t (c) (z) = F t (d) (z)} Note that if c ∞ = d then l d t (
1. If F is k-expansive, then ∀c = k d, (l d t (c)) t∈N is not lower bounded and (r d t (c)) t∈N is not upper bounded. 2. If ∀k ≤ k, ∀c = k d,
1. Let us suppose that F is k-expansive with pre-expansivity constant m. Let c = k d be two configurations, and let us assume that l d t (c) > n for some n ∈ Z; this means that

F t (c) ]-∞,n] = F t (d) ]-∞,n] for every t ∈ N. Thus T m (σ n-m (c)) = T m (σ n-m (d))
, which is a contradiction. The analogous happens if (r d t (c)) t∈N is upper bounded. 2. We need to prove that F is k-expansive with pre-expansivity constant 2 -m = 2 -max{l,r} . Let c = k d be two configurations, and let us define the next two additional configurations. If k = 0, (l d t (c r )) t∈N is not lower bounded, thus by Lemma 5.2 and the fact that c r is equal to d below position m, there is a minimal iteration t r such that

c l (i) = c(i) if i < 0 d(i) if i ≥ 0 c r (i) = d(i) if i < 0 c(i) if i ≥ 0 If c [-m,m] = d [-m,m] , T m (c) = T m (d)
F tr (c r ) [m-r,m] = F tr (d) [m-r,m] . Analogously, if k = 0 there is a minimal iteration t l such that F t l (c l ) [-m,-m+l] = F t l (d) [-m,-m+l] .
Let us take t = min{t r , t l }, by the choice of m we have that

F t (c) [0,m] = F t (c r ) [0,m] and F t (c) [-m,0] = F t (c l ) [-m,0]
, and at least one of them is different from

F t (d) between [-m, m], thus T m (c) = T m (d).
The last lemma establishes that the pre-expansivity constant is uniform in dimension one (it does not depends on k), thus we can conclude the next corollary.

Corollary 5.5. If F is k-expansive for every k ∈ N then it is pre-expansive. Left and right propagation determines also expansivity. The next lemma can be proven by using the techniques from the last lemmas.

c, d, if c ]-∞,0] = d ]-∞,0] then (l d t (c)) t∈N is not lower bounded, and if c [0,∞[ = d [0,∞[ then (r d t (c))
t∈N is not upper bounded. The last two lemmas show a similarity in information propagation between pre-expansivity and positive expansivity: the differences between two configurations are spread both to the left and to the right and thus there is a sensitivity to initial conditions in all directions. We can formalize this following the directional dynamics setting of [START_REF] Sablik | Directional dynamics for cellular automata: A sensitivity to initial condition approach[END_REF] (we could also use the more general viewpoint of [START_REF] Delacourt | Directional dynamics along arbitrary curves in cellular automata[END_REF] but we prefer to keep a lighter setting for clarity of exposition). Let α ∈ R. A CA F is said to be pre-expansive in direction α if there is some δ > 0 such that

∀c, d ∈ Q Z , c = d and c ∞ = d ⇒ ∃t ∈ N, ∆(σ αt • F t (c), σ αt • F t (d)) > δ.
In particular, pre-expansivity in direction 0 is the same as pre-expansivity. Similarly F is said to be sensitive to initial conditions in direction α if there is some δ > 0 such that

∀c ∈ Q Z , ∀ > 0, ∃d ∈ Q Z ∃t ∈ N : ∆(c, d) < ∧∆(σ αt •F t (c), σ αt •F t (d)) > δ.
Remark 5.8. Lemma 5.6 generalizes to the directional dynamics setting: F is pre-expansive in direction β if and only if for all c ∞ = d, (l d t (c) -βt ) t∈N is not lower bounded and (r d t (c) -βt ) t∈N is not upper bounded. In particular, if the CA neighborhood is N ⊆ {l, . . . , r}, then its set of preexpansivity directions is included in ] -r, -l[. Proposition 5.9. Let F be any CA which is pre-expansive in some direction α. Then the following holds:

1. F is sensitive to initial conditions in any direction; 2. if F is also pre-expansive in direction α > α then it is pre-expansive in any direction β with α ≤ β ≤ α .

Proof. We first deduce that if α ≤ β ≤ α and α is a direction of pre-expansivity, then for any c = d with c ∞ = d:

l d t (c) -βt ≤ l d t (c) -αt is not lower bounded and
r d t (c) -βt ≥ r d t (c) -α t is not upper bounded so β is also a direction of pre-expansivity.
Finally, consider a direction β ≥ α (the case β ≤ α is symmetric), some configuration c and some > 0. Take any d = c with c ∞ = d and l d 0 (c) large enough so that ∆(c, d) ≤ . Since (l d t (c) -αt ) t∈N is not lower bounded and β ≥ α then there is some t with l d t (c) -βt ≤ 0. Let t 0 be the smallest such t. Since |l d t+1 (c) -l d t (c)| is bounded by the radius of F we deduce that there exists a constant M , depending only on β and the radius of F , such that

M ≤ l d t0 (c) -βt ≤ 0. Said differently ∆(σ βt0 • F t0 (c), σ βt0 • F t0 (d)) ≥ 2 M .
We have thus shown that F is sensitive in direction β.

Hierarchy of expansive-like properties

The following proposition shows that the simplest form of linearity is not sufficient to achieve the separation between positive expansivity and pre-expansivity. Let us first introduce some notation. Proposition 5.10. Let Z n be the group of integers modulo n with addition, and let F be a one-dimensional linear CA over Z n . Then F is 1-expansive if and only if it is positively expansive.

Proof. First by Proposition 4.4 if F is positively expansive it is in particular 1-expansive.

For the other direction, it is sufficient to consider the case n = p k with p a prime number by Lemma 3.2 because if some F 1 × F 2 is 1-expansive then both F 1 and F 2 must be 1-expansive.

By commutation with shifts we have l 0 t (σ n (c a )) = -n + l 0 t (c a ) and the analogous for r t . Moreover c a = a • c 1 because we are on a cyclic group.

Let us define

l U t (c a ) = min{i ∈ Z | gcd(F t (c a ) i , p) = 1}. The next properties hold. 1. If gcd(a, p) = 1, then l U t (c a ) = ∞ (respectively r U t (c a ) = -∞).
In fact, in this case the entire evolution of F over c a is composed by multiples of a, which are multiples of p too.

If gcd(a

, p) = 1, then l U t (c a ) = l U t (c 1 ) (respectively r U t (c a ) = r U t (c 1 )). In fact, in this case F t (c a ) i = aF t (c 1 ) i is coprime with p if and only if F t (c 1 ) i is. 3. l 0 t (c a ) ≤ l U t (c 1 ) (respectively r 0 t (c a ) ≥ r U t (c 1 )
). In fact, if F t (c 1 ) i is coprime with p, then F t (c a ) i = aF t (c 1 ) i is not null. 4. l 0 t (c p k-1 ) = l U t (c 1 ) (respectively r 0 t (c p k-1 ) = r U t (c 1 )). In fact,

F t (c p k-1 ) i = p k-1 F t (c 1 ) i = 0 ⇔ gcd(F t (c 1 ) i , p) = 1.
From the last assertion and Lemma 5.4 (first item) we have that l U t (c 1 ) is not lower bounded and r U t (c 1 ) is not upper bounded. Now let us take a configuration v ∈ (Z p k ) Z , such that v i = 0 for every i < 0 and v 0 = 0. Let us define j = max{i ∈ {0, ..., k} | ∀x ∈ Z, p i |v(x)}, and let us consider u = v/p j . In this way, there is y ≥ 0 with u(y) = 0 and gcd(p, u(y)) = 1. Let y be the smallest integer with this property.

F t (u) l U t (c 1 )+y = l U t (c 1 )+y+rt x=0 F t (c ux ) l U t (c 1 )+y-x
But u(x) is a multiple of p when x < y, thus F t (c ux ) i = 0 mod p for any i and any x < y. For x > y, F t (c ux ) l U t (c 1 )+y-x is also a multiple of p because the smallest index for which F t (c ux ) is coprime with p is l U t (c ux ) which is greater than or equal to l U t (c 1 ). In this way we conclude that

F t (u) l U t (c 1 )+y = F t (c uy ) l U t (c 1
) mod p is coprime with p and is non null. Therefore F t (v) l U t (c 1 )+y is non null as well. This implies that l 0 t (v) is not lower bounded. Symmetrically, r 0 t (w) is not upper bounded when w is any configuration equal to zero on positive coordinates. Lemma 5.7 concludes that F is positively expansive.

To establish a separation between positive expansivity and pre-expansivity, we will focus on linear CA obtained by what is often called "second order method" in the literature [START_REF] Margolus | Physics-like models of computation[END_REF]. The idea is to turn any CA into a reversible one by memorizing one step of history and combining, in a reversible way, the memorized past step into the produced future step. The interest of this construction for our purpose is that positive expansivity is excluded from the beginning because no non-trivial CA can be positively expansive and reversible at the same time [START_REF] Coven | Every compact metric space that supports a positively expansive homeomorphism is finite[END_REF].

Let Q = {0, . . . , n -1} be equipped with some group law ⊕ and consider some CA F over state set Q. The second-order CA associated to F and ⊕ , denoted SO F, ⊕ is the CA over state set Q × Q, which is conjugated through the natural bijection

Q Z × Q Z → (Q × Q) Z to the map: (c, d) → d, F (d) ⊕ c
The following proposition shows that second order construction is useful to separate positive expansivity from 1-expansivity. Some of the results in the next proposition can be deduced from more general results in [START_REF] Lukkarila | On undecidable dynamical properties of reversible onedimensional cellular automata[END_REF][START_REF] Lena | Decidable and computational properties of cellular automata[END_REF][START_REF] Kitchens | Expansive dynamics on zero-dimensional groups[END_REF], but we develop a new specific proof here. Proposition 5.11. Let ⊕ be a group law over Q with neutral element 0 and F be a CA over Q which is linear for ⊕ . It holds:

1. SO F, ⊕ is bijective and linear for the law ⊕ × ⊕ ; 2. if F is LR-permutive then SO F, ⊕ is Z-expansive and 1-expansive; 3. if F is LR-permutive then for any m > 0 the subshift of traces

T m (Q × Q) Z is a vertex SFT.
Proof.

1. It is sufficient to check that the CA over the state set Q × Q is conjugated to the following map:

(c, d) → ι(F (c)) ⊕ d, c
the inverse of SO F, ⊕ , where ι denotes the inverse function for the group law ⊕ . Moreover SO F, ⊕ is linear for ⊕ × ⊕ because it is component-wise linear for ⊕ . 2. Let us suppose that F is LR-permutive with neighborhood {-l, ..., r} and denote Ψ = SO F, ⊕ . To prove Z-expansivity of Ψ it is sufficient to notice that Ψ propagates to left and right when the second Q-component is non-null and Ψ -1 propagates to left and right when the first Q-component is non-null. In fact, let us consider a configuration c ∈ (Q × Q) Z equal to (0, 0) on negative coordinates but such that c(0) = (0, 0). If the second Qcomponent of c( 0) is non-null then, and since F (0, ..., 0) = 0, the leftmost non-null cell of Ψ(c) is at position -r and it is its second Q-component which is non-null, i. e., if the leftmost difference from (0,0) is in the second Q-component, this will be always like this and the difference will propagate to the left. The same holds symmetrically for propagation to the right. In the same way, and given the form of Ψ -1 , differences in the first Q-component will propagate to the left and right through Ψ -1 , thus by lemma 5.7, Ψ is Z-expansive. Now let us take c (a,b) (recall it is the configuration equal to (a, b) at 0 and (0, 0) everywhere else). By the previous arguments, if b = 0, (l

(0,0) t (c (a,b)
)) t∈N is not lower bounded and (r

(0,0) t (c (a,b)
)) t∈N is not upper bounded. But if b = 0 and a = 0, then (Ψ(c))(0) = (0, a) and null everywhere else, then again (l (0,0) t (c (a,b) )) t∈N is not lower bounded and (r (0,0) t (c (a,b) )) t∈N is not upper bounded. Therefore, Ψ (and Ψ -1 ) is 1expansive.

3. The proof of the third item will be performed in two steps. To simplify notations, for any pair of words u, v ∈ Q * of the same length, we will denote by u v the word over alphabet Q × Q whose projection on the first (resp. second) component is u (resp. v).

Assertion 1L: For every word u ∈ Q r there exists a configuration c such that

Ψ t (c)| [0,r-1] = u 0 r and Ψ k (c) i = (0, 0) for every 0 ≤ k ≤ t and i < (t -k)r.
Proof of Assertion 1L. By induction on t. If t = 0 it is obvious, we just take c equal to u 0 r at [0, r -1] and (0, 0) everywhere else. Now, since F is LR-permutive, given a word w ∈ Q l+r , let us define the permutation τ w (a) = f (wa) for every a ∈ Q. Given a word u ∈ Q r , we inductively define another word v ∈ Q r as follows:

v 0 = τ -1 0 l+r (u 0 ), v i+1 = τ -1 0 l+r-i v [0,i] (u i+1
). In this way, f (0 l+r v) = u. By induction hypothesis, there exists a configuration c such that Ψ t (c)| [0,r-1] = v 0 r and Ψ k (c) i = (0, 0) for every 0 ≤ k ≤ t and i < (t -k)r. We take d = σ -r (c), then Ψ t (d)| [r,2r-1] = v 0 r , and (0, 0) to the left of r; and Ψ t+1 (d)| [0,r-1] = u 0 r , and (0, 0) to the left of 0. Moreover, Ψ k (d) i = (0, 0) for every 0 ≤ k ≤ t + 1 and i < (t + 1 -k)r.

Assertion 1R: For every word u ∈ Q l there exists a configuration c such that

Ψ t (c)| [-l+1,0] = u 0 l and Ψ k (c) i = (0, 0) for every 0 ≤ k ≤ t and i > (k -t)l.
The proof of Assertion 1R is analogous to the proof of Assertion 1L.

Assertion 2: A sequence w t n t=0 , with w t ∈ (Q × Q) 2m+1 , is a finite subsequence of a trace in T m (Q × Q) Z if and only if for any t, there are extensions w R ∈ (Q × Q) r and w L ∈ (Q × Q) l verifying ψ(w L • w t • w R ) = w t+1
where ψ denotes the action of Ψ over finite words.

Proof of Assertion 2. In one direction, it is clear, so let w t n t=0 be a sequence such that for any t, there are extensions

w R ∈ (Q × Q) r and w L ∈ (Q × Q) l verifying ψ(w L • w t • w R ) = w t+1
, and let us prove that it is a subsequence of a trace of Ψ. We perform the proof by induction on n. If n = 0 there is nothing to prove, of course any sequence of length 1 can be part of a trace. Now let c be a configuration such that Ψ k (c)| [-m,m] = w k , for every k ∈ {0, ..., n -1}. By locality, only the values of c between -m -nl and m + nr are relevant to this hypothesis, and we take c(i) = (0, 0) outside these limits. Let w R and w L be such that ψ(w L • w n-1 • w R ) = w n . Let us remark that the first Q-component of w L and w R can be chosen arbitrarily, given the form of Ψ. We will suppose that π 1 (w

L ) = π 1 (Ψ n-1 (c) [-m-l,-m-1] ) and π 1 (w R ) = π 1 (Ψ n-1 (c) [m+1,m+r] ), thus we can take u L 0 l = w L -Ψ n-1 (c)| [-m-l,-m-1] and u R 0 r = w R - Ψ n-1 (c)| [m+1,m+r]
. We take from Assertion 1L a configuration c R that produces the word u R 0 r at time n -1 at position [m + 1, m + r] and (0, 0) to the left of the light cone that starts at m + nr with slope -1/r. From Assertion 1R we take a configuration c L that produces the word u L 0 r at time n -1 at position [-m -l, -m -1] and (0, 0) to the right of the light cone that starts at -m -nl with slope 1/l. By linearity,

Ψ n-1 (c L ⊕ c R ⊕ c)| [-m-l,m+r] = w L w n-1 w R , and then Ψ n (c L ⊕ c R ⊕ c)| [-m,m] = w n , moreover Ψ k (c L ⊕ c R ⊕ c)| [-m,m] = w k ,
for every 0 ≤ k < n, which completes the proof.

We will now give an example of pre-expansive CA which is not positively expansive.

Example 5.12 (Ψ). Let Q = {0, 1, 2}, + be the addition modulo 3, and F 3 be the CA defined over Q Z by F 3 = σ+σ -1 . We define Ψ as the second order construction applied to F 3 . Ψ = SO F 3 , +

Figure 1 shows a space-time diagram of Ψ.

To establish the pre-expansivity of Ψ we will study its dependency structure, i.e. how the value of the cell at position z and time t depends on value of cells at other positions and earlier times. To express these space-time relations we denote by Ψ t z the map σ z • Ψ t and by ⊕ the component-wise addition modulo 3 over {0, 1, 2} × {0, 1, 2} naturally extended to configurations of (Q × Q) Z and then naturally extended to functions on such configurations.

Following section 3, and lemma 3.5, the matrix that represents Ψ is: existence of a multi-scale additive identity, next lemma gives the precise shape of this identity in the special case of Ψ. Lemma 5.13. Let c be a configuration in (Q × Q) Z .Then, for any k ≥ 0, any t ≥ 0 and any z ∈ Z we have:

0 1 1 x -1 + x . Its characteristic polynomial is p(λ) = λ 2 -λ(x -1 + x) -1, which gives the relation Ψ 2 = Ψ • σ -1 ⊕ id ⊕ Ψ • σ. Lemma 3.

proves that this imply the

Ψ 2•3 k +t z (c) = Ψ t z ⊕ Ψ 3 k +t z-3 k ⊕ Ψ 3 k +t z+3 k (c).
Proof. First it is straightforward to check that

Ψ 2 0 (c) = Ψ 1 -1 ⊕ Id ⊕ Ψ 1 1 (c).
Then, by property of the Frobenius endomorphism, we have (a + b)

3 k = a 3 k + b 3 k
when doing the arithmetics modulo 3. This identity naturally extends to ⊕ and therefore we have:

Ψ 2•3 k 0 (c) = Ψ 3 k -3 k ⊕ Id ⊕ Ψ 3 k 3 k (c).
Finally, by linearity of both σ and Ψ with respect to ⊕ we can compose both sides of the above equality by Ψ t z and the lemma follows.

Using the above lemma, and arithmetics modulo 3, we can show that Ψ has a simple dependency structure at some space-time locations.

Q × Q. For any integers k ≥ 0 and M ≥ 1, let d M,k = Ψ M •3 k+1 (c).
Then we have:

• d M,k (-M • 3 k+1 + 2 • 3 k ) = d M,k (M • 3 k+1 -2 • 3 k ) = φ(a, b) • d M,k (i) = (0, 0) for (M -1) • 3 k+1 ≤ |i| < (M -1) • 3 k+1 + 3 k
where φ is an automorphism of Q × Q which does not depend on k nor on M .

Proof. Let's first show the two items for M = 1 and let d k = d 1,k . Denote by c t z the state Ψ t (c) (z). First, by a simple recurrence we can show that

c n -n = c n n = π(a, b) where π is the projection π(a, b) = (0, b). Then, applying Lemma 5.13 on Ψ 2•3 k +3 k -3 k
, we obtain:

d k (-3 k ) = c 2•3 k -2•3 k + c 3 k -3 k + c 2•3 k 0 .
Applying Lemma 5.13 to Ψ 2•3 k +0 0 we then have:

d k (-3 k ) = c 2•3 k -2•3 k + 2 • c 3 k -3 k + c 3 k 3 k + c 0 0 = (0, b) + 2(0, b) + (0, b) + (a, b) = (a, 2b)
where φ(a, b) = (a, 2b) is an automorphism. The same equality holds for d k (3 k ) by symmetry and the first item of the lemma is shown. |α| < 1 -2 3M . By a finite number of applications of Lemma 5.14, and by linearity and translation invariance of Ψ, we have:

Ψ M •3 k+1 (c) (r -M • 3 k+1 + 2 • 3 k ) = φ c(r) Ψ M •3 k+1 (c) (l + M • 3 k+1 -2 • 3 k ) = φ c(l) .
Since φ is a permutation of Q sending (0, 0) to itself and since c(r) and c(l) are both different from (0, 0) we deduce that l (0,0)

M •3 k+1 (c) < r -M • 3 k+1 + 2 • 3 k and r (0,0) 3 k+1 (c) > l + M • 3 k+1 -2 • 3 k
for any k large enough. This shows that l t (c) -αt t∈N is not lower-bounded and r t (c) -αt t∈N is not upper-bounded and concludes the proof by a directional version of Lemma 5.6. We now give an example of CA that is 1-expansive but not pre-expansive.

Example 5.16 (Υ). Let Q = {0, 1}, + be the addition modulo 2, and F 2 be the CA defined over Q Z by F 2 = σ+σ -1 . We define Υ as the second order construction applied to F 2 :

Υ = SO F 2 , + .
Υ has the same matrix as Ψ, the same characteristic polynomial, and a similar multi-scale identity, but arithmetics modulo 2 gives a different shape to the time space diagram as we can see in figure 3.

Proposition 5.17. Υ is not k-expansive when k ≥ 2 and in particular Υ is not pre-expansive.

Proof. Let k ≥ 2 be fixed and for each z ∈ Z define the configuration c z by:

c z (z ) =                (0, 0) if z < z, (0, 1) if z = z, (1, 1) if z < z ≤ z + k -2, (1, 0) if z = z + k -1, (0, 0) if z ≥ z + k.
We have c z = k (0, 0) and it is straightforward to check that Υ(c z ) = c z-1 . We conclude that Υ is not k-expansive by Lemma 5.6.

With these two examples we have proven two of the items of Theorem 1, this together with the preliminary results of section 3 and 4 allow us to conclude.

Proof of Theorem 5.1. Let F be any irreversible and positively expansive CA. It holds:

• Ψ is pre-expansive (by Proposition 5.15) and it is reversible and not positively expansive (by Proposition 5.11 and [START_REF] Coven | Every compact metric space that supports a positively expansive homeomorphism is finite[END_REF]);

• therefore Ψ × F is pre-expansive and irreversible and not positively expansive;

• Υ is 1-expansive and reversible (by Proposition 5.11) but it is not preexpansive (by Proposition 5.17);

• therefore Υ × F is 1-expansive and irreversible and not pre-expansive;

• finally Proposition 4.5 gives an example of 1-expansive CA which is not surjective.

Non linear examples: multiplication CA

Now we exhibit a non linear family of reversible CA that will provide us with new examples of pre-expansive CA. This family has already been considered with different points of view in the literature [START_REF] Blanchard | Dynamical properties of expansive one-sided cellular automata[END_REF][START_REF] Kari | Universal pattern generation by cellular automata[END_REF] and underlined for its links with some Furstenberg problems in ergodic theory [START_REF] Pivato | Ergodic theory of cellular automata[END_REF].

Given two natural numbers k and k , let us consider the cellular automaton F k,k on the state set Z m , with m = kk , defined as follows

F k,k (c) i = kc i %m + kc i+1 /m
where i%j denotes i mod j with operation precedence as follows: a + b%c means a + (b mod c) and ab%c means (ab) mod c. Note that F k,k (c) i is always in Z m because kc i %m ≤ k(k -1) and kc i+1 /m < k. F k,k can be seen as a multiplication by k in base kk , and the fact that there is no carry propagation ensures that it is a CA. Figure 4 shows the evolution of a finite configuration in a background of 0 under F 3,2 .

Proposition 5.18. F k,k is bijective and

F -1 k,k = F k ,k • σ -1 . Proof. We will show that F k,k • F k ,k = σ. F k,k • F k ,k (c) i = (kF k ,k (c) i )%m + kF k ,k (c) i+1 m = 0 + c i+1 -c i+1 %k + (mc i+1 )%(mk) + k c i+2 /k m = c i+1 -c i+1 %k + m(c i+1 -k c i+1 /k ) + k c i+2 /k m = c i+1 -c i+1 %k + c i+1 -k c i+1 k + c i+2 -c i+2 %k m = c i+1 + 0 + 0
from here we obtain that F k,k is surjective and F k ,k is injective, but exchanging the roles of k and k we obtain that both are bijective and we are done.

Next lemma establishes some elementary bounds on the way perturbations propagates through Z.

l d t (c) < r d 0 (c) + 1 -t log(k) log(m) . 4. l d 0 (c) -1 -t log(k) log(m) < r d t (c).
Proof.

1. The result is directly obtained from the definition of F k,k and g. We can see that I q, then F k,k is α-pre-expansive if and only if

g(F k,k (c) -F k,k (d)) is equal to: = i∈Z (kc i %m + c i+1 /k -kd i %m -d i+1 /k )m -i = i∈Z (k(c i+1 %m -d i+1 %m)m -(i+1) + i∈Z ( c i+1 /k -d i+1 /k )m -i = i∈Z (kc i+1 %m + m kc i+1 /m -(kd i+1 %m + m kd i+1 /m ))m -(i+1) = i∈Z k(c i+1 -d i+1 )m -(i+1) = kg(c -d).
• α ∈] -log m (k), -min{ ei ei+e i : i ∈ {1, . . . , I}}[ and q = 1, or • α ∈] -log m (k), 0[ and q = 1.
Proof. We need to prove that l d t (c) -βt is not lower bounded and r d t (c) -βt is not upper bounded for every c In order to prove the second fact, we will first study the way r d t (c) varies in time. Let us fist suppose that q = q f1 1 • • • q f J J . Let us suppose, without loss of generality, that r d 0 (c) = 0, and let n = |g(c -d)|, which must be a natural number. Finally, let us assume that n = o p

e 1 1 • • • p e I I q f 1 1 • • • q f J J , where o is co-prime with p 1 • • • p I q 1 • • • q J .
From Lemma 5.19 [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Kůrka | Topological and symbolic dynamics[END_REF], we know that s t = -r d t (c) is the largest natural number such that m st |k t n. But m st = o st p st(e1+e 1 ) 1 (q > 1) In this case J ≥ 1, and the condition 3 is non empty, thus for some j ∈ {1, . . . , J}, -s t -βt ≥ - I q where o and q are co-prime (but possibly 1)

• • • p st(e I +e 1 ) I q stf1 1 • • • q stf J J and k t n = o o t p e 1 +te1 1 • • • p e I +te I I q f 1 1 • • • q f J J ,
and co-prime with p 1 for all i, which is not the case since k and m are multiplicatively independent. We deduce by Theorem 5.20 that the set of directions of pre-expansivity of F k,k is not empty.

Let us interpret this result in a more geometrical way. Theorem 5.20 establishes that perturbations will diffuse (at least sparsely) inside a cone whose left slope is -log m (k) and right slope is 0 or -M where M = -min{ ei ei+e i : i ∈ {1, . . . , I}. Lemma 5.19 expresses moreover that perturbations are actually always present close to the left boundary of the cone (with a tolerance equal to the size of the initial perturbation). In the case q = 1, perturbations also accumulate on the right boundary of the cone since the CA is one-way.

In [START_REF] Blanchard | Dynamical properties of expansive one-sided cellular automata[END_REF], it was proved that F k,k is left-expansive if and only if q = 1, where left-expansive means {l d t (c)} t∈N not lower bounded for every d = c. The proof is performed through an argument using interesting results about the entropy of left-expansive CA. Let us stress that left-expansivity and directional preexpansivity are independent properties (none of them implies the other), and that any reversible CA has directions of left expansivity (any direction greater than the radius of the CA). Left expansivity asks for left-propagation of any perturbation, including perturbations over infinitely many cells. That is why Lemma 5.19 cannot be applied in this case, and in fact these perturbation may not propagate to the left when q = 1. The conflictive cases are those corresponding to configurations which are identical up to some cell at which one configuration has a n = 0 followed by 0s and the other has n -1 followed by m -1s. Until this boundary, both configurations will evolve in the same way, thus when q = 1, the cell where their differences start, which is equal to the right boundary of the first with respect to 0, will stop shifting to the left.

On the other hand, if k and k are multiplicatively dependent, there are natural numbers a, b such that F a k,k = σ b , that is, F k,k is a rational power of the shift (thus left-expansive), this means that all the perturbations propagate in a unique direction, in this case the direction is α = -b a , to the left. This direction is actually a direction of equicontinuity (see [START_REF] Sablik | Directional dynamics for cellular automata: A sensitivity to initial condition approach[END_REF]), a strong form of nonsensitivity and prevents such CA from having any direction of pre-expansivity (see Proposition 5.9).

As a final remark, let us recall that [START_REF] Kari | Universal pattern generation by cellular automata[END_REF] establishes that F 3,2 is a universal pattern generator: precisely, from every initial configuration c on Z Z 6 , and every finite pattern p there exists an iteration t such that p appear in F t 3,2 (c) at some position. The theorem is stated for k = 3 and k = 2 but the proof only uses that log k (k ) is irrational, which is exactly the condition for F k,k to admit pre-expansive directions.

6. Cellular automata over the free group Some of the properties proved in the last section come from the fact that the graph (Z, {(i, i + j) | j ∈ V }) can be always disconnected by extracting a finite part from Z. The graph of any free group where the edges are given by any finite neighborhood has this feature, and we would be able to extend some of the previous properties to the case of a cellular automaton over the free group. In particular, the pre-expansivity constant is strictly related with the neighborhood size, as in Z, and it does not depend on k for a k-expansive CA. We denote by F n the free group with n generators (F 1 is Z). Proposition 6.1. If F is a cellular automaton with a neighborhood V ⊆ B r (0) of radius r over the free group F n and it is k -expansive for all k ≤ k, then F is k-expansive with pre-expansivity constant equal to 2 -r .

Proof. The proof takes the ideas of Lemma 5.

c s (i) = c(i) if i ∈ R s d(i) otherwise
At the beginning, c s differs from d only on branch R s . We will see that this will be always the case. Let us suppose that, for some t ∈ N, F t (c s ) i = F t (c) i for all i ∈ R s and F t (c s ) j = F t (d) j , for all j ∈ R s . We remark that, we assumed that

if j ∈ B r (0), F t (c s ) j = F t (d) j = F t (c) j . Since F n is a tree and F is a CA of radius r, if i ∈ R s , B r (i) ⊂ R s ∪ B r (0), thus F t+1 (c s ) i = F t+1 (c) i . If j ∈ {0} s ∈S\{s} R s , B r (j) ⊂ s ∈S\{s} R s ∪ B r (0), then F t+1 (c s ) j = F t+1 (d) j .
We conclude that T r (c s ) = T r (c) = T r (d), for every s ∈ S. But we know, by hypothesis, that F is k -expansive, let us take its preexpansivity constant as = 2 -m . Let us consider now the configuration σ -ms (c s ), the shift of c s by ms ∈ F n . By construction, σ -ms (c s ) and σ -ms (d) are equal over B m (0). By the k -expansivity of F , there exists a time t and j ∈ B m (0) such that F t (σ -ms (c s )) j = F t (σ -ms (d)) j . But, as shown before, F t (c s ) and F t (d) differ only on branch R s . Therefore F t (σ -ms (c s )) and F t (σ -ms (d)) differ only on branch R ms which is disjoint from B m (0): this is a contradiction.

The last proposition shows that being k-expansive for every k ∈ N is enough to being pre-expansive, as in F 1 = Z. But not all the properties survive from F 1 to F n , when n > 1; k-expansivity is possible for infinitely many k's in F n even without pre-expansivity, as the next example shows. Example 6.2 (Λ n ). Let Q = {0, 1}, + be the addition modulo 2, and Λ n be the CA defined over Q Fn by

Λ n (c) i = c(i) + j∈S c(i + j).
In this CA, a spot will produce a wave of 1s advancing with velocity 1 over the boundary of a ball, as the next lemma establishes.

Lemma 6.3. If i, j ∈ F n are such that ||i|| = ||j||, then for every t ∈ N Λ t n (c 1 ) i = Λ t n (c 1 ) j , moreover Λ ||i|| n (c 1 ) i = 1.
Proof. We prove by induction on l that for every t ≤ l and every x, y ∈ B l (0), ||i|| = ||j|| ⇒ Λ t n (c 1 ) i = Λ t n (c 1 ) j and that Λ l n (c 1 ) i = 1 if ||i|| = l. For l = 0 is clear since in this case i = 0 = j and Λ 0 n (c 1 ) 0 = 1. Now let us suppose it true for some l, and let us prove it for l + 1.

Case 1, t ≤ l. By the induction hypothesis, we only need to verify the property for i, j ∈ B l+1 (0) -B l (0), but Λ t n (c 1 ) i = 0 = Λ t n (c 1 ) j because at time t ≤ l no perturbation at 0 has the time to arrive to these cells. Case 2, t = l +1. We first remark that any cell i in F n has exactly 2n-1 neighbors farther and exactly one neighbor closer than i to 0; we also remark that the local rule of Λ n is totalistic, only the quantity of neighbors at a given state counts. If i, j ∈ B l (0), all of their neighbors are in B l+1 (0), thus by Case 1, their state at time l depends only on their distance to 0, thus Λ l+1 n (c 1 ) i = Λ l+1 n (c 1 ) j . If i, j ∈ B l+1 (0) \ B l (0), then their neighbors outside B l (0) and themselves have all state 0 at time l; their unique neighbors in B l (0) have both state 1, by induction hypothesis. Thus, by the definition of Λ n , Λ l+1 n (c 1 ) i = Λ l+1 n (c 1 ) j = 1.

Proposition 6.4. Λ n is k-expansive for every k odd with pre-expansivity constant equal to 1, and it is not 2-expansive if n ≥ 2.

Proof. Let c = k 0. Let D = {i | c(i) = 0} and let D l = D ∩ (B l (0) \ B l-1 (0)).
It is clear that c = i∈D σ -i (c 1 ). Since |D| = k is odd, there exists some l such that |D l | is odd, let us take l as the smallest one. For every x, y ∈ D l , Now consider F of dimension d ≥ 2 linear over a p-group and some m ≥ 0. By Lemma 3.8, we know that the trace T m of a finite configuration of size n is determined by its prefix of size λ(n) where λ ∈ O(n). The number of such finite configurations grows like α n d for some α > 0 and the number of prefixes of T m of length λ(n) grows like β λ(n) for some β > 0 which depends only on m, G p and d. Since d ≥ 2 and λ is linear we deduce for n large enough that two finite configurations of size n have the same trace T m . Therefore T m is not pre-injective and by Proposition 4.4, F is not pre-expansive.

Note that this does not avoid a priori the existence of a linear CA which is k-expansive for any k ∈ N or for infinitely many k.

Simple Abelian CA

In general, in a CA with neighborhood V ⊂ G, we can remark that the influence of the cell 0 is restricted to the set generated by linear combinations of -V . More precisely, at time t, its influence is restricted to the following set:

-V t (0) = t i=1 v i | (∀i ∈ {1, .., t}) v i ∈ -V
A perturbation in a cell u ∈ G can produce a change in the state of cells in -V t (u) = u -V t (0) up to time t.

If G is commutative, for example G = Z n and V = {v 1 , .., v m }, this set can be computed as follows.

-V t (0) = ⊆ co(-tV )

Where tV = {tv | v ∈ V }, and co(•) stands for the convex hull (in R n ).

In the simpler case where G p = Z p , any linear CA F can be expressed as

F = z∈V a z σ z ,
where (a z ) z∈V is a sequence of elements of Z p . When p is prime, the Frobenius endomorphism gives strong self-similar properties to linear CAs, more precisely:

F p k = z∈V a z σ p k z .
More generally, consider any Abelian CA F with states G p such that p • g = 0 for all g ∈ G p and such that

F = z∈V h z • σ z ,
where h z are commuting automorphisms of G p . The Binomial formula and the fact that p divides all p k i for 0 < i < p k gives:

F p k = z∈V h p k z σ p k z .
Since the h z are automorphisms of G p there are infinitely many k such that h z = h p k z for all z ∈ V and therefore

F p k = z∈V h z σ p k z .
These particular cases suggest the following definition.

Definition 7.2. An Abelian CA F = z∈V h z • σ z is simple if it verifies

F M = z∈V h z σ M z (5)
for arbitrarily large M .

The next lemma establishes that the constant of k-expansivity in a simple Abelian CA on Z p depends only on the radius of the neighborhood. The radius of a neighborhood V is the smallest integer r such that V ⊆ B r (0). Lemma 7.3 (Amplification). Let F be a simple Abelian CA with neighborhood V ⊂ Z n of radius r. If there exists a configuration c = 0 such that T r (c) = 0, then for any m ≥ r there exists a configuration c = 0 such that T m (c ) = 0.

Proof. Let c be such that T r (c) = 0 and let M be such that m ≤ M -1. We define c by c M x = c x for every x ∈ Z n and 0 elsewhere.

From Equation 5, it is easy to see that F tM (c ) M x = F t (c) x , and 0 elsewhere. Therefore, for every t ∈ N and every v ∈ B r (0), F tM (c ) M v = 0. Now, between iterations tM and (t+1)M , we know, from the former remarks, that only cells in Ω =

x ∈Br(0) (M x -V M (0)) can have a state different from 0.

Since -V ⊆ B r (0), we have that -V M (0) ⊆ B rM (0), and the complement of Ω contains B M -1 (0), which is what we were looking for, in fact, The next corollary shows that in this case again the expansivity constant depends only on the neighborhood radius. Let us remark that here it is a little bit stronger than in the 1-dimensional case because it does not need k expansivity for every k ≤ k.

y ∈ Ω =   x ∈Br M x -V M (0)   ⇒ (∃x ∈ B r (0))(∃v ∈ -V M (0)) y = M x + v ⇒ ||y|| ≥ ||M x|| -||v|| ≥ M (r + 1) -M r = M ⇒ y ∈ B M -1 (0). -3 • 2 k -2 • 2 k -2 k 2 k 2 • 2 k 3 • 2 k -2 • 2 k-1 -2 k-1 2 k-1 2 • 2 k-1
Corollary 7.4. Let F be a linear CA in Z p . It holds:

• F is k-expansive, if and only if F is k-expansive with pre-expansivity constant 2 -r ;

• F is k-expansive for all k ∈ N if and only if F is pre-expansive.

With this lemma we can establish k-expansivity just by looking at T r . We will show a CA in that setting which is 1-expansive, 3-expansive and non 2expansive, and another which is non 1-expansive (and so non k-expansive for every k).

The rule ⊕ 2 with von Neumann neighborhood in Z 2

The rule that simply sums the state of its 5 neighbors in the von Neumann neighborhood: (0, 0), (0, 1), (1, 0), (0, -1), (-1, 0) is not 2-expansive. This can be seen through a simple picture: let us suppose that we start with the configuration c that has a '1' in cell (-2 k , 2 k-1 ) and in cell (2 k , 2 k-1 ). By symmetry, the vertical line {0} × Z will be always null. Thus, at iterations t2 k only cells at 2 k (Z \ {0}) × Z will be activated. Between iterations t2 k and (t + 1)2 k these cells cannot influence the ball B 2 k-1 -1 (0, 0) (see figure 5) and this ball will have a null trace: T 2 k-1 (c) = 0.

In order to establish the 3-expansivity of this CA, we will start by proving some lemmas that describe the form of the traces T 1 (σ z (c 1 )) of the evolution of and its four even neighbors cannot equal the odd neighbors of the first cell, and then the trace of radius 1 of the sum of the three cells cannot be null.

The rule ⊕ 2 with triangular neighborhood

The last rule is 1-and 3-expansive, now we present a linear rule which is even not 1-expansive. Thanks to Proposition 4.6, it implies in particular that is not k-expansive, for any k ∈ N. It correspond to addition modulo 2 as the last one but with a triangle shaped neighborhood: N = {(-1, 1), (1, 1), (0, 0), (0, -1)}. We only need to prove that it is not 1-expansive with expansivity constant equal to 2 -2 thanks to Corollary 7.4. Proposition 7.14. T 2 (σ (0,36) (c 1 )) is null.

Proof. We will prove, by induction, that T 2 (σ (0,36) (c 1 )) is null from 0 to 2 k . For k = 0 to 5 is clear since cell (0, 36) is too far to touch B 2 (0, 0). At iteration 2 k the only active cells are (-2 k , -2 k + 36), (2 k , -2 k + 36), (0, 2 k + 36) and (0, 36). The first three are too far to touch B 2 (0, 0) from iterations 2 k to 2 k+1 . By induction hypothesis (0, 36) does not attain B 2 (0, 0) in 2 k iterations, thus B 2 (0, 0) remains null until iteration 2 k+1 .

Open Problems

We showed in this paper that dynamics like pre-expansivity or k-expansivity can exist without necessarily implying positive expansivity. We also showed that some combinations of the space structure and the local rule structure forbid preexpansivity (Theorem 7.1). However, we left many open questions concerning pre-expansivity and k-expansivity:

• is there a pre-expansive cellular automata on Z d when d ≥ 2?

• is there a 2-expansive cellular automata on Z 2 ? on the free group? more generally what is the set of integers k such that a given group admits k-expansive cellular automata?

• a lot of results are known on traces of (positively) expansive cellular automata. What can we say for pre-expansive CA? for instance are they always transitive? what are their mixing properties?

• is the property of pre-expansivity decidable?

Acknowledgment

We would like to thank the anonymous referees who pointed out several technical errors and made valuable comments that certainly improved the present paper.

Definition 2 . 1 .

 21 defined by σ z (c)(x) = c(z +x) for every x ∈ G. The Cantor distance in Q G is defined for any two configurations c, d as follows. ∆(c, d) = 2 -min{||z||:c(z) =d(z)} if c = d 0 if c = d Two configurations c, d are asymptotic, denoted c ∞ = d, if they differ only in finitely many positions: {z ∈ G : c(z) = d(z)} is finite.

Lemma 3 . 8 .

 38 Let F be any d-dimensional Abelian CA having admitting multiscale additive identity. Let m > 0 and denote by T m the trace function associated to F and m. There exist a function λ : N → N with λ ∈ O(n) and such that for any n and for any pair of configurations c 1 , c 2 with:

Proof.

  First, by linearity of the trace functions T m , we have that T m (c) = T m (c ) if and only if T m c ⊕ (-c) = T m (0) where -c is the configuration such that c ⊕ (-c) = 0. Moreover we also have c = k c if and only if c ⊕ (-c) = k 0. Hence F is pre-expansive (resp. k-expansive) if and only if there is m such that no c = 0 with c ∞ = 0 (resp. c = k 0) can verify T m (c) = T m (0). From this we deduce the second item of the proposition. For the first item, consider k 1 and k 2 in I.

Lemma 5 . 4 .

 54 c) and r d t (c) are always finite integers. Given a CA F of neighborhood [-l, r] and k ∈ N, the next assertions hold.

  and we are done, so let us suppose that c [-m,m] = d [-m,m] . Let k and k be such that c r = k d, c l = k d and k + k = k.

Lemma 5 . 6 .

 56 F is pre-expansive if and only if for all c ∞ = d, (l d t (c)) t∈N is not lower bounded and (r d t (c)) t∈N is not upper bounded. Proof. (⇒) Let c = k d be two asymptotic configurations. Since F is pre-expansive, it is also k-expansive, thus by Lemma 5.4, (l d t (c)) t∈N is not lower bounded and (r d t (c)) t∈N is not upper bounded. (⇐) If for every k ∈ N and every pair c = k d we have that (l d t (c)) t∈N is not lower bounded and (r d t (c)) t∈N is not upper bounded, then by Lemma 5.4, F is k-expansive, and by Corollary 5.5, we conclude that F is pre-expansive.

Lemma 5 . 7 .

 57 F is positively expansive if and only if for any pair of different configurations

Figure 1 :

 1 Figure 1: Space-time diagram of Ψ starting from a configuration with a single non-zero cell.

Figure 2 :

 2 Figure 2: In the first row some space-time diagrams of Ψ are shown (state (0, 0) is represented by empty space). The third diagram shows the morphisms representing the dependence of Ψ t (c (a,b) ) i on (a, b), for each space-time coordinate (i, t): in particular, white means no dependence and red means bijective dependence.

Lemma 5 . 14 .

 514 Let us consider a configuration c = c (a,b) for some pair (a, b) ∈

Figure 3 :

 3 Figure 3: Some space-time diagrams of Υ (state (0, 0) is not represented). The right bottom figure represents the morphism transforming the state at the central cell into the state at each space-time coordinate.

Figure 4 :

 4 Figure 4: . (a) Space-time diagram of F 3,2 starting from a configuration with a finite number of non-zero cells (time goes from bottom to top, states are represented by tones of grey from white for 0 to black for 5). (b) Space-time diagrams of F 3,2 starting from two random asymptotic configurations (the coincident cells are colored with light grey tones, the effect of the perturbation is colored with dark grey tones)

Lemma 5 . 19 . 2 .

 5192 Given a sequence a ∞ = 0 in {-m + 1, . . . , 0, . . . , m -1} Z , we define the rational number:g(a) = i∈Z a i m -i , then, given two configurations c ∞ = d ∈ Z Z m with c = d,the next properties hold. 1. If '-' represents the substraction in Z, then |g(F k,k (c) -F k,k (d))| = k|g(c -d)|. If i = l d 0 (c), and j = r d 0 (c), then m -j ≤ |g(c -d)| < m -i+1 , moreover, -j is the biggest integer such that |g(c -d)|/m -j ∈ Z. 3.

2 . 1 1

 21 |g(c -d)| = | j n=i (c n -d n )m -n | from where the result is clear. 3. From item 1 and 2, we have that m-l d t (c)+1 > |g(F t (c)-F t (d))| = k t |g(cd)| ≥ k t m -r d 0 (c) , thus m -l d t (c)+1 > k t m -r d 0 (c) . 4. Analogously, we have that m -r d t (c) ≤ |g(F t (c) -F t (d))| = k t |g(c -d)| < k t m -l d 0 (c)+1 , thus m -r d t (c) < k t m -l d 0 (c)+1, from where we can conclude.Theorem 5.20. Suppose that p 1 , . . . , p I are distinct prime numbers and o and q are co-prime integers (possibly 1) which are also co-prime with p 1• • • p I . If k = op e1 1 • • • p e I I and k = p e • • • p e I

∞=

  d if and only if β in the given interval. The fact about l d t (c) can be obtained directly from Lemma 5.19: first l d t (c) -βt < r d 0 (c)+1-tlog m (k)-βt is not lower bounded when β > -log m (k). Conversely, if β ≤ -log m (k) then l d t (c) -βt is lower bounded when considering d = 0 and c the configuration with c 0 = 1 and c z = 0 for z = 0, because in this case g F t k,k (c) -F t k,k (d) = k t and tlog m (k) -1 ≤ -l d t (c) ≤ tlog m (k) + 1.

1 • 1 1

 11 f j fj -βt which is not upper bounded if and only if β < 0.It is said that two integers n and m are multiplicatively dependent if there are positive integers a and b such that n a = m b , and multiplicatively independent otherwise. Corollary 5.21. F k,k has directions of pre-expansivity if and only if k and k are multiplicatively independent. Proof. First, multiplicative independence of k and k is equivalent to multiplicative independence of k and m = kk . Let us first suppose there are positive integers a and b such that k a = m b . It is clear that a > b in this case. Then m b = o b p be1+be 1 • • p be I +be I I q b = o a p ae1 1 • • • p ae I I , and we deduce that q = o = 1 and b a = ei ei+e i = log m (k) for every i. Then from theorem 5.20 there is no α such that F k,k is α-expansive. Suppose now that k and k are multiplicatively independent and let p 1 , . . . , p I be the common primes in the decomposition of k and k so that we have k = op e1 1 • • • p e I I and k = p e • • • p e I

4 .

 4 Let c = k d be two configurations in F n . Let us call S the set of standard generators of F n , including their inverses (i. e. |S| = 2n), and for each s ∈ S, let us call R s the branch of F n that hangs from s; we mean the set of elements whose shortest description in terms of S starts with s. In this way F n = {0} ( s∈S R s ). Now let us define D = {i ∈ F n | c(i) = d(i)} and D s = D ∩ R s . We want to prove that T r (c) = T r (d) so let us suppose the opposite. This implies that D = s∈S D s , and we can consider k s = |D s | ≤ |D| = k. As in the case of Lemma 5.4, we define configurations c s which are equal to d everywhere except on branch s, as follows.

n

  k (-v k ) | m k=1 n k = t and for each k, n k ∈ N = m k=1 n k t (-tv k ) | m k=1 n k = t and for each k, n k ∈ N ⊆ m k=1 λ k (-tv k ) | m k=1 λ k = 1 and for each k, λ k ∈ [0, 1],

Figure 5 :

 5 Figure 5: Potentially active cells at iteration t2 k cannot influence B 2 k-1 -1 (0) before iteration (t + 1)2 k . Big dots represent the initially active cells.

Figure 7 :

 7 Figure7: Simulation of ⊕ 2 with a triangular neighborhood at iteration 25 starting from an initial configuration with a single 1 inside 0s: cells in state 1 are in red, cells that have been in state 1 between iteration 0 and 24 but not at 25 are in blue, and the others cells are not drawn.

  thus m st |k t n if and only if 1. o st |o o t 2. ∀i ∈ {1, . . . , I}, s t (e i + e i ) ≤ te i + e i 3. ∀j ∈ {1, . . . , J}, s t f j ≤ f jThe first condition is asymptotically true, because we know from Lemma 5.19(4) that s t < -l d 0 (c) + 1 + tlog m (k) which is smaller than t for bigger enough t. We distinguish two cases.(q = 1) In this case, condition 3 is empty, I ≥ 1, ands t =min te i + e i e i + e i : i ∈ {1, . . . , I} , for big enough t, thus r d t (c) -βt = -s t -βt is not upper bounded if and only if β <

	-min{ ei ei+e i	: i ∈ {1, . . . , I}}.

  • • • p I as in the hypothesis of Theorem 5.20. First, if q = 1 then Theorem 5.20 shows that F k,k has a non-empty set of directions of preexpansivity.

	Suppose now that q = 1, then it holds
	log(k) log(m)	=	log(o) + i e i log(p i ) log(o) + i (e i + e i ) log(p i )	≥	M log(o) + i M (e i + e i ) log(p i ) log(o) + i (e i + e i ) log(p i )	= M
	where M = min i equality holds only if o = 1 and M = ei ei because M ≤ 1 and for all i we have M ei+e i ei+e i	ei+e i ei	≤ 1. The

It can be checked that any direction greater than both the radius of the CA and its inverse is a direction of Z-expansivity, see[START_REF] Sablik | Directional dynamics for cellular automata: A sensitivity to initial condition approach[END_REF] Proposition 5.3] for more details.

0, 2 2, 0 0, 1 1, 0 0, 2 0, 2 2, 0 0, 2 2, 0 0, 2 2, 0 0, 2 2, 0 0, 2 time 0, 2 0, 2 2, 0 0, 2 2, 0 0, 1 0, 2 2, 0 0, 2 2, 0 0, 2 2, 0 0, 1 0, 2 2, 0 0, 1 1, 0 0, 2 2, 0 0, 2 2, 0 0, 2 2, 0 0, 2 2, 0 0, 1 1, 0 0, 2 2, 0 0, 2 2, 0 0, 2 2, 0 0, 1 0, 2 2, 0 0, 2 2, 0 0, 1 0, 2 2, 0 0, 2

This author acknowledges the support of CONICYT-FONDECYT#1140684 and EN-LACE project of Universidad de Concepción

2 This author acknowledges the support of CONICYT-Basal PFB03.

For the second item, first note that c t z = (0, 0) whenever z < -t or z > t because Ψ has radius 1. Consider any i with -3 k < i < 3 k . Applying Lemma 5.13 on Ψ 2•3 k +3 k i , we obtain:

Applying Lemma 5.13 to

we further get:

From what we said before and doing the arithmetics modulo 3 we deduce d k (i) = (0, 0) and the lemma follows. Now, proceeding by induction on M , suppose we have:

Writing (M + 1) • 3 k+1 = 2 • 3 k+1 + t with t = (M -1) • 3 k+1 and applying Lemma 5.13 to Ψ 2•3 k+1 +t z with z = (M + 1) • 3 k+1 -2 • 3 k we get:

Applying again Lemma 5.13 but with z = (M + 1)

By symmetry z → -z we obtain the corresponding equalities and we finally have:

which completes the induction step. The lemma follows.

The last lemma assures that finite configurations will always produce at least one non 0 cell at arbitrary large positions in the line.

By Lemma 6.3, this last term is equal to 1 which proves the k-expansivity when k is odd.

The second part of the proposition is almost direct from lemma 6.3. In fact, let m ∈ N be any natural number and let us take z = ms for some fixed generator s. Now let s be another generator, different from s and -s and define x = z +s and y = z -s . This imply that ||x|| = ||y|| = ||z|| + 1 = m + 1. Lemma 6.3 says that T 0 (σ x (c 1 )) = T 0 (σ y (c 1 )), but also that T m (σ x (c 1 )) = T m (σ y (c 1 )), because x and y are equidistant from z, as well as from all the other members of B m (0).

Cellular Automata on Z n , with n ≥ 2

Expansivity is not possible in dimension n ≥ 2 or more, due to combinatorial reasons: the number of possible n-dimensional patterns grows too quickly to be uniformly conveyed into a 1-dimensional array without loss (see [START_REF] Pivato | Positive expansiveness versus network dimension in symbolic dynamical systems[END_REF] for a general result of inexistence of expansive CA). This argument does not apply to pre-expansivity because only finite differences have to be propagated. Nevertheless, in Abelian CA the information propagates in a very regular way, and pre-expansivity is impossible as we will show. For Proof. First, if G is the Abelian group of the theorem it can be decomposed in a direct product G = G p × G where G p is a finite p-group for some prime p and G is a group whose order m is such that p doesn't divide m (structure theorem for finite Abelian groups, see [START_REF] Fuchs | Abelian groups, International series of monographs in pure and applied mathematics[END_REF]). Then F is isomorphic to F p × F according to Lemma 3.2, where F p is linear over G p . Moreover if F is pre-expansive, then F p must also be pre-expansive (by Proposition 4.4). It is therefore sufficient to show the Theorem for p-groups.

the configuration c 1 at the different points of Z 2 . In order to achieve this, we start by computing the partial traces

We first give a way for compute them, and afterwards we prove they are effectively the partial traces.

Definition 7.5. Given k ≥ 0 and z ∈ B 2 k -1 (0, 0), we recursively define u k (z) and v k (z) as follows. Let us define S k = {(0, 0), (0, 2 k ), (2 k , 0), (0, -2 k ), (-2 k , 0)}, the active cells of iteration 2 k .

Proof. When k = 0, B 0 (0, 0) = {(0, 0)}, and the trace of (0, 0) is constant and equal to 1.

Let us suppose the lemma true for k -1 ≥ 0. Let z ∈ B 2 k -1 (0, 0). Figure 6(a) depicts the first two cases in the definition of u k (z), the last one corresponds to cells in the diagonals segments, which remains null by symmetry .

• Case 1) z ∈ B 2 k-1 -1 (0, 0). In this case, the induction hypothesis says that the trace until 2 k -1 is given by u k-1 (z)v k-1 (z)

only the cells in S k-1 are in state 1, thus z is influenced by only one of the cells in S k-1 , say x, its trace from 2 k-1 to 2 k -1 is equal to the trace of the cell z -x from 0 to 2 k-1 -1, thus by induction again, it is equal to u k-1 (z -x).

• Case 3) If z belong to none of these balls, it belongs to one of the two diagonals lines that pass through (0, 0), and its trace is null. • Case 1) z ∈ B 2 k-1 1 (0, 0). At iteration 2 k , only the cells in S k are in state 1. Therefore, from 2 k to 2 k + 2 k-1 -1, z will be influenced only by the cell (0, 0), and its trace will be equal to u k-1 (z). At iteration 2 k + 2 k-1 , the active cells corresponds to red and brown cells in Figure 6(b), and again only cell (0, 0) reaches z, the process is repeated. • Case 2) z ∈ B 2 k -1 (0, 0) \ B 2 k-1 -1 (0, 0). At iteration 2 k , only the cells in S k are in state 1, thus, before iteration 2 k + 2 k-1 , z is touched only if it is at distance less than 2 k-1 from one of the cells in S k , say x, (orange zone in Figure 6(b)), then its trace is equal to u k-1 (z -x). At iteration 2 k + 2 k-1 , the active cells are far again, and z is influenced only by x again.

• Case 3) If z belong to none of these balls, its trace is null.

This lemma proves that the traces can be obtained through the substitution u → uv and v → uu. The basic u and v for a given cell z are obtained at iteration 2 k+1 if B 2 k -1 (0, 0) is the smallest ball containing z. From the next lemma we can conclude the 1-expansivity of this automaton with pre-expansivity constant equal to 2 -1 . Lemma 7.7. If i + j is odd and smaller than 2 k , then the trace of the cell z = (i, j), T 0 (σ z (c 1 )) is not null and its first non null index is odd and smaller than 2 k , in particular u k (i, j) is not null.

Proof. For k = 1, the trace of the odd cells inside B 1 (0, 0) from 0 to 1 is u = 01, the result holds. Let us assume the result true for k ≥ 1, and let z = (i, j) be an odd cell in B 2 k+1 -1 (0, 0) \ B 2 k -1 (0, 0). Since the cell is odd, it is not over the diagonals, and it belongs to the ball of radius 2 k of one of the four cells of S k \{(0, 0)}, say x. Then, by lemma 7.6, its trace from 2 k to 2 k+1 -1 is given by u k (z -x). Since the cells of S k are even, (z -x) is also odd, and the conclusion follows by induction. Now we will prove several properties that will be useful to prove 3-expansivity.

Proof. It is clear from Definition 7.5 and the fact that k > 0.

Lemma 7.9.

Proof. By induction on k. For k = 1, if z is inside the von Neumann neighborhood of (0, 0), thus u 1 (z) = 01 which is not a square. Let us suppose the assertion true for k -1 ≥ 1. Since k ≥ 1, from Definition 7.5, we recognize two cases for u k (z).

to be a square is to be equal to 0

. By the induction hypothesis u is either null or not a square. From Lemma 7.

Lemma 7.10. If |i| = |j| and (i, j) = 0, then the trace of the cell (i, j), T 0 (σ (i,j) (c 1 )) is equal to 0 ω .

Proof. Cells in the diagonals systematically falls in the boundaries of the zones given by the substitution, then their traces are systematically assigned equal to 0.

Lemma 7.11. If i+j is even, smaller than 2 k and the trace of the cell z = (i, j), T 0 (σ z (c 1 )) is not null, then the first non null index of the trace is even and it is smaller than 2 k .

Proof. For k = 0, the trace of the even cell inside B 0 (0, 0) from 0 to 0 is u = 1, the result holds. Let us assume the result true for k ≥ 0, and let z = (i, j) be an even cell in B 2 k+1 -1 (0, 0) \ B 2 k -1 (0, 0). Since the cell is attained, from Lemma 7.10, it is not over the diagonals, then it belongs to the ball of radius 2 k of one of the four cells in S k , say x. Then, its trace from 2 k to 2 k+1 -1 is given by u k (z -x). Since the cells in S k are even, z -x is also even, and the conclusion follows by induction. Now we are ready to prove that this automaton is 3-expansive.

Lemma 7.12. If z 1 , z 2 and z 3 are three different cells and T 0 (σ z1 (c 1 )) + T 0 (σ z2 (c 1 )) + T 0 (σ z3 (c 1 )) = 0 ω , then there exists z ∈ {z 1 , z 2 , z 3 } such that T 0 (σ z (c 1 )) = 0 ω .

Proof. We will prove a stronger assertion:

If z 1 , z 2 and z 3 are three different cells in B 2 k -1 (0, 0) and

It is stronger because from Lemmas 7.7 and 7.11, if z ∈ B 2 k -1 (0, 0) and u k (z) = 0 2 k , then T 0 (σ z (c 1 )) = 0 ω . By contradiction, let z 1 , z 2 and z 3 be three different cells in a ball

Let us choose these cells such that k is as small as possible.

Let be t z1 , t z2 and t z3 the indices where the respective traces equals 1 by the first time. It is clear that two of these numbers are equal and smaller than the third. Let us suppose that t z1 = t z2 < t z3 .

Case 1: z 1 , z 2 ∈ B 2 k-1 -1 (0, 0). In this case, from Lemma 7.6, the trace of z

is also a square, then it cannot be equal to u k-1 (z 3 -x) which is not a square thanks to Lemma 7.9.

Case 2: z 1 , z 2 , z 3 ∈ B 2 k-1 -1 (0, 0). In this case, from Lemma 7.6, for each i ∈ {1, 2, 3} there exists some x i ∈ S k-1 such that u k (z i ) = 0 2 k-1 u k-1 (z i -x i ).

Of course z i -x i ∈ B 2 k-1 -1 (0, 0) for each i ∈ {1, 2, 3} and u k-1 (z 1 -x 1 ) + u k-1 (z 2 -x 2 ) + u k-1 (z 3 -x 3 ) = 0 2 k-1 , which contradicts the minimality of k.

Theorem 7.13. The rule ⊕ 2 with von Neumann neighborhood in Z 2 is 1expansive, 3-expansive but not 2k-expansive for every k ∈ N.

Proof. We have stated that the rule is not 2-expansive, through a counter example, and this fact can be extended to every even number 2k, thanks to Proposition 4.6. Since B 1 (0, 0) always contains odd cells, from Lemma 7.7 we know that T 1 (σ z (c 1 ) is never null, which proves that the CA is 1-expansive. Finally, Lemma 7.12 shows that if three cells produce a null trace of radius 1, then one of them has a null trace of radius 0, this means that this cell is even, and its four neighbors are odd. When looking at the neighbors of these cells, their sum is also null, for each if its neighbors. Thus at least one cell must have even neighbors with a null trace, but in this case, two of these cells are odd,