Á N Sebasti

Fabien Donoso
email: sdonoso@dim.uchile.cl

Alejandro Durand

AND Samuel Maass
email: amaass@dim.uchile.cl

Petite

ON AUTOMORPHISM GROUPS OF LOW COMPLEXITY MINIMAL SUBSHIFTS

Keywords: . 2010 Mathematics Subject Classification. Primary: 54H20; Secondary: 37B10 Minimal subshifts, automorphism group, complexity

In this article we study the automorphism group Aut(X, σ) of a minimal subshift (X, σ) of low word complexity. In particular, we prove that Aut(X, σ) is virtually Z for aperiodic minimal subshifts with affine complexity on a subsequence, more precisely, the quotient of this group by the one generated by the shift map is a finite group. In addition, we provide examples to show that any finite group can be obtained in this way. The class considered includes minimal substitutions, linearly recurrent subshifts and even some minimal subshifts with polynomial complexity. In the case of polynomial complexity, first we prove that for minimal subshifts with polynomial recurrence any finitely generated subgroup of Aut(X, σ) is virtually nilpotent. Then, we describe several subshifts of polynomial complexity to illustrate that the group of automorphisms can still be virtually Z. This behavior seems to be very frequent for low complexity minimal subshifts. The main technique in this article relies on the study of classical relations among points used in topological dynamics, in particular asymptotic pairs.

Introduction

An automorphism of a topological dynamical system (X, T ), where T : X → X is a homeomorphism of the compact metric space X, is a homeomorphism from X to itself which commutes with T . We call Aut(X, T ) the group of automorphisms of (X, T ). There is a similar definition for measurable automorphisms when we consider an invariant measure µ for the system (X, T ) or a general measure preserving system. The group of measurable automorphisms is historically denoted by C(T ) that stands for the centralizer group of (X, T, µ).

The study of automorphism groups is a classical and widely considered subject in ergodic theory. The group C(T ) has been intensively studied for mixing systems of finite rank. We refer to [START_REF] Ferenczi | Systems of finite rank[END_REF] for an interesting survey. Let us mention some key theorems. D. Ornstein proved in [START_REF] Ornstein | On the root problem in ergodic theory[END_REF] that a mixing rank one dynamical system (X, T, µ) has a trivial (measurable) automorphism group: it consists in powers of T . Later, A. del Junco [START_REF] Del Junco | A simple measure-preserving transformation with trivial centralizer[END_REF] showed that the famous weakly mixing (but not mixing) rank one Chacon subshift also shares this property. Finally, for mixing systems of finite rank J. King and J.-P. Thouvenot proved in [START_REF] King | A canonical structure theorem for finite joining-rank maps[END_REF] that C(T ) is virtually Z. That is, its quotient by the subgroup T generated by T is a finite group.

In the non weakly mixing case, B. Host and F. Parreau [START_REF] Host | Homomorphismes entre systèmes dynamiques définies par substitutions[END_REF] proved, for a family of constant length substitution subshifts, that C(σ) is also virtually Z and equals to Aut(X, σ), where σ is the shift map. Concomitantly, M. Lemańczyk and M. Mentzen [START_REF] Lemańczyk | On metric properties of substitutions[END_REF] realized any finite group as the quotient of C(σ) by σ with constant length substitution subshifts.

Priorly to these results, in the topological setting G. A. Hedlund in [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF] described the automorphism groups for a family of binary substitutions including the Thue-Morse subshift. Precisely, he proved that Aut(X, σ) is generated by the shift and a flip map (a map which interchanges the letters). In the positive entropy situation, M. Boyle, D. Lind and D. Rudolph [START_REF] Boyle | The automorphism group of a shift of finite type[END_REF] obtained that the group of automorphisms of mixing subshifts of finite type contains various subgroups, so this group is large in relation to previous examples.

In this paper we focus on the group of automorphisms Aut(X, σ) of minimal subshifts of subaffine complexity and, more generally, on zero entropy subshifts without assuming any mixing condition. All evidence described before in the measurable and topological context shows that we must expect that low complexity systems have a simple automorphism group. This is one of the main questions we want to address in this paper. Here, by complexity we mean the increasing function p X : N → N that for n ∈ N counts the number of words of length n appearing in points of the subshift.

Recently V. Salo and I. Törmä in [START_REF] Salo | Block Maps between Primitive Uniform and Pisot Substitutions[END_REF] proved that for subshifts generated by constant length or primitive Pisot substitutions the group of automorphisms is virtually Z. This generalizes a result of E. Coven for constant length substitutions on two letters [START_REF] Coven | Endomorphisms of substitution minimal sets[END_REF]. In [START_REF] Salo | Block Maps between Primitive Uniform and Pisot Substitutions[END_REF] is asked whether the same result holds for any primitive substitution or more generally for linearly recurrent subshifts. In this paper we answer positively to this question, proving the following more general theorem whose proof is given in Section 3.

Theorem 1.1. Let (X, σ) be an aperiodic minimal subshift. If

lim inf n∈N p X (n) n < ∞
then Aut(X, σ) is virtually Z.

The class of systems satisfying the condition of Theorem 1.1 includes primitive substitutions, linearly recurrent subshifts [START_REF] Durand | Linearly recurrent subshifts have a finite number of nonperiodic factors[END_REF] and more generally subaffine complexity subshifts or even some families with polynomial complexity (see Section 4). In addition, we illustrate this by realizing any finite group as the quotient group Aut(X, σ)/ σ , where (X, σ) is a substitutive subshift. We observe that this result can be obtained combining the main results of [START_REF] Host | Homomorphismes entre systèmes dynamiques définies par substitutions[END_REF] and [START_REF] Lemańczyk | On metric properties of substitutions[END_REF] but we prefer to present here a different and straightforward proof.

Extending Theorem 1.1 for subshifts of polynomial complexity seems to be more intriguing. Nevertheless, several classes of examples still show that Aut(X, σ) has small growth rate. Indeed, in Sections 3 and 4 we give classes of minimal subshifts with polynomial complexity where Aut(X, σ) is virtually nilpotent (Theorem 3.8) and in most cases the finite group is Abelian. Also, very recently, V. Cyr and B. Kra [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF] proved the fact that for transitive subshifts with subquadratic complexity Aut(X, σ)/ σ is periodic, meaning that any element in this group has finite order. Their proof translates the question into a coloring problem of Z 2 and uses a deep combinatorial result of A. Quas and L. Zamboni [START_REF] Quas | Periodicity and local complexity[END_REF]. Our results arise from obstructions related to some classical and some less classical equivalence relations associated to fibers of special topological factors. This idea was already used by J. Olli in [START_REF] Olli | Endomorphisms of Sturmian systems and the discrete chair substitution tiling system[END_REF] to prove that Aut(X, σ) of Sturmian subshifts consists only in powers of the shift by studying the irrational rotation defining the subshift. Here, we consider the maximal nilfactor ( [START_REF] Host | Nilsequences and a Structure Theory for Topological Dynamical Systems[END_REF], [START_REF] Shao | Regionally proximal relation of order d is an equivalence one for minimal systems and a combinatorial consequence[END_REF]) of a minimal subshift to find a class of examples with arbitrarily big polynomial complexity whose group of automorphisms is virtually Z.

Preliminaries, notation and background

2.1. Topological dynamical systems. A topological dynamical system or just a system is a homeomorphism T : X → X where X is a compact metric space. It is classically denoted by (X, T ). Let dist denote a distance on X and for x ∈ X Orb(x) denotes its orbit {T n x; n ∈ Z}. A topological dynamical system is minimal if the orbit of any point is dense in X and is transitive if at least one orbit is dense in X.

An automorphism of the topological dynamical system (X, T ) is a homeomorphism φ of the space X such that φ • T = T • φ. We let Aut(X, T ) denote the group of automorphisms of (X, T ).

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 ni x, T ni y) = 0.
A stronger condition than proximality is asymptoticity. Two points x, y ∈ X are said to be asymptotic if lim n→+∞ dist(T n x, T n y) = 0.

Non trivial asymptotic pairs may not exist in an arbitrary topological dynamical system but it is well known that a non-empty aperiodic subshift always admits one [START_REF] Auslander | Minimal flows and their extensions[END_REF].

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 also say that (Y, S) is a factor of (X, T ) or that (X, T ) is an extension of (Y, S). We also use the notation π : (X, T ) → (Y, S) to indicate a factor map. If π : X → Y is a factor map, we say that (X, T ) is a proximal extension of (Y, S) if for x, x ′ ∈ X the condition π(x) = π(x ′ ) implies that x, x ′ are proximal. For minimal systems, the extension (X, T ) is called an almost one-to-one extension if there exists a point y ∈ Y with at most one pre-image for the map π.

The relation between these two notions is given by the following folklore lemma.

Lemma 2.1. Let π : (X, T ) → (Y, S) be an almost one-to-one extension of minimal systems. Then, (X, T ) is a proximal extension of (Y, S)

Proof. Let y 0 ∈ Y be a point with one pre-image by π. For any points x, x ′ ∈ X with the same image π(x) = π(x ′ ), there is a sequence (n i ) i∈N in Z such that T ni π(x) converges to y 0 as i goes to infinity. Since π(x) = π(x ′ ), the sequence (T ni π(x ′ )) i∈N also converges to y 0 . Taking a subsequence if needed, the sequences (T ni x) i∈N and (T ni x ′ ) i∈N converge to the same unique point in the pre-image of y 0 by π. This shows that points x and x ′ are proximal.

2.2. Subshifts. Throughout this paper the shift map is denoted by σ : A Z → A Z where A is some finite alphabet and A Z is the set of bi-infinite sequences (x n ) n∈Z on this alphabet. It is defined by σ((x n ) n∈Z ) = (x n+1 ) n∈Z . The elements of A are called letters. A subshift is a topological dynamical system (X, σ) where X is a closed σ-invariant subset of A Z (we consider the product topology on A Z ).

Observe that even if the alphabet may change we continue to denote the shift map by σ. For convenience, when we state general results about topological dynamical systems we use the notation (X, T ), and we use (X, σ) to state particular results about subshifts. Let φ : (X, σ) → (Y, σ) be a factor map. By the Curtis-Hedlund-Lyndon Theorem, φ is determined by a local map φ : A 2r+1 → A in such way that φ(x) n = φ(x n-r . . . x n . . . x n+r ) for any n ∈ Z and x ∈ X, where r ∈ N is called a radius of φ. The local map φ naturally extends to the set of words of length at least 2r + 1, and we denote this map also by φ.

A word w = w 0 . . . w ℓ-1 with symbols w i 's on the alphabet A is a element of the free monoid A * endowed with the concatenation. The length of w is ℓ and is denoted by |w|. For a subshift (X, σ) we call language of X to the set L(X) of all words x n x n+1 . . . x n+ℓ-1 , x n ∈ A, appearing in some sequence x ∈ X. We denote by L n (X) the set of words of L(X) of length n. The map p X : N → N defined by p X (n) = ♯L n (X) is called the complexity function of (X, σ).

In the proof of Theorem 1.1 we will need the following well known notion that is intimately related to asymptotic pairs. A word w ∈ L(X) is said to be left special if there exist at least two distinct letters a and b such that aw and bw both belong to L(X). In the same way we define right special words.

Equicontinuous systems.

We recall that a topological dynamical system (X, T ) is equicontinuous if the family of transformations {T n ; n ∈ Z} is equicontinuous. It is well known that for an equicontinuous minimal system (X, T ), the closure of the group T in the set of homeomorphisms of X, for the uniform topology, is a compact Abelian group G acting transitively on X (see [START_REF] Auslander | Minimal flows and their extensions[END_REF]).

A typical example is when X is topologically a Cantor set. The dynamical system (X, T ) is then called an odometer. One can show that X is then a pro-finite group. More precisely, there exists a nested sequence of finite index subgroups .

. . ⊂ Γ n+1 ⊂ Γ n ⊂ • • • ⊂ Γ 0 ⊂ Z, with n≥0 Γ n trivial, such that X is isomorphic to the inverse limit lim ←n (Z/Γ n , π n ) = {(x n ) n∈N ; x n ∈ Z/Γ n , x n = π n (x n+1 ) ∀n ≥ 0},
where π n : Z/Γ n+1 → Z/Γ n denotes the canonical projection. The addition in this group is thus given for (

x n ) n∈N , (y n ) n∈N ∈ lim ←n (Z/Γ n , π n ), by (x n ) n∈N + (y n ) n∈N = (x n + n y n ) n∈N ,
with + n stands for the addition in Z/Γ n . The group Z is a dense subgroup through the injection i : k → (k mod Γ n ) n∈N . The action T is then given by the addition by i(1) in the group X. It is a minimal and uniquely ergodic action on X.

2.4.

Nilsystems. We introduce a special class of systems which allows us to compute the automorphism group in some interesting examples and that generalizes equicontinuous systems.

Let G be a group. For g, h ∈ G we write [g, h] = ghg -1 h -1 for the commutator of g and h and for A, B ⊆ G we write [A, B] for the subgroup spanned by {[a, b]; a ∈ A, b ∈ B}. The commutator subgroups G j , j ≥ 1, are defined inductively by setting G 1 = G and G j+1 = [G j , G]. Let d ≥ 1 be an integer. We say that G is d-step nilpotent if G d+1 is the trivial subgroup. Notice that a subgroup of a d-step nilpotent group is also d-step nilpotent, and any Abelian group is 1-step nilpotent.

Let G be a d-step nilpotent Lie group and Γ a discrete cocompact subgroup of G. The compact manifold X = G/Γ is called a d-step nilmanifold. The group G acts on X by left translations and we write this action as (g, x) → gx. Let τ ∈ G and T be the transformation x → τ x. Then (X, T ) or (X, τ ) is called a d-step nilsystem. Nilsystems are distal systems, meaning that there are no proximal pairs and they are uniquely ergodic when the action is minimal. See [START_REF] Auslander | Flows on homogeneous spaces. With the assistance of L[END_REF] and [START_REF] Leibman | Pointwise convergence of ergodic averages for polynomial sequences of translations on a nilmanifold[END_REF] for general references.

An important subclass of nilsystems is the class of affine nilsystems. Let d ∈ N and let A be a d × d integer matrix such that (A -Id) d = 0 (such a matrix is called unipotent). Let α ∈ T d and consider the transformation T :

T d → T d , x → Ax + α.
Let G be the group spanned by A and all the translations of T d . Since A is unipotent one can check that G is a d-step nilpotent Lie group. The stabilizer of 0 is the subgroup Γ spanned by A thus we can identify T d with G/Γ. The topological dynamical system (T d , T ) = (G/Γ, T ) is called a d-step affine nilsystem and it is proved in [START_REF] Parry | Ergodic properties of affine transformations and flows on nilmanifolds[END_REF] that this system is minimal if the projection of α on T d /ker(A -Id) defines a minimal rotation.

2.5. Maximal nilfactor. Let (X, T ) be a minimal topological dynamical system. We say that x, y ∈ X are regionally proximal of order d if for any δ > 0 there exists x ′ , y ′ ∈ X and n = (n 1 , . . . , n d ) ∈ Z d such that dist(x, x ′ ) < δ, dist(y, y ′ ) < δ and dist(T n• ǫ x ′ , T n•ǫ y ′ ) < δ for every ǫ = (ǫ 1 , . . . , ǫ d ) ∈ {0, 1} d \ {(0, . . . , 0)}, where n

• ǫ = d i=1 n i • ǫ i .
Let RP [d] (X) denote the set of regionally proximal points of order d. It is proved that RP [d] (X) is an equivalence relation, first in [START_REF] Host | Nilsequences and a Structure Theory for Topological Dynamical Systems[END_REF] in the distal case and then in [START_REF] Shao | Regionally proximal relation of order d is an equivalence one for minimal systems and a combinatorial consequence[END_REF] in the general minimal case. Of course the map T preserves each class, so that it induces a map T d on the quotient space Z d (X) := X/RP [d] (X). Theorem 2.2 ([20], [START_REF] Shao | Regionally proximal relation of order d is an equivalence one for minimal systems and a combinatorial consequence[END_REF]). Let (X, T ) be a minimal topological dynamical system. Then (Z d (X), T d ) is isomorphic to an inverse limit of minimal d-step nilsystems. Moreover, it is the maximal factor of (X, T ) with this property or maximal d-step nilsystem, meaning that any other factor which is an inverse limit of minimal d-step nilsystems is a factor of (Z d (X), T d ).

In particular, (Z 1 (X), T 1 ) is the maximal equicontinuous factor of (X, T ) [START_REF] Auslander | Minimal flows and their extensions[END_REF].

2.6. General results on automorphisms through factor maps. Definition 2.3. Let π : (X, T ) → (Y, S) be a factor map between the minimal systems (X, T ) and (Y, S), and let φ be an automorphism of (X, T ). We say that π is compatible with φ if π(x) = π(x ′ ) implies π(φ(x)) = π(φ(x ′ )) for any x, x ′ ∈ X. We say that π is compatible with Aut(X, T ) if π is compatible with any φ ∈ Aut(X, T ).

If the factor map π : (X, T ) → (Y, S) is compatible with Aut(X, T ) we can define the projection π(φ) ∈ Aut(Y, S) as the map defined by the equation π(φ(x)) = π(φ)(π(x)) for every x ∈ X. We have that π is a group morphism.

Notice that the map π : Aut(X, T ) → Aut(Y, S) may not be onto or injective. For an irrational rotation on the circle, the group of automorphisms is the whole circle but for its Sturmian extension the group of automorphisms is Z [START_REF] Olli | Endomorphisms of Sturmian systems and the discrete chair substitution tiling system[END_REF]. We will show in Lemma 2.12 that this extension is compatible, hence π is not onto. On the other hand, the projection on the trivial system π cannot be injective.

By considering compatible factor maps in this section we prove that the automorphism group of a d-step nilsystem and any proximal extension is d-step nilpotent. Before considering factors we need two general properties of automorphism groups.

Lemma 2.4. Let (X, T ) be a minimal topological dynamical system. Then the action of Aut(X, T ) on X is free, meaning that every non-trivial element in Aut(X, T ) has no fixed points.

Proof. Let φ ∈ Aut(X, T ) and let x ∈ X such that φ(x) = x. Since φ commutes with T and is continuous, then by minimality φ is the identity. Lemma 2.5. Let (X, T ) be a minimal topological dynamical system. Let x ∈ X and φ ∈ Aut(X, T ). Then x and φ(x) are proximal if and only if φ is the identity.

Proof. We prove the non-trivial direction. Let x ∈ X and φ ∈ Aut(X, T ) such that (x, φ(x)) is a proximal pair. There exists a sequence (n i ) i∈N in Z such that lim i→+∞ dist(T ni x, T ni φ(x)) = 0. We can assume that T ni x converges to y ∈ X and therefore dist(y, φ(y)) = 0. By Lemma 2.4 φ is the identity.

Then considering a proximal extension between minimal systems we get that, Lemma 2.6. Let π : (X, T ) → (Y, S) be a proximal extension between minimal systems and suppose that π is compatible with Aut(X, T ). Then π : Aut(X, T ) → Aut(Y, S) is an injection.

Proof. It suffices to prove that π(φ) = id Y , where id Y is the identity map on Y , implies that φ = id X . Let φ be an automorphism with π(φ) = id Y . For x ∈ X we have that π(φ(x)) = π(φ)π(x) = π(x). Since π is proximal, points x and φ(x) are proximal. By Lemma 2.5 we get the conclusion. Now we study the automorphism group of d-step nilsystems.

Lemma 2.7. Let π : (X, T ) → (Y, S) be an almost one-to-one extension between minimal systems. Then, for any integer d ≥ 1, their maximal d-step nilsystems

(Z d (X), T d ) and (Z d (Y ), S d ) are topologically conjugated. Proof. Let π d : X → Z d (X) and π d : Y → Z d (Y ) denote the quotient maps and let p : Z d (X) → Z d (Y ) be the natural factor map (it exists by maximality of Z d (X)). Let x ∈ X be such that π -1 {π(x)} = {x}. We claim that p -1 {p(π d (x))} = {π d (x)}. Let x ′ be such that p(π d (x)) = p(π d (x ′ )). Then π d (π(x)) = π d (π(x ′ )) and thus ( π(x), π(x ′ )) ∈ RP [d] (Y ). Particularly, there exists a sequence ( n i ) i∈N in Z d such that S ni•ǫ π(x ′ ) converges to π(x) for every ǫ ∈ {0, 1} d \ {(0, . . . , 0)}.
Taking a subsequence we can assume that T ni•ǫ x ′ converges to some point in π -1 {π(x)}. By our assumption, T ni•ǫ x ′ can only converge to x for every ǫ ∈ {0, 1} d \ {(0, . . . , 0)} and thus (x, x ′ ) ∈ RP [d] (X), which means that π d (x) = π d (x ′ ). It follows that p is an almost one-to-one map between distal systems and thus it is a topological conjugacy.

We deduce that, Corollary 2.8. Let π : (X, T ) → (Y, S) be an almost one-to-one extension between minimal systems. If (Y, S) is a nilsystem of order d, then it is the maximal d-step nilsystem of (X, T ).

For instance, since any Sturmian subshift is an almost one-to-one extension of a rotation on the circle [START_REF] Durand | Linearly recurrent subshifts have a finite number of nonperiodic factors[END_REF], this rotation is its maximal 1-step nilsystem or more classically its maximal equicontinuous factor. Similarly, Toeplitz subshifts are the symbolic almost one-to-one extensions of odometers [START_REF] Downarowicz | Survey of odometers and Toeplitz flows[END_REF]. These odometers are hence their maximal 1-step nilsystems.

The next result is a characterization of the automorphisms of an equicontinuous system. In particular, we get that its group of automorphisms is Abelian. Lemma 2.9. Let (X, T ) be an equicontinuous minimal system. Then Aut(X, T ) is the closure of the group T in the set of homeomorphisms of X for the topology of uniform convergence. Moreover Aut(X, T ) is homeomorphic to X.

We deduce the automorphism group of an odometer is the whole odometer group.

Proof. Let x be a point in X and let φ be an automorphism in Aut(X, T ). Let G denote the closure of the group T . By Ascoli's Theorem it is a compact Abelian group. Let us consider a sequence of integers (n i ) i∈N such that the sequence (T ni x) i∈N converges to φ(x). Taking a subsequence if needed, we can assume that the sequence of maps (T ni ) i∈N converges to a homeomorphism g in G. So we get that g -1 • φ(x) = x, and then φ belongs to G by Lemma 2.4. This lemma also ensures that the map g ∈ G → g(x) is a homeomorphism onto its image. The latter being T invariant, it is equal to X. Proof. Let φ be an automorphism of (G/Γ, τ ) and let µ be the unique ergodic invariant measure of (G/Γ, τ ). Since φ commutes with τ we have that τ φµ = φτ µ = φµ and thus τ φµ = φµ. Since µ is the unique τ -invariant measure we have that φµ = µ. Hence φ is also an automorphism of the system (G/Γ, τ, µ) in the measurable setting (a measure preserving transformation that commutes with τ ). It is proved in [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF] that G/Γ is isomorphic to G/Γ ′ where G is a nilpotent Lie group of measure preserving transformations of G/Γ. By Lemma 5.5 of [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF], φ belongs to G and thus Aut(G/Γ, τ ) is d-step nilpotent.

If (Y, S) = (G/Γ, τ ) is a d-step nilsystem,
Theorem 2.11. Let (X, T ) be an inverse limit of d-step nilsystems. Then, its automorphism group Aut(X, T ) is a d-step nilpotent group.

On the other hand, by definition of the regionally proximal relation of order d we have that, Lemma 2.12. Let (X, T ) be a minimal topological dynamical system. Let φ ∈ Aut(X, T ). Then (x, y) ∈ RP [d] (X) if and only if (φ(x), φ(y)) ∈ RP [d] (X). Consequently, the projection π d : X → Z d (X) from X to its maximal d-step nilsystem is compatible with Aut(X, T ).

Combining Theorem 2.11, Lemma 2.12 and Lemma 2.6 we get, Corollary 2.13. Let (X, T ) be a proximal extension of a minimal d-step nilsystem. Then, Aut(X, T ) is a d-step nilpotent group.

Since Sturmian and Toeplitz subshifts are almost one-to-one extensions of their maximal equicontinuous factors, they are also proximal extensions (Lemma 2.1). We obtain as a corollary that their automorphism groups are Abelian. More precisely, Lemma 2.12 and Lemma 2.6 imply that their automorphism groups are subgroups of the automorphism group of their maximal equicontinuous factors, characterized in Lemma 2.9. In addition, it is not difficult to construct minimal symbolic almost one-to-one extensions of d-tep nilsystems by considering codings on well chosen partitions. An example will be developed in Section 4.

On the automorphisms of subshifts with polynomial complexity

In this section we prove the main results of this paper. We start by proving Theorem 1.1 and in a second part we give new proofs of byproduct results from [START_REF] Host | Homomorphismes entre systèmes dynamiques définies par substitutions[END_REF][START_REF] Lemańczyk | On metric properties of substitutions[END_REF]. Namely, a characterization of the automorphisms of bijective constant length substitutions and the realization of any finite group as the quotient Aut(X, T )/ T . We end this section by presenting a tentative generalization of Theorem 1.1 to polynomial complexity by using a result on the growth rate of groups.

For the sequel, we recall that a group G satisfies virtually a property P (e.g., nilpotent, solvable, isomorphic to a given group, ...) if there is a finite index subgroup H ⊂ G satisfying the property P.

3.1.

Proof of Theorem 1.1. Let (X, T ) be a topological dynamical system. It is clear from the definition that for any proximal (asymptotic) pair (x, y) ∈ X ×X and for any φ ∈ Aut(X, T ) we have that (φ(x), φ(y)) is a proximal (asymptotic) pair. We say that the asymptotic pairs (x, y) and (x ′ , y ′ ) belong to the same class if they are in the same orbit, meaning that there exists n ∈ Z such that (x ′ , y ′ ) = (T n x, T n y). A class of asymptotic pairs is a (non closed) T × T -invariant subset of X × X. We denote by [(x, y)] the class of the asymptotic pair (x, y). We say that two classes [(x, y)], [(x ′ , y ′ )] are equivalent if there is an asymptotic pair

(x ′ 1 , y ′ 1 ) ∈ [(x ′ , y ′ )] such that x = x ′
1 or x and x ′ 1 are asymptotic. This defines an equivalence relation and any class is called an asymptotic component. We denote by AS [(x,y)] the asymptotic component of the class [(x, y)] and by AS the collection of asymptotic components.

It is also plain to check for φ ∈ Aut(X, T ) and two equivalent asymptotic classes [(x, y)] and [(x ′ , y ′ )], that classes [(φ(x), φ(y))] and [(φ(x ′ ), φ(y ′ ))] are also equivalent. So the automorphism φ induces a permutation j(φ) on the collection AS of asymptotic components of (X, T ). By denoting PerAS the set of such permutations, formally we have the group morphism

j : Aut(X, T ) → PerAS (1) φ → AS [x,y] → AS [(φ(x),φ(y))] .
In the case of subshifts, the following lemma is a key observation which relates the complexity of the subshift with asymptotic classes. The proof relies in classical ideas from [START_REF]Queffélec Substitution dynamical systems-spectral analysis[END_REF]. Lemma 3.1. Let (X, σ) be a subshift. If (X, σ) has a sublinear complexity, then there is a finite number of asymptotic classes. More generally, if the complexity

p X (n) satisfies lim inf n→+∞ p X (n) n < +∞ ,
then there is a finite number of asymptotic classes.

In particular, this lemma provides a sufficient condition to bound the number of asymptotic components.

Proof. For the first statement see [START_REF]Queffélec Substitution dynamical systems-spectral analysis[END_REF] Lemma V. 22. For the second claim we proceed as follows. The hypothesis implies the existence of a constant κ and an increasing sequence (n i ) i∈N in N such that p X (n i + 1)p X (n i ) ≤ κ. Indeed, if not, for any A > 0 and for any integer n large enough we have p

X (n + 1) -p X (n) ≥ A. It follows that p X (n) -p X (m) = n-1 i=m p X (i + 1) -p X (i) ≥ (n -m)A for any n ≥ m enough large. From here we get that lim inf n→+∞ pX (n) n ≥ A which is a contradiction since A is arbitrary.
Hence, the number of left special words of length n i (see Section 2.2 for the definition) is bounded by κ. Any asymptotic pair defines a sequence with arbitrarily long special words, so there are at most κ asymptotic classes.

A second main ingredient for proving Theorem 1.1 is the following direct corollary of Lemma 2.5. We recall that an asymptotic pair is proximal and that the map j used in the following corollary has been defined in [START_REF] Arnoux | Complexité de suites engendrées par des récurrences unipotentes[END_REF]. Corollary 3.2. Let (X, T ) be a minimal topological dynamical system with at least one asymptotic pair. We have the following exact sequence

1 / / T Id / / Aut(X, T ) j / /
PerAS, where PerAS denotes the set of permutations on the collection of asymptotic components of (X, T ). Moreover, for any automorphism φ, the permutation j(φ) has a fixed point if and only if φ is a power of T .

As a byproduct of this result and Lemma 3.1 we get Theorem 1.1 that we recall and extend here.

Theorem. Let (X, σ) be a minimal aperiodic subshift with lim inf

n→+∞ p X (n) n < +∞.
Then, (1) Aut(X, σ) is virtually isomorphic to Z.

(2) The quotient group Aut(X, σ)/ σ is isomorphic to a finite subgroup of permutations without fixed points. In particular, ♯Aut(X, σ)/ σ divides the number of asymptotic components.

Proof. Only the second part of statement ( 2) is not straightforward from Corollary 3.2. The group Aut(X, σ)/ σ acts freely on the finite set of asymptotic component AS: the stabilizer of any point is trivial. Thus, AS is decomposed into disjoint Aut(X, σ)/ σ -orbits, and any such orbit has the same cardinality as Aut(X, σ)/ σ .

Statement (2) of the theorem enables us to perform explicit computations of the automorphism group for easy cases. A first example comes from Sturmian subshifts. It is well-known that this system admits just one asymptotic component, so any automorphism is a power of the shift map. A bit more general case is when the number of asymptotic components is a prime p (e.g., 2 for the Thue-Morse subshift), then the group Aut(X, σ)/ σ is a subgroup of Z/pZ: either the trivial one or Z/pZ. In particular, since the Thue-Morse subshift admits an automorphism which is not the power of the shift map, then the quotient automorphism group is isomorphic to Z/2Z.

One could ask whether the automorphism group is computable algorithmically, at least for substitution subshifts, or explicitly by theoretical arguments for some families of subshifts. This will be achieved in [START_REF] Durand | Decidability of the factorization for minimal substitutive subshifts[END_REF] for substitutive and linearly recurrent subshifts.

Statement ( 2) is not a real restriction. Given any finite group G, it acts on itself by left multiplication L g (h) = g • h for g, h ∈ G. The map L g defines then a permutation on the finite set G without fixed points. So G is a subgroup of elements of the permutation group on ♯G elements which verifies statement (2) in the theorem. Thus, it is natural to ask whether we can realize any finite group as Aut(X, T )/ T or if we can characterize those finite groups. This is done in the next subsection.

Finally, notice that the complexity condition of Theorem 1.1 is compatible with lim sup n→+∞ p X (n)/n = +∞. In Section 4.4 we construct a minimal subshift with subexponential complexity satisfying lim inf n→+∞ p X (n)/n < +∞ and lim sup n→+∞ p X (n)/n d = +∞ for every d > 1. Thus, in this case, the automorphism group is virtually Z by Theorem 1.1.

3.2.

A characterization of Aut(X, σ)/ σ for constant length substitutions. In this section, by using the results of Section 3.1, we provide a characterization of the automorphism group for subshifts given by a constant length substitution τ : A → A * on a finite alphabet A. Our characterization follows from the one of asymptotic components. We deduce then new and direct proofs of two already known results. The first one is due to B. Host and F. Parreau [START_REF] Host | Homomorphismes entre systèmes dynamiques définies par substitutions[END_REF] on the characterization of the automorphism group of bijective constant length substitutions. The second one is a combination of results in [START_REF] Lemańczyk | On metric properties of substitutions[END_REF] and [START_REF] Host | Homomorphismes entre systèmes dynamiques définies par substitutions[END_REF], giving an explicit example of a substitutive minimal subshift (X, σ) such that Aut(X, σ)/ σ is isomorphic to an arbitrary finite group G. Notice that in [START_REF] Lemańczyk | On metric properties of substitutions[END_REF] the authors have a similar statement but in the measurable setting.

We recall that a substitution τ : A → A * is of constant length ℓ > 0 if any word τ (a) for the letter a ∈ A is of length ℓ. A substitution of constant length is bijective if the corresponding letters at position i ∈ {0, . . . , ℓ -1} of all τ (a)'s are pairwise distinct. We denote by X τ the subshift X τ = {x ∈ A Z ; any word of x appears in τ n (a) for some n ≥ 0 and a ∈ A}.

For constant length substitution, it is well known (e.g. see [START_REF]Queffélec Substitution dynamical systems-spectral analysis[END_REF]) that the subshift (X τ , τ ) is minimal if and only if the substitution τ is primitive, that is, for some power p ≥ 0 and any letter a ∈ A, the word τ p (a) contains all the letters of the alphabet. Recall that the substitution τ is aperiodic if and only if X τ is infinite. Lemma 3.3. Let τ be a primitive aperiodic bijective constant length substitution.

Let (x, y) = ((x n ) n∈Z , (y n ) n∈Z ) ∈ X 2
τ be an asymptotic pair with x n = y n for any n ≥ 0 and x -1 = y -1 . Then, there exists an asymptotic pair

((x ′ n ) n∈Z , (y ′ n ) n∈Z ) ∈ X 2 τ with x ′ n = y ′ n for any n ≥ 0 and x ′ -1 = y ′ -1 , such that τ ((x ′ n ) n∈Z ) = (x n ) n∈Z and τ ((y ′ n ) n∈Z ) = (y n ) n∈Z .
Proof. Let ℓ be the length of the substitution τ . By the classical result of B. Mossé [START_REF] Mossé | Reconnaissabilité des substitutions et complexité des suites automatiques[END_REF][START_REF] Mossé | Puissances de mots et reconnaissabilité des points fixes d'une substitution, Theoret[END_REF] on recognizability, the substitution τ : X τ → τ (X τ ) is one-to-one. Moreover, the collection {σ k τ (X τ ) : k = 0, . . . , ℓ -1} is a clopen partition of X τ . So, there are

x ′ = (x ′ n ) n∈Z , y ′ = (y ′ n ) n∈Z ∈ X τ and 0 ≤ k x , k y < ℓ such that σ kx τ (x ′ ) =
x and σ ky τ (y ′ ) = y.

We claim that we have k x = k y = 0. Since the sequences x and y are asymptotic, there are integers n ≥ 0, k ′ ∈ {0, . . . , ℓ -1} such that σ n (x), σ n (y) ∈ σ k ′ (τ (X τ )). The substitution τ is of constant length ℓ, so we have σ ℓ • τ = τ • σ. Therefore, we get x and y are in the same clopen set σ k (τ (X τ )) for some k ∈ {0, . . . , ℓ -1}. Let us assume that k ≥ 1. The words x -1 x 0 . . . x k-1 , y -1 y 0 . . . y k-1 are then prefixes of the words τ (x ′ -1 ) and τ (y ′ -1 ) respectively. Since the substitution τ is bijective and x 0 = y 0 , we have x ′ -1 = y ′ -1 . In particular, we get x -1 = y -1 : a contradiction. To finish the proof, notice that the substitution τ is injective on the letters, so we obtain x ′ n = y ′ n for any n ≥ 0 and x ′ -1 = y ′ -1 . Lemma 3.4. Let τ be a primitive aperiodic bijective constant length substitution. Then, there exists an integer p ≥ 0 such that for any asymptotic pair

((x n ) n∈Z , (y n ) n∈Z ) ∈ X 2
τ the one-sided infinite sequences (x n+n0 ) n≥0 , (y n+n0 ) n≥0 are equal for some n 0 ∈ Z and fixed by τ p .

Proof. Shifting the indices if needed by some σ n0 , we can assume that for the asymptotic pair (x, y) = ((x n ) n∈Z , (y n ) n∈Z ) we have x n = y n for any integer n ≥ 0 and x -1 = y -1 . Let p ≥ 0 be an integer such that for any letter a ∈ A, any word in {τ pn (a)} n≥1 starts with the same letter. Hence, the sequence of sequences (τ pn (aa • • • )) n≥0 converges to a one-sided infinite word fixed by τ p .

Applying inductively Lemma 3.3 to the substitution τ p , we get a sequence of asymptotic pairs ((x (i) , y (i) )) i≥0 verifying the conclusions of the lemma and such that τ p (x (i+1) ) = x (i) , τ p (y (i+1) ) = y (i) , x (0) = x and y (0) = y. By the definition of p, all sequences x (i) and also y (i) , i ≥ 0, share the same letter a at index 0. The conclusion of the lemma follows straightforwardly since we assume that τ pn (a • • • ) converges to a one-sided infinite word fixed by τ p .

Thanks to this lemma we can obtain another proof of the following result due to B. Host and F. Parreau. Theorem 3.5. [START_REF] Host | Homomorphismes entre systèmes dynamiques définies par substitutions[END_REF] Let τ be a primitive bijective constant length substitution. Then, any automorphism of the subshift X τ is the composition of some power of the shift with an automorphism φ of radius 0. Moreover, its local rule φ :

A → A satisfies τ • φ = φ • τ. (2)
Conversely, notice that a local map satisfying (2) defines an automorphism of the subshift. Hence we obtain an algorithm to determine in this case the group of automorphisms since there is just a finite number of local rules of radius 0.

Proof. Notice first that when X τ is finite, it is reduced to a finite orbit. Hence any automorphism is a power of the shift map by Lemma 2.9.

Let us assume now that the substitution τ is aperiodic and let x = (x n ) n∈Z , y = (y n ) n∈Z ∈ X τ be two asymptotic sequences. Lemma 3.4 provides a power p ≥ 0 such that, shifting the sequences if needed by some σ n0 , we can assume that (x n ) n≥0 and (y n ) n≥0 coincide and are fixed by τ p . Let φ be an automorphism of the subshift (X τ , σ). The pair (φ(x), φ(y)) is also an asymptotic pair. Again, Lemma 3.4 ensures that for some integer n 1 ∈ Z, the sequences (φ(x) n+n1 ) n≥0 and (φ(y) n+n1 ) n≥0 coincide and are also fixed by τ p (observe as stated in Lemma 3.4, we can use the same power p for any couple of asymptotic pairs). In the following, we will consider the automorphism φ ′ = σ n1 •φ, thus by definition, the sequence (φ ′ (x) n ) n≥0 is also fixed by τ p .

Let r and φ′ denote the radius and the local map of φ ′ respectively. Taking a power of τ p if needed, we can assume that the length ℓ of τ p is greater than 2r + 1. Suppose now that x n = x m for some n, m ≥ 0. We have φ ′ (x) mℓ+r = φ′ (x mℓ . . . x mℓ+2r ) = φ′ (τ p (x m ) [0,2r] ) = φ′ (τ p (x n ) [0,2r] ) = φ ′ (x) nℓ+r , where for a word u = u 0 . . . u ℓ-1 , u [0,2r] stands for the prefix u 0 . . . u 2r . Since φ ′ (x) nℓ+r and φ ′ (x) mℓ+r are the r+1 th letters of the words τ p (φ ′ (x) n ) and τ p (φ ′ (x) m ) respectively, and the substitution τ is bijective, we obtain that φ ′ (x) n = φ ′ (x) m .

Hence, we can define the local map ψ : A → A by ψ(x n ) = φ ′ (x) n for any n ≥ 0. This provides a shift commuting map ψ : A Z → A Z such that for any word w in the language L(X τ ), we have that ψ(τ p (w)) = τ p (ψ(w)). Thus ψ(X τ ) ⊂ X τ . Since the substitution τ is bijective we also get relation [START_REF] Auslander | Minimal flows and their extensions[END_REF]. In the same way, using φ ′-1 instead of φ ′ we obtain that ψ is invertible. By construction, we have that ψ -1 φ ′ (x) is asymptotic to x, so by Lemma 2.5,

ψ = φ ′ = σ n1 • φ.
A second consequence of Lemma 3.4 is the realization of any finite group as the group Aut(X, σ)/ σ for a substitutive subshift of constant length. Proposition 3.6. Given a finite group G, there is a substitutive minimal subshift (X, σ) such that Aut(X, σ)/ σ is isomorphic to G.

Proof. The Fibonacci subshift is both a substitutive and a Sturmian subshift, then by previous discussion the quotient group Aut(X, σ)/ σ is trivial. Then, let us assume that the finite group G is not trivial. We choose an enumeration of its elements G = {g 0 , g 1 , . . . , g p-1 } with p ≥ 2 where g 0 denotes the neutral element.

For an element h ∈ G, we denote by L h : G → G the bijection g → hg. We consider the alphabet G, viewed as a finite set, and define the substitution τ from the set of letters G into the set of words G * , by

τ : g → L g (g 0 )L g (g 1 ) • • • L g (g p-1 ).
Since the map L g is a bijection on G, the substitution τ of constant length is primitive and bijective. Thus the associated subshift (X τ , σ).

Moreover observe that for any letter g ∈ G, the word τ (g) starts by the letter g, so any sequence (τ n (gg • • • )) n≥1 converges to a τ -invariant infinite word.

We claim that the subshift (X τ , σ) is not periodic, i.e., not reduced to a periodic orbit. To show this it suffices to give an example of an asymptotic pair. The word g 0 g 1 belongs to the language L(X τ ) of the subshift X τ . Hence the words τ (g 0 )τ (g 1 ) and its sub-word g p-1 g 1 (which is different from the word g 0 g 1 ) also belong to L(X τ ). It follows for any integer n ≥ 0 that the words τ n (g 0 ).τ n (g 1 ) and τ n (g p-1 ).τ n (g 1 ) are also in the language. Taking a subsequence if needed, these words converge as n goes to infinity to two sequences x and y ∈ X τ that are, by construction, asymptotic.

Given an element g ∈ G we extend the definition of the map L g to G * by defining for a word w = h 1 . . . h n , L g (w) := L g (h 1 ) . . . L g (h n ). By concatenation, it defines a left continuous G-action on G Z . It is important to note that we have the relation for any g, h ∈ G L g (τ (h)) = τ (L g (h)).

(3) Hence any map L g preserves the subshift X τ and we have a left action of G on X τ . It is plain to check that L : g → L g defines an injection of G into Aut(X τ , σ). Actually, we claim that we have a converse which allows to finish the proof. Lemma 3.7. For the subshift X τ defined above the map

ϕ : Z × G → Aut(X τ , σ) (n, g) → σ n • L g is a group isomorphism.
Proof of Lemma 3.7. To show the injectivity of the map ϕ let us assume there are g ∈ G and an integer k such that L g (x) = σ k (x) for any x ∈ X. Necessarily k = 0, otherwise the infinite sequence L g lim n→+∞ τ n (g 3), is ultimately periodic. This is impossible since the subshift X τ is not periodic. The injectivity of the map L implies finally that the map ϕ is injective.

-1 g -1 • • • ) , which is equal to lim n τ n (g 0 g 0 • • • ) by formula (
To show it is also onto, it is enough to prove that any automorphism φ ∈ Aut(X τ , σ) may be written as a power of the shift composed with a map of the kind L g . Let (x, y) be an asymptotic pair. By Lemma 3.4 up to shift x, y and compose φ with a power of the shift map, there exist g 1 , g 2 ∈ G such that the sequences x, y are positively asymptotic to lim n→+∞ τ n (g 1 ), and φ(x), φ(y) are positively asymptotic to lim n→+∞ τ n (g 2 g 2 • • • ). It follows from (3) that the points x and L g1(g -1

2 ) • φ(x) are asymptotic. So, by Lemma 2.5 the maps φ and (L g1(g -1

2 ) ) -1 = L g2(g -1 1 ) coincide.

3.3.

Recurrence and growth rate of groups. We try to extend Theorem 1.1 to subshifts with higher complexity. For this, we need to introduce a stronger condition. We define, for a topologically transitive subshift (X, σ) and an integer n ≥ 1, a local recurrence time:

N X (n) := inf{|w|; w ∈ L(X) contains any word of X of length n}.
Clearly, this value is well defined and satisfies N X (n) ≥ p X (n) + n. For instance, it is well-known that any primitive substitutive subshift is linearly repetitive meaning that sup n≥1 NX (n) n < +∞. We obtain the following result.

Theorem 3.8. Let (X, σ) be a transitive subshift such that sup n≥1

NX (n) n d
< +∞ for some d ≥ 1. Then, there is a constant C depending only on d, such that any finitely generated subgroup of Aut(X, σ) is virtually nilpotent of step at most C.

Proof. Let S = φ 1 , . . . , φ ℓ ⊂ Aut(X, σ) be a finitely generated group. Let r be an upper bound of the radii of the local maps associated to all generators φ i of S and their inverses. For n ∈ N consider

B n (S) = {φ s1 i1 • • • φ sm im ; 1 ≤ m ≤ n, i 1 , .
. . , i m ∈ {1, . . . , ℓ}, s 1 , . . . , s m ∈ {1, -1}} . Let w be a word of length N X (2nr+1) containing any word of length (2nr+1) of X. If φ, φ ′ ∈ B n (S) are different then φ(w) = φ ′ (w). Then, B n (S) can be injected into the set of words of length N X (2nr + 1) -2r (the injection is just the valuation of φ on w). This implies that ♯B n (S) ≤ p X (N X (2nr + 1) -2r). We deduce from the hypothesis on N X that ♯B n (S) ≤ n d 2 +1 for all large enough integers n ∈ N. Therefore, by the quantitative result of Y. Shalom and T. Tao in [START_REF] Shalom | A finitary version of Gromov's polynomial growth theorem[END_REF] generalizing Gromov's classical result on the growth rate of groups, we get the conclusion.

Notice that the constant C may be given explicitly in the result of [START_REF] Shalom | A finitary version of Gromov's polynomial growth theorem[END_REF]. It is clear that a subshift of polynomial local recurrence complexity has a polynomial complexity. The converse is not clear, but an additional possible condition is that the subshift has bounded repetitions of words. The natural question here is whether the automorphism group of a minimal subshift of polynomial local recurrence complexity, or just polynomial complexity, is finitely generated.

Gallery of examples

We present here examples of subshifts with various complexities. The first two examples are substitutive subshifts with superlinear complexity. Even if we can not apply straightforwardly the main results of the paper (e.g., the substitutions are not primitive), we study their asymptotic components to prove their automorphism groups are isomorphic to Z. Next, we define a coding of a nil-translation with a polynomial complexity of arbitrary high degree but having an automorphism group which is virtually Z. To enlarge the zoology of automorphism groups we provide a subshift whose automorphism group is isomorphic to Z d . We end with a subshift whose complexity is, for infinitely many integers, subaffine and superpolynomial. Theorem 1.1 applies in this case.

4.1. Substitutions with superlinear complexity. Recall that substitutive subshifts have a prescribed complexity: with growth bounded or equivalent to n, n log log n, n log n, or to n 2 (see [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming[END_REF]). Below we give two examples having a unique asymptotic component. This is enough to conclude that their automorphism groups are isomorphic to Z.

4.1.1.

A n log log n complexity substitutive subshift. Let A = {a, b} and consider the substitution τ 1 : A → A * defined by τ 1 (a) = aba and τ 1 (b) = bb.

We set X τ1 = {x ∈ {a, b} Z ; any word of x appears in some τ n 1 (c), n ≥ 0, c ∈ {a, b}}. It can be checked that (X τ1 , σ) is a non minimal transitive subshift. Moreover, it is proven in [START_REF] Cassaigne | Complexité et facteurs spéciaux, Journées Montoises[END_REF] that its complexity is equivalent to n log 2 log 2 n.

In the sequel we need some specific notations. For a sequence x ∈ {a, b} Z we set

x -= • • • x -2 x -1 , x + = x 0 x 1 • • • and x = x -.x + . Let b +∞ = bbbbb . . . ∈ A N and b -∞ = . . . bbbbb ∈ A Z<0
, where Z <0 is the set of negative integers. Thus the sequence x = . . . bb.bb . . . ∈ {a, b} Z can be written b -∞ .b +∞ . In the same spirit we put τ +∞ It is easy to check that the subshift (X τ2 , σ) is transitive but not minimal. Moreover, from [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming[END_REF] its complexity is of the order n 2 . Before showing it has a unique asymptotic component, let us introduce some key concepts for the treatment of this example.

Let x be a sequence of B N , where B is an alphabet. We denote by L(x) the set of words having an occurrence in x. A return word to u ∈ L(x) is a word w ∈ L(x) such that wu belongs to L(x), contains exactly two occurrences of u and has u as a prefix. We denote by R x (u) the set of return words to u.

In [START_REF] Cassaigne | Factor complexity. Combinatorics, automata and number theory[END_REF] is defined the notion of sparse sequence on the alphabet B. It is an element x of B N satisfying:

∃b ∈ A, ∀n ∈ N, b n ∈ L(x) and #R x (b n ) = 2.
It is proven that p x (n) (the number of words of length n appearing in x) is less than or equal to (n 2 + n + 2)/2 whenever x is sparse. In Example 4.7.67 of [START_REF] Cassaigne | Factor complexity. Combinatorics, automata and number theory[END_REF] it is claimed that x = τ +∞ 2 (a) is sparse. Using Lemma 4.5.15 in [START_REF] Cassaigne | Factor complexity. Combinatorics, automata and number theory[END_REF] one can deduce that for all n ≥ 1,

R x (b n ) = {b, b n u}, where τ n 2 (a) = ub n . (5)
We show (X τ2 , σ) has a unique asymptotic component. Let (x, y) be an asymptotic pair. It suffices to prove that x and y end with b +∞ . We can suppose that x = x -.x + 0 ax + and y = y -.y + 0 bx + . We set

x + = x + 2 x + 3 • • • . Suppose that x + 2 = a.
Then the only possibility to have bax + 3 in L(X τ2 ) is x + 3 = a. Consequently, aaa would belong to L(X τ2 ), which is not the case. Therefore,

x + 2 = b and necessarily x - -1 x - 0 = ba: x = • • • x - -1 b.aabx + 3 x + 4 x + 4 • • • y = • • • y - -2 y - -1 .y + 0 bbx + 3 x + 4 x + 5 • • • .
Suppose we are in the following situation:

x = • • • x - -1 b.aab n aax + n+4 • • • y = • • • y - -2 y - -1 .y + 0 bb n aax + n+4 • • • . From (5) one gets that x = • • • x - -1 b.aab n τ n+1 2 (a) • • • y = • • • y - -2 y - -1 .y + 0 bb n τ n+1 2 (a) • • • .
Then, using (5) again, x would have an occurrence of w = τ n 2 (a)τ n 2 (a)τ n 2 (a), but w does not belong to L(X τ2 ). Indeed, if it was the case, by a finite recurrence we prove that aaa should belong to L(X τ2 ), which is not the case. Hence,

x + 3 x + 4 x + 4 • • • = b +∞ and (X τ2 , σ) has a unique asymptotic component.
Observe that (σ -n (τ n 2 (a -∞ )).b +∞ ) converges in X τ2 . Let z denote its limit. We can check that if (x, y) is an asymptotic pair then x and y belong to

{b -∞ .b +∞ , σ i (z); i ∈ Z}.
We finish this section by proving that in both examples (X τ1 , σ) and (X τ2 , σ) the group of automorphisms is isomorphic to Z. Lemma 4.1. Let τ denote either the substitution τ 1 or τ 2 . Then, the group Aut(X τ , σ) is generated by the shift map σ.

Observe that the main result of [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF] gives only that the group Aut(X τ1 , σ) is a periodic group.

Proof. Let us first recall that for any asymptotic pair (x, y) of (X τ , σ), x and y belong to

{b -∞ .b +∞ , σ i (z); i ∈ Z}, for some z ∈ X τ .
Notice that (X τ , σ) has a unique minimal subsystem, namely ({b -∞ .b +∞ }, σ). Moreover, it is clear that an automorphism φ of the subshift (X τ , σ) maps any minimal subsystem onto a minimal subsystem, so φ fixes the sequence b -∞ .b +∞ . The morphism φ mapping asymptotic pairs onto asymptotic pairs, σ i (z) should be mapped to some σ j (z). The orbit {σ k (z); k ∈ Z} being dense in X τ one deduces that φ • σ i = σ j . Thus, φ is a power of the shift map.

4.2.

Coding a nil-translation. We introduce a class of examples of symbolic systems with polynomial complexity of arbitrarily high degree and with a group of automorphisms which is virtually Z. We build these systems as symbolic extensions of minimal nilsystems.

We start by stating some general results we need and then review some generalities about the coded systems.

Let (X, T ) be a minimal topological dynamical system and let U = {U 1 , . . . , U m } be a finite collection of subsets of X. We say that U covers X if m i=1 U i = X. For two covers U = {U 1 , . . . , U m } and V = {V 1 , . . . , V p } of X we let U ∨ V denote the cover given by {U i ∩ V j ; i = 1, . . . m, j = 1, . . . p}.

Let U = {U 1 , . . . , U m } be a finite cover of X and let A denote the set {1, . . . , m}. We say that ω = (w

i ) i∈Z ∈ A Z is a U-name of x if x ∈ i∈Z T -i U wi . Let X U denote the set {ω ∈ A Z ; i∈Z T -i U wi = ∅} ⊆ A Z .
It is easy to check that X U is closed when each U i is closed and if we let U denote the collection {U 1 , . . . , U m } we have that X U ⊂ X U . For N ∈ N, let

U N = N i=-N T -i U.
We say that the cover U separates points if every ω ∈ X U is a name of exactly one x ∈ X. If U separates points in X, we can build a factor map π between (X U , σ) and (X, T ) where π(ω) is defined as the unique point in i∈Z T -i U wi . Lemma 4.2. Let (X, T ) be a minimal topological dynamical system and let U = {U 1 , . . . , U m } be a partition which covers and separates points in X. Let suppose that for every N ∈ N every atom of U N has non-empty interior, then (X U , σ) is a minimal system. Proof. Let ω, ω ′ ∈ X U and let N ∈ N. We denote x = π(ω) and x ′ = π(ω ′ ). By definition we have that N -N T -i U wi = ∅ and therefore it has non-empty interior. Since (X, T ) is minimal, there exists n ∈ Z such that T n x ′ ∈ int( N -N T -i U wi ). This implies that w ′

[n-N,n+N ] = w [-N,N ] and the proof is finished. Now we compute the automorphism groups of symbolic extensions of some nilsystems. First we recall the construction of the systems studied in [START_REF] Arnoux | Complexité de suites engendrées par des récurrences unipotentes[END_REF]. Let us consider the infinite matrix A = (a i,j ) i,j∈N where a i,j

= j i A =         1 1 1 1 1 • • • 1 2 3 4 • • • 1 3 6 • • • 1 4 • • • 1 • • • • • • • • •         .
It is proven in Section 4 of [START_REF] Arnoux | Complexité de suites engendrées par des récurrences unipotentes[END_REF] that for all i ∈ N, A i is well defined and

A i =         1 i i 2 i 3 i 4 • • • 1 2i 3i 2 4i 3 • • • 1 3i 6i 2 • • • 1 4i • • • 1 • • • • • • • • •         .
Let α ∈ [0, 1] be an irrational number. For any d ∈ N, consider A d+1 the restriction of A to (d + 1) × (d + 1) coordinates. We let T d : T d → T d denote the application that maps (x 0 , . . . x d ) to the d first coordinates of A d+1 (x 0 , . . . , x d , α) t . For example, T 2 is the application (x 0 , x 1 ) → (x 0 + x 1 + α, x 1 + 2α) and T 3 is the application (x 0 , x 1 , x 2 ) → (x 0 + x 1 + x 2 + α, x 1 + 2x 2 + 3α, x 2 + 3α).

We can represent the transformation T d as T d (x) = A d x + α where α is the restriction to the first d-coordinates of the last column of A d+1 multiplied by α. This is the classical presentation of an affine nilsystem.

Fix d ∈ N and for i, n ∈ Z let H i,n be the plane given by the equation

d-1 k=0 i k x k + i d α = n. It can be proven that H i,n = T -i
d H 0,n and for a fixed value of i, the planes H i,n are projected in T d to the same plane H i . We remark that

H 0 = {(0, x 1 , . . . , x d-1 ); (x 1 , . . . , x d-1 ) ∈ T d-1 }.
We refer to Section 4 of [START_REF] Arnoux | Complexité de suites engendrées par des récurrences unipotentes[END_REF] for further details.

We consider the partition U given by the cells generated by the planes H 0 , . . . , H d-1 . The partition n+d-1 i=0

T -i d U coincides with the cells generated by the planes H 0 , . . . , H n+d-1 (see Section 6 of [START_REF] Arnoux | Complexité de suites engendrées par des récurrences unipotentes[END_REF]). Let (x 0 , . . . , x d-1 ) and (y 0 , . . . , y d-1 ) be different points in T d and let k = max{k; x k = y k }. Then the difference (in R) between d-1 k=0 i k x k + i d α and d-1 k=0 i k y k + i d α grows to infinity as i goes to infinity since this difference behaves like i k (x ky k ). This implies that for big enough N , (x 0 , . . . , x d-1 ) and (y 0 , . . . , y d-1 ) lie on different cells of N i=-N T -i d U since for big enough i these points are separated by the cells generated by H i .

We recall that (X U , σ) is the subshift associated to U. By Lemma 4.2, one can see that (X U , σ) is a minimal system and it is an extension of (T d , T d ) since U separates points. Moreover, the complexity function of (X U , σ) is given by

p(n) = 1 V (0, 1, . . . , d -1) 0≤k1<k2<•••<k d ≤n+d-1 V (k 1 , k 2 , • • • , k d ) where V (k 1 , k 2 , • • • , k d ) = 1≤i<j≤d (k j -k i ) is a Vandermonde determinant.
We remark that varying d ∈ N we get an arbitrarily large complexity with a polynomial growth.

By construction and Corollary 2.8 we also get:

Lemma 4.3. The maximal d-step nilfactor of (X U , σ) is the nilsystem (T d , T d ).

Proposition 4.4. The group Aut(X U , σ) is virtually Z.

Proof. Let φ be an automorphism of (X U , σ) and let π : X U → T d be the natural factor map. Let W = {ω ∈ X; #π -1 {π(ω)} ≥ 2} be the set of points where π is not one-to-one. Since φ preserves the regionally proximal pairs of order d, we have that W is invariant under φ. We remark that the projection of W under π are the points which fall in

F := H 0 ∪ H 1 ∪ • • • ∪ H d-1
under some power of T , which is nothing but j∈Z T j F = j∈Z T j H 0 . We have that the projection π(φ) is an automorphism that commutes with the affine ergodic transformation T which has eigenvalues equal to 1. By Theorem 2 and Corollary 1 in [START_REF] Walters | Topological conjugacy of affine transformations of tori[END_REF] we have that π(φ) has the form (x 0 , . . . , x d-1 ) t → B(x 0 , . . . , x d-1 ) t + β where B is an integer matrix and β ∈ T d . Since W is invariant under φ we get that the projection π(φ) leaves invariant j∈Z T j H 0 . Particularly, since H 0 is the restriction of a plane to T d , so is its image under π(φ) and therefore there exists j ∈ Z such that π(φ) H 0 = T j H 0 . Hence, the automorphism T -j π(φ) leaves invariant H 0 . So we are left to study the automorphisms of (T, T d ) which leave invariant H 0 . Let ϕ be such an automorphism. By [START_REF] Walters | Topological conjugacy of affine transformations of tori[END_REF] we can assume that ϕ has the form

ϕ      x 0 x 1 . . . x d-1      = B      x 0 x 1 . . . x d-1      +      β 0 β 1 . . . β d-1     
where the matrix B = (b j,k ) j,k=1...,d has integer entries and β = (β 0 , . . . , β d-1 ) t ∈ T d . Since ϕ commutes with T we have that B commutes with A d (as real matrices) and (B -

Id) α = (A d -Id) β in T d . Since ϕ(0, x 1 , . . . , x d-1 ) ∈ H 0 , for any (x 1 , . . . , x d-1 ) ∈ T d-1 we deduce that b 1,2 = • • • = b 1,d = 0 = β 0 . Since A i d B = BA i d for any i ∈ N
, by looking at the first row of these matrices we deduce that for any j = 1, . . . , d and any

i ∈ N d k=1,k =j (b j,k )i k-1 + (b j,j -b 1,1 )i j-1 = 0.
Since the vectors (1, i, i 2 , . . . , i d-1 ) are linearly independent for different values of i we deduce that B

= b 1,1 I d . Therefore, (A d -Id)β = (B -Id) α = (b 1,1 -1) α.
Since A d is upper triangular with ones in the diagonal, this condition implies that (b 1,1 -1)α ∈ Q and thus b 1,1 = 1. We conclude that B is the identity matrix and then ϕ is the rotation by β := (0, β 1 , . . . , β d-1 ) t and (A d -Id) β ∈ Z d . We can write this system as

        0 1 1 1 1 • • • 0 2 3 4 • • • 0 3 6 • • • 0 4 • • • 0 d • • • 0                0 β 1 β 1 . . . β d-1        ∈ Z.
This implies that dβ d-1 ∈ Z and this is possible for finitely many β d-1 ∈ T. Inductively, we deduce that there are finitely many (and rational) solutions β = (0, β 1 , . . . , β d-1 ) t in T d . This means that the group of automorphisms that leaves invariant H 0 is a finite group of rational rotations. Therefore, π(Aut(X U , σ)) is spanned by T d and a finite group. Since the map π : Aut(X U , σ) → Aut(T, T d ) is an injection we have that Aut(X U , σ) is spanned by σ and a finite group. The result follows.

4.3.

Example of a larger automorphism group. We remark that the statement of Theorem 1.1 is no longer valid for an arbitrary polynomial complexity, as the following shows. Proposition 4.5. For any d ∈ N, there exists a minimal subshift (X, σ) with complexity satisfying lim n→+∞ p X (n)/n d+1 = 0 and where Aut(X, σ) is isomorphic to Z d . Proof. Let α 1 , . . . , α d ∈ R \ Q be rationally independent numbers. For every i = 1, . . . , d, let (X i , σ i ) be the Sturmian extension of the rotation R αi by the angle α i on the circle S 1 , and let X

= X 1 × X 2 • • • × X d and σ = σ 1 × σ 2 • • • × σ d .
We remark that for any i = 1, . . . , d, on (X i , σ i ) the proximal relation and the regionally proximal relation coincide and thus the proximal relation is an equivalence relation. Since the maximal equicontinuous factor of (X i , σ i ) is (S 1 , R αi ) via the factor map π i , by [START_REF] Auslander | Minimal flows and their extensions[END_REF], Chapter 11, theorems 7 and 9, we have that (X, σ) is a minimal system and the product system ((S

1 ) d , R α1 × • • • × R α d ) is its maximal equicontinuous factor.
The complexity function of any (X i , σ i ) is n + 1, so we get that the complexity function of (X, σ) is (n+1) d . On the other hand, we observe that φ 1 ו • •×φ d belongs to Aut(X, σ) for any choice of φ i ∈ Aut(X i , σ i ). Since for every i, Aut(X i , σ i ) is Z, we conclude that Z d can be embedded as a subgroup of Aut(X, σ).

We claim this embedding is actually an isomorphism. To prove this, recall that the Sturmian subshift X i is an almost one-to-one extension of a rotation on the circle via an onto map π i : X i → S 1 that it is injective except on the orbit of the unit Orb Rα i (1), where any point has two pre-images (e.g., see [START_REF] Durand | Linearly recurrent subshifts have a finite number of nonperiodic factors[END_REF]). By Lemma 2.12, for any automorphism φ ∈ Aut(X, σ), the automorphism π(φ) preserves the set of points in (S 1 ) d having a maximum number (namely 2 d ) of pre-images for the factor map π

= π 1 ו • •×π d . This set is the product set Orb Rα 1 (1)ו • •×Orb Rα d (1).
Clearly, the group of automorphisms of the form π

(σ n1 1 × • • • × σ n d d )
, n 1 , . . . , n d ∈ Z, acts transitively on this set. Since the group Aut((S 1 ) d , R α1 × • • • × R α d ) acts freely and the morphism π is injective (Lemma 2.6), we get that any automorphism φ ∈ Aut(X, σ) may be written as a product of automorphisms in Aut(X i , σ i ).

4.4. Subshift with subexponential complexity. In this section we give an example of a minimal subshift (X, σ) generated by a uniformly recurrent sequence x ∈ {0, 1} Z such that:

• There exists C such that for infinitely many n's one has p X (n) ≤ Cn.

• For any subexponential function φ there are infinitely many n's such that p X (n) ≥ φ(n), where subexponential means that lim n→+∞ φ(n)/α n = 0 for all α ∈ R. As for subshifts p z (n) will stand for the number of words of length n occurring in the sequence z ∈ {0, 1} Z or z ∈ {0, 1} N .

The proofs of the two following lemmas are left to the reader.

Lemma 4.6. Let ξ be a substitution on {0, 1} * of constant length L and τ be an endomorphism of {0, 1} * having all words of length 2 in its images. Let x ∈ {0, 1} N . Then, for any y ∈ {0, 1} N having occurrences of all words of length 2 and 0 ≤ l ≤ L we have

p ξ•τ (x) (l) = p ξ(y) (l).
Below ρ stands for the Morse substitution: ρ(0) = 01 and ρ(1) = 10.

Lemma 4.7. Let ξ be a substitution on {0, 1} * of constant length L. Let x ∈ {0, 1} N . We have

p ξ•ρ 3 (x) (2L) ≤ 6L.
Below, when a substitution τ is of constant length L we set |τ | = L. Let us construct inductively the sequence x. In fact, we will construct two increasing sequences of integers (a i ) i≥1 and (b i ) i≥1 , and a sequence of morphisms (τ i ) i≥1 such that (1) x = lim i→∞ ρ 3 τ 1 . . . ρ 3 τ i (0 ∞ ), where 0

∞ = 00 • • • , (2) a 1 < b 1 < a 2 < b 2 < . . ., (3)
p x (a i ) ≤ 3a i , i ∈ N and (4) p x (b i ) ≥ φ(b i ), i ∈ N. We start fixing a 1 = 2. Let x (1) = ρ 3 (0 ∞ ). Then, p x (1) (a 1 ) = 4, which is less than 3a 1 .

Let k 1 be such that 2 k1 ≥ φ(k 1 |ρ 3 |) (observe it is always possible because φ has a subexponential growth) and τ 1 be a substitution of {0, 1} * of length L 1 = 2 m1 such that τ 1 (0) starts with 0 and the number of words of length k 1 in τ 1 (0) and τ 1 (1) is 2 k1 . We set Let k 2 ≥ k 1 be such that 2 k2 ≥ φ(k 2 |ρ 3 τ 1 ρ 3 |) and τ 2 be a substitution of {0, 1} * of length L 2 = 2 m2 such that the number of words of length k 2 in τ 2 (0) and τ 2 (1) is 2 k2 . We set 5.2. Eigenvalues, roots of T and automorphisms. We obtain, in the good cases, that the group of automorphisms is a subgroup of the corresponding one of a maximal nilfactor. This proves that there are connections between automorphisms and continuous eigenvalues. To study these relations we can focus on rational eigenvalues. So it is natural to ask: does a Cantor minimal system (X, T ) admit a non trivial automorphism with finite order or have some roots, are there constraints on the rational continuous eigenvalues of (X, T ) ?

Classical examples of Toeplitz sequences with a unique asymptotic component (so Aut(X, σ) is generated by σ) show that the converse is false: a system may have rational eigenvalues and no automorphisms of finite order. 5.3. Complexity versus group of automorphisms. The results of [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF] and of this paper show a relation between complexity and the growth rate of the groups. Is it possible to be more precise ? For instance, is it true that for a transitive subshift with a subquadratic complexity the group Aut(X, σ)/ σ is finite ? The result in [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF] states it is periodic, but we do not know any subshift with this complexity and with an infinite group Aut(X, σ)/ σ (see Section 4.1.2). Inspired by the main theorem of this paper and examples in Section 4.3 we ask, Question. Let (X, σ) be a minimal subshift such that d = inf{δ ∈ N; 0 < lim inf p X (n)/n δ < +∞} > 0.

Is it true that it is virtually Z d ? Can we extend these results to the category of transitive subshifts ? 5.4. Measurable versus continuous automorphisms. The main result in [START_REF] Host | Homomorphismes entre systèmes dynamiques définies par substitutions[END_REF] shows a rigidity result, any measurable automorphism is almost everywhere continuous for bijective constant length substitutions. Is it possible to enlarge this class of subshifts with the same rigidity property ? A first answer is negative: This is not true for substitution of non-constant length and even for Pisot substitution on the alphabet {0, 1}. Consider the two substitutions τ and ξ defined by τ (0) = 010, τ (1) = 01, ξ(0) = 001 and ξ(1) = 10. Let (X τ , σ) and (X ξ , σ) be the subshift they generate. It can be shown that they are both measure theoretically isomorphic to (S 1 , R α ) (see [START_REF] Barge | Coincidence for substitutions of Pisot type[END_REF]), where R α is the rotation of angle α = (1 + √ 5)/2, and, thus (X τ , σ) and (X ξ , σ) are measure theoretically isomorphic. But they cannot be topologically isomorphic because their dimension groups are not isomorphic (see [START_REF] Durand | Contributions à l'étude des suites et systèmes dynamiques substitutifs[END_REF] for their computations). 5.5. Realization of automorphism groups. By the Curtis-Hedlund-Lyndon theorem, the collection of automorphisms of a subshift is countable. We leave open the realization of any countable group as an automorphism group. More precisely, Question. Given a countable group G (not necessarily finitely generated). Does it exist a minimal subshift (X, σ) such that Aut(X, σ)/ σ is isomorphic to G ? Notice that Toeplitz sequences can also be realized on residually finite groups [START_REF] Cortez | G-odometers and their almost one-to-one extensions[END_REF]. A priori, they may provide interesting solutions in this class. But, as stated in the remark below Corollary 2.13, their automorphism group is Abelian. This kills any non commutative group realization by this way.

A second question that was left open in the text is when the automorphism group of polynomial complexity subshifts is finitely generated. Again, the intuition is based on the fact that asymptotic classes in such systems are few, and prevent the growth of the automorphism group.

If we restrict to some families of subshifts (e.g. Sturmian or Toeplitz sub shifts), we prove that their automorphism groups are subgroups of their maximal equicontinuous factors. Can we characterize these groups for the Sturmian and Toeplitz cases ? 5.6. Extension to higher dimensional subshifts. A natural question is to study the generalization to Z d -subshifts with d ≥ 1, or to the geometrical notion of tilings and Delone sets of R d . More intrinsically, the method used in [START_REF] Cyr | The automorphism group of a shift of subquadratic growth[END_REF] illustrates how properties on complexity of multidimensional subshifts give information on one dimensional subshifts. Unfortunately, this uses results related to the famous Nivat's conjecture, that are known to be true only in dimension two. Nevertheless, we can hope a similar strategy may provide interesting information on multidimensional subshifts. We believe that the study of asymptotic components or the similar notion of non-expansive directions in higher dimensions may also provide useful results. For instance in [START_REF] Donoso | Dynamical cubes and a criteria for systems having products extensions[END_REF], such a way leads to prove that the automorphism group of the minimal component of the Robinson subshift of finite type is trivial.

  we can generalize previous results. Theorem 2.10. Let (G/Γ, τ ) be a minimal d-step nilsystem. Then Aut(G/Γ, τ ) is a d-step nilpotent group.

1 ( 1 (

 11 c) for lim n→+∞ τ n 1 (cc . . .), when it exists in {a, b} N , and, τ -∞ c) for lim n→+∞ τ n 1 (• • • cc), when it exists in {a, b} Z<0 . Let us ckeck (X τ1 , σ) has a unique asymptotic component. We show that asymptotic points should end with b +∞ . 4.1.2. A n 2 complexity substitutive subshift. Below we use the notation of the previous section. Consider the substitution τ 2 : A → A * defined by τ 2 (a) = aab and τ 2 (b) = b.

b 1 = k 1 |ρ 3 |

 3 and y(1) = ρ 3 τ 1 (0 ∞ ). One gets p y (1) (b 1 ) ≥ φ(b 1 ). Moreover, notice that from Lemma 4.6 one has thatp y (1) (l) = p x (1) (l) for all l ≤ |ρ 3 |. Now consider x (2) = ρ 3 τ 1 ρ 3 (0 ∞ ). Then from Lemma 4.7 p(2|ρ 3 τ 1 |) ≤ 6|ρ 3 τ 1 |. Setting a 2 = 2|ρ 3 τ 1 |, one gets p x (2) (a 2 ) ≤ 3a 2 .

SEBASTI ÁN DONOSO, FABIEN DURAND, ALEJANDRO MAASS, AND SAMUEL PETITE

SEBASTI ÁN DONOSO, FABIEN DURAND, ALEJANDRO MAASS, AND SAMUEL PETITE

This research was partially supported by grants Basal-CMM & Fondap 15090007, CONICYT Doctoral fellowship 21110300, ANR SubTile and the cooperation project MathAmSud DYSTIL. The first and third authors thanks University of Picardie Jules Verne where this research was finished.

Let (x, y) be an asymptotic pair. We can suppose, shifting if needed, that

Observe that x + 0 = b because aa does not belong to L(X τ1 ):

Then, we should have x + 2 x + 3 = bb because aba is necessarily followed by bb. Thus, bbabb should appear in some element of x which is not the case. Therefore x + 1 = b:

Suppose x + begins with b 2n+1 a for some n ≥ 1. Then, abab 2n+1 aba should belong to the language of X τ1 . But it should appear in some τ 1 (u) and then we must have abab 2n+1 aba = τ 1 (ava) for some word v ∈ L(X τ1 ), hence b 2n+1 = τ 1 (v), which is not possible. Thus, x + begins with b 2n a for some n ≥ 1 or it is equal to b +∞ . Suppose we are in the first situation:

It can be checked that τ 1 is one-to-one on X τ1 . Consequently, there are two unique sequences

Thus, (x (1) , y (1) ) is also an asymptotic pair. From the observation made before, n should be even and we can obtain a new asymptotic pair (x (2) , y (2) ) having the shape given by (4). Of course n is decreasing at each step and we can continue until n = 1: we get an asymptotic pair (x (k) , y (k) ) such that

But ababa does not belong to L(X τ1 ). Consequently x + = b +∞ and (X τ1 , σ) has a unique asymptotic component. Furthermore, it can be checked, using already used arguments, that z

b n for some non-negative integer n. Hence, if (x, y) is an asymptotic pair then x and y belong to

One gets that p y (2) (b 2 ) is greater than φ(b 2 ). Moreover, notice that from Lemma 4.6 one has that

) and p y (2) (a 2 ) ≤ 3a 2 . Now suppose we have constructed:

(1) morphisms τ i of constant length such that τ i (0) starts with 0, 1

We have seen this construction is realizable for n = 2. Proceeding as we did for the first cases, it is not difficult to see that it can be achieved for every n ≥ 1.

To conclude, it suffices to observe that (y (n) ) n≥1 converges to the sequence x we are looking for. Indeed, the convergence follows from (4c) and (4d). Also observe that y (n) is a prefix of x. It is a classical exercise to show that x is uniformly recurrent. From (4g) we get that p x (b i ) ≥ φ(b i ) for all i ∈ N. For the last point, p x (a i ) ≤ 3a i for all i ∈ N, it comes from (4f) because it is true for all n ≥ 1.

Comments and open questions

A standard question related to automorphisms is to determine if the transformation T has a root. That is, does it exist a transformation U such that U p = T for some integer p ≥ 0. A classical way to deal with this problem is to notice that a root is an automorphism.

The automorphism group is also related to the collection of conjugacy maps between two systems. If π 1 and π 2 are two conjugacy maps between the same systems, then π 1 • π -1

2 is an automorphism. Hence, a characterization of when the automorphism group is trivial, i.e. Aut(X, T ) is generated by T , implies rigidity results in both problems. 5.1. Automorphisms and nilfactors. We have shown that a large family of minimal subshifts, either with sublinear or other type of polynomial complexity, have automorphisms groups that are virtually Z. Even in the case of minimal subshifts obtained as extensions of minimal systems whose automorphism group is much complex (the case of extensions of nilsystems). So a natural question is whether this behaviour is generally true just because the fibres over particular topological factors are constrained.