Csaba Schneider
email: c.schneider@maths.anu.edu.au

Computing nilpotent quotients in finitely presented Lie rings †

Keywords: Lie rings, nilpotent Lie rings, finitely presented Lie rings, nilpotent presentation

A nilpotent quotient algorithm for finitely presented Lie rings over Z (LIENQ) is described. The paper studies the graded and non-graded cases separately. The algorithm computes the so-called nilpotent presentation for a finitely presented, nilpotent Lie ring. A nilpotent presentation consists of generators for the abelian group and the products expressed as linear combinations for pairs formed by generators. Using that presentation the word problem is decidable in L. Provided that the Lie ring L is graded, it is possible to determine the canonical presentation for a lower central factor of L.L IENQ's Complexity is studied and it is shown that optimising the presentation is NP-hard. Computational details are provided with examples, timing and some structure theorems obtained from computations. Implementation in C and GAP interface are available

Introduction

The nilpotent quotient algorithm for finitely presented Lie rings -LIENQ as we shall refer to it in the sequel -operates with Lie rings over Z. Its essential goal is to compute an efficient and useful presentation for the nilpotent factors of a given Lie ring. It actually means to compute a presentation for its additive group and to compute the structure constants in order to determine the Lie ring structure. By efficient and useful we mean that several important pieces of information can be read off immediately (e.g.: nilpotency, nilpotency class etc). Furthermore, by this presentation the so-called word problem is decidable, although it is known to be undecidable in the general case. On word problem in groups and Lie algebras see [START_REF] Hall | Some word problems[END_REF].

Such algorithms have existed for several decades for groups and Lie rings as well. Recall, the most important commutator identities, such as

[x, y] = [y, x] -1 (1) [[x, y -1 ], z] y [[y, z -1 ], x] z [[z, x -1 ], y] x = 1 (2) [xy,z] = [x,z] y [y,z] (3) [x, yz] = [x, z][x, y] z (4)
reminds us of the defining axioms of Lie rings. In details, (2) is \similar" to the Jacobi identity while (3) and ( 4) can be interpreted as some \distributive" property of the group commutator. This analogy allows us to alter the known group algorithms for Lie rings.

The algorithm described here is a variation of those presented in [START_REF] Havas | A nilpotent quotient algorithm for graded lie rings[END_REF] and [START_REF] Nickel | Computing nilpotent quotients in finitely presented groups[END_REF], however it differs at several points from them.

There are three main sections in this paper. The first part contains the basic properties of the nilpotent presentation and describes an algorithm to compute it in the general case. The next part is devoted to graded Lie rings. We shall see that in the graded case we can simplify LIENQ and, using other techniques, it is possible to determine the isomorphism type of the underlying abelian group of such a Lie ring. The last part contains computational issues. We shall see how the implementation works and some examples with timing will display the scope of LIENQ in both graded and non-graded cases.

The basic properties of Lie rings can be found in any textbook on that topic. We refer to [START_REF] Humphreys | Introduction to Lie Algebras and Representation Theory[END_REF] for details. The first lemma is of fundamental importance to our goal, since it essentially shows that it is realistic to build a nilpotent quotient algorithm for finitely presented Lie rings.

Lemma 1.1 In a finitely presented Lie ring each lower central factor is finitely presented.

The lemma is a consequence of the argument presented in [START_REF] Hall | The Theory of Groups[END_REF] on basic commutators.

The Nilpotent Presentation of a Lie Ring

Let L denote a Lie ring and L i the ith term of its lower central series. Product in L is denoted by brackets -as it is usual -and we use the left-normed convention that is, [a, b, c] = [[a, b], c]. If L is finitely presented Lemma 1.1 implies that L i /L i+1 is finitely presented for each i. Since at the present stage we are only interested in the nilpotent factor L/L k , we think L is nilpotent of class k -1. In other words we think L/L k is equal to L. In this case L has a so-called nilpotent presentation in accordance with the following definition.

Definition 2.1 A nilpotent presentation is a tuple (G, S)

, where G is a finite set of generators, {a 1 ,... ,a r } say, and S is a finite set of relations of the form

γ i • a i = α i,i+1 • a i+1 +•••+α i,r •a r for some i, TR [a j , a i ] = β j,i, j+1 • a j+1 +•••+β j,i,r •a r for each j > i, PR
where the α, β, γ are integer coefficients, furthermore, γ i > 1 where applicable.

Note that the relations of type TR are sometimes referred to as torsion relations, while those of PR are called product relations. A more detailed description and the proof for existence of such presentation can be found in [START_REF] Schneider | Computations in finitely presented lie rings[END_REF], while it is easy to see that a nilpotent presentation always defines a nilpotent Lie ring. Observe that we demand the existence of PR relations for each pair ( j, i), where j > i, but only some of those of type TR (even possibly none). Throughout this paper I denotes the set of indices, so that i ∈ I if and only if a i has TR relation. One easily sees that the relations of type TR determine the underlying abelian group structure for L, while the relations of type PR define its ring structure. The β can be viewed as structure constants for the Z-module defined by G and the TR relations.

For our purpose this concept will be too general, so we shall keep some restrictions. Define a weight function ω : G → N as follows. Let ω be an increasing function in i, such that the following holds.

1. ω(a 1 ) = 1, 2. if the nilpotent presentation contains a relation of the form [a j , a i ] = w ji , where w ji is a sum of integer multiples of generators from G, then all generators a k ∈ G such that ω(a k )<ω(a j )+ω(a i ) have coefficients zero in w ji .

Another restriction, if a k ∈ G and ω(a k )>1, we require a k to have a definition, i.e. a relation of the form [a j , a i ] = a k [START_REF] Hall | The Theory of Groups[END_REF] where ω(a k ) = ω(a j ) + ω(a i ) and ω(a i ) = 1. It might easily happen that a nilpotent presentation contains more then one relation of the form (5) for some k, in this case we arbitrarily choose one for the definition of a k . If for a nilpotent presentation there exists a function ω which satisfies the conditions 1. and 2. then it is called a weighted nilpotent presentation with weight function ω.

Suppose that we are given a nilpotent presentation

G | γ i • a i = w i , i ∈ I, [a j , a i ] = w ji , 1 ≤ i < j ≤ r . (6)
Let L denote the Lie ring presented by [START_REF] Hartley | Rings, Modules and Linear Algebra[END_REF] and A the anti-commutative, non-associative ring defined by [START_REF] Hartley | Rings, Modules and Linear Algebra[END_REF]. Clearly [START_REF] Hartley | Rings, Modules and Linear Algebra[END_REF] does not care about Jacobi identities, so L does not automatically coincide with A.

It is important in the sequel to decide if L ∼ = A, in other words if A is a Lie ring. To do that, we arrange a collection process in A. Suppose that we are given a sum of products ℓ ∈ A expressed in terms of the elements from G. The collection process consists of two main steps. In the first step we substitute the products by the right-hand side of the appropriate PR relations. In the second step we reduce those coefficients that are not less than the corresponding γ i in [START_REF] Hartley | Rings, Modules and Linear Algebra[END_REF].

After proceeding so, we get a reduced form for ℓ ∈ A subject to [START_REF] Hartley | Rings, Modules and Linear Algebra[END_REF]. That is,

ℓ = α 1 • a 1 +•••+α r •a r ( 7
)
where 0 ≤ α i <γ i whenever i ∈ I . This reduced form is unique in A, but the same element in L can be represented by a more reduced form subject to the nilpotent presentation. We do not want this phenomenon to happen at all, thus we define consistency of the nilpotent presentation.

Definition 2.2 A weighted nilpotent presentation for a Lie ring L is said to be consistent if every element of L has a unique normal form.

In Section 3.3 we shall see how to check if an arbitrary nilpotent presentation is consistent and develop a method to make it consistent if it is not. In general, it is an equivalent condition to that of Definition 2.2 that the element 0 uniquely has a normal form.

From the computational point of view it is important to see that not all the relations of type PR are necessary to determine the structure of L. Our first result is devoted to this observation.

Lemma 2.1 Let L be a Lie ring given by the consistent weighted nilpotent presentation

G | γ i • a i = w i , i ∈ I, [a j , a i ] = w ji , 1 ≤ i < j ≤ r .
Then L is already determined by the presentation

G | γ i • a i = w i , i ∈ I, [a j , a i ] = w ji , 1 ≤ i < j ≤ r,ω ( a i )=1 . ( 8
)
Proof. Essentially we want to prove that all PR relations can be expressed by those listed in [START_REF] Havas | Hermite normal form computation for integer matrices[END_REF]. We proceed by an induction argument on ω(a i ).I f ω(a i ) = 1 then we are done. Suppose now, that ω(a i ) = k > 1 and we have already expressed all relations of the form [a m , a n ] = w ji where ω(a n )<k.

Using the definition for a i and the identities of a Lie ring one has: [a j ,

a i ] = [a j , [a k , a l ]] = -[a k , a l , a j ] = [a l , a j , a k ] + [a j , a k , a l ] = [a j , a k , a l ] -[a j , a l , a k ].
And the latter ones are known since both a k and a l have weight smaller than k, hence by the induction hypothesis and linearity result we obtain an expression for [a j , a i ]. Note that in the first equality we substituted a i by its definition. ✷

Computing a Weighted Nilpotent Presentation

The aim of this section is to show how it is possible to compute a consistent weighted nilpotent presentation for a nilpotent factor of a a given finitely presented Lie ring L and determine an epimorphism from L onto that nilpotent factor. The basic ideas -besides being simple -are similar to those used in [START_REF] Havas | A nilpotent quotient algorithm for graded lie rings[END_REF] and [START_REF] Nickel | Computing nilpotent quotients in finitely presented groups[END_REF]. Our algorithm is based on an induction argument. Suppose that we are given a consistent weighted nilpotent presentation for L/L l and an epimorphism from L onto L/L l , we shall show how to extend them to a consistent weighted nilpotent presentation and an epimorphism for L/L l+1 .

As computational tools, matrices over Z play an important rôle. Computing the row Hermite normal form is a crucial point of the algorithm. Since its details can be found in [START_REF] Nickel | Computing nilpotent quotients in finitely presented groups[END_REF] and [START_REF] Charles | Computation with finitely presented groups[END_REF], we do not emphasise them further in this paper.

Computing the Abelian Factor

Suppose that we are given a Lie ring L with finite presentation X | R , where X is a finite set of generators, while R is a finite set of relators. For simplicity, suppose X ={ x 1 ,... ,x n }. Set G ={a 1 ,... ,a n }. Construct a map φ : X → G, by simply saying

x i φ = g i .
Furthermore, we set all PR relations to be trivial and I =∅. We call the presentation constructed above a trivial weighted nilpotent presentation and it is clear that it represents the free abelian Lie ring F ab n on n generators. It is straightforward to see that it contains L/L 2 as a factor ring. Indeed, let I be the ideal generated by the set Rφ, where we evaluate φ as if it was a homomorphism elementwise on R. Then we have Lemma 3.1 L/L 2 is isomorphic to F ab n /I. Proof. Both Lie rings are generated by n elements and satisfy exactly the same relations. It justifies the isomorphic property. ✷ What we do in practice is the following. Evaluate the relations in F ab n as described above and put the images in a matrix M. Then compute the row Hermite normal form M H for M. It is well known that the rows of M generate the same subgroup, in the free abelian group, as those of M H . If the first non-zero element, the ith say, of a row of M H is 1, i.e. we have a row of the form 0,... ,0,1,m i+1 ,... ,m n we simply throw a i out of G and modify the map φ

x i φ =-m i+1 •a i+1 -•••-m n •a n .
Otherwise, if the leading element is greater then one, i.e. we have a row of the form 0,... ,0,m i > 1,m i+1 ,... ,m n , we introduce a TR relation

m i • a i =-m i+1 •a i+1 -•••-m n •a n .
and put i into I .

Proceeding through each row as described above, we obtain a presentation for L/L 2 . We set the surviving generators of weight one and it is straightforward to see that the presentation obtained so far is indeed a presentation for the abelian factor and φ extends to an epimorphism. We summarise this result in Proposition 3. [START_REF] Caranti | Thin groups of prime-power order and thin Lie algebras[END_REF] The so obtained presentation is a consistent nilpotent presentation for L/L 2 and φ extends to a epimorphism from L onto L/L 2 .

Remark 3.1

The untouched images under epimorphism will be referred to as definitions of generators of weight one. This terminology will be important later on.

Extending the Presentation

In this section we shall describe how to extend the weighted consistent nilpotent presentation of L/L l to a weighted consistent nilpotent presentation of L/L l+1 and how to lift the epimorphism from L onto L/L l to an epimorphism from L onto L/L l+1 . Then the weighted nilpotent presentation can be built for an arbitrary nilpotent factor of L by building it for the abelian factor and iterating the extension finitely many times. Suppose that we have a weighted nilpotent presentation for the factor ring L/L l , an epimorphism from L onto L/L l . Extending the presentation will consist of three steps, i.e.

1. extending the epimorphism φ, 2. modifying the TR relations, 3. modifying the PR relations.

Extending the epimorphism means introducing a new generator for all x i ∈ X , where x i φ is not a definition (see Remark 3.1). In other words, if x i φ = w i , we modify x i φ so that x i φ = w i + t i . The torsion relations will change so that if i ∈ I , γ i • a i = w ii , then we alter γ i • a i = w ii +t ii . Those of the PR relations that are not definitions are modified in a similar way. If [a j , a i ] = w ji j > i and [a j , a i ] is not a definition then let the new relation be [a j , a i ] = w ji + t ji .

Note, that all newly introduced generators t i , t ii ,t ji are different from one another. We introduce PR relations so that all of them are central. At this stage we do not alter I . We prove the following.

Theorem 3.1

The Lie ring defined by the extended presentation contains L/L l+1 as a factor ring.

Proof. Let L/L l be generated by d generators. Write down the nilpotent presentation for L/L l and using the definitions of the generators we can write down a presentation for L/L l consisting only of generators of weight one. Thus we obtained a presentation of the form F/R where F is the free Lie ring on d generators and R is a suitable ideal. Doing the same we get the presentation for L * as F/R * . One easily checks that

R * = [R, F].
Let us prove that F/[R, F] contains L/L l+1 as a factor ring. Note that L/L l , L/L l+1 and L * can be generated by d generators. Fix a generating set f 1 ,... , f d for F. Let θ and φ denote the homomorphisms from F onto F/R and form L/L l+1 onto L/L l , respectively. Note that φ has kernel

L l /L l+1 . Let h 1 ,... ,h d be elements of L/L l such that h i φ = f i θ . L/L l+1 is generated by {h 1 ,... ,h d } therefore the map ψ : f i → h i extends to a homomorphism from F onto L/L l+1 . Let M be the kernel of ψ. Then it is enough to show that R * is contained in M. But this is true since, ψφ = θ and r ∈ R is mapped to the kernel of φ by ψ. But the kernel of φ is central, hence an element from [R, F]i s mapped to zero by ψ. Thus R * = [R, F] ≤ ker ψ = M. ✷
In practice we use Lemma 2.1. This lemma essentially says, that we do not need to introduce new generators for all PR relations, but only for those of the form [a j , a i ] = w ji for j > i and a i is of weight one. The remaining ones can be computed as we have seen in the proof of this lemma. This computation is usually referred to as computing the tails.

Enforcing Consistency

Recall that we called a weighted nilpotent presentation consistent if each element in L uniquely had a normal form. The extended presentation investigated in the previous subsection might not happen to be consistent, as is the case in general.

In order to investigate the uniqueness property we introduce an operation on the nilpotent quotient. First of all let A be an abelian group generated by G and the TR relations of the extended presentation. Introduce a map ψ such that,

ψ : G × G → A ψ(a j ,a i ) =    w ji if j > i, -w ji if j < i, 0i f j = i ,
provided that the weighted nilpotent presentation possesses a PR relation of the form [a j , a i ] = w ji for j > i. Then the following is true.

Proposition 3.2 ψ can be extended to a bilinear operation on A if and only if

γ j • [a j , a i ] = n k= j+1 α jk [a k ,a i ], C1
where j ∈ I and the relation corresponding to a j is of the form

γ j • a j = α j, j+1 a j+1 +•••+α in • a n .
Proof. It is immediate that the condition is necessary. To see that it is sufficient as well, observe that the two expressions, w and w ′ say, are equal, it means that they can be transformed to each other by using TR relations. The condition of the proposition claims that such a transition respects the equality ψ(w, v) = ψ(w ′ ,v) for any v. Similar result is obtained in the second variable of ψ by swapping the two variables. ✷

If A is equipped by that operation then it happens to be a non-associative ring. We prove the following.

Lemma 3.2 The weighted nilpotent presentation of L is consistent if and only if A is a Lie ring.

Proof. Observe that L = A/J where J is the ideal generated by all instances of the Jacobi identity. A normal word ℓ represents the zero element in L if and only if ℓ ∈ J .I fAis a Lie ring then J = 0, so ℓ must be the trivial word. On the other hand, if the nilpotent presentation is consistent, then all instances of the Jacobi identity collect to the trivial word, so J = 0 and A = L holds. ✷

One can easily check the Jacobi identity, since it is a multi-linear identity, thus it is enough to check it on the triples formed by the abelian group generators. However, we can restrict ourselves even more by the following.

Lemma 3.3 A weighted nilpotent presentation (G, S) of a Lie ring L is consistent if and only if the relations (C1) and the Jacobi identity holds for each triple

(a i , a j , a k ) ∈ G × G × G where 1 ≤ i < j < k ≤ n
and a i is of weight one. In other words

[a i , a j , a k ] + [a j , a k , a i ] + [a k , a i , a j ] = 0 C2 for 1 ≤ i < j < k ≤ n and a i is of weight one.
The above lemma first appeared in [START_REF] Vaughan-Lee | An aspect of the nilpotent quotient algorithm[END_REF] for pc-presentation of p-groups. It was modified for Lie algebras in [START_REF] Havas | A nilpotent quotient algorithm for graded lie rings[END_REF], where one finds its proof. The Lie ring case can be handled in the same way as Lie algebras.

Enforcing the Defining Relations

One can easily observe that the presentation obtained so far is a presentation of the freest Lie ring of class l on the same number of generators as L/L l that happens to contain L/L l+1 as a factor ring in it.

What is still needed is to assure that the images of the elements of R, under the epimorphism, are 0. It simply means taking the factor ring over the ideal generated by the epimorphic images.

Let L be freely presented as F/R then one sees that L/L l = F/(R + F l ) = F/S. Then the extended Lie ring L * was obtained as L * = F/S * where

S * = [S, F] = [R + F l , F] = [R, F] + F l+1 .
But F/S * is not necessarily a factor of L. Hence we have to pass to the largest factor of F/S * which is a factor of F/R too. Obviously it is F/(R + S * ).

R + S * = R + [R, F] + F l+1 = R + F l+1 . Therefore L/L l+1 = F/(R + S * ) = F/(R + F l+1 ).
By the induction hypothesis images of R vanish in L/L l , so they must lie in L l /L l+1 and we are allowed to use abelian group methods again, such as Hermite normal form and other integer based strategies.

In practice we proceed as follows. Put all elements obtained from the consistency relations (C1), (C2) and the defining relations together in a matrix M. Compute the row Hermite normal form M H for M. Using those rows of M H whose leading element is equal to 1, we can eliminate some of the generators from the weighted nilpotent presentation. The other rows express linear dependence among the generators over Z. They can be viewed as TR relations and are added to the presentation. Extend the weight function to the newly introduced generators, by saying that they are of weight i and add the indices of generators that were provided with TR relations to I . The following lemma makes sure that generators of weight i have definitions.

Lemma 3.4 If L is a Lie ring and suppose that L/L 2 is additively generated as

L/L 2 = ℓ 1 +L 2 ,... ,ℓ k + L 2 and L i-1 /L i is additively generated as L i-1 /L i = ℓ 1 ′ +L i ,... ,ℓ l ′ + L i then L i /L i+1 is additively generated as L i /L i+1 = [ℓ ′ m ,ℓ n ]+ L i+1 | 1 ≤ m ≤l, 1 ≤ n ≤ k .
The proof of the above lemma can be done essentially in the same way as in the group case. That proof can be found in [START_REF] Charles | Computation with finitely presented groups[END_REF] Proposition 2.6. But see also [START_REF] Schneider | Computations in finitely presented lie rings[END_REF] for a detailed study of the Lie ring case.

4 The Graded Case

Simplifying LieNQ in Graded Lie Rings

The following section is devoted to graded Lie rings. Gradedness of a Lie ring is defined in accordance with the following definition.

Definition 4.1 Let L be a Lie ring, L is said to be graded if L, as an abelian group, splits into a direct sum of its lower central factors.

Since a Lie ring of that kind possesses a relatively easy structure, we are allowed to simplify our algorithm in this case.

First of all, we need not extend the TR relations any more since if a i ∈ L l /L l+1 for some i ∈ I implies γ i • a i ∈ L l /L l+1 , so the right-hand side of the relation corresponding to a i cannot contain generators of weight greater than l.

Similar thing happens when we extend the PR relations. At the lth step we only alter the relations of the form [a j , a i ] = w ji for i > ji + j = l .

We regard these facts when we introduce new generators and compute the tails. Now it should be clear that enforcing the consistency simply means enforcing the consistency relations (C2) for the triples

(a i , a j , a k ) ∈ G × G × G, where 1 ≤ i < j < k ≤ n ω(a i )+ω(a j )+ω(a k ) = l
and ω(a i ) = 1. And the relations of type (C1) are checked for only pairs (a i , a j ) ∈ G × G, where ω(a i ) + ω(a j ) = l. Note that l still denotes the nilpotency class of the current factor.

We are allowed to simplify it further, namely we need to enforce only those relations of R that have weight l.

The natural question arises. How can one recognise a graded Lie ring by looking at its finite presentation? We only mention here the well known fact that a Lie ring defined by homogeneous relations is always graded.

Another approach -Canonical Weighted Nilpotent Presentation

In a graded Lie ring we shall construct the so-called canonical nilpotent presentation instead of the weighted nilpotent presentation defined in Section 2. The concept of the canonical weighted nilpotent presentation fits the concept of canonical presentation for finitely generated abelian groups. In the sequel we shall use additive notation for abelian groups and + to denote the binary operation in such structures. Recall that C n denotes the cyclic group of order n. Theorem 4.1 Let (A, +) be a finitely generated abelian group. Then A can be written as a direct sum of cyclic groups, i.e.

A ∼ = C k 1 ⊕•••⊕C k r ⊕C ∞ ⊕•••⊕C ∞ , ( 9
)
where k 1 |k 2 ,... ,k r-1 |k r . The [START_REF] Havas | Integer matrix diagonalization[END_REF] form is called the canonical decomposition for A. The canonical decomposition is unique for an arbitrary such A.

The proof of the theorem can be found in [START_REF] Suzuki | Group Theory I[END_REF] Theorem 5.2.

In the following we define the canonical weighted nilpotent presentation for a graded Lie ring.

Definition 4.2 A Lie ring presentation is said to be canonical weighted nilpotent presentation, if it is of the form

a 1 ,...,a n | c i •a i for i ∈ I, [a j , a i ] = w ij for j > i , ( 10
)
where the w ij are normal words as in [START_REF] Havas | Recognizing badly presented Z -modules[END_REF].

Remark 4.1 Using the results of Section 3 we shall see that each finitely presented graded nilpotent Lie ring possesses such a presentation. Essentially it is enough to see, that the generators corresponding to

a certain lower central factor can be chosen so that the torsion relations are trivial in [START_REF] Havas | Application of computers to questions like those of Burnside[END_REF]. Conversely, it is rather easy to see that a Lie ring defined by a canonical weighted nilpotent presentation is always a finitely presented, nilpotent and graded.

Remark 4.2 Actually we shall construct more than a simple presentation defined in [START_REF] Havas | Application of computers to questions like those of Burnside[END_REF]. We shall construct a presentation in which the lower central factors are canonically presented as abelian groups, according to Theorem 4.1. That is, we shall enforce the appropriate divisibility conditions for the c i .

The following theorem is an easy consequence of Theorem 4.1 and Definition 4.2.

Theorem 4.2 Requiring the divisibility condition for each lower central factor in [START_REF] Havas | Application of computers to questions like those of Burnside[END_REF], the coefficients γ i are uniquely determined by the isomorphism type of L.

Computing the Canonical Weighted Nilpotent Presentation

After this preparation we are ready to describe, how one can compute the canonical weighted nilpotent presentation for a finitely presented nilpotent graded Lie ring.

Recall that we computed the matrix consisting of consistency relations and defining relations. We computed its Hermite normal form. Now we shall compute its Smith normal form. Recall that if M is a n × m matrix then there exist n × n and m × m matrices P and Q, respectively, such that PMQ = S where S is the Smith normal form of M. To construct canonical nilpotent presentation we shall compute S, Q and Q -1 . Using Proposition 8.3.1 of [START_REF] Charles | Computation with finitely presented groups[END_REF] one can compute new generators for the canonical presentation. Put Q = (q i, j ) and Q -1 = ( qi, j ).

The condition for the existence of the definition cannot be kept any more in that case. We use the following approach instead.

Suppose that at a certain layer we introduced new generators x 1 ,... ,x s , such that they correspond to the following products:

x i = [b 1i , b 2i ] where ω(b 1i ) = 1 and ω(b 2i ) = ω(x 1 ) -1, 1 ≤ i ≤ s.
Using Proposition 8.3.1 of [START_REF] Charles | Computation with finitely presented groups[END_REF] one gets the generators a 1 ,... ,a s of the canonical presentation for that layer. Moreover one has that

   a 1 . . . a n    = Q -1    [b 11 , b 21 ] . . . [b 1s , b 2s ]   .
So, we can introduce definitions for the canonical generators of the following form

a i :=q i , 1 [ b 11 , b 21 ] +•••+ qi,s [b 1s ,b 2s ] for 1 ≤ i ≤ s.
That is, the definitions are linear combinations consisting of Lie products with generators of smaller weight.

In Section 2 we already computed products of current weight. They need one more look as follows. After tail computation, we expressed those products in terms of newly introduced generators x 1 ,... ,x s . Now, those generators are to be replaced by the canonical generators a 1 ,... ,a s . To do that we use Proposition 8.3.1 of [START_REF] Charles | Computation with finitely presented groups[END_REF] again. That is,

x i = q i,1 a i +•••+q i,s a s for 1 ≤ i ≤ s.
We proceed the old generators occuring in the epimorphic images in the same way. Lemma 2.1 is still true in the canonical case and its proof can be done in essentially the same way as presented before. Lemma 3.3 seemingly has no connection to the form of the definitions. However, having a deeper look at its proof, one finds that it depends heavily on the concept of definitions, but can be modified to the new approach too.

The canonical weighted nilpotent presentation computed so far depends on the transformer unimodular matrix Q. Among many possible matrices, we want to choose the one with the smallest possible entries, because they will appear in the presentation. This is a hard problem as is stated next. Theorem 4.3 Let L be a finitely presented nilpotent, graded Lie ring. The task of minimising the vectors in the right-hand side of the epimorphic images and the PR relations, according to the maximum norm, (MINLIE)isNP-hard.

Proof . Let MINGCD be the problem that is proved to be NP-hard by Theorem 2 in [START_REF] Havas | Hermite normal form computation for integer matrices[END_REF]. We reduce MINGCD to MINLIE in polynomial time. Let us be given an instance (c 1 ,... ,c n ) of MINGCD. Write down the finite presentation

x 1 ,... ,x n | c 1 x 1 +•••+c n x n = 0, [x i ,x j ] = 0 for 1 ≤ i < j ≤ n .
Clearly, this can be done in time proportional to n 2 . Use LIENQ on this presentation. LIENQ terminates at the abelian factor and produces the following output:

x i ϕ = q i,1 a 1 +•••q i,n a n for 1 ≤ i ≤ n, gcd(c 1 ,... ,c n )a 1 = 0, [a i ,a j ] = 0 for 1 ≤ j < i ≤ n. ( 11
)
Where the transformer matrix Q = (q i, j ). The ability of minimising the vectors in [START_REF] Havas | A nilpotent quotient algorithm for graded lie rings[END_REF] implies the ability of minimising the vectors in Q and hence solving MINGCD. ✷ Another disadvantage of this approach is presented by the following theorem.

Theorem 4. [START_REF] Hall | Some word problems[END_REF] The absolute values of the coefficients appearing in the canonical nilpotent presentation cannot be bounded by a function depending only on the number of generators.

Proof. Easy consequence of [START_REF] Havas | Hermite normal form computation for integer matrices[END_REF] Lemma 4. ✷ 5 Performance

Implementing LieNQ in C

The implementation for the LIENQ algorithm has been written in the C programming language. The currently available version is Version 2.0, which provides time measure, and computations for graded and non-graded cases separately.

The program takes a finite presentation (X , R) for a Lie ring L and the nilpotency class of required factor as its input. It outputs the TR, PR relations and the images of the elements of X under the epimorphism. The nilpotency class can be omitted, in this case the program runs until the lower central series stabilises or the algorithm goes beyond the capacity of the computer.

Throughout the computation the data of the weighted nilpotent presentation is stored in normal word form. At previous stages they were stored as coefficient vectors, but it turned out to be more efficient in an array consisting of structures, where the first element of a structure contains the number of a generator and the second one its coefficient (the idea is due to [START_REF] Nickel | [END_REF]). For instance, the Lie ring element

0 • a 1 + 0 • a 2 + 2 • a 3 -4 • a 4 + 0 • a 5 is stored as (3, 2), (4, -4), (0, 0) .
The first component of the last pair indicates an EOW (end-of-word) sign, while the second one, in fact, is arbitrary.

The information of the weighted nilpotent presentation is stored in several arrays as follows:

Coefficients[i] γ i if i ∈ I , 0 otherwise, Power[i]
w i , right-hand side of the TR relation

γ i • a i , Product[j][i]
w ji , right-hand side of the PR relation [a j , a i ], Epimorphism [i] x i φ, the ith epimorphic image,

Weight[i] ω(a i ), the weight of a i , Dimension[i]
number of generators of weight i,

Definition[i]
the definition of a i .

Note that Definition[i] is an array of structures. A component of the array either contains the number of two generators and a positive integer, if the definition of a i is like

a i = c i • [a k i , a l i ],
or contains the number of the generator from X in the first component and 0 in the second and the third if a i is defined as an epimorphic image. In the latter case the length of the array is, of course, one.

The defining relations are stored as expression trees. See [START_REF] Nickel | Computing nilpotent quotients in finitely presented groups[END_REF] for its description which emphasises its advantages in details.

During the computation graded and non-graded cases are distinguished according to whether the user switched on the -g option or not. There are different tails routines, that is Tails and GradedTails, and consistency routines, like Consistency and GradedConsistency, built into the code. Of course, introducing new generators is also a different task.

It is, however, important to introduce the new generators in the right order. Lemma 3.4 makes it possible to express all tails in terms of generators a k of weight l where a k = [a j , a i ] for some a j of weight l -1 and a i of weight 1. In order to use this fact in practice, we introduce those generators last and when we compute the row Hermite normal form for the matrix they will be, in fact, the only surviving generators and all the others disappear. In this way, we ensure that the new generators indeed have definitions, so the restrictions we kept are reasonable. In the graded case such restrictions are not kept.

The main routines for matrix computation and the basics of the parser program are due to W. Nickel. The first mentioned one uses the GNU MP package to deal with long integers.

LIENQ was successfully compiled on several UN*X platforms, such that Linux, Free-BSD, SunOS, Solaris.

GAP Interface

LIENQ might be invoked from GAP [START_REF] Schönert | GAP -Groups, Algorithms and Programming[END_REF] using a GAP interface. Since GAP does not know about Lie algebras until version 3.5, it is necessary to have at least GAP-3.5 to use the interface. We remark, that even GAP-3.5 knows only Lie algebras but not Lie rings over a ring, so LIENQ kills torsions in that case and GAP considers the result as Lie algebra over Q.

Some Sample Computations

In this section we present some examples, that were tried by LIENQ. We consider the following Lie ring presentations. b,c,d,e | [b,a],[c,a],[e,c],[e,d],[d,a The first example presents the free Lie ring of rank two. The second and third examples are found in [START_REF] Caranti | Thin groups of prime-power order and thin Lie algebras[END_REF] and are of great importance from the point of view of thin Lie algebras. The fourth example is due to Jürgen Wisliceny and has a very nice structure, as we shall see later. The fifth one is not else than the presentation of the positive part of the classical Lie algebra A 10 factored out by the ideal generated by the torsions appearing over Z.

L 1 = x, y L 2 = x, y | [y, x, y], [y, x, x, x, x, x] L 3 = x, y ||[[y, x], x, y], [[y, x], y, x], [[y, x], x, x] + [[y, x], y, y] L 4 = a,
] = [c, b], [d, b] = [e, a], [d, c] = [e, b] L 5 = e 1 ,e
The structure of L 4 is very nice as we mentioned before. Having a look at its canonical weighted nilpotent presentation one has the following.

L i+1 /L i+2 ∼ = C i/2 ⊕ C ∞ ⊕ C ∞ ⊕ C ∞ if i is even, C ∞ ⊕ C ∞ ⊕ C ∞ ⊕ C ∞ ⊕ C ∞ if i is odd. for 0 ≤ i ≤ 67.
By computation, the following structure theorem is true for L 5 . Theorem 6.2 L 5 is nilpotent of class 10. Its lower central factors are of the form

L i 5 /L i+1 5 = C ∞ ⊕•••⊕C ∞ , ( 12
)
where the number if direct factors is 11i for 1 ≤ i ≤ 10.

The structure of L 1 is well known. Witt's formula ( [START_REF] Hall | The Theory of Groups[END_REF] Theorem 11.2.2) can be used to compute the dimension for a lower central factor of L 1 . The result of the computation coincides with the known dimensions.

The One easily sees that using those ideas speeds up the computation by a significant factor. The need of using a better algorithm for Smith normal form computation is reasonable. While computing L 3 an integer overflow occured with 32 bit arithmetic at the 68th factor.

Theorem 6 . 1

 61 The underlying abelian group of the lower central factors of L 4 is of the form

  2 ,e 3 ,e 4 ,e 5 ,e 6 ,e 7 ,e 8 ,e 9 ,e 10 | [e 2 , e 1 , e 1 ], [e 1 , e 2 , e 2 ], [e 3 , e 1 ], [e 4 , e 1 ], [e 5 , e 1 ], [e 6 , e 1 ], [e 7 , e 1 ], [e 8 , e 1 ], [e 9 , e 1 ], [e 10 , e 1 ], [e 3 , e 2 , e 2 ], [e 2 , e 3 , e 3 ], [e 4 , e 2 ], [e 5 , e 2 ], [e 6 , e 2 ], [e 7 , e 2 ], [e 8 , e 2 ], [e 9 , e 2 ], [e 10 , e 2 ], [e 4 , e 3 , e 3 ], [e 3 , e 4 , e 4 ], [e 5 , e 3 ], [e 6 , e 3 ], [e 7 , e 3 ], [e 8 , e 3 ], [e 9 , e 3 ], [e 10 , e 3 ], [e 5 , e 4 , e 4 ], [e 4 , e 5 , e 5 ], [e 6 , e 4 ], [e 7 , e 4 ], [e 8 , e 4 ], [e 9 , e 4 ], [e 10 , e 4 ], [e 6 , e 5 , e 5 ], [e 5 , e 6 , e 6 ], [e 7 , e 5 ], [e 8 , e 5 ], [e 9 , e 5 ], [e 10 , e 5 ], [e 7 , e 6 , e 6 ], [e 6 , e 7 , e 7 ], [e 8 , e 6 ], [e 9 , e 6 ], [e 10 , e 6 ], [e 8 , e 7 , e 7 ], [e 7 , e 8 , e 8 ], [e 9 , e 7 ], [e 10 , e 7 ], [e 9 , e 8 , e 8 ], [e 8 , e 9 , e 9 ], [e 10 , e 8 ], [e 10 , e 9 , e 9 ], [e 9 , e 10 , e 10 ], [e 3 , e 2 , e 1 , e 2 ], [e 4 , e 3 , e 2 , e 3 ], [e 5 , e 4 , e 3 , e 4 ], [e 6 , e 5 , e 4 , e 5 ], [e 7 , e 6 , e 5 , e 6 ], [e 8 , e 7 , e 6 , e 7 ], [e 9 , e 8 , e 7 , e 8 ], [e 10 , e 9 , e 8 , e 9 ] .

  following table contains the computational informations concerning those examples. example class computed nr. of gens. torsion rank CPU time (ms) Since all Lie rings presented by those relations are graded we used the graded approach to compute the presentation for them. That is summarised in the following table. example class computed nr. of gens. torsion rank CPU time (ms) All computations, except for the 67th class of L 4 , were done on a 486-DX4 100 MHz PC with 16 MB memory plus 16 MB swap space. The above mentioned exception was computed on a Sun SparcCenter 2000 with 256 MB of RAM.

	L 1	10	226	0	811100
	L 2	14	89	70	66200
	L 3	12	81	63	33150
	L 4	7	51	22	41333
	L 5	6	45	0	254016
	L 1	10	226	0	8633
	L 1	12	757	0	257383
	L 2	14	57	38	3150
	L 2	18	195	171	197483
	L 3	12	81	63	4133
	L 4	67	300	32	903553
	L 5	10	55	0	36083

† The research presented in this paper was sponsored by the TEMPUS and HCM foundations of the EU.1365-8050 c 1997 Chapman & Hall

Acknowledgements

The author whishes to express his gratitude to those who helped him in the preparation of this paper, but especially to Dr Werner Nickel.


Augustin Ido

Guy Melançon
email: melancon@labri.u-bordeaux.fr

Guy Melanc

Lyndon factorization of the Thue-Morse word and its relatives

Keywords: Lyndon factorization, Thue-Morse word, morphisms

We compute the Lyndon factorization of the Thue-Morse word. We also compute the Lyndon factorization of two related sequences involving morphisms that give rise to new presentations of these sequences.

Introduction

Some attention has recently been given to the Lyndon factorization of infinite words [START_REF] Siromoney | Infinite Lyndon Words[END_REF], [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF], [START_REF] Melanc ¸on | Lyndon Factorization of Sturmian Words[END_REF]. These works are themselves related to the earlier works by Reutenauer [START_REF] Reutenauer | Mots de Lyndon et un théorème de Shirshov[END_REF] and Varricchio [START_REF] Varricchio | Factorizations of Free Monoids and Unavoidable Regularities[END_REF], concerned with unavoidable regularities and semigroup theory.

The results we present here reinforce those in [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF] and [START_REF] Melanc ¸on | Lyndon Factorization of Sturmian Words[END_REF], and give an additional application of the general Lyndon factorization theorem for infinite words ( [START_REF] Siromoney | Infinite Lyndon Words[END_REF]Theorem 2.4]; see [START_REF] Melanc ¸on | Viennot Factorizations of Infinite Words[END_REF] for a generalization). In [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF] we explicitely compute the Lyndon words appearing in the factorization of Sturmian words and identify them as Christoffel primitive words (a result obtained differently by Berstel and de Luca [START_REF] Berstel | Sturmian Words, Lyndon Words and Trees[END_REF]). In this paper, we concentrate on the Thue-Morse word and give the computation of its Lyndon factorization (Theorem 3.1) and describe some of its properties (Corollary 3.2, Remark 3.3 and Corollary 3.4). Incidentally, we are able to compute the factorization for the 'dual' Thue-Morse word in which appears an infinite Lyndon word (cf Theorem 3.7). We also look at relatives (Equations ( 4) and ( 6)) of the Thue-Morse word from the same point of view; these were first studied in [START_REF] Kimberling | Problem E 2850[END_REF] and [START_REF] Brlek | Enumeration of Factors in the Thue-Morse word[END_REF], and later in [START_REF] Allouche | A relative of the Thue-Morse sequence[END_REF]. The factorizations given here for these infinite words (cf Theorems 4.6 and 4.7) use morphisms having special properties with respect to Lyndon words. Moreover, we give identities involving these morphisms for these infinite words.

Basic Results and Notations

The notations used are those usual in theoretical computer science (cf [START_REF] Lothaire | Combinatorics on Words[END_REF]). Throughout the paper, we use the alphabet A = fa; bg, totally ordered by a<b, and we denote by A the set of all words with the lexicographical order.

Lyndon words

Let L denote the set of Lyndon words over A: they are words strictly smaller than any of their proper non empty right factors. For instance, letters are Lyndon words, and ab, aab, abb are Lyndon words if a; b 2 A satisfy a<b. More generally, given two Lyndon words u; v 2 L,wehaveuv 2 L iff u<v. The central result about Lyndon words is Lyndon's factorization theorem: Theorem 2.1 ([5]) Any non-empty word w 2 A is a unique non-increasing product of Lyndon words: w = `1 `n, with `i 2 L (i =1, :::, n) and `1 `n.

For a proof, see [START_REF] Lothaire | Combinatorics on Words[END_REF]. The expression of a Lyndon word as an increasing product of two Lyndon words may not be unique. For example, we have aababb =(a)(ababb)=( aab)(abb)=(aabab)(b).G i v e n w 2 L,definew 00 to be the longest right factor of w qualifying as a Lyndon word. Denote by w 0 the unique left factor of w such that w = w 0 w 00 .T h e nw eh a v ew 0 ;w 00 2 L and w 0 <w<w 00 . Thus, we have e.g. (aababb) 0 = a; (aababb) 00 = ababb. Proposition 2.2 (cf [START_REF] Lothaire | Combinatorics on Words[END_REF]Prop. 5.1.4]) Let u = u 0 u 00 2 L and v 2 L be Lyndon words such that u<v. Then the factorization uv is standard (i.e. (uv) 0 = u; (uv) 00 = v)iffu 00 v.

Infinite Lyndon Words

Siromoney et al. [START_REF] Siromoney | Infinite Lyndon Words[END_REF] have extended Lyndon's theorem to (right) infinite words. They define an infinite word s = a 0 a 1 to be an infinite Lyndon word if an infinite number of its left factors qualify as Lyndon words. For instance, the infinite word abbb = lim n ab n is an infinite Lyndon word; more generally, given u; v 2 L with u<vthe infinite word lim n uv n is an infinite Lyndon word. The central result in [START_REF] Siromoney | Infinite Lyndon Words[END_REF] is: Theorem 2.4]) Any infinite word s factorizes uniquely into one of the following forms: either there exists an infinite non-increasing sequence of finite Lyndon words (`k) k0 such that: s = `0`1

Theorem 2.3 ([16,
or there exist finite Lyndon words `0, ::: , `m 1 ( m0) and an infinite Lyndon word t such that: s = `0 `m 1 t; with `0 `m 1 >t

(2)

Remark 2. [START_REF] Brlek | Enumeration of Factors in the Thue-Morse word[END_REF] In [START_REF] Varricchio | Factorizations of Free Monoids and Unavoidable Regularities[END_REF], the author implicitely shows the existence of the Lyndon factorization of type [START_REF] Allouche | A relative of the Thue-Morse sequence[END_REF] for certain infinite words. This work, as well as [START_REF] Reutenauer | Mots de Lyndon et un théorème de Shirshov[END_REF], is related to the study of unavoidable regularities in infinite words. This is echoed by results in [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF]Sect. 4] and [START_REF] Melanc ¸on | Viennot Factorizations of Infinite Words[END_REF].

Morphisms and Lyndon Words

This last subsection contains a proposition we shall need in the sequel. It formulates a condition for a morphisms to preserve Lyndon words and lexicographical order.

Proposition 2.5

Let A = fa<b gand Z be finite alphabets. Suppose : A ! Z is a morphism given by (a)=a m b p and (b)=a n b q with a m b p <a n b q . Then is strictly increasing over A . Moreover, sends Lyndon words to Lyndon words and preserve their standard factorizations. That is, given w 2 L(A), we have (w) 2 L(B) and (w) 0 = (w 0 ), (w) 00 = (w 00 ).

As a consequence, the sequence ( n (b)) n0 forms a strictly decreasing sequence of Lyndon words.

Remark 2.6

The last statement of Proposition 2.5 has a geometrical interpretation. To each Lyndon word is associated a (planar rooted) binary tree having its leaves labelled by letters. Indeed, the tree associated with w 2 L is either a single vertex labelled by a if w = a 2 A, or is formed of a left tree associated with w 0 and a right tree associated with w 00 . Hence, for a morphism to preserve standard factorization means that the tree structure of (w) is obtained from that of w by attaching to a leave labelled by a,the tree associated with (a) (see Fig. 1).

( Proof of Proposition 2.5.T h a t is strictly increasing over A is easy. An induction then allows to show (L) L since any Lyndon word is an increasing product of two Lyndon words of smaller length. The last part of the proposition is proved using Prop. 2.2. The last part of the statement is clear.

= Y n1 w n (3)
The following corollary is a straightforward consequence of a general result concerning the Lyndon factorization of infinite words. See [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF]Proposition 15]. 3shows that the Thue-Morse word is !-divided. Remark 3.3 For all n 2,t hew ordw n is a conjugate of u n 1 (and of v n 1 ). This is straightforward from the definition for w n in terms of u n 1 ,since(u n 1 )=u n .

Corollary 3.2 Equation

As a consequence of Theorem 3.1, we obtain a second recursive construction for the words w n that does not use the morphism . This result was announced in [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF] (without proof). We prove it here for sake of completeness.

Corollary 3.4 Fo r a l l n 2, we have w n =( w n 1 b 1 ) w 1 w n 2 .

We must first observe that it makes sense to compute w n b 1 since every word w n ends with b,as follows from their definition given in Theorem 3.1.

We proceed by induction and compute, for n 1: w n+1 = a(w n )a 1 = a((w n 1 b 1 )w 1 w n 2 )a 1 = a(w n 1 )(ba) 1 (w 1 )(w 2 ) (w n 2 )a 1 = (a(w n 1 )a 1 )b 1 (w 1 )(w 2 ) (w n 2 )a 1

= (a(w n 1 )a 1 )b 1 (abbaba)(abba) (w n 2 )a 1 = (a(w n 1 )a 1 )b 1 (abb)(ab)(aabba) (w n 2 )a 1 = (a(w n 1 )a 1 )b 1 (abb)(ab)(w 3 a)(w 3 )a 1 a a(w n 2 )a 1

= (a(w n 1 )a 1 )b 1 (abb)(ab)w 3 (a(w 3 )a 1 ) (a(w n 2 )a 1 ) = (w n b 1 )w 1 w 2 w n 1

Proof of Theorem 3.1. First observe that if n ends with a b, then the last letter of (w n ) is equal to a.So we may compute (w n )a 1 , showing that w n is well defined for all n 1. To show that is obtained by the infinite product expansion (3) we only have to verify that Q n1 w n is kept fixed by .Wehave:

( Y n1 w n ) = (abb) Y n2 (w n ) = (abb)(ab)a Y n2 (w n ) = w 1 w 2 Y n2 a(w n )a 1 = w 1 w 2 Y n3 w n = Y n1 w n
Now, we need to show that a(w n )a 1 form a decreasing sequence of Lyndon words. Observe first that is increasing, since (a) and (b) have the same length and (a) <(b). Hence, assuming w n >w n+1

for n 1,wefind(w n ) >( w n +1 ) from which follows w n+1 = a(w n )a 1 >a(w n +1 )a 1 = w n+2 . Hence the sequence (w n ) n1 is decreasing.

Again, we use the fact that is increasing to show by induction that w n (n 1) is a Lyndon word.

This holds true for w 1 ;w 2 . By virtue of Remark 3.3, we know that w n is a conjugate of u n 1 .S i n c e Lyndon words are minimal representatives of their conjugacy classes, assume inductively that the least element of the conjugacy class of u n 1 is w n . Now, observe that the elements of the conjugacy class for u n = (u n 1 ) are of the form (v), a(v)a 1 , b(v)b 1 where v is a conjugate of u n ,s i n c e j(a)j = j(b)j =2. So we deduce that the least element among these is a(v)a 1 where v is the least element of the conjugacy class for u n . This shows that w n+1 = a(w n )a 1 is a Lyndon word. That concludes the proof of Theorem 3.1.

2 Remark 3.5 The idea of using the pattern n+1 = a(w n )a 1 for proving Theorem 3.1 was suggested to us by G. Sénizergues, who happened to read a first version of the manuscript. This idea may be exploited to obtain the factorization for the 'dual' Thue-Morse word, namely lim n v n (see the next remark). Remark 3.6 Note that we could have set a>b ; this would amount to imposing on A the inverse lexicographical order. Note that, for all n 0, v n is obtained from u n by exchanging a's and b's. Hence, the factorization of u n using the total order a>bis directly obtained from that of v n with a<b.T h e next theorem fully answers the question just raised. Theorem 3.7 Let w 1 = aab and and for all n 1, w n+1 = a(w n )a 1 .T h ew o r d s(w n ) n1 form a stricly increasing sequence of Lyndon words such that w n is a left factor of w n+1 . Thus, `= lim n w n is an infinite Lyndon word, and we have a`= (`). Moreover, the factorization of the 'dual' Thue-Morse word is of type [START_REF] Berstel | Axel Thue's papers on repetitions in words: a translation[END_REF] and is lim n v n = b`. Proof.T h a t(w n ) n1 is an increasing sequence of Lyndon words is proved as in Theorem 3.1. That w n is a left factor of w n+1 is a property gained from the morphism . So, we may indeed define the limit `= lim n w n which is by definition an infinite Lyndon word (cf. Sect. 2.2). The identity a`= (`) is equivalent to `= a 1 (`), which comes at once from the definition for To show that we have lim n v n = b`, we verify that the latter is kept fixed by .Wehave: More precisely, it is possible to show that the words u n factorize as a decreasing product of p(n) Lyndon words, u n = w n 1 w n p(n) where p(n)=3k 1if n =2kand p(n)=3kif n =2k+1,andthatw n 1 i and w n i coincide for i =1, :::, n 2. For more details, the reader is referred to [START_REF] Ido | Factorisation du mot de Thue-Morse et de deux mots cousins[END_REF].

(b`) = (b lim n1 w n ) = ba lim n1 (w n ) = b lim n1 a(w n ) = b lim n1 a(w n )a 1 = b lim n1 w n+1 = bR
Lemma 4.5 ([1, Lemma 2]) The infinite word is completely determined by the following conditions:

2n+1 =1 4 n+2 =0 4 n = n (7)
We define two morphisms : f1; 2g f0;1g and : f1; 2g f1;2g by setting (1) = 01,

(2) = 0111,a nd(1) = 112 and (2) = 11222. Note that, by virtue of Proposition 2.5, both and preserve the order on A and send Lyndon words to Lyndon words. As a consequence, we are able to show that is, except for its first letter, a morphic image of d. As we will see, that is in fact a consequence of [1, Lemma 2] (Lemma 4.5 above). We have the following theorems:

Theorem 4.6 Consider the sequence of words (s n ) n0 with s 0 =2 , s n+1 = (s n ) (n 0). The words (s n ) n0 form a strictly decreasing sequence of Lyndon words and we have:

d = Y n0 s n (8)
Moreover, this infinite product expansion for d implies d =2 (d).

Theorem 4.7 Consider the sequence of words (t n ) n0 with t 0 =1and t n+1 = (s n ) (n 0). The words (t n ) n0 form a strictly decreasing sequence of Lyndon words and we have:

= Y n0 t n (9)
Moreover, this infinite product expansion for implies =1 (d).

Remark 4.8 Theorems 4.7 and 4.6 should be looked at from a point of view developed in [START_REF] Shallit | A Generalization of Automatic Sequences[END_REF], where the author answers a question asking for conditions for the characteristic word of a sequence to be the image a fixed point of a morphism.

Define the sequence of integers m =( m i ) i 0 with m 0 =1and m n+1 =4 m n +1 ; hence we have m =1 , 5, 21, 85, ::: Let (w n ) n0 be the unique consecutive factors of d, starting with w 0 = d 0 =2 defined by w n+1 = d m0++mn+1 d m0++mn+mn+1 , satisfying jw n j = m n . Hence, we have w 0 = 2, w 1 = 11222, w 2 = 112112112221122211222, ::: Proposition 4.9 We have, for any n 0, w n+1 = (w n ).

As we will see, this proposition is a consequence of Equation [START_REF] Kimberling | Problem E 2850[END_REF]. First, observe that by definition of , we have for any w 2 A , j(w)j 1 = 2(jwj 1 + jwj 2 ) j(w)j 2 = jwj 1 +3jwj 2 [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF] Then observe that, since w 0 =2 , we may show by induction that j n (w 0 )j 2 = j n (w 0 )j 1 +1and j n (w 0 )j = m n . Recall from Equation (4) that for any n, the letter d n is determined by the difference c n+1 c n . Moreover, we have c n+1 =( P n i=0 d i )+1= ( P n i=0 c i+1 c i )+1 . Hence, it is natural to think of the letter d n as corresponding to the integer c n+1 . Any integer 2 c is of the form = c k for agivenk 0. We denote this unique integer by c 1 (m). So for instance, c 1 (3) = 1;c 1 (4) = 2 and c 1 (5) = 3; hence d c 1 (3) 1 = d 0 =2 ,andd c 1 (4) 1 = d 1 = d c 1 (5) 1 = d 2 =1 . associating to c n+1 (n 0) the letter d n , we see that the mapping T is nothing else but the morphism . Indeed, the only integer in T (c n ) not belonging to c is the least element of T (c n ), namely 2c n .L e t us prove this claim. Suppose d n =1 ;t h e nw eh a v ec n+1 c n =1and T (c n 2 c n ; 2 c n +1 g and 2c n 6 2 c; 2c n +1 2 cis obviously true. Suppose now d n =2 . We obviously have 2c n 6 2 c, 2c n +1 ;2c n +32 c. Moreover, we have 2c n +2 2csince c n +1 6 2 c because c n+1 c n =2 .T h e equality =1 (d)is straightforward. This concludes the proof of Theorem 4.7.

2

Fig. 1 :

 1 Fig. 1: Computing the image of ababb under (preserving standard factorization).

2 3Theorem 3 . 1

 231 Factorizing Thue-Morse's WordIn this section, we give the computation of the Lyndon factorization (1) for the Thue-Morse word. Let A = fa; bg and set u 0 = a and v 0 = b.D e fi n ef o ra l ln 1,u n = u n 1 v n 1 and v n = v n 1 u n 1 . Hence, u 1 = ab, v 1 = ba, u 2 = abba, v 2 = baab, and so on. The sequence (u n ) n0 converges to a unique infinite word , called the Thue-Morse word (over fa; bg). This infinite word possess numerous interesting properties (cf [8, Chap. 2]), and has been studied by a large number of authors; the interested reader is refered to (the bibliography of) the survey by Berstel[START_REF] Berstel | Axel Thue's papers on repetitions in words: a translation[END_REF]. The words u n may alternatively be obtained using a morphism we denote : A ! A ,d e fi n e db y(a)=ab and (b)=ba.O n et h e n finds u n = (u n 1 ),foralln 1. Iterating to infinity leads to = lim n1 n (a); this is equivalent to the fact that is a fixed-point of .Recall that if u 2 A and a 2 A then the expression ua 1 consists in deleting the last a in u (if possible). Our main result concerning the Thue-Morse word is: Let w 1 = abb, w 2 = ab, and for all n 2, w n+1 = a(w n )a 1 .T h ew o r d s(w n ) n1 form a strictly decreasing sequence of Lyndon words, and we have:

emark 3 . 8

 38 Another proof of Theorem 3.1 proceeds by induction and first computes the Lyndon factorization of all u n (and all v n ). It then exploits the fact that these factorizations stabilize, i.e. they form a converging sequence of finite decreasing sequence of Lyndon words. This proof we first developed enabled us to obtain the exact number of factors occuring in the factorization for u n (and v n ).

Acknowledgement

We wish to thank the referees for their comments that helped improve the organization of the paper.

Remark 3.9 There exists a generalization of the Thue-Morse word over an arbitrary finite alphabet A.

We define it here over the three letters and refer the interested reader to [START_REF] Brlek | Enumeration of Factors in the Thue-Morse word[END_REF]. Define three sequence of words by setting u 0 = a, v 0 = b, w 0 = c and u n+1 = u n v n w n , v n+1 = v n w n u n , w n+1 = w n u n v n . Then the word = lim n u n is the Thue-Morse word over fa; b; cg. It may also be obtained as the limit lim n n (a),where is the morphism sending a 7 abc, b 7 bca and c 7 cab.

It is natural to look at the Lyndon factorization for this general Thue-Morse word. However, the problem of describing this factorization is still open. Indeed, our techniques did not enable us to obtain any result as for the two letter case.

Factorization and Properties of Thue-Morse's Relatives

In this section, we give a complete description of the Lyndon factorization of two infinite words d and obtained from infinite sequences (d n ) n0 and ( n ) n0 related to the Thue-Morse word. These were first studied in [START_REF] Kimberling | Problem E 2850[END_REF] and [START_REF] Brlek | Enumeration of Factors in the Thue-Morse word[END_REF], and later in [START_REF] Allouche | A relative of the Thue-Morse sequence[END_REF]. Definition 4.1 ([7]) Let c =(c n ) n 0 , c n 2IN , be defined inductively by c 0 =1and:

Thus, c =1, 3, 4, 5, 7, 9, 11, 12, 13, ::: Equivalently, c is the lexicographically least sequence of positive integers satisfying n 2 c implies 2n 6 2 c (cf [START_REF] Allouche | A relative of the Thue-Morse sequence[END_REF]). Note that the difference between two consecutive terms in the sequence is c n+1 c n =1or 2. Hence, we may define: Definition 4.2 Let d = d 0 d 1 denote the infinite word defined by

Hence, we have d = 21122211211211222 . The link between this sequence and is given by the following result:

The sequence (d n ) n0 and the coding given in Equation 5 appeared for the first time in [START_REF] Brlek | Enumeration of Factors in the Thue-Morse word[END_REF]. In [START_REF] Allouche | A relative of the Thue-Morse sequence[END_REF], it is proved that d n = c n+1 c n . The sequence c may also be studied by means of its characteristic function (or sequence) we now define.

for all n 1. We then define the infinite word by setting = 0 1 2 Hence, we have = 1011101010111 . We will make use of a result borrowed from [START_REF] Allouche | A relative of the Thue-Morse sequence[END_REF].

Lemma 4.10 Let n 0. Suppose first that d n = c n+1 c n =1 .T h e n4c n 2 c,but4c n +2 6 2 c.

.

Suppose now that d n = c n+1 c n =2 .T he n4c n 2 c,but4c n +2;4c n +4;4c n +6 6 c. Consequently,

Suppose d n =1 .T h a t4c n 2 c follows from the fact that 2c n 6 2 c,sincec n 2 c.That4c n +26 2 c is given by Equation [START_REF] Kimberling | Problem E 2850[END_REF]. That 4c n 1, 4c n +1, 4n+32cfollows from the fact that c contains every odd integer. Hence the integers 4c n 1; 4c n ; 4c n +1 ;4c n +3are consecutive terms in c. Hence, we have

.

Suppose now that d n =2 .A g a i n ,w eh a v e4c n 2 c.T h a t4c n +2 ;4c n +6 6 2 c follows from Equation [START_REF] Kimberling | Problem E 2850[END_REF]. Observe that, c n+1 c n =2implies that c n +1 6 2 c, hence 2c n +2 2cso 4c n +4 6 2 c. That 4c n + k 2 c for k = 1; 1; 3; 5; 7 follows from the fact that they all are odd. Hence, the integer 4c n 1; 4c n ; 4c n +1 ;4c n +3 ;4c n +5 ;4c n +7are consecutive terms in c. Hence, we have

Proof of Proposition 4.9. We first associate to any integer c n a subsequence S(c n ) of c by setting:

f4c n 1 ;4c n ;4c n +1;4c n +3 gif c n+1 c n =1 f4c n 1 ;4c n ;4c n +1;4c n +3 ;4c n +5 ;4c n +7gotherwise

Observe that S(c n ) and S(c n+1 ) only have a single element in common, namely the greatest element of S(c n ) which is also the least element of S(c n+1 ). This element is equal to 4c n +3 if c n+1 c n =1 ,andto 4c n +7otherwise, as is easily checked. This shows that c 0 ; S(c 0 ); S(c 1 ), ::: coincides with c. Moreover, associating to c n+1 (n 0) the letter d n , we see that the mapping S is nothing else but the morphism . Indeed, suppose d n = c n+1 c n =1then we have S(c n )=f 4 c n 1 ;4c n ;4c n +1 ;4c n +3 g;thethree letter word associated with this subsequence, which is a factor of d,is112. The case d n =2is similar.

We now define for all n 0 a subsequence I n of c.P u tI 0 = fc 0 g,andI n+1 = S(I n ).W eh a v e c = I 0 ;I 1 , ::: ; this follows from c = c 0 ; S(c 0 ); S(c 1 ), ::: Now, we claim that the number of elements in I n (n 0) is equal to m n +1. Indeed, this follows from the observation that S coincides with when going from c to d. Hence, a simple induction counting the number of consecutive terms c k ;c k+1 of I n according to the value c k+1 c k =1or c k+1 c k =2leads to a result identical with Equations [START_REF] Melanc ¸on | Lyndon Factorization of Infinite Words[END_REF]. This implies that the factor of d associated with I n is equal to w n , since its length is jI n j 1=m n .T his , together with the previous observation that S coincides with , concludes the proof of Proposition 4.9. 2 Proof of Theorem 4.6. The first part of the statement follows directly from Proposition 2.5 applied to and from Lemma 4.9. The last part of the statement is clear.

2

Proof of Theorem 4.7. The first part of the statement is also proved using Proposition 2.5. Next, we use a technique similar to the one developed for the proof of Proposition 4.9.

We first associate to any integer c n a subsequence T (c n ) of consecutive integers by setting: Observe that T (c n ) and T (c n+1 ) are disjoint and that the greatest element of T (c n ) is one less than the least element of T (c n+1 ). This shows that every integer except 1 appears in T (c 0 ), T (c 1 ), ::: Moreover,