Aldo De Luca
email: aldo.deluca@unina.it

Luca Q Zamboni

On some variations of coloring problems of infinite words

Keywords: Ramsey theory, combinatorics on words. 2010 MSC: 5D10, 68R15

Given a finite coloring (or finite partition) of the free semigroup A + over a set A, we consider various types of monochromatic factorizations of right sided infinite words x ∈ A ω . Some stronger versions of the usual notion of monochromatic factorization are introduced. A factorization is called sequentially monochromatic when concatenations of consecutive blocks are monochromatic. A sequentially monochromatic factorization is called ultra monochromatic if any concatenation of arbitrary permuted blocks of the factorization has the same color of the single blocks. We establish links, and in some cases equivalences, between the existence of these factorizations and fundamental results in Ramsey theory including the infinite Ramsey theorem, Hindman's finite sums theorem, partition regularity of IP sets and the Milliken-Taylor theorem. We prove that for each finite set A and each finite coloring ϕ : A + → C, for almost all words x ∈ A ω , there exists y in the subshift generated by x admitting a ϕ-ultra monochromatic factorization, where "almost all" refers to the Bernoulli measure on A ω .

Introduction and preliminaries

Let A be a non-empty set, or alphabet, and A + denote the free semigroup over A, i.e., the set of all finite words x = x 0 x 1 • • • x n with x i ∈ A, 0 ≤ i ≤ n. Adding to A + an identity element ε, usually called empty word, one obtains the free monoid A * . Let A ω denote the set of all right sided infinite words x = x 0 x 1 • • • with x i ∈ A, i ≥ 0. For x ∈ A ω we let Fact(x) = {x i x i+1 • • • x i+j | i, j ≥ 0} denote the set of (non-empty) factors of x. A word x ∈ A ω is said to be (purely) periodic if x = u ω , u ∈ A + , and ultimately periodic if some suffix of x is periodic. A word x is called aperiodic if it is not ultimately periodic.

Let ϕ : A + → C be any mapping of A + into a finite non-empty set C. We call the elements of C colors and ϕ a finite coloring of A + . We consider three general notions of monochromatic factorization of x relative to the coloring ϕ. Definition 1. Let ϕ : A + → C be a finite coloring of A + and x ∈ A ω . A factorization

x = V 0 V 1 V 2 • • • with each V i ∈ A + is called • ϕ-monochromatic if ∃c ∈ C such that ϕ(V i ) = c for all i ≥ 0. • ϕ-sequentially monochromatic if ∃c ∈ C such that ϕ(V i V i+1 • • • V i+j ) = c
for all i, j ≥ 0.

• ϕ-ultra monochromatic if ∃c ∈ C such that for all k ≥ 1, and all 0 ≤ n 1 < n 2 < • • • < n k , and all permutations σ of {1, 2, • • • , k} we have ϕ(V n σ(1)

V n σ(2) • • • V n σ(k) ) = c.
Clearly any ϕ-ultra monochromatic factorization is ϕ-sequentially monochromatic and any ϕsequentially monochromatic factorization is ϕ-monochromatic. We begin with some examples.

Let ϕ : A + → C be any finite coloring, and let x = u ω , u ∈ A + , be a periodic infinite word. Then the factorization x = u • u • u • • • is ϕ-monochromatic. In general this factorization need not be ϕ-sequentially monochromatic.

Let T = t 0 t 1 t 2 • • • ∈ {0, 1} ω denote the Thue-Morse infinite word, where t n is defined as the sum modulo 2 of the digits in the binary expansion of n.

T = 011010011001011010010 • • •
The origins of T go back to the beginning of the last century with the works of A. Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF][START_REF] Thue | Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen[END_REF] in which he proves amongst other things that T is overlap-free i.e., contains no word of the form uuu where u is a non-empty prefix of u.

Consider ϕ : {0, 1} + → {0, 1} defined by ϕ(u) = 0 if u is a prefix of T and ϕ(u) = 1 otherwise. It is easy to see that T may be factored uniquely as

T = V 0 V 1 V 2 • • • where each V i ∈ {0, 01, 011}. Since each V i is a prefix of T, it follows that this factorization is ϕ-monochromatic. Since V 1 V 2 =
010 is not a prefix of T, this factorization of T is not ϕ-sequentially monochromatic. Next consider the coloring ϕ : {0, 1} + → {0, 1, 2} defined by ϕ (u) = 0 if u is a prefix of T ending with 0, ϕ (u) = 1 if u is a prefix of T ending with 1, and ϕ (u) = 2 otherwise. We claim that T does not admit a ϕ -monochromatic factorization. In fact, suppose to the contrary that

T = V 0 V 1 V 2 • • • is a ϕ -monochromatic factorization. Since V 0 is a prefix of T, it follows that there exists a ∈ {0, 1} such that each V i is a prefix of T terminating with a. Pick i ≥ 1 such that |V i | ≤ |V i+1 |. Then aV i V i ∈ Fact(T). Writing V i = ua, (with u empty or in {0, 1} + ), we see aV i V i = auaua is an overlap, contradicting that T is overlap-free.
The following question1 was independently posed by T. Brown in [START_REF] Brown | Colorings of the factors of a word[END_REF] and by the second author in [START_REF] Zamboni | A Note on Coloring Factors of Words[END_REF]: Question 1. Let x ∈ A ω be non-periodic. Does there exist a finite coloring ϕ : A + → C relative to which x does not admit a ϕ-monochromatic factorization?

Various partial results in support of an affirmative answer to this question were obtained in [START_REF] De Luca | On prefixal factorizations of words[END_REF][START_REF] De Luca | A coloring problem for infinite words[END_REF][START_REF] Salo | Factor colorings of linearly recurrent words[END_REF]. In particular, it is shown that Question 1 admits an affirmative answer for all nonuniformly recurrent words and various classes of uniformly recurrent words including Sturmian words. What is immediate to see is that if x ∈ A ω is not periodic, then there exists a finite coloring ϕ : A + → {0, 1} relative to which no factorization of x is ϕ-sequentially monochromatic. In fact, it suffices to define ϕ(u) = 0 if u is a prefix of x and ϕ(u) = 1 otherwise. We claim that x does not admit a ϕ-sequentially monochromatic factorization. In fact, suppose to the contrary that

x = V 0 V 1 V 2 • • • is a ϕ-sequentially monochromatic factorization. Then since V 0 is a prefix of x, it follows that ϕ(V 0 ) = 0 and hence ϕ(V i V i+1 • • • V i+j ) = 0 for each i, j ≥ 0. In particular taking i = 1 we deduce that V 1 V 2 • • • V j is a prefix of x for each j ≥ 1. It follows that x = V 1 V 2 V 3 • • • , and hence x = V 0 x, whence x is periodic, a contradiction.
In the next sections, we establish links, and in some cases equivalences, between the existence of the factorizations given in Definition 1 and fundamental results in Ramsey theory including the infinite Ramsey theorem, Hindman's finite sums theorem, partition regularity of IP sets, and the Milliken-Taylor theorem. One of the main results is that for each finite set A and each finite coloring ϕ : A + → C, for almost all words x ∈ A ω , there exists y in the subshift generated by x admitting a ϕ-ultra monochromatic factorization, where "almost all" refers to the Bernoulli measure on A ω .

We conclude this section by introducing some notations and definitions which are relevant to subsequent sections. Given a set S and a positive integer k, let Σ k (S) denote the set of k-element subsets of S and Fin(S) the set of all finite subsets of S. We let N = {0, 1, 2, . . .} denote the set of natural numbers and N + = N \ {0} the set of positive integers. For F, G ∈ Fin(N), we write

F < G if max(F ) < min(G). Let x = x 1 x 2 • • • x n , x i ∈ A, 1 ≤ i ≤ n
, be a word. The quantity n is called the length of x and is denoted |x|. The length of ε is 0. For each word x and a ∈ A, we let |x| a denote the number of occurrences of a in x. The reversal of x is the word x ∼ = x n • • • x 1 . A factor y of a finite or infinite word x is called right special (resp., left special) if there exist two different elements a and b of A such that ya and yb (resp., ay and by) are factors of x.

Let x ∈ A ω . The factor complexity of x is the map λ x : Fact(x) → N defined as follows:

for any n ≥ 0, λ x (n) counts the number of distinct factors of x of length n. An occurrence of u ∈ Fact(x) in x is any integer n ≥ 0 such that x n x n+1 • • • x n+|u|-1 = u. A factor u of x ∈ A ω is called recurrent if u occurs
infinitely many times in x and uniformly recurrent if there exists an integer k such that in any factor of x of length k there is at least one occurrence of u. An infinite word x is called recurrent (resp., uniformly recurrent) if each of its factors is recurrent (resp., uniformly recurrent). As is well known [START_REF] Furstenberg | Recurrence in Ergodic Theory and Combinatorial Number Theory[END_REF] for any infinite word x there exists a uniformly recurrent word y such that Fact(y) ⊆ Fact(x).

We endow A ω with the topology generated by the metric d(x, y) = 1 2 n where n = min{k | x k = y k } whenever x = (x n ) n∈N and y = (y n ) n∈N are two elements of A ω . The resulting topology is generated by the collection of cylinders [a 0 , . . . , a n ], where for each n ≥ 0 and a

i ∈ A, 0 ≤ i ≤ n, [a 0 , . . . , a n ] = {x ∈ A ω | x i = a i for 0 ≤ i ≤ n}.
It can also be described as being the product topology on A ω with the discrete topology on A. In particular this topology is compact. The Bernoulli measure on A ω , where A is finite, is defined as the unique measure µ on the σ-algebra of A ω such that µ([a 0 , . . . ,

a n ]) = d -(n+1) with d = card(A). Let T : A ω → A ω denote the shift transformation defined by T : (x n ) n∈N → (x n+1 ) n∈N . The shift orbit of x is the set orb(x) = {T k (x) | k ≥ 0}, i.e.
, the set of all suffixes of x. By a subshift on A we mean a pair (X, T ) where X is a closed and T -invariant subset of A ω . A subshift (X, T ) is said to be minimal whenever X and the empty set are the only T -invariant closed subsets of X. With each x ∈ A ω is associated the subshift (X, T ) where X is the shift orbit closure of x. This subshift, denoted by Ω(x), is usually called the subshift generated by x. As is well known (see, for instance, [1, Theorem 10.8.9]) one has that

Ω(x) = {y ∈ A ω | Fact(y) ⊆ Fact(x)}.
If x is uniformly recurrent, then Ω(x) is minimal, so that any two words y and z in Ω(x) have exactly the same set of factors.

A word x ∈ {0, 1} ω is called Sturmian (cf., [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]Chap. 2]) if it is aperiodic and balanced, i.e., for all factors u and v of x such that |u| = |v| one has

||u| a -|v| a | ≤ 1, a ∈ {0, 1}.
It follows that each Sturmian word contains exactly one of the two factors 00 and 11. Alternatively, a binary infinite word x is Sturmian if x has a unique left (or equivalently right) special factor of length n for each integer n ≥ 0. This is equivalent to saying that for each n ≥ 0 the number of distinct factors of x of length n is exactly equal to n + 1. As a consequence one derives that a Sturmian word x is closed under reversal, i.e., if u is a factor of x, then so is its reversal u ∼ (see, for instance, [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]Proposition 2.1.19]). The most famous Sturmian word is the Fibonacci word f = 0100101001001010010 • • • which is the fixed point of the morphism F defined by

F : 0 → 01, 1 → 0.
For a ∈ {0, 1}, we consider the injective endomorphism L a of {0, 1} * defined by L a : a → a, b → ab. We recall [11, Proposition 2.3.1] that the image L a (y) of any Sturmian word y is a Sturmian word. Moreover, for any word y ∈ {0, 1} ω if L a (y) is a Sturmian word, then y is also Sturmian [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]Proposition 2.3.2].

An infinite word x ∈ A ω is r-power free, r > 1, if for each u ∈ Fact(x) one has u r ∈ Fact(x). For instance, the word T is 3-power free and f is 4-power free (see, for instance, [START_REF] Carpi | Special factors, periodicity, and an application to Sturmian words[END_REF]).

Main results

Given any finite coloring ϕ of A + and any infinite word x ∈ A ω , while it may happen as we have previously seen, that x does not admit a ϕ-monochromatic factorization, M. P. Schützenberger proved that for each finite coloring ϕ of A + and each infinite word x ∈ A ω there exists always a suffix of x admitting a ϕ-monochromatic factorization (see [START_REF] Schützenberger | Quelques problèmes combinatoires de la théorie des automates[END_REF]). The next theorem however provides a remarkable strengthening of Schützenberger's result.

Theorem 1. The following statements are equivalent:

1. For any finite coloring ϕ : A + → C and any word x ∈ A ω , there exists a suffix x of x which admits a ϕ-sequentially monochromatic factorization. 2. For each finite coloring ϕ : Σ 2 (N) → C, there exist c ∈ C and an infinite set

N ⊆ N such that Σ 2 (N ) ⊆ ϕ -1 (c).
Proof. We note that item (2) is a special case of the Infinite Ramsey's Theorem (see [START_REF] Graham | Ramsey Theory[END_REF]). We begin by showing that (2) =⇒ (1). Let ϕ : A + → C be any finite coloring, and

x = x 0 x 1 x 2 • • • ∈ A ω . Then ϕ induces a finite coloring ϕ : Σ 2 (N) → C given by ϕ ({m < n}) = ϕ(x m x m+1 • • • x n-1 )
. By (2) there exists c ∈ C and an infinite subset

N = {n 0 < n 1 < n 2 < • • • } of N such that for all m, n ∈ N with m < n we have ϕ ({m < n}) = c. It follows that the factorization of the suffix x = x n 0 x n 0 +1 x n 0 +2 • • • given by x = V 0 V 1 V 2 • • • where |V i | = n i+1 -n i is ϕ-sequentially monochromatic.
To see that (1) =⇒ ( 2), let ϕ : Σ 2 (N) → C be any finite coloring of Σ 2 (N). Let x ∈ {0, 1} ω be any aperiodic word. Then ϕ induces a finite coloring ϕ : A + → C ∪ { * }, where * denotes a symbol not in C, defined as follows: For each u ∈ A + , if u / ∈ Fact(x), then set ϕ (u) = * . Otherwise, let m(u) be the least natural number m such that u = x m x m+1 • • • x m+|u|-1 , that is m(u) is the first occurrence of u in x. Then we put ϕ (u) = ϕ({m(u), m(u) + |u|}).

By (1) there exists n ≥ 0 such that the suffix

x = x n x n+1 x n+2 • • • of x admits a ϕ -sequentially monochromatic factorization x = V 0 V 1 V 2 • • • . Put c = ϕ (V 0 ). Since V 0 ∈ Fact(x) we have c ∈ C. Also, as x is aperiodic, there exists s ≥ 0 such that n = m(V 0 V 1 • • • V s ). Indeed, set x = U x with |U | = n. The statement is clear if n = 0. Otherwise, if for each s, m(V 0 V 1 • • • V s ) < n, then by the pigeonhole principle there exists 0 ≤ k < n such that k = m(V 0 V 1 • • • V s )
for infinitely many values of s. This implies that x = T k (x) = T n (x), whence x is purely periodic and hence x is ultimately periodic, a contradiction.

Similarly, for each r ≥ 1 there exists

s ≥ r such that m(V r • • • V s ) = n + r-1 i=0 |V i |. Given any increasing sequence 0 = n 0 < n 1 < n 2 < • • • , put W k = V n k V n k +1 • • • V n k+1 -1 . Then clearly the factorization x = W 0 W 1 W 2 • • • is also ϕ -sequentially monochromatic.

Thus we can assume that

x admits a ϕ -sequentially monochromatic factorization

x = V 0 V 1 V 2 • • • , such that m(V 0 ) = n and m(V r ) = n + r-1 i=0 |V i | for each r ≥ 1. Setting N = {n < n + |V 0 | < • • • < n + r i=0 |V i | < • • • },
we have Σ 2 (N ) ⊆ ϕ -1 (c) as required.

Example 1. Let x = 010110111011110 • • • . Consider the finite coloring ϕ : {0, 1} + → {0, 1} defined by ϕ(u) = 0 if u is a prefix of x, and ϕ(u) = 1 otherwise. Following [6, Lemma 3.4], since 0 is not uniformly recurrent in x, it follows that x does not admit a prefixal factorization, i.e., x is not a concatenation of its prefixes. It follows that x does not admit a ϕ-monochromatic factorization. In contrast, by Theorem 1, for every finite coloring ϕ : {0, 1} + → C, there exists a suffix of x which admits a ϕ-sequentially monochromatic factorization. Finally, let ϕ : {0, 1} + → {0, 1} be defined by ϕ(u) = 0 if u is a factor of x, and ϕ(u) = 1 otherwise. We claim that no suffix of x admits a ϕ-ultra monochromatic factorization. In fact, suppose to the contrary that some suffix x of x admits a ϕ-ultra monochromatic factorization

x = V 0 V 1 V 2 • • • .
By concatenating several of the V i together (as in the proof of Theorem 1), we can assume that each V i contains at least two occurrences of 0. Then, V j V i is not a factor of x whenever i < j.

Thus 0 = ϕ(V 0 ) = ϕ(V j V i ) = 1.
The following proposition illustrates how in some very special cases, Theorem 1 can be used to construct an ultra monochromatic factorization: Proposition 2. Let C be a finite semigroup and ϕ : A + → C a morphism. Let x ∈ A ω . There exists a suffix x of x which admits a ϕ-ultra monochromatic factorization.

Proof. By Theorem 1 there exists a suffix x of x which admits a ϕ-sequentially monochromatic factorization

x = V 0 V 1 • • • V n • • • . Thus there exists c ∈ C such that for all i ≥ 0, one has ϕ(V i • • • V i+j ) = c, for all i, j ≥ 0. This implies ϕ(V 0 V 1 ) = c = ϕ(V 0 )ϕ(V 1 ) = c 2 . Therefore, c is an idempotent of the semigroup C. Thus ϕ(u) = c for any u ∈ {V i | i ≥ 0} + . Whence the factorization x = V 0 V 1 • • • V n • • • is also ϕ-ultra monochromatic.
In view of the preceding results, it is natural to ask the following question: Question 2. Let ϕ : A + → C be a finite coloring of A + and x ∈ A ω . Does there exist y ∈ Ω(x) admitting a ϕ-ultra monochromatic factorization?

It turns out that in general Question 2 does not admit an affirmative answer. We begin by exhibiting a ϕ : A + → C and x ∈ A ω such that no y ∈ Ω(x) admits a ϕ-ultra monochromatic factorization.

Lemma 1. Let r ∈ N + and x ∈ {0, 1} ω be a r-power free Sturmian word. Then for each infinite sequence

ω = V 0 , V 1 , V 2 , • • • with V i ∈ {0, 1} + there exist k ≥ 1, 0 ≤ n 1 < n 2 < • • • < n k , and a permutation σ of {1, 2, . . . , k} such that V n σ(1) V n σ(2) • • • V n σ(k) / ∈ F act(x).
the case of any infinite word of linear factor complexity.

Proposition 3. Let r ∈ N + and x ∈ {0, 1} ω be a r-power free Sturmian word. Define ϕ : {0, 1} + → {0, 1} by ϕ(u) = 0 if u is a factor of x and ϕ(u) = 1 otherwise. Then no y ∈ Ω(x) admits a ϕ-ultra monochromatic factorization.

Proof. Let y ∈ Ω(x) and consider any factorization

y = V 0 V 1 V 2 • • • .
Then since V 0 is a factor of x, we have that ϕ(V 0 ) = 0. On the other hand, since y is also Sturmian and r-power free, by the previous lemma there exist

k ≥ 1, 0 ≤ n 1 < n 2 < • • • < n k and a permutation σ of {1, 2, . . . , k} such that V n σ(1) V n σ(2) • • • V n σ(k) / ∈ Fact(y). Hence ϕ(V n σ(1) V n σ(2) • • • V n σ(k) )
= 1 from which it follows that no y ∈ Ω(x) admits a ϕ-ultra monochromatic factorization.

We next show (cf. Corollary 1) that if A is finite, then Question 2 admits an affirmative answer for almost all x ∈ A ω , where "almost all" refers to the Bernoulli measure on A ω . We begin by showing that Question 2 admits a positive answer in case x is periodic. Even this simplest case however turns out to be somewhat nontrivial, and in fact is equivalent to the so-called Finite Sums Theorem proved by N. Hindman in [START_REF] Hindman | Finite sums of sequences within cells of a partition of N[END_REF].

Theorem 4. The following statements are equivalent:

1. For every finite coloring ϕ : A + → C, each periodic word x ∈ A ω admits a ϕ-ultra monochromatic factorization. 2. For each finite coloring ϕ : N + → C of the positive integers, there exist c ∈ C and an infinite sequence

(n k ) ∞ k=0 such that FS((n k ) ∞ k=0 ) = { i∈F n i |F ∈ Fin(N)} ⊆ ϕ -1 (c).
Proof. We note that item (2) is the Finite Sums Theorem by Hindman. We begin by showing that (1) =⇒ [START_REF] Baumgartner | A short proof of Hindman's theorem[END_REF]. Let ϕ : N + → C be a finite coloring of the positive integers, and let x be the periodic word x = a ω , with a ∈ A. Then ϕ induces a finite coloring ϕ : {a} + → C given by ϕ (a n ) = ϕ(n). By (1) there exists a ϕ -ultra monochromatic factorization

x = V 0 V 1 V 2 • • • . Put c = ϕ (V 0 ). For k ≥ 0, set n k = |V k | so that each V k = a n k . Then for each finite subset F of N, we have ϕ( i∈F n i ) = ϕ( i∈F |V i |) = ϕ(| i∈F V i |) = ϕ ( i∈F V i ) = c since i∈F V i = a i∈F n i and hence is a factor of x. Whence FS((n k ) ∞ k=0 ) = { i∈F n i |F ∈ Fin(N)} ⊆ ϕ -1 (c).
To see that (2) =⇒ (1), let ϕ :

A + → C, u ∈ A + , and x = u ω . Define ϕ : N + → C by ϕ (n) = ϕ(u n ). By (2) there exist c ∈ C and an infinite sequence (n k ) ∞ k=0 such that FS((n k ) ∞ k=0 ) = { i∈F n i |F ∈ Fin(N)} ⊆ ϕ -1 (c). For each k ≥ 0 set V k = u n k . Then clearly the factorization x = V 0 V 1 V 2 • • • is ϕ-ultra monochromatic.
As an immediate consequence we obtain: Corollary 1. Let A be a finite set, and let µ be the Bernoulli measure on A ω . Let ϕ : A + → C be any finite coloring. Then for µ-almost all x ∈ A ω there exists y ∈ Ω(x) which admits a ϕ-ultra monochromatic factorization.

Proof. As is well known almost all words x ∈ A ω with respect to the measure µ, are of full complexity, meaning Fact(x) = A + (see, for instance, [START_REF] Allouche | Automatic Sequences: Theory, Applications, Generalizations[END_REF]Theorem 10.1.6]). (As an example, normal words [START_REF] Niven | Irrational numbers[END_REF]Chap. 8] are of full complexity). Thus for almost all words x ∈ A ω , relatively to measure µ, there exists a ∈ A such that a ω ∈ Ω(x). The result now follows from Theorem 4.

The above results suggest the following questions: Question 3. Let x ∈ A ω be a uniformly recurrent word. Suppose that for each ϕ : A + → C, there exists y ∈ Ω(x) admitting a ϕ-ultra monochromatic factorization. Then does it follow that x is periodic?

Let ϕ : A + → C and x ∈ A ω . A factorization x = V 0 V 1 V 2 • • • with V i ∈ A + , i ≥ 0, is called ϕ-conditionally monochromatic if ∃c ∈ C such that ∀k ≥ 1, for all n 1 < n 2 < • • • < n k and
for all permutations σ of {1, 2, . . . , k} we have either

V n σ(1) V n σ(2) • • • V n σ(k) / ∈ Fact(x) or ϕ(V n σ(1) V n σ(2) • • • V n σ(k) ) = c.
Thus a ϕ-ultra monochromatic factorization of a word x ∈ A ω is a ϕ-conditionally monochromatic factorization, but not vice versa. For instance, consider x = 010110111011110 • • • . We saw in Example 1 that relative to the coloring ϕ : {0, 1} + → {0, 1} defined by ϕ(u) = 0 if u is a factor of x, and ϕ(u) = 1 otherwise, no suffix of x admits a ϕ-ultra monochromatic factorization. On the other hand given any coloring ϕ of {0, 1} + , by Theorem 1 there exists a suffix x admitting a ϕ-sequentially monochromatic factorization x = V 0 V 1 V 2 • • • . By concatenating several of the V i together (as in the proof of Theorem 1), we can assume that each V i contains at least two occurrences of 0. The resulting ϕ-sequentially monochromatic factorization is then also ϕ-conditionally monochromatic since the only concatenation of blocks which yields a factor of x are consecutive concatenations.

Question 4. Let ϕ : A + → C be a finite coloring of A + and x ∈ A ω . Does there exist y ∈ Ω(x) admitting a ϕ-conditionally monochromatic factorization?

We have not a single example of an aperiodic uniformly recurrent word in which we can give an answer (positive or negative) to the above question.

Shift invariant monochromatic factorizations

Let ϕ : A + → C be a finite coloring of A + , x ∈ A ω , and k be a positive integer. A ϕmonochromatic (resp., ϕ-sequentially monochromatic, ϕ-ultra monochromatic) factorization

x = V 0 V 1 V 2 • • • is said to be k-shift invariant if for each 1 ≤ j ≤ k the induced factorization T j (x) = W 0 W 1 W 2 • • • with |W i | = |V i |, i ≥ 0, is ϕ-monochromatic (resp., ϕ-sequentially monochro- matic, ϕ-ultra monochromatic). A ϕ-monochromatic (resp., ϕ-sequentially monochromatic, ϕ- ultra monochromatic) factorization x = V 0 V 1 V 2 • • • is called shift invariant if for each positive integer j, the induced factorization T j (x) = W 0 W 1 W 2 • • • with |W i | = |V i | is ϕ-monochromatic (resp., ϕ-sequentially monochromatic, ϕ-ultra monochromatic).
We begin with the following simple variation of the infinite Ramsey theorem, whose proof is omitted as it is a simple iterated application of the usual version of Ramsey's theorem. Proposition 5. Let ϕ : Σ 2 (N) → C be a finite coloring and k a nonnegative integer. There exists an infinite set N ⊆ N and a sequence (c i ) k i=0 such that for each 0

≤ i ≤ k we have c i ∈ C and Σ 2 (N + i) ⊆ ϕ -1 (c i ).
As an immediate consequence we deduce that Corollary 2. Let ϕ : A + → C, x ∈ A ω , and k ≥ 1. Then there exists a suffix x of x which admits a k-shift invariant ϕ-sequentially monochromatic factorization.

Proof. As in the proof of Theorem 1, we apply the above variation of Ramsey's theorem to the coloring ϕ : Σ 2 (N) → C given by ϕ ({m < n}) = ϕ(x m x m+1 • • • x n-1 ). Proposition 6. A word x ∈ A ω is ultimately periodic if and only if for every finite coloring ϕ :

A + → C there exists a suffix of x which admits a shift invariant ϕ-monochromatic factorization.

Proof. Clearly, if x is ultimately periodic, and hence of the form x = uv ω for some u, v ∈ A * with v = ε, then for any ϕ :

A + → C, the factorization v • v • v • • • • of the suffix v ω is shift invariant ϕ-monochromatic.
Conversely, suppose x is aperiodic. Choose a recurrent word y ∈ Ω(x). Thus each prefix of y occurs infinitely often in x. Let ϕ : A + → {0, 1} be given by ϕ(u) = 0 if u is a prefix of y and ϕ(u) = 1 otherwise. Let x be any suffix of x. We claim that x does not admit a shift invariant ϕ-monochromatic factorization. In fact, suppose to the contrary that x admits a shift invariant ϕ-monochromatic factorization x = V 0 V 1 V 2 • • • . Since y is recurrent and each prefix of y occurs infinitely often in x, there exist 0 ≤ i < j such that if we consider the shifted factorizations

T i (x ) = W 0 W 1 W 2 • • • and T j (x ) = W 0 W 1 W 2 • • • , where |W i | = |W i | = |V i |
for each i ≥ 0, both W 0 and W 0 are prefixes of y. It follows that W i and W i are prefixes of y for each i ≥ 0. But since they are of equal length, we have W i = W i for each i ≥ 0. Thus T i (x ) = T j (x ) which implies that x is ultimately periodic, a contradiction.

We recall that a subset A of N + is called an IP set if A contains FS((n i ) ∞ i=1 ) for some infinite sequence (n i ) ∞ i=1 . In terms of IP sets, Hindman's theorem states that any finite coloring of N + contains a monochromatic IP set. By using the so-called Finite Unions Theorem, which is equivalent to Hindman's Finite Sums Theorem (cf. [START_REF] Baumgartner | A short proof of Hindman's theorem[END_REF][START_REF] Milliken | Ramsey's Theorem with sums or unions[END_REF]), one can show that IP sets in N + are partition regular, i.e., if A is an IP set and A = k i=1 A i , then there exists 1 ≤ i ≤ k such that A i is an IP set. We recall also the following well-known theorem of Milliken-Taylor [START_REF] Milliken | Ramsey's Theorem with sums or unions[END_REF][START_REF] Taylor | A canonical partition relation for finite subsets of ω[END_REF]: defined by

Ψ({n 1 < n 2 < • • • < n k }) = (ϕ((u 1 u 2 • • • u k ) n 1 ), ϕ((u 2 u 3 • • • u k u 1 ) n 2 ), . . . , ϕ((u k u 1 • • • u k-1 ) n k ).
u j • • • u k u 1 • • • u j-1 ) i∈F n i ) = c j .
This is a consequence of ( * ) by taking F i = {i} for 1 ≤ i < j, F j = F, and F j+i = {M + i} for 1 ≤ i ≤ k -j where M = max(F ). It follows that the factorization x = u n k u n k+1 u n k+2 • • • is shift invariant ϕ-ultra monochromatic.

By Theorem 7 F 1 < F 2 <

 712 there exist c = (c 1 , c 2 , . . . , c k ) ∈ C k and (n i ) ∞ i=1 such that • • • < F k with F i ∈ Fin(N + ), 1 ≤ i ≤ k. Fix 1 ≤ j ≤ k and F ∈ Fin({k, k + 1, k + 2, . . .}). We claim that ϕ((

The original formulation of the question was stated in terms of finite colorings of Fact(x) instead of A + .

Acknowledgments: We are indebted to Neil Hindman for his suggestions and we thank the two anonymous reviewers for their useful comments.

We proceed by induction on N (ω) to show that for each ω = V 0 , V 1 , V 2 , • • • with V i ∈ {0, 1} + , and each r-power free Sturmian word x there exist k ≥ 1, 0 ≤ n 1 < n 2 < • • • < n k and a permutation σ of {1, 2, . . . , k} such that

∈ Fact(x). The base case of the induction is when N (ω) = r + 1, i.e., |V 0

Let x be a r-power free Sturmian word. For a ∈ {0, 1}, put ā = 1 -a so that {a, ā} = {0, 1}. Fix a ∈ {0, 1} so that āā / ∈ Fact(x). First suppose that V i = V j = ā for some 0 ≤ i < j. In this case V i V j / ∈ Fact(x). Thus we can assume that at most one V i = ā. In this case, there

∈ Fact(x). For the inductive step, let N > r + 1, and suppose that for each

i ≥ 0 and N (ω) = N and let x be a r-power free Sturmian word. Without loss of generality we may assume 11 / ∈ Fact(x) and that x begins with 0. Note that if 11 / ∈ Fact(x) and x begins with 1, we can replace x with 0x which is Sturmian and r-power free. We claim that for some k ≥ 1, and

Suppose first that for some a ∈ {0, 1} there exist 0 ≤ i < j such that V i begins with a and

and x has exactly one right special factor of each length, it follows that V m V n = V n V m , from which one easily derives that V r m is a prefix of V n and hence in particular V r m ∈ Fact(x), a contradiction. Thus we may suppose that all V i begin with the same letter a ∈ {0, 1}. A similar argument shows that all V i terminate with the same letter b ∈ {0, 1}. Moreover, as 11 / ∈ Fact(x), either a or b must equal 0. Since Fact(x) is closed under reversal, short of replacing each V i in ω by its reversal, we may suppose that a = 0, i.e., each V i begins with 0. Thus V i 0 ∈ Fact(x) for each i ≥ 0. Now consider the morphism L 0 : 0 → 0, and 1 → 01. For each i ≥ 0, define

, . . . . Finally, as x begins with 0, define x ∈ {0, 1} ω by L 0 (x ) = x. Then, as is well known, x is a Sturmian word. Moreover, since x is r-power free, so is x and at least one

, and this is a contradiction to our inductive hypothesis.

We mention that very recently Anna Frid [7] has extended the validity of previous lemma to Theorem 7. Let k be a positive integer and ϕ : Σ k (N + ) → C a finite coloring. Then there exist c ∈ C and an infinite sequence

The next theorem shows that for each finite coloring ϕ : A + → C, and each periodic word x ∈ A ω there exists a shift invariant ϕ-ultra monochromatic factorization of x. We present two proofs, one uses the fact that IP sets are partition regular and the other uses the Milliken-Taylor Theorem.

Theorem 8. For each finite coloring ϕ : A + → C, each periodic word x ∈ A ω admits a shift invariant ϕ-ultra monochromatic factorization.

Proof. (First proof) Let ϕ :

Then by Hindman's theorem there exists an infinite sequence (n

). This implies that the factorization

By partition regularity of IP sets it follows that there exists an infinite sequence (n

are both ϕ-ultra monochromatic. Continuing in this way up to stage k, we can find an infinite sequence (n

i=1 such that for each 0 ≤ i ≤ k -1 the factorization

is ϕ-ultra monochromatic. Since T k (x) = x the result now follows.

(Second proof) As before let ϕ : A + → C be given, u = u 1 u 2 • • • u k ∈ A + , u i ∈ A, i = 1, . . . , k, and x = u ω . Then ϕ induces a finite coloring


Aldo De Luca
email: aldo.deluca@unina.it

Luca Q Zamboni

On prefixal factorizations of words

Keywords: Combinatorics on words, Prefixal factorization, Sturmian word, Coloring problems 2010 MSC: 68R15

We consider the class P 1 of all infinite words x ∈ A ω over a finite alphabet A admitting a prefixal factorization, i.e., a factorization

With each x ∈ P 1 one naturally associates a "derived" infinite word δ(x) which may or may not admit a prefixal factorization. We are interested in the class P ∞ of all words x of P 1 such that δ n (x) ∈ P 1 for all n ≥ 1. Our primary motivation for studying the class P ∞ stems from its connection to a coloring problem on infinite words independently posed by T. Brown and by the second author. More precisely, let P be the class of all words x ∈ A ω such that for every finite coloring ϕ :

In a recent paper (A coloring problem for infinite words, J. Combin. Theory (Ser. A) 125 (2014) 306-332), we conjectured that a word x ∈ P if and only if x is purely periodic. In this paper we prove that P P ∞ , so in other words, potential candidates to a counter-example to our conjecture are amongst the non-periodic elements of P ∞ . We establish several results on the class P ∞ . In particular, we prove that a Sturmian word x belongs to P ∞ if and only if x is nonsingular, i.e., no proper suffix of x is a standard Sturmian word.

Introduction

Let P denote the class of all infinite words x ∈ A ω over a finite alphabet A such that for every finite coloring ϕ : A + → C there exist c ∈ C and a factorization

x = V 0 V 1 V 2 • • • with ϕ(V i ) = c
for all i ≥ 0. Such a factorization is called ϕ-monochromatic. In [START_REF] De Luca | A coloring problem for infinite words[END_REF] we conjectured: Conjecture 1. Let x be an infinite word. Then x ∈ P if and only if x is (purely) periodic.

Various partial results in support of Conjecture 1 were obtained in [START_REF] De Luca | A coloring problem for infinite words[END_REF][START_REF] De Luca | On some variations of coloring problems of infinite words[END_REF][START_REF] Salo | Factor colorings of linearly recurrent words[END_REF]. Given x ∈ A ω , it is natural to consider the binary coloring ϕ : A + → {0, 1} defined by ϕ(u) = 0 if u is a prefix of x and ϕ(u) = 1 otherwise. Then any ϕ-monochromatic factorization is nothing more than a prefixal factorization of x, i.e., a factorization of the form x = U 0 U 1 U 2 • • • where each U i is a non-empty prefix of x. Thus a first necessary condition for a word x to belong to P is that x admits a prefixal factorization. Not all infinite words admit such a factorization, in fact as is shown in [START_REF] De Luca | A coloring problem for infinite words[END_REF], square-free words and Lyndon words do not admit a prefixal factorization.

Thus in the study of Conjecture 1, one can restrict to the class of words P 1 admitting a prefixal factorization. But in fact more is true. We prove that if x ∈ P 1 , then x has only finitely many distinct unbordered prefixes and admits a unique factorization in terms of its unbordered prefixes. This allows us to associate with each x ∈ P 1 a new infinite word δ(x) on an alphabet corresponding to the finite set of unbordered prefixes of x. In turn, the word δ(x) may or may not admit a prefixal factorization. In case δ(x) / ∈ P 1 , then δ(x) / ∈ P and from this one may deduce that x itself does not belong to P. This is for instance the case of the famous Thue-Morse infinite word t = t 0 t 1 t 2 • • • ∈ {0, 1} ω where t n is defined as the sum modulo 2 of the digits in the binary expansion of n, t = 011010011001011010010 • • •

The origins of t go back to the beginning of the last century with the works of A. Thue [START_REF] Thue | Über unendliche Zeichenreihen[END_REF][START_REF] Thue | Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen[END_REF] in which he proves amongst other things that t is overlap-free, i.e., contains no word of the form uuu where u is a non-empty prefix of u. It is readily checked that t admits a prefixal factorization, in particular t may be factored uniquely as

t = V 0 V 1 V 2 • • •
where each V i ∈ {0, 01, 011}. On the other hand, as is established later (see Example 4), the derived word δ(t) is the square-free ternary Thue-Morse word fixed by the morphism 1 → 123, 2 → 13, 3 → 1. Hence δ(t) / ∈ P 1 . This in turn implies that t / ∈ P. Concretely, consider the coloring ϕ : {0, 1} + → {0, 1, 2} defined by ϕ (u) = 0 if u is a prefix of t ending with 0, ϕ (u) = 1 if u is a prefix of t ending with 1, and ϕ (u) = 2 otherwise. We claim that t does not admit a ϕ -monochromatic factorization. In fact, suppose to the contrary that t = V 0 V 1 V 2 • • • is a ϕ -monochromatic factorization. Since V 0 is a prefix of t, it follows that there exists a ∈ {0, 1} such that each V i is a prefix of t terminating with a. Pick i ≥ 1 such that |V i | ≤ |V i+1 |. Then aV i V i ∈ Fact(t). Writing V i = ua, (with u empty or in {0, 1} + ), we see aV i V i = auaua is an overlap, contradicting that t is overlap-free.

In the study of Conjecture 1, one can further restrict to the subset P 2 of P 1 consisting of all x ∈ P 1 for which δ(x) ∈ P 1 . In this case, one can define a second derived word δ 2 (x) = δ(δ(x)) which again may or may not belong to P 1 . In case δ 2 (x) / ∈ P 1 , then not only is δ 2 (x) / ∈ P, but as we shall see neither are δ(x) and x. Continuing in this way, we are led to consider the class P ∞ of all words x in P 1 such that δ n (x) ∈ P 1 for all n ≥ 1. We prove that P ⊆ P ∞ , so in other words any potential counter-example to our conjecture is amongst the non-periodic words belonging to P ∞ . However, P = P ∞ . In fact, we prove in Sect. 6 that a large class of Sturmian words belong to P ∞ , while as proved in [START_REF] De Luca | A coloring problem for infinite words[END_REF], no Sturmian word belongs to P.

The paper is organized as follows: In Sect. 2 we give a brief overview of some basic definitions and notions in combinatorics on words which are relevant to the subsequent material. In Sect. 3 we study the basic properties of words admitting a prefixal factorization and in particular prove each admits a unique factorization in terms of its finite set of unbordered prefixes. From this we define the derived word δ(x). We prove amongst other things that if x is a fixed point of a morphism, then the same is true of δ(x).

In Sect. 4 we recursively define a nested sequence • • • ⊂ P n+1 ⊂ P n ⊂ • • • ⊂ P 1 where P n+1 = {x ∈ P n | δ(x) ∈ P n }, and study some basic properties of the set P ∞ = n≥1 P n .

In Sect. 5 we study the connection between the class P and the class P ∞ and prove that P ⊂ P ∞ . We also prove that if x ∈ P ∞ , then x is uniformly recurrent, from which we recover a result previously proved in [START_REF] De Luca | A coloring problem for infinite words[END_REF] via different techniques.

Sect. 6 is devoted to prefixal factorizations of Sturmian words. Any Sturmian word x = aS, where a ∈ {0, 1} and S a standard Sturmian word, admits a prefixal factorization. The main result of the section is that a Sturmian word x belongs to P ∞ if and only if no proper suffix of x is a standard Sturmian word.

Notation and Preliminaries

Given a non-empty set A, or alphabet, we let A * denote the set of all finite words u = u 1 u 2 • • • u n with u i ∈ A. The quantity n is called the length of u and is denoted |u|. The empty word, denoted ε, is the unique element in A * with |ε| = 0. We set A + = A * \ {ε}. For each word v ∈ A + , let |u| v denote the number of occurrences of v in u. In the following we suppose that the alphabet A is finite even though several results still hold for any alphabet.

Let u ∈ A * . A word v is a factor of u if there exist words r and s such that u = rvs; v is a

proper factor if v = u. If r = ε (resp., s = ε), then v is called a prefix (resp., a suffix) of u.
Given words u, v ∈ A + we say v is a border of u if v is both a proper prefix and a proper suffix of u. In case u admits a border, we say u is bordered. Otherwise u is called unbordered.

Let A ω denote the set of all one-sided infinite words

x = x 0 x 1 • • • with x i ∈ A, i ≥ 0. Given x ∈ A ω , let Fact + (x) = {x i x i+1 • • • x i+j | i, j ≥ 0}
denote the set of all non-empty factors of x. Moreover, we set Fact(x) = {ε} ∪ Fact + (x). The factor complexity of x is the map λ x : N → N defined as follows: for any n ≥ 0

λ x (n) = card(A n ∩ Fact(x)),
i.e., λ x (n) counts the number of different factors of x of length n. A factor u of a finite or infinite word x is called right special (resp., left special) if there exist two different letters a and b such that ua and ub (resp., au and bu) are factors of x. A factor u of x which is right and left special is called bispecial.

Given x = x 0 x 1 x 2 • • • ∈ A ω . A factor u of x ∈ A ω is called recurrent if u occurs in
x an infinite number of times, and is called uniformly recurrent if there exists an integer k such that every factor of x of length k contains an occurrence of u. An infinite word x is called recurrent (resp., uniformly recurrent) if each of its factors is recurrent (resp., uniformly recurrent).

Let x ∈ A ω and S denote the shift operator. The shift orbit of x is the set orb(x) = {S k (x) | k ≥ 0}, i.e., the set of all suffixes of x. The shift orbit closure of x is the set

Ω(x) = {y ∈ A ω | Fact(y) ⊆ Fact(x)}.
An infinite word x is called (purely) periodic if x = u ω for some u ∈ A + , and is called ultimately periodic if x = vu ω for some v ∈ A * , and u ∈ A + . It is easy to see via the pigeon hole principle that any recurrent ultimately periodic word is necessarily periodic. An infinite word x is called aperiodic if x is not ultimately periodic.

We say that two finite or infinite words x = x 0 x 1 . . . and y = y 0 y 1 . . . on the alphabets A and A respectively are word isomorphic, or simply isomorphic, and write x y, if there exists a bijection φ : A → A such that y = φ(x 0 )φ(x 1 ) . . . . For all definitions and notation not explicitly given in the paper, the reader is referred to the books [START_REF] Allouche | Automatic Sequences: Theory, Applications, Generalizations[END_REF][START_REF] Lothaire | Combinatorics on Words[END_REF][START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF].

Prefixal factorizations

Definition 1. We say that an infinite word x ∈ A ω admits a prefixal factorization if x has a factorization

x = U 0 U 1 U 2 • • • where each U i , i ≥ 0, is a non-empty prefix of x.
Some properties of words having a prefixal factorization have been proved in [START_REF] De Luca | A coloring problem for infinite words[END_REF]. We mention in particular the following: Lemma 2. Let x ∈ A ω be an infinite word having a prefixal factorization. Then the first letter of x is uniformly recurrent.

Given x = x 0 x 1 x 2 • • • ∈ A ω ,
we let U P (x) denote the set of all (non-empty) unbordered prefixes of x.

Proposition 3. Let x = x 0 x 1 x 2 • • • ∈ A ω .
The following conditions are equivalent:

1. x admits a prefixal factorization.

x admits a unique factorization of the form

x = U 0 U 1 U 2 • • • with U i ∈ U P (x) for each i ≥ 0. 3. card(U P (x)) < +∞. Proof. Let us first prove that if x admits a factorization x = U 0 U 1 U 2 • • • with U i ∈ U P (x)
, then such a factorization is necessarily unique. Indeed, suppose that there exists a different factorization

x = U 0 U 1 U 2 • • • with U i ∈ U P (x). Let n ≥ 0 be the first integer such that U n = U n . Without loss of generality we suppose that |U n | > |U n |. We can write U n = U n U n+1 • • • U n+p ξ, with p ≥ 0 and ξ prefix of U n+p+1 . Hence, U n is bordered, a contradiction.
We will now prove that 3. ⇒ 2. ⇒ 1. ⇒ 3. 3. ⇒ 2. We begin by assuming card(U P (x)) < +∞ and show how to construct a factorization of x in terms of unbordered prefixes of x. We define recursively an infinite sequence U 0 , U 1 , U 2 , . . . ∈ U P (x) such that U 0 U 1 • • • U n is a prefix of x for each n ≥ 0, U 0 is the longest unbordered prefix of x, and for n ≥ 1, U n is the longest unbordered prefix of x which is a prefix of (U 0 • • • U n-1 ) -1 x. For n = 0 we simply set U 0 to be the longest unbordered prefix of x. Note U 0 is well defined since card(U P (x)) < +∞. For the inductive step, let n ≥ 0 and suppose we have defined U 0 , . . . , U n with the required properties. We show how to construct U n+1 . Let V be the prefix of

x of length |U 0 • • • U n | + 1. Then since |V | > |U 0 | it follows that V is bordered. Let v denote
the shortest border of V. Then v ∈ U P (x) and by induction hypothesis that U n is unbordered it follows that |v| = 1. In other words,

(U 0 • • • U n ) -1
x begins with an unbordered prefix of x. Thus we define U n+1 to be the longest unbordered prefix of x which is a prefix of

(U 0 • • • U n ) -1 x. It follows immediately that U 0 • • • U n U n+1 is a prefix of x.
Thus we have proven that 3. ⇒ 2.. 2. ⇒ 1. This implication is trivially true.

1. ⇒ 3. If x = V 0 V 1 V 2 • • • is a prefixal factorization of x, then each prefix of x longer than |V 0 | is necessarily bordered. Hence, card(U P (x)) ≤ |V 0 |.
A direct proof of the equivalence of conditions 1. and 3. in the preceding proposition is in [START_REF] De Luca | A coloring problem for infinite words[END_REF]Lemma 3.7]. Following a well known result of Ehrenfeucht and Silberger, we also observe that an infinite word having a finite number of unbordered factors is purely periodic [START_REF] Ehrenfeucht | Periodicity and unbordered segments of words[END_REF].

Let P 1 denote the set of all infinite words x = x 0 x 1 x 2 • • • over any finite alphabet satisfying any one of the three equivalent conditions given in Proposition 3. For x ∈ P 1 let

x = U 0 U 1 U 2 • • • (1)
be the unique factorization of x with U i ∈ U P (x) for i ≥ 0. Let U P (x) = {U i | i ≥ 0} ⊆ U P (x), and set n x = card(U P (x)).

Given distinct elements U, V ∈ U P (x), we write

U ≺ V if min{i | U i = U } < min{i | U i = V },
in other words if the first occurrence of U in (1) is before the first occurrence of V in (1). Let

φ : {1, 2, . . . , n x } → U P (x)
denote the unique order preserving bijection. We define δ(x) ∈ {1, 2, . . . , n x } ω by

δ(x) = φ -1 (U 0 )φ -1 (U 1 )φ -1 (U 2 ) • • • .
Clearly φ(δ(x)) = x. We call δ(x) the derived word of x with respect to the morphism induced by the bijection φ : {1, 2, . . . , n x } → U P (x).

Example 1. Let A = {0, 1} and let f be the Fibonacci word over A,

f = 010010100100101001010010010100 • • • ,
which is fixed by the morphism (Fibonacci morphism) defined by 0 → 01, 1 → 0. It is readily verified that U P (f ) = U P (f ) = {0, 01} and that 01 ≺ 0. One has n f = 2 and φ(1) = 01, φ(2) = 0. The unique factorization of f in terms of U P (f ) is

f = (01)(0)(01)(01)(0)(01)(0)(01)(01)(0)(01)(01)(0)(01)(01)(0) • • • Hence, δ(f ) = 1211212112112121121 • • • , and δ(f ) f .
x = (1213)(12)(1)(1213)(12)(1213)(12)(1)(1213)(1213)(12)(1)(1213)(12)(1213)(12)(1)(1213) • • • and hence δ(x) = 123121231123121231 • • • . Remark 1.
In general, if x ∈ P 1 , the set U P (x) may be a proper subset of U P (x). For instance, consider x = 10f where f is the Fibonacci word. Then it is readily verified that U P (x) = {1, 10, 100} while U P (x) = {10, 100}.

We extend φ to a morphism φ : {1, 2, . . . , n x } + → U P (x) + .

Lemma 4. The morphism φ : {1, 2, . . . , n x } + → U P (x) + is injective.

Proof. Suppose w = φ(v) = φ(v ) with v, v ∈ {1, 2, . . . , n x } + .
Then w factors as a product of elements in U P (x). Since any such factorization is necessarily unique, it follows that v = v .

While, as is readily verified, every prefix w of x may be written uniquely as a product of unbordered prefixes of x, in general, as we saw in the example of 10f (see Remark 1), it may not be possible to factor w over U P (x). However, the following lemma proves that if w occurs in a prefixal factorization of x, then w = φ(v) for some factor v of δ(x).

Lemma 5. Let x = V 0 V 1 V 2 • • • be a prefixal factorization of x. Then there exists a (unique) fac- torization δ(x) = v 0 v 1 v 2 • • • such that φ(v i ) = V i for each i ≥ 0. Proof. Let x = U 0 U 1 U 2 • • • be the factorization of x in unbordered prefixes. Define r 0 = 0 and r n = n-1 i=0 |U i |.
In other words, r n corresponds to the position of U n in the preceding factorization. Similarly we define s 0 = 0 and s

n = n-1 i=0 |V i |. Then we claim that {s n | n ≥ 0} ⊆ {r n | n ≥ 0}.
In fact, suppose to the contrary that there exist indices i, j such that r j < s i < r j+1 . This implies that there exists k ≥ i, such that a prefix of V k (possibly all of V k ) is a proper suffix of U j . This is a contradiction since U j is unbordered. Thus we have proven that any prefixal factorization of x is also a factorization of x viewed as an infinite word over the alphabet U P (x). The result now follows.

Combining the two previous lemmas we obtain:

Corollary 6. Let x = V 0 V 1 V 2 • • • be a prefixal factorization of x. Then for each i ≥ 0 there exists a unique factor v i of δ(x) such that φ(v i ) = V i .
As another consequence:

Corollary 7. Suppose x ∈ P 1 is a fixed point of a morphism τ : A + → A + . Then there exists a morphism τ : {1, 2, . . . , n x } + → {1, 2, . . . , n x } + fixing δ(x) such that φ • τ = τ • φ. Proof. Applying τ to the unique factorization x = U 0 U 1 U 2 • • • with U i ∈ U P (x), we obtain a pre- fixal factorization x = τ (U 0 )τ (U 1 )τ (U 2 ) • • • . Writing δ(x) = a 0 a 1 a 2 • • • with a i ∈ {1, 2, . . . , n x } and φ(a i ) = U i , by Lemma 5 there exists a unique factorization δ(x) = v 0 v 1 v 2 • • • such that φ(v i ) = τ (U i ) = τ (φ(a i )) for each i ≥ 0. The result now follows by defining τ (a i ) = v i .
Example 3. As we saw in Example 2, the Tribonacci word x is in P 1 . It follows from the previous corollary that δ(x) is also a fixed point of a morphism τ : {1, 2, 3} + → {1, 2, 3} + which we can compute using the relation τ = φ -1 • τ • φ where τ denotes the Tribonacci morphism defined by 1 → 12, 2 → 13, 3 → 1. So

1 φ → 1213 τ → 1213121 φ -1 → 123 2 φ → 12 τ → 1213 φ -1 → 1 3 φ → 1 τ → 12 φ -1 → 2.
Thus δ(x) is fixed by the morphism defined by 1 → 123, 2 → 1, 3 → 2. It may be verified that in this example, δ(x) has the same factor complexity as x, namely it contains 2n + 1 distinct factors of each length n ≥ 0. However, unlike x which has a unique right and left special factor of each length, δ(x) has a unique left special factor of each length, and two right special factors of each length. It is also readily verified that δ(x) ∈ P 1 . In fact U P (δ(x)) = U P (δ(x)) = {1, 12, 123}, and 123 ≺ 12 ≺ 1. Thus we obtain the infinite word δ 2 (x) = δ(δ(x)) ∈ {1, 2, 3} ω which is a fixed point of a morphism τ verifying τ = φ -1 • τ • φ . We compute τ as before:

1 φ → 123 τ → 12312 φ -1 → 12 2 φ → 12 τ → 1231 φ -1 → 13 3 φ → 1 τ → 123 φ -1 → 1
and hence τ = τ, whence δ 2 (x) = x. Thus for each n ≥ 1 we have that δ n (x) ∈ P 1 and δ n (x) = x for n even and δ n (x) = δ(x) for n odd.

Remark 2. We note that by Lemma 2, if x ∈ P 1 , the first letter x F of x is uniformly recurrent in x, so that one can also define (see [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]) the bijection σ : {1, . . . , card(R x F )} → R x F , where R x F is the finite set of the first returns of x F to x F in x, and define the derived word D x F (x) with respect to the morphism induced by σ [START_REF] De Luca | A coloring problem for infinite words[END_REF]. The two derived words δ(x) and D x F (x) can be equal, as in the case of x equal to Fibonacci word; they can be different as in the case of Tribonacci word. In the case of a word aS where a ∈ {0, 1} and S is a standard Sturmian word, one has that δ(aS) is not defined (cf. Lemma 19), whereas D a (aS) is defined.

A hierarchy of words admitting a prefixal factorization

We may recursively define a nested collection of words

• • • ⊆ P n+1 ⊆ P n ⊆ • • • ⊆ P 1 by P n+1 = {x ∈ P n | δ(x) ∈ P n } and P ∞ = ∞ n=1 P n .
Hence, a word x ∈ P ∞ if and only if x ∈ P 1 and δ n (x) ∈ P 1 for all n ≥ 1. The previous example proves that the Tribonacci word belongs to P ∞ . Similarly, following Example 1, the Fibonacci word also belongs to P ∞ . In contrast, the following example proves that the Thue-Morse word does not belong to P ∞ .

Example 4. The Thue-Morse word t = 0110100110010110 • • • is fixed by the morphism τ defined by 0 → 01, 1 → 10. It is readily verified that t ∈ P 1 . In fact, U P (t) = U P (t) = {0, 01, 011} and 011 ≺ 01 ≺ 0. Let φ : {1, 2, 3} → U P (t) be given by 1 → 011, 2 → 01, 3 → 0. Then δ(t) is the fixed point of the morphism τ which we compute as in Example 3:

1 φ → 011 τ → 011010 φ -1 → 123 2 φ → 01 τ → 0110 φ -1 → 13 3 φ → 0 τ → 01 φ -1 → 2.
We thus obtain that τ is defined by 1 → 123, 2 → 13, 3 → 2 which is the well known Hall morphism [START_REF] Hall | Generators and relations in groups. The Burnside problem[END_REF]. Thus δ(t) is the so-called ternary Thue-Morse word which is well known to be square-free (cf. [START_REF] Allouche | Automatic Sequences: Theory, Applications, Generalizations[END_REF], [START_REF] Lothaire | Combinatorics on Words[END_REF]). It follows (cf. [START_REF] De Luca | A coloring problem for infinite words[END_REF]) that δ(t) does not admit a prefixal factorization, i.e., δ(t) / ∈ P 1 . Thus t / ∈ P 2 and hence t / ∈ P ∞ .

Let ≤ p denote the prefixal order in A * , i.e., for u, v ∈ A * , u ≤ p v if u is a prefix of v. We write u < p v if u is a proper prefix of v. For any word u ∈ A + we let u F denote the first letter of u. Lemma 8. Let Γ = {u 1 , u 2 , . . . , u k } be a finite set of unbordered words over the alphabet A = {1, 2, . . . , k} such that

u k < p u k-1 < p • • • < p u 1 . Let u F
1 = 1 and f be the morphism defined by i → u i , i = 1, . . . , k. Then the word x = f ω (1), fixed point of f , is such that δ(x) = x.

Proof. Let x = f ω (1) = x 0 x 1 • • • x n • • • . Since x is fixed by f , one has x = f (x) = f (x 0 )f (x 1 ) • • • .
Hence, x admits a unique factorization in unbordered prefixes of the set {f (x i ) | i ≥ 0} = U P (x) ⊆ Γ. Let φ : {1, 2, . . . , n x } → U P (x) be the unique order preserving bijection. One has:

δ(x) = φ -1 (f (x 0 ))φ -1 (f (x 1 )) • • • Since φ -1 (f (x n )) = x n , n ≥ 0, it follows δ(x) = x.
Proposition 9. P n+1 is a proper subset of P n for each n ≥ 1.

Proof. Let t be the Thue-Morse word on two symbols t = 0110100110010110 • • • . We have previously seen (see Example 4) that t ∈ P 1 \ P 2 . Let F be the Fibonacci morphism and F (t) = 01000100101000101001001 • • • . The word F (t) has a prefixal factorization and δ(F (t))

t ∈ P 1 \ P 2 . It follows that F (t) ∈ P 2 \ P 3 . It is easily verified that for any n > 1 one has that δ(F n (t))

F n-1 (t). From this it easily follows that δ n (F n (t)) t and δ n+1 (F n (t)) = δ(t) ∈ P 1 . Hence, F n (t) ∈ P n+1 \ P n+2 .

Given an infinite word x with card(U P (x)) < ∞, we let N (x) denote the length of the longest unbordered prefix of x. Now, for x ∈ P ∞ , we define the map ν x : N → N by

ν x (n) = N (δ n (x)), n ≥ 0,
where δ 0 (x) = x. This is well defined and the sequence (ν x (n)) n≥0 is a sequence of natural numbers (≥ 2) which may be bounded or unbounded. If x is the Tribonacci word we have (ν x (n)) n≥0 = 4, 3, 4, 3, 4, 3, . . . Let a ∈ A = {0, 1} and put b = 1 -a. In the following for a ∈ {0, 1}, we let L a be the injective endomorphism of {0, 1} * defined by

L a : a → a, b → ab. ( 2
)
Proposition 10. If x ∈ P ∞ and (ν x (n)) n≥0 = 2, 2, 2, 2, ...., then x is isomorphic to the Fibonacci word.

Proof. Without loss of generality we can assume that x begins with 0. Since N (x) = 2, it follows that x begins with 01 and 01 is the longest unbordered prefix of x. It follows that x is a concatenation of 01 and 0 so we can write x = L 0 (x ) for some binary word x beginning with 1, where x is isomorphic to δ(x). Since N (δ(x)) = N (x ) = 2, it follows that x begins with 10 and 10 is the longest unbordered prefix of x . Hence x is a concatenation of 10 and 1 so that x = L 1 (x ) where x begins with 0 and x is isomorphic to δ(x ) = δ 2 (x). Since N (x ) = 2, it follows that x begins with 01 and 01 is the longest unbordered prefix of x . Thus x = L 0 (x ) for some x beginning with 1 and isomorphic to δ 3 (x). Continuing in this way for each k we have (L 0 L 1 ) k (0) is a prefix of x. Hence, x is isomorphic to the Fibonacci word.

Let us observe that in general the sequence (ν(n)) n≥0 does not determine x. For instance, let x be the word fixed by the morphism 0 → 00001, 1 → 0 and y be the word fixed by the morphism 0 → 00101, 1 → 001. Then (ν x (n)) n≥0 = (ν y (n)) n≥0 = 5, 5, 5, ....

The following question naturally arises:

Question 1. What can be said about the nature of x if (ν x (n)) n≥0 is ultimately periodic? Is x necessarily a fixed point of a morphism? Conversely, if x ∈ P ∞ is a fixed point of a primitive morphism, is (ν x (n)) n≥0 ultimately periodic (in particular bounded) ?

A coloring problem

Let P be the class of all infinite words x over any finite alphabet A such that for every finite coloring ϕ :

A + → C there exists c ∈ C and a factorization x = V 0 V 1 V 2 • • • with ϕ(V i ) = c for all i ≥ 0. Such a factorization is called ϕ-monochromatic. Thus if x /
∈ P, then there exists a finite coloring ϕ : A + → C such that for every factorization

x = V 0 V 1 V 2 • • • we have ϕ(V i ) = ϕ(V j )
for some i = j. Any such coloring will be called a separating coloring for x.

We conjectured [START_REF] De Luca | A coloring problem for infinite words[END_REF] that P coincides with the set of all periodic words. Partial results in this direction are given in [START_REF] De Luca | A coloring problem for infinite words[END_REF] (see also [START_REF] De Luca | On some variations of coloring problems of infinite words[END_REF][START_REF] Salo | Factor colorings of linearly recurrent words[END_REF]). Lemma 11. Let x ∈ P 1 . The following holds:

x ∈ P ⇐⇒ δ(x) ∈ P.

Proof. We begin by proving that if δ(x) ∈ P then x ∈ P. Since x ∈ P 1 , we have x = φ(δ(x)), where φ is the morphism induced by the unique order bijection φ : {1, 2, . . . , n x } → U P (x). Thus if x / ∈ P, then by the morphic invariance property [3, Proposition 4.1], one obtains that δ(x) / ∈ P. We next prove the converse. Suppose δ(x) / ∈ P. Then there exists a separating coloring ϕ :

A + → C for δ(x). Put C = C ∪ {+∞, -∞} where we assume +∞, -∞ / ∈ C. The coloring ϕ induces a coloring ϕ : A + → C defined as follows:

ϕ (u) =        ϕ(φ -1 (u)) if u is a prefix of x and u = φ(v) for some v ∈ Fact(δ(x)); +∞ if u is a prefix of x and u / ∈ φ(Fact(δ(x))); -∞ if u is not a prefix of x.
We note that it follows from Lemma 4 that ϕ is well defined. We now claim that ϕ is a separating coloring for x. Suppose to the contrary that x admits a ϕ -monochromatic factorization

x = V 0 V 1 V 2 • • • in non-empty factors. Since V 0 is a prefix of x, it follows that ϕ (V 0 ) = -∞, and hence ϕ (V i ) = -∞ for each i ≥ 0. Thus the factorization x = V 0 V 1 V 2 • • • is a prefixal factoriza- tion of x.
It now follows from Lemma 5 that there exists a factorization δ(x)

= v 0 v 1 v 2 • • • such that φ(v i ) = V i for each i ≥ 0. Since ϕ (V i ) = ϕ(v i )
, it follows that δ(x) admits a ϕ-monochromatic factorization, a contradiction.

Theorem 12. The following holds: P ⊆ P ∞ .

Proof. Suppose that x ∈ P ∞ . Thus there exists some n ≥ 1 such that x ∈ P n . First suppose x ∈ P 1 . Since x does not admit a prefixal factorization, one has x / ∈ P (see [START_REF] De Luca | A coloring problem for infinite words[END_REF]Proposition 3.3]). Next suppose x ∈ P 1 but x ∈ P n for some n ≥ 2. Then δ n (x) ∈ P 1 and hence as above δ n (x) / ∈ P. By an iterated application of the preceding lemma it follows that x / ∈ P.

Let us observe that if x is a periodic word of A ω , then for every finite coloring x has a monochromatic factorization, so that by Theorem 12, or as one immediately verifies, x ∈ P ∞ . From Theorem 12 one has that any counter-example to our Conjecture 1 belongs to the set P ∞ , which is our main motivation for studying this class of words. However, the reverse inclusion in Theorem 12 does not hold. For instance, as proved in [START_REF] De Luca | A coloring problem for infinite words[END_REF], Sturmian words do not belong to P whereas, as we shall see in the next section (see Theorem 25), a large class of Sturmian words belong to P ∞ . Lemma 13. If ϕ : A + → C is a separating coloring for x, then φ :

A + → C ∪ {∞}, with ∞ ∈ C, defined by φ(u) = ∞ if u is not a prefix of x; ϕ(u) if u is a prefix of x,
is a separating coloring for x.

Proof. Suppose that there exists a φ-monochromatic factorization

x = V 0 V 1 V 2 • • • in non-empty factors V i , i ≥ 0.
Since V 0 is a prefix of x, the preceding factorization has to be a ϕ-monochromatic prefixal factorization, a contradiction as ϕ is separating for x.

Proposition 14. Let x ∈ A ω and Ω(x) be the shift-orbit closure of x. If x ∈ P ∞ , there exists a separating coloring ϕ for x such that if y ∈ Ω(x) and y = x, then y has a ϕ-monochromatic factorization.

Proof. By Theorem 12 one has x / ∈ P. If y ∈ Ω(x) and y = x, then, as x is not periodic, y can always be factorized as y

= V 0 V 1 V 2 • • • where each V i , i ≥ 0, is not a prefix of x.
Let φ be the separating coloring for x defined in the preceding lemma. Then one has that φ(V j ) = ∞ for all j ≥ 0. Proposition 15. Let x ∈ A ω and let A be any finite collection of words in P c ∞ ∩ Ω(x), where P c ∞ denotes the complement of P ∞ . Then there exists a finite coloring ϕ : A + → C such that for each y ∈ Ω(x), ϕ is a separating coloring for y if and only if y ∈ A.

Proof. The result is clear if A = ∅. Indeed in this case it is sufficient to consider the coloring ϕ : A + → C defined as follows: for any u ∈ A + , ϕ(u) = c ∈ C. In this way any y ∈ Ω(x) will have a ϕ-monochromatic factorization. Let us then suppose that A is not empty. Let A = {y 1 , . . . , y r }. Since for i and j with 1 ≤ i < j ≤ r, y i = y j , there exists a positive integer k such that any word of A * of length ≥ k can be prefix of at most one of the words of A. As A ⊆ P c ∞ by Theorem 12, no word y i ∈ A belongs to P. Hence, for each integer i ∈ [1, r] there exists a coloring ϕ i : A + → C i which is separating for y i . Let us observe that as A ⊆ Ω(x) one has

r i=1 Fact(y i ) ⊆ Fact(x).
We can define a finite coloring ϕ on A + as follows. For u ∈ A + ,

ϕ(u) =                  u if |u| < k
and u is a prefix of at least one word of A;

ϕ 1 (u) if u is a prefix of y 1 of length ≥ k; . . . . . . ϕ r (u) if u is a prefix of y r of length ≥ k; ∞ if u is not a prefix of

any of the words of A.

Let us first prove that for each y ∈ A, the coloring ϕ is separating. Let y = y i ∈ A and suppose that there exists a ϕ-monochromatic factorization

y i = V 0 V 1 V 2 • • • where each V i is non- empty. Since V 0 is a prefix of y i , the preceding factorization has to be a prefixal factorization. If ϕ(V i ) = ϕ(V 0 ) and |V 0 | < k it would follow that y i = V ω 0 a contradiction because y i / ∈ P. Thus as V 0 is a prefix of y i of length ≥ k, it follows that ϕ i (V j ) = ϕ i (V 0 )
for all j ≥ 0 and this contradicts the fact that ϕ i is separating for y i .

Let us now prove that if y ∈ A, then y admits a ϕ-monochromatic factorization. Since for each i ∈ [1, r] we have y = y i and y i is not periodic, one easily derives that y can be factored as

y = V 0 V 1 • • •
, where each V j , j ≥ 0, is not a prefix of any of the words y i ∈ A, i = 1, . . . , r. From this one has ϕ(V j ) = ∞ for all j ≥ 0. Question 2. Let x ∈ A ω be uniformly recurrent. Given a finite coloring ϕ : A + → C does there exist a finite (possibly empty) set A ⊂ Ω(x) such that for each y ∈ Ω(x) we have that y admits a ϕ-monochromatic factorization if and only if y / ∈ A?

Let us observe that in the previous question the hypothesis that x is uniformly recurrent is necessary. Indeed, let x = 010 2 1 2 0 3 1 3 • • • and ϕ : {0, 1} + → {0, 1, * } be the finite coloring defined for all u ∈ Fact + (x) by ϕ(u) = 0, if u begins with 0, ϕ(u) = 1 if u begins with 1, and if u ∈ Fact + (x), by ϕ(u) = * . In the shift orbit closure Ω(x) of x there are infinitely many words 0 n 1 ω , n ≥ 1 which do not admit a ϕ-monochromatic factorization. Proposition 16. Let x ∈ P ∞ . Then x is uniformly recurrent.

Proof. We prove by induction on n ≥ 1 that for any infinite word x over a finite alphabet if the prefix of x of length n is not uniformly recurrent, then x / ∈ P ∞ . If the first letter of x is not uniformly recurrent in x, then by Lemma 2 the word x does not admit a prefixal factorization, hence x / ∈ P 1 . Let n ≥ 1, and suppose the result holds up to n. Let x ∈ A ω and suppose the prefix of x of length n + 1 is not uniformly recurrent in x. We will prove that x / ∈ P ∞ . If x / ∈ P 1 , we are done. So we may assume that x ∈ P 1 . Let φ : {1, 2, . . . , n x } → U P (x) denote the unique order preserving bijection. Consider δ(x) ∈ {1, 2, . . . , n x } ω . Since x = φ(δ(x)) it follows that δ(x) is not uniformly recurrent. If v is a prefix of δ(x) which is uniformly recurrent in δ(x), then φ(v) is a uniformly recurrent prefix of x. Moreover, for every prefix v of δ(x) we have |v| < |φ(v)|. Thus the shortest non-uniformly recurrent prefix of δ(x) is of length smaller than or equal to n. By induction hypothesis, δ(x) / ∈ P ∞ , and hence x / ∈ P ∞ .

As a consequence of Proposition 16 and Theorem 12 we recover the following result first proved in [START_REF] De Luca | A coloring problem for infinite words[END_REF]:

Corollary 17. If x ∈ P then x is uniformly recurrent.

The case of Sturmian words

There exist several equivalent definitions of Sturmian words (see, for instance, [1? ]). We will use the following one: A word x ∈ {0, 1} ω is called Sturmian if it is aperiodic and balanced, i.e., for all factors u and v of x such that |u| = |v| one has

||u| a -|v| a | ≤ 1, a ∈ {0, 1}.
Definition 18. Let a ∈ {0, 1}. We say that a Sturmian word is of type a if it contains the factor aa.

Clearly a Sturmian word is either of type 0 or of type 1, but not both.

Alternatively, a binary infinite word x is Sturmian if x has a unique left (or equivalently right) special factor of length n for each integer n ≥ 0. In terms of factor complexity, this is equivalent to saying that λ x (n) = n + 1 for n ≥ 0. As a consequence one derives that a Sturmian word x is closed under reversal, i.e., if u is a factor of x, then so is its reversal u ∼ (see, for instance, [13, Chap. 2]).

A Sturmian word x is called standard (or characteristic) if all its prefixes are left special factors of x. Since Sturmian words are uniformly recurrent (see for instance Proposition 2.1.25 in [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]), it follows that for any Sturmian word x there exists a standard Sturmian word S such that Fact(x) = Fact(S).

Following [START_REF] Bucci | Central sets generated by uniformly recurrent words, Ergodic Theory Dynam[END_REF] we say that a Sturmian word x ∈ {0, 1} ω is singular if it contains a standard Sturmian word as a proper suffix, i.e., there exist u ∈ {0, 1} + and a standard Sturmian word S such that x = uS. It is readily verified that the previous factorization is unique. A Sturmian word which is not singular is said to be nonsingular.

Let a ∈ {0, 1} and b = 1 -a. In the following for a ∈ {0, 1}, we consider the injective endomorphism L a of {0, 1} * defined in [START_REF] Berstel | Sturmian words, Lyndon words and trees[END_REF] given by L a : a → a, b → ab and the injective endomorphism R a of {0, 1} * defined by

R a : a → a, b → ba.
We recall [13, Chap. 2] that the monoid generated by L a and R a , with a ∈ {0, 1} is contained in the set of all endomorphisms f of {0, 1} * which preserve Sturmian words, i.e., the image f (y) of any Sturmian word y is a Sturmian word.

Let us observe that for any infinite word x over {0, 1} we have L a (x) = aR a (x). If x is a Sturmian word and v is a left special factor of x, then L a (v) is a left special factor of L a (x). Thus if S is a standard Sturmian word, then so is L a (S) = aR a (S). Conversely, if S is a standard Sturmian word of type a, then S = L a (S ) for some standard Sturmian word S . Lemma 19. A Sturmian word x belongs to P 1 if and only if x = aS where a ∈ {0, 1} and S a standard Sturmian word.

Proof. Indeed, as is well known (see [START_REF] Berstel | Sturmian words, Lyndon words and trees[END_REF][START_REF] Harju | Minimal Duval extensions[END_REF]), the unbordered factors of length greater than 1 of a Sturmian word x are exactly those factors of the form bU c with {b, c} = {0, 1} and U (possibly empty) a bispecial factor of x. Therefore, if x = ax has infinitely many unbordered prefixes, then x begins with infinitely many bispecial factors of x, and hence x is a standard Sturmian word. Conversely, let x = aS where S is a standard Sturmian word and a ∈ {0, 1}. We claim the Sturmian word aS does not admit a prefixal factorization. Indeed, aS begins with an infinite number of distinct prefixes of the form aU b with U bispecial and {a, b} = {0, 1}. It follows that aS begins with arbitrarily long unbordered prefixes and hence, by Proposition 3 does not admit a prefixal factorization.

We begin by reviewing some terminology which will be used in the proof of the following lemma. Let x ∈ A ω and a ∈ A. A word u ∈ A + is called a left first return to a in x if ua is a factor of x which begins and ends with a and |ua| a = 2, i.e., the only occurrences of a in ua are as a prefix and as a suffix. A word u ∈ A + is called a right first return to a in x if au is a factor of x which begins and ends with a and |au| a = 2. A word u ∈ A + is called a complete return to a in x if u is a factor of x which begins and ends with a and |u| a ≥ 2. It is a basic fact that if u is a complete return to a in x, then ua -1 factors uniquely as a product of left first returns to a in x and that a -1 u factors uniquely as a product of right first returns to a in x.

Lemma 20. Let x ∈ {0, 1} ω be a Sturmian word of type a with card(U P (x)) < +∞, and N (x) the length of the longest unbordered prefix of x. Then: i) If N (x) = 2, there exists a Sturmian word y ∈ {0, 1} ω isomorphic to δ(x) and x = L a (y). ii) If N (x) > 2 and x begins with a, there exists a Sturmian word y ∈ {0, 1} ω beginning with a such that x = L a (y), N (y) < N (x), and δ(x) = δ(y). Moreover L a establishes a one-to-one correspondence between U P (y) and U P (x), i.e., L a : U P (y) → U P (x) is a bijection. iii) If N (x) > 2 and x begins with b there exists a Sturmian word y ∈ {0, 1} ω beginning with b such that x = R a (y), N (y) < N (x), and δ(x) = δ(y). Moreover R a establishes a one-toone correspondence between U P (y) and U P (x) \ {b}, i.e., R a : U P (y) → U P (x) \ {b} is a bijection.

Proof. To prove i), suppose N (x) = 2. It follows that U P (x) = {c, cd} where {c, d} = {0, 1}. Since x is of type a and admits a factorization over U P (x) and hence contains the factor cc, it follows that a = c and hence U P (x) = {a, ab}. Thus the unique factorization of x over U P (x) is equal to the factorization of x according to left first returns to a which is well known to be Sturmian. Alternatively, there exists a unique Sturmian word y such that x = L a (y). It follows that δ(x) is word isomorphic to y.

To prove ii), suppose x begins with a and its longest unbordered prefix is of length N (x) > 2. Then x begins with aa; in fact if x begins with ab, since x is of type a we would have that U P (x) = {a, ab} contradicting our assumption that N (x) > 2. Having established that x begins with aa, it follows that there exists a unique Sturmian word y such that x = L a (y) and moreover y also begins with a. In fact, y is obtained from x by factoring x according to left first returns to a where one codes the left first return to a by a, and the left first return ab by b.

Next we prove that L a establishes a bijection between U P (y) and U P (x). We use the key fact that if u ∈ {0, 1} + and ua is a factor of x which begins and ends with a, then there exists a unique factor v of y such that u = L a (v). In fact, ua is a complete return to a and hence v is obtained from u by factoring u as a product of left first returns to a. In particular, if u ∈ {0, 1} + is a factor of x which begins with a and ends with b, then u = L a (v) for some factor v of y.

We begin by proving that L a (U P (y)) ⊆ U P (x), i.e., that L a : U P (y) → U P (x). So let u be an unbordered prefix of y. If |u| = 1, then u = a and hence L a (u) = a which is an unbordered prefix of x. If |u| > 1, then u begins with a and ends with b, and hence L a (u) begins with a and ends with b. If L a (u) were bordered, then any border v of L a (u) would also begin with a and end with b, whence we can write v = L a (v ) for some border v of u, contradicting that u is unbordered. Since the mapping L a : U P (y) → U P (x) is clearly injective, to prove that it is a bijection it remains to prove that the mapping is surjective. So assume u is a unbordered prefix of x; we will prove that u = L a (u ) for some unbordered prefix of y. This is clear if u = a, in which case u = a. If |u| > 1, then u begins with a and ends with b and hence u = L a (u ) for some prefix u of y. Moreover, if u were bordered (say v is a border of u ) then L a (v ) is a border of u, a contradiction.

It follows that if u is the longest unbordered prefix of y, then N (y) = |u| < |L a (u)| ≤ N (x) where the first inequality follows from the fact that u must contain an occurrence of both 0 and 1. Finally, since card(U P (y)) < +∞, we have that y admits a factorization y = U 0 U 1 U 2 • • • with U i ∈ U P (y), which by definition is isomorphic to δ(y). Applying L a we obtain

x = L a (U 0 )L a (U 1 )L a (U 2 ) • • • with L a (U i ) ∈ U P (x)
which is isomorphic to δ(x). Hence, δ(x) = δ(y) as required. This completes the proof of ii).

Finally to prove iii), suppose x begins with b. Then there exists a unique Sturmian word y such that x = R a (y) and moreover y begins with b. As in the previous case, it is readily checked that R a : U P (y) → U P (x) \ {b} is a bijection. The idea is that if u ∈ {0, 1} + and au is a factor of x which begins and ends with a, then there exists a unique factor v of y such that u = R a (v). In fact, au is a complete return to a and hence u factors uniquely as a product of right first returns to a. Thus in particular, if u ∈ {0, 1} + is a factor of x which begins with b and ends with a, then u = R a (v) for some factor v of y. Finally, as in the previous case we deduce that N (y) < N (x) and δ(y) = δ(x). Remark 3. We note that if x is a Sturmian word with card(U P (x)) < +∞ and N (x) > 2, then, applying repeatedly ii) and iii) of Lemma 20, we deduce that there exist a Sturmian word y and a morphism f ∈ {L 0 , L 1 , R 0 , R 1 } + such that x = f (y), N (y) = 2, and δ(y) = δ(x).

Corollary 21. Let x ∈ {0, 1} ω be a Sturmian word with card(U P (x)) < +∞. Then δ(x) is again Sturmian.

Proof. First suppose N (x) = 2. In this case the result follows immediately from i) of Lemma 20. Next suppose N (x) > 2. Then by Remark 3 there exists a Sturmian word y such that N (y) = 2 and δ(y) = δ(x). Hence δ(x) is Sturmian.

Corollary 22. If x is a standard Sturmian word, then so is δ(x).

Proof. By Lemma 19 any standard Sturmian word x has a prefixal factorization. Thus card(U P (x)) < ∞. Moreover, if x is of type a, then it begins with the letter a. The proof is then easily obtained by induction on N (x). If N (x) = 2 by i) of Lemma 20 there exists a Sturmian word y isomorphic to δ(x) such that x = L a (y). Since x is a standard Sturmian word, it follows that y, as well as δ(x), is a standard Sturmian word. Let us now suppose N (x) > 2. By ii) of Lemma 20 there exists a Proof. Let us first suppose that S is a standard Sturmian word and y is singular and of the form y = u S with u ∈ {0, 1} + and |u | ≥ 2. Since |u | ≥ 2, it follows that either 01S or 10S is a suffix of y. In particular, u must contain an occurrence of both 0 and 1. Whence for each a ∈ {0, 1} we have that |u Let us now suppose that x = f (y) is singular, i.e., x = uS with u ∈ {0, 1} + and S a standard Sturmian word. We wish to prove that y is singular. It suffices to prove the assertion for f ∈ {L a , R a }, a ∈ {0, 1}. Let us first take f = L a . One has that x, as well as S, is a Sturmian word of type a beginning with the letter a. Hence the word u either ends with the letter b or ends with the letter a immediately followed by the letter a. Thus setting S = L -1 a (S) and u = L -1 a (u), one has y = u S . Since S is a standard Sturmian word, one has that y is singular.

| < |L a (u )| and |u | < |R a (u )|. For a ∈ {0, 1} let g ∈ {L a , R a }. Taking g = L a we have g(y) = L a (u S ) = L a (u )L a (S ) and |u | < |L a (u )|. Taking g = R a we have g(y) = R a (u S ) = R a (u )a -1 aR a (S ) = R a (u )a -1 L a (S ) and |u | ≤ |R a (u )a -1 |. Since L a (S )
Let us now take f = R a . One has that x, as well as S, is a Sturmian word of type a. We have to consider two cases. Case 1. The word u ends with the letter a. We can set u = R -1 a (u). Since the first letter of S is a, we can write y = u aS with S = R a (aS ) = aR a (S ) = L a (S ). This implies that S is a standard Sturmian word and that y is singular. Case 2. The word u ends with the letter b. Since S begins with the letter a, we can write x = u 1 baS with S = aS and u = u 1 b, where the word u 1 if it is different from ε, ends with the letter a. Setting u = R -1 a (u 1 ) one has that y = u bS where bS = R a (bS ) = baR a (S ) = bL a (S ). Thus S = L a (S ) and S is a standard word. From this it follows that y is singular.

Remark 5. We note that the assumption in the preceding lemma that |u | ≥ 2 is actually necessary. For instance, if y is singular and of the form y = aS with a ∈ {0, 1} and S standard, then R a (y) = aR a (S ) = L a (S ) is nonsingular.

Theorem 25. Let x be a Sturmian word. Then x ∈ P ∞ if and only if x is nonsingular.

Proof. We begin by proving that if x / ∈ P ∞ then x is singular. For this we prove by induction on n, that if x / ∈ P n , then x is singular. For n = 1, we have that if x / ∈ P 1 , then by Lemma 19, x = aS where a ∈ {0, 1} and S is a standard Sturmian word. Thus x is singular. Next let n ≥ 2, and suppose by inductive hypothesis that if y is a Sturmian word and y / ∈ P n-1 , then y is singular. Let x be a Sturmian word with x / ∈ P n . By inductive hypothesis we can suppose x ∈ P n-1 . In particular, x ∈ P 1 . If N (x) = 2, then by i) of Lemma 20 we have x = L a (y) where a ∈ {0, 1} and y is Sturmian and isomorphic to δ(x). Since x / ∈ P n it follows that δ(x) / ∈ P n-1 , whence y / ∈ P n-1 . Hence by induction hypothesis y is singular. Thus we can write y = uS where u ∈ {0, 1} + and S a standard Sturmian word. Thus x = L a (y) = L a (uS) = L a (u)L a (S) and since L a (S) is a standard Sturmian word, we deduce that x is singular as required.

If N (x) > 2, then, following Remark 3, there exist a Sturmian word y and a morphism f ∈ {L 0 , L 1 , R 0 , R 1 } + such that x = f (y), N (y) = 2, and δ(y) = δ(x). In particular, δ(y) / ∈ P n-1 and hence y / ∈ P n . Thus applying i) of Lemma 20 as above, we deduce that y is singular. Hence there exist u ∈ {0, 1} + and a standard Sturmian word S such that y = uS. On the other hand, since δ(y) is defined (or equivalently y ∈ P 1 ), it follows from Lemma 19 that |u| ≥ 2. Thus applying Lemma 24 we deduce that x is singular.

Conversely, suppose x ∈ {0, 1} ω is a Sturmian word of the form x = uS with u ∈ {0, 1} + and S a standard Sturmian word. We will prove by induction on |u| that x / ∈ P ∞ . If |u| = 1, i.e., x = aS for some a ∈ {0, 1}, then, by Lemma 19, x / ∈ P 1 , whence x / ∈ P ∞ . Next let n ≥ 2 and assume by induction hypothesis that if y is a Sturmian word of the form y = u S where S is a standard Sturmian word, and u ∈ {0, 1} + with |u | < n, then y / ∈ P ∞ . Let x be a Sturmian word of the form x = uS with S standard, u ∈ {0, 1} + and |u| = n. Since n ≥ 2, by Lemma 19, x admits a prefixal factorization so that card(U P (x)) < ∞. We consider two cases. If N (x) = 2, then by i) of Lemma 20 we can write x = L a (y) where a ∈ {0, 1} and y is Sturmian and isomorphic to δ(x). Since x is singular, it follows by Lemma 24 that y is singular. Thus we can write y = u S for some u ∈ {0, 1} and some standard Sturmian word S . If |u | = 1, then y / ∈ P 1 , whence δ(x) / ∈ P 1 and hence x / ∈ P ∞ . If |u | ≥ 2, again by Lemma 24 we deduce that |u | < |u| and hence by induction hypothesis we conclude that y / ∈ P ∞ . Hence δ(x) / ∈ P ∞ whence x / ∈ P ∞ . Finally suppose N (x) > 2. Then by Remark 3 there exist a Sturmian word y, and a morphism f ∈ {L 0 , L 1 , R 0 , R 1 } + such that x = f (y) and δ(x) = δ(y) and N (y) = 2. By i) of Lemma 20 there exists a Sturmian word y isomorphic to δ(y) such that y = L a (y ). Thus x = f • L a (y ) and y is isomorphic to δ(x). Since x is singular, by Lemma 24 we deduce that y is singular. Thus we can write y = u S for some u ∈ {0, 1} + and some standard Sturmian word S . If |u | = 1, then y / ∈ P 1 , whence δ(x) / ∈ P 1 and hence x / ∈ P ∞ . If |u | ≥ 2, then by Lemma 24 we deduce that |u | < n, and hence by induction hypothesis we conclude that y / ∈ P ∞ . Hence δ(x) / ∈ P ∞ whence x / ∈ P ∞ .

Example 2 .

 2 Let x = 121312112131212131211213121312112131212131211213 • • • denote the Tribonacci word fixed by the morphism defined by 1 → 12, 2 → 13, 3 → 1. It is readily verified that U P (x) = U P (x) = {1, 12, 1213}, and 1213 ≺ 12 ≺ 1. It follows that n x = 3 and φ(1) = 1213, φ(2) = 12, and φ(3) = 1. The unique factorization of x in terms of U P (x) begins with

  is a standard Sturmian word, one has that g(y) is singular. Iterating we deduce that there exist a standard Sturmian word S and u ∈ {0, 1} + such that x = f (y) = uS and |u | ≤ |u|. Moreover, if f admits at least one occurrence of either L 0 or L 1 , then |u | < |u|.

Acknowledgments: We thank the two anonymous reviewers for their many useful comments.

Sturmian word y such that N (y) < N (x) and x = L a (y) and δ(y) = δ(x). Since y is standard, by induction δ(y) = δ(x) is a standard Sturmian word. Remark 4. An infinite word x over the alphabet A is called episturmian [START_REF] Droubay | Episturmian words and some constructions of de Luca and Rauzy[END_REF] if it is closed under reversal and x has at most one right special factor of each length. Corollary 21 cannot be extended to episturmian words. Indeed, as we observed in Example 3, in the case of Tribonacci word x, which is an episturmian word, δ(x) has a unique left special factor of each length and two right special factors of each length, so that δ(x) is not episturmian. Lemma 23. Let x ∈ {0, 1} ω be a Sturmian word with card(U P (x)) < +∞. Let x = U 0 U 1 U 2 • • • be the unique factorization of x over U P (x). Then there exist distinct unbordered prefixes U and

Moreover U the longest unbordered prefix of x and V is the longest proper unbordered prefix of U.

Proof. Following Corollary 21 we have that δ(x) is a Sturmian word. In particular, writing

Without loss of generality we may assume that x is of type 0. We proceed by induction on the length N (x) of the longest unbordered prefix of x to prove that V is the longest proper unbordered prefix of U, where U and V are as above. If N (x) = 2, we have that U P (x) = {0, 01} and the result follows taking V = 0 and U = 01. Next suppose N (x) > 2 and suppose that the result is true up to N (x) -1. Then by ii) and iii) of Lemma 20 it follows that there exists a Sturmian word y such that x = L 0 (y) in case x begins with 0, and x = R 0 (y) in case x begins with 1. Moreover, again using ii) and iii) it follows that N (y) < N (x). Hence, if U denotes the longest unbordered prefix of y, and V denotes the longest proper unbordered prefix of U , then it follows by induction hypothesis that y factors over {U , V }. If x begins with 0, then applying L 0 to this factorization we obtain a factorization of x over {L 0 (U ), L 0 (V )} and hence U = L 0 (U ) and V = L 0 (V ). Since L 0 : U P (y) → U P (x) is a bijection, we deduce that V is the longest proper unbordered prefix of U. Similarly, if x begins with 1, then applying R 0 to this factorization we obtain a factorization of x over {R 0 (U ), R 0 (V )} and hence U = R 0 (U ) and V = R 0 (V ). Since R 0 : U P (y) → U P (x) \ {1} is a bijection and U begins with 1 and ends with 00, and the shortest prefix of U beginning with 1 and ending with 0 is a proper unbordered prefix of U, we deduce that V is the longest proper unbordered prefix of U.

Lemma 24. Let y ∈ {0, 1} ω be a Sturmian word, f ∈ {L 0 , L 1 , R 0 , R 1 } + and set x = f (y). If x is singular, then y is singular. Conversely, if y is singular and of the form y = u S , where S is a standard Sturmian word and u ∈ {0, 1} + with |u | ≥ 2, then x is singular. More precisely, there exist a standard Sturmian word S and u ∈ {0, 1} + with |u | ≤ |u| such that x = uS. Moreover, if f admits at least one occurrence of either L 0 or L 1 , then |u | < |u|.