Tero Harju
email: harju@utu.fi

Mari Huova
email: mahuov@utu.fi

Luca Q Zamboni

On Generating Binary Words Palindromically

Keywords: Palindromes, Sturmian words, balanced words. 2000 MSC: 68R15

We regard a finite word u = u 1 u 2 • • • u n up to word isomorphism as an equivalence relation on {1, 2, . . . , n} where i is equivalent to j if and only if u i = u j . Some finite words (in particular all binary words) are generated by palindromic relations of the form k ∼ j +i-k for some choice of 1 ≤ i ≤ j ≤ n and k ∈ {i, i + 1, . . . , j}. That is to say, some finite words u are uniquely determined up to word isomorphism by the position and length of some of its palindromic factors. In this paper we study the function µ(u) defined as the least number of palindromic relations required to generate u. We show that if x is an infinite word such that µ(u) ≤ 2 for each factor u of x, then x is ultimately periodic. On the other hand we establish the existence of non-ultimately periodic words for which µ(u) ≤ 3 for each factor u of x, and obtain a complete classification of such words on a binary alphabet (which includes the well known class of Sturmian words). In contrast, for the Thue-Morse word, we show that the function µ is unbounded.

Introduction

Palindromes play an important role in various areas of mathematics including diophantine approximation and number theory (see for instance [START_REF] Adamczewski | On complexity of algebraic numbers, II. Continued fractions[END_REF][START_REF] Col | Palindromes dans les progressions arithmétiques (French)[END_REF]), discrete math (see for instance [START_REF] Glen | Palindromic richness[END_REF][START_REF] Brlek | On the palindromic complexity of infinite words[END_REF]), algebra (see for instance [START_REF] Kassel | A palindromization map for the free group[END_REF][START_REF] Deloup | Palindromes and orderings in Artin groups[END_REF]), biomathematics (see for instance [START_REF] Kari | Watson-Crick palindromes in DNA computing[END_REF]), geometric symmetry in translation surfaces associated with various dynamical systems including interval exchange transformations (see for instance [START_REF] Ferenczi | Eigenvalues and simplicity of interval exchange transformations[END_REF]) and theoretical physics in the spectral properties of discrete Schrödinger operators defined on quasicrystals (see for instance [START_REF] Hof | Singular continuous spectrum for palindromic Schrödinger operators[END_REF]).

Let A be a finite non-empty set of letters. For each positive integer n, let

S(n) = {(i, j) | 1 ≤ i ≤ j ≤ n}. Let u = u 1 u 2 • • • u n ∈ A n
be a word of length n with values in A.

Let Alph(u) = {u i | 1 ≤ i ≤ n} denote the subset of A consisting of all letters occurring in u. For each pair (i, j) ∈ S(n), we denote by u[i, j] the factor u i u i+1 • • • u j . In case i = j, we write u[i] in lieu of u [i, i]. Finally, let P denote the collection of all palindromes. Definition 1. Let u ∈ A n and S ⊆ S(n). We say that S palindromically generates u if the following three conditions are verified:

• u[i, j] ∈ P for all (i, j) ∈ S,

• for all k ∈ {1, 2, . . . , n}, there exists (i, j) ∈ S with i ≤ k ≤ j,

• for each non-empty set B and word v ∈ B n , if v[i, j] ∈ P for all (i, j) ∈ S then there exists a mapping c : Alph(u) → B which extends to a morphism c : Alph(u) * → B * of words such that c(u) = v.

We call the elements of S generators (or palindromic generators). It follows from the definition that if a set S ⊆ S(n) palindromically generates two words u ∈ A n and v ∈ B n of length n, then u and v are word isomorphic, i.e., there is a bijection ν : Alph(u) → Alph(v) which extends to a morphism of words such that ν(u) = v. In particular, the last condition in Definition 1 states that Alph(u) has the largest cardinality such that the first two conditions are satisfied.

Example 2. For each letter a ∈ A, the singleton set S = {(1, 1)} palindromically generates a. The set S = {(1, 2)} palindromically generates the word a 2 = aa, while S = {(1, 1), (2, 2)} palindromically generates the word ab. For n ≥ 3, the set S = {(1, n -1), (1, n)} as well as S = {(1, n), (2, n)} palindromically generate a n .

Given a word u ∈ A n , let µ(u) denote the infimum of the cardinality of all sets S ⊆ S(n) that palindromically generate u, i.e., µ(u) = inf{Card S | S ⊆ S(|u|) palindromically generates u}.

As usual, we let inf(∅) = +∞. It is easily checked that, for instance, µ(a n ) = 1 for n = 1, 2 and µ(a n ) = 2 for n ≥ 3. Also µ(u) < +∞ whenever u ∈ A * is a nonempty word and Card A = 2, i.e., whenever u is a binary word. Indeed, it is readily verified that for each nonempty word u ∈ {0, 1} * , the set [START_REF] Berstel | Sturmian and Episturmian Words (A Survey of Some Recent Results)[END_REF][START_REF] Brlek | On the palindromic complexity of infinite words[END_REF], [START_REF] Berstel | Sturmian words, Lyndon words and trees[END_REF][START_REF] Carpi | Codes of central Sturmian words[END_REF], (4, 7), [START_REF] Deloup | Palindromes and orderings in Artin groups[END_REF][START_REF] De Luca | Sturmian words: structure, combinatorics, and their arithmetics[END_REF]} palindromically generates u. In this example, also [START_REF] Carpi | Codes of central Sturmian words[END_REF][START_REF] Col | Palindromes dans les progressions arithmétiques (French)[END_REF] is in S u , but it is not needed in the generating set. The set S is the smallest palindromic generating set whence µ(00101100) = 5. In contrast, for the ternary word abca no subset S of S(4) palindromically generates abca. For this reason, we shall primarily restrict ourselves to binary words.

S u = {(i, j) | u[i, j] = ab k a for {a, b} = {0, 1}, k ≥ 0} palindromically generates u. Typically µ(u) < Card S u , e.g., if u = 00101100, then the set S = {(1, 2),
Given an infinite word x ∈ A N , we are interested in the quantity

ψ(x) = sup{µ(u) | u is a factor of x}.
We begin by showing that if x ∈ A N is aperiodic (i.e., not ultimately periodic), then ψ(x) ≥ 3. This is stated in Proposition 10. We will also prove that ψ(T) = +∞ for the Thue-Morse infinite word T defined as follows. Let T = 01101001100101101001 . . . denote the Thue-Morse infinite word defined as the fixed point beginning in 0 of the morphism τ : {0, 1} * → {0, 1} * given by τ (0) = 01 and τ (1) = 10. Indeed, in Proposition 11 we will show that for each integer n > 0 there exists a factor u of T with µ(u) ≥ n.

The main result of this paper is to establish the existence of aperiodic binary words x for which ψ(x) = 3 and in fact to obtain a complete classification of such words. Recall that an infinite binary word x ∈ {0, 1} N is called Sturmian if x contains exactly n + 1 factors of each given length n ≥ 1. As is well known, each Sturmian word x is aperiodic and uniformly recurrent, i.e, each factor of x occurs in x with bounded gap. In order to state our main result we will make use of the following morphisms: For each subset A ⊆ {0, 1}, we denote by d A : {0, 1} * → {0, 1} * the doubling morphism defined by the rule

d A (a) = { aa if a ∈ A a if a / ∈ A. Definition 3. A word y ∈ {0, 1} N is called double Sturmian if y is a suffix of d A (x)

Preliminaries

Throughout this section A will denote a finite non-empty set. We denote by A + the set of all words (or finite sequences) of the form w = a 1 a 2 • • • a n with a i ∈ A. We write |w| = n for the length of w. We denote the empty word by ε and set

A * = A + ∪ {ε}. Given w, u, v ∈ A + with w = uv, we write v = u -1 w and u = wv -1 . For w = a 1 a 2 • • • a n ∈ A n
we denote by w R the reversal (or mirror image) a n • • • a 2 a 1 . A word w is a palindrome if w = w R . Let P denote the set of all palindromes (over any alphabet).

Given two non-empty words u and v, we say u is a border of v if u is both a proper prefix and a proper suffix of v. If v has no borders then it is said to be unbordered.

A word u ∈ A + is said to be overlap-free if it has no factors of the form vzvzv where v and z are nonempty words.

An infinite word ω ∈ A N is aperiodic if it is not of the form ω = uv N = uvv • • • for some words u, v ∈ A * with v ̸ = ε. The following result was shown by Saari in [START_REF] Saari | Lyndon words and Fibonacci numbers[END_REF]. It improves an earlier result of Ehrenfeucht and Silberger in [START_REF] Ehrenfeucht | Periodicity and unbordered segments of words[END_REF]. We shall give a simplified proof of this result. Lemma 6. Each aperiodic infinite word ω contains an infinite number of Lyndon words. In particular ω has arbitrarily long unbordered factors.

Proof. Let ≼ be a lexicographic ordering of words, and suppose to the contrary that ω contains only finitely many Lyndon factors. We write ω = u 1 u 2 • • • where for each i ≥ 2 we have that u i is the longest Lyndon word that is a prefix of the suffix (u

1 • • • u i-1 ) -1 w.
Then, for all i, we have u i+1 ≼ u i since otherwise u i u i+1 would be a Lyndon prefix longer than u i . Thus there exists a positive integer j such that w = u 1 • • • u j-1 u ω j , contradicting that ω is aperiodic.

The last claim now follows from the well known fact that every Lyndon word is unbordered. Indeed, if u = vuv is a Lyndon word with respect to the order ≼, then vvu ≼ vuv (since vu ≼ uv), and hence v is the empty word.

For each pair I = (i, j) ∈ S(n), we define a function ρ I : {i, i + 1, . . . , j} → {i, i + 1, . . . , j} called a reflection by ρ I (k) = i + j -k. The function ρ I is an involution, i.e., it is a permutation that satisfies ρ I (ρ

I (k)) = k for all i ≤ k ≤ j. For u ∈ A n we have that u[i, j] ∈ P if and only if u[k] = u[ρ I (k)] for each i ≤ k ≤ j. If J = (i ′ , j ′ ) with i ≤ i ′ ≤ j ′ ≤ j,
we denote by ρ I (J) the reflected pair (ρ I (j ′ ), ρ I (i ′ )). The following lemma gives essentially a reformulation of Definition 1: Lemma 7. Let u ∈ A n be such that all letters of A occur in u. Let S ⊆ S(n). The following conditions are equivalent: (i) S palindromically generates u.

(ii) for each k ∈ {1, 2, . . . , n}, there exists an (i, j) ∈ S such that i ≤ k ≤ j, and for each

1 ≤ i, j ≤ n, we have u[i] = u[j] if and only if
there exists a finite sequence (or path)

(I t ) r t=1 ∈ S r (⋆) such that j = ρ Ir ρ I r-1 • • • ρ I 1 (i).
Proof. We first define relation θ as follows. Let iθj if and only if there exists an I ∈ S such that j = ρ I (i). Denote by θ * the reflexive and transitive closure of θ. The relation θ is symmetric by the definition of the mappings ρ I and thus θ * is an equivalence relation.

Here iθ * j if and only if (⋆) holds for some sequence (I t ) r t=1 of elements from S. Let then v ∈ B n be any word such that the factor v[i, j] is a palindrome for each (i, j) ∈ S. Now,

iθj implies v[i] = v[j]. Consequently, iθ * j implies u[i] = u[j]
by transitivity. It follows that the cardinality of B is at most the number of equivalence classes of θ * .

If S palindromically generates the given word u, then, by the last condition of Definition 1, each equivalence class of θ * corresponds to a different letter in A. Therefore u[i] = u[j] if and only if iθ * j. This proves the claim from (i) to (ii).

Suppose then that S satisfies (ii). First, let I = (i, j) ∈ S, and

let i ≤ k ≤ j. Denote k ′ = ρ I (i). By (ii), we have that u[k] = u[k ′ ],
and therefore u[i, j] ∈ P. Hence the first condition of Definition 1 holds. The second condition is part of (ii). For the third condition, by the beginning of the proof, any word v ∈ B n for which v[i, j] is a palindrome for each (i, j) ∈ S, the cardinality of B is at most the cardinality of A. By (ii), we have that v

[i] = v[j] implies u[i] = u[j] which proves the claim.
Definition 8. Suppose S ⊆ S(n) palindromically generates a word u ∈ A n , and let m ∈ {1, 2, . . . , n}. We say m is a leaf with respect to S if there exists at most one pair

I = (i, j) ∈ S for which i ≤ m ≤ j and ρ I (m) ̸ = m. Lemma 9. Let u ∈ A + . Then µ(v) ≤ µ(u) for all factors v of u.
Proof. The result is clear in case µ(u) = +∞. So suppose S ⊆ S(|u|) palindromically generates u and set k = Card S. It suffices to show that if u = ax = yb for some words x and y and letters a, b ∈ A, then max{µ(x), µ(y)} ≤ k. We prove only that µ(x) ≤ k as the proof that µ(y) ≤ k is completely symmetric.

Suppose S = {I 1 , I 2 , . . . , I k } palindromically generates u and let m ∈ N be the largest integer such that It follows that S ′ also palindromically generates u and I is the only generator in S ′ containing the initial position 1. Whence 1 is a leaf w.r.t. S ′ , and hence

I = (1, m) ∈ S. Let D = {r ∈ {1, 2, . . . , k} | I r = (1, q) with q < m}. Let S ′ = S ∪ {I ′ r | r ∈ D} \ {I r | r ∈ D} where for each r ∈ D we set I ′ r = ρ I (I r ) = (m -q + 1, m); see Fig. 1. £ I r £ I ′ r ¢ ¡ I • • • w
S ′′ = S ′ ∪ {(2, m -1)} \ {I}
palindromically generates the suffix x = a -1 u. This proves the claim.

Proposition 10. If x ∈ A N is aperiodic, then ψ(x) ≥ 3.
Proof. Let r = Card A and let x ∈ A N be aperiodic. Suppose on the contrary that ψ(x) ≤ 2. By Lemma 6, x contains an unbordered factor w of length |w| ≥ 2r + 1. If w is palindromically generated by a singleton set {I} ⊆ S(|w|), then w contains at least r + 1 distinct symbols, a contradiction. If w is palindromically generated by a set {(1, p), (q, |w|)} ⊆ S(|w|) of size 2, then as w is unbordered, it follows that the palindromic prefix w [1, p] does not overlap the palindromic suffix w[q, |w|] (i.e., p < q). It follows again that w must have at least r + 1 distinct symbols, a contradiction. Hence by Lemma 9, ψ(x) ≥ 3.

Consider the Thue-Morse word T = 0110100110010110100101100110100110010110 . . . whose origins go back to the beginning of the last century with the works of the Norwegian mathematician Axel Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF]. The nth entry t n of T is defined as the sum modulo 2 of the digits in the binary expansion of n. Alternatively, T is the fixed point beginning in 0 of the morphism τ : {0, 1} * → {0, 1} * given by τ (0) = 01 and τ (1) = 10. Proposition 11. For each integer n > 0 there exists a factor u of T with µ(u) ≥ n, i.e., ψ(T) = +∞.

Proof. Set t k = τ k (0) for k ≥ 0. We will show that µ(t 2k ) > µ(t 2k-2 ) for each k > 1 from which it follows immediately that ψ(T) = +∞. For each k ≥ 0 there exists S 2k ⊆ S (2 2k ) which palindromically generates t 2k and µ(t 2k ) = Card S 2k . We first observe that the prefix

t 2k of T of length 2 2k is a palindrome, since t 2k = t 2k-1 t R 2k-1 .
Also, since T is overlap-free (see e.g. [START_REF] Lothaire | Combinatorics on Words[END_REF]), it follows that if v is a palindromic factor of t 2k , either v lies completely in the prefix t 2k-1 or completely in the suffix t R 2k-1 , or its midpoint is the midpoint of t 2k . There necessarily exists a generator in S 2k that shares the middle point with t 2k in order to relate an occurrence of 0 in the prefix t 2k-1 with an occurrence of 0 in the suffix t R 2k-1 of t 2k . Such a generator can always be replaced by the pair F = (1, 2 2k ) corresponding to the full palindrome t 2k , and thus without loss of generality we can assume that F ∈ S 2k .

If I = (i, j) ∈ S 2k lies in the suffix t R 2k-1 of t 2k , i.e., if i > 2 2k-1 , then we replace I by its reflection I ′ = ρ F (I) which lies entirely in the first half of t 2k . Since ρ I = ρ F ρ I ′ ρ F on the domain of ρ I , the set (S 2k \ {I}) ∪ {I ′ } generates t 2k . In this fashion we obtain a generator set S ′ 2k consisting of F and a set of pairs (i, j) where j ≤ 2 2k-1 . Thus S ′ 2k \ {F } palindromically generates the prefix t 2k-1 of t 2k . Since t 2k-2 is a factor of t 2k-1 , it follows from Lemma 9 that µ(t 2k ) > µ(t 2k-1 ) ≥ µ(t 2k-2 ) as required.

The following lemmas will be used in the subsequent section: Lemma 12. Suppose u ∈ A n is palindromically generated by a set S ⊆ S(n). Suppose further that there exist p, q ∈ N such that (p, p + 2q) ∈ S. Then for

A = {u[p + q]} we have µ(d A (u)) ≤ Card S.
Proof. Let a = u[p+q], and write d a for d {a} . We define first a mapping p da : {1, 2, . . . , n} → N ∪ {(j, j + 1) | j ∈ N} for the positions of u ∈ A n . It maps every position of u to a corresponding position of d a (u) or to a pair of positions of d a (u) depending on whether the position of u has a label a that will be doubled or some other label. For convenience let us denote the prefix u [1, i] of u by u i and let u 0 be the empty word.

p da (i) = { |d a (u i )| if u[i] ̸ = a (|d a (u i )| -1, |d a (u i )|) if u[i] = a. Let S ′ = {(i ′ , j ′ ) | (i, j) ∈ S} where i ′ = |d a (u i-1 )| + 1 and j ′ = |d a (u j )|.
In other words, we dilate each generator (i, j) by applying d a to the corresponding factor u[i, j]. Clearly Card S ′ = Card S. We shall show that S ′ palindromically generates d a (u). We claim first that if a position i 1 of u is reflected to i 2 by a generator (i S , j S ) ∈ S then p da (i 1 ) is reflected to p da (i 2 ) by a generator (i S ′ , j S ′ ) ∈ S ′ . Here (i S ′ , j S ′ ) is the generator in S ′ corresponding to the generator (i S , j S ) in S.

Now U = u[i S , i 1 -1] = u[i 2 + 1, j S ] R , and thus |d a (U )| = |d a (U R )| = |d a (u[i 2 + 1, j S ])|; see Figure 2. So if u[i 1 ] ̸ = a then p da (i 1 ) -i S ′ = j S ′ -p da (i 2 ) and otherwise p da (i 1 ) -(i S ′ , i S ′ + 1) = (j S ′ -1, j S ′ ) -p da (i 2 ).
Thus p da (i 1 ) is reflected to p da (i 2 ) as a single or as a pair of positions. Let us denote, for any x ∈ A,

u i S U s i 1 s i 2 U R j S d a (u) i ′ S £ ¢ ¡ |d a (U )| s p da (i 1 ) s p da (i 2 ) £ ¢ ¡ |d a (U R )| j ′ S
Ω u,x = {i | 1 ≤ i ≤ n and u[i] = x},
i.e., Ω u,x is the set of occurrences of x in u. By Lemma 7, for each i, j ∈ Ω u,x there exists a sequence i = i 1 , i 2 , . . . , i l = j of positions i m ∈ Ω u,x such that i m is reflected to i m+1 by some generator in S. As we just showed there also exists a sequence i ′ = p da (i 1 ), p da (i 2 ), . . . , p da (i l ) = j ′ such that p da (i m ) is reflected to p da (i m+1 ) by some generator in S ′ . Thus if i ∈ Ω u,x then p da (i) ∈ Ωda(u),x where

Ωda(u),x = {p da (i) | i ∈ Ω u,x }.
In fact, if x ̸ = a then Ωda(u),x is the same set as Ω da(u),x . The only problematic set is Ωda(u),a = {(i ′ , i ′ + 1) | 1 ≤ i ′ < |d a (u)| and for which ∃i ∈ Ω u,a s.t. p da (i) = (i ′ , i ′ + 1)}. Now, consider the generator (p ′ , q ′ ) ∈ S ′ that is obtained from (p, p + 2q) ∈ S, i.e. (p ′ , q ′ ) = (|d a (u p-1 )| + 1, |d a (u p+2q )|). The length of the palindrome determined by the generator (p ′ , q ′ ) is even because

|d a (u[p, p + q -1])| = |d a (u[p + q + 1, p + 2q])| and |d a (u[p + q])| = 2.
Hence a pair of two consecutive positions of d a (u), namely the positions of p da (p + q) ∈ Ωda(u),a , is now in the middle of this palindrome (p ′ , q ′ ) thus these two positions reflect to each other and they have to have the same letter in word d a (u). Because of the pairwise reflections among the set Ωda(u),a , the positions of u according to the pairs in this set contain the same letter a.

So we have that Ωda(u),x = Ω da(u),x for x ̸ = a. In the case x = a the positions covered by the pairs in Ωda(u),a are exactly the positions in Ω da(u),a . This shows that there exists a path as described in Lemma 7 between each positions in Ω da(u),x for any x ∈ A thus S ′ palindromically generates the doubled word d a (u) and this ends the proof.

Corollary 13. Let a ∈ A and u

∈ A n . Then for A = {a} we have µ(d A (u)) ≤ µ(u) + 1.
Proof. The result is clear if the symbol a does not occur in u since in this case d A (u) = u. Thus we can assume that a occurs in u. Suppose S ⊆ S(n) palindromically generates u and µ(u) = Card S. If S contains a generator that determines a palindrome of odd length whose center is equal to a, then by Lemma 12 we deduce that µ(d A (u)) ≤ µ(u) < µ(u) + 1. If no such generator exists, then we can add a "trivial" generator (i, i) where i is such that u[i] = a. Now S ∪ {(i, i)} has µ(u) + 1 elements and the result follows again from Lemma 12.

Example 14. Consider a palindrome u = aba which can be generated by one palindromic generator [START_REF] Adamczewski | On complexity of algebraic numbers, II. Continued fractions[END_REF][START_REF] Berstel | Sturmian words, Lyndon words and trees[END_REF]. The doubled word d {a} (u) = aabaa can be generated by the set {(1, 5), (1, 2)} and µ(d {a} (u)) = µ(u) + 1. If we instead double the letter b then we do not need any additional generators, i.e., the doubled word d {b} (u) = abba can be generated by [START_REF] Adamczewski | On complexity of algebraic numbers, II. Continued fractions[END_REF][START_REF] Brlek | On the palindromic complexity of infinite words[END_REF] and µ(d {b} (u)) = µ(u). Lemma 15. Let w ∈ {0, 1} * be an unbordered word of length n which is palindromically generated by a set S ⊆ S(n) with Card S = 3. Then w has at most four leaves. Moreover, there are at most two leaves with label 0, and at most two leaves with label 1.

Proof. We note first that since w is unbordered, the longest palindromic prefix U and the longest palindromic suffix V of w do not overlap. Indeed, if U = ux and V = xv then w has a border x R ; a contradiction.

Let S = {(1, i), (j, n), (k, m)}. Since the maximal palindromes U and V do not overlap, we have i < j, and hence every path starting from a leaf has a unique continuation to a new position until the path enters another leaf. Therefore, there is at most one path for the letter 0 and at most one for the letter 1. These two paths necessarily consume every position of w, and the endpoints of these paths are the leaves of S.

A characterization of binary words with ψ(x) = 3

We begin by recalling a few basic facts concerning Sturmian words (see [START_REF] Berstel | Sturmian and Episturmian Words (A Survey of Some Recent Results)[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF]). An infinite binary word ω ∈ {0, 1} N is called Sturmian if ω contains exactly n + 1 factors of each given length n ≥ 1. Each Sturmian word ω is aperiodic, uniformly recurrent, closed under reversal (i.e., if u is a factor of ω then so is u R ) and balanced (for any two factors u and v of the same length, ||u| a -|v| a | ≤ 1 for each a ∈ {0, 1}, where |w| a denotes the number of occurrences of a in w). In fact an infinite binary word ω ∈ {0, 1} N is Sturmian if and only if it is aperiodic and balanced.

A factor u of a Sturmian word ω is called right special (resp. left special) if both u0 and u1 (resp. 0u and 1u) are factors of ω. Thus ω contains exactly one right special (resp. left special) factor of each given length, and u is right special if and only if u R is left special. A factor u of ω is called bispecial if u is both right and left special. Thus, if u is a bispecial factor of ω, then u is a palindrome. A binary word x ∈ {0, 1} * is called a central word if and only if x ∈ P and x0 and x1 are both balanced. We recall the following fact which is a consequence of a result in [START_REF] De Luca | Sturmian words: structure, combinatorics, and their arithmetics[END_REF] (see also [START_REF] Carpi | Codes of central Sturmian words[END_REF]): Lemma 16 (Proposition 22 in [START_REF] Berstel | Sturmian and Episturmian Words (A Survey of Some Recent Results)[END_REF]). A word x ∈ {0, 1} * is a central word if it is a power of a single letter or if it satisfies the equations x = u01v = v10u with u, v ∈ {0, 1} * . Moreover in the latter case u and v are central words and setting p = |u| + 2 and q = |v| + 2, we have that p and q are relatively prime periods of x and min{p, q} is the least period of x.

We will also need the following result. Lemma 17. Let u be an unbordered factor of a Sturmian word ω ∈ {0, 1} N . Then either u ∈ {0, 1} or u = axb, where {a, b} = {0, 1}, and x is a central word.

Proof. If u / ∈ {0, 1}, then we can write u = axb with {a, b} = {0, 1}. We claim that x is a palindrome. In fact, suppose vc (resp. dv R ) is a prefix (resp. suffix) of x with v ∈ {0, 1} * and {c, d} = {0, 1}. Since u is balanced it follows that c = b and d = a. Since av R b and avb are both factors of ω, it follows that v is a bispecial factor of ω, and hence a palindrome. Thus avb is both a prefix and a suffix of u. Since u is unbordered, it follows that u = avb, and hence x = v. Thus x is central.

We also recall the following extremal property of the Fine and Wilf theorem [START_REF] Fine | Uniqueness theorem for periodic functions[END_REF] concerning central words due to de Luca and Mignosi [START_REF] De Luca | Some combinatorial properties of Sturmian words, Theoret[END_REF] Lemma 18 (Proposition 23 in [START_REF] Berstel | Sturmian and Episturmian Words (A Survey of Some Recent Results)[END_REF]). A word x is a central word if and only if there exist relatively prime positive integers p and q with |x| = p + q -2 such that x has periods p and q.

We will also use the following property by Lothaire [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] several times to find a period of a palindrome which has a palindromic prefix (and suffix).

Lemma 19 ([19]

). If uv = vu ′ , then |u| is a period of uv.

A word y ∈ {0, 1} N is called double Sturmian if y is a suffix of d A (x) for some Sturmian word x and A ⊆ {0, 1} (where d A is the doubling morphism defined in section 1). By taking A = ∅, each Sturmian word is double Sturmian. Proposition 20. Let y be a factor of a double Sturmian word ω ∈ {0, 1} N . Then µ(y) ≤ 3.

Proof. Let y be a factor of a double Sturmian word ω. Thus there exists a Sturmian word ω ′ ∈ {0, 1} N and a subset A ⊆ {0, 1} such that ω is a suffix of d A (ω ′ ). Let y ′ be the shortest unbordered factor of ω ′ such that y is a factor of d A (y ′ ). Because ω ′ is aperiodic and uniformly recurrent, such a factor y ′ always exists. Now by Lemma 9 it is enough to show that d A (y ′ ) is palindromically generated by a set with at most three generators. By Lemma 12 it suffices to show that y ′ is palindromically generated by a set S ′ with Card S ′ ≤ 3 and containing two generators which determine two palindromes of odd length in y ′ with distinct central symbols .

Since y ′ is unbordered, by Lemma 17, we may write y ′ = axb where x ∈ {0, 1} * is a central word and {a, b} = {0, 1}. Without loss of generality we can assume that a = 0 and b = 1. We first consider the case where x is a power of a single letter. If x is empty, then y ′ = 01 is palindromically generated by

S ′ = {(1, 1), (2, 2)}. If x = 0 n with n ≥ 1, then y ′ = 0 n+1 1 is palindromically generated by S ′ = {(1, n), (1, n + 1), (n + 2, n + 2)}. If x = 1 n with n ≥ 1, then y ′ = 01 n+1 is palindromically generated by S ′ = {(1, 1), (2, n + 1), (2, n + 2)}.
z begins in 0. On the other hand, since 10u is a suffix of x of length p and p divides p ′ , it follows that z begins in 1. This contradiction proves that 0u0 is the longest palindromic prefix of 0x1. Similarly one deduces that 1v1 is the longest palindromic suffix of 0x1.

By Lemma 16, p and q are relatively prime so two of the three palindromes {x, 0u0, 1v1} have odd length and by Lemma 15 the central symbols of these have to be different.

We next prove the converse of Theorem 4, namely: Proposition 22. Suppose w ∈ {0, 1} + is such that µ(w) ≤ 3. Then w is a factor of a double Sturmian word ω.

In the following lemmas we use a and b as variables of letters such that {a, b} = {0, 1}. Lemma 15 on the number of leaves entails some immediate restrictions on w.

Lemma 23. Suppose w ∈ {a, b} * be such that µ(w) ≤ 3. Then (i) The words a 3 and b 3 do not both occur in w.

ii) For odd k, ba k b and a k+2 do not both occur in w.

(iii) The words ba k b and a k+3 do not both occur in w for any k ≥ 1.

(iv) All three words a k+2 , ba k+1 b and ba k b do not occur in w for any k ≥ 1.

Proof. In each of the cases we assume that w with |w| = n is a minimal counter example, i.e., none of its proper factors is a counter example. By the minimality assumption, w begins and ends in the expressed forbidden words. Since also the reverse w R is a counter example, we may assume that the first letter of w is b.

For Case (i), let w = b 3 ua 3 for some u. By the minimality assumption, w is unbordered, and w is palindromically generated by the set S = {(1, 3), (n -2, n), (i, j)} for some (i, j) that determines the palindrome w[i, j]. Here either i > 3 or j < n-2, since the palindrome w[i, j] starts and ends with the same letter. However, this means that there are three leaves for a or three leaves for b. This contradicts Lemma 15. § ¤ For Case (ii), let w = ba k bua k+2 for some u. Since w is minimal, it is unbordered, and it is palindromically generated by S = {(1, k + 2), (n -k -1, n), (i, j)} for some (i, j). For Case (iii), let w = ba k bua k+3 . Since w is minimal, w is unbordered, and it is palindromically generated by S = {(1, k + 2), (n -k -2, n), (i, j)} for some (i, j). The palindrome w[i, j] misses at least the last three a's of w. Again Lemma 15 yields a contradiction.

ba k b § ¤ a k+2 ¦ ¥ w[i, j]
For Case 4, consider first any factor of the form v = ba k bua k+1 of w, where ba k b occurs only as a prefix and a k+1 only as a suffix of v. Again v is unbordered, and S contains a generator (i, j), where i > 1 and j < |v|, i.e., the palindrome v[i, j] misses at least the suffix a and the prefix b of v. By Case (ii), u ̸ = ab (for otherwise k + 1 ≥ 3), and hence, by Lemma 15, u ∈ {ε, b}. Similarly, if v = a k+1 uba k b then u ∈ {ε, b}. This proves the case since if a k+2 and ba k b occur in w, by the above ba k+1 b does not occur in w.

The key result for the converse is stated in Lemma 25 which gives a simplified criterion for pairs witnessing that a word is unbalanced when compared to the general case of Lemma 24. We have Lemma 24 (Proposition 2.1.3 in [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]). If w ∈ {a, b} * is unbalanced then there is a palindrome u such that both aua and bub are factors of w.

Lemma 25. Suppose w ∈ {a, b} * is unbalanced and µ(w) ≤ 3. Let aua and bub be any palindromic factors of w. Then u = a k or u = b k for some even k ≥ 0.

Proof. By Lemma 23 we can assume without loss of generality that b 3 is not a factor of w. Also, the case for u = ε is clear, and thus we can assume that u ̸ = ε.

Consider a shortest factor z of w containing both aua and bub. Then z begins with aua and ends with bub, or vice verse, and z has unique occurrences of the factors aua and bub. We can suppose that z starts with a, since otherwise we take the reverse of z. Now, aua is a maximal palindromic prefix of z, since a longer palindromic prefix of z would contain aua as a suffix. Similarly bub is a maximal palindromic suffix of z.

By Lemma 9, µ(z) ≤ 3. Since u is a palindrome, the factors aua and bub do not overlap. Indeed, if z = au 1 bu 2 au 3 b, where u = u 1 bu 2 = u 2 au 3 , then by taking a reverse of u, we have u R 2 bu R 1 = u 2 au 3 , and so bu R 1 = au 3 ; a contradiction since a ̸ = b. Since aua and bub do not overlap and z is chosen to be minimal, z is unbordered, and thus Lemma 15 applies to z.

Let the palindromic generators of z be (1, p) (s, n) and (i, j). Then z [1, p] is a prefix of the maximal palindromic prefix aua of z, z[s, n] is a suffix of the maximal palindromic suffix bub of z, and z = xz[i, j]y, where x and y are non-empty. By Lemma 15, |x|+|y| ≤ 4, and |x|, |y| ≥ 1 since two of the leaves (one a and one b) reside at the ends of z. We have |x| ̸ = |y|, since the last letter of aua and the first letter of bub cannot be reflected to each other by the generator (i, j). Therefore, either |x| = 1 or |y| = 1. We assume that |y| = 1 (i.e., y = b) and |x| > 1, the proof for |x| = 1 and |y| > 1 being similar. We now have found three leaves, two in the prefix of z and one at the end. Hence, we have z = z [1, p]vz [s, n] where |v| ≤ 1 since the positions in v are also leaves.

Since bub is a maximal palindromic suffix of z and y = b, z[i, j] is preceded by the letter a. It follows that both leaves for the letter a occur in the prefix x, and the remaining fourth leaf resides at a position for the letter b. In particular, if v ̸ = ε then v = b. d A(x) (y) Suppose then that k = 0. Since now 11 occurs in u but 111 does not occur in w, we have 1 / ∈ A(w). By the definition of A(w), the word 010 must be a factor of u, and hence by the minimality of w, we have u = 00(10) r 11 for some positive r ≥ 1. From this also 0 / ∈ A(w) follows, and hence u = w. However, the palindromic generators of w are now (1, 2) that determines the prefix w [START_REF] Adamczewski | On complexity of algebraic numbers, II. Continued fractions[END_REF][START_REF] Berstel | Sturmian and Episturmian Words (A Survey of Some Recent Results)[END_REF] = 00, and (n -1, n) that determines the suffix w[n -1, n] = 11, and (i, j) that determines the factor w[i, j]. But the palindrome w[i, j] cannot overlap with both w [START_REF] Adamczewski | On complexity of algebraic numbers, II. Continued fractions[END_REF][START_REF] Berstel | Sturmian and Episturmian Words (A Survey of Some Recent Results)[END_REF] and w[n -1, n] and thus the two 0's in w [START_REF] Adamczewski | On complexity of algebraic numbers, II. Continued fractions[END_REF][START_REF] Berstel | Sturmian and Episturmian Words (A Survey of Some Recent Results)[END_REF] and the latter 0 are not equivalent or the two 1's in w[n -1, n] are not equivalent to a preceding 1; a contradiction. Proof of Proposition 22. By Lemma 26, if µ(w) ≤ 3, then w is a factor of the word d A(w) (u) for a balanced word u. Since the factors of Sturmian words are exactly the balanced words, see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF], the claim follows. This also proves Theorem 4.

y J J J J J J v ¦ ¥ u § ¤ d A(x) (u) J J J J J J d A(x) (v)
Proof of Corollary 5. Let x ∈ {0, 1} N be aperiodic. By Proposition 10, ψ(x) ≥ 3.

If x is double Sturmian then, by Proposition 20, µ(w) ≤ 3 for all factors of x, and thus by definition, ψ(x) = 3.

For the converse, assume that ψ(x) = 3, and consider the set A(x) ⊆ {0, 1} together with the lean word y of x. Then x is a suffix of d A(x) (y). We need to show that y is Sturmian. Let v be a factor of y, and let u be a factor of y such that u contains v and d A(x) (u) contains a factor of the form ba 2k+1 b with k ≥ 0 for each a / ∈ A(x). Hence A(d A(x) (u)) = A(x), and therefore u is the lean word of d A(x) (u); see Figure 4. By Lemma 9, µ(d A(x) (u)) ≤ 3, and thus Lemma 26 yields that u, and hence also v, is balanced. It follows that y is Sturmian as required.

Figure 1 :

 1 Figure 1: Reflecting the generators in S.

Figure 2 :

 2 Figure 2: Reflection complies with doubling morphism d a .

Figure 3 :

 3 Figure 3: The palindromic factors of w in Case 2.

  These generators determine the factors w[1, k + 2] = ba k b, w[n -k -1, n] = a k+2 and w[i, j], respectively, where the palindrome w[i, j] necessarily misses the first b of w[1, k + 2] and the last two a's of w[n -k -1, n]; see Figure 3. Also, w[1, k + 2] and w[n -k -1, n] are both of odd length, since k is assumed to be odd, and thus their middle positions are leaves. This contradicts Lemma 15.

Figure 4 :

 4 Figure 4: Proof of Proposition 5: The word v is extended to a lean factor u of d A(x) (u).

  but then d A(w) (u) has factors 0 2m+4 and 10 2m 1, and thus w has factors 0 2m+3 and 10 2m 1 contradicting Lemma 23(iii).

 [START_REF] Adamczewski | On complexity of algebraic numbers, II. Continued fractions[END_REF]Partially supported by a FiDiPro grant (137991) from the Academy of Finland and by ANR grant SUBTILE.

In all of these cases there exist two generators which determine odd length palindromes with distinct central symbols.

Next we assume x is not a power of a single letter. By Lemma 16 there exist central words u and v such that y ′ = 0u01v1. Put U = 0u0 and V = 1v1. We claim that y ′ is palindromically generated by the set

we deduce by Lemma 18 that x ′ is a central word. Thus x ′ is either a power of a single letter or it is isomorphic to x. In the first case w is also a power of a single letter. In the second case, w is word isomorphic to y ′ . Thus in either case there exists a mapping ν : We have an auxiliary result which shows that the generating set obtained in Proposition 20 for y = axb includes both the longest palindromic prefix and the longest palindromic suffix of y. This follows from the following refinement of Lemma 16.

Proposition 21. Let x ∈ {0, 1} * be a central word which is not a power of a single letter. Let u and v be as in Lemma 16. Then 0u0 (respectively 1v1) is the longest palindromic prefix (respectively suffix) of 0x1. Moreover, two of the three palindromes {x, 0u0, 1v1} are of odd length and have distinct central symbols.

Proof. Since u is a central word and hence a palindrome, we have that 0u0 is a palindromic prefix of 0x1. It remains to show that it is the longest such prefix. Suppose to the contrary that 0x1 admits a palindromic prefix 0u ′ 0 with |u ′ | > |u|. Then by lemmas 16 and 19, we have that p = |u| + 2, q = |v| + 2 and

follows from Lemma 16 that the min{p, q} = p. Also, as

But since both p and p ′ are periods of x, it follows from the Fine and Wilf Theorem [START_REF] Fine | Uniqueness theorem for periodic functions[END_REF] that x has period gcd(p, p ′ ) which by Lemma 16 is equal to p. Whence p divides p ′ . Let z denote the suffix of x of length p ′ . Since 0u ′ 0 is a palindromic prefix of 0x1 it follows that Suppose first that |u| is odd. If |v| = 1, and thus v = b, then the position of v is the fourth leaf, and z [1, p] = aua or z[s, n] = bub. Here z[s, n] ̸ = bub since otherwise the midpoint of bub would be a fifth leaf. Hence z [1, p] = aua and the midpoint of aua is a leaf. To avoid a fifth leave, it must be at position i = 2, i.e., |u| = 1, and consequently z = acabcb where c = a because b 3 does not occur in z. However, µ(aaabab) = 4. Therefore, by Lemma 15, v = ε, in which case, z [1, p] = aua and z[s, n] = bub, and they both have odd length. Again, necessarily |u| = 1 to avoid a fifth leaf, and as above z = aaabab with µ(z) = 4.

Consequently, |u| must be even. Let u = u 1 u 2 be such that z[i, j] = u 2 atbu 1 u 2 for some t and hence z = au 1 u 2 atbu 1 u 2 b. By the above, we have |t| ≤ 1, and if |t| = 1, then z [1, p] = aua and z[s, n] = bub. Here u 2 is a palindrome since z[i, j] is one. Also, in all cases both u 1 and t consist of leaves only, and hence 1 [1, p] = aua and z[s, n] = bub by Lemma 15, since the three positions of the prefix au 1 and the last position of z are leaves. Also, u 1 = ba since z[i, j] and thus also its middle factor abu 1 is a palindrome. Since z[i, j] is a palindrome, and |u 1 | is a period of u, we have z [1, p] = aua = a(ba) i+1 ba for some i. However, now |u| is odd; a contradiction. This proves the claim.

For w ∈ {0, 1} + ∪ {0, 1} N , we define A(w) ⊆ {0, 1} by the rule a ∈ A(w) if and only if w has no factors of the form ba 2k+1 b for any k ≥ 0 with a ̸ = b. If w is a finite word, we define the lean word of w to be the shortest word u such that d A(w) (u) contains w as a factor. We extend this notion to the infinite case as follows: If w ∈ {0, 1} N , we say u ∈ {0, 1} N is the lean word if d A(w) (u) contains w as a suffix and for all v ∈ {0, 1} N , if w is a suffix of d A(w) (v), then u is a suffix of v. Clearly, in each case the lean word of w is uniquely determined by w.

For instance, if w = 0010011, then A(w) = {0} and the lean word of w is u = 01011. Similarly if w = 011001, then A(w) = {0, 1} and the lean word u = 0101. For w = 0010110, we have A(w) = ∅ and hence w is its own lean word.

Lemma 26. Let w ∈ {0, 1} * be a binary word with µ(w) ≤ 3. Then the lean word u of w is balanced.

Proof. Let w be a shortest counter example to the claim such that its lean word u is unbalanced. By appealing to symmetry and Lemma 23(i), we can assume that w contains no occurrences of 111.

Since u is not balanced, it has factors 0v0 and 1v1 for some palindrome v according to Lemma 24. Now, also 0d A(w) (v)0 and 1d A(w) (v)1 are palindromes, and they are factors of w. By Lemma 25, we have d A(w) (v) = 0 k for some even integer k. It follows that v = 0 m for m = k/2 or m = k depending on whether 0 is in A(w) or not. Here u has factors 0 m+2 and 10 m 1.

Suppose first that k > 0. Since w has factors 0 k+2 and 10 k 1, it has no blocks of 0's of odd length by Lemma 23(iii) and (iv). Hence 0 ∈ A(w) by the definition of A(w),


Luca Q Zamboni
email: zamboni@math.univ-lyon1.fr

On the character of words of sub-linear complexity

Keywords:

Let A * denote the free monoid generated by a finite nonempty set A. For each infinite word

In other words, the factor complexity of x is the complexity of the language of its factors Fac

Our starting point in this paper is the following characterisation of infinite words of sub-linear factor complexity obtained recently by the author together with J. Cassaigne, A. Frid and S. Puzynina: Let x ∈ A ω . Then p x (n) = O(n) if and only if Fac(x) ⊆ S 2 for some S ⊆ A * with lim sup p S (n) < +∞. In other words, p x (n) ≤ Cn for some constant C if and only if there exists a set S of bounded complexity such that every factor w of x can be factored as w = uv with u, v ∈ S. Given an infinite word x ∈ A ω , we define its character, denoted χ(x), to be the least value for lim sup p S (n) over all languages S such that Fac x ⊆ S 2 . Clearly χ(x) ∈ [1, +∞] and it follows from the above characterisation that p x (n) = O(n) if and only if χ(x) < +∞. We prove that χ(x) = 1 if and only if x is ultimately periodic and that χ(x) = 2 whenever x is a Sturmian word.

Introduction

Let A be a finite non-empty set. For each infinite word x = x 0 x 1 x 2 • • • ∈ A ω , the complexity or factor complexity p x (n) counts the number of distinct blocks x i x i+1 • • • x i+n-1 ∈ A n of length n occurring in x. First introduced by Hedlund and Morse in their seminal 1938 paper [START_REF] Morse | Symbolic dynamics[END_REF] under the name of block growth, the factor complexity measures the extent of randomness of x : Periodic (meaning ultimately periodic) words have bounded factor complexity while digit expansions of normal numbers have maximal complexity. A celebrated theorem of Morse and Hedlund in [START_REF] Morse | Symbolic dynamics[END_REF] states that every aperiodic (meaning non-ultimately periodic) word contains at least n + 1 distinct factors of each length n. Words having precisely n + 1 factors of each given length n are called Sturmian words. From the point of view of the Morse-Hedlund theorem, they are those aperiodic words of minimal factor complexity. They arise naturally in various branches of mathematics including combinatorics, algebra, number theory, ergodic theory, dynamical systems and differential equations. In theoretical physics, Sturmian words constitute 1-dimensional models for quasi-crystals, and in theoretical computer science they are used in computer graphics as digital approximation of straight lines. Perhaps the most studied Sturmian word is the so-called Fibonacci word x = 0100101001001010010 • • • defined as the fixed point of the substitution 0 → 01, 1 → 0.

There are several variations and extensions of the Morse-Hedlund theorem associated with other notions of complexity including Abelian complexity [START_REF] Coven | Sequences with minimal block growth[END_REF][START_REF] Richomme | Abelian complexity of minimal subshifts[END_REF], Abelian first returns [START_REF] Puzynina | Abelian returns in Sturmian words[END_REF], maximal pattern complexity [START_REF] Kamae | Sequence entropy and the maximal pattern complexity of infinite words[END_REF], palindrome complexity [START_REF] Allouche | Palindrome complexity, Selected papers in honor of Jean Berstel[END_REF], cyclic complexity [START_REF] Cassaigne | Cyclic complexity of words[END_REF] and group complexity [START_REF] Charlier | On a group theoretic generalization of the Morse-Hedlund theorem[END_REF] to name just a few. In most cases, these alternative notions of complexity may be used to detect (and in some cases characterize) ultimately periodic words. Generally, amongst all aperiodic words, Sturmian words have the lowest possible complexity, although in some cases they are not the only ones. For instance, a restricted class of Toeplitz words is found to have the same maximal pattern complexity as Sturmian words (see section 4 of [START_REF] Kamae | Maximal pattern complexity for discrete systems, Ergodic Theory & Dynam[END_REF]). There have also been numerous attempts at extending the Morse-Hedlund theorem in higher dimensions. A celebrated conjecture of M. Nivat states that any 2-dimensional word having at most mn distinct m × n blocks must be periodic. In this case, it is known that the converse is not true. To this day the Nivat conjecture remains open although the conjecture has been verified for m or n less or equal to 3 (see [START_REF] Cyr | Complexity of short rectangles and periodicity[END_REF][START_REF] Sander | The rectangle complexity of functions on two-dimensional lattices[END_REF]). A very interesting higher dimensional analogue of the Morse-Hedlund theorem was obtained by Durand and Rigo in [START_REF] Durand | Multidimensional extension of the Morse-Hedlund theorem[END_REF] in which they re-interpret the notion of periodicity in terms of Presburger arithmetic.

Beyond Sturmian words, there are many other rich families of infinite words having low (meaning sub-linear) factor complexity. They include all words generated by primitive substitutions and more generally all linearly recurrent words [START_REF] Durand | Substitutional dynamical systems, Bratteli diagrams and dimension groups[END_REF], automatic sequences [START_REF] Allouche | Automatic Sequences, Theory, Applications, Generalizations[END_REF], Arnoux-Rauzy sequences [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF] and symbolic codings of interval exchange transformations [START_REF] Arnold | Small denominators and problems of stability of motion in classical and celestial mechanics[END_REF]. In [START_REF] Ferenczi | Rank and symbolic complexity[END_REF], S. Ferenczi proved that the language of any uniformly recurrent word having sublinear factor complexity is S-adic, meaning that for any such x there exist a finite set S of morphisms over some finite alphabet A, a ∈ A and an infinite sequence

(τ n ) n≥0 ∈ S ω such that x = lim n→∞ τ 0 • • • τ n (a ω ).
An important open question along these lines is the so-called S-adic conjecture which involves finding some condition (*) such that for any word x, the factor complexity of x is sub-linear if and only if x is an S-adic word verifying condition (*). See for instance [START_REF] Leroy | Some improvements of the S-adic conjecture[END_REF] and the references therein.

Our starting point in this paper is a different characterisation of infinite words x ∈ A ω of sub-linear factor complexity recently obtained by the author together with J. Cassaigne, A. Frid and S. Puzynina in [START_REF] Cassaigne | Cost and dimension of words of zero topological entropy[END_REF]:

Theorem 1 (Theorem 1 in [START_REF] Cassaigne | Cost and dimension of words of zero topological entropy[END_REF]). Let A be a finite non-empty set and x ∈ A ω . Then p x (n) = O(n) if and only if Fac x ⊆ S 2 for some S ⊆ A * with lim sup p S (n) < +∞.

In other words, p x (n) ≤ Cn for some constant C if and only if there exists a set S of bounded complexity such that every factor w of x can be factored as w = uv with u, v ∈ S. The proof of Theorem 1 in [START_REF] Cassaigne | Cost and dimension of words of zero topological entropy[END_REF] is constructive in the sense that if p x (n) = O(n), it describes a way of constructing a set S of bounded complexity such that Fac x ⊆ S 2 . However, it is natural to ask what is the smallest value for lim sup p S (n) < +∞ over all languages S for which Fac x ⊆ S 2 . More precisely, for each x ∈ A ω , we define the character of x by

χ(x) = inf{lim sup p S (n) : S ⊆ A * , Fac x ⊆ S 2 }
where we take the convention that inf ∅ = +∞. Thus χ(x) ∈ [1, +∞] ∩ Z and by Theorem 1 we have that p x (n) = O(n) if and only if χ(x) < +∞. In this paper we prove that χ(x) = 2 whenever x is a Sturmian word. More precisely, given a Sturmian word x ∈ {0, 1} ω there exists a set S such that Card(S ∩ {0, 1} n ) = 2 for all n ≥ 1 and Fac x ⊆ S 2 . Moreover, this is optimal in the sense that χ(x) = 1 if and only if x is ultimately periodic.

The paper is organised as follows: In §2 we recall some fundamental notions concerning finite and infinite words. In §4 we establish the main result of the paper, namely that an infinite word x is ultimately periodic if and only if χ(x) = 1. In §5 we prove that χ(x) = 2 whenever x is a Sturmian word.

Preliminaries

In this section we briefly recall some basic definitions and notations concerning finite and infinite words which are relevant to the subsequent sections. For a more detailed exposition, the reader is referred to one of the standard texts in combinatorics on words such as the Lothaire books [START_REF] Lothaire | Combinatorics on words[END_REF][START_REF] Lothaire | Algebraic combinatorics on words[END_REF].

The set A * consisting of all finite words over the alphabet A is naturally a free monoid under the operation of concatenation, with the empty word ε playing the role of the identity. Given a finite word u = a 1 a 2 . . . a n with n ≥ 1 and a i ∈ A, we denote the length n of u by |u|. For each a ∈ A, we let |u| a denote the number of occurrences of the letter a in u. Let A ω denote the set of (right) infinite words

x = x 0 x 1 x 2 • • • with x i ∈ A. Given an infinite word x ∈ A ω , a word u ∈ A * is called a factor of x if either u = ε or if u = x i x i+1 • • • x i+n
for some natural numbers i and n. We denote by Fac x (n) the set of all factors of x of length n, and set Fac x = n∈ω Fac x (n).

Let p x : N → N denote the factor complexity of x defined by:

p x (n) = Card(Fac x (n)).
An infinite word x is called ultimately periodic if x = uvvv • • • = uv ω for some non-empty words u, v ∈ A * . An infinite word is said to be aperiodic if it is not ultimately periodic. A celebrated theorem of Morse and Hedlund in [START_REF] Morse | Symbolic dynamics[END_REF] states that every aperiodic word contains at least n + 1 distinct factors of each length n. Sturmian words are infinite words having exactly n + 1 distinct factors of each length n ≥ 1.

A factor u of x is called right (resp., left) special if ua, ub ∈ Fac(x) (resp., au, bu ∈ Fac(x)) for distinct letters a, b ∈ A. A factor u of x is called bispecial if u is both left and right special. It follows that every aperiodic word contains a right and a left special factor of each length. More precisely, let x ∈ A ω be aperiodic. Given a factor u of x, let R(u) (L (u), respectively ) denote the shortest right (left, respectively ) special factor of x beginning (ending, respectively) in u. We note that if u is right (left, respectively) special, then L (u) (R(u), respectively) is bispecial. Also, since x is aperiodic, for any factors u and v of x with |u| < |v|, if u is both a prefix and a suffix of v, then R(u) is a prefix of v. Otherwise, every occurrence of u in x is an occurrence of v in x and x would be ultimately periodic.

For each finite word u on the alphabet A we set

x u = {n ∈ ω | x n x n+1 • • • x n+|u|-1 = u}.
In other words, x u denotes the set of all occurrences of u in x. We say x is recurrent if for every u ∈ Fac x the set x u is infinite. We say x is uniformly recurrent if for every u ∈ Fac x the set x u is syndedic, i.e., of bounded gap.

A characterisation for periodicity

We begin by establishing some preliminary results needed in the proof of our main result (see Theorem 5). Throughout this section A will denote a finite nonempty set.

Lemma 2. Let C, N ∈ Z + and x ∈ A ω be such that p x (n) = n + C for all n ≥ N. 1 Then there exist distinct letters a, b ∈ A and, for each n ≥ N, a unique factor r n ∈ Fac x (n) having exactly two right extensions in x of length n + 1 given by r n a and r n b, while all other factors of x of length n have a unique right extension in x to a factor of length n + 1.

Proof. Clearly for each n ≥ 0, each word u ∈ Fac x (n) is a prefix of at least one word v ∈ Fac x (n + 1). Now since p x (n + 1) -p x (n) = 1 for each n ≥ N, it follows that for each n ≥ N, there exists a unique factor r n of x of length n having exactly two right extensions r n a n and r n b n to a factor of x of length n + 1, where a n and b n are distinct letters in A, and all other factors of x of length n have a unique right extension to a factor of length

n + 1. Moreover, since r n is necessarily a suffix of r n+1 it follows that {a n , b n } = {a n+1 , b n+1 }, whence there exist distinct letters a, b ∈ A such that {a, b} = {a n , b n } for each n ≥ N. Lemma 3. Let C, N ∈ Z + and x ∈ A ω be such that p x (n) = n + C for all n ≥ N. If x is recurrent,
then there exist distinct letters a, b ∈ A and, for each n ≥ N, a unique factor l n ∈ Fac x (n) having exactly two left extensions in x of length n + 1 given by al n and bl n while all other factors of x of length n have a unique left extension in x to a factor of length n + 1.

Proof. The proof is identical to that of Lemma 2 with prefix replaced by suffix and right replaced by left. Proposition 4. Let C, N ∈ Z + and x ∈ A ω be such that p x (n) = n + C for all n ≥ N. Then there exists a uniformly recurrent suffix y of x.

Proof. We begin by showing that there exists a recurrent suffix y of x. Then we show this same suffix is uniformly recurrent. Let a, b ∈ A and

r n ∈ Fac x (n) (n ≥ N ) be as in Lemma 2. Let R = {u ∈ A + : |u| ≤ N, Card(x u ) < +∞}.
In other words, R is the set of all non-recurrent factors u of x with |u| ≤ N. Pick a suffix y of x such that y u = ∅ for all u ∈ R. We claim that y is recurrent. In fact, supposing y were not recurrent, let v be the shortest non-recurrent prefix of y and let y be a suffix of y such that

y v = ∅. Then |v| > N otherwise v belongs to R. Let u be the prefix of v of length |v| -1 so that v = uc for some c ∈ A. Set n = |u|.
Then n ≥ N and since u is recurrent in y and v = uc is not recurrent in y, it follows that u is a right special factor of x and hence by Lemma 2 u = r n and c ∈ {a, b}. Moreover, since u is the unique right special factor of x of length n and the only right extensions of u in x of length n + 1 are ua and ub, it follows that the suffix y of y contains no right special factors of length n. In other words, p y (n + 1) = p y (n) whence y is ultimately periodic, a contradiction. Next we show y is uniformly recurrent. It suffices to show that every prefix u of y of length |u| ≥ N occurs in y with bounded gap. Since y is recurrent, every prefix u of y is contained in a right special prefix of y. Thus it suffices to show that every right special prefix u of y with |u| ≥ N occurs in y with bounded gap. So let us fix a right special prefix u of y with |u| ≥ N. Set n = |u| and consider any factor w of y of length 2n + C. We claim that u occurs in w. In fact, there are n + C + 1 occurrences in w of words of length n. Since p y (n) ≤ p x (n) = n + C, there exists some factor v of y of length n occurring at least twice in w. Let z be a factor of w which begins and ends in v and of length |z| > |v|. Since y is aperiodic, there exists a right special prefix z of z of length |z | ≥ |v| = n. Then by Lemma 2 we deduce that u is a suffix of z and hence u occurs in w as required.

Theorem 5. A word x ∈ A ω is ultimately periodic if and only if χ(x) = 1 where

χ(x) = inf{lim sup p S (n) : S ⊆ A * , Fac x ⊆ S 2 } Proof. One direction is straightforward. Suppose x = uv ω for some u, v ∈ A + . Let S = Fac uv ∪ Pref(v ω ).
We claim Fac x ⊆ S 2 from which it follows that χ(x) = 1 (since p S (n) = 1 for all n ≥ |uv|+1). In fact, let w ∈ Fac x . If w ∈ Fac uv , then w ∈ S and so w = w • ε ∈ S 2 . Otherwise, we can write w = w w ∈ S 2 where w is a suffix of uv and w a prefix of v ω .

For the reverse implication, let us assume that x ∈ A ω and χ(x) = 1. Fix S ⊆ A * and a positive integer N 0 with Fac x ⊆ S 2 and p S (n) ≤ 1 for all n ≥ N 0 .

Without loss of generality, we may assume that p S (n) = 1 for all n ≥ N 0 . In fact, we could extend S to a set S by adding to S an arbitrary element of A n for each n such that S ∩ A n = ∅. Then Fac x ⊆ S2 and p S (n) = 1 for all n ≥ N 0 . Lemma 6. Assume x ∈ A ω , S ⊆ A * and N 0 ∈ Z + are such that Fac x ⊆ S 2 and p S (n) = 1 for all n ≥ N 0 . Then either x is ultimately periodic, or there exist positive integers C, N with

N ≥ 2N 0 such that p x (n) = n + C for all n ≥ N. Proof. Assume x is aperiodic. Let C 0 = max{p S (n) | 0 ≤ n < N 0 }. Fix n ≥ 2N 0 . Each w ∈ Fac x (n)
p x (n + 1) ≥ p x (n) + 1 = n + 1 + C. Thus p x (n + 1) = n + 1 + C as required.
Returning to the proof of Theorem 5, we wish to show that if x ∈ A ω , S ⊆ A * and N 0 ∈ Z + are such that Fac x ⊆ S 2 and p S (n) = 1 for all n ≥ N 0 , then x is ultimately periodic. In view Lemma 6 combined with Proposition 4, short of replacing x by a suffix of x, we may assume without loss of generality that x itself is uniformly recurrent. So henceforth in proof of Theorem 5, we will assume that x ∈ A ω is uniformly recurrent, S ⊆ A * and N 0 ∈ Z + are such that Fac x ⊆ S 2 and p S (n) = 1 for all n ≥ N 0 . As before let

C 0 = max{p S (n) | 0 ≤ n < N 0 }. We note C 0 ≥ 1.
We propose to show that x is ultimately periodic. So suppose to the contrary that x is aperiodic. Let N and C be as in Lemma 6. Also set d = 2(N 0 -1)(C 0 -1).

(2)

We will show that for each K ≥ max{4, N, 6d + 1} there exists z ∈ A 2 such that z K 2 ∈ Fac x . As x is assumed to be uniformly recurrent, this will give the desired contradiction.

For each i ≥ N 0 , let s i denote the unique element of S of length i. For each n ≥ N, let

d n = Card{i : N 0 ≤ i ≤ n -N 0 , s i s n-i / ∈ Fac x }.
Recall that each factor w of x of length n is a product uv with u, v ∈ S. Thus d n corresponds to the number of factorisations uv with N 0 ≤ |u|, |v| ≤ n -N 0 which are not needed in generating all factors of x of length n. Hence, for each n ≥ N, a refinement of the estimation used in the proof of Lemma 6 yields:

2C 0 (N 0 -1) + n -2N 0 + 3 -d n ≥ p x (n) ≥ n + 1 (3)
where the last inequality is a consequence of the Morse-Hedlund theorem as we are assuming that x is aperiodic. It follows from ( 2) and ( 3) that d n ≤ d.

For n ≥ N, let

U (n) = {u ∈ S | N 0 ≤ |u| ≤ n -N 0 ,
and ∃v ∈ S with {uv, vu} ⊆ Fac x (n)}.

We note that our assumption on p S (n) implies that if u ∈ U (n), then there exists a unique v ∈ S with {uv, vu} ⊆ Fac x (n) and v too belongs to U (n). In other words, if

s i s n-1 / ∈ Fac x (n) for N 0 ≤ i ≤ n -N 0 , then s i / ∈ U (n) and s n-1 / ∈ U (n). Thus Card U (n) ≥ n -2N 0 + 1 -2d n ≥ n -2N 0 + 1 -2d. (4)
Let B x = {B 0 , B 1 , B 2 , . . .} denote the infinite set of bispecial factors of x and set b i = |B i |. We order B x so that b m < b m+1 for each m ≥ 0. Recall that by Lemma 6, we have p x (n) = n + C for each n ≥ N and hence by application of Lemma 2 and Lemma 3 it follows that x has a unique right and left special factor, denoted r n and l n , of each length n ≥ N. Hence given any two bispecial factors of x each of length greater or equal to N, the shorter of the two is both a prefix and a suffix of the other. Since x is uniformly recurrent, it follows that lim inf m→∞ (b m+1 -b m ) = +∞. In fact, if b m ≥ N then setting π m = b m+1 -b m we have that π m is a period of B m+1 .

Let K be any positive integer verifying K ≥ max{4, N, 6d + 1}. We will show that for each such K there exists z ∈ A 2 such that z

K 2 ∈ Fac x . Pick a positive integer m such that b m+1 -6K > b m > N,
and set n = b m + 2K. For convenience, we summarise the inclusions thus far

1 ≤ N 0 < N < b m < b m + K < n = b m + 2K < b m + 6K < b m+1 .
We claim there exists

u ∈ U (n) ∩ U (n + 1) ∩ U (n + 2) with b m < |u| ≤ b m + K. (5)
In fact, consider all elements u ∈ S of length b m < |u| ≤ b m + K. Then by ( 4) at most 2d of them do not belong to U (n). Of those which belong to U (n), at most 2d do not belong to U (n + 1). Of those which belong to U (n) ∩ U (n + 1), at most 2d do not belong to U (n + 2). Since K ≥ 6d + 1 the result follows. Thus there exists

{u, v (0) , v (1) , v (2) } ⊆ S with b m < |u| ≤ b m + K and {uv (i) , v (i) u} ⊆ Fac x (n + i) for each 0 ≤ i ≤ 2. We note that |v (i+1) | = |v (i) | + 1 and since |v (0) | = n -|u| = b m + 2K -|u| it follows from (5) that 2K > |v (0) | ≥ K. (6)
We now consider three possible cases: Case 1: uv (2) is a prefix of R(u) and v (2) u is a suffix of L (u). Case 2: There exists a proper prefix w of uv (2) of length |w| ≥ |u| which is a right special factor of x. Case 3: There exists a proper suffix w of v (2) u of length |w| ≥ |u| which is a left special factor of x.

In Case 1, every occurrence of u in x is an occurrence of uv (2) . Hence v (1) is a prefix v (2) . Similarly, every occurrence of u in x is immediately preceded by v (2) whence v (1) is also a suffix of v (2) . Hence v (2) = c k for some c ∈ A. Since k = |v (2)

| = |v (0) | + 2 ≥ K + 2, by taking z = c 2 we have that z K 2 ∈ Fac x .
In Case 2, we first claim that w is unique, i.e., w = R(u). In fact, suppose that w and w are both proper right special prefixes of uv (2) with |w | > |w| ≥ |u|. Then as w is also a suffix of w it follows that w occurs twice in uv (2) . Then L (w) is a bispecial factor of x contained in uv (2)

whence b m < |u| ≤ |w| ≤ |L (w)| ≤ |uv (2) | = n + 2 = b m + 2K + 2 < b m+1
a contradiction since b m and b m+1 are the lengths of consecutive bispecial factors of x. We next claim that at least two v (i) are prefixes of one another. In fact, if uv (0) is not a prefix of uv (1) , then for some choice of distinct letters a, b ∈ A we would have that wa is a prefix of uv (0) and wb is a prefix of uv (1) . We recall that by Lemma 2, w has only two right extensions in x of length |w| + 1, namely wa and wb. Thus if in addition uv (0) is not a prefix of uv (2) , then wb is a prefix of uv (2) . But then, since wb is a both a prefix of uv (1) and uv (2) and every occurrence in x of wb is an occurrence in x of uv (2) , it follows that uv (1) is a prefix of uv (2) . Finally we claim that no suffix w of v (2) u with |w | ≥ |u| is left special. In fact, if L (u) were a suffix of v (2) u, then L (w) = L (R(u)) is a bispecial factor of x contained in v (2) uv (2) , whence

b m < |u| ≤ |L (R(u))| ≤ |v (2) uv (2) | = |u|+2|v (2) | < b m +K +2(2K +2) = b m +5K +4 < b m+1
again a contradiction since b m and b m+1 are the lengths of consecutive bispecial factors of x. Thus in summary we have that each of the v (i) are suffixes of one another and at least two of the v (i) are prefixes of one another. Whence either v (1) or v (2) has period equal to 1 or 2.

In either case we have z K 2 is a factor of x for some z ∈ A 2 . Case 3 works similarly to Case 2. Using Lemma 3 we argue that each of the v (i) are prefixes of one another and at least two of the v (i) are suffixes of one another and hence either v (1) or v (2) has period equal to 1 or 2. This completes our proof of Theorem 5.

The character of Sturmian words

Let x = x 0 x 1 x 2 • • • ∈ {0, 1} ω be a Sturmian word, i.e., p x (n) = n + 1 for each n ≥ 0.
We will also make use of the balance characterisation of Sturmian words due to Morse and Hedlund in [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF] and Coven and Hedlund in [START_REF] Coven | Sequences with minimal block growth[END_REF]: x ∈ {0, 1} ω is Sturmian if and only if x is aperiodic and for any two factors u and v of x of equal length we have ||u| 0 -|v| 0 | ≤ 1. The slope s(x) is defined as the frequency of the symbol 1 in x, i.e.,

s(x) = lim n→∞ |x 0 x 1 • • • x n-1 | 1 n .
In [START_REF] Morse | Symbolic dynamics II. Sturmian trajectories[END_REF], Hedlund and Morse showed that this limit always exists and that x is the symbolic coding of the orbit of a point ρ(x), called the intercept, on the unit circle under a rotation by an irrational angle s(x), where the circle is partitioned into two complementary intervals, one of length s(x) and the other of length 1 -s(x). Conversely each such coding defines a Sturmian word. Moreover, the set of factors of a Sturmian word depends only on the slope: Let x, y be two Sturmian words. Then Fac x = Fac y if and only if x and y have the same slope. Let O(x) = {y ∈ A ω : Fac y = Fac x }.

The condition p x (n) = n + 1 implies that x admits a unique left and right special factor of each length n denoted l n and r n respectively. For each n ≥ 0 we have that l n is a prefix of l n+1 and r n is a suffix of r n+1 . Moreover, l n and r n are reversals of one another (see for instance Chapter 2 of [START_REF] Lothaire | Algebraic combinatorics on words[END_REF]). Let x * = lim n→∞ l n denote the characteristic word of slope s(x), i.e., x * is the unique word all of whose prefixes are left special factors of x. Theorem 7. Let x ∈ {0, 1} N be a Sturmian word. Then χ(x) = 2.

Proof. Fix a Sturmian word x ∈ {0, 1} ω of slope α. As x is aperiodic, it follows from Theorem 5 that χ(x) ≥ 2. Thus it suffices to show that Fac x ⊆ S 2 for some language S ⊆ {0, 1} * with lim sup p S (n) = 2. Set

S = {ε} ∪ {r n 0 | n ≥ 0} ∪ {1l n | n ≥ 0}.
Then S consists of precisely 2 words of each given length n ≥ 1. It remains to show that Fac x ⊆ S 2 . Lemma 8. Let x * denote the characteristic Sturmian word of slope s(x). Then for each n ≥ 0 we have that r n 01x * and r n 10x * belong to O(x).

Proof. Since each prefix of x * is a left special factor of x it follows that each of 0x * and 1x * belong to O(x) and moreover each has a unique infinite left extension (otherwise x * would be a suffix of itself and x * would be periodic). We recall that 0x * (1x * , respectively) is the lexicographically smallest (largest, respectively) element of O(x) (see for instance [START_REF] Pirillo | Inequalities characterizing standard Sturmian and episturmian words[END_REF]). It follows immediately from this lexicographic property that 0x * must extend to the left by 1 and that 1x * must extend to the left by 0 so that 10x * , 01x * ∈ O(x). We now claim that 10x * , 01x * have the same infinite left extension i.e., there exists a left infinite word w such that each suffix of w10x * and of w01x * belongs to O(x). It follows immediately that each suffix of w is a right special factor of x. To establish the claim let z (z , respectively) be the unique infinite left extensions of 10x * (01x * , respectively). We will show that z = z . Assume to the contrary that z = z . Then there exists u ∈ A * such that au is a suffix of z and bu is a suffix of z where {a, b} = {0, 1}. Since au1 and bu0 are each factors of x, by the balance property, we must have that a = 0 and b = 1. Since u is a left special factor of x we must have that either u0 or u1 is a prefix of x * . If u0 is a prefix of x * , then 1u0 is a prefix of 1x * and hence 1u0 is the lexicographically largest factor of x to its length. It follows that 1u01x * is lexicographically larger than 1x * , a contradiction. If on the other hand u1 is a prefix of x * , then 0u1 is a prefix of 0x * and hence 0u1 is the lexicographically smallest factor of x to its length. It follows that 0u10x * is lexicographically smaller than 0x * , a contradiction. This completes the proof of Lemma 8.

Returning to the proof of Theorem 7, it follows from Lemma 8 that the word w(n) = r n-1 01l n-1 is a factor of x of length 2n. We claim that for each n ≥ 1, w(n) contains n + 1 distinct factors of length n. To prove the claim, we proceed by induction on n. For n = 1, we have w(1) = 01 which contains 2 factors of length 1. For the inductive step, let n ≥ 1, and assume w(n) contains n + 1 distinct factors of length n. We wish to show that w(n + 1) contains n + 2 distinct factors of length n + 1. Suppose to the contrary that some word u of length n + 1 occurs twice in w(n + 1). We claim u = r n 0, for otherwise the word u obtained by deleting the last letter of u would occur twice in w(n), a contradiction. Similarly, if u = 1l n , then the word u obtained by deleting the first letter of u would occur twice in w(n), a contradiction. Thus u = r n 1 = 0l n , which is a contradiction since, as r n and l n are reversals of one another, |r n 1| 1 > |0l n | 1 . Having established the claim, it follows that each factor of x of length n is a factor of w(n) and hence Fac x ⊆ S 2 as required.

Potential generalisations

It would be interesting to determine the character of other classes of infinite words of sub-linear complexity including automatic words, words generated by primitive substitutions and Arnoux-Rauzy words. The precise determination of the character of a Sturmian word x consisted in showing that on one hand χ(x) ≥ 2 (Theorem 5) and on the other hand that χ(x) ≤ 2 (Lemma 8). Given a word x of sub-linear complexity, the proof of Theorem 1 in [START_REF] Cassaigne | Cost and dimension of words of zero topological entropy[END_REF] yields an explicit method for constructing a set S of bounded complexity for which Fac x ⊆ S 2 . This construction, which makes use of so-called D-markers (see §4.1 in [START_REF] Cassaigne | Cost and dimension of words of zero topological entropy[END_REF]), yields an upper bound on the character of a given word of sub-linear complexity. The difficulty in general is in obtaining a lower bound on the character. For example, let x ∈ {a 1 , a 2 , . . . , a k } N be an Arnoux-Rauzy word on a k-letter alphabet. Let x denote the corresponding characteristic word, i.e., the unique element of the subshift generated by x each of whose prefixes is a left special factor of x. It follows that for each n ≥ 1 there exist words u 1 (n), u 2 (n), . . . , u k (n) of length n such that each u i (n) terminates in the letter a i and u i (n)x belongs to the subshift generated by x. In other words, u i (n)x are the k-left extensions of length n of x. It is easy to see that each factor w of x may be written in the form w = uv where u is either empty or u = u i (n) for some 1 ≤ i ≤ k and n ≥ 1 and where v is either empty or a prefix of x. This decomposition of w is obtained by setting v (possibly empty) equal to the longest suffix of w which is a left special factor of x. It follows that Fac x ⊆ S 2 where S = {u i (n) : 1 ≤ i ≤ k ; n ≥ 1} ∪ Pref(x) ∪ {ε} and hence χ(x) ≤ k + 1. For example, if t is the Tribonacci word fixed by the substitution a → ab, b → ac, and c → a we obtain 2 ≤ χ(t) ≤ 4, where the lower bound is a consequence of Theorem 5. We note that in case x is Sturmian, the above upper bound yields χ(x) ≤ 3 which as we saw earlier is not optimal. Similarly, in the case of the Tribonacci word, a more careful analysis yields the upper bound χ(t) ≤ 3. We suspect that in fact χ(t) = 3 but we do not know how to improve the lower found on the character. It would be reasonable to conjecture in general that if x is an Arnoux-Rauzy word on a k-letter alphabet then χ(x) = k.

A similar analysis applies to the Thue-Morse word x = 0110100110010110 • • • fixed by the uniform substitution ϕ : 0 → 01 and 1 → 10. For each n ≥ 0 let t n = ϕ n (0) and t n = ϕ n (1) and let S be the set of all prefixes and all suffixes of t n and t n for all n ≥ 0. Since t n+1 = t n t n and t n+1 = t n t n it follows that S consists of at most 4 words of each given length. Finally it is easy to see that Fac x ⊆ S 2 and hence χ(x) ≤ 4.

For words of higher than linear complexity, things become even more difficult. For example, in [START_REF] Cassaigne | Cost and dimension of words of zero topological entropy[END_REF] it is shown that if x is a fixed point of the (non-primitive) morphism a → ab, b → b and c → ca (which is known to have quadratic complexity), then there does not exist a language S of bounded complexity such that Fac x ⊆ S 3 . On the other hand it is shown that there exists a language S of bounded complexity such Fac x ⊆ S k for some k ∈ {4, 5, 6}. It is also shown in [START_REF] Cassaigne | Cost and dimension of words of zero topological entropy[END_REF] that for every real number α ∈ (0, 1), there exists an infinite word x of complexity O(n 2+α ) such that Fac x is not contained in S k for any language S of bounded complexity and any positive integer k.

1 )

 1 may be written as w = uv with u, v ∈ S. Thus an upper bound for p x (n) is obtained by counting the number words of the form uv with u, v ∈ S and |u| + |v| = n. If u or v is in the range 1 ≤ |u|, |v| ≤ N 0 -1, then we obtain at most C 0 distinct words of the form uv with u, v ∈ S. While if u and v are in the range N 0 ≤ |u|, |v| ≤ n -N 0 or {|u|, |v|} = {0, n}, then we obtain at most 1 word of the form uv with u, v ∈ S. Whence p x (n) ≤ 2C 0 (N 0 -1) + n -2N 0 + 3. (Thus setting C 1 = 2C 0 (N 0 -1) -2N 0 + 3 we have that p x (n) ≤ n + C 1 for all n ≥ 2N 0 . Let C ≤ C 1 be the largest positive integer for which we have p x (n) = n + C for some n ≥ 2N 0 , and pick N ≥ 2N 0 such that p x (N ) = N + C. Then it is readily checked by induction that p x (n) = n + C for all n ≥ N. In fact, if for n ≥ N we have p x (n) = n + C, then by maximality of the choice of C we have p x (n + 1) ≤ n + 1 + C. On the other hand since x is aperiodic,

Infinite words x of complexity p x (n) = n + C for all n sufficiently large were studied and characterised by A. Heinis in his doctoral thesis. He proved that every such word is a morphic image of a Sturmian word (see also[START_REF] Heinis | Languages under substitutions and balanced words[END_REF]).