Anton Černý

Lyndon factorization of generalized words of Thue

Keywords: Lyndon word, Lyndon factorization, automatic sequence

The i-th symbol of the well-known infinite word of Thue on the alphabet {0, 1} can be characterized as the parity of the number of occurrences of the digit 1 in the binary representation of i. Generalized words of Thue are based on counting the parity of occurrences of an arbitrary word w ∈ {0, 1} * -0 * in the binary representation of i. We provide here the standard Lyndon factorization of some subclasses of this class of infinite words.

Introduction

When we are interested in getting a better insight into the structure of some object, whether in mathematics or in computer science, one of the basic approaches how to tackle the problem is decomposition of the object into smaller "canonical" objects. The classical example is the factorization of a natural number into prime numbers being a powerful tool in the number theory. Natural numbers coded in unary notation correspond to finite words (strings) over a single-letter alphabet. Words over arbitrary alphabets can be considered to be a generalization of the concept of the natural number. A canonical decomposition of words to concatenation factors being Lyndon words is provided by the Lyndon factorization theorem ( [START_REF] Lothaire | Combinatorics on words[END_REF]). Lyndon words are primitive words minimal in their conjugacy classes. They are easy to deal with, e.g., there exists a simple linear algorithm, introduced by Duval ( [START_REF] Duval | Factorizing words over an ordered alphabet[END_REF], [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF]) for generating Lyndon words, up to a given length, in lexicographic order. A structural relationship of Lyndon words to other important classes of words has been established ( [START_REF] Berstel | Sturmian words, Lyndon words and trees[END_REF]). Application of the Lyndon factorization leads to important results in the investigation of finite factorizations of the free monoid A * and to discovery of new unavoidable regularities in words ( [START_REF] Varricchio | Factorizations of free monoids and unavoidable regularities[END_REF]). Similar investigations of factorizations were performed for the case of free partially commutative monoids ( [START_REF] Duchamp | Lazard's factorizations of free partially commutative monoids[END_REF]). The Lyndon factorization can be generalized to Viennot factorization by proceeding from the lexicographic ordering to Viennot orderings ( [START_REF] Melanc ¸on | Viennot factorization of infinite words[END_REF]).

The Lyndon-factorization theorem has been further extended to infinite words (infinite sequences of symbols - [START_REF] Siromoney | Infinite Lyndon words[END_REF]). Investigation of infinite words is crucial in the area of combinatorics on words, since properties of infinite words very often imply regularities in infinite sets of finite words. It is quite natural Anton Černý that, after the existence of the unique Lyndon factorization of infinite words had been proved, the factorization of some important sequences was investigated. In particular, the factorization of the sequence of Thue, of the Fibonacci sequence, of the regular paperfolding sequence and of the characteristic Sturmian sequences was characterized in [START_REF] Ido | Lyndon factorization of the Thue-Morse word and its relatives[END_REF], [START_REF] Melanc ¸on | Lyndon factorization of infinite words[END_REF], [START_REF] Melanc ¸on | Lyndon Factorization of Sturmian Words, 8th international Conference on Formal Power Series and Algebraic Combinatorics (FPSAC)[END_REF].

The sequence of Thue was historically the first sequence where the structural properties were systematically studied ( [START_REF] Thue | Ueber unendliche Zeichenreihen, Videnskabsselskabets Skifter[END_REF], [START_REF] Thue | Über die gegenseitige Lage gleichen Teile gewisser Zeichenreihen, Videnskapsselskapets Skifter, I. Mat. -naturv. Klasse[END_REF]; a construction of that sequence was mentioned, probably for the first time, in [START_REF] Prouhet | Mémoire sur quelques relations entre les puissances des nombres[END_REF]). The Thue sequence is one of the simplest non-periodic sequences in the important class of automatic sequences (originally called uniform tag sequences - [START_REF] Cobham | Uniform tag sequences[END_REF]). Automatic sequences can be equivalently characterized by, among others, finite state automata, uniform morphisms or substitutions ( [START_REF] Cobham | Uniform tag sequences[END_REF], [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF]).

In the current paper we investigate the Lyndon factorization of several subclasses of the class of generalized sequences of Thue. The generalized Thue sequences were first introduced in [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF]. Each word w on the alphabet {0,1}, which contains at least one symbol 1, describes, as a parameter, a sequence t w in this class. The i-th symbol of t w corresponds to the parity of occurrences of w as a factor of the binary representation for i. The Thue sequence corresponds to the single-letter parameter word 1. As is well known, the Thue sequence does not contain cubic factors. Similarly, the sequence t w does not contain a factor, which is the 2 |w| -th power of a non-empty word ( [START_REF] Černý | On a class of infinite words with bounded repetitions[END_REF]). In fact, t w does not contain any cubic factors except powers of a single letter ( [START_REF] Séébold | Generalized Thue-Morse sequences[END_REF], [START_REF] Séébold | Complément à l'étude des suites de Thue-Morse généralisées[END_REF]).

The present work is, in a sense, of an experimental character. We believe that studying the factorization pattern of a whole class of structurally related infinite sequences may bring some deeper insight to the relationship between the structure of a sequence and its Lyndon decomposition. Though we provide here a description of the Lyndon factorization of just a few subclasses of the generalized Thue sequences, it seems to be apparent that the Lyndon factors follow the block structure of the sequence determined by the iteration underlying uniform morphism or substitution. On the other hand, there does not seem to be a straightforward way leading to the unique description of the factorization of the whole class of the generalized words of Thue.

Notation and basic notions

Preliminaries

We denote as N ={0, 1, . . .} the set of all natural numbers and, for p ∈ N, we denote [p] = {i ∈ N; i < p}. An alphabet is any finite non-empty set Σ (its elements are called symbols). In particular, we will use the set [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] = {0, 1} as an alphabet consisting of 2 symbols. A finite word w of length |w| = n ∈ N on Σ is a finite sequence w = a 0 a 1 • • •a n-1 of symbols from Σ. The empty word (of length 0) is denoted by λ. An infinite word (a sequence for short) on Σ is an infinite sequence w = a 0 a 1 • • • of symbols from Σ.

The symbol in a word or sequence w at the position i is denoted as w(i) (the position numbering starts from 0). By Σ * , Σ p , (Σ p ) * , Σ ω we denote the sets of all words, of all words of length p, of all words of length being a multiple of p and of all sequences on Σ, respectively. Further we denote

Σ ∞ = Σ * ∪ Σ ω and (Σ p ) ∞ = (Σ p ) * ∪ Σ ω . For a number i ∈ [2 k ] we denote as i [2],k ∈ [2]
k the word being the binary representation of i of length k ≥ 0. For a word w ∈ [2] k we denote as [w] 2 the unique number from [2 k ] with binary representation w.

The concatenation of the words x ∈ Σ * and y ∈ Σ ∞ is xy ∈ Σ ∞ . For x, y ∈ Σ * , the words xy and yx are called conjugates. If w = xyz ∈ Σ ∞ , then x, y, z are called a prefix, a factor at position |x|, and a suffix of w, respectively. In this case, we further denote x -1 w = yz and wz -1 = xy. A prefix, factor, or suffix is called proper if the remaining part of w is not empty. A word is primitive if it is not a concatenation of two or more equal factors. If (w i ) ∞ i=0 is a sequence of finite words of unlimited length such that, for each i ≥ 0, w i is a prefix w i+1 , then lim i→∞ w i will denote the unique infinite word having each w i as a prefix.

Let r ≥ 1, s ≥ 0 and let (Σ r ) * = k∈N Σ kr . A (r, s)-substitution (introduced in [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF]) is a mapping µ :

(Σ r ) ∞ → Γ ∞ , satisfying µ(Σ r ) ⊂ Γ s , and µ(xy) = µ(x)µ(y) for x ∈ (Σ r ) * , y ∈ (Σ r ) ∞ .
Thus µ is completely determined by its values on Σ r . The substitution µ is prolongable in a word u ∈ Σ r if u is a proper prefix of µ(u). Then, clearly, s > r ≥ 1 and the sequence (µ i (u)) ∞ i=0 of words obtained by repeated application of µ starting from u yields a limit s = lim i→∞ µ i (u) being a fixed point of µ, i.e., satisfying µ(s) = s. A (1, p)-substitution is called p-uniform morphism.

Automatic sequences are described by finite state automata ( [START_REF] Cobham | Uniform tag sequences[END_REF], where these sequences are called uniform tag sequences). We will limit here our considerations to 2-automatic sequences on the alphabet [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] only. A 2-finite-state automaton (2-fsa) is a tuple A = (Σ, [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF], δ, a 0 , F) where Σ is a (state) alphabet, δ : Σ × [2] → Σ is the transition function, a 0 ∈ Σ is the initial state and F ⊂ Σ. We will assume that A satisfies δ(a 0 , 0) = a 0 . We will consider the usual extension δ

* : Σ × [2] * → Σ defined for a ∈ Σ, w ∈ [2] * , x ∈ [2] inductively as δ * (a, λ) = a, δ * (a, wx) = δ(δ * (a, w), x). A sequence s = b 0 b 1 • • • ∈ [2] ω is 2-automatic if
there exists a 2-fsa A as above such that, for i ∈ N, b i = 1 iff δ * (a 0 , i [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],⌈log(i+1)⌉ ) ∈ F. We say that s is described by A. We will use here several equivalent characterizations of 2-automatic sequences -see [START_REF] Cobham | Uniform tag sequences[END_REF], [START_REF] Černý | Modular trellises[END_REF] for the proof of Theorem 2.1.1. (Remark 2.1.2 is based on this proof.)

Theorem 2.1.1 Let s = b 0 b 1 • • • ∈ [2] ω be a sequence. The following conditions i, ii, iii are equivalent. (i) s is a 2-automatic sequence (ii) there is an alphabet Σ, a 2-uniform morphism ϕ : Σ ∞ → Σ ∞ and a 1-uniform morphism ψ : Σ ∞ → [2] ∞ such that s = ψ( lim n→∞ ϕ n (a)) (iii) s is a fixed point of some (k, kp m )-substitution µ : [2] ∞ → [2] ∞ , k, m ≥ 1.
Remark 2.1.2 Let a 2-automatic sequence be described by the fsa A = (Σ, [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF], δ, a 0 , F). The morphisms ϕ, ψ from ii of Theorem 2.1.1 are given, for a ∈ Σ, as ϕ(a) = δ(a, 0)δ(a, 1), ψ(a) = (if a ∈ F then 1 else 0). The symbol of ψ(ϕ r (a)) at position i ∈ [2 r ], r ≥ 0, is then ψ(δ * (a, i [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],r )).

Lyndon words

Assume a totally ordered alphabet Σ with the corresponding lexicographic order on Σ ∞ . Lyndon words are defined as primitive words, which are minimal in the class of all their conjugates. The proof of the following equivalent characterization of Lyndon words and the proof of the Lyndon's theorem can be found in [START_REF] Lothaire | Combinatorics on words[END_REF].

Proposition 2.2.1 A non-empty word is a Lyndon word iff it is strictly smaller than any of its non-empty proper suffixes.

Theorem 2.2.2 (Lyndon) Any non-empty finite word can be written uniquely as a concatenation of a non-increasing sequence of Lyndon words.

In [START_REF] Siromoney | Infinite Lyndon words[END_REF] the authors defined infinite Lyndon words as those sequences, which have infinitely many prefixes being Lyndon words. They proved the following generalization of the Lyndon theorem.

Anton Černý

Theorem 2.2.3 Any infinite word s can be uniquely factorized in one of the following forms:

s = l 0 l 1 • • •, where l 0 ≥ l 1 ≥ • • • are finite Lyndon words or s = l 0 l 1 • • •l k l k+1 where l 0 ≥ l 1 ≥ • • • ≥ l k
are finite Lyndon words and l k+1 < l k is an infinite Lyndon word.

Generalized words of Thue

The infinite word of Thue t can be defined as t = lim i→∞ ϕ i (0) where ϕ is the 2-uniform morphism on the alphabet {0, 1} described as ϕ(0) = 01, ϕ(1) = 10. Hence t = 0110100110010110• • •. The digit at the i-th position of t can be determined as the parity of the number of occurrences of the digit 1 in the binary representation of i. In [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF] generalized words of Thue were introduced. They were further investigated in [START_REF] Černý | On a class of infinite words with bounded repetitions[END_REF], [START_REF] Séébold | Generalized Thue-Morse sequences[END_REF] and [START_REF] Séébold | Complément à l'étude des suites de Thue-Morse généralisées[END_REF]. Each such infinite word t w = t w (0)t w (1)t w (2)• • • ∈ {0, 1} ω is based on a word w ∈ {0, 1} * -{0} * . The symbol t w (i) at the i-th position of t w is defined as t w (i) = # w 0 |w| i [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] mod 2 where # w 0 |w| i [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] denotes the number of factors w occurring in the binary representation of i padded with at least |w| leading zeroes. Every occurrence of a factor is counted, e.g., t 010 (10) = 0, since 0001010 (the binary representation of 10 padded with 3 leading zeroes) contains two overlapping factors 010. In particular, t = t 1 .

Let for the remaining part of the paper w ∈ {0, 1} * -{0} * be an arbitrary but fixed word. Denote k = |w|, Σ w = { α, m ; α is a proper prefix of w, m ∈ [2]}. We will suppose that k ≥ 2 since the case k = 1 means t w is the sequence of Thue. For the purpose of the next theorem (the proof of the theorem can be found in [START_REF] Černý | On a class of infinite words with bounded repetitions[END_REF]), for each x, y = λ, let sp(x, y) denote the longest suffix of x that is a proper prefix of y.

Theorem 2.3.1 The sequence t w is described by the fsa

A w = (Σ w , [2], δ w , a 0,w , F w ) where, for α, m ∈ Σ w , j ∈ [2], δ w ( α, m , j) = sp(α j, w), if α j = w then 1 -m else m , ( 1
)
a 0,w = sp(0 k , w), 0 and F w = { α, 1 ; α, 1 ∈ Σ w }. Moreover , A w is the minimal fsa, with respect to the size of the state alphabet, describing t w .

We will denote as ϕ w , ψ w the morphisms corresponding to A w according to Remark 2.1.2 (it is worth to observe that ψ w ( α, m ) = m). The sequence t w is a fixed point of a substitution described by the following theorem from [START_REF] Christol | Suites algébriques, automates et substitutions[END_REF].

Theorem 2.3.2 Let µ w be the (2 k-1 , 2 k )-substitution defined on [2] k-1 as µ w (x 0 x 1 • • •x 2 k-1 -1 ) = y 0 y 1 • • •y 2 k -1 (2)
where, for i

∈ [2 k ], y i = (x ⌊i/2⌋ + χ w (i)) mod 2, and χ w (i) = if w = i [2],k then 1 else 0. Then µ w (t w ) = t w . Property 2.3.3 For i ≥ 0 and a ∈ Σ w , µ i w (ψ w (ϕ k-1 w (a))) = ψ w (ϕ k-1+i w (a)).
Proof. Let a ∈ Σ w . Since the automaton A w is minimal, the state a can be reached from the initial state a 0,w . Remark 2.1.2 then implies that a occurs in the sequence lim n→∞ ϕ n (a 0,w ). Let it be at position j.

Then Theorem 2.3.2 implies that

µ w (ψ w (ϕ k-1 w (a))) = µ w (t w (2 k-1 j)• • • t w (2 k-1 j + 2 k-1 -1)) = t w (2 k j)• • • t w (2 k j + 2 k -1) = ψ w (ϕ k w (a)) = ψw(ϕ k-1 w (ϕ(a))). (3)
The

Σ 010 = { λ, 0 , 0, 0 , 01, 0 , λ, 1 , 0, 1 , 01, 1 }, F 010 = { λ, 1 , 0, 1 , 01, 1 }
and the transition function is given by the following table

δ 010 0 1 λ, 0 0, 0 λ, 0 0, 0 0, 0 01, 0 01, 0 0, 1 λ, 0 δ 010 0 1 λ, 1 0, 1 λ, 1 0, 1 0, 1 01, 1 01, 1 0, 0 λ, 1 (5)
The morphism ϕ 010 is described by the rows of the

We will further use the following two easy observations without explicitly referring to them.

Observation 2.3.5 Let r ≥ 1. x ∈ Σ ∞ w .
No symbol from Σ can occur in ϕ r w (x) both in an even and in an odd position.

( ā) = ϕ r w (a)
2. For each a ∈ Σ w and r ≥ 0, ψ w (ϕ r w ( ā)) = ψ w (ϕ r w (a))

3. For each x ∈ ([2] k-1 ) ∞ , µ w ( x) = µ w (x).
In the remaining part of this text we will omit the subscript w from A w , Σ w , δ w , δ * w , a 0,w , F w , ϕ w , ψ w , µ w and χ w .

3 Generalized words of Thue and the lexicographic order

Lexicographic order on the set Σ ∞

We consider the set [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] ∞ to be ordered lexicographically based on the ordering 0 < 1 of [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF]. We will investigate the factors of the sequence t w and their properties related to this lexicographic ordering. The structure of the sequence t w closely matches the structure of the sequence τ w = lim n→∞ ϕ n (a 0 ) ∈ Σ ω . It seems to be useful to look for an order relation on Σ (and the corresponding lexicographic order on Σ ∞ ) related to the order of the block factors of Σ of the form ψ(ϕ r (a)), such that the morphism ϕ is growing on Σ ∞ . Since t w is a fixed point of the (2 k-1 , 2 k )-substitution µ, one would expect that the relative order of two symbols a, b ∈ Σ should be implied by the order of the words ψ(ϕ k-1 (a)), ψ(ϕ k-1 (b)). This choice need not be (always) suitable as illustrated by the following example.

Example 3.1.1 Consider w = 10 s , s ≥ 2, hence k -1 = s, k -1 + s = 2s. Let a = 1, 1 , b = 10 s-1 , 1 . Then ψ(δ * (a, i [2],2s-1 )) = 0 for i < 2 s-1 ; 1 for i = 2 s-1 ; ψ(δ * (a, i [2],2s )) = 0 for i ≤ 2 s ; ψ(δ * (b, i [2],2s-1 )) = 0 for i ≤ 2 s-1 ; ψ(δ * (b, i [2],2s )) = 0 for i < 2 s ; 1 for i = 2 s . Therefore ψ(ϕ k-1+s-1 (a)) > ψ(ϕ k-1+s-1 (b)) and ψ(ϕ k-1+s (a)) < ψ(ϕ k-1+s (b)).
For the rest of the paper, denote by s the length of the longest suffix of w belonging to 0 * . Example 3.1.1 documented that choosing for the definition of the order relation on Σ an exponent of ϕ smaller than k -1 + s results in an order relation, with respect to which ϕ is not a growing function. Therefore we will consider the ordering of Σ based on the blocks ψ(ϕ k-1+s (a)).

Definition 3.1.2 The (total) order relation

< on Σ is defined, for a, b ∈ Σ, as a < b iff ψ(ϕ k-1+s (a)) < ψ(ϕ k-1+s (b)) .
The relation < is indeed an order relation due to the following Lemma.

Lemma 3.1.3 Let a, b ∈ Σ, a = b. Then, for r ≥ 0, ψ(ϕ k-1+r (a)) = ψ(ϕ k-1+r (b)). Proof. Let a = α, m , b = β, n , a = b and let d ∈ [2] be different from the last symbol of w. We will use Remark 2.1.2. If m = n then α = β, assume |α| < |β|. Let w = βγ. Then ψ(δ * (a, γd k-1+r-|γ| )) = m, ψ(δ * (b, γd k-1+r-|γ| )) = 1 -n = m. If m = n then ψ(δ * (a, d k-1+r )) = m = n = ψ(δ * (b, γd k-1+r-|γ| )). ✷

Monotonicity of ϕ and µ

The total order of Σ induces the lexicographic order on Σ ∞ . We will denote

Ψ = ψ • ϕ k-1+s . Clearly, the (k -1 + s)-uniform morphism Ψ : Σ ∞ → [2] ∞ is a strictly growing function. Property 2.1.2 implies Property 3.2.1 For i ≥ 0 and x ∈ Σ * , µ i (Ψ(x)) = Ψ(ϕ i (x)).
We want to show that the morphism ϕ is strictly growing, as well. To prove it we need Property 3.2.2, which was proved in [START_REF] Černý | On a class of infinite words with bounded repetitions[END_REF] and one more technical lemma. Proof. Assume r is not a multiple of 2 s , i.e., r ≥ 1 and 0 s is not a suffix of r [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],k-1+s . Denote ρ the word obtained from r [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],k-1+s by removing the last symbol. Let a = α, m , b = β, n . Since neither of αr [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],k-1+s , βr [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],k-1+s contains the suffix w, we have The following Corollary 3.2.6 follows from Property 3.2.1.

ψ(δ * (a, r [2],k-1+s )) = ψ(δ * (a, ρ))and ψ(δ * (b, r [2],k-1+s )) = ψ(δ * (b, ρ)), hence ψ(ϕ k-1+s (a)) and ψ(ϕ k-1+s (b)) differ in position ⌊r/2⌋ < r -a contradiction to the minimality of r. ✷ Lemma 3.2.4 For a, b ∈ Σ, if a < b then ϕ(a) < ϕ(b).

Corollary 3.2.6 µ is strictly growing on

{Ψ(x); x ∈ Σ ∞ }.
In the remaining part of the paper we will provide the characterization of the Lyndon factorization of the sequence t w for four different shapes of the word w.

4 Factorization of four types of generalized words of Thue.

We consider here four types of generalized Thue sequences, based on the shape of the underlying word w. For each type we provide a theorem describing the Lyndon factorization of the sequence t w . Typically, the Lyndon factorization of t w starts by an initial finite sequence of Lyndon factors (we will call this part the "preamble" of the factorization) , followed by a product of a recurrently described infinite sequence of Lyndon factors (the "body" of the factorization). The length of the preamble may grow with the increasing length of the word w. The recurrent description of the body is based on the generating substitution µ w . Proofs of the theorems from this section can be found in Section 5. Each theorem is followed by an example of factorization of one sequence t w of the particular type, together with the corresponding mappings µ w and ϕ w . In the examples, we include spaces to increase readability of t w . The first symbol of each Lyndon factor of t w is underlined. The morphism ϕ w is given for arguments of the form α, 0 only. The values for arguments of the form α, 1 can be obtained by replacing each 0 or 1 in the second position by the complementary value.

Case

w = 0 k-1 1 Theorem 4.1.1 Let w = 0 k-1 1. Then t w = ∏ ∞ i=0 w i where w 0 = 01 2 k , w 1 = 01 2 k -1 , w i+1 = 1 -1 µ(1w i 1 -1 )1 for i > 1. For i ≥ 0,
ϕ 001 λ, 0 → 0, 0 λ, 0 0, 0 → 00, 0 λ, 0 00, 0 → 00, 0 λ, 1 4.2 Case w = 10 k-2 1 Theorem 4.2.1 Let w = 10 k-2 1, k ≥ 3 ‡ . Then t w = ∏ ∞ i=0 w i where w 0 = 0 2 k-1 +1 10 2 k-1 1 2 0 2 k-1 -3 1; w 1 = 0 6 101 2 0 2 1 2 01 if k = 3; 0 2 k-1 +2 1 4 0 2 k-1 -7 10 2 k-1 1 2 0 2 k-1 -3 1 if k > 3; w i+1 = 0 2 k-1 -2 µ((0 2 k-1 -2 ) -1 w i 0 2 k-1 -2 )(0 2 k-1 -2 ) -1 for i ≥ 1.
For i ≥ 0, the word w i is a Lyndon word and w i > w i+1 . t 1001 0 ¯0000000 01000000 00110000 010 ¯00000 00001111 01000000 00110000 010 ¯00000 00000000 10111111 00110000 01000000 00001111 01000000 00110000 010 ¯00000 00000000 01000000 11001111 10111111 00001111 01000000 00110000 01000000 00000000 10111111 00110000 01000000 00001111 01000000 00110000 010 ¯00000 00000000 01000000 00110000 01000000 11110000 10111111 11001111 10111111 00000000 10111111 00110000 01000000 00001111 01000000 00110000 01000000 00000000 01000000 11001111 10111111 00001111 01000000 00110000 01000000 00000000 10111111 00110000 01000000 00001111 01000000 00110000 010 ¯00000 00000000 01000000 00110000 01000000 00001111 01000000 00110000 01000000 11111111 01000000 11001111 10111111 11110000 10111111 11001111

ϕ 1001 λ, 0 → λ, 0 1, 0 1, 0 → 10, 0 1, 0 10, 0 → 100, 0 1, 1 100, 0 → λ, 0 1, 1 4.3 Case w = 1 k . Theorem 4.3.1 Let w = 1 k ,. k ≥ 2. Then t w = ∏ ∞ i=0 w i where w 0 = 0 2 k -1 10 2 k-2 1, w 1 = w -1
0 µ 2 (w 0 0)0 -1 and w i+1 = 0µ 2 (0 -1 w i 0)0 -1 for i ≥ 1. For i ≥ 0, the word w i is a Lyndon word and w i > w i+1 .

ϕ 11 λ, 0 → λ, 0 1, 0 1, 0 → λ, 0 1, 1 4.4 Case w = 10 k-1 Theorem 4.4.1 Let w = 10 k-1 , k ≥ 2. Denote ρ = µ 2k-2 (1 2 k-1 )µ k-1 (0 2 k-1 )(0 2 k-1 -1 ) -1 , j 0 = 0, j 1 = 10 k-1 10 2k-2 2 j 2 = 10 k 10 2k-2 2 ,
and, for

1 ≤ r ≤ k -1, denote j 2r+1 = 10 k-1 10 k-1 1 r 0 k-2 1 2 , j 2r+2 = 10 k 10 k-1 1 r 0 k-2 1 2 .
For 0 ≤ i ≤ 2k -1, let w i be the factor of t w of length j i+1j i at the position j i and,

for i ≥ 2k, let w i = ρ -1 µ(ρw i-1 ρ -1 )ρ. Then t w = ∏ ∞ i=0 w i and, for i ≥ 0, w i > w i+1 ,
ϕ 100 λ, 0 → λ, 0 1, 0 1, 0 → 10, 0 1, 0 10, 0 → λ, 1 1, 0
5 Proofs of the factorization results.

The present part contains proofs of the four theorems from Section 3. In each of the four cases, we start by observing some specific properties of ϕ w , Ψ w , A w and µ w for the particular shape of w. The proof of each of the theorems consists of the following parts:

Part A. We prove the consistency of the recurrent formula for factors w i and we show that the sequence t w can be written as a concatenation of the factors w i .

Part B.

We prove that w 0 , w 1 , . . . is a decreasing sequence.

Part C. We show that each word w i is a Lyndon word-separately for the preamble and for the body of the factorization.

Case

w = 0 k-1 1 Let w = 0 k-1 1, k ≥ 2 § . In this case s = 0, Ψ = ψ • ϕ k-1 and each element of Σ is of the form 0 r , m for some r ∈ [k], m ∈ [2]. The initial state of A is 0 k-1 , 0 .
We have a simple equivalent characterization of the order relation on Σ for this case. Proof.

If 0 = m < n = 1 then ψ(δ * (a, 0 k-1 )) = 0, ψ(δ * (b, 0 k-1 )) = 1, and a < b. Now let m = n. For r ∈ {p, q}, i ∈ [2 k-1 ] we have Ψ( 0 r , m )(i) = ψ(δ * ( 0 r , m , i [2],k-1 )) = m if i = 0 or i ≥ 2 r ; 1 -m for 1 ≤ i < 2 r . (7)
Thus

Ψ( 0 r , m ) has the prefix m(1 -m) 2 r -1 . If m = 0 then a < b iff p < q, if m = 1 then a < b iff p > q.
✷ The following complete description of the mapping ϕ can be easily obtained using Remark 2.1.2. Property 5.1.2 ϕ( 0 r , 0 ) = 0 r+1 , 0 λ, 0 for 0 ≤ r < k -1, and ϕ(

0 k-1 , 0 ) = 0 k-1 , 0 λ, 1 .
The first of the next two properties may be obtained, considering Remark 2.1.2, by observing the shapes of the words i

[2],k-1 , i ∈ [2 k-1 ].
The second is a consequence of the trivial fact that the binary representation of a position number has suffix 0 iff the position number is even. Proof. Observing the shape of the words r [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],k+2 , for 0 ≤ r ≤ 2 k+1 , we find

Property 5.1.3 Let a ∈ Σ. If 0 2 is a prefix of Ψ(a) then a = λ, 0 . If 0 2 k-1 -1 is a suffix of Ψ(a) then a = λ, 0 or a = 0 k-1 , 1 .
ψ(δ * ( 0 k-1 , 0 , r [2],k+2 )) =          0 if r = 0; 1 if 0 < r ≤ 2 k ; 0 if r = 2 k + 1; 1 if 2 k + 1 < r ≤ 2 k+1 . ( 8
)
Therefore t w has the prefix 01 2 k 01 2 k -1 . ✷ Lemma 5.1.6 For i ≥ 1, 11 is a suffix of w i and 1w i 1 -1 = Ψ(ϕ i ( λ, 1 ).

Proof. The assertion is true for i = 1 since w 1 = 01 2 k -1 and 1w 1 1 -1 is a factor of t w at position 2 k , as implied by Lemma 5.1.5. Assume that the assertion is true for some i ≥ 1. Then 1 is both a prefix and a suffix of 1w i 1 -1 . Theorem 2.3.2 implies that 1 is both a prefix and a suffix of µ(1w i 1 -1 ) since w [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] is neither a suffix of 0 [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],k+i nor of (2 k+i -1) [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],k+i . Hence 11 is a suffix of w i+1 = 1 -1 µ(1w i 1 -1 )1. Using Property 3.2.1 we obtain

1w i+1 1 -1 = 11 -1 µ(1w i 1 -1 )11 -1 = µ(1w i 1 -1 ) = µ(Ψ(ϕ i ( λ, 1 )) = Ψ(ϕ i+1 ( λ, 1 ). (9)
✷ Lemma 5.1.7 t w = ∏ ∞ i=0 w i . Proof. Since t w is a fixed point of µ, the image in µ of the prefix 01 2 k -1 of length 2 k of t w is the prefix of length 2 k+1 of t w . Then

µ(∏ ∞ i=0 w i ) = µ(01 2 k ∏ ∞ i=1 w i ) = µ(01 2 k -1 ∏ ∞ i=1 (1w i 1 -1 )) = µ(01 2 k -1 ) ∏ ∞ i=1 µ(1w i 1 -1 )) = (w 0 w 1 1 -1 ) ∏ ∞ i=1 µ(1w i 1 -1 )) = (w 0 w 1 1 -1 ) ∏ ∞ i=1 (1w i+1 1 -1 ) = ∏ ∞ i=0 w i . (10)
Both sequences t w and ∏ ∞ i=0 w i are fixed points of µ starting by the same prefix of length 2 k-1 , therefore

t w = ∏ ∞ i=0 w i . ✷ Part B Lemma 5.1.8 (w i ) ∞
i=0 is a decreasing sequence of words. Proof. Clearly w 0 > w 1 . Property 5.1.1 implies that λ, 1 > 0, 1 λ, 1 = ϕ( λ, 1 ). Since ϕ an Ψ are strictly growing, we get, for i ≥ 1, ϕ i ( λ, 1 ) > ϕ i+1 ( λ, 1 ), and, consequently,

w i = 1 -1 Ψ(ϕ i ( λ, 1 ))1 > 1 -1 Ψ(ϕ i+1 ( λ, 1 ))1 = w i+1 ✷ Part C
We start by observing the fact that w 0 is strictly smaller than any of its non-empty proper suffixes. Observation 5.1.9 The word w 0 is a Lyndon word. Lemma 5.1.10 For 1 ≤ i ≤ k, w i = 0 2 i -1 1 2 k -2 i x i , where x i does not contain a factor 0 2 i -1

Proof. For 0 ≤ r ≤ k -2, ϕ( 0 r , 0 ) = 0 r+1 , 0 λ, 0 and (for r = k -1) ϕ( 0 k-1 , 0 ) = 0 k-1 , 0 λ, 1 . An easy induction yields, for 0

≤ i ≤ k -1, ψ(ϕ i ( λ, 0 )) = ψ( 0 i , 0 λ, 0 ϕ( λ, 0 )ϕ 2 ( λ, 0 ) • • • ϕ i-1 ( λ, 0 )) = 0 2 i . For 1 ≤ i ≤ k, ψ(ϕ k-1+i ( λ, 1 )) = xy ( 11
)
where

x = ψ( 0 k-1 , 1 λ, 0 ϕ( λ, 0 )• • •ϕ i-1 ( λ, 0 )ϕ i ( λ, 1 )• • •ϕ k-1 ( λ, 1 )) = 10 2 0 +2 1 +•••2 (i-1) 1 2 i +2 i+1 +•••2 k-1 and y = ψ(ϕ k-1+1 ( λ, 1 )• • •ϕ k-1+i-1 ( λ, 1 )) = Ψ(ϕ( λ, 1 ))• • •Ψ(ϕ i-1 ( λ, 1 )).
Hence, following Lemma 5.1.6,

w i = 1 -1 ψ(ϕ k-1+i ( λ, 1 ))1 = 0 2 i -1 1 2 k -2 i (1w 1 1 -1 )• • •(1w i-1 1 -1 )1 = 0 2 i -1 1 2 k -2 i w 1 • • •w i-1 , (12)
where w 1 • • •w i-1 does not contain a factor 0 2 i -1 , the latter fact follows by induction. ✷ Corollary 5.1.11 w 1 , . . ., w k are Lyndon words Lemma 5.1.12 For i ≥ k + 1, 0 2 k is a prefix of w i .

Proof. It is enough to prove the assertion for w k+1 , since, by Lemma 5.1.8, for i > k + 1, w k+1 > w i . From Lemma 5.1.6 we obtain

w k+1 = 1 -1 Ψ(ϕ k+1 ( λ, 1 ))1 = 1 -1 Ψ( 0 k-1 , 1 λ, 0 0, 0 x)1 = 1 -1 10 2 k-1 -1 0 2 k-1 010 2 k-1 -2 Ψ(x) = 0 2 k y ( 13
)
where x ∈ Σ * , y ∈ [2] * are suitable words. ✷ Lemma 5.1.13 For i ≥ 1, w 1 is a primitive word.

Proof. Denote ω = Ψ(ϕ i ( λ, 1 )). By Lemma 5.1.6, w i = 1 -1 ω1. Assume that w i is not primitive. Then neither is ω. Since the length of ω is a positive power of 2, ω is a concatenation of two equal factors, implying ϕ(b 1 ) = aa for some symbol a ∈ Σ -a contradiction to Proposition 2.3.5. ✷ Lemma 5.1.14 For i ≥ k, w i is a Lyndon word.

Proof. By induction. For i = k the assertion follows from Corollary 5.1.11. Let i > k. Assume that w i-1 is a Lyndon word. By Lemma 5.1.13, w i is not primitive. Assume that w i is not minimal in its conjugacy class. Let w i = uv where vu < w i is the smallest conjugate of w i . The minimality of vu implies that the last symbol of u is 1. The word vu, as a conjugate of ω, is of the form ξ 0 x 1 x 2 yξ ′ 0 , ξ 0 = λ, where ξ ′ 0 ξ 0 = Ψ(c 0 ),

x 1 = Ψ(c 1 ), x 2 = Ψ(c 2 ) for some c 0 , c 1 , c 2 ∈ Σ and ξ ′ 0 ξ 0 x 1 x 2 y = Ψ(c 0 c 1 c 2 z) for some conjugate c 0 c 1 c 2 z of ϕ i ( λ, 1
). Since 0 2 k is a prefix of w i , 0 2 k must be a prefix of vu. The last symbol of v is 1 (the last symbol of w i ) therefore 0 2 k is a prefix of v. Hence ξ 0 x 1 ∈ 0 * , and, consequently, x 1 = 0 2 k-1 and c 1 = λ, 0 .

Property 5.1.4 implies that c 0 = λ, 0 , c 2 = λ, 0 , otherwise λ, 1 occurs in two neighbor positions. As a consequence of Property 5.1.3, x 1 x 2 has the prefix 0 2 k-1 +1 1 or 0 2 k-1 1 . Therefore ξ 0 has the suffix 0 2 k-1 -1 and, again by Property 5.1.3, c 0 = 0 k-1 , 1 and ξ ′ 0 = 1. We have

Ψ(c 0 c 1 c 2 z) = ξ ′ 0 ξ 0 x 1 x 2 y = 1vu1 -1 < 1w i 1 -1 = Ψ(ϕ i ( λ, 1 )) ( 14
)
yielding c 0 c 1 c 2 z < ϕ i ( λ, 1 ). The word c 0 c 1 c 2 z = 0 k-1 , 1 λ, 0 c 2 z is a conjugate of ϕ i ( λ, 1 ), hence either 0 k-1 , 1 λ, 0 c 2 z or λ, 0 c 2 z 0 k-1 , 1 is
an image in ϕ of some word from Σ * , the latter case contradicting Property 5.1.4.

Thus 0 k-1 , 1 λ, 0 c 2 z = ϕ(z ′ ) for some conjugate z ′ of ϕ i-1 ( λ, 1 ) where the initial symbol of z ′ is either 0 k-1 , 1 or 0 k-2 , 1 , in both cases the first symbol of Ψ(z ′ ) is 1. Since ϕ(z ′ ) < ϕ i ( λ, 1 ), we have z ′ < ϕ i-1 ( λ, 1 ) and Ψ(z ′ ) < Ψ(ϕ i-1 ( λ, 1 )) implying 1 -1 Ψ(z ′ )1 < 1 -1 Ψ(ϕ i-1 ( λ, 1 ))1 = w i-1 ( 15
)
where the left-hand side is a conjugate of w i-1 -a contradiction to the inductive hypothesis that w i-1 is a Lyndon word. ✷ Let w = 10 k-2 1, k ≥ 3. In this case s = 0, Ψ = ψ • ϕ k-1 and each element of Σ is of the form 10 r , m for some r ∈

[k -1], m ∈ [2]. The initial state of A is λ, 0 .
The first of the following two properties may be observed applying Remark 2.1.2. The second one follows from the fact that the only proper prefix of w finished by 1 is 1.

Property 5.2.1 for r ∈ [k -1], ψ(ϕ r ( λ, 0 )) = ψ(ϕ r ( 1, 0 )) = 0 2 r , and
Ψ( λ, 0 ) = 0 2 k-1 , Ψ( 10 r , 0 ) = 0 2 r 1 2 r 0 2 k-1 -2 r+1 .
Property 5.2.2 If a symbol a ∈ Σ occurs in an odd position of a word of the form ϕ(x), x ∈ Σ * , then a = 1, 0 or a = 1, 1 .

Proof of Theorem 4.2.1

Part A Lemma 5.2.3 w 0 w 1 is a prefix of t w and w

1 = 0 2 k-1 -2 Ψ(ϕ 2 ( 1, 0 ))(0 2 k-1 -2 ) -1 .
Proof. The sequence t w has the prefix

Ψ(ϕ 3 ( λ, 0 )) = Ψ( λ, 0 1, 0 10, 0 1, 0 λ, 0 1, 1 10, 0 1, 0 ) if k = 3; Ψ( λ, 0 1, 0 10, 0 1, 0 100, 0 1, 0 10, 0 1, 0 ) if k > 3. ( 16
)
In both cases Property 5.2.1 implies

Ψ(ϕ 2 ( λ, 0 1, 0 )) = w 0 w 1 0 2 k-1 -2 and ( 17
)
(0 2 k-1 -2 ) -1 w 1 0 2 k-1 -2 = Ψ(ϕ 2 ( 1, 0 )) (18)
since the latter word is a factor of t w of the length 2 k+1 starting at position 2 k+1 .

✷ Lemma 5.2.4 For i ≥ 1, 0 2 k-1 -2 is a suffix of µ((0 2 k-1 -2 ) -1 w i 0 2 k-1 -2
) and

w i = 0 2 k-1 -2 Ψ(ϕ i+1 ( 1, 0 ))(0 2 k-1 -2 ) -1 .
Proof. Theorem 2.3.2 implies that the string µ(x0 2 k-1 -2 ), where x0 2 k-1 -2 is a string of a length, which is a multiple of 2 k-1 , ends in a string of length 2 k -4 containing 0 in all positions i except those where i [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF],⌈log i⌉ ends in w. This is not true for the last 2 k-1 -2 position numbers, therefore 0 occurs in these positions. The proof of the latter part of the assertion of the lemma is a simple induction where Lemma 5.2.3 provides the basic step and Property 3.2.1 is applied in the inductive step. ✷ Lemma 5.2.5 t w = ∏ ∞ i=0 w i . Proof. Since t w is a fixed point of µ, the image in µ of the prefix w 0 0 2 k-1 -2 of length 2 k+1 of t w is the prefix w 0 w 1 0 2 k-1 -2 of length 2 k+2 of t w . Applying Lemma 5.2.4 and Property 3.2.1 we obtain

µ(∏ ∞ i=0 w i ) = µ(w 0 0 2 k-1 -2 ∏ ∞ i=1 (0 2 k-1 -2 ) -1 w i 0 2 k-1 -2 ) = µ(w 0 0 2 k-1 -2 ∏ ∞ i=1 Ψ(ϕ i+1 ( 1, 0 ))) = µ(w 0 0 2 k-1 -2 ) ∏ ∞ i=1 µ(Ψ(ϕ i+1 ( 1, 0 ))) = w 0 w 1 0 2 k-1 -2 ∏ ∞ i=1 Ψ(ϕ i+2 ( 1, 0 )) = (w 0 w 1 0 2 k-1 -2 ) ∏ ∞ i=1 (0 2 k-1 -2 ) -1 w i+1 0 2 k-1 -2 ) = ∏ ∞ i=0 w i ( 19
)
Both sequences t w and ∏ ∞ i=0 w i are fixed points of µ starting by the same prefix of length 2 k-1 , therefore

t w = ∏ ∞ i=0 w i . ✷ Part B Lemma 5.2.6 For i ≥ 0, w i > w i+1 .
Proof. Clearly, w 0 > w 1 . Let i ≥ 1. Property 5.2.1 implies that

Ψ( 1, 0 ) > Ψ( 10, 0 ), therefore 1, 0 > 10, 0 1, 0 = ϕ( 1, 0 ),
and Lemma 5.2.4 implies

w i = 0 2 k-1 -2 Ψ(ϕ i+1 ( 1, 0 ))(0 2 k-1 -2 ) -1 > 0 2 k-1 -2 Ψ(ϕ i+2 ( 1, 0 ))(0 2 k-1 -2 ) -1 = w i+1 . ✷ Part C Lemma 5.2.7 For i ∈ [k -1], w i is a Lyndon word.
Proof. Applying Property 5.2.1, for 2 ≤ i ≤ k -2, we obtain

(0 2 k-1 -2 ) -1 w i 0 2 k-1 -2 = Ψ(ϕ i+1 ( 1, 0 )) = ψ(ϕ k+i ( 1, 0 )) = ψ(ϕ i+2 ( 10 k-2 , 0 1, 0 ϕ( 1, 0 )• • •ϕ k-3 ( 1, 0 ))) = ψ(ϕ i+1 ( λ, 0 1, 1 ϕ( 1, 0 )• • •ϕ k-2 ( 1, 0 ))). (20)
If i < k -2 then

(0 2 k-1 -2 ) -1 w i 0 2 k-1 -2 = 0 2 i+1 1 2 i+1 ψ(ϕ i+2 ( 1, 0 )• • •ϕ k+i-1 ( 1, 0 )) = 0 2 i+1 1 2 i+1 xyz (21) where x = ψ(ϕ i+2 ( 1, 0 )• • •ϕ k-2 ( 1, 0 )) = 0 2 i+2 +•••+2 k-2 = 0 2 k-1 -2 i+2 y = ψ(ϕ k-1 ( 1, 0 )ϕ k ( 1, 0 )) = Ψ( 1, 0 10, 0 1, 0 ) = (010 2 k-1 -2 )(0 2 1 2 0 2 k-1 )(010 2 k-1 -2 ) z = ψ(ϕ k+1 ( 1, 0 )• • •ϕ k+i-1 ( 1, 0 )) = (0 2 k-1 -2 ) -1 w 1 • • •w i-1 0 2 k-1 -2 (22)
and, consequently,

w i = 0 2 k-1 +2 i+1 -2 1 2 i+1 0 2 k-1 10 2 k-1 1 2 0 2 k-1 +1 1w 1 • • •w i-1 . If i = k -2 then (0 2 k-1 -2 ) -1 w i 0 2 k-1 -2 = Ψ( λ, 0 1, 1 ϕ( 1, 0 )ϕ 2 ( 1, 0 )• • •ϕ k-2 ( 1, 0 )) = xy (23) where x = Ψ( λ, 0 1, 1 Ψ(ϕ( 1, 0 )) = (0 2 k-1 )(101 2 k-1 -2 )(0 2 1 2 0 2 k-1 -4 010 2 k-1 -2 ) y = Ψ(ϕ 2 ( 1, 0 ))• • •Ψ(ϕ k-2 ( 1, 0 )) = (0 2 k-1 -2 ) -1 w 1 • • •w i-1 0 2 k-1 -2 (24)
and, consequently,

w i = 0 2 k -2 101 2 k-1 -2 0 2 1 2 0 2 k-1 -3 1w 1 • • •w i-1 .
In both cases, denote as α the prefix of w i satisfying

w i = αw 1 • • •w i-1 .
Let us now prove the assertion of the lemma by induction. Each of the words w 0 , w 1 is smaller than any of its non-empty proper suffixes, therefore they are Lyndon words. Let us now assume that w 0 , . . .,

w i-1 , 2 ≤ i ≤ k -2, are Lyndon words. If β = λ is a proper suffix of α then 0 2 k +2 i+1 -2 is not a factor of β, hence w i < β < βw 1 • • •w i-1 . If β = λ is a proper suffix of some w j , j ∈ [i], then Lemma 5.4.7 implies w i < w j < β < βw 1 • • •w i-1 since w j is a Lyndon word. Moreover, w i < w j < w j • • •w i-1 for j ∈ [i].
Therefore w i is a Lyndon word, since it is smaller than any of its non-empty proper suffixes. ✷ Lemma 5.2.8 If λ, 0 x ∈ Σ * is a conjugate of a word ϕ 2 (y) for some y ∈ Σ * then λ, 0 x = ϕ 2 (y ′ ) for some conjugate y ′ of y and the last symbol of ϕ(y ′ ) is 1, 0 .

Proof. Assume the smallest number r, 0 ≤ r ≤ 2, such that λ, 0 x = ϕ 2-r (z) for some conjugate z of ϕ r (y). If r > 0 then, as implied by Property 5.2.2, z starts either by 1, 0 or by 1, 1 . Consequently, λ, 0 x = ϕ 2-r (z) starts by 10 2-r , 0 or by 10 2-r , 1 -a contradiction. The second assertion of the lemma follows from the observation, that if, for some a ∈ Σ, ϕ(a) ends in 1, 0 then either a = 10 k-2 , 1 or a = 1, 0 . As follows from Property 5.2.2, the former case is not possible if a is the last symbol of ϕ(y ′ ). ✷ Lemma 5.2.9 For i ≥ 1, w 1 is a primitive word.

Proof. Analogous to the proof of Lemma 5.1.13. ✷ Lemma 5.2.10 For i ≥ k -2, w i is a Lyndon word.

Proof. We proceed by induction. For i = k -2 the assertion follows from Lemma 5.2.7.

Let i ≥ k -1 and let w i-1 be a Lyndon word. Lemma 5.2.9 states that w i is not primitive. Assume that w i is not minimal in its conjugacy class. Let w i = uv where vu < w i is the smallest conjugate of w i (and of ω). The minimality of vu implies that the last symbol of u is 1. The word vu, as a conjugate of w i , is of the form ξ 0 x 1 x 2 yξ ′ 0 , ξ 0 = λ, where ξ ′ 0 ξ 0 = Ψ(c 0 ),

x 1 = Ψ(c 1 ), x 2 = Ψ(c 2 ) for some c 0 , c 1 , c 2 ∈ Σ and ξ ′ 0 ξ 0 x 1 x 2 y = Ψ(c 0 c 1 c 2 z) for some conjugate c 0 c 1 c 2 z of ϕ i+1 ( 1, 0 ). The prefix of (0 2 k-1 -2 ) -1 w i is Ψ(ϕ i+1-(k-1) ( λ, 0 )) being a prefix of length 2 i+1 ≥ 2 k of t w . Therefore w i has the prefix 0 2 k-1 -2 0 2 k-1 +1 1 = 0 2 k -1 1.
This must be a prefix of vu, as well.

Either ξ 0 x 1 ∈ 0 * or x 1 = 0 2 k-1 -1 1, the latter case is not possible due to Property 5.2.1, hence x 1 = 0 2 k-1 and c 1 = λ, 0 . Property 5.2.2 implies that c 0 = λ, 0 , and, again using Property 5.2.1, c 0 = 1, 0 , ξ 0 = 0 2 k-1 -2 , ξ ′ 0 = 01, and c 2 = 1, 0 . Following Lemma 5.2.8, c 1 c 2 zc 0 = ϕ 2 (y ′ ) for some conjugate y ′ of ϕ i-1 ( 1, 0 ) where the last symbol of ϕ i (y ′ ) is 1, 0 . We have

Ψ(c 1 c 2 zc 0 ) = x 1 x 2 yξ ′ 0 ξ 0 = ξ -1 0 vuξ 0 < ξ -1 0 w i ξ 0 = Ψ(ϕ i+1 ( 1, 0 )) yielding ϕ 2 (y ′ ) = c 1 c 2 zc 0 < ϕ i+1
( 1, 0 ) and ϕ(y ′ ) < ϕ i ( 1, 0 ). Since the suffix 1, 0 is preserved by ϕ, the strings on both sides of the last inequality are finished by 1, 0 , therefore Ψ(ϕ(y ′ )) < Ψ(ϕ i ( 1, 0 )) and the strings on both sides of the last inequality are finished by

Ψ( 1, 0 ) = 010 2 k-1 -2 . Hence 0 2 k-1 -2 Ψ(ϕ(y ′ ))(0 2 k-1 -2 ) -1 < 0 2 k-1 -2 Ψ(ϕ i ( 1, 0 ))(0 2 k-1 -2 ) -1 = w i-1
-a contradiction, since the left-hand side is a conjugate of w i-1 and w i-1 is a Lyndon word. ✷ Theorem 4.1.1 now follows from Lemma 5.2.5, Lemma 5.2.6, Lemma 5.2.7 and Lemma 5.2.10.

Case w

= 1 k . Let w = 1 k , k ≥ 2 . In this case s = 0, Ψ = ψ • ϕ k-1 and each element of Σ is of the form 1 r , m for some r ∈ [k], m ∈ [2]. The initial state of A is a 0 = λ, 0 .
The first of the following two properties follows from Remark 2.1.2. The second is based on the fact that the last symbol of each non-empty prefix of w is 1.

Property 5.3.1 for r ∈ [k -1], ψ(ϕ r ( λ, 0 )) = ψ(ϕ r ( 1, 0 )) = 0 2 r , and
Ψ( λ, 0 ) = 0 2 k-1 , Ψ( 1, 0 ) = 0 2 k-1 -1 1,
and, for k ≥ 3, r ≥ 2,

Ψ( 1 r , 0 ) = 0 2 k-1 -2 r-1 1 2 r-2 0 2 r-3 1 2 r-4 0 2 r-5 • • •d 2 0 (1 -d)
where d = 0 if r is odd and d = 1 if r is even. Property 5.3.2 If a symbol a ∈ Σ occurs in an even position of a word of the form ϕ(x), x ∈ Σ * , then a = λ, 0 or a = λ, 1 . No symbol from Σ can occur both in an even and in an odd position of ϕ(x).

Proof of Theorem 4.3.1 Part

A Lemma 5.3.3 w 0 w 1 is a prefix of t w , w 1 = 0Ψ(ϕ 2 ( 1, 0 )ϕ 3 ( 1, 0 ))0 -1 and 0 2 k 1 is a prefix of w 1 .
Proof. Property 5.3.1 implies that

w 0 = Ψ( λ, 0 1, 0 λ, 0 1, 1 )0 -1 i if k = 2 and w 0 = Ψ( λ, 0 1, 0 λ, 0 11, 0 )0 -1 if k ≥ 3.
In each case, w i is smaller than any of its non-empty proper suffix. Let now i ≥ 2. By Lemma 5.3.4,

w i = 0Ψ(ϕ 2i ( 1, 0 )ϕ 2i+1 ( 1, 0 ))0 -1 = 0Ψ(ϕ 2i-1 ( λ, 0 1, 0 )ϕ 2i+1 ( 1, 0 ))0 -1 , (35)
therefore 0 -1 w i has the same prefix 0 2 k -1 1 as t w and w i has the prefix 0 2 k 1. Lemma 5.3.8 implies that w i is a primitive word. The word w i is a conjugate of Ψ(ϕ 2i ( 1, 0 )ϕ 2i+1 ( 1, 0 )). Assume that w i is not minimal in its conjugacy class. Let w i = uv where vu < w i is the smallest conjugate of w i . The minimality of vu implies that the last symbol of u is 1. The word vu is of the form ξ

0 x 1 x 2 yξ ′ 0 , ξ 0 = λ, where ξ ′ 0 ξ 0 = Ψ(c 0 ), x 1 = Ψ(c 1 ), x 2 = Ψ(c 2 ) for some c 0 , c 1 , c 2 ∈ Σ and ξ ′ 0 ξ 0 x 1 x 2 y = Ψ(c 0 c 1 c 2 z) for some conjugate c 0 c 1 c 2 z of ϕ 2i ( 1, 0 )ϕ 2i+1 ( 1, 0 ). Since 0 2 k
is a prefix of w i , 0 2 k must be a prefix of vu. Therefore ξ 0 x 1 ∈ 0 * , x 1 = 0 2 k-1 and, consequently, c 1 = λ, 0 . Property 5.3.2 then implies that c 0 = λ, 0 , c 2 = λ, 0 and from Property 5.3.1 we obtain that Ψ(c 2 ) does not have the prefix 0 2 k-1 . Hence Ψ(c 0 ) has the suffix 10, therefore ξ 0 = 0. This further implies that x 2 = 0 2 k-1 -1 1 and c 2 = 1, 0 . Now either c 0 c 1 c 2 z or c 1 c 2 zc 0 is of the form ϕ(z ′ ) where z ′ is a conjugate of ϕ 2i-1 ( 1, 0 )ϕ 2i ( 1, 0 ). The former case is not possible, since, by Property 5.3.2, c 1 = λ, 0 can occur only at even positions. If z ′ = az ′′ where a ∈ Σ then ϕ(a) = c 1 c 2 = λ, 0 1, 0 , hence a = λ, 0 . Now either az ′′ = ϕ(y ′ ) or z ′′ a = ϕ(y ′ ) for some y ′ ∈ Σ * being a conjugate of ϕ 2i-2 ( 1, 0 )ϕ 2i-1 ( 1, 0 ). Considering Property 5.3.2 again, a must appear in ϕ(y ′ ) at an even position, thus the former case takes place and

0 -1 vu0 = x 1 x 2 yξ ′ 0 ξ 0 = Ψ(ϕ(z ′ )) = Ψ(ϕ 2 (y ′ )). (36)
Moreover, since a = λ, 0 , the first symbol of ϕ k-1 (y ′ ) is λ, 0 , and the first symbol of

Ψ(y ′ ) is 0. Since vu < w i , Ψ(ϕ 2 (y ′ )) = 0 -1 vu0 < 0 -1 w i 0 = Ψ(ϕ 2i ( 1, 0 )ϕ 2i+1 ( 1, 0 )). ( 37
) Thus ϕ 2 (y ′ ) < ϕ 2i ( 1, 0 )ϕ 2i+1 ( 1, 0 ), (38)
y ′ < ϕ 2i-2 ( 1, 0 )ϕ 2i-1 ( 1, 0 ) (39)
and 0

-1 Ψ(y ′ )0 < 0 -1 Ψ(ϕ 2i-2 ( 1, 0 )ϕ 2i-1 ( 1, 0 ))0 = w i-1 . (40)
However, the left-hand side is a conjugate of the right-hand side and we have a contradiction to the inductive hypothesis that w i-1 is a Lyndon word. This concludes the proof of Theorem 4.1.1 Theorem 4.3.1 follows from Lemma 5.3.5, Lemma 5.3.6, and Lemma 5.3.9..

Case w

= 10 k-1 Let w = 10 k-1 , k ≥ 2 . In this case s = k -1, Ψ = ψ • ϕ 2k-2 and each element of Σ is of the form λ, m or 10 r , m for some r ∈ [k -1], m ∈ [2]. The initial state of A is a 0 = λ, 0 .
The first of the next two properties may be observed applying Remark 2.1.2. The second follows from the fact that the only prefix of w, which ends in 1 is 1.

(iv) w 2k-2 is the factor of t w of length j 2k-1j 2k-2 at position j 2k-2 . The length of ρ is

2 3k-3 + 2 2k-2 -2 k-1 + 1.
The suffix of w 2k-2 of length |ρ| is a factor of t w at position

j 2k-2 + |w 2k-1 | -|ρ| = j 2k-1 -|ρ| = 2 4k-3 .
This is the starting position of the factor Ψ(ϕ 2k-1 ( 1, 0 )), which by (iii) has the prefix ρ.

(v) We will prove the assertion by induction. Let first i = 2k -1. The factor of length |ρ| preceding the factor w 2k-1 in t w starts at position j 2k-1 -|ρ| = 2 4k-3 . This is the starting position of the factor Ψ(ϕ 2k-1 ( 1, 0 )), which by (iii) has the prefix ρ. Thus the first part of the assertion has been proved in (iii).

Since

|w 2k-1 | = j 2k-1 -|ρ| = 2 4k-3 , the word ρw 2k-1 ρ -1 is identical with Ψ(ϕ 2k-1 ( 1, 0 )) and w 2k-1 = ρ -1 Ψ(ϕ 2k-1 ( 1, 0 ))ρ. Now µ(ρw 2k-1 ρ -1 ) = µ(Ψ(ϕ 2k-1 ( 1, 0 ))) = Ψ(ϕ 2k ( 1, 0 )) (44)
having the prefix ρ by (iii).

Assume now that the assertion is true for some i ≥ 2k -1. Then

w i+1 = ρ -1 µ(ρw i ρ -1 )ρ = ρ -1 µ(Ψ(ϕ i ( 1, 0 )))ρ = ρ -1 Ψ(ϕ i+1 ( 1, 0 ))ρ (45)
and

µ(ρw i+1 ρ -1 ) = µ(Ψ(ϕ i+1 ( 1, 0 ))) = Ψ(ϕ i+2 ( 1, 0 )) (46)
has the prefix ρ according to (iii).

✷ Lemma 5.4.4 t w = ∏ ∞ i=0 w i Proof. Since t w is a fixed point of µ with the prefix w 0 of length greater than 2 k-1 , it is enough to prove that the sequence ∏ ∞ i=0 w i having the same prefix is a fixed point of µ as well. From the definition of the words w 0 , w 2k-1 , ρ we can observe that w 0 w

1 • • •w 2k-2 w 2k-1 is a prefix of t w , the length of w 0 w 1 • • •w 2k-2 ρ -1 is twice the length of w 0 w 1 • • •w 2k-2 ρ -1
and the length of the latter word is a multiple of 2 k-1 .We obtain:

µ(∏ ∞ i=0 w i ) = µ(w 0 w 1 • • •(w 2k-2 ρ -1 )ρw 2k-1 ρ -1 ) ∏ ∞ i=2k (ρw i ρ -1 )) = µ(w 0 w 1 • • •w 2k-2 ρ -1 )µ(ρw 2k-1 ρ -1 ) ∏ ∞ i=2k µ(ρw i ρ -1 ) = (w 0 w 1 • • •w 2k-2 w 2k-1 ρ -1 )ρw 2k ρ -1 ∏ ∞ i=2k (ρw i+1 ρ -1 ) = ∏ ∞ i=0 w i . ( 47
) since |w 0 w 1 • • •(w 2k-2 ρ -1 )| = 2 4k-3 and |w 0 w 1 • • •w 2k-2 (w 2k-1 ρ -1 )| = 2 4k-2 . ✷
and w 2 has the prefix 0 2 k-1 +1 1 2 k-1 -1 . The word ϕ( 1, 1 10, 0 ) has the prefix 10, 1 1, 1 and ϕ k-1 ( 10, 1 1, 1 ) has the prefix λ, 0 1, 0 10, 1 1, 1 .

Therefore the suffix of Ψ(ϕ( 1, 1 10, 0 ))

at position 2 k-1+1 -2 k-1 + 1 = 2 k-1 + 1 has the prefix (0 2 k-1 )(10 2 k-1 -1 )(0 2 1 2 k-1 -2 )(01 2 k-1 -1 )
and w 3 has the prefix 0

2 k-1 +1 1 2 k-1 -2 01 2 k-1 -1 . Clearly, w 2 > w 3 . ✷ Lemma 5.4.8 For i ≥ 2k -1, w i > w i+1
Proof. Using Remark 2.1.2, it is not difficult to observe that Ψ( 1, 0 ) has the prefix 1 2 k-1 +1 while Ψ( λ, 1 ) has the prefix 1 2 k-1 0. Hence Ψ( 1, 0 ) > Ψ( λ, 1 ) and 1, 0 > λ, 1 . Property 5. (i) The first two occurrences of the factor λ, 0 in τ are at positions ⌊ j 0 /2 k-1 ⌋ and ⌊ j 1 /2 k-1 ⌋.

(ii) The first two occurrences of the factor λ, 0 1, 1 in τ are at positions ⌊ j 1 /2 k-1 ⌋ and ⌊ j 2 /2 k-1 ⌋.

(iii) For 1 ≤ r ≤ k -2, the first two occurrences of the factor 1, 0 10 r , 1 are at positions ⌊ j 2r+1 /2 k-1 ⌋ and ⌊ j 2r+2 /2 k-1 ⌋.

(iv) The first two occurrences of the factor 1, 0 λ, 0 1, 1 in τ are at positions ⌊ j 2k-1 /2 k-1 ⌋ and ⌊ j 2k /2 k-1 ⌋.

(v) The first occurrence of the factor 1, 0 λ, 0 1, 0 in τ is at a position greater than ⌊ j 2k-1 /2 k-1 ⌋.

Proof.

(i) The first occurrence of λ, 0 after position 0 = ⌊ j 0 /2 k-1 ⌋ is at the position (10 k-1 10 k-1 ) [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] = ⌊ j 1 /2 k-1 ⌋.

(ii) If the factor λ, 0 1, 1 occurs in τ at (an even) position j then the symbol at position j/2 is 10 k-2 , 1 . This must be a prefix of a factor ϕ k-2 ( 1, 1 ). Since the first two occurrences of 1, 1 in τ are at positions (10 k-1 1) [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] = 2 k + 1 and (10 k 1) [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] = 2 k+1 + 1, the first two occurrences of the factor λ, 0 1, 1 in τ are at positions (2 k + 1).2 k-2 .2 = 2 2k-1 + 2 k-1 = ⌊ j 1 /2 k-1 ⌋ and (2 k+1 + 1).2 k-2 .2 = 2 2k + 2 k-1 = ⌊ j 2 /2 k-1 ⌋.

3. i = 3 or i = 4, k ≥ 3. As shown in the proof of Lemma 5.4.7, w 3 has the prefix 0 2 k-1 +1 1 2 k-1 -2 01 2 k-1 -1 and w 4 the same or smaller prefix. If a factor 0 2 k-1 +1 occurs in w 3 or w 4 at the position j of t w then the factor λ, 0 1, 1 occurs at position ⌊ j/2 k-1 ⌋ of τ. Hence 0 2 k-1 +1 occurs in w 3 or w 4 as a prefix of the factor 0 2 k-1 01 2 k-1 -1 > 0 2 k-1 +1 1 2 k-1 -2 01 2 k-1 -1 .

4. i = 2r + 1 or i = 2r + 2, 2 ≤ r ≤ k -2. A factor 0 2 k-1 -1+2 r , occurs in t w at position j only if either 1, 0 λ, 0 or 1, 0 10 r , 1 occurs at position ⌊ j/2 k-1 ⌋ of τ. If the factor 1, 0 λ, 0 occurs in τ, then it is a prefix of the factor 1, 0 λ, 0 1, 1 or 1, 0 λ, 0 1, 0 . We apply iii and iv and v of Lemma 5.4.9.

5. i = 2k -1. A factor 0 2 k occurs in t w at position j only if 1, 0 λ, 0 1, 1 occurs at position ⌊ j/2 k-1 ⌋ of τ. We apply iv of Lemma 5.4.9.

✷ Lemma 5.4.11 For i ≥ 2k -1, w 1 is a primitive word.

Proof. Analogous to the proof of Lemma 5.1.13. ✷ Lemma 5.4.12 For i ≥ 2k -1, w i is a Lyndon word.

Proof. We proceed by induction. The assertion for i = 2k -1 is implied by Lemma 5.4.10. Let the assertion be true for some i -1 ≥ 2k -1. Lemma 5.4.11 implies that w i is a primitive word. By Lemma 5.4.3, w i is a conjugate of Ψ(ϕ i ( 1, 0 )). Assume that w i is not minimal in its conjugacy class. Let w i = uv where vu < w i is the smallest conjugate of w i . According to Lemma 5.4.8, w i < w 2k-1 , hence w i , and vu have the same prefix 0 2 k 1 as w 2k-1 because no conjugate of Ψ(ϕ i ( 1, 0 )) may contain the factor 0 2 k +1 , as one easily observes using Property 5.4.1. The word vu is of the form ξ 0 x 1 x 2 xξ ′ 0 , ξ 0 = λ, where ξ ′ 0 ξ 0 = ψ(ϕ k-1 (c 0 )), x 1 = ψ(ϕ k-1 (c 1 )), x 2 = ψ(ϕ k-1 (c 2 )) for some c 0 , c 1 , c 2 ∈ Σ and ξ ′ 0 ξ 0 x 1 x 2 x = ψ(ϕ k-1 (c 1 c 2 x ′ c 0 ) for some conjugate c 1 c 2 x ′ c 0 of ϕ k-1+i ( 1, 0 ). Property 5.4.1 in combination with Property 5.4.2 implies that the only possibility is ξ 0 = 0 2 k-1 -1 , ξ ′ 0 = 1, x 1 = 0 2 k-1 , x 2 = 01 2 k-1 -1 , c 0 = 1, 0 , c 1 = λ, 0 and c 2 = 1, 1 .

A repeated application of Property 5.4.2 leads to the conclusion that c 1 c 2 x ′ c 0 is a conjugate of ϕ k-1+i ( 1, 0 ) of the form ϕ k-1 ( 1, 1 y α, 0 ), where 1, 1 y α, 0 is a conjugate of ϕ i ( 1, 0 ), since c 1 c 2 may occur only as a prefix of ϕ k-1 ( 1, 1 ). Hence ξ -1 0 vuξ 0 = x 1 x 2 zξ ′ 0 ξ 0 = Ψ( 1, 1 y α, 0 ) for a conjugate 1, 1 y α, 0 of ϕ i ( 1, 0 ). Property 5.4.2 now implies that α, 0 1, 1 y = ϕ(y ′ ) for some conjugate y ′ of ϕ i-1 ( 1, 0 ).

Again, the only possibility is that α = λ and λ, 0 1, 1 y = ϕ k-1 ( 1, 1 by ′′ ) for some conjugate 1, 1 by ′′ of ϕ i-(k-1) ( 1, 0 ) where b is some symbol from Σ occurring at an even position and therefore different from 1, 0 and 1, 1 . We will use the fact that, since b = 1, 0 and b = 1, 1 , ϕ k-2 (b) starts by c ∈ Σ where either c = λ, 0 or c = λ, 1 . Hence y ′ = ϕ k-2 ( 1, 1 )cz for some z ∈ Σ * .

We have λ, 0 1, 1 y = ϕ k-1 ( 1, 1 )ϕ(cz), where either c = λ, 0 or c = λ, 1 and ϕ k-2 ( 1, 1 )cz is a conjugate of ϕ i-1 ( 1, 0 ). factors are growing with µ 2 . This fact prevents us from trying to make any kind of conjecture on the general shape of the Lyndon factors for the whole class of generalized sequences of Thue. A study of the Lyndon factorization of further subclasses will be necessary to have a kind of general result. We hope that Definition 3.1.2 together with Lemma 3.2.4 may be equally useful as they proved to be in the investigation of the four subclasses in the present work.

Observation 2 . 3 . 6

 236 For each x ∈ Σ ∞ w let x denote the word obtained by replacing each symbol α, m by α, 1m . Similarly, for each word x ∈ [2] ∞ let x denote the word obtained by replacing each symbol m by 1m. Then 1. For each a ∈ Σ w and r ≥ 0, ϕ r w

Property 3 . 2 . 2 ϕLemma 3 . 2 . 3

 322323 is a one-to-one function. If a, b ∈ Σ, a = b, and r ≥ 0 is the first position where Ψ(a) and Ψ(b) contain a different symbol then r is a multiple of 2 s .

Proof.

  Let a < b (i.e., Ψ(a) < Ψ(b)) and let r be the first position in which Ψ(a) and Ψ(b) differ. Then Ψ(a)(r) = 0 and Ψ(b)(r) = 1. Assume by contrary that ϕ(a) ≥ ϕ(b), i.e., ϕ(a) > ϕ(b) as implied by Property 3.2.2. Then Ψ(ϕ(a)) > Ψ(ϕ(b)). Considering Proposition 3.2.1, this means µ(Ψ(a)) > µ(Ψ(b)). Theorem 2.3.2 implies that µ(Ψ(a)) and µ(Ψ(b)) have a common prefix of length 2r. Moreover, the "correction" caused by the function χ must take place at position 2r, since otherwise µ(Ψ(a))(2r) = Ψ(a)(r) < Ψ(b)(r) = µ(Ψ(b))(2r) and, consequently, µ(Ψ(a)) < µ(Ψ(b)). Therefore 2r = 2 k t + [w] 2 for some t ≥ 0 and Lemma 3.2.3 implies that [w] 2 is a multiple of 2 s+1 -a contradiction to the maximality of s. ✷ Corollary 3.2.5 ϕ is strictly growing on Σ ∞ .

Example 4 . 2 . 2 w

 422 = 1001 (k = 4) ‡ The case k = 2 yields a different Lyndon factorization-see Section 4.3.

Property 5 . 1 . 1

 511 Let a, b ∈ Σ, a = 0 p , m , b = 0 q , n . Then a < b iff one of the following is true: 1. m < n or 2. m = n = 0 and p < q or 3. m = n = 1 and p > q.

Property 5 . 1 . 4

 514 Let x ∈ Σ * . Then λ, 0 does not occur in any even position of ϕ(x) and 0 k-1 , 1 does not occur in any odd position of ϕ(x).Proof of Theorem 4.1.1 Part ALemma 5.1.5 w 0 w 1 is a prefix of t w .

Theorem 4 . 1 .

 41 1 now follows from Lemma 5.1.7, Lemma 5.1.8, Observation 5.1.9, Corollary 5.1.11 and Lemma 5.1.14. ✷ 5.2 Case w = 10 k-2 1

4 . 1 Lemma 5 . 4 . 9

 41549 implies that 1, 0 > ϕ( 1, 0 ) and v of Lemma 5.4.3 implies w i > w i+1 . ✷ Part C Let τ=lim n→∞ ϕ n ( λ, 0 ).

table ,

 ,

		e.g.,
	ϕ 010 ( 0, 1 ) = 0, 1 01, 1 ,
	and
	ψ w ( α, m ) = m for α ∈ {λ, 0, 01}, m ∈ {0, 1}.
	The sequence t 010 is a fixed point of the substitution
	0000 → 00100000	1111 → 11011111
	0010 → 00101100	1101 → 11010011
	1100 → 11010000	0011 → 00101111

  the word w i is a Lyndon word and w i > w i+1 .

	Example 4.1.2 w = 001 (k = 3)
	t 001
	0 ¯1111111 10 ¯111111 10 ¯001111 10111111 10 ¯000000 10111111 10001111 10111111 10 ¯000000 01000000 10001111 10111111 10000000 10111111 10001111 10111111 10 ¯000000 01000000 01110000 01000000 10000000 10111111 10001111 10111111 10000000 01000000 10001111 10111111 10000000 10111111 10001111 10111111
	10 ¯000000 01000000 01110000 01000000 01111111 01000000 01110000 01000000 10000000 01000000 10001111 10111111 10000000 10111111 10001111 10111111
	10000000 01000000 01110000 01000000 10000000 10111111 10001111 10111111
	10000000 01000000 10001111 10111111 10000000 10111111 10001111 10111111
	10 ¯000000 01000000 01110000 01000000 01111111 01000000 01110000 01000000 01111111 10111111 01110000 01000000 01111111 01000000 01110000 • • •
	µ 001
	0000 → 0100 0000 1111 → 1011 1111
	0100 → 0111 0000 1011 → 1000 1111
	0111 → 0111 1111 1000 → 1000 0000

  and w i is a Lyndon word.

	Example 4.4.2 w = 100 (k = 3)
	t 100
	0 ¯0001000 11001000 11111000 11001000 11110111 11001000 11111000 11001000 11110111 00110111 11111000 11001000 11110111 11001000 11111000 11001000
	11110111 00110111 0 ¯0000111 00110111 11110111 11001000 11111000 11001000 11110111 00110111 11111000 11001000 11110111 11001000 11111000 11001000
	11110111 00110111 0 ¯0000111 00110111 000010 ¯00 00110111 00000111 00110111 11110111 00110111 11111000 11001000 11110111 11001000 11111000 11001000
	11110111 00110111 00000111 00110111 11110111 11001000 11111000 11001000
	11110111 00110111 11111000 11001000 11110111 11001000 11111000 11001000
	11110111 00110111 00000111 00110111 000010 ¯00 00110111 00000111 00110111 00001000 110010 ¯00 00000111 00110111 00001000 00110111 00000111 • • • µ 100
	0000 → 0000 1000 1111 → 1111 0111
	1000 → 1100 1000 0111 → 0011 0111
	1100 → 1111 1000 0011 → 0000 0111

§ The case k = 1 corresponds to the sequence of Thue. Though the factorization in this case (see[START_REF] Ido | Lyndon factorization of the Thue-Morse word and its relatives[END_REF]) has the same shape as for k ≥ 2, the proof for k ≥ 2 will use the fact that w contains at least one symbol 0.

Acknowledgements

The author would like to thank the anonymous referees for multiple useful remarks and suggestions towards improving readability of the paper.

† This work was supported by the Kuwait University grant SM-178 1365-8050 c 2002 Maison de l'Informatique et des Mathématiques Discrètes (MIMD),

In both cases, w 0 =.Ψ(ϕ 2 ( λ, 0 ))0 -1 . The sequence t w has the prefix Ψ(ϕ 2 ( λ, 0 )) = w 0 0. Using Property 3.2.1 we obtain w 0 w 1 0 = w 0 [(w 0 ) -1 0 µ 2 (w 0 0)] = µ 2 (w 0 0) = Ψ(ϕ 4 ( λ, 0 ))) = Ψ(ϕ 2 ( λ, 0 1, 0 ))Ψ(ϕ 3 ( 1, 0 )) = w 0 0Ψ(ϕ 2 1, 0 ))Ψ(ϕ 3 ( 1, 0 )).

(25) Thus w 0 w 1 is a prefix of t w , w 1 = 0Ψ(ϕ 2 ( 1, 0 ϕ 3 ( 1, 0 )0 -1

and w 1 has the prefix 0Ψ( λ, 0 1, 0 ) = 00 2 k-1 0 2 k-1 -1 1 = 0 2 k 1, as implied by Property 5.3.1. ✷ Lemma 5.3.4 For i ≥ 1,

and the last symbol of the word µ 2 (0 -1 w i-1 0) is 0.

Proof. Theorem 2.3.2 implies, that the last symbol of µ(x) is complementary to the last symbol of x. Therefore µ 2 preserves the last symbol of its argument. The assertion of the lemma is true for i = 1 as follows from Lemma 5.3.3. Now let the assertion be true for some i -1 ≥ 1. Then

It is enough to prove that the sequence ∏ ∞ i=0 w i , having the same prefix w 0 0 of length 2 k+1 as t w , is a fixed point of µ 2 . Applying Lemma 5.3.3 we obtain

Proof. By Lemma 5.3.3, w 1 has the prefix 0 2 k 1, therefore w 0 > w 1 . Let i ≥ 1. Property 5.3.1 implies that

and

since the first symbol of ϕ 2 ( 1, 0 ) is λ, 0 . Corollary 3.2.5 and Lemma 5.3.3 imply

Proof. An easy application of Theorem 2.3.2. ✷ Lemma 5.3.8 For i ≥ 1, w i is a primitive word.

where

If w i is not primitive then neither is ω. The length of ω is 3 • 2 2i , therefore ω is a concatenation of either two or three identical factors. Since both Ψ and ϕ are strictly growing, this implies λ, 0 = 1, 0 in the former case and a = 1, 0 in the latter case. ✷ Lemma 5.3.9 For i ≥ 1, w i is a Lyndon word. w 0 is clearly a Lyndon word, since it is smaller than any of its non-empty proper suffixes. It is easy to check, that w 1 is of the form

(34)

Anton Černý

Property 5.4.1

(iv) w 2k-2 has the suffix ρ.

) has the prefix ρ.

Proof.

(i) Property 2.3.3 implies

Using Remark 2.1.2 it is easy to observe that the last symbol of

(ii) Again applying Property 2.3.3 we obtain µ 2k-2 (1

or i > 0 and ϕ i ( λ, 1 )has the prefix λ,

having the prefix (ρ0

Anton Černý

Part B Lemma 5.4.5 For 0 ≤ i ≤ 2k -1 the last symbol in w i is 1.

Proof. The last symbol of w i occurs at position j i+1 -1 in t w . The binary representation of each j i+1 -1 contains an odd number of occurrences of w. ✷ Lemma 5.4.6

w 0 has the prefix 0 2 k-1 1,

w 2r+1 and w 2r+2 have the prefix 0 2 k-1 -1+2 r 1 and w 2k-1 has the prefix 0 2 k 1.

Proof.

A simple observation of the shape of binary representation of the position numbers following

Proof. Lemma 5.4.6 implies that w 0 > w 1 and, for 2

The word w 2r+1 occurs as a factor of length 2 3k-2+r in t w at position

In a similar way, the suffix of

In any case, Ψ(b) starts by 1 and Ψ(c) starts by 0, hence w 2r+1 > w 2r+2 .

We still have to prove that w 2 > w 3 for k ≥ 3. Since ϕ k-1 ( 1, 1 ) has the prefix λ, 0 1, 1 10, 1 1, 1 , the suffix of Ψ( 1, 1 10, 1 ) at position 2 k-1+0 -2 k-1 + 0 = 0 has the prefix

Anton Černý

(iii) If the factor 1, 0 10 r , 1 occurs in τ then 10 r , 1 is the prefix of a factor ϕ r ( 1, 1 ). In that case 1, 0 is a suffix of some ϕ r (b), b ∈ Σ. Then b = α, 0 where α = 1, since b 1, 1 is a factor of τ and 1, 1 must be in an odd position. Then b 1, 1 = ϕ(c) for some c ∈ Σ. This is only possible if c = 10 k-2 , 1 and c is a prefix of a factor ϕ k-2 ( 1, 1 ). Since the first two occurrences of 1, 1 in τ are at positions (10 k-1 1) [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] = 2 k + 1 and (10 k 1) [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] = 2 k+1 + 1, the first two occurrences of the factor 1, 0 10 r , 1 in τ are at positions

and

(iv) Let the factor 1, 0 λ, 0 1, 1 occur in τ at (an odd) position j. Then the factor of length 2 at position ⌊ j/2⌋ is 1, 0 10 k-2 , 1 and in the same way (taking r = k -2) as in the proof of iii we deduce that ⌊ j/2⌋corresponds to the position 2(2 k-2 -1) + 1 of a factor ϕ 1+(k-2)+1+(k-2) ( 1, 1 ) , hence the first two occurrences of the factor 1, 0 λ, 0 1, 1 in τ are at positions

and

(v) Let the factor 1, 0 λ, 0 1, 0 occur in τ for the first time at (an odd) position j. Then the factor of length 3 at position ⌊ j/2⌋ is either 1, 0 λ, 0 1, 0 or 1, 0 λ, 0 1, 1 . The former case would mean an earlier occurrence of the factor, hence the latter case take place. The factor 1, 0 λ, 0 1, 0 hence occurs later than 1, 0 λ, 0 1, 1 .

✷

Lemma 5.4.10 For 0 ≤ i ≤ 2k -1, w i is a Lyndon word.

Proof. The binary representation of each j i+1 -1 contains an odd number of occurrences of 10 k-1 , and therefore the last symbol of each w i is 1. To prove that w i is a Lyndon word, we will show that w i besides in its prefix 0 p 1 (as described by Lemma 5.4.6), does not contain any occurrence of the factor 0 p . We will use Lemma 5.4.9, which will imply in each particular case that the next occurrence of 0 p in t, after the prefix of w i , is in some of the following factors w j .

1. i = 0. Property 5.4.1 implies that a factor 0 2 k-1 occurs in t w at some position j only if either λ, 0 or, for some r ≥ s ≥ 0, 10 s , 0 10 r , 1 occurs at position ⌊ j/2 k-1 ⌋ of τ=lim n→∞ ϕ n ( λ, 0 ). Property 5.4.2 implies that in the latter case exactly one of r, s must be equal to 0, hence r > s = 0 and the factor has the form 1, 0 10 r , 1 for some r ≥ 1. We apply i and iii of Lemma 5.4.9.

2. i = 1 or i = 2. A factor 0 2 k-1 +1 occurs in t w at position j only if either λ, 0 1, 1 or 1, 0 10 r , 1 , for some r ≥ 1, or 1, 0 λ, 0 occurs at position ⌊ j/2 k-1 ⌋ of τ. We apply ii and iii of Lemma 5.4.9.

Anton Černý

Furthermore, ξ -1 0 vuξ 0 = Ψ( 1, 1 y λ, 0 ) and, finally, ρ = Ψ(ϕ k-1 ( λ, 1 ) λ, 0 )ξ -1 0 as stated by ii of Lemma 5.4.3. We get

0 . The latter inequality therefore implies that the first symbol of Ψ(c) is not greater than 0 being the first symbol of Ψ( λ, 0 )ξ -1 0 . The word Ψ( λ, 0 ) starts by 0 and Ψ( λ, 1 ) starts by 1, hence c = λ, 0 . Then Ψ(ϕ k-1 ( λ, 1 ) λ, 0 z) < Ψ(ϕ i-1 ( 1, 0 )ϕ k-2 ( λ, 1 )) Ψ(ϕ k-1 ( λ, 1 ))Ψ( λ, 0 )Ψ(z) < Ψ(ϕ i-1 ( 1, 0 ))Ψ(ϕ k-2 ( λ, 1 )) ρξ 0 Ψ(z(ϕ k-2 ( 1, 1 ) λ, 0 )ξ -1 0 < Ψ(ϕ i-1 ( 1, 0 ))ν where ν = Ψ(ϕ k-2 ( λ, 1 ))Ψ(ϕ k-2 ( 1, 1 ) λ, 0 )ξ -1 0 = Ψ(ϕ k-1 ( λ, 1 ) λ, 0 )ξ -1

where the left-hand side is a conjugate of Ψ(ϕ i-1 ( 1, 0 )) and hence of w i-1 . This contradicts to the inductive hypothesis that w i-1 is a Lyndon word. ✷

Concluding remarks

Out of the four subclasses of the generalized Thue sequences, for three subclasses the canonical Lyndon factors grow proportionally with applications of the substitution µ. In the only case, when w = 1 k , the


Kenneth G Monks
email: monks@scranton.edu

3x + 1 Minus the +

Keywords: Collatz conjecture, 3x + 1 problem, Fractran, discrete dynamical systems

We use Conway's Fractran language to derive a function R : Z + → Z + of the form

where d is a positive integer, 0 ≤ i < d and r 0 , r 1 , . . . r d-1 are rational numbers, such that the famous 3x + 1 conjecture holds if and only if the R-orbit of 2 n contains 2 for all positive integers n. We then show that the R-orbit of an arbitrary positive integer is a constant multiple of an orbit that contains a power of 2. Finally we apply our main result to show that any cycle {x 0 , . . . , x m-1 } of positive integers for the 3x + 1 function must satisfy

where O = {i : x i is odd}, E = {i : x i is even}, and k = |O|. The method used illustrates a general mechanism for deriving mathematical results about the iterative dynamics of arbitrary integer functions from Fractran algorithms.

Introduction and Main Results

The famous 3x + 1 conjecture (cf. [START_REF] Lagarias | The 3x + 1 problem and its generalizations[END_REF], [START_REF] Wirsching | The Dynamical System Generated by the 3n + 1 Function[END_REF]) states that for every n ∈ Z + there exists k ∈ Z + such that T k (n) = 1 where

T (n) = 1 2 n if n is even 3 2 n + 1 2
if n is odd.

and

T k = T • T • • • • • T k
denotes the k-fold composition of T with itself. If we let T 0 (x) = x 2 and T 1 (x) =

(n) = T v k-1 • T v k-2 • • • • • T v 0 (n)
for some v 0 , . . . v k-1 ∈ {0, 1} and v i ≡ T i (n) mod 2. Several authors (cf. [START_REF] Lagarias | The 3x + 1 problem and its generalizations[END_REF]) have given explicit formulas for this composition, e.g. Compare this somewhat unwieldy expression with the much simpler one

T v k-1 • T v k-2 • • • • • T v 0 (n) = 3 m 2 k n + k-1 ∑ i=0 v i 3 v i+1 +•••+v k-1 2 k-i where m = k-1 ∑ i=0 v i .
R v k-1 • R v k-2 • • • • • R v 0 (n) = 3 m 2 k n
when R 0 (n) = 1 2 n and R 1 (n) = 3 2 n. With this example in mind, it is natural to ask if there is some function of the form

R(n) =            r 0 n if n ≡ 0 mod d r 1 n if n ≡ 1 mod d . . . . . . r d-1 n if n ≡ d -1 mod d (1.1)
where r 1 , . . . , r d-1 are rational numbers and d ≥ 2 such that knowledge of certain R-orbits would settle the 3x + 1 problem, i.e. is there an addition-free variant of the 3x + 1 function whose dynamics encode the conjecture? We answer this question in the affirmative with the following result Theorem 1 There are infinitely many functions R of the form (1.1) having the property that the 3x + 1 conjecture is true if and only if for all positive integers n the R-orbit of 2 n contains 2. In particular,

R (n) =                                     
2 n , 2 T (n) , 2 T 2 (n) , 2 T 3 (n) . . .
and these are the only powers of two that occur.

Note that the function R given in the theorem is of the form (1.1) if we take d = lcm (11, 15, 17, 5, 21, 13, 7, 4, 2) = 1021020 since the first condition satisfied by n will also be the first condition satisfied by n + d j for any j. Proof : The proof is a straightforward application of Conway's Fractran language and its mathematical consequences. We refer the reader to [START_REF] Conway | FRACTRAN: A Simple Universal Programming Language for Arithmetic[END_REF] for details. A Fractran program consists of a finite list of positive rational numbers, [r 1 , . . . r t ] . The state of a Fractran machine consists of a single positive integer S. The exponents of the primes in the prime factorization of S are used as registers for storing nonnegative integers. The program is executed by multiplying S by the first rational number in the list for which the product is a nonnegative integer (and halts if no such integer exists). Thus, each Fractran program corresponds to a function of the form (1.1) where execution of the program corresponds to iteration of the function.

The

when started with S = 2 n , will produce S = 2 T (n) as the next S power of 2 in the orbit. To see this, consider the flowchart for this program indicated in Figure 1. (In what follows we will only be concerned with an initial state that is a power of 2, as required.) The edges of the flowchart are labeled in order of decreasing priority using a single arrow, double arrow, and triangle respectively. At a given node, the current state S is multiplied by the fraction labeling the edge of highest priority for which the product is a positive integer. The powers of the primes 5, 7, 11, 13, 17 in S correspond to the nodes o, q, n, r, p respectively, a positive exponent of one of the primes indicating the program is at that node (and it is at node m if it is at no other node). The exponents of 2 and 3 in S are used as registers to compute T. We will refer to these exponents as α and β respectively.

When the program is started with S = 2 n at node m, it will execute the loop between nodes m and n exactly q = n 2 times, each time decreasing α by 2 and incrementing β. This results in S = 2 n mod 2 3 q . If n is odd then n = 2q + 1 for some positive integer q and execution proceeds to node o where the state becomes S = 3 q 5. The loop between nodes o and p then produces S = 2 3q 5 which is then multiplied by 2 2 5 to produce

S = 2 3q+2 = 2 (6q+4)/2 = 2 (6q+3+1)/2 = 2 (3(2q+1)+1)/2 = 2 (3n+1)/2 = 2 T (n) as required.
If n is even, then upon completion of the mn loop S is multiplied by 7 moving execution to node q. The loop between nodes q and r produces S = 2 q 7 which is then multiplied by 1/7 to produce

S = 2 q = 2 n/2 = 2 T (n)
as required.

Iteration of the function R given in the theorem starting with seed 2 n corresponds exactly to execution of this Fractran program (the sequence of states being the R-orbit of 2 n ). Since the choice of primes and algorithm used in this program was arbitrary, there are infinitely many such programs, and thus infinitely many such functions. This completes the proof.

✷ Theorem 1 shows the relationship between the R-orbits of two powers and the 3x + 1 problem. One might ask for its own sake † how the iterates of R behave for arbitrary positive integer inputs. We answer this question with the following result.

Theorem 2 Let R be defined as in (1.2). Then for all a, b, c, d, e, f , g, h ∈ N 1. for all m ∈ Z + with gcd (m, 2

• 3 • 5 • 7 • 11 • 13 • 17) = 1, R 2 a 3 b 5 c 7 d 11 e 13 f 17 g m = m • R 2 a 3 b 5 c 7 d 11 e 13 f 17 g and 2.
there exists k ∈ N such that R k 2 a 3 b 5 c 7 d 11 e 13 f 17 g = 2 j for some j.

Thus if we iterate R starting with an arbitrary positive integer n, the prime factors of n that are greater than 17 are left unchanged, and the iterates of the remaining factor eventually reach a two power (after which the behavior proceeds as indicated in Theorem 1).

Proof : The proof of part (1) follows immediately from the definition of R, since prime factors greater than 17 are not affected when a positive integer is multiplied by any of the rational numbers listed in (1.3).

To prove part (2), let S be the set of positive integers that are not divisible by a prime greater than 17. Since no prime greater than 17 is a factor of the numerator of any fraction in (1.3), R maps elements of S to elements of S.

Let S ′ be the subset of S consisting of integers of the form 2 a 3 b for some a, b ∈ N. Let a, b ∈ N. By the definition of R, R 2 2 a+2 3 b = 2 a 3 b+1 so that R 2b 2 a+2b = 2 a 3 b . Thus any element of S ′ is in the R-orbit of a power of two. Since the R-orbit of 2 a+2b contains infinitely many terms that are powers of two by Theorem 1, so does the R-orbit of 2 a 3 b for any a, b ∈ N. Thus it suffices to show that the R-orbit of any element of S contains an element of S ′ .

Define α : S → N by α (2 e 1 3 e 2 5 e 3 7 e 4 11 e 5 13 e 6 17 e 7 ) = ∑ 7 i=2 e i . We argue by contradiction, and suppose that we have an element n of S so that all iterates R k (n) / ∈ S ′ . Then all terms in the R-orbit of n are divisible † Thanks to the anonymous referee of an earlier draft of this paper for suggesting this line of inquiry.

by some prime in {5, 7, 11, 13, 17}. Thus by the definition of R,

for all k ≥ 1, R k (n) = r k R k-1 (n) for some r k ∈
α R k+1 (n) = α r k+1 R k (n) < α R k (n) and if r k+1 ∈ 5 17 , 7 13 then α R k+1 (n) = α r k+1 R k (n) = α R k (n) .
So the R-orbit of n has nonincreasing values of α, i.e. the sequence

α (n) , α (R (n)) , α R 2 (n) , . . . (1.4)
is a nonincreasing. Since none of the terms are a two power (by our assumption), (1.4) is a nonincreasing sequence of positive integers whose terms are all less than or equal to α (n). Thus there must be some

h ≥ 0 such that α R k (n) = α R h (n) for all k ≥ h. So r k ∈ 5 17 , 7
13 for all k ≥ h. But multiplication by these values of r k decreases the exponent of either 13 or 17 in the prime factorization of an integer, so that repeated multiplication by these fractions eventually produces a non-integer value. This contradicts our assumption and completes the proof.

✷ Conway [START_REF] Conway | Unpredictable Iterations[END_REF] used an argument similar to the proof of Theorem 1 to show that there exist functions of the form (1.1) for which the fate of the orbit of an arbitrary positive integer is algorithmically undecidable. In Theorem 1 we turn this method around to obtain a positive result, and now illustrate how this result can be used to obtain mathematical results about the conjecture itself.

An Application

Let x 0 , . . . , x n-1 be positive integers such that x i = T (x i-1 ) for 0 < i < n and x 0 = T (x n-1 ) . In this situation we say {x 0 , . . . , x n-1 } is a T -cycle. If the 3x+1 conjecture is true, then the only T -cycle of positive integers is {1, 2} (the existence of any other positive integer in a T -cycle being a counterexample). Thus it is of interest to study the properties of positive integer T -cyles.

Suppose {x 0 , . . . , x n-1 } is a T -cycle of positive integers with x i = T (x i-1 ) for 0 < i < n and x 0 = T (x n-1 ) . Then by Theorem 1 the R-orbit of 2 x 0 is also cyclic and contains {2 x 0 , . . . , 2 x n-1 } as a subset. Thus there exists some positive integer t such that R t (x 0 ) = x 0 . But each application of R is simply multiplication by one of the rational numbers in 1 11 , 136 15 , 5 17 , 4 5 , 26 21 , 7 13 , 1 7 , 33 4 , 5 2 , 7 so that we must have for some nonnegative integers a, b, c, d, e, f , g, h, i, j with a+b+c+d +e+ f +g+h+i+ j = t. Collecting prime factors on the right hand side and dividing by x 0 gives us 2 3b+2d+e-2h-i 3 -b-e+h 5 -b+c-d+i 7 -e+ f -g+ j 11 -a+h 13 e-f 17 b-c = 1. This yields the system of linear equations

x 0 = R t (x 0 ) = 1
3b + 2d + e -2h -i = 0 -b -e + h = 0 -b + c -d + i = 0 -e + f -g + j = 0 -a + h = 0 e -f = 0 b -c = 0
which is equivalent to the system It should be noted that this formula can be proven directly from the known relationship

a = 2c + i (2.1) b = c d = i e = c + i f = c + i g = j h = 2c + i. Now define O = {i : x i is odd} and E = {i : x i is even} and let k = |O| so that |E| = n -k. Then as explained in the proof of Theorem 1 we see that i = k (2.2) j = n -k c = ∑ i∈O x i 2 a = n-1 ∑ i=0 x i 2 Substituting (2.2) into a = 2c + i from (2.1) we obtain n-1 ∑ i=0 x i 2 = 2 ∑ i∈O x i 2 + k. (2.3) But ∑ n-1 i=0 x i 2 = ∑ i∈E x i 2 + ∑ i∈O
∑ i∈E x i = ∑ i∈O x i + k (2.4)
(obtained by noticing that {x 0 , . . . , x n-1 } = {T (x 0 ) , . . . , T (x n-1 )} so that ∑ x i = ∑ T (x i ) and thus ∑ i∈E x i + ∑ i∈O x i = ∑ i∈O

3x i +1 2 + ∑ i∈E x i
2 which can be solved to obtain (2.4)). However, the method used here reveals the results of the Corollary without specifically searching for those results. Thus this method provides a general approach for discovering new mathematical results by simply coding different algorithms for computing T (or any other computable integer function) and solving a simple linear system.

3 2 x + 1 2 ,

 32 then for any n and k, T k

1365-8050 c 2002

 2002 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Fig. 1 :

 1 Fig. 1: A Fractran program for T

x i 2 .

 2 Substituting this into (2.3) and simplifying proves Corollary 1 If {x 0 , . . . , x n-1 } is a T -cycle of positive integers and O = {i : x i is odd} andE = {i : x i is even} then