Sebastian Donoso

Fabien Durand

Alejandro Maass

Samuel Petite

On automorphism groups of Toeplitz subshifts *

Keywords: Toeplitz subshifts, automorphism group, complexity function, coalescence

In this article we study automorphisms of Toeplitz subshifts. Such groups are abelian and any finitely generated torsion subgroup is finite and cyclic. When the complexity is non-superlinear, we prove that the automorphism group is, modulo a finite cyclic group, generated by a unique root of the shift. In the subquadratic complexity case, we show that the automorphism group modulo the torsion is generated by the roots of the shift map and that the result of the non-superlinear case is optimal. Namely, for any ε > 0 we construct examples of minimal Toeplitz subshifts with complexity bounded by Cn 1+ε whose automorphism groups are not finitely generated. Finally, we observe the coalescence and the automorphism group give no restriction on the complexity since we provide a family of coalescent Toeplitz subshifts with positive entropy such that their automorphism groups are arbitrary finitely generated infinite abelian groups with cyclic torsion subgroup (eventually restricted to powers of the shift).

Introduction

Given a finite set A, the full shift A Z is the set of all bi-infinite sequences (x i ) i∈Z with x i ∈ A for all i ∈ Z. This set can be thought of as all colorings of Z with colors in A. The finite set A is usually called the alphabet. A subshift is a subset of a fullshift A Z which is closed for the product topology and invariant under the shift map σ : A Z → A Z , (x i ) i∈Z → (x i+1 ) i∈Z . A word w is an element of ∪ n∈N A n . Its length |w| is the positive integer such that w ∈ A |w| . We say that a word w appears in a sequence x = (x i ) i∈Z ∈ X if there exists n ∈ Z such that w = x n • • • x n+|w|-1 . The complexity of a subshift X is the map p X (•) : N → N which for n ∈ N counts the number of words of length n appearing in sequences of X. An endomorphism is a continuous onto map φ : X → X such that φ • σ = σ • φ . It is called an automorphism whenever it is bijective. We remark that since X is compact, the inverse of an automorphism φ is also continuous and thus is an automorphism too. The group of all automorphisms is countable and denoted Aut(X, σ ).

The study of the group of automorphisms of low complexity subshifts has become very active in the last five years. In contrast with the positive entropy studies, where the automorphism group can be very large (see for instance [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF]), a lot of evidence suggests that low complexity systems ought to have a small automorphism group. In particular, studies [18] and [16] on classes of minimal substitutive subshifts showed that the automorphism groups are virtually Z. It turns out that this result holds for any minimal subshift with non-superlinear complexity (i.e., lim inf n→∞ p X (n)/n < ∞) [START_REF] Cyr | The automorphism group of a shift of linear growth[END_REF][START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF]. Also, for some special substitution subshifts with this complexity growth, the automorphism group is cyclic [7]. Higher order polynomial complexity growth was also considered by Cyr and Kra in [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF][START_REF] Cyr | The automorphism group of a minimal shift of stretched exponential growth[END_REF]. In [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF], the authors proved that for transitive subshifts, if lim inf n→∞ p X (n)/n 2 = 0 then the quotient Aut(X, σ )/ σ is a periodic group, where σ is the group spanned by the shift map. In [START_REF] Cyr | The automorphism group of a minimal shift of stretched exponential growth[END_REF], for a large class of minimal subshifts of subexponential complexity they also proved that the automorphism group is amenable. These results showed that the automorphism group seems to gain in constraints when the complexity goes down but this is not always true. Interestingly, in [19] the author provided a Toeplitz subshift with complexity p X (n) ≤ Cn 1.757 , whose automorphism group is not finitely generated.

Even though these results allow us to slowly understand the group of automorphisms of low complexity subshifts, the complete picture is still unclear, even for particular classes of subshifts. The purpose of this article is to use the class of Toeplitz subshifts and study their automorphism groups in order to understand some general questions relating complexity growth and the size of the automorphism group. We observe that since the automorphism group of a Toeplitz subshift is a subgroup of the associated odometer [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF], then it is a countable abelian group. This fact restricts our study to such class of groups.

We start by considering Toeplitz subshifts of subquadratic complexity. In this case, any endomorphism is bijective, so the coalescent property holds (see Section 3 for an expanded discussion). In Theorem 3.2 we show that the automorphism group is spanned by the roots of the shift map modulo the torsion subgroup. In fact, this result holds each time the quotient Aut(X, σ )/ σ is periodic and the subquadratic case is a consequence of [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF]. When this quotient is finite, in particular when the Toeplitz subshift has non-superlinear complexity [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF], we also prove in Theorem 3.2 that the automorphism group modulo a finite cyclic group is spanned by one root of the shift map, thus this quotient is a cyclic group. Both results open the door to applications to other Toeplitz subshifts with higher complexities. These results follow from the study of subgroups of odometers and allow us to recover Theorem 12 from [7], where the authors consider a family of Toeplitz subshifts generated by substitutions. The condition on Theorem 3.2 is true for many Toeplitz in the family called (p, q)-Toeplitz [5], including the example in [19]. Then, using this class of Toeplitz subshifts we extend the example given by Salo in [19], proving that the condition of non-superlinear complexity of [START_REF] Cyr | The automorphism group of a shift of linear growth[END_REF][START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF] cannot be relaxed. More precisely, in Theorem 4.1 we prove that for any ε > 0 there exists a Toeplitz subshift in the aforementioned family such that the complexity verifies p X (n) ≤ Cn 1+ε for all n ∈ N and whose automorphism group is not finitely generated. In fact, this construction allows us to produce Toeplitz subshifts with arbirarily big polynomial complexity whose automorphism group is not finitely generated. We left open the question whether we can get the same result with an even smaller complexity. For instance, p X (n)/n ≤ C log(n) for all n ∈ N.

In contrast with previous results, large complexity is not enough to have a large automorphism group. Here we prove that coalescence and the size of the automorphism group impose no restrictions to the complexity function. In Theorem 5.4 we provide a family of coalescent Toeplitz subshifts with positive entropy such that its automorphism group is an arbitrary infinite countable and finitely generated abelian group with cyclic torsion subgroup. For the group Z, this result resembles the main result in [START_REF] Bulatek | Strictly ergodic Toeplitz flows with positive entropies and trivial centralizers[END_REF] where the construction is not explicit. Also, in [START_REF] Downarowicz | A criterion for Toeplitz flows to be topologically isomorphic and applications[END_REF], an explicit example is given, with an arbitrary entropy but with a specific maximal equicontinuous factor. Our construction is explicit, self-contained and may be generalized to Z d -Toeplitz arrays or G-Toeplitz arrays for any countable amenable residually finite group G (see [START_REF] Cortez | G-odometers and their almost one-to-one extensions[END_REF]).

Finally, we remark that not every infinite countable abelian group can be the automorphism group of a Toeplitz subshift: it has to be a subgroup of an odometer [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF], hence residually finite. For instance, the rational numbers Q does not satisfy this property (see Section 2.3). But besides this restriction, we do not know if every infinitely generated countable abelian group (embedded in an odometer) can be realized as the automorphism group of a Toeplitz subshift.

Background

Topological dynamical systems

A topological dynamical system (or just a system) is a pair (X, T ) where X is a compact metric space and T : X → X is a homeomorphism. Let "dist" be a distance in X. The orbit of a point x ∈ X is given by Orb T (x) = {T n x; n ∈ Z}. A topological dynamical system is minimal if the orbit of every point is dense in X and is transitive if at least one orbit is dense in X. In a transitive system, points with dense orbits are called transitive points.

Let (X, T ) be a topological dynamical system. We say that x, y ∈ X are proximal if there exists a sequence (n i ) i∈N in Z such that lim i→∞ dist(T n i x, T n i y) = 0. A stronger condition than proximality is asymptoticity. Two points x, y ∈ X are asymptotic if lim n→∞ dist(T n x, T n y) = 0. Nontrivial asymptotic pairs may not exist in an arbitrary topological dynamical system but it is well known that a nonempty aperiodic subshift always admits at least one [2, Chapter 1].

A factor map between the topological dynamical systems (X, T ) and (Y, S) is a continuous onto map π : X → Y such that π • T = S • π. We say that (Y, S) is a factor of (X, T ) and that (X, T ) is an extension of (Y, S). We use the notation π : (X, T ) → (Y, S) to indicate the factor map. If in addition π is a bijective map we say that (X, T ) and (Y, S) are topologically conjugate.

The system (X, T ) is a proximal extension of (Y, S) via the factor map π : (X, T ) → (Y, S) (or the factor map itself is a proximal extension) if for every x, x ∈ X the condition π(x) = π(x ) implies that x, x are proximal. For minimal systems, (X, T ) is an almost one-to-one extension of (Y, S) via the factor map π : (X, T ) → (Y, S) (or the factor map itself is an almost one-to-one extension) if there exists y ∈ Y with a unique preimage for the map π. The relation between these two notions is given by the following folklore result. If the factor map π : (X, T ) → (Y, S) between minimal systems is an almost one-to-one extension then it is also a proximal extension (see [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF] for a proof).

A topological dynamical system (X, T ) is equicontinuous if for any ε > 0 there is δ > 0 such that if dist(x, y) ≤ δ then for any n ∈ Z one has dist(T n x, T n y) ≤ ε. It is well known that any topological system has a maximal equicontinuous factor, that is, a factor that is equicontinuous and that is an extension of any other equicontinuous factor of the system (see [2]).

An automorphism of the topological dynamical system (X, T ) is a homeomorphism φ of the space X to itself such that φ • T = T • φ . We denote by Aut(X, T ) the group of automorphisms of (X, T ). The subgroup of Aut(X, T ) generated by T is denoted by T . Analogously one defines an endomorphism of the topological dynamical system (X, T ) as a continuous and onto map φ : X → X such that φ • T = T • φ . The space of endomorphisms of (X, T ) is denoted End(X, T ). A system (X, T ) is coalescent if End(X, T )=Aut(X, T ). When (X, σ ) is a subshift, the Curtis-Hedlund-Lyndon theorem asserts that an endomorphism φ is defined by a local rule. That is, there exists r ∈ N (called a radius of φ ) and a block map φ : A 2r+1 → A such that φ (x) n = φ (x n-r . . . x n . . . x n+r ) for every n ∈ Z.

Odometers

Let (p n ) n≥1 be a sequence of natural numbers such that p n divides p n+1 for all n ≥ 1. Define the quotients associated to this sequence by q 1 = p 1 and q n+1 = p n+1 /p n for n ≥ 1. The odometer at scale (p n ) n≥1 is given by

Z (p n ) = {(x n ) n≥1 ∈ ∞ ∏ n=1 Z p n ; x n+1 = x n mod p n ∀n ≥ 1},
where Z p stands for Z/pZ, notation which is usually devoted to the ring of p-adic integers when p is prime. In this framework this ring is the one associated to the scale (p n ) n≥1 so will be denoted Z (p n ) .

The set Z (p n ) is an inverse limit lim ← Z p n of the canonical homomorphisms Z p n+1 → Z p n . Clearly Z (p n ) is an abelian group with the coordinatewise addition and when finite it is cyclic. The odometer Z (p n ) where p n = n! for all n ≥ 1 is called the universal odometer. We notice that the odometers Z (p n ) and Z (p in ) , where (i n ) n≥1 is strictly increasing, are isomorphic as groups. We denote by 0 and 1 the elements (0, 0, . . .) and (1, 1, . . .) in any odometer. The natural dynamics on an odometer Z (p n ) is given by the addition by 1. It is not difficult to see that it is a minimal equicontinuous topological dynamical system, that we also call odometer and denote by (Z (p n ) , +1). In particular, the subgroup 1 generated by 1 is dense in Z (p n ) . This subgroup is identified with the integers.

The following simple lemma is a slight generalization of the minimality of the odometer. The proof is given for completeness.

Lemma 2.1. Let Z (p n ) be an odometer and consider an integer m ∈ Z such that (m, p n ) = 1 for all n ≥ 1. Then, the dynamics defined by the addition by m1 in Z (p n ) is minimal.

Proof. Since the addition by 1 is minimal in Z (p n ) , it suffices to show that the orbit of 0 in Z p n by the addition by m contains 1 for all n ≥ 1. Since (m, p n ) = 1, there exist integers a, b such that am = bp n + 1. This ends the proof.

We will also need to understand when an odometer has torsion elements. For that we need some extra notation. For each prime number p, denote by v p (n) the p-adic valuation of the integer n, that is, v p (n) = max{k ≥ 0; p k divides n}. Given an odometer Z (p n ) , the sequence (v p (p n )) n≥1 is a nondecreasing sequence and we can define the multiplicity function, as proposed in [START_REF] Downarowicz | Survey of odometers and Toeplitz flows in Algebraic and topological dynamics[END_REF], by

v((p n )) = lim n→∞ v p (p n ); p prime .
For an abelian group G, let T (G) denote its torsion subgroup, that is, the subgroup generated by the torsion elements, i.e., elements of finite order. For an integer p, let T (G) p denote the set of elements in G of order a power of p.

Lemma 2.2. Let Z (p n ) be an odometer. Then its torsion subgroup is

T (Z (p n ) ) = p T (Z (p n ) ) p ,
where the sum is taken over all the prime numbers p such that lim n→∞ v p (p n ) is positive and finite. Moreover, each group T (Z (p n ) ) p is a finite cyclic group of order p lim n→∞ v p (p n ) . In particular, if lim n→∞ v p (p n ) ∈ {0, ∞} for all prime numbers, then Z (p n ) is torsion free.

It follows from the Chinese remainder theorem that the torsion subgroup of a finitely generated subgroup of an odometer is cyclic. Also, the group of p-adic integers Z (p n ) is torsion free. In contrast, the odometer Z (p n ) where p n is the product of the first n primes, i.e., lim n→∞ v p (p n ) = 1 for any prime number p, has a non-finitely generated torsion subgroup.

Proof. The Chinese remainder theorem implies that T (Z (p n ) ) = p T (Z (p n ) ) p , where the sum is taken over all the prime numbers. So it suffices to study each group T (Z (p n ) ) p .

Let p be a prime such that there exists (x n ) n≥1 ∈ T (Z (p n ) ) p different from 0, of order p k for some k ≥ 1, meaning p k x n = 0 mod p n for each n ≥ 1. Moreover there exists n such that for all large enough m ≥ n, p k is the order of x m in Z p m , and, thus p k divides p m . Thus, if T (Z (p n ) ) p is non trivial then lim n→∞ v p (p n ) is positive. Let us show it is finite. If it is not the case then there would be some m such that p m = p n pq for some integer q and we should have p k-1 x m = ap n q for some integer a. Consequently, p k-1 x n = 0 mod p n and thus x n = 0 mod p n . This would contradict the fact that p k is the order of x n .

Hence, lim n→∞ v p (p n ) = k p is finite and the order of (x n ) n≥1 is at most p k p . Since for each large enough n (so that v p (p n ) = k p ), the set of elements in Z p n of order p k for some 0 ≤ k ≤ k p , forms a cyclic group of cardinality p k p , the group T (Z (p n ) ) p is a cyclic group of cardinality p k p .

Toeplitz subshifts

We will use classical notions of symbolic dynamics (e.g. subshift, words, complexity,. . .) and we refer to Section 2.3 in [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF] for a presentation and the notation of these notions. We assume some familiarity of the reader with the notion of Toeplitz subshift so we review them succinctly. We refer to [START_REF] Downarowicz | Survey of odometers and Toeplitz flows in Algebraic and topological dynamics[END_REF] for a survey on this topic.

Let x = (x n ) n∈Z ∈ A Z , where A is a finite alphabet. For an integer p ≥ 1, we let Per p (x) = {n ∈ Z; x n = x n+kp for all k ∈ Z} be the set of indexes where x is p-periodic. The sequence x is said to be Toeplitz if there exists a sequence (p n ) n≥1 in N \ {0} such that Z = n≥1 Per p n (x). Equivalently, the sequence x is Toeplitz if all finite blocks in x appear periodically. We say that p n is an essential period if for any 1 ≤ p < p n the sets Per p (x) and Per p n (x) do not coincide. If the sequence (p n ) n≥1 is formed by essential periods and p n divides p n+1 , we call it a periodic structure of x. Clearly, if (p n ) n≥1 is a periodic structure, then (p i n ) n≥1 is also a periodic structure for any strictly increasing sequence of positive integers

(i n ) n≥1 .
A subshift (X, σ ) is a Toeplitz subshift if X is the orbit closure of a Toeplitz sequence x ∈ X. The subshift (X, σ ) is also referred as the subshift generated by x. Let ? be a symbol not in A. If (p n ) n≥1 is a periodic structure of x, then for every n ≥ 1 we can define the skeleton map at scale p n by S p n : X → (A ∪ ?) Z by putting (S p n (y)) m equal to y m if m ∈ Per p n (y) and to ? otherwise. Not all the points y ∈ X are Toeplitz sequences, but they all have the same skeleton structure (S p n (y)) n≥1 modulo a shift. More precisely, if (p n ) n≥1 is the periodic structure of the Toeplitz sequence x and y is any point in X, then for any n ≥ 1 there exists j n ∈ {0, . . . , p n -1} such that Per p n (y) = Per p n (x)j n and sequences x and y coincide on these coordinates, i.e., S p n (y) = σ j n S p n (x) (see [START_REF] Downarowicz | Survey of odometers and Toeplitz flows in Algebraic and topological dynamics[END_REF], Section 8).

It is well known that a minimal subshift (X, σ ) is a Toeplitz subshift if it is an almost one-to-one extension of an odometer. The odometer is given by Z (p n ) , where (p n ) n≥1 is a periodic structure of a Toeplitz point x generating X. The projection of a point y ∈ X into the odometer is given by the sequence ( j n ) n≥1 described above (see for instance [START_REF] Williams | Toeplitz minimal flows which are not uniquely ergodic[END_REF]). Hence, the projection of the Toeplitz sequence x is 0. Moreover, this odometer is the maximal equicontinuous factor of (X, σ ). A finite Toeplitz subshift is generated by a periodic Toeplitz sequence so it can be identified with its also finite associated odometer.

Since a Toeplitz subshift is an almost one-to-one extension of its maximal equicontinuous factor, to study its group of automorphisms, we will use the following result proved in [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF] (Lemma 2.1 and Lemma 2.4).

Lemma 2.3 ([13]

). Let (X, T ) be a minimal system and π : (X, T ) → (Y, S) be the projection of X onto its maximal equicontinuous factor. Then, we can define a map π : Aut(X, T ) → Aut(Y, S), φ → π(φ ), such that π(φ )(π(x)) = π(φ x) for every x ∈ X. If π is a proximal extension (in particular if π is an almost one-to-one extension) then π is injective.

It is worth mentioning that the same result holds for endomorphisms and that endomorphisms of an equicontinuous system are automatically automorphisms [START_REF] Auslander | Endomorphisms of minimal sets[END_REF]. It follows that the automorphism group of a Toeplitz subshift can be identified with a subgroup of the associated odometer. Indeed, it is well known that the group of automorphisms of an equicontinuous system is homeomorphic to the space itself (see [START_REF] Auslander | Endomorphisms of minimal sets[END_REF] or Lemma 5.9 in [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF] for a shorter proof). It follows that the automorphism group of a Toeplitz subshift is a countable abelian group.

Many other results described below will follow from the analysis of subgroups of odometers. As a first remark we have that if (X, σ ) is a Toeplitz subshift and Z (p n ) is its associated odometer, then any finitely generated subgroup G ≤ Aut(X, σ ) is isomorphic to Z d ⊕ H, where, by Lemma 2.2, H is a finite cyclic abelian group. If the odometer has no torsion, then the group H is trivial and thus G is isomorphic to Z d . This kind of properties restrict the groups that can be realized as the automorphism groups of Toeplitz subshifts. We already mentioned in the introduction that the group of rational numbers with the addition cannot be injected in any odometer Z (p n ) . Nevertheless, we will see in Section 5 that any finitely generated abelian group whose torsion subgroup is cyclic can be realized as the automorphism group of a Toeplitz subshift.

Automorphism group of disjoint Toeplitz subshifts

Two topological dynamical systems (X, T ) and (Y, S) are said to be disjoint if the product system (X ×Y, T × S) does not have any non-empty, closed and T × S invariant subsets projecting onto X and Y respectively, different from X ×Y .

In what follows we use the symbol ⊕ (instead of ×) whenever we want to stress that a product is in the group category. We start with a general lemma. Notice that the inclusion End(X, T ) ⊕ End(Y, S) ⊆ End(X ×Y, T × S) is always true.

Lemma 2.4. Let (X, T ) and (Y, S) be disjoint minimal systems. If φ ∈ End(X ×Y, T × S) (resp. Aut(X × Y, T ×S)) commutes with id×S and T ×id, then φ ∈ End(X, T )⊕End(Y, S) (resp. Aut(X, T )⊕Aut(Y, S)). In particular, the conclusion holds if End(X ×Y, T × S) is abelian.

Proof. Write the endomorphism φ (x, y) = (φ 1 (x, y), φ 2 (x, y)). If φ commutes with id × S and T × id, then we get that φ 1 (x, y) = φ 1 (x, S n y) and φ 2 (T n x, y) = φ 2 (x, y) for every n ∈ Z. By minimality of (X, T ) and (Y, S) we get that φ 1 only depends on x and φ 2 only depends on y, meaning that φ belongs to End(X, T ) ⊕ End(Y, S). The same is true for φ an automorphism.

Corollary 2.5. Let (X 1 , σ ) and (X 2 , σ ) be disjoint Toeplitz subshifts. Then, End(X 1 × X 2 , σ × σ ) = End(X 1 , σ ) ⊕ End(X 2 , σ ) and Aut(X 1 × X 2 , σ × σ ) = Aut(X 1 , σ ) ⊕ Aut(X 2 , σ ). In particular, if (X 1 , σ ) and (X 2 , σ ) are coalescent then (X 1 × X 2 , σ × σ ) is coalescent too. Proof. It suffices to notice that the system (X 1 × X 2 , σ × σ ) is a Toeplitz subshift itself. By Lemma 2.3, End(X 1 × X 2 , σ × σ
) is abelian and we can apply Lemma 2.4.

Automorphism group of Toeplitz subshifts with subquadratic complexity

In this section we study the automorphism groups of Toeplitz subshifts of subquadratic complexity. That is, the complexity function verifies lim inf n→∞ p X (n) n 2 = 0. In this case, a simple argument relying in Lemma 5 of [17] implies that these systems are coalescent. In fact, if (X, σ ) is a minimal subshift of subquadratic complexity (not necessarily Toeplitz), we can consider the spacetime tiling of an endomorphism φ , as done in [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF][START_REF] Cyr | The spacetime of a shift automorphism[END_REF]12], and obtain a periodicity condition on this tiling that is translated into φ n = σ m for some n ∈ N and m ∈ Z. From this we deduce that φ is injective and then is an automorphism.

Recall that for an abelian group G, T (G) is its torsion subgroup and that G/T (G) is a torsion free group. Most of the proofs rely on the following property of odometers. Lemma 3.1. If G is an abelian group and s ∈ G is an element of infinite order such that G/ s, T (G) is finite, then G/T (G) is a cyclic group isomorphic to s . In particular, the quotient (G/T (G)) / s is also a cyclic group.

Proof. Since G/ s, T (G) is finite, let g 1 , . . . , g m ∈ G be representatives for all of its cosets. For every i ∈ {1, . . . , m} there exists an integer i ∈ Z such that i g i ∈ s, T (G) . Let denote the smallest positive integer such that g ∈ s, T (G) for every g ∈ G. It is standard to check that divides lcm( 1 , . . . , m ). Now, for each i ∈ {1, . . . , m}, let k i be the integer such that g i ≡ k i s mod T (G). Since G/T (G) is torsion free, the minimality of gives that ( , k 1 , . . . , k m ) = 1. By Bezout's Theorem there exist integers a 0 , . . . , a m such that

a 0 + a 1 k 1 + • • • + a m k m = 1. Therefore, s = (a 0 +a 1 k 1 +• • •+a m k m )s ≡ (a 0 s+a 1 g 1 +• • •+a m g m ) mod T (G)
, and consequently there exists g ∈ G such that g ≡ s mod T (G). Since g i ≡ k i g mod T (G) for each i ∈ {1, . . . , m} and G/T (G) is torsion free, it follows g i ≡ k i g mod T (G). This together with g ≡ s mod T (G) shows that G/T (G) is generated by g, thus is cyclic. Clearly (G/T (G))/ s is also cyclic. Theorem 3.2. Let (X, σ ) be a Toeplitz subshift and let T = T (Aut(X, σ )) be the torsion subgroup of Aut(X, σ ).

1. If Aut(X, σ )/ T, σ is a periodic group, then any subgroup H of Aut(X, σ ) containing the shift is spanned by the roots of σ mod T (H) in H and T (H). In particular, a torsion free subgroup H containing σ is spanned by the roots of σ in H.

2. If Aut(X, σ )/ σ is finite, then Aut(X, σ ) is isomorphic to Z ⊕ T and T is either trivial or isomorphic to some Z N .

The statement (1) of this theorem applies for instance when (X, σ ) has subquadratic complexity, by the main result in [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF]. Statement (2) applies when (X, σ ) has non-superlinear complexity [START_REF] Donoso | On automorphism groups of low complexity subshifts[END_REF]. Moreover, since Aut(X, σ ) embeds into the odometer Z (p n ) associated to (X, σ ), Lemma 2.2 implies that any prime divisor p of N satisfies lim n→∞ v p (p n ) is positive and finite. In this situation, the odometers of the Toeplitz substitutions considered in [7] are groups of p-adic integers Z (p n ) , that have no torsion. So it follows that in this case Aut(X, σ ) is itself a cyclic group, which corresponds to Corollary 12 in [7].

Proof. Let Z (p n ) be the odometer associated to the Toeplitz subshift (X, σ ) and let H be a subgroup of Aut(X, σ ) containing σ . For φ ∈ H, consider the subgroup G of H spanned by φ and σ . By Lemma 2.3 we can see G as a subgroup of the odometer Z (p n ) and translate the hypothesis to the statement: G/ T (G), 1 is an abelian finitely generated periodic group. But this implies that G/ T (G), 1 is in fact finite. From Lemma 3.1, the group G/T (G) is cyclic. In particular, there exist ρ ∈ G and m 1 , m 2 ∈ Z such that φ ≡ ρ m 1 mod T (H) and σ = ρ m 2 mod T (H). This completes [START_REF] Auslander | Endomorphisms of minimal sets[END_REF].

If Aut(X, σ )/ σ is finite, then Aut(X, σ ) is finitely generated. So Lemma 2.2 implies that its torsion subgroup

T is cyclic. A direct consequence of Lemma 3.1 to Aut(X, σ ) is that Aut(X, σ )/T is cyclic. Since Aut(X, σ ) (Aut(X, σ )/T ) ⊕ T we have proved statement (2).
It is worth noting that if ϕ is a root of σ , then the integer such that ϕ = σ has to be prime with each p n appearing in the odometer Z (p n ) . This follows from the fact that the equality ϕ = σ (in Aut(X, σ )) is translated into z = 1 for z ∈ Z (p n ) , which is possible only if is prime with p n for all n ≥ 1. This observation allows us to produce examples of Toeplitz subshifts without roots, so where the automorphism group is trivial.

We illustrate Theorem 3.2 and previous comment in the next general construction. We concentrate on part (2). Examples for part (1) appear in the next section.

Consider a sequence (w n ) n≥1 on the finite alphabet A ∪ {?} such that for each n ≥ 1, |w n | = q n ≥ 3 and, for n ≥ 2, w n = u n ?v n , where u n and v n are non empty words on the alphabet A. Thus w n contains exactly one symbol ?. Now define the sequence (W n ) n≥1 by: W 1 = w ∞ 1 = . . . w 1 w 1 .w 1 w 1 . . ., where the central dot indicates the position to the left of the zero coordinate, and

W n+1 = F W n (w ∞ n+1 ) for every n ≥ 1. Here, F W n (w ∞ n+1
) is the sequence obtained from W n replacing consecutively all the symbols ? by the sequence w ∞ n+1 , where (w ∞ n+1 ) 0 is placed in the first ? to the right of coordinate 0. The map F will be studied in more details in next section.

Since symbol ? moves away from zero coordinate with n, then the sequence (W n ) n≥2 converges to a point x ∈ A Z . In addition, each coordinate of x is periodic with periods in the sequence (p n ) n≥1 , where p n = q 1 • • • q n . Hence x is a Toeplitz sequence. We let the reader check that one can choose the words u n 's and v n 's to construct a non periodic sequence x. Also, special choices of the u n 's and v n 's allow us to prove that (p n ) n≥1 is the sequence of essential periods of x (for example consider two different letters a, b ∈ A and take u n = a, v n = b q n -2 ). So, under this assumption we have that Z (p n ) is the odometer associated with X, the orbit closure of x by the shift map. Finally, remark that any word of length p n appearing in x can be constructed filling one symbol ? in W n , which is a periodic sequence of period p n . Then, the complexity of X verifies p X (p n ) ≤ |A| p n , and thus X has non-superlinear complexity.

Fixing the values of (q n ) n≥1 in such a way that p n = n! for all n ≥ 3 we get a Toeplitz subshift whose odometer is the universal one. In this case, by Lemma 2.2 we have that Aut(X, σ ) is torsion free and by Theorem 3.2 it is spanned by the roots of σ . But by the discussion after previous theorem the only possible root is the shift itself. Again, by Lemma 2.2, one can make other choices of the sequence (q n ) n≥1 in such a way that Aut(X, σ ) is torsion free and isomorphic to Z.

The same construction together with Corollary 2.5 allow us to get Toeplitz subshifts with nonsuperlinear complexity such that Aut(X, σ ) is isomorphic with Z ⊕ Z N for any N ∈ N. Indeed, in previous construction consider p a prime number not dividing N and set q n = p for any n ≥ 1. Then consider the cartesian product system (X × Z N , σ × +1), which, by the mentioned corollary, is a Toeplitz subshift with the desired automorphism group.

As consequence of the discussion of this section we can formulate the following dichotomy.

Corollary 3.3. Let (X, σ ) be a Toeplitz subshift such that Aut(X, σ )/ σ is a periodic group. If Aut(X, σ ) is torsion free, then either Aut(X, σ ) is cyclic or Aut(X, σ ) is not finitely generated.

Proof. The dichotomy follows from considering the cases whether Aut(X, σ ) is spanned by finitely or infinitely many roots of σ .

We can think of this result as a consequence of the algebraic structure of the automorphism group of a Toeplitz subshift, which for given automorphisms φ 1 and φ 2 allow us to take a "common divisor", i.e. an automorphism φ such φ 1 and φ 2 belong to φ (assuming that there is no torsion). This situation has to be contrasted with the case of a mixing shift of finite type, where the shift always admits only finitely many roots (see the discussion after Problem 3.5 in [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF]).

In the next section we exhibit some examples where the shift does have infinitely many roots. It remains open whether we can give a precise description of the roots of the shift map generating the automorphism groups in previous theorems.

As proved in Theorem 3.2, the quotient of the automorphism group by the torsion subgroup for a Toeplitz subshift of subquadratic complexity is generated by the roots of the shift map. In the particular case of non-superlinear complexity the automorphism group modulo its torsion subgroup is virtually Z and generated by a unique root. In this section we prove that the last result is in some sense optimal. That is, we can construct Toeplitz subshifts of subquadratic complexity such that the automorphism group is even not finitely generated. The same construction allows to get Toeplitz subshifts of arbitrary polynomial complexity whose automorphism groups are not finitely generated.

The main result of the section is the following, Theorem 4.1. For every ε > 0, there exists a Toeplitz subshift (X, σ ) such that the complexity verifies p X (n) n ≤ Cn ε for all n ≥ 1 and whose automorphism group is torsion free and not finitely generated.

To achieve this, we make use of the class of (p, q)-Toeplitz subshifts. In [5], Cassaigne and Karhumäki introduced this class and established the fundamental properties we discuss in the sequel. In this class one can get complexities that are arbitrarily close to non-superlinear (but always superlinear). This class was implicitly used by Salo [19] to give an example of a subshift of complexity p X (n) ≤ Cn 1.757 with a non-finitely generated automorphism group. We simplify and extend his result in the generality of Theorem 4.1. We start introducing the basic notions from [5], then we use freely their results. It is worth noting that in [5] the construction was carried out for one sided subshifts, but all can be extended without any problem to the two sided case.

(p, q)-Toeplitz subshifts

We refer to Section 2 in [5] for a detailed discussion on next properties and concepts.

Let A be a finite alphabet and ? a letter not in A (usually the symbol ? is referred as a "hole"). Let x ∈ (A ∪ {?}) Z . The sequence x represents a sequence over the alphabet A with holes. Given x, y ∈ (A ∪ {?}) Z , define F x (y) as the sequence obtained from x replacing consecutively all the ? by the symbols of y, where y 0 is placed in the first ? to the right of coordinate 0. In particular, if x has no holes, F x (y) = x for every y ∈ (A ∪ {?}) Z . In addition, observe that:

if z = F x (y) then F z = F x • F y . (1)
Now, consider a finite word w in A ∪ {?}. Let p be the length of w and q the number of its holes. Denote by w ∞ the sequence

• • • www.www • • • ∈ (A ∪ {?}) Z
, where the central dot indicates the position to the left of coordinate 0. We define the sequence (T n (w)) n≥1 by: T 1 (w) = w ∞ and T n+1 (w) = F w ∞ (T n (w)) for every n ≥ 1. It is not complicated to see that each T n (w) = u ∞ n for some word u n of length p n and u n has q n holes. We have that the limit x = lim n→∞ T n (w) is well defined as a sequence in (A ∪ {?}) Z . Moreover, if w does not start or finish with a hole, then the limit sequence belongs to A Z , i.e., x has no holes. The point x is called a (p, q)-Toeplitz sequence. Its orbit closure under the shift map X is called a (p, q)-Toeplitz subshift.

One of the main results in [5, Theorem 5] states that the complexity of a non periodic (p, q)-Toeplitz is Θ(n r ), where r = log(p/d)/ log(p/q) and d = (p, q). Now suppose that (p, q) = 1. Then, there exist positive constants C 1 and C 2 such that

C 1 n 1+ log q log p-log q ≤ p X (n) ≤ C 2 n 1+ log q log p-log q , ∀n ≥ 1. (2)
Moreover, the length of |u n | above is the smallest possible, (p n ) n≥1 is a periodic structure for x and the associated odometer is given by Z (p n ) which is torsion free by Lemma 2.2. Therefore, thanks to Lemma 2.3 we get the same conclusion for Aut(X, σ ).

If p is large enough compared with q, we have that | log q log p-log q | ≤ ε. Thus, (p, q)-Toeplitz subshifts is a natural class to study to prove Theorem 4.1.

Self reading properties of (p, q)-Toeplitz

Let w be a finite word in (A ∪ {?}) of length p and q holes with (p, q) = 1. Let x = lim n→∞ T n (w) be the (p, q)-Toeplitz sequence generated and X its orbit closure under the shift. The purpose of this section is to prove the main consequences of the so called "self-reading" property of x. First we summarize some basic results, some were already discussed in [5], others need to be proved. Proposition 4.2. We have, 1. For every n ≥ 1, the map F T n (w) :

(A ∪ {?}) Z → (A ∪ {?}) Z is continuous and F T n (w) (x) = x.
2. F T n (w) (σ q n y) = σ p n F T n (w) (y) for every y ∈ (A ∪ {?}) Z .

3. The skeleton structure of x is (T n (w)) n , i.e., S p n (x) = T n (w) for all n ≥ 1.

4. The transformation σ q n is minimal in X for every n ≥ 1.

F T n (w) leaves X invariant.

Proof. Continuity in statement ( 1) is direct from definition. Now, from [START_REF] Auslander | Endomorphisms of minimal sets[END_REF] we have that T n+1 (w) = F w ∞ (T n (w)), and thus

F T n+1 (w) = F w ∞ • F T n (w) , which implies F T n (w) = (F w ∞ ) n . From this equality we deduce F T n (w) (x) = lim m→∞ (F w ∞ ) n+m (w ∞ ) = x. This proves (1).
Statement (2) follows from the fact that each T n (w) is periodic of period p n and contains q n holes. Statement (3) is direct.

Let π denote the factor map from X to Z (p n ) . Since (p, q) = 1, statement (4) follows from the fact that translation by q n 1 acts minimally in the odometer Z (p n ) by Lemma 2.1, for every n ≥ 1. Indeed, if A ⊆ X is closed and invariant under σ q n , then π(A) is also closed (since X is compact) and invariant. By minimality we get that π(A) = π(X) = Z (p n ) . But π is almost one-to-one and thus A contains all points with one preimage (which is a G δ -set). Since A is closed we get A = X. This proves (4).

We finally notice that properties (1) and (2) imply that F T n (w) ((σ q n ) m x) ∈ X for all n ≥ 1 and m ∈ Z. The minimality of σ q n implies that F T n (w) leaves invariant X, proving (5).

Proof of Theorem 4.1

First, we choose a word w of length p and with q holes in A ∪ {?} such that the associated limit sequence x is non periodic and in A Z . It is enough to avoid the symbol ? in the first and last coordinates of w. Recall we are considering p and q to be relatively primes. Notice that, by (2), within the family of (p, q)-Toeplitz subshifts with p and q relatively primes we can get for any ε > 0 complexities such that for some constant C > 0, p X (n)/n ≤ Cn ε , for all n ≥ 1. It remains to prove that the automorphism group of the subshift X generated by x is not finitely generated.

Let n ≥ 1 and z ∈ X. As observed in Section 2.3, we can find a unique m = m(n, z) ∈ {0, . . . , p n -1} such that S p n (z) = σ m S p n (x) = σ m T n (w), where in the last equality we have used Proposition 4.2 (3). Recall that S p n (•) is the skeleton map at scale p n and m is nothing but the projection of z onto the factor Z p n .

Let z ∈ X → H n (z) be the map that associates the sequence in A Z of the consecutive symbols of z in the holes of S p n (z) from the coordinate -m(n, z). That is, the unique sequence satisfying

F S p n (x) (H n (z)) = σ -m(n,z) (z). (3)
We have that H n is a continuous function. Let k be an integer and r such that 0 ≤ r < p n and k +m = l p n +r for some l ∈ Z. It is straightforward to check that m(n, σ k (z)) = r. Then, using (3) and Proposition 4.2

(2), one gets

H n (σ k z) = σ lq n H n (z). (4)
We claim that H n (z) belongs to X. Since S p n (z) = σ m S p n (x), there is an integer sequence ( i ) i≥0 so that z can be written as z = lim i→∞ σ p n i +m (x). Using formula (4) we get,

H n (z) = H n (lim i→∞ σ p n i +m (x)) = lim i→∞ σ q n i H n (σ m (x)).
But, from (3), H n (σ m (x)) = H n (x) and by Proposition 4.2 (1)

H n (x) = x, then H n (z) = lim i→∞ σ q n i (x) ∈ X. The claim is proved. Define ϕ n (z) = σ m F S p n (x) (σ (H n (z))).
We have that this map ϕ n : X → X is well defined by the previous claim and Proposition 4.2 (5). This map leaves invariant each A-letter in the p n -skeleton of z and shift the symbols of z in the holes by one within the holes.

Using again formula (4) it is not difficult to check that ϕ n is an automorphism of (X, σ ). Moreover, we have that ϕ q n n = σ p n because there are q n holes in the first p n letters of S p n (x) = T n (w). On the other hand, q n is the minimum positive integer such that ϕ n ∈ σ . Indeed, if ϕ n = σ r for some integer r, then σ p n = ϕ q n n = σ rq n and by aperiodicity, p n = rq n . Since p and q are relatively prime, q n divides .

In particular, {ϕ n : n ∈ N}, σ / σ is an infinite periodic group and thus it is not finitely generated (finitely generated torsion abelian groups are finite). This implies that Aut(X, σ ) is not finitely generated.

We finish this section pointing out that if we choose p and q = p -2 for a large odd value of p, then the associated (p, q)-Toeplitz subshift has a polynomial complexity of degree log(p) log(p)-log(p-2) ≥ p-2 2 log(p). We conclude that, Corollary 4.3. There exist Toeplitz subshifts of arbitrarily large polynomial complexity with a not finitely generated automorphism group.

In the light of Corollary 3.3, we notice that we can easily exhibit infinitely many roots of the shift.

Corollary 4.4. Let (X, σ ) be a (p, q)-Toeplitz, with (p, q) = 1. Then for every n ≥ 1, σ admits a q n -root.

Proof. We have that for every n ≥ 1 there exists an automorphism ϕ n such that ϕ q n n = σ p n . Since (p, q) = 1 we can find a, b ∈ Z such that ap n = bq n + 1. Then ϕ aq n n = σ ap n = σ bq n σ and the automorphism ϕ a n σ -b is a q n -root of σ .

Realization of finitely generated abelian groups

In this section we show that within the class of Toeplitz subshifts we can realize any finitely generated abelian group with cyclic torsion subgroup as an automorphism group. Recall that the property of the torsion is necessary by Lemma 2.2. In the process, we show that large entropy does not suffice to have a large automorphism group, by constructing Toeplitz subshifts with arbitrarily large entropy and no automorphisms other than powers of the shift. This result is a consequence of the following theorem.

Theorem 5.1. For any infinite odometer there exists a uniquely ergodic Toeplitz subshift (X, σ ) with an arbitrarily large topological entropy whose associated odometer is equal to the given one and Aut(X, σ ) = End(X, σ ) = σ .

Proof. Fix an odometer Z (p n ) not isomorphic to a finite group. In this case we can consider (p n ) n≥1 strictly increasing. Below we construct a Toeplitz point x and its associated subshift X in an iterative process and prove all the desired properties. Without loss of generality we may assume that p 1 = 1. The Toeplitz subshift. Let D 0 > 1 and k 1 > 3 be constants that will be adjusted later. In the following, we will assume that k 1 is large enough so that 2 n-2 k 1 > (n + 1) 2 D 0 for all integer n ≥ 2. We consider an alphabet A with k 1 letters and let i 1 = 1.

Fix n ≥ 2 and suppose that at step (n-1) we have defined

k n-1 ≥ 2 n-2 k 1 words B 1,n-1 , . . . , B k n-1 ,n-1 of the same length p i n-1 on A. Pick a positive integer i n > i n-1 such that p i n > p i n-1 3k n-1 ((n 2 D 0 ) -1 -k -1 n-1 ) -1 (the definition of k 1 ensures that the term (n 2 D 0 ) -1 -k -1
n-1 is positive). Next, we build words of length p i n by concatenating the words B 1,n-1 , . . . , B k n-1 ,n-1 according to the following rules:

C1) The words B 1,n-1 . . . B k n-1 /2 ,n-1 and B k n-1 /2 +1,n-1 . . . B k n-1 ,n-1 respectively always appear as prefix and suffix of all words of step n. C2) After ensuring C1), we complete the remaining positions with p i n /p i n-1k n-1 words of length p i n-1 of the previous step. To do so, we consider all different concatenations of B 2,n-1 , . . . , B k n-1 ,n-1 (we exclude B 1,n-1 ) such that each B i,n-1 appears the same number of times d i,n-1 , for every i ≥ 2. More precisely, set

d n = d i,n-1 = (p i n /p i n-1 -k n-1 )/(k n-1 -1) for i ≥ 3 (so it is constant for such i) and dn = d 2,n-1 = p i n /p i n-1 -k n-1 -(k n-1 -2)d n .
Clearly, dn ≥ d n . For any such concatenation we obtain a word of step n of length p i n and we let k n denote the number of words of this length we get. We have the bound k n ≥ f (d n , k n-1 -1), where f (d, k) = (dk)! (d!) k denotes the number of partitions of a set of cardinality dk in k atoms such that each atom has d elements. Observe that f (d, k) ≥ k! and so k n ≥ 2k n-1 ≥ 2 n-1 k 1 for each n ≥ 2. We choose an order B 1,n , . . . , B k n ,n of them and continue with step n + 1. By construction, there exists a sequence x in A Z such that for every n ≥ 1 the word around coordinate 0 is equal to B k n ,n .B 1,n , where the dot indicates the position to the left of coordinate 0 in x. It is not difficult to see that for every n ≥ 1 the sequence x is a concatenation of words B •,n . Moreover, any finite word in x appears periodically with period p i n for some n ≥ 1. Indeed, by construction, any finite word in x is a subword of B k n ,n .B 1,n for some n ≥ 1, which by C1) is p i n+1 -periodic. This implies that x is a Toeplitz sequence. Call (X, σ ) the associated Toeplitz subshift.

We will need the following fundamental claim. We say a word u has a trivial overlapping with the word v whenever u appears in v only as a prefix or a suffix, meaning if v = pus for some words p, s then p or s has to be the empty word.

Claim 5.2. For every n ≥ 1, each word B i,n has a trivial overlapping with B j,n B k,n for any i, j, k ∈ {1, . . . , k n }.

Proof. We proceed by induction. The case n = 1 is true by construction. Now assume the result holds for n and by contradiction assume that B i,n+1 is a subword (different from a prefix or a suffix) of B j,n+1 B k,n+1 for some i, j, k ∈ {1, . . . , k n+1 }. We have that in the word B j,n+1 B k,n+1 , B 1,n only appears as prefix of B j,n+1 and prefix of B k,n+1 , otherwise B 1,n would be a subword of B j ,n B k ,n for some j , k ∈ {2, . . . , k n }, contradicting the induction hypothesis. But B i,n+1 also starts with B 1,n so the only possibility is B j,n+1 B k,n+1 = B i,n+1 B k,n+1 or B j,n+1 B k,n+1 = B j,n+1 B i,n+1 , which contradicts our assumption.

Before giving the rest of the proof, let us fix some notations. For a word y (eventually infinite), i < j ∈ Z, y| [i, j) denotes the word y i • • • y j-1 . We say that a word u occurs in y if there exists some i ∈ Z such that y| [i,i+|u|) = u, where |u| denotes the length of u and the index i is called an occurrence of u. Now we check that X is an almost one-to-one extension of the odometer Z (p in ) . For this, it is enough to verify that (p i n ) n≥1 is a periodic structure of x = (x n ) n , and for this it is only left to check that each p i n is an essential period of x. If not, there exists n ≥ 1 and 1 ≤ p < p i n such that Per p (x) = Per p in (x). By condition C1), {0, 1, . . . , p i n-1 -1} ⊆ Per p in (x), so p is an occurrence of x| [0,p i n-1 ) = B 1,n-1 in x. Since B 1,n is a concatenation of words B •,n-1 , Claim 5.2 and condition C2), both imply that B 1,n-1 has no occurrence, except 0, in B 1,n = x| [0,p in ) . This contradicts the fact that 1 ≤ p < p i n .

Lower bound for the topological entropy. We use the following lower bound of the topological entropy h(X, σ ) = lim for every d and k larger than some universal constant. Since we have

d n ≥ 3(((n + 1) 2 D 0 ) -1 - (2 n-2 k 1 ) -1 ) -1 -2 and k n ≥ 2 n-1 k 1 ,
in what follows we can assume that k 1 and D 0 are large enough so that d n and k n satisfy the previous estimates for all n ≥ 1. An iterated use of the previous inequality leads to:

log k n p i n ≥ log f (d n , k n-1 -1) p i n ≥ d n -1 p i n (k n-1 -2) log k n-1 = p i n-1 p i n (d n -1)(k n-1 -2) log k n-1 p i n-1 ≥ p i n-1 p i n (d n -1)(k n-1 -2) • • • p i 1 p i 2 (d 2 -1)(k 1 -2) log k 1 p i 1 .
Now, a standard computation gives that for all n ≥ 2

p i n-1 p i n (d n -1)(k n-1 -2) -1 ≤ 1 k n-1 -1 + p i n-1 p i n 3k n-1 ≤ 1 n 2 D 0 .
Let C > 0 and 0 < r < 1 be constants such that z + 1 ≥ exp(-C|z|) when |z| < r. Then, if D 0 is large enough, we can take z =

p i n-1 p in (d n -1)(k n-1 -2) -1 to get ∏ n≥2 p i n-1 p i n (d n -1)(k n-1 -2) ≥ exp(-C ∑ n≥2 1 n 2 D 0 ). It follows that h(X, σ ) ≥ exp(-C ∑ n≥2 1 n 2 D 0 ) log k 1 p i 1
. Hence, we can make the entropy arbitrarily large by moving k 1 .

Unique ergodicity. Condition C2) and Claim 5.2 both impose that for every n ≥ 1 and i ∈ {1, . . . , k n } the set of occurrences of the word B i,n in x has a specific frequency. More precisely, the word B i,n appears exactly a specific number of time in B j,n+1 for every j ∈ {1, . . . , k n+1 } (Namely one time if i = 1 and d i,n + 1 times otherwise). Since any x ∈ X is a concatenation of words B •,n+1 (Condition C2)), it follows that the average number of occurrences of B i,n , 1 N ∑ N-1 k=0 1 [B i,n ] 0 (σ k x) converges, as N goes to infinity, to

(1 + d i,n )/|B 1,n+1 | = (1 + d i,n
)/p i n+1 (with the convention d 1,n = 0). Hence for every ergodic measure µ we have that µ([B i,n ] 0 ) = (1 + d i,n )/p i n+1 by the Ergodic Theorem. Since the cylinders [B i,n ] 0 (and their images under the powers of the shift) generate the Borel σ -algebra, the associated subshift is uniquely ergodic.

Automorphism group. We now prove that (X, σ ) has no other endomorphisms than the powers of σ . Let φ ∈ End(X, σ ) and consider n ≥ 1 large enough such that p i n-1 is greater than the radius of a block map for φ .

By Claim 5.2 and condition C2), any occurrence i ∈ Z of B 1,n is an occurrence of some B j,n+1 in x. Since x is a concatenation of words B

•,n+1 , the index i -(k n -k n /2 )p i n -p i n-1 is an occurrence of the word B k n-1 ,n-1 B k n /2 +1,n . . . B k n ,n B 1,n B 2,n . . . B k n /2 ,n B 1,n-1 ,
meaning that the word B 1,n is always preceded in x by B k n-1 ,n-1 B k n /2 +1,n . . . B k n ,n and followed by the word B 2,n . . . B k n /2 ,n B 1,n-1 . This phenomenon is usually referred as B 1,n is an extensible word.

Therefore, there exists a word w of length k n p i n such that

{i ∈ Z; x| [i,i+p in ) = B 1,n } ⊆ {i ∈ Z; φ (x)| [i-(k n -k n /2 )p in ,i+ k n /2 p in ) = w}.
DISCRETE ANALYSIS, 2017 :11, 19pp.

By construction, the set in the left hand side of the equation is p i n+1 Z, so the word w occurs periodically with period p i n+1 in φ (x).

Recall that φ (x) is a concatenation of the words B i,n+1 of length p i n+1 and, in such decomposition, condition C2) ensures that each word B i,n+1 B j,n+1 , i, j ∈ {2, . . . , k n+1 } appears at least once. From the periodicity of occurrences of w there exists 0 ≤ p ≤ p i n+1 such that for every i, j ∈ {2, . . . , k n+1 },

B i,n+1 B j,n+1 | [p,p+k n p in ) = w.
(5)

The following claim shows that this p has to be close to p i n+1 , that is, w starts with a suffix of B i,n+1 and ends with a prefix of B j,n+1 .

Claim 5.3. Let p be an integer 0 ≤ p ≤ p i n+1 that satisfies (5). Then,

p + k n p i n -p i n+1 -k n /2 p i n -1 ≤ p i n-1 ( k n-1 /2 + 1).
Proof. Assume the inequality is false. This implies that the word w = B i,n+1 B j,n+1 | [p,p+k n p in ) has a suffix (or a prefix) with a factor B •,n-1 of B i,n+1 (or of B j,n+1 ) different from the ordered part given by condition C1). Since condition C2) ensures that we can find any word B ,n-1 , ≥ 2, at any position in

p i n Z ∩ {p i n k n /2 , . . . , p i n+1 -(k n -k n /2 )p i n } outside the ordered parts given by condition C1), there exist indices i , j ∈ {2, . . . , k n+1 } such that B i ,n+1 B j ,n+1 | [p,p+k n p in ) = w, leading to a contradiction Call the word B i,n+1 B j,n+1 | [p+(k n -k n /2 )p in -1,p+(k n -k n /2 +1)p in )
the middle word of w. For any occurrence of B 1,n in x, the unique extension property implies that also is an occurrence of the middle word of w in φ (x). Thus, by Claim (5.3), is at distance at most p i n-1 ( k n-1 /2 + 1) from an occurrence of B 1,n in φ (x). Finally, we get k ∈ Z with |k| ≤ p i n-1 ( k n-1 /2 + 1) such that both x and σ k φ (x) starts with B 1,n . Considering σ k φ instead of φ , we can assume that x and φ (x) start with the word B 1,n , where φ admits a block map φ of radius smaller than p i n-1 + p i n-1 ( k n-1 /2 + 1) ≤ p i n .

By the extensible property of B 1,n we get that φ ([B 1,n ] 0 ) ⊆ [B 1,n ] 0 , where [B 1,n ] 0 is the cylinder set starting with word B 1,n at zero coordinate. Using that B 1,n only appears as a prefix of the words B j,n+1 for all j ∈ {1 . . . , k n+1 }, we get that φ (x) has to start with some word B j,n+1 . Since the radius of φ is lower than p i n , the same argument as before shows that there exists another k ∈ Z with |k| ≤ p i n ( k n /2 + 1) < p i n+1 such that both x and σ k φ (x) starts with B 1,n+1 . But since φ (x) starts with some B j,n+1 we have that if j = 1 then k ≥ p i n+1 . So we get that j = 1 and k = 0. Inductively we conclude that x and φ (x) start with the word B 1,n for every n ≥ 1. Hence, x and φ (x) are right asymptotic. Since any word of x has a positive occurrence in x, the block map φ codes the identity map, so φ = Id. We conclude that End(X, σ ) = Aut(X, σ ) = σ , finishing the proof.

In the previous proof we can relax condition C2) by considering all the concatenations of words B i,n-1 , i ∈ {2, . . . , k n-1 }, without imposing restrictions on their number of occurrences, leading to the construction of a coalescent Toeplitz subshift with entropy arbitrarily high but not necessarily uniquely ergodic.

The fact that we can choose first an infinite odometer and then find a Toeplitz almost one-to-one extension of it with arbitrarily high entropy allow us to deduce the following.

Theorem 5.4. Any infinite finitely generated abelian group with cyclic torsion subgroup can be realized as the automorphism group of a coalescent Toeplitz subshift with arbitrarily large or zero entropy.

Proof. Let G be a finitely generated abelian group with cyclic torsion subgroup. By the fundamental theorem of finitely generated abelian groups, we may identify G with Z d ⊕ Z a , where d ≥ 1 and a = a s 1 1 • • • a s with different prime numbers a i for i ∈ {1, . . . , } and ≥ 1. Consider d different primes r 1 , . . . , r d , where each r j is also chosen to be different from the a i 's for i ∈ {1, . . . , }. Let us consider for each j ∈ {1, . . . , d} a Toeplitz subshift (X j , σ ) such that End(X j , σ ) = Aut(X j , σ ) = σ , so is isomorphic to Z, and whose associated odometer is Z (r n j ) , i.e., where the scale is given by (r n j ) n≥1 . Examples of such subshifts are provided by Theorem 5.1, in the positive entropy case and by the examples illustrating Theorem 3.2 (2) in the zero entropy case.

Consider the product space X = X 1 × • • • × X d × Z a with the action σ : X → X given by the shift on each X j for j ∈ {1, . . . , d} and by the addition by one on the finite system Z a (recall that in the case a Toeplitz is finite we identify it with the associated odometer). The fact that all the involved odometers (finite and infinite) have different primes in their bases implies that the system (X, σ ) is a minimal system (we refer to Section 12 in [START_REF] Downarowicz | Survey of odometers and Toeplitz flows in Algebraic and topological dynamics[END_REF] for a deeper discussion on disjointness properties of Toeplitz subshifts). Moreover, (X, σ ) is also a Toeplitz subshift: the k-th coordinate of x = (x 1 , . . . , x d , m) ∈ X is periodic of period the product of the periods of the k-th coordinates of x 1 , . . . , x d , m. By Corollary 2.4 we get that (X, σ ) is coalescent and its automorphism group is abelian and equal to Aut(X 1 , σ ) ⊕ • • • ⊕ Aut(X d , σ ) ⊕ Aut(Z a , +1), which is nothing but Z d ⊕ Z a , and thus is isomorphic to G.

Finally remark that any finite cyclic group can be realized as the automorphism group of a periodic Toeplitz subshift. So to summarize, any finitely generated abelian group with cyclic torsion subgroup can be realized as the automorphism group of a Toeplitz subshift.

We finish this section with some open questions: Given a countable subgroup of an odometer Z (p n ) , can we find a Toeplitz subshift whose automorphism group realizes this group? In particular, does there exist a Toeplitz subshift whose automorphism group contains an infinite countable direct sum of Z?

  n→∞ log p X (n)/n ≥ lim sup n→∞ log k n p i n . A standard computation using the Stirling formula gives that log f (d, k) ≥ (d -1)(k -1) log(k + 1)

DISCRETE ANALYSIS, 2017:11, 19pp.

* This research was supported through the cooperation project MathAmSud DCS 38889 TM. † Partially supported by ERC grant 306494 and CMM-Basal grant PFB-03. ‡ Supported by CMM-Basal grant PFB-03. c 2017 Sebastián Donoso, Fabien Durand, Alejandro Maass, and Samuel Petite c b Licensed under a Creative Commons

AUTHORS


Fabien Durand
email: fabien.durand@u-picardie.fr

Julien Leroy
email: j.leroy@ulg.ac.be

The Constant of Recognizability is Computable for Primitive Morphisms

Mossé proved that primitive morphisms are recognizable. In this paper we give a computable upper bound for the constant of recognizability of such a morphism. This bound can be expressed using only the cardinality of the alphabet and the length of the longest image of a letter under the morphism.

Introduction

Infinite words, i.e., infinite sequences of symbols from a finite set, usually called the alphabet, form a classical object of study. They have an important power of representation: they provide a natural way to code elements of an infinite set using finitely many symbols, e.g., the coding of an orbit in a discrete dynamical system or the characteristic sequence of a set of integers. A rich family of infinite words, with a simple algorithmic description, consists of the words obtained by iterating a morphism σ : A * → A * [START_REF] Choffrut | Combinatorics of words[END_REF], where A * is the free monoid generated by the finite alphabet A.

If σ is prolongable on some letter a ∈ A, that is, if σ(a) = au for some non-empty word u and lim n→+∞ |σ n (a)| = +∞, then σ n (a) converges to an infinite word x = σ ω (a) ∈ A N that is a fixed point of σ. Two-sided fixed points are similarly defined as infinite words of the form σ ω (a • b) ∈ A Z , where σ(a) = ua and σ(b) = bv with u, v ∈ A + and lim n→+∞ |σ n (a)| = lim n→+∞ |σ n (b)| = +∞. Such a fixed point is said to be admissible if ab occurs in σ n (c) for some n ∈ N and some c ∈ A. When the morphism is primitive, i.e., there exists k ∈ N such that b occurs in σ k (c) for all b, c ∈ A, then x is uniformly recurrent: each finite word u that occurs in x occurs infinitely many times in x and the gaps between two consecutive occurrences of u in x are bounded [START_REF] Queffélec | Substitution Dynamical Systems-Spectral Analysis[END_REF]. The converse almost holds: if x = σ ω (a) is uniformly recurrent, then there exist a primitive morphism ϕ : B * → B * , a letter b ∈ B and a morphism ψ : B * → A * such that x = ψ(ϕ ω (b)) [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]. We let L(x) denote the set of factors of x, i.e., L(x) = {u ∈ A * | ∃p ∈ A * , w ∈ A N : x = puw} (with an analogous definition for twosided fixed points). We also let p x : N → N denote the complexity function of x defined by p x (n) = Card L n (x) where L n (x) = L(x) ∩ A n . A primitive morphism σ is aperiodic if its fixed points are not periodic, i.e., are not of the form u ω = uuu • • • .

Recognizability is a central notion when dealing with fixed points of morphisms. It roughly means that any sufficiently long finite word that occurs in σ ω (a) has a unique pre-image under σ, except for a prefix and a suffix of bounded length. Recognizability of a morphism is linked to the existence of long powers u k in L(x) [START_REF] Mignosi | If a D0L language is k-power free then it is circular[END_REF]. An infinite word x ∈ A Z is said to be k-power-free if there is no non-empty word u such that u k belongs to L(x). We refer, for example, to [START_REF] Canterini | Geometric representation of substitutions of Pisot type[END_REF][START_REF] Durand | Substitutional dynamical systems, Bratteli diagrams and dimension groups[END_REF][START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF][START_REF] Holton | Descendants of primitive substitutions[END_REF]. A fundamental result concerning recognizability is due to Mossé, who proved that aperiodic primitive morphisms are recognizable [START_REF] Mossé | Puissances de mots et reconnaissabilité des points fixes d'une substitution[END_REF][START_REF] Mossé | Reconnaissabilité des substitutions et complexité des suites automatiques[END_REF]. In this paper, we present a detailed proof of this result. This allows us to give a bound on the constant of recognizability.

Recognizability

Recognizability of a morphism deals with uniqueness of pre-images of words. More precisely, given a morphism σ, an admissible fixed point x of σ and a sufficiently long word w ∈ L(x), we would like to find some word u ∈ L(x) such that w appears in σ(u) and such that any other word u ∈ L(x) satisfying the same property has a large part in common with u. This large common part is the pre-image that the notion of recognizability is concerned with.

To find such a pre-image, it suffices to consider the pre-images of the letters. As a letter a can appear in several images σ(b) and at different positions in σ(b), we need to consider it in some context of length , i.e., to consider a word uav ∈ L(x) with |u| = |v| = . We would like that the length of the context ensures the uniqueness of b and of the position i ∈ {0, 1, . . . , |σ(b)| -1} such that (σ(b)) i = a. This length will be defined as the constant of recognizability in Definition 1.

Let us consider an example with the morphism τ defined by τ (0) = τ (1) = 021 and τ (2) = 0. The letter 0 appears at the first position in the image of 0, 1 and 2. The contexts of length 4 of 0 are the words of length 9 that occur in x = τ ω (1 • 0) and that have 0 for central letter, i.e., c 1 = 0021 0 2100; c 2 = 0021 0 2102; c 3 = 0210 0 2102; c 4 = 1021 0 0210; c 5 = 1021 0 2100.

In the contexts c 1 , c 2 and c 5 , the central occurrence of 0 is the first letter in the image τ (0). Indeed, the first occurrence of 0 in the word 00 can only be the image of 2 and the words 12, 22 and 20 do not occur in x. Therefore we necessarily have the following factorization for c 1 :

c 1 = 0 τ (2) 021 τ (1)
021

τ (0) 0 τ (2) 0.
Similar arguments show that in c 3 (resp., in c 4 ) the central occurrence of 0 is the first letter in the image τ (1) (resp., τ (2)). We have Let us now formalize the precise definition of recognizability. Let x = (x n ) n∈Z ∈ A Z be an infinite word. Given two integers i, j with i ≤ j, we let x [i,j] (resp., x [i,j) ) denote the factor

c 3 = 021 τ (0) 0 τ (2
x i x i+1 • • • x j (resp., x i x i+1 • • • x j-1 ) x [i,i) = ε,
where ε is the empty word, i.e., the identity element of A * .

Assume that the morphism σ : A * → A * is non-erasing and has an admissible fixed point

x = (x n ) n∈Z ∈ A Z . For all p ∈ N, we let f (p)
x denote the function

f (p) x : Z → Z, i → f (p) x (i) =      |σ p (x [0,i) )|, if i > 0; 0, if i = 0; -|σ p (x [i,0) )|, if i < 0. We set E(x, σ p ) = f (p)
x (Z). When it is clear from the context, we write f (p) instead of f (p)

x . Observe that σ being non-erasing, all functions f (p)

x are increasing. Definition 1. We say that σ is recognizable on x if there exists some constant L > 0 such that for all i, m ∈ Z,

(x [m-L,m+L] = x [f (1) (i)-L,f (1) (i)+L] ) ⇒ (∃j ∈ Z)((m = f (1) (j)) ∧ (x i = x j )).
(1)

We say that the factor x [f (1) (i)-L,f (1) (i)+L] uniquely determines the letter x i . By extension, we say that the factor x [f (1) (i)-L,f (1) (j)+L] uniquely determines the factor x [i,j] . The smallest L satisfying Equation ( 1) is called the constant of recognizability of σ for x. When σ is recognizable on all its admissible fixed points, we say that it is recognizable and its constant of recognizability is the greatest one.

In the example above, the arguments given for the contexts of the letter 0 can be similarly applied for the contexts of length 4 of the letters 1 and 2. Thus those contexts also have unique factorizations as images of τ . Therefore the constant of recognizability of τ on the admissible fixed point τ ω (1 • 0) is at most 4. A careful inspection of the contexts of length 4 actually shows that the constant is at most 3 (no context of length 3 appears as a subword of two contexts of length 4 having different factorization). We can finally show that it cannot be equal to 2. Indeed, the word 21 0 21 is a context of length 2 of 0 but appears as a subword of c 1 and c 3 that have different decompositions as images of τ . The constant of recognizability of τ is thus equal to 3.

The following result shows that any primitive aperiodic morphism is recognizable.

Theorem 2. Let σ : A * → A * be an aperiodic primitive morphism and let x ∈ A Z be an admissible fixed point of σ.

[14]

There exists M > 0 such that, for all i, m ∈ Z,

x [f (1) (i)-M,f (1) (i)+M ] = x [m-M,m+M ] ⇒ m ∈ E(x, σ).

[15]

There exists L > 0 such that, for all i, j ∈ Z,

x [f (1) (i)-L,f (1) (i)+L] = x [f (1) (j)-L,f (1) (j)+L] ⇒ x i = x j .
By a careful reading of the proofs of Mossé's results, we can improve the statements as follows. The proof of Theorem 3 is given in Section 3. Given a morphism σ : Theorem 3. Let σ : A * → A * be a morphism with an admissible fixed point x ∈ A Z . If x is k-power-free and if there is some constant N such that for all n ∈ N, |σ n | ≤ N σ n , then σ is recognizable on x and its constant of recognizability for x is at most

A * → A * ,
R|σ dQ | + |σ d |, where • R = N 2 (k + 1) + 2N ; • Q = 1 + p x (R) R N ≤i≤RN +2 p x (i) ; • d ∈ {1, 2, . . . , Card A} is such that for all words u, v ∈ L(x), we have σ d-1 (u) = σ d-1 (v) ⇒ ∀n, σ n (u) = σ n (v).
Then, we give some computable bounds for N , R, k, Q and d in the case of primitive morphisms. These bounds are not sharp but can be expressed using only the cardinality of the alphabet and the maximal length |σ|. The proof is given in Section 4.

Theorem 4. Each aperiodic primitive morphism σ : A * → A * that has an admissible fixed point x ∈ A Z is recognizable on x and the constant of recognizability for x is at most

2|σ| 6(Card A) 2 +6(Card A)|σ| 28(Card A) 2 + |σ| Card A .
The bound given in the previous theorem is far from being sharp. When the morphism σ is injective on A, we can take d = 1 in Theorem 3 and the computation in the proof of Theorem 4 gives the bound

2|σ| 6(Card A) 2 +6|σ| 28(Card A) 2 + |σ|.
The notion of recognizability is also known as circularity in the terminology of D0Lsystems [START_REF] Kari | L systems[END_REF]. Assume that σ : A * → A * is non-erasing (i.e., σ(a) = ε for all a ∈ A) and that a ∈ A is a letter such that the language Fac(σ, a) defined as the set of factors occurring in σ n (a) for some n is infinite. Given a word u = u 1 • • • u |u| ∈ Fac(σ, a), we say that a triple (p, v, q) is an interpretation of u if v ∈ Fac(σ, a) and σ(v) = puq. Two interpretations (p, v, q), (p , v , q ) are said to be synchronized at position k if there exist i, j such that 1

≤ i ≤ |v|, 1 ≤ j ≤ |v | and σ(v 1 • • • v i ) = pu 1 • • • u k and σ(v 1 • • • v j ) = p u 1 • • • u k .
The word u has a synchronizing point (at position k) if all its interpretations are synchronized (at position k). The pair (σ, a) is said to be circular if σ is injective on Fac(σ, a) and if there is a constant C such that all words of length at least C have a synchronizing point. The smallest such C is called the synchronizing delay of σ. Thus, despite some considerations about whether we deal with fixed points or languages, recognizability and circularity are roughly the same notion and the synchronizing delay C is associated with the constant of recognizability L through L ≤ C ≤ 2L + |σ| + 1. Using the terminology of D0L-systems, Klouda and Medková obtained the following result which greatly improves our bounds, but for restricted cases.

Theorem 5 ([11]). If Card A = 2 and if (σ, a) is circular with σ : A * → A * a k-uniform morphism for some k ≥ 2, then the synchronizing delay C of (σ, a) is bounded as follows, where d is the least divisor of k greater than 1:

1. C ≤ 8, if k = 2; 2. C ≤ k 2 + 3k -4, if k is an odd prime number; 3. C ≤ k 2 k d -1 + 5k -4, otherwise.
3 Proof of Theorem 3

As is the case in Mossé's original proof, the proof of Theorem 3 goes in two steps.

As a first step, we express the constant M of Theorem 2 in terms of the constants N , R, k and Q of Theorem 3. This is done in Proposition 7 with a proof following the lines of the proof of [START_REF] Kůrka | Topological and Symbolic Dynamics[END_REF]Proposition 4.35]. The difference is that we take care of all the needed bounds to express the constant of recognizability.

As a second step, we show that the constant L of Theorem 2 can be taken equal to M + |σ d |, where d is defined as in Theorem 3 and M is such that for all i, m ∈ Z,

x [f (d) (i)-M ,f (d) (i)+M ] = x [m-M,m+M ] ⇒ m ∈ E(x, σ d ).
We first start with the following lemma. Lemma 6. Let σ : A * → A * be a non-erasing morphism, u ∈ A * be a word and n be a positive integer.

If v = v 0 • • • v t+1 ∈ A * is a word of length t + 2 such that σ n (v[1, t]) is a factor of σ n (u), and σ n (u) is a factor of σ n (v), then σ n |σ n | |u| -2 ≤ t ≤ |σ n | σ n |u|. Proof. Indeed, since σ n (v[1, t]) is a factor of σ n (u) we have t σ n ≤ |σ n (v [1,t] )| ≤ |σ n (u)| ≤ |u||σ n |. Hence t ≤ |u||σ n |/ σ n . Similarly, since σ n (u) is a factor of σ n (v), we have |u| ≤ (t + 2)|σ n |/ σ n . We thus have |u| σ n |σ n | -2 ≤ t ≤ |u| |σ n | σ n .
Proposition 7. Let σ : A * → A * be a morphism with an admissible fixed point x ∈ A Z . Assuming that x is k-power-free and that there is some constant N such that for all n ∈ N, |σ n | ≤ N σ n , we consider the constants

• R = N 2 (k + 1) + 2N ; • Q = 1 + p x (R) R N ≤i≤RN +2 p x (i) . The constant M = R|σ Q | is such that for all i, m ∈ Z, x [f (1) (i)-M,f (1) (i)+M ] = x [m-M,m+M ] ⇒ m ∈ E(x, σ). (2)
Proof. We follow the lines of the proof of [START_REF] Kůrka | Topological and Symbolic Dynamics[END_REF]Theorem 2]. Obviously, if Equation ( 2) is true when we replace M by some l ≤ M , then it is true with M . Let us show such an l exists. We proceed by contradiction, assuming that for all l ≤ M , there exist i, j such that x [i-l,i+l] = x [j-l,j+l] with i ∈ E(x, σ) and j / ∈ E(x, σ). For each integer p such that 0 < p ≤ Q, we consider the integer l p = R|σ p | ≤ M . Let i p and j p be some integers such that

x [ip-lp,ip+lp] = x [jp-lp,jp+lp] ,
with i p ∈ E(x, σ) and j p / ∈ E(x, σ).

We let r p and s p denote the smallest integers such that

Card ([i p -r p , i p ) ∩ E(x, σ p )) = R 2 ; Card ([i p , i p + s p ] ∩ E(x, σ p )) = R 2 + 1.
There is an integer i p such that

f (p) (i p ) = i p -r p and f (p) (i p + R) = i p + s p .
We set

u p = x [i p ,i p +R) .
We have σ p (u p ) = x [ip-rp,ip+sp) . Notice that any interval of length l p contains at least R -1 elements of E(x, σ p ). We thus have i p -l p ≤ i p -r p ≤ i p + s p ≤ i p + l p . Consequently we also have

x [jp-rp,jp+sp) = σ p (u p ). (3)
However, j p -r p does not need to belong to E(x, σ p ). Let j p and t p denote the unique integers such that f (p) (j p ) < j p -r p ≤ f (p) (j p + 1);

f (p) (j p + t p + 1) ≤ j p + s p < f (p) (j p + t p + 2). (4)
Consequently, the word σ p (x [j p +1,j p +tp] ) is a factor of σ p (u p ) and the word σ p (u p ) is a factor of σ p (x [j p ,j p +tp+1] ). By Lemma 6, we have

R σ p |σ p | -2 ≤ t p ≤ R |σ p | σ p . ( 5
) Hence R N -2 ≤ t p ≤ RN. Let v p = x [j p ,j p +tp+1] .
The number of possible pairs of words (u p , v p ) is at most

p x (R)   R N ≤i≤RN +2 p x (i)   < Q.
Therefore, there exist p and q in [1, Q] such that p < q and (u p , v p ) = (u q , v q ). In particular, we also have t p = t q . We write

t = t p , u = u p , v = v p , ṽ = x [j p +1,j p +t] .
Using the above notation we recall that we have

u = x [i p ,i p +R) = x [i q ,i q +R) ; (6) v = x [j p ,j p +t+1] = x [j q ,j q +t+1] . (7)
Let A p , B p , A q and B q be the words

A p = x [jp-rp,f (p) (j p +1)) ; B p = x [f (p) (j p +t+1),jp+sp) ; A q = x [jq-rq,f (q) (j q +1)) ; B q = x [f (q) (j q +t+1),jq+sq) .
We thus have

x [jp-rp,jp+sp) = A p σ p (ṽ)B p and x [jq-rq,jq+sq) = A q σ q (ṽ)B q ,

with, using (4),

max{|A p |, |B p |} ≤ |σ p | and max{|A q |, |B q |} ≤ |σ q |. (9)
From ( 3) and ( 8), we obtain σ q-p (A p )σ q (ṽ)σ q-p (B p ) = A q σ q (ṽ)B q .

We claim that A q = σ q-p (A p ) (and hence B q = σ q-p (B p )). [START_REF] Kari | L systems[END_REF] If not, the word σ q (ṽ) has a prefix which is a power w r with r = |σ q (ṽ)| ||Aq|-|σ q-p (Ap)|| . Since, using ( 5) and ( 9),

|σ q (ṽ)| ≥ t σ q ≥ R N -2 σ q and ||A q | -|σ q-p (A p )|| ≤ |σ q |,
we deduce from the choice of R that r ≥ k + 1, which contradicts the definition of k. We thus have A q = σ q-p (A p ) and B q = σ q-p (B p ). We now show that the elements of E(x, σ) occur in the two intervals [i q -r q , i q + s q ] and [j q -r q , j q + s q ] at the same relative positions, i.e., [j q -r q , j q + s q ] ∩ E(x, σ) = ([i q -r q , i q + s q ] ∩ E(x, σ)) -(i q -j q ). [START_REF] Klouda | Synchronizing delay for binary uniform morphisms[END_REF] This will contradict the fact that i q belongs to E(x, σ) and j q does not. By [START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF], we have

σ p (v) = x [f (p) (j p ),f (p) (j p +t+2)) = x [f (p) (j q ),f (p) (j q +t+2)) .
Since σ p (u) is a factor of σ p (v), we deduce from ( 4) that there exists m q ∈ Z such that

f (p) (j q ) < m q -r p < m q + s p < f (p) (j q + t + 2) ( 12
)
and

x [mq-rp,mq+sp) = σ p (u) = A p σ p (ṽ)B p .
By applying σ q-p , we obtain

x [f (q-p) (mq-rp),f (q-p) (mq+sp)) = A q σ q (ṽ)B q ,
and, from [START_REF] Kůrka | Topological and Symbolic Dynamics[END_REF],

f (q) (j q ) < f (q-p) (m q -r p ) < f (q-p) (m q + s p ) < f (q) (j q + t + 2).
As we also have x [jq-rq,jq+sq) = A q σ q (ṽ)B q with, by (4), f (q) (j q ) < j q -r q ≤ f (q) (j q + 1) ≤ f (q) (j q + t + 1) ≤ j q + s q < f (q) (j q + t + 2), we apply the same argument as to show [START_REF] Kari | L systems[END_REF] and get j q -r q = f (q-p) (m q -r p ) (hence j q + s q = f (q-p) (m q + s p )). We thus get that j q -r q belongs to E(x, σ q-p ) ⊂ E(x, σ). Since we also have

x [f (1) -1 (jq-rq),f (1) -1 (jq+sq)) = σ q-p-1 (x [mq-rp,mq+sp) ) = σ q-p-1 (A p σ p (ṽ)B p ), x [f (1) -1 (iq-rq),f (1) -1 (iq+sq)) = σ q-1 (x [i q ,i q +R) ) = σ q-p-1 (A p σ p (ṽ)B p ), we get x [f (1) -1 (jq-rq),f (1) -1 (jq+sq)) = x [f (1) -1 (iq-rq),f (1) -1 (iq+sq)) ,
with j q -r q , i q -r q belonging to E(x, σ). By applying σ to these two words, we thus obtain [START_REF] Klouda | Synchronizing delay for binary uniform morphisms[END_REF], which ends the proof.

Proposition 7 gives a more precise statement than Item 1 in Theorem 2. It also makes Item 2 more precise in the case of morphisms that are injective on A by taking L = M + |σ|. For non-injective morphisms, a key argument in Mossé's original proof is to prove the existence of an integer d such that for all a, b ∈ A, if σ n (a) = σ n (b) for some n, then σ d (a) = σ d (b). Theorem 8 below ensures that we can take d = (Card A) -1.

Theorem 8 ([6, Theorem 3]). Let σ : A * → A * be a morphism such that σ(A) = {ε}. For all words u, v ∈ A * , we have

σ (Card A)-1 (u) = σ (Card A)-1 (v) ⇒ ∀n, σ n (u) = σ n (v).
We now give the proof of Item 2 in Theorem 2.

Proposition 9. Let σ : A * → A * be a morphism with an admissible fixed point x ∈ A Z . Let d ∈ {1, 2, . . . , Card A} be such that for all words u, v ∈ L(x),

σ d-1 (u) = σ d-1 (v) ⇒ ∀n, σ n (u) = σ n (v).
If M is a constant such that for all i, m ∈ Z,

x [f d (i)-M,f d (i)+M ] = x [m-M,m+M ] ⇒ m ∈ E(x, σ d ),
then σ is recognizable on x and its constant of recognizability for x is at most

M + |σ d |. Proof. Let i, m ∈ Z such that x [f (1) (i)-M -|σ d |,f (1) (i)+M +|σ d |] = x [m-M -|σ d |,m+M +|σ d |] .
By the definition of M , there exists j ∈ Z such that m = f (1) (j). Our goal is to show that

x i = x j .
There exists k ∈ Z such that

f (1) (i) -|σ d | < f (d) (k) ≤ f (1) (i) < f (d) (k + 1) ≤ f (1) (i) + |σ d |.
In particular, this implies that

f (d-1) (k) ≤ i < f (d-1) (k + 1). Consider c = f (1) (i) -f (d) (k) and d = f (d) (k + 1) -f (1) (i). We have x [f (d) (k)-M,f (d) (k)+M ] = x [f (1) (j)-c-M,f (1) (j)-c+M ] ; x [f (d) (k+1)-M,f (d) (k+1)+M ] = x [f (1) (j)+d-M,f (1) (j)+d+M ] .
By the definition of M , there exists l ∈ Z such that

f (d) (l) = f (1) (j) -c and f (d) (l + 1) = f (1) (j) + d.
We thus have f (d-1) (l) ≤ j < f (d-1) (l + 1), and,

x [f (d) (k),f (d) (k+1)) = x [f (d) (l),f (d) (l+1)) . Hence σ d (x k ) = σ d (x l )
. By the definition of d, we also have

σ d-1 (x k ) = σ d-1 (x l ). Hence x [f (d-1) (k),f (d-1) (k+1)) = x [f (d-1) (l),f (d-1) (l+1)) .
Since we have f (1)

(i) -f (d) (k) = f (1) (j) -f (d) (l), we also have i -f (d-1) (k) = j -f (d-1) (l). Hence x i = x j .

Proof of Theorem 4

In this section, we show that the constants appearing in Theorem 3 can all be bounded by some computable constants. In all what follows, we assume that σ : A * → A * is a primitive morphism. By taking a power of σ if needed, we can assume that it has an admissible fixed point x ∈ A Z . Furthermore, we have L(x) = L(y) for all admissible fixed points y of σ. We let L(σ) denote this set and we write L n (σ) = L(σ) ∩ A 2 . The constants appearing in Theorem 3 are thus the same whatever the admissible fixed point we consider and the morphism is recognizable.

With the morphism σ, one associates its incidence matrix M σ defined by (M σ ) a,b = |σ(b)| a , where |u| a denotes the number of occurrences of the letter a in the word u. If σ is a primitive morphism, it is well known that for all a ∈ A there exists a constant c a such that |σ n (a)| ≤ c a α n for all n, where α is the dominant eigenvalue of M σ (see [START_REF] Charlier | Asymptotic properties of free monoid morphisms[END_REF] for a detailed study of |σ n (a)|).

Lemma 10 ([9]

). A d×d matrix M is primitive if and only if there is an integer k ≤ d 2 -2d+2 such that M k contains only positive entries.

Given an infinite word x ∈ A Z and a word u ∈ L(x), a return word to u in x is a word r such that ru belongs to L(x), u is a prefix of ru and ru contains exactly two occurrences of u. The infinite word x is linearly recurrent if it is recurrent (all words in L(x) appear infinitely many times in x) and there exists some constant K such that for all u ∈ L(x), any return word to u has length at most K|u|.

The next two results give bounds on the constants appearing in Theorem 3.

Theorem 11 ([5]). If x ∈ A Z is a aperiodic and linearly recurrent sequence for the constant K, then x is (K + 1)-power-free and p x (n) ≤ Kn for all n.

Proposition 12 ([4]). Let σ : A * → A * be an aperiodic primitive morphism and x be one of its admissible fixed points. Then, for all n, we have

|σ n | ≤ |σ| (Card A) 2 σ n .
Furthermore, x is linearly recurrent for some constant

K σ < |σ| 4(Card A) 2 .
Proof. Durand [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF] showed that the constant of linear recurrence K σ is at most equal to T N |σ|, where

• N is a constant such that |σ n | ≤ N σ n for all n;

• T is the maximal length of a return word to a word in L 2 (σ).

Here we only prove that N ≤ |σ| (Card A) 2 and T ≤ 2|σ| 2(Card A) 2 . The constant of linear recurrence is thus at most 2|σ| 1+3(Card A) 2 < |σ| 4(Card A)

n | ≤ σ n+d 2 ≤ |σ d 2 | σ n , so N ≤ |σ d 2 |.
Let a ∈ A such that σ is prolongable on a. Thus for all n, any word that occurs in σ n (a) also occurs in σ n+1 (a). Let us show that for all n > d 2 , any word u ∈ L 2 (σ) occurs in σ n (a). For all n, the words of L 2 (σ) that occur in σ n+1 (a) occur in images under σ of the words of L 2 (σ) that occur in σ n (a). As any word occurring in σ n (a) also occurs in σ n+1 (a), the words of L 2 (σ) that occur in σ n+1 (a) are those that occur in σ n (a) together with those occurring in the images under σ of these words. Thus, if there is a word of L 2 (σ) that does not occur in σ n (a), there is a sequence (u 1 , u 2 , . . . , u n ) of words in L 2 (σ) such that for all i ≤ n, u i occurs in σ i (a) and does not occur in σ i-1 (a). Hence all words u 1 , . . . , u n are distinct. For n > d 2 , this is a contradiction since there are at most d 2 words in L 2 (σ). Thus, for any letter b ∈ A, all words u ∈ L 2 (σ) occur in σ 2d 2 (b). We deduce that T ≤ 2|σ 2d 2 |.

Proof of Theorem 4. We just have to carry out the computation. Using Theorem 11, Proposition 12 and the notation of Theorem 3, we can take d = Card A and we successively have

k ≤ 1 + K σ ≤ |σ| 4d 2 ; N ≤ |σ| d 2 ; R = N 2 (k + 1) + 2N ≤ |σ| 2d 2 (|σ| 4d 2 + 1) + 2|σ| d 2 ≤ 2|σ| 6d 2 ; Q = 1 + p x (R)   R N ≤i≤RN +2 p x (i)   ≤ K σ 2|σ| 6d 2   0≤i≤2+2|σ| 7d 2 iK σ   ≤ 6|σ| 28d 2 .
We finally get that the constant of recognizability of σ is at most

2|σ| 6d 2 |σ| 6d|σ| 28d 2 + |σ| d = 2|σ| 6d 2 +6d|σ| 28d 2 + |σ| d .

Recognizability of powers of morphisms

Theorem 3 gives a general bound on the constant of recognizability of recognizable morphisms. Powers of a recognizable morphism σ are obviously recognizable. However, the bound given in Theorem 3 applied to σ p is far from being optimal. In this section we give two results concerning the constant of recognizability of σ p .

Proposition 13. If σ : A * → A * is recognizable on x ∈ A Z and if L is the constant of recognizability of σ for x, then for all p > 0, σ p is recognizable on x and its constant of recognizability for x is at most L p-1 i=0 |σ i |.

Proof. The result holds by induction on p > 0. The case p = 1 is trivial. Let us assume that the result holds for p -1 and let us prove it for p. The infinite word x is obviously an admissible fixed point of σ p . With L p = L p-1 i=0 |σ i |, let us show that for all i ∈ Z, the word x [f (p) (i)-Lp,f (p) (i)+Lp] uniquely determines the letter x i .

Let m and M be, respectively, the smallest and the largest integer such that f (p) (i) -L p ≤ f (p-1) (m) -L p-1 < f (p-1) (M ) + L p-1 ≤ f (p) (i) + L p [START_REF] Mignosi | If a D0L language is k-power free then it is circular[END_REF] and let us show that m ≤ f (1) (i) -L < f (1) (i) + L ≤ M.

We consider the first inequality with m > 0; the other cases are similar. The integer m being the smallest one satisfying (13), we have

f (p-1) (m -1) -L p-1 < f (p) (i) -L p .
Since we have f

Assume by contradiction that f (1) (i) < m + L, hence that f (1) (i) ≤ m + L -1. The function f (p-1) being increasing, we have

f (p-1) (f (1) (i)) = f (p) (i) ≤ f (p-1) (m + L -1) = f (p-1) (m) + |σ p-1 (x [m,m+L-1) )|.
We thus get f (p) (i) ≤ f (1) Corollary 14. If σ : A * → A * is aperiodic primitive and if L is its constant of recognizability on x ∈ A Z , then σ p is recognizable on x and its constant of recognizability for x is at most LC α p -1 α-1 , where α is the dominant eigenvalue of M σ and C is a constant such that |σ p | ≤ Cα p for all p. In particular, the constant C can be taken equal to max 1≤k≤Card A y k min 1≤k≤Card A y k , where y = (y k ) 1≤k≤Card A is a positive eigenvector of M σ .

Proof. The proof directly follows from [START_REF] Horn | Matrix Analysis[END_REF]Corollary 8.1.33].

  we define |σ| and σ by, respectively,

2 .

 2 Let us write d = Card A. By Lemma 10, the matrix M d 2 σ contains only positive entries. For all n ≥ 0 and all a ∈ A, we have |σ n+d 2 (a)| = b∈A |σ d 2 (a)| b |σ n (b)| ≥ |σ n |. Since this is true for all a, we get |σ

  (p-1) (m) = f (p-1) (m -1) + |σ p-1 (x m-1 )| and L p -L p-1 = L|σ p-1 |, we get f (p) (i) > f (p-1) (m) + L|σ p-1 | -|σ p-1 (x m-1 )| ≥ f (p-1) (m) + (L -1)|σ p-1 |.

  (m) + (L -1)|σ p-1 |, which contradicts[START_REF] Mossé | Reconnaissabilité des substitutions et complexité des suites automatiques[END_REF].Let us now finish the proof of the result. Using the induction hypothesis, the wordx [f (p-1) (m)-L p-1 ,f (p-1) (M )+L p-1 ] uniquely determines x [m,M ] . As x [f (p-1) (m)-L p-1 ,f (p-1) (M )+L p-1 ] is a factor of x [f (p) (i)-Lp,f (p) (i)+Lp] by (13) and x [f (1) (i)-L,f (1) (i)+L] is a factor of x [m,M ] by (14), the word x [f (p) (i)-Lp,f (p) (i)+Lp] uniquely determines x [f (1) (i)-L,f (1) (i)+L]. We conclude by the definition of recognizability.

Acknowledgements

This work is supported by the Hubert Curien Partnership Tournesol entitled "Algorithmique des substitutions et systèmes de numération".