Frédérique Bassino

Marie-Pierre Béal

Dominique Perrin

Ed Fr

Bassino Erique

Gaspard Institut

Monge

Enumerative sequences of leaves and nodes in rational trees

HAL is

Introduction

This paper is a study of problems linked with coding and symbolic dynamics. The results can be considered as an extension of the old results of Hu man, Kraft, McMillan and Shannon on source coding. We actually prove results on rational sequences of integers that can be realized as the enumerative sequence of leaves or nodes in a rational tree.

Let s be an IN-rational sequence of nonnegative numbers, that is a sequence s = (s n ) n 1 such that s n is the number of paths of length n going from an initial state to a nal state in a nite multigraph or a nite automaton. We say that s satis es the Kraft inequality for a positive integer k if P n 1 s n k n 1. 1 A rational tree is a tree which has only a nite number of non-isomorphic subtrees. If s is the enumerative sequence of leaves of a rational k-ary tree, then s satis es Kraft's inequality for the integer k.

In this paper, we study the converse of the above property. Consider for example the series s(z) = 3z 2 1 z 2 . We have s(1=2) = 1 and we can obtain s as the enumerative sequence of the tree of the gure below associated with the pre x code X = (aa) (ab + ba + bb) on the binary alphabet fa; bg.

Fig. 1. Tree associated to 3z 2 (z 2 ) Known constructions allow one to obtain a sequence s satisfying Kraft's inequality as the enumerative sequence of leaves of a k-ary tree, or as the enumerative sequence of leaves of a (perhaps not k-ary) rational tree. These two constructions lead in a natural way to the problem of building a tree both rational and k-ary. This question was already considered in 10], where it was conjectured that any IN-rational sequence satisfying Kraft's inequality is the enumerative sequence of leaves of a k-ary rational tree.

In this paper, we prove this conjecture in the case where the sequence satis es Kraft's inequality with a strict inequality. Proofs and algorithms used to establish this result are based on automata theory and symbolic dynamics. In particular, we use the state splitting algorithm which has been introduced by R. Adler, D. Coppersmith and M. Hassner in 1] to solve coding problems for constrained channels by constructing nite-state codes with sliding block decoders. This was partly based on earlier work of B. Marcus in 7]. A variant of Franaszek's algorithm of computation of an approximate eigenvector makes the algorithms practical.

A variant of the problem considered here consists in replacing the enumerative sequence of leaves by the enumerative sequence of all nodes. Soittola ( 12]) has characterized the series which are the enumerative sequence of nodes in a rational tree. We prove that any IN-rational sequence t that satis es some necessary conditions : t 0 = 1, 8n 1; t n kt n 1 , the convergence radius of t is strictly greater than 1=k, and such that t has a primitive linear representation, is the enumerative sequence of nodes by height of a kary rational tree. The proof of this result is based on an extended notion of state splitting that allows us to output split states without outgoing edges.

The problem of a similar characterization for rational k-ary trees remains open in the general case.

The paper is organized as follows. We rst give basic de nitions and properties of rational objects, sequences and trees. We then give some denitions coming from the theory of symbolic dynamics. We de ne the notions of state splitting, approximate eigenvector and recall the algorithm of 1]. In Section 3, we establish the announced result (Theorem 1) concerning enumerative sequences of leaves and an give example for the construction. Next we give an e cient algorithm, that is a variant of Franaszek's algorithm, to nd approximate eigenvectors. Section 5 devoted to enumerative sequences of nodes gives an extension (Theorem 2) of the main result of Section 3.

A preliminary shorter version of this paper was presented at the ICALP'97.

2 De nitions and background

Rational sequences of nonnegative numbers

We denote by G a directed graph with E as its set of edges. We actually use multigraphs instead of ordinary graphs in order to be able to have several distinct edges with the same origin and end. Formally a multigraph is given by two sets E (the edges) and V (the vertices) and two functions from E to V which de ne the origin and the end of an edge. An edge in a multigraph going from p to q will be noted (p; x; q) where x 2 IN. This is equivalent to number the edges going from p to q in order to distinguish them. We shall always say \graph" instead of \multigraph".

In this paper, we consider sequences of nonnegative numbers. Such a sequence s = (s n ) n 0 will be said to be IN-rational if s n is the number of paths of length n going from a state in I to a state in F in a nite directed graph G, where I and F are two special subsets of states, the initial and nal states respectively. We say that the triple (G; I; F) is a representation of the sequence s. We now give some basic de nitions about trees. A tree T on a set of nodes N with a root r is a function T : N frg ! N which associates to each node distinct from the root its father T(n) in such a way that, for each node n, there is a nonnegative integer h such that T h (n) = r. The integer h is the height of the node n. A tree is k-ary if each node has at most k sons. A leaf is a node without son. We denote by l(T) the enumerative sequence of its leaves by height, that is the sequence of numbers s n , where s n is the number of leaves of T at height n. A tree is said to be rational if it admits only a nite number of non isomorphic subtrees. If T is a rational tree, the sequence l(T) is an IN-rational sequence.

The sequence s = l(T) of a k-ary tree is the length distribution of a pre x code over a k-letter alphabet. The associate series s(z) = P n 1 s n z n satis es then Kraft's inequality : s(1=k) 1. We shall say that Kraft's strict inequality is satis ed when s(1=k) < 1. The equality is reached when each node of the tree has exactly zero or k sons. Conversely, the McMillan construction establishes that for any series s satisfying Kraft's inequality, there is a k-ary tree such that s = l(T). Moreover, if the series satis es Kraft's equality, then the internal nodes will have exactly k sons. But the tree obtained is not rational in general.

It is also easy to see that an IN-rational sequence is the enumerative sequence of the leaves of a rational tree. A normalized representation can be used to do that by \developing" the tree. The root will correspond to the initial state of the graph. If a node of the tree at height n corresponds to a state i in the graph which has r outgoing edges ending in states j 1 ; j 2 ; : : :; j r , it will admit r sons at height n + 1, each of them corresponding respectively to the states j 1 ; j 2 ; : : :; j r of the graph. The leaves of the tree will correspond to the nal states of the normalized representation. The maximal number of sons of a node we get is then equal to the maximal number of edges going out of any state of the graph of this representation.

If s satis es Kraft's inequality, the above construction does not lead in general to a k-ary rational tree. The aim of this paper is to get a k-ary rational tree T such that s = l(T). This result was conjectured in 10]. We solve it for all IN-rational sequences satisfying Kraft's strict inequality and give a weaker result for the case of equality.

Approximate eigenvector and state splitting

Let s be an IN-rational sequence and let (G; i; F) be a normalized representation of s. If we identify the initial state i and all nal states of F in a single state still denoted i, we get a new graph denoted G, which is strongly connected. The sequence s is then the length distribution of the paths of rst returns to state i, that is of nite paths going from i to i without going through state i. Using the terminology of symbolic dynamics, the graph G can be seen as an irreducible shift of nite type (see, for example, 3], 4] or 6]).

We denote by M the adjacency matrix associated to the graph G, that is the matrix M = (m ij ) 1 i;j n , where n is the number of nodes of G and where m ij is the number of edges going from state i to state j. By the Perron-Frobenius theorem (see 6]), the positive matrix M associated to the strongly connected graph G has a positive eigenvalue of maximal modulus denoted by , also called the spectral radius of the matrix. Actually, only depends on the series s, 1= is the minimal modulus of the poles of 1 1 s . The dimension of the eigenspace of is equal to one. There is a positive eigenvector (componentwise) associated to . Moreover, if there is a positive eigenvector associated to an eigenvalue , then = .

When is an integer , the matrix admits a positive integral eigenvector.

When < k, where k is an integer, the matrix admits a k-approximate eigenvector, that is, by de nition, a positive integral vector v with Mv kv.

For example the left side of the gure below gives a representation (G; i; F) of the serie s(z) = 3z 2 =(1 z 2 ), and the right side gives the associated graph G. The adjacency matrix of G is

M = 0 B @ 0 3 0 1 0 1 0 1 0 1 C A
Its maximal eigenvalue is = 2. The components of a positive integral eigenvector are written on the nodes. We now de ne the operation of output state splitting in a graph G = (V; E). Let q be a vertex of G and let I (resp. O) be the set of edges coming in q (resp. going out of q). Let O = O 0 + O 00 be a partition of O. The operation of (output) state splitting relative to (O 0 ; O 00 ) transforms G into the graph G 0 = (V 0 ; E 0 ) where V 0 = (V nfqg) q 0 q 00 is obtained from V by splitting state q into two states q 0 and q 00 , and where E 0 is de ned as follows:

1. All edges of E that are not incident to q are left unchanged. 2. The both states q 0 and q 00 have the same input edges as q.

3. The output edges of q are distributed between q 0 and q 00 according to the partition of O into O 0 and O 00 . We denote U 0 and U 00 the sets of output edges of q 0 and q 00 respectively : U 0 = f(q 0 ; x; p) j (q; x; p) 2 O 0 g and U 00 = f(q 00 ; x; p) j (q; x; p) 2 O 00 g.

O" q O' Fig. 4. Graph G q" U' q' U" Fig. 5. Graph G 0 Let us now assume that v is a k-approximate eigenvector for the graph G. We denote by v p the component of index p of v. All components v p are positive integers. A state splitting of a state q is said to be admissible according to k, if the partition in O 0 and O 00 is such that O 0 and O 00 are not empty and:

k divides X (q;x;r)2O 0 v r
If the state splitting is admissible (according to k), the vector v 0 de ned as follows will be a k-approximate eigenvector for the new graph G 0 . If p is a state distinct from q 0 and q 00 then v 0 p = v p . For states q 0 and q 00 we have: v 0 q 0 = 1 k X (q;x;r)2O 0 v r and v 0 q 00 = v q v 0 q 0 : By the state splitting construction, one can check that M 0 v 0 kv 0 , where M 0 is the adjacency matrix of G 0 .

The state splitting algorithm of 1] ensures that there is a nite number of state splittings leading to a k-ary graph, that is a graph such that at most k edges are going out of any state. For the sake of completeness, we brie y recall the proof. If there is a state q which admits more than k edges going out of it, we choose k of them and denote by r 1 ; r 2 ; : : :; r k the sequence of end states of these edges. We then choose a subset O 0 of these k edges such that k divides P (q;x;r)2O 0 v r . This is always possible. Indeed, by considering the k + 1 numbers v r 1 ; v r 1 + v r 2 ; : : :; v r 1 + v r 2 + v r k , we can see that at least two of them are equal modulo k, and then their di erence is equal to zero modulo k. The partition of the output edges of q in O 0 and O 00 leads to an admissible state splitting and v 0 q is strictly less than v q . This point ensures that the process stops after a nite number of splits, the nal number of states being bounded by the sum of the components of the initial approximate eigenvector. The nal graph obtained is k-ary.

We shall compute approximate eigenvectors for the strongly connected graphs G associated to normalized representations (G; i; F) of sequences.

We shall then perform admissible state splittings that can be seen either on the graph G or on the graph G. To do that, we shall associate to each node of G a value equal to the corresponding component of the approximate eigenvector of the graph G. The initial and the nal states will have same value since they correspond to the same state of G.

Enumerative sequences of leaves

We now state the result in the case of Kraft strict inequality.

Theorem 1 Let s = (s n ) n 1 be an IN-rational sequence of nonnegative integers et let k be an integer such that P n 1 s n k n < 1. Then there is a k-ary rational tree such that s is the enumerative sequence of its leaves.

In order to prove this result, we rst prove one lemma that remains true in the case of equality. We therefore consider an IN-rational sequence s and an integer k such that P n 1 s n k n 1. We begin with a normalized representation (G; i; F) of the IN-rational sequence s. We denote by M the adjacency matrix of G and by its spectral radius. Then k. We then compute a k-approximate eigenvector v = (v 1 ; v 2 ; : : :; v n ) t of the graph G.

By de nition, we have Mv kv. Without loss of generality, we can assume that state 1 is the initial state in all normalized representations.

Lemma 1 If k divides v 1 , then there is another normalized representation for s and a new corresponding approximate eigenvector v 0 with v 0 1 = v 1 div k.

Proof : We denote by P the set of states q such that there is in G an edge denoted (q; x; t) going from q to a nal state t of F. Remark that, as state t is equal to state 1 in G, the value of state t is equal to the value of state 1.

Let us rst suppose that the initial state 1 does not belong to P. If there is in P a state q which admits more than one (say n) outgoing edges, we split q in q 0 and q 00 according to partition (O 0 ; O 00 ) where O 0 = f(q; x; t)g contains exactly one edge. Since k divides v 1 , this state splitting is admissible and v 0 q 0 = v 1 div k. Moreover, in the new graph G 0 , q 0 admits only one outgoing edge (going to t) and q 00 is either not in P or admits less than n outgoing edges. By successive state splittings of all states in P having more than one outgoing edges, we shall get, in a nite number of steps, a representation such that all states with one outgoing edge ending in F have no other outgoing edges. Under the hypothesis that state 1 does not belong to P, the initial state has not been split during this process and so each new computed graph is still a normalized representation of the sequence. We denote again by (G; 1; F) the nal representation obtained for s and by P last the set of states having one outgoing edge ending in F in this graph. Remark that the values of states of P last are greater than or equal to v 1 div k. We turn all values of states of P last greater than v 1 div k into v 1 div k; the vector v remains a k-approximate eigenvector.

We then transform the representation (G; 1; F) in a new one, (H; i; P last ), where H is the graph obtained from G by adding a state i, an edge from i to 1 and by removing all edges of G going out of a state of P last . If we look at paths in G going from 1 to F, we have just cut the last edge and added one at the beginning. We assign to state i the value v 1 div k, and the values of all states correspond now to a new k-approximate eigenvector for H. We call this tranformation the \shift" transformation.

Let us now suppose that the initial state 1 belongs to P. We rst split, as explained above, all states of P having more that one outgoing edge. In this case, state 1 may have been split. We denote by 1 (1) ; 1 (2) ; 1 (3) ; : : :1 (r) the copies of state 1 obtained by successive state splittings of the initial state 1. We still denote by G the graph obtained by this transformation and by P last the set of states having one outgoing edge ending in F in this graph. We then transform the representation (G; 1; F) into a new one, (H; i; P last ), where H is the graph obtained from G by adding a state i, an edge from i to each 1 (j) ; 1 j r and by removing all edges of G going out of a state of P last . Remark that (r 1) states among 1 (1) ; 1 (2) ; 1 (3) ; : : :1 (r) belong to P last . We again assign to the state i the value v 1 div k, and the values of all states correspond now to a new k-approximate eigenvector for H. 2 Corollary 1 If v 1 is a power of k, then there is another normalized representation and a new corresponding approximate eigenvector v 0 with v 0 1 = 1.

Proof : If v 1 = k m , we iterate the construction given in previous lemma and get v 0 1 = 1 in m steps. 2

Example

Let s be the following series:

s(z) = 2z 3 + 2z 2 z 2 (z 2 )
Here, k = 2 and s(1=2) = 1:

In the following pictures, the nodes are labeled with their value. The last step is described in the proof of Theorem 1. It corresponds here to a state splitting of all states of the graph of value different from 1.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Fig.

Last representation

We now prove another lemma which is true only in the case of Kraft strict inequality.

Lemma 2 Let M be a nonnegative integral matrix. If its spectral radius is strictly less than k, then there is a k-approximate eigenvector w of M such that w 1 is a power of k.

Proof : Let ( < k) be the positive real eigenvalue of maximal modulus of M and let v be an eigenvector associated to . We denote by P the set of positive vectors w such that Mw < kw. The set P is an open set and v belongs to P. By dividing all components of v par v 1 , we can assume that v 1 is equal to 1. As P is open, there is a positive real such that B(v; ) P, where B(v; ) = fw j v i w i v i + g. Let us now choose an integer m such that 1=k m < . As B(v; 1=k m ) P, we have fk m w j w 2 B(v; 1=k m )g P. This set is fw j k m v i 1 w i k m v i + 1g and contains w where w i = dk m v i e. This vector is a positive integer vector w with Mw < kw : it is a k-approximate eigenvector. Moreover w 1 = k m .

2

We now prove Theorem 1.

Proof : (Theorem 1) We begin with a normalized representation of s and compute, by Lemma 2, a k-approximate eigenvector whose component for the initial state is a power of k. We then compute, by Corollary 1, a normalized representation (G; 1; F) of s which admits a k-approximate eigenvector of component 1 for the initial state. Finally, we apply to G the state splitting algorithm described in the previous section to obtain a k-ary graph. As the component of the approximate eigenvector on the initial state is 1 and as the state splittings have to be admissible, this state will never be split during the process. A state splitting of a state of G di erent from state 1 leads by construction to a graph G 0 still representing the same sequence. The result follows then from the fact that the nal normalized representation has a k-ary graph. 2

We can apply the construction given above to the case of Kraft equality when it is possible to nd a representation of s which admits a k-eigenvector with a power of k as component on the initial state. This may perhaps not always be the case. We can consider the example : s(z) = (2z + 2z 2 )(z 2 ) z. It has a representation given by the graph G with an eigenvector such that v 1 = 3 and it admits also the representation given by graph H with an eigenvector such that v 1 = 1. The series is also equal to 2z 2 z . There is no hope to succeed in transforming G into H by state splitting and merging since H and G are non isomorphic symbolic subshifts.

Computation of an approximate eigenvector

Although Lemma 2 tells us that, for an irreducible matrix with a spectral radius strictly less than an integer k, an approximate eigenvector with a power of k as rst component, exists, it does not provide a good way to nd one. Fortunately, there is an e cient algorithm to nd such small approximate eigenvectors. The algorithm we give is a variant of Franaszek's algorithm to compute an upper approximate eigenvector (see 6] p.153). This makes the algorithm of Theorem 1 practical.

Let M be a nonnegative irreducible integral matrix and its spectral radius. If k, a k-upper approximate eigenvector is a positive integral vector v such that Mv kv. If k, a k-lower approximate eigenvector is a positive integral vector v such that Mv kv. In the case where < k, we want to compute a k-lower approximate eigenvector with a rst component which is a power of k. In the sequel, we shall omit the word lower.

We use the following notation to state the algorithms. If u and v are vectors, let w = maxfu; vg (resp. w = minfu; vg) denote the componentwise maximum (resp. minimum), so that w i = maxfu i ; v i g (resp.

w i = minfu i ; v i g) for each index i. For a real number r, let dre denote the integer top of r, i.e., the smallest integer greater than or equal to r.

Proposition 2 Let M be an integral irreducible matrix with a spectral radius less than or equal to an integer k. A smallest k-approximate eigenvector exists. If the spectral radius is strictly less than k, a smallest k-approximate eigenvector, whose rst component is a power of k, exists.

Proof : The proof of the existence of a k-(lower) approximate eigenvector is the same as the proof of the existence of a k-upper approximate eigenvector (for irreducible matrices with a spectral radius greater than or equal to k). Let now u and u 0 be two k-approximate eigenvectors. Then it is straightforward that v = minfu; u 0 g is a k-approximate eigenvector.

When the spectral radius is strictly less than k, the proof of the existence of a k-approximate eigenvector, whose rst component is a power of k, is given in Lemma 2. If u and u 0 are two k-approximate eigenvectors, whose rst component is a power of k, then this is true also of minfu; u 0 g. 2

The lower version of Franaszek's algorithm that computes the smallest k-approximate eigenvector is the following: The proof that the algorithm is correct is the following: Proof : The vectors computed are monotonically nondecreasing in each component. Let u be a k-approximate eigenvector. As all components of u are positive integers, we have v 0 u. In fact, this is true for the rst vector v 0 = (1; 1; : : :; 1) t . If we assume that v u in the repeat loop, then either v 0 = v, or v 0 = d 1 k Mve. In the rst case, v 0 u. In the second case, v 0 d 1 k Mue due. Since u has integer components, we also get v 0 u.

This proves that the process eventually stops.

The nal vector v obtained is then a k-approximate eigenvector. In fact, as v 0 = v, d 1 k Mve v. Then Mv kv. As v is less than or equal to any other k-approximate eigenvector, it is the smallest. 2

We now suppose that the spectral radius of M is strictly less than k. We are interested in computing a k-approximate eigenvector whose rst component is a power of k. We give a variant of Franaszek's algorithm that nds the smallest k-approximate eigenvector whose rst component is a power of k. end until v 0 = v; end The proof that the algorithm is correct is the following: Proof : The vectors computed are monotonically nondecreasing in each component. Let u be now a k-approximate eigenvector whose rst component is a power of k. We assume that u 1 = k s , where s is a nonnegative integer. We still have v 0 u. In fact, this is true at the beginning of the repeat loop since u is a positive integral vector. Let us suppose that v u in the loop, we have Mv Mu ku. Then d 1 k (Mv) 1 e u 1 = k s and d 1 k (Mv) i e u i for i 2, since u is integer. We get v 0 i u i for i 2, and log k (d 1 k (Mv) 1 e) s. Finally, we have dlog k (d 1 k (Mv) 1 e)e s and v 0 1 k s = u 1 . This proves that v 0 u and that the process stops. Let v be the nal vector computed. We still have Mv kv. This is easily veri ed for all components greater than 1 as in the previous proof.

For the rst component, we successively get, as v = v 0 :

k dlog k (d 1 k (M v) 1 e)e v 1 ; k log k (d 1 k (M v) 1 e) v 1 ; d 1 k (Mv) 1 e v 1 ; 1 k (Mv) 1 v 1 ; (Mv) 1 v 1 :
The last vector computed is also smaller than any other k-approximate eigenvector whose rst component is a power of k. This concludes the proof. 2

5 Link with enumerative sequences of nodes

In this section, we are going to extend Theorem 1 to the case of Kraft equality when, moreover, the enumerative sequence of nodes corresponding to the sequence of leaves has a primitive linear representation.

Let s be an IN-rational series. A linear representation of s is a triple (l; M; c), where l is a nonnegative integral row vector, c is a nonnegative integral column vector, and M is a nonnegative integral matrix, with: 8n 0; s n = lM n c: The triple (l; M; c) corresponds to a representation (G; I; F) of s de ned in such a way that M is the adjacency matrix of G. The linear representation is said to be primitive if M is primitive. Recall that a matrix is primitive if there exists an integer n such that M n > 0. Equivalently, the adjacency matrix of a strongly connected graph G is primitive if the g.c.d of lengths of cycles in G is 1.

Let T be a tree. We de ne the enumerative sequence t of internal nodes by height of the tree T by t = (t n ) n 0 , where t n is the number of internal nodes of T at height n. An internal node is a node which is not a leaf. Let s (resp. t) be the enumerative sequence of leaves (resp. of nodes) by height of a complete k-ary tree. The link between s and t is the following: t(z) = 1 s(z) 1 kz with s(1=k) = 1: We also have s(z) = P(z)=Q(z), where P(z) and Q(z) are polynomials with nonnegative integral coe cients and Q(0) = 1. Therefore the series t associated to s sati es: t(z) = Q(z) P(z)

(1 kz)Q(z) :

As s(1=k) = 1, P(1=k) = Q(1=k). Thus the series s and t have the same poles and especially the same convergence radius 1= > 1=k.

We can now state the following result that we are going to prove:

Theorem 2 Let t(z) = P n 0 t n z n be an IN-rational series such that: t 0 = 1. 8n 1; t n kt n 1 . the convergence radius of t is strictly greater than 1=k (k 2 IN ). t has a primitive linear representation. Then (t n ) n 0 is the enumerative sequence of nodes by height in a k-ary rational tree.

The construction that we give is partly based on a proof by Perrin [START_REF] Marcus | So c systems and encoding data[END_REF]).

Let l; M; c be matrices with nonnegative entries such that (l; M; c) is a linear representation of t, i.e. 8n 0; t n = lM n c:

We denote by 1= the convergence radius of t. As the matrix M has < k as spectral radius and is primitive, the sequence ((M= ) n ) n 1 tends toward a positive matrix N such that (M= )N = N. Thus, the sequence ((M= ) n c) n 1 tends toward a positive vector w = Nc. The vector w is an eigenvector associated to 1 for M= since (M= )Nc = Nc. Since Mw < kw, for all large enough n, we get M M n c < k M n c; and so, we have the inequality 8n n 0 ; M n+1 c < kM n c:

We shall give a construction of paths in the tree beginning at the nodes of height n 0 , the construction of the remaining part of the tree being obvious.

In order to do that, we transform the linear representation of (t n ) n 0 into the one of (t n ) n n 0 . The latter is (l; M; v) with v = M n 0 c since 8n 0; t n+n 0 = lM n (M n 0 c):

is an admissible k-approximate eigenvector of M 0 .

Let us now assume that r 1 i r. We de ne the splitting of q according to the partition (O 1 ; : : :; O m ), where O 1 = O and O i = ; for 2 i m, and v 0 by v 0 q i = 1 for 1 i m:

The vector v 0 is still admissible. 5 th case We suppose that Card(O) = r < k < m.

If r > 1, we de ne the splitting of q according to the partition (O 1 ; O 2 = O n O 1 ), where O 1 contains exactly one edge of O. We number 1; 2; : : :; r the states of J, and we can suppose that state 1 is the ending state of the edge of O 1 . The vector v 0 is de ned by v 0 q 1 = d v 1 k e and v 0 q 2 = v q v 0 q 1 :

We have: v 1 + v 2 + + v r rm (k 1)m; and as v 1 > k(d v 1 k e 1), v 2 + + v r < (k 1)m k(d v 1 k e 1); k(m d v 1 k e) + k m k(m d v 1 k e): This proves that v 0 is again an admissible vector.

If r 1, we then de ne the splitting of q according to the partition (O 1 ; : : :; O m d v 1 k e ), where O 1 contains the only edge of O and O i = ; for 2 i (m d v 1 k e). The vector v 0 de ned by v 0 q 1 = d v 1 k e and v 0 i = 1 for 2 i (m d v 1 k e) is again an admissible vector.

In all cases, the state q is split in states with new values stricly less than the maximal value m. Moreover each state without output edge obtained by state splitting has value 1. This transformation is iterated until all components of the vector v 0 are equal to 1, concluding the proof of Proposition 3. 2

  Fig. 2. Representation (G; i; F)

Fig. 10 .

 10 Fig. 6. Initial normalized representation First step

Fig. 13 .

 13 Fig. 12. Root of value 3 (G)

Franaszek

The vector v is then a k-(lower) approximate eigenvector of the matrix M, since we have Mv kv. Now we shall prove that we can replace the triple (l; M; v) by a triple (l 0 ; M 0 ; v 0 ), which is also a linear representation of (t n ) n n 0 , such that v 0 has all its entries equal to 1, and such that the entries of each row of M 0 are at most k. The construction of this new linear representation basically makes use of the state splitting.

We shall use the following extended notion of state splitting, that we call again a state splitting. Let G = (V; E) be a graph and let q be a vertex of G.

We denote by I (resp. O) be the set of edges coming in q (resp. going out of q). Let (O 1 ; O 2 ; ; O r ) be a partition of O in r parts. Main di erence with the de nition of state splitting in Section 2 is that some parts O i of the partition may be here empty. The operation of (output) state splitting relative to this partition transforms G into the graph G 0 = (V 0 ; E 0 ) where V 0 = (V n fqg) q 1 q 2 : : : q r is obtained from V by splitting state q into r states q 1 ; : : :; q r , and where E 0 is de ned as follows:

1. All edges of E that are not incident to q are left unchanged. 2. All states q i have the same input edges as q.

3. The output edges of q are distributed between q 1 ; : : :; q r according to the partition of O into (O 1 ; O 2 ; : : :; O r ). We denote by U i the set of output edges of q i : U i = f(q i ; x; p) j (q; x; p) 2 O i g. Note that some U i may be empty.

Let us now assume that a k-approximate eigenvector v for the graph G, that is a k-approximate eigenvector of the adjacency matrix of G, exists.

We denote by v p the component of index p of v, if p is a state of G. It is also called the value of state p (before the state splitting). All components v p are positive integers. An admissible vector v 0 for the new graph G 0 is a positive integral vector satisfying the following conditions:

If p is a state distinct from q i then v 0 p = v p . P 1 i r v 0 q i = v q .

The vector v 0 is a k-approximate eigenvector of the adjacency matrix M 0 of the new graph G 0 .

Note the di erence with the de nition of an admissible state splitting given in Section 2.

Finally, let l be the row vector of a linear representation (l; M; v). We transform l into l 0 de ned in the following way: l 0 q 1 = l 0 q 2 = = l 0 qr = l q ; if p 6 = q i l 0 p = l p :

If (l; M; v) is a linear representation of a given series, then (l 0 ; M 0 ; v 0 ) is a representation of the same series.

Proposition 3 Let M be a nonnegative integral matrix whose spectral radius is less than a positive integer k. Let v be a k-(lower) approximate eigenvector for M. If (l; M; v) is the linear representation of an IN-rational series, there is another representation (l 0 ; M 0 ; v 0 ), with matrices having entries in IN, of the same series, such that the sum of the entries of each row of M 0 is at most k, and all components of v 0 are equal to 1.

Note that the matrix M is not necessarily irreducible. We de ne the graph G associated to M 2 IN n n as the n-state graph having M ij edges from i to j.

Proof : (Proposition 3) We may suppose that the matrix M is a 0 1 matrix.

Otherwise, we obtain such a matrix by successive output state splittings of all states having more than one output edges going to a same state.

The method consists in successive output state splittings of the graph G associated to M, in such a way that a new graph G 0 and a new admissible k-approximate eigenvector v 0 are obtained at each step. The inequality Mv kv is then an invariant of the iteration of state splittings.

More precisely, we choose a state q of the graph G such that v q is maximal and has not exactly k outgoing edges all ending in states of maximal value. Such a state of maximal value exists, since otherwise G would admit a subgraph whose states all have k outgoing edges, and the spectral radius of the matrix M would be then greater than or equal to k. We denote by O the set of outgoing edges of q, and we denote by m = v q the maximal value of the components of v. We can assume that m > 1 since otherwise the process immediately stops. We denote by J the ending states of edges of O.

We consider several cases to de ne the state splitting:

1 st case We suppose that there is a non empty and strict subset J 0 of J such that P p2J 0 v p 0 mod k. This is true especially when Card(O) > k (see Section 3).

In this case, we do an output state splitting of q relative to the partition (O 1 ; O 2 ), where O 1 are the edges of O ending in J 0 and O 2 = O n O 1 . The graph G is transformed into a graph G 0 having M 0 as adjacency matrix. We de ne the vector v 0 by v 0 q 1 = 1 k X p2J 0 v p ; v 0 q 2 = v q v 0 q 1 ; and if p 6 = q 1 ; q 2 v 0 p = v p :

The vector v 0 is positive integral vector that satis es the inequality: M 0 v 0 kv 0 : Indeed, setting J 00 = J n J 0 , we get if p 6 = q 1 ; q 2 ; (M 0 v 0 ) p = (Mv) p :

(M 0 v 0 ) q 1 = ( P p2J 0 v 0 p if q = 2 J 0 P p2J 0 nfqg v 0 p + v 0 q 1 + v 0 q 2 if q 2 J 0 = X p2J 0 v p = kv 0 q 1 (M 0 v 0 ) q 2 = ( P p2J 00 v 0 p if q = 2 J 00 P p2J 00 nfqg v 0 p + v 0 q 1 + v 0 q 2 if q 2 J 00 = X p2J 00 v p = X p2J v p X p2J 0 v p kv q kv 0 q 1 kv 0 q 2 : Therefore v 0 is an admissible k-approximate eigenvector.

2 nd case We suppose that Card(O) = k. Then we can also suppose that P p2J v p 0 mod k. Otherwise we would be in the rst case. Since, by hypothesis, q has at least one outgoing edge ending in a state of value strictly less than the maximal value m = v q , we have P p2J v p < km. As the left member of the inequality is a multiple of k, we obtain X p2J v p k(m 1):

(1)

We split state q according to the partition (O 1 = O; O 2 = ;) and de ne a k-approximate eigenvector v 0 by v 0 q 1 = m 1; v 0 q 2 = 1 18

We still have M 0 v 0 kv 0 and v 0 is admissible.

We mention here another possibility of splitting according to a partition of O into two non empty subsets. If J 0 denotes the ending states of edges of O 1 , the admissible vector v 0 is in this case de ned by v 0 q 1 = d 1 k P p2J 0 v p e. The remaining cases are devoted to the case where Card(O) = r < k.

3 rd case We suppose that Card(O) = r < k and r m k.

We split q in q 1 ; q 2 ; : : :; q m according to (O 1 ; O 2 ; : : :; O m ), where O i contains exactly one edge from O, for 1 i r, and O i = ; for r + 1 i m. We de ne a k-approximate eigenvector v 0 by v 0 q i = 1; 1 i m As v 0 p m k for any state p, M 0 v 0 kv 0 and v 0 is admissible. 4 th case We suppose that m < Card(O) = r < k.

We number 1; 2 : : :; r the states of J. Let i be the greatest index such that v 1 + v 2 + + v i < k m; if it does not exist, we set i = 0. Let us rst assume that 0 i < r 1. Then v 1 + v 2 + + v i+1 rm k(m 1):

In fact, otherwise we would have:

We then also get:

As a consequence we de ne the splitting of q according to the partition (O 1 ; O 2 = O n O 1 ), where O 1 is the set of outgoing edges of q ending in states 1 to i + 1. The vector v 0 de ned by v 0 q 1 = 1 and v 0 q 2 = m 1;

We then obtain, by Proposition 3, a new representation (l 0 ; M 0 ; v 0 ) of the sequence (t n ) n n 0 , where the sum of each row of M 0 is at most k (since M 0 v 0 kv 0 ), and all components of v 0 are equal to 1. The sum of the components of l 0 is then t n 0 .

The interpretation of this new representation shows that t is the generating series of internal nodes of a k-ary rational tree, concluding the proof.

Example Let t be the following series: t(z) = (z + z 3 ) (1 + z). We get that M 2 c kMc, so Mc = (2; 1; 2) t is a k approximate eigenvector and after splittings we obtain the tree of the last picture.


Frédérique Bassino
email: bassino@univ-mlv.fr

Julien Clément
email: clementj@univ-mlv.fr

Cyril Nicaud
email: nicaud@univ-mlv.fr

The Standard Factorization of Lyndon Words: an Average Point of View

Keywords: Lyndon word, standard factorization, average-case analysis, analytic combinatorics, success run

A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a twoletter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4.

Introduction

Given a totally ordered alphabet A, a Lyndon word is a word that is strictly smaller, for the lexicographical order, than any of its conjugates (i.e., all words obtained by a circular permutation on the letters). Lyndon words were introduced by Lyndon [START_REF] Lyndon | On Burnside problem I[END_REF] under the name of "standard lexicographic sequences" in order to give a base for the free Lie algebra over A; the standard factorization plays a central role in this framework (see [START_REF] Lothaire | Encyclopedia of mathematics and its applications[END_REF], [START_REF] Reutenauer | Free Lie algebras[END_REF], [START_REF] Ruskey | Generating Lyndon brackets: a basis for the n-th homogeneous component of the free Lie algebra[END_REF]). More precisely to a Lyndon word w is associated a binary tree T (w) recursively built in the following way: if w is a letter, then T (w) is a leaf labeled by w, otherwise T (w) is an internal node having T (u) and T (v) as children where u • v is the standard factorization of w. This structure encodes a nonassociative operation, either a commutator in the free group [START_REF] Chen | Free differential calculus IV: The quotient groups of the lower central series[END_REF], or a Lie bracketing [START_REF] Lothaire | Encyclopedia of mathematics and its applications[END_REF]; both constructions lead to bases of the free Lie algebra. The average complexity of the algorithms computing these bases is basically determined by the average height of these trees.

One of the basic properties of the set of Lyndon words is that every word is uniquely factorizable as a non increasing product of Lyndon words. As there exists a bijection between Lyndon words over an alphabet of cardinality k and irreducible polynomials over F k [START_REF] Golomb | Irreducible polynomials, synchronizing codes, primitive necklaces and cyclotomic algebra[END_REF], lots of results are known about this factorization: the average number of factors, the average length of the longest factor [START_REF] Flajolet | The complete analysis of a polynomial factorization algorithm over finite fields[END_REF] and of the shortest [START_REF] Panario | Smallest components in decomposable structures: exp-log class[END_REF].

Several algorithms deal with Lyndon words. Duval gives in [START_REF] Duval | Factorizing words over an ordered alphabet[END_REF] an algorithm that computes, in linear time, the factorization of a word into Lyndon words. There exists [START_REF] Fredricksen | Necklaces of beads in k colors and k-ary de Bruijn sequences[END_REF] an algorithm generating all Lyndon words up to a given length in lexicographical order. This algorithm runs in a constant average time (see [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF]).

In Section 2, we define more formally Lyndon words and give some enumerative properties of these sets of words. Then we introduce the standard factorization of a Lyndon word w which is the unique couple of Lyndon words u, v such that w = uv and v is of maximal length.

In Section 3, we study the set of Lyndon words having a given right factor in their standard factorization and prove that it is a regular language. We also compute its associated generating function. But as the set of Lyndon words is not context-free [START_REF] Berstel | The set of lyndon words is not context-free[END_REF], we are not able to directly derive asymptotic properties from these generating functions. The results of this section had been announced in [START_REF] Bassino | Lyndon words with a fixed standard right factor[END_REF].

In Section 4 we use probabilistic techniques and results from analytic combinatorics (see [START_REF] Flajolet | Analytic combinatorics-symbolic combinatorics[END_REF]) in order to compute the average length of the factors of the standard factorization of Lyndon words over a two-letter alphabet.

Section 5 is devoted to algorithms and experimental results. We give an algorithm to randomly generate a Lyndon word of a given length and another one related to the standard factorization of a Lyndon word. Finally experiments are given which confirm our results and give hints of further studies.

An extended abstract of a preliminary version of this work has been presented in [START_REF] Bassino | The average lengths of the factors of the standard factorization of Lyndon words[END_REF].

Preliminary

We denote A * the free monoid over the totally ordered alphabet A = {a 1 < a 2 < • • • < a q } obtained by all finite concatenations of elements of A. The length |w| of a word w is the number of the letters w is product of. We consider the lexicographical order < over all non-empty words of A * defined by the extension of the order over A.

We record two properties of this order (i) For any word w of A * , u < v if and only if wu < wv. (ii) Let x, y ∈ A * be two words such that x < y. If x is not a prefix of y then for every x ′ , y ′ ∈ A * we have xx ′ < yy ′ .

By definition, a Lyndon word is a primitive word (i.e, it is not a power of another word) that is minimal, for the lexicographical order, in its conjugate class (i.e, the set of all words obtained by a circular permutation). The set of

w = uv with u, v ∈ L, u < v.
Theorem 2 (Lyndon) Any word w ∈ A + can be written uniquely as a nonincreasing product of Lyndon words:

w = ℓ 1 ℓ 2 . . . ℓ n , ℓ i ∈ L, ℓ 1 ≥ ℓ 2 ≥ • • • ≥ ℓ n .
Moreover, ℓ n is the smallest suffix of w.

The number Card(L n ) of Lyndon words of length n over A (see [START_REF] Lothaire | Encyclopedia of mathematics and its applications[END_REF]) is

Card(L n ) = 1 n d|n µ(d) Card(A) n/d ,
where µ is the Moebius function defined on N \ {0} by µ(1) = 1, µ(n) = (-1) i if n is the product of i distinct primes and µ(n) = 0 otherwise.

When Card(A) = 2, we obtain the following estimate

Card(L n ) = 2 n n 1 + O 2 -n/2 . (1)
For w ∈ L \ A a Lyndon word consisting of more than a single letter, the pair (u, v), u, v ∈ L such that w = uv and v of maximal length is called the standard factorization. The words u and v are called the left factor and right factor of the standard factorization.

Equivalently, the right factor v of the standard factorization of a Lyndon word w of length greater than 1 can be defined as the smallest proper suffix of w.

Example 3 For instance, with a binary alphabet A = {a, b}, we have the following standard factorizations:

aaabaab = aaab • aab, aaababb = a • aababb, aabaabb = aab • aabb.
3 Counting Lyndon words with a given right factor

In this section, we prove that the set of Lyndon words with a given right factor in their standard factorization is a regular language and compute its generating function. The techniques used in the following basically come from combinatorics on words.

Let A = {a 1 < • • • < a q = γ} where γ denotes the greatest symbol of the q-ary ordered alphabet A. Let w be a word of A * \ {γ} * , the successor S(w) of w = uαγ i , where α is a symbol of A\{γ} and i ≥ 0, is defined by S(w) = uβ with β the immediate next symbol after α in A. For any Lyndon word v, we define the set of words

X γ = {γ} and X v = {v, S(v), S 2 (v), . . . , S k-1 (v) = γ} if v = γ.
Note that k = 1 + q × |v| -q i=1 i × |v| i where q is the cardinality of the alphabet A, |v| is the length of v and |v| i is the number of occurrences of the ith letter of the alphabet A in v.

Example 4 (1) for A = {a, b}, v = aabab: X aabab = {aabab, aabb, ab, b}.

(2) for A = {a, b, c}, v = abb: X abb = {abb, abc, ac, b, c}.

By construction, v is the smallest element of X v A * for the lexicographical order.

Lemma 5 Let v be a Lyndon word, then every word of X v is a Lyndon word.

PROOF. First of all, if v = γ, then X v = {γ}.
Next we shall prove that for any Lyndon word v = γ, S(v) is still a Lyndon word.

If v ∈ A \ {γ}, then S(v) is a letter and, so, is a Lyndon word. Now let v be a Lyndon word of length greater than 1. Then v can uniquely be written as v = uαγ i where i ≥ 0 and α ∈ A \ {γ}, so that S(v) = uS(α). If S(v) is not a Lyndon word, there exists a decomposition u = x 1 x 2 with x 1 = ε such that x 2 S(α)x 1 ≤ x 1 x 2 S(α). So x 2 α is not a prefix of x 1 x 2 and x 2 α < x 1 x 2 . Thus we get x 2 αγ i x 1 < x 1 x 2 αγ i = v. This is impossible since v ∈ L, proving that S(v) is a Lyndon word. 2

A code C over A * is a set of non-empty words such that any word w of A * can be written in at most one way as a product of elements of C. A set of words is prefix if none of its elements is the prefix of another one. Such a set is a code, called a prefix code. A submonoid M of A * is called pure if, for all w ∈ A * and all n ≥ 1,

w n ∈ M ⇒ w ∈ M.
For a general reference about codes, see [START_REF] Berstel | Theory of codes[END_REF].

Proposition 6 Let v be a Lyndon word, then the set X v is a prefix code and the submonoid X * v is pure.

PROOF. If x, y ∈ X v with |x| < |y|, then, by construction of X v , x > y. So x is not a prefix of y and X v is a prefix code.

Moreover, for every n ≥ 1, if w is a word such that w n ∈ X * v then w ∈ X * v . Indeed if w / ∈ X * v , then either w is a proper prefix of a word of X v or w has a prefix in X * v . If w is a proper prefix of a word of X v , it is a prefix of v and it is strictly smaller than any word of X v . As w n ∈ X * v , w or one of its prefixes is a suffix of a word of X v . But all elements of X v are Lyndon words greater than v, so their suffixes are strictly greater than v and w can not be a prefix of a word of X v . Now if w = w 1 w 2 where w 1 is the longest prefix of w in X + v , then w 2 is a non-empty prefix of a word X v , so w 2 is strictly smaller than any word of X v . As w n ∈ X * v , w 2 or one of its prefix is a suffix of a word of X v , but all elements of X v are Lyndon words greater than v, so their suffixes are strictly greater than v and w can not have a prefix in X + v .

As a conclusion, since for every n ≥ 1, if w n ∈ X * v then w ∈ X * v , the submonoid X * v is pure. 2

Proposition 7 Let ℓ and v be Lyndon words, then ℓ ≥ v if and only if ℓ ∈ X + v .

PROOF. If ℓ ≥ v, let ℓ 1 be the longest prefix of ℓ which belongs to X * v , and ℓ 2 such that ℓ = ℓ 1 ℓ 2 . If ℓ 2 = ε, we have the inequality

ℓ 2 ℓ 1 > ℓ ≥ v, thus ℓ 2 ℓ 1 > v. The word v is not a prefix of ℓ 2 since ℓ 2 has no prefix in X v , hence we have ℓ 2 = ℓ ′ 2 βℓ ′′ 2 and v = ℓ ′ 2 αv ′′ with α, β ∈ A and α < β. Then, by construction of X v , ℓ ′ 2 β ∈ X v which is impossible. Thus ℓ 2 = ε and ℓ ∈ X + v . Conversely, if ℓ ∈ X + v ,
if u ∈ (A ≤α X * v ) \ X + v .
Hence the set F v of Lyndon words having v as right standard factor is a regular language.

PROOF. Let v be a Lyndon word whose first letter is α and u ∈ A * . Assume that uv is a Lyndon word, then uv < v and so u = α ′ w with α ′ ∈ A ≤α . Now let u • v be the standard factorization of uv. By Theorem 2, wv can be written uniquely as

wv = ℓ 1 ℓ 2 . . . ℓ n , ℓ i ∈ L, ℓ 1 ≥ ℓ 2 ≥ • • • ≥ ℓ n .
As v is the smallest (for the lexicographical order) suffix of uv, and consequently of wv, we get

ℓ n = v; if w = ε, then n = 1, else n ≥ 2 and for 1 ≤ i ≤ n -1, ℓ i ≥ v. Thus, w ∈ X * v and u ∈ A ≤α X * v . Moreover if u ∈ X + v , then u ≥ v which is impossible since uv is a Lyndon word. Conversely, if u ∈ (A ≤α X * v ) \ X + v , then u = α ′ w with α ′ ∈ A ≤α and w = x 1 x 2 . . . x n with x i ∈ X v .
From Proposition 1, the product ℓℓ ′ of two Lyndon words such that ℓ < ℓ ′ is a Lyndon word. Replacing as much as possible x i x i+1 by their product when x i < x i+1 , w can be rewritten as

w = y 1 y 2 . . . y m , y i ∈ X + v ∩ L, y 1 ≥ y 2 ≥ • • • ≥ y m . As u / ∈ X + v , for any integer 1 ≤ i ≤ m, one has α ′ y 1 . . . y i / ∈ X + v .
Now we prove by induction that u is a Lyndon word. As y

1 ∈ L ∩ X v and α ′ < y 1 , α ′ y 1 ∈ L. Suppose that α ′ y 1 . . . y i ∈ L. Then, as y i+1 ∈ L ∩ X + v , and α ′ y 1 . . . y i ∈ L \ X + v , from Proposition 7, we get α ′ y 1 . . . y i < v ≤ y i+1 . Hence α ′ y 1 . . . y i+1 ∈ L. So, u is a Lyndon word. As u ∈ L \ X + v , u < v and uv ∈ L. Setting v = y m+1 , we have wv = y 1 y 2 . . . y m y m+1 , y i ∈ X * v ∩ L, y 1 ≥ y 2 ≥ . . . ≥ y m+1 .
Moreover any proper suffix s of uv is a suffix of wv and can be written as s = y ′ i y i+1 . . . y m+1 where y ′ i is a suffix of y i . As

y i ∈ L, y ′ i ≥ y i . As y i ∈ X + v , y i ≥ v and thus s ≥ v.
Thus, v is the smallest suffix of uv and u • v is the standard factorization of the Lyndon word uv.

Finally as the set of regular languages is closed by complementation, concatenation and Kleene star operation, for any Lyndon word v, the set F v of Lyndon words having v right standard factor is a regular language. 2

We define the generating functions

X v (z) of X v and X * v (z) of X * v : X v (z) = w∈Xv z |w| and X * v (z) = w∈X * v z |w| .
As the set X v is a code, the elements of X * v are sequences of elements of X v (see [START_REF] Flajolet | Analytic combinatorics-symbolic combinatorics[END_REF]):

X * v (z) = 1 1 -X v (z)
.

Denote by F v (z) = x∈Fv z |x| the generating function of the set

F v = {uv ∈ L | u • v is the standard factorization}.
Theorem 9 Let v be a Lyndon word over a q-ary alphabet. The generating function of the set F v of Lyndon words having a right standard factor v can be written

F v (z) = z |v| 1 + qz -1 1 -X v (z)
.

PROOF. First of all, let a 1 be the smallest, in the lexicographical order, letter of the alphabet A. Then any Lyndon word of A * which is not a letter ends with a letter greater than a 1 , so F a 1 (z) = 0. And as X a 1 = A, the formula given for F v (z) holds for v = a 1 .

Assume that v = a 1 and denote α the first letter of v. From Theorem 8, F v (z) can be written as

F v (z) = z |v| u∈A ≤α X * v \X + v z |u| .
In order to transform this combinatorial description involving A ≤α X * v \ X + v into an enumerative formula for the generating function F v (z), we prove that

A ≤α X * v ∩ X + v = (X v \ A >α ) X * v with A >α = {a ∈ A | a > α}.
By construction all words of X v begin with a letter greater than or equal to α, thus

A ≤α X * v ∩ X + v ⊂ (X v \ A >α ) X * v . If u ∈ (X v \ A >α ) X * v , then u = αu ′
is greater than or equal to v and as u is a Lyndon word, its proper suffixes are strictly greater than v; consequently, writing u ′ as a non-increasing sequence of Lyndon word ℓ 1 , . . . , ℓ m , we get, since ℓ m > v, that for all i, ℓ i is greater than v. Consequently from Proposition 7, for all i, ℓ i ∈ X * v and as a product of elements of

X + v , u ′ ∈ X + v . Therefore (X v \ A >α ) X * v ⊂ A ≤α X * v .
Consequently the generating function of the set F v of Lyndon words having v as right factor satisfies

F v (z) = z |v|   u∈A ≤α X * v z |u| - (Xv\A>α)X * v z |u|   = z |v| Card(A ≤α )z 1 -X v (z) - X v (z) -Card(A >α )z 1 -X v (z)
and finally the announced equality. 2

Note that the function F v (z) is rational for any Lyndon word v. But the right standard factor runs over the set of Lyndon words which is not context-free [START_REF] Berstel | The set of lyndon words is not context-free[END_REF]. Therefore in order to study the average length of the factors in the standard factorization of Lyndon words, we adopt another point of view. Moreover, for the sake of clarity we focus on the case of a binary alphabet.

Main result

In this section, the alphabet A consists of two letters {a, b}.

Making use of probabilistic techniques and results from analytic combinatorics (see [START_REF] Flajolet | Analytic combinatorics-symbolic combinatorics[END_REF]), we establish the following result.

Theorem 10 Under the uniform distribution over the binary Lyndon words of length n, the average length of the right factor of the standard factorization is

3n 4 1 + O log 3 n n .
Remark 11 The error term comes from successive approximations at different steps of the proof and, for this reason, it is probably overestimated (see experimental results in Section 5).

First we partition the set L n in the two following subsets: aL n-1 and L n \aL n-1 .

Note that aL

n-1 ⊂ L n , that is, if w is a Lyndon word then aw is also a Lyndon word. Moreover if w ∈ aL n-1 , the standard factorization is w = a • v with v ∈ L n-1 .
As, from Equation (1) on page 4,

Card (L n-1 ) = 2 n-1 n -1 1 + O 2 -n/2 ,
the contribution of the set aL n-1 to the mean value of the length of the right factor is

(n -1) × Card (aL n-1 ) Card (L n ) = n 2 1 + O 2 -n/2 .
The remaining part of this paper is devoted to the standard factorization of the words of L n \ aL n-1 which requires a careful analysis.

Proposition 12 The contribution of the set L n \ aL n-1 to the mean value of the length of right factor is

n 4 1 + O log 3 n n .
This proposition basically asserts that in average for the uniform distribution over L n \ aL n-1 , the length of the right factor is asymptotically n/2.

The idea is to build a transformation ϕ, which is an involution on almost all the set L n \ aL n-1 , such that the sum of the lengths of standard right factors of w and ϕ(w) is about the length |w| of w. The word ϕ(w) is obtained from w by exchanging particular suffixes of the factors of the standard factorization of w so that standard factors of w and ϕ(w) have the same prefixes.

Max-run decomposition of words of L \ aL

For any Lyndon word w of length greater than 1, there exists a positive integer k = k(w) such that a k b is a prefix of w. It is also the length of the longest runs of a's in w. Let R k be the set of Lyndon words with a first run of length k. We partition each set R k \ aR k-1 in two sets R ′ k corresponding to words with a unique occurrence of a k b and R ′′ k containing words with at least two longest runs of length k.

Denote by

X k the set X a k-1 b namely X k = {a i b | 0 ≤ i ≤ k -1}, then we can write R ′ k = a k bX * k-1 (a k-1 bX * k-1 ) + ∩ (L \ aL), R ′′ k = a k bX * k (a k bX * k ) + ∩ (L \ aL).
Note that the standard factorization of a word w of R k \ aR k-1 can only be one of the following

w = a k bu • a k-1 bv when w ∈ R ′ k w = a k bu • a k bv when w ∈ R ′′ k .
This means that the right factor of a Lyndon word w begins with a k-1 b or a k b.

We define the integer K to be

K = k -1 when w ∈ R ′ k and K = k when w ∈ R ′′ k . Then K is the length of the first run of a's of the right factor of w ∈ R k \ aR k-1 .
With these notations, we introduce a decomposition of words of L \ aL called max-run decomposition throughout this paper.

Definition 13 (max-run decomposition) Let w be a word of L \ aL. Denoting by k the length of the longest runs of a's in w and defining K as k -1 when w contains only one longest run of a's and k otherwise, the max-run decomposition of w is

w = f 1 . . . f m with f 1 ∈ a k bX * K and for, 2 ≤ i ≤ m, f i ∈ a K bX * K .
The standard factorization always occurs at a point of the max-run decomposition: there exists j ∈ {2, . . . , m} such that the standard factorization of w is

j-1 i=1 f i • m i=j f i .
Example 14 For instance, when k = 2, -The Lyndon word aababab is in R ′ k , K = 1, its standard factorization is aabab • ab and its max-run decomposition is aab • ab • ab.

-The Lyndon word aababaabbaabbb is in R ′′ k , K = 2, its standard factorization is aabab • aabbaabbb and its max-run decomposition is aabab•aabb•aabbb.

We will study this decomposition by means of analytical tools and present now definitions and results which play a central role hereafter. Let X k (z) and X * k (z) be the generating functions respectively associated to X k and X * k (z) namely

X k (z) = k i=1 z i and X * k (z) = 1 1 -X k (z)
.

The smallest pole of X * k (z) that is, from the Rouché theorem (see [START_REF] Cartan | Théorie élémentaire des fonctions analytiques d'une ou plusieurs variables complexes[END_REF]), the only one in the unit disc is

ρ k = 1 2 + ǫ k , with ǫ k = 1 2 k+2 + k + 1 2 2k+3 + O k 2 2 3k .
The value of ǫ k is obtained by the bootstrapping method as in [START_REF] Knuth | The average time for carry propagation[END_REF] using the fact that ρ k is a root of 1 -2z + z k+1 .

Denoting by [z n ]F (z) the coefficient of z n in F (z) and using the standard extraction formula for rational series with a simple pole (see [START_REF] Flajolet | Analytic combinatorics-symbolic combinatorics[END_REF]), we can write

[z n ] P (z) 1 -X k (z) = P (ρ k ) X ′ k (ρ k ) ρ -(n+1) k + O(1) (2)
provided that ρ k is not a root of the polynomial P (z). Therefore we also need the following estimate of the derivative

X ′ k of X k at z = ρ k (X ′ k (ρ k )) -1 = 1 4 1 -4ǫ 2 k 1 -2kǫ k = 1 4 1 + k 2 k+1 + O k 2 2 2k . (3)
In the following, subsets of Lyndon words will be enumerated by means of the elegant construction of primitive cycles [START_REF] Flajolet | The cycle construction[END_REF].

Proposition 15 (Primitive cycles) Let C be a code, with generating function C(z) = w∈C z |w| . Then the generating function of the primitive cycles of

elements of C is m≥1 µ(m) m log 1 1 -C(z m )
.

This equation can be used directly to obtain several interesting generating functions of sets of words (i) the set of Lyndon words taking C = {a, b}, C(z) = 2z.

(ii) the set of Lyndon words beginning with strictly less than k a's taking C = X k , C(z) = X k (z). (iii) the set of Lyndon words beginning with exactly k a's taking

C = a k b(X k ) * , C(z) = z k+1 1-X k (z) .

Length k of longest runs.

First we study the precise distribution of the length of the longest runs of a's in a Lyndon word w. This question is strongly related to the notion of success run in probability theory [START_REF] Feller | An introduction to Probability Theory and Its Applications[END_REF] Proposition 16 The probability p n,k that a i b, with 1 ≤ i < k, is a prefix of a Lyndon word of length n is

p n,k = (1 + 2ǫ k ) -n + O 2 -n/2 with ǫ k = 1 2 k+2 + k + 1 2 2k+3 + O k 2 2 3k .
PROOF. Denote R <k the set of Lyndon words beginning with strictly less than k a's

R <k = {w ∈ L | w ≥ a k-1 b}.
The number of words of length n in R <k is the number of primitive cycles of elements in X k of total length n. From Proposition 15, we get

R <k (z) = m≥1 µ(m) m log 1 1 -X k (z m ) ,
where µ is the Moebius function. We set R <k (z) = n≥1 ℓ n,k z n . Then, differentiating with respect to z, we obtain

n≥1 nℓ n,k z n-1 = m≥1 µ(m) X ′ k (z m ) 1 -X k (z m ) z m-1 .
Hence we have

nℓ n,k = m|n µ n m [z m ] X ′ k (z) 1 -X k (z) z.
Introducing ρ k and using Equation (2), we get

ℓ n,k = 1 n m|n µ n m ρ -m k + O(1) .
Moreover as the number of divisors (see [START_REF] Hardy | An Introduction to the Number Theory[END_REF]) of n is O(n δ ) for any positive δ, we can write for any positive δ < 1

ℓ n,k = 1 n m|n µ n m ρ -m k + O n δ-1 .
Finally replacing ρ k by 1/2 + ǫ k , we obtain

ℓ n,k = 2 n n (1 + 2ǫ k ) -n + O 2 n/2 n .
Making use of the following equalities

p n,k = ℓ n,k Card(L n ) and Card(L n ) = 2 n n 1 + O 2 -n/2 ,
we get the announced result. 2

The next result gives an interval to which belongs almost surely the length of the longest runs of a's in a Lyndon word. In this way we restrict our combinatorial model over Lyndon words, leaving apart only a negligible portion of them.

Lemma 17

The length k of the longest runs of a's in a word w ∈ L n satisfies

Pr{k(w) ∈ [log 2 n -log 2 log 2 n -1, 2 log 2 n[} = 1 -O 1 n . ( 4
)
PROOF. From Proposition 16, one has for the length k(w) of the longest run of a's in a word w of L n Pr{k(w)

< k} = (1 + 2ǫ k ) -n + O 2 -n/2 . ( 5
)
The inequality log(1 + x) > x log 2 is true for 0 < x < 1 gives after simple algebra the result that is the value of k for which Pr{k(w

) < k} ≤ 1 n , namely k = log 2 n -log 2 log 2 n -1.
Again, in Equation ( 5), the inequality log(1 + x) < x (true for all x) and the estimation 2ǫ

k = 2 -(k+1) 1 + O k2 -k give the values of k for which Pr{k(w) < k} ≤ 1 - 1 n , namely k = 2 log 2 n. 2
Remark 18 As Card(L n \ aL n-1 ) ∼ 1 2 Card(L n ), using Lemma 17, we obtain that the length k of the longest runs of a's in a word w ∈ L n \ aL n-1 also satisfies the property stated in Equation [START_REF] Berstel | Theory of codes[END_REF].

In what follows I n denotes the interval [log 2 nlog 2 log 2 n -1, 2 log 2 n[.

Number of factors of the max-run decomposition.

Now we establish a bound on the number of factors in the max-run decomposition. PROOF. Denote R ′ k,≥m the set of words of R ′ k with more than m runs of a's of length k -1 and R ′′ k,≥m the set of words of R ′′ k with more than m runs of a's of length k. We want to estimate the ratio

k∈In Card((R ′ k,≥m 0 ∪ R ′′ k,≥m 0 ) ∩ A n ) k∈In Card((R ′ k ∪ R ′′ k ) ∩ A n ) for m 0 = 2 log 2 n. First of all (R ′ k ∪ R ′′ k ) ∩ A n is the set of Lyndon words of L n \ aL n-1 beginning with a longest run of a's of length k. From Card(L n \ aL n-1 ) = 2 n-1 n (1 + O( 1 n )) and Lemma 17, we get k∈In Card((R ′ k ∪ R ′′ k ) ∩ A n ) = 2 n-1 n 1 + O 1 n . (6)
In order to estimate the remaining part of the ratio, we introduce the set W k,m of words beginning by a longest run of a's of length k and containing at least m longest runs of a's

W k,m = a k b(X * k a k b) m-1 X * k+1 .
Then, denoting W k,m (z) the generating function of

W k,m , Card((R ′ k+1,≥m ∪ R ′′ k,≥m ) ∩ A n ) ≤ [z n ]W k,m (z). Indeed we have (R ′′ k,≥m ∩A n ) ⊂ (W k,m ∩L n ) and R ′ k+1,≥m ∩ A n ⊂ a(W k,m ∩A n-1 )\aL n-1 . Moreover Card((W k,m ∩ A n-1 ) \ L n-1 ) ≤ Card((W k,m ∩ A n ) \ L n ),
since by adding a b just after the first occurrence of a k b we define an injection from the first set on the second one. Thus, setting

I n = [k 1 , k 2 [, we obtain k∈In Card((R ′ k,≥m ∪ R ′′ k,≥m ) ∩ A n ) ≤ k 2 k=k 1 -1 [z n ]W k,m (z).
Moreover considering the ambiguous language (a k bX * k+1 ) m , we get the following bound

[z n ]W k,m (z) ≤ [z n ] z k+1 1 -X k+1 (z) m . ( 7
)
Since we shall consider m = 2 log 2 n, here we can not use directly a formula like in (2) to extract coefficients for this rational function. So using the saddle point method, we establish a bound for its coefficients.

Lemma 20 Let F (z) be analytic function such that F (1) = 1 and F ′ (1) = 0, and

G(z) = (1 -F (z)) -m . When m = O(log n) there exists c < 1 such that for n large enough [z n ] 1 (1 -F (z)) m ≤ (1 + c) en mF ′ (1) m .
PROOF. Using the saddle point bound [START_REF] De Bruijn | Asymptotic Method in Analysis[END_REF][START_REF] Odlyzko | Handbook of Combinatorics[END_REF] on the function

1 (1-F (z)) m yields that [z n ] 1 (1 -F (z)) m ≤ 1 (1 -F (ξ(n))) m (ξ(n)) -n ( 8
)
where ξ is the unique positive solution in ]0, 1[ of the equation

ξ G ′ (ξ) G(ξ) = n.
The last equation is equivalent to

ξ F ′ (ξ) 1 -F (ξ) = n m .
Thus replacing in [START_REF] De Bruijn | Asymptotic Method in Analysis[END_REF] gives

[z n ] 1 (1 -F (z)) m ≤ ξn mF ′ (ξ) m 1 ξ n .
Setting ξ = 1 -x and studying Taylor coefficients of F (1 -x), we obtain

x = m n (1 + o(1)).
Using the standard estimate (1 -x) n ∼ e -nx , one can write for all c > 0 and n large enough

[z n ] 1 (1 -F (z)) m ≤ (1 + c) ne mF ′ (1) m ,
concluding the proof of the lemma. 2 Since ρ k+1 is the smallest root of X k+1 (z) -1 and

[z n ] z k+1 1 -X k+1 (z) m = 1 ρ n-m(k+1) k+1 [z n-m(k+1) ] 1 (1 -X k+1 (ρ k+1 z)) m
applying Lemma 20 and using inequality [START_REF] Chen | Free differential calculus IV: The quotient groups of the lower central series[END_REF] one has for c > 0 and m = O(log n)

[z n ]W k,m (z) ≤ (1 + c) 1 ρ n k+1 neρ k+1 k+1 mX ′ k+1 (ρ k+1 ) m .
Denoting by b k the last quantity, we get

k 2 k=k 1 -1 [z n ]W k,m (z) ≤ k 2 k=k 1 -1 b k . Since ρ k+1 k+1 = 2 -(k+1) (1 + O(k2 -k
)) and by Equation 3, we have

neρ k+1 k+1 mX ′ k+1 (ρ k+1 ) m = ne 2 k+3 m m 1 + O mk 2 k . Moreover for k ∈ I n , ρ -n k = 2 n (1 + 2 -(k+1) + O(k2 -2k )) n = 2 n e -n/2 k+1 1 + O nk 2 2k . (9)
This entails for k = O(log n) and m = O(log n),

b k = (1 + c) 2 n e -n/2 k+2 ne 2 k+3 m m 1 + O log 3 n n .
When n and m are fixed, b k is maximal for k = log 2 (n/m) -2 and is equal to

O(2 n-m ). So for m 0 = 2 log 2 n, k∈In Card((R ′ k,≥m 0 ∪ R ′′ k,≥m 0 ) ∩ A n ) ≤ k 2 k=k 1 -1 b k = O 2 n n 2 log n .
Finally using (6), we obtain

k∈In Card (R ′ k,≥m 0 ∪ R ′′ k,≥m 0 ) ∩ A n k∈In Card((R ′ k ∪ R ′′ k ) ∩ A n ) = O log n n ,
concluding the proof. 2

Nature of the factors of the max-run decomposition.

Our goal in the following is to distinguish for the lexicographical order the factors of the max-run decomposition (see Definition 13 on page 10). Recall that any word of w ∈ L\aL can be written w = f 1 . . . f m where f 1 = a k(w) bw 1 , f i = a K bw i for i > 1, w i ∈ X * K for all i and K = k(w) or k(w) -1. The w i are called the interleaving words. We first prove that all interleaving words are of length at least K.

We introduce the set P K of words w ∈ X * K such that denoting by

w[i] the i-th letter of w K ≤ |w| ≤ 2K -1 and ∀i ∈ {K, . . . , |w| -1}, w[i] = a.
For example for K = 3, we have X 3 = {b, ab, aab} and the set P 3 is P 3 = {baab, abaab, bbaab, bab, abab, bbab, bbb, abb, aab}.

The following formula stresses the role of the last word of X K in the factorization of words of

P K P K = ∪ K-2 j=0 A j b a K-1 b ∪ ∪ K-2 j=1 A j b a K-2 b ∪ • • • ∪ ∪ K-2 j=K-2 A j b ab ∪ A K-1 b.
Usual translation to generating functions entails

P K (z) = K j=2 z j+1   K-2 i=K-j (2z) i   + z(2z) K-1 = z(2z) K-1 z K+1 + 4 z 2 ( 1 2 ) K+1 -4 z ( 1 2 ) K+1 (2 z -1) (z -1) - z z -1 + 1 .
The closed form of this formula is not as important as the fact that

for x = O 1 2 K , P K 1 2 + x = 1 + O(Kx) and P ′ k 1 2 + x = O(K). (10)
Lemma 21 Let w be a Lyndon word of L n \ aL n-1 with k(w) ∈ I n . In its max-run decomposition, all interleaving words are of length at least K with probability

1 -O log 2 n n .
PROOF. We distinguish two cases depending on the values of K, namely k and k -1. More precisely we prove that all longest runs a k b in Lyndon words of length n are followed by words of P k with high probability. If the longest run a k b is unique then all runs of a k-1 b are also followed by words of P k-1 with high probability.

We consider the code C = a k bP k X * k and the set C ↔ k of primitive cycles over the code C, i.e. the set of Lyndon words beginning with k a's and such that all occurences of a k b are followed by words of P k . Applying Proposition 15 with C(z) = z k+1 P k (z)

1-X k (z) yields the generating function of

C ↔ k C ↔ k (z) = m≥1 µ(m) m log 1 -X k (z m ) 1 -X k (z m ) -z m(k+1) P k (z m )
.

Moreover, let w = aw ′ be a word with a unique longest run of length k, all possible occurences of a b in w ′ must be separated by words of P k-1 . So instead of C ↔ k we are bound to study the set

D ↔ k = C ↔ k \ a k bP k X * k ∪ a k bP k-1 X * k-1 a k-1 bP k-1 X k-1 * .
Its generating function can be written

D ↔ k (z) = C ↔ k (z)-∆ k (z) with ∆ k (z) = z k+1 P k (z) 1 -X k (z) - z k+1 P k-1 (z) 1 -X k-1 (z) -z k P k-1 (z)
.

We shall compare the cardinality of the set

L ↔ n = ∪ k∈In (D ↔ k ∩ A n ) namely Card(L ↔ n ) = k∈In [z n ]D ↔ k (z)
with the number of Lyndon words of length n. Let ̺ k be the smallest root of 1 -X k-1 (z) -z k P k-1 (z). We can prove as in Section 4.1 that ̺ k is simple and belongs to [1/2, 1[. Using the bootstrapping method and the estimates (10) of P k and P ′ k , we obtain

̺ k = 1 2 + 1 2 k+2 + O k 2 2k = ρ k + O k 2 2k . ( 11
) Let c ↔ n,k = [z n ]C ↔ k (z). By usual coefficient extraction we have c ↔ n,k = 1 n 1 ̺ n k+1 - 1 ρ n k + O 2 n/2 n .
¿From Equations ( 9) and ( 11) we get

k∈In c ↔ n,k = 2 n n e -n/2 k 2 +2 -e -n/2 k 1 +1 + 2 n n k∈In e -n/2 k+2 O nk 2 2k .
By definition of I n ,

e -n/2 k 2 +2 -e -n/2 k 1 +1 = 1 + O(1/n) . Moreover as n 2 k 2 exp(-n 2 k+2
) is uniformly bounded for k > 0, we obtain

k∈In c ↔ n,k = 2 n n 1 + O log 2 n n . (12)
On the other hand, using again coefficient extraction of rational functions and using Equations ( 3), ( 9), [START_REF] Flajolet | The complete analysis of a polynomial factorization algorithm over finite fields[END_REF] and we have

[z n ] z k+1 P k-1 (z) 1 -X k-1 (z) -z k P k-1 (z) = ̺ k+1 k P k-1 (̺ k ) ̺ -(n+1) k X ′ k-1 (̺ k ) + (k + 1)̺ k k P k (̺ k ) + ̺ k+1 k P ′ k-1 (̺ k ) + O(1) [z n ] z k+1 P k (z) 1 -X k (z) = ρ k+1 k P k (ρ k ) X ′ k (ρ k ) 1 ρ n+1 k + O(1). As X ′ k (z) = X ′ k-1 (z) + (k + 1)
z k , we get by Equations ( 9) and ( 11)

[z n ]∆ k (z) = 2 n 1 2 k+1 e -n/2 k+2 O nk 2 2k .
Again as n

2 k 3 exp(-n 2 k+2
) is uniformly bounded for k > 0, we obtain

k∈In [z n ]∆ k (z) = O 2 n log 2 n n 2 .
Consequently using Equation ( 12), we get Card(L

↔ n ) = 2 n n 1 + O log 2 n n and Card(L n ) Card(L ↔ n ) = 1 + O log 2 n n .
Thus almost all Lyndon words of length n belong to L ↔ n .

Finally, since Card(L n \ aL n-1 ) ∼ 1 2 Card(L n ), the property on the length of the interleaving words also holds on L n \ aL n-1 with an error term of the same order. 2

To compare the lexicographical order of two factors beginning with a longest run of a's of length K, it remains to distinguish at most m = 2 log 2 n interleaving words of P K X * K . PROOF. From Lemma 21, interleaving words are longer than K with probability 1 -O(log 2 n/n). Thus we focus on the subsets Q ↔ n,K of L n \ aL n-1 of Lyndon words with a max-run decomposition where all interleaving words are in P K X * K . We shall prove that all the prefixes in P K of these words are pairwise distinct with high probability and that the restriction on the length of the interleaving words does not affect the order of the error term.

Given a sequence of positive integers m = (m 1 , . . . , m ℓ ) and an increasing sequence of positive integers ω = (ω 1 , . . . , ω ℓ ), define the set Q ↔ n,K,m,ω as the set of Lyndon words w ∈ Q ↔ n,K such that (i) w admits a decomposition into m = ℓ i=1 m i factors; (ii) for i ∈ {1, . . . , ℓ}, w has exactly m i interleaving words with prefixes of length ω i in P K .

This defines a partition of Q ↔ n,K according to m and ω. Denote by Q = n,K,m,ω the subset of words of Q ↔ n,K,m,ω with interleaving words having pairwise distinct prefixes in P K .

Let S be a set of m distinct words of P K of total length N = ω i m i . There are (m -1)(m -1)! possible way of ordering S so that the first word is not the smallest, yielding a word of R ′ k , and (m -1)! possible ways of ordering S so that the first word is the smallest, yielding a word of R ′′ k . So completing the words up to length n with a K b (possibly a K+1 b at the beginning) before each word of P K and words of X * K after each word of P K , we obtain

z n-m(K+1)-N (m -1)! 1 + (m -1)z (1 -X K (z)) m
Lyndon words for a given set S. If the words of S are not distinct, then the last quantity is just an upper bound for the number of Lyndon words one can obtain.

Let us fix a sequence of positive integers m = (m 1 , . . . , m ℓ ) and an increasing sequence of positive integers ω = (ω 1 , . . . , ω ℓ ) and denote by P

K,n = Card(P K ∩ A n ). As ∀(a 1 , a 2 , . . . , a p ) ∈ [0, 1] p , p i=1 (1 -a i ) ≥ 1 - p i=1 a i ,
we have the following chain of inequalities provided the sets Q ↔ n,K,m,ω and Q

= n,K,m,ω are not empty Card(Q = n,K,m,ω ) Card(Q ↔ n,K,m,ω ) ≥ ℓ i=1 P K,ω i m i ℓ i=1 P m i K,ω i ≥ ℓ i=1 1 - m 2 i P K,ω i .
Lyndon words ( [START_REF] Fredricksen | Necklaces of beads in k colors and k-ary de Bruijn sequences[END_REF][START_REF] Duval | Factorizing words over an ordered alphabet[END_REF][START_REF] Lothaire | Applied Combinatorics on Words[END_REF]). It stores in an array pos of size k the positions where the factors begin.

Let u ∈ A * be a word, we denote by l u the Lyndon word associated to u, that is the smallest conjugate of u for the lexicographic order if it is primitive and its root otherwise. PROOF. Let u ∈ A + . We can uniquely write u = p(qp) k q with k ≥ 0, q = ε such that qp is a Lyndon word. Then we have uu = p(qp) k qp(qp) k q. Since qp is a Lyndon word and the primitive root of u, for any suffix s of uu, we have s ≥ qp = ℓ u . So the Lyndon factorization must be of the form

uu = ℓ 1 • • • ℓ n p ℓ 2k+1 u (qp) 2k+1 ℓ ′ 1 • • • ℓ ′ m q .
Now if we look at the factor f of the factorization of uu such that f is the last factor in the factorization that begins in the first occurrence of u in uu, we see that f = qp = ℓ u . 2

Recall that to draw uniformly an element from a subset S of Ω when no direct procedure is known, a reject algorithm can be used. The idea is to repeatively draw an element of Ω until it belongs to S. For such an algorithm to be efficient, we must ensure that -there is a simple way to draw uniformly an element from Ω; -it is easy to test whether a given element of Ω belongs to S; -the proportion of elements from Ω in S is not too "small".

For instance, this method can be used if one wants to draw uniformly a random irreducible polynomial on a finite field.

In the following algorithms, we denote u[i..j] (with 1 ≤ i ≤ j ≤ |u|) the factor of u starting at position i and ending at letter j. We use Lemma 24 to make a reject algorithm which is efficient to generate randomly a Lyndon word of length n:

RandomLyndonWord(n) //

Open problems

The results obtained in this paper are only a first step toward the average case-analysis of the tree obtained from a Lyndon word by successive standard factorizations. In order to study the height of these trees, a better insight of the nature of the right factors of words of L n \ aL n-1 is needed.

Figure 2 hints a very strong equi-repartition property of the length of the right factor over this set. Indeed a recent result (see [START_REF] Marchand | Limit law of the length of the standard right factor of a Lyndon word[END_REF]) obtained by probabilistic methods gives the limit law of the length of the standard right factor of a Lyndon word over a q-letter alphabet.

Lemma 19

 19 Let w be a Lyndon word of L n \ aL n-1 with k(w) ∈ I n . The number m of factors in the max-run decomposition satisfies Pr{m ≥ 2 log 2 n} = O log n n .

Lemma 22

 22 Let w be a Lyndon word of L n \ aL n-1 with k(w) ∈ I n having a max-run decomposition into m = O(log n) factors. The m interleaving words have pairwise distinct prefixes in P K with probability greater than 1 -O log 3 n n .

Lemma 24

 24 Let u ∈ A + and v = uu. If the Lyndon decomposition ℓ 1 • • • ℓ k of v and ℓ i is such that |ℓ 1 . . . ℓ i-1 | < |u| and |ℓ 1 . . . ℓ i | ≥ |u|, then ℓ i is the Lyndon word of u.

4 Fig. 1 .Fig. 2 .

 412 Fig. 1. Average length of the right factor of random Lyndon words of length from 1, 000 to 10, 000. Each plot is computed with 1, 000 words. The error bars represent the standard deviation.

Fig. 3 .

 3 Fig. 3. Zoom on the distribution of the length of the right factor over L n \ aL n-1 .

  return a random Lyndon word repeat u ← RandomWord(n) // u is a random word of A n x ← uu

Finally since m 2 i ≤ ( m i ) 2 and P K,ω i ≥ 2 K-1 for all i, we have

So for m = O(log n) and K > log 2 nlog 2 log 2 n -2 the ratio becomes

Since Q ↔ n,K is the disjoint union of Q ↔ n,K,m,ω for all (m, ω), the result is also true for Q ↔ n,K . Finally, as the error term O(log 3 n/n) is uniform for all subsets Q ↔ n,K and the error term O(log 2 n/n) coming from the hypothesis on the length of the interleaving words is of smaller order, the property holds for words w of L n \ aL n-1 with k(w) ∈ I n and m = O(log n). 2

An involution over L n \ aL n-1

We now introduce an involution on almost all the set L n \ aL n-1 such that the sum of the lengths of the right factors of w and its image is approximatively |w|.

To achieve this goal we partition the set L n \ aL n-1 in two subsets,

The set G n is the set of words in L n \ L n-1 whose max-run decomposition a k bw 1 . . . a K bw m verifies (i) k ∈ I n ; (ii) m < 2 log 2 n; (iii) the interleaving words w i have pairwise distinct prefixes in P K .

Recall that the set P K , defined on page 17, is the set of words w of X * K such that K ≤ |w| ≤ 2K -1 and ∀i ∈ {K, . . . , |w| -1} the i-th letter of w is a.

For any word w = a k bu • a K bv ∈ G n , we define ϕ(w) as

The key fact is that, globally, ϕ preserves the runs of a's and the prefixes in P K of the interleaving words of the max-run decomposition.

If ℓ is a Lyndon word, we denote by right(ℓ) the right factor of ℓ.

Lemma 23 Under the uniform distribution over G n the average length of the right factor of the standard factorization is

PROOF. We prove that ϕ is an involution on G n and the sum of the lengths of the right factors of a word w ∈ G n and ϕ(w) is about |w|.

Let w ∈ G n with standard factorization

Moreover for a word w of G n , the position of the smallest proper suffix of ϕ(w) can be easily determined. Indeed ϕ preserves the relative order between

So ϕ(w) ∈ G n and ϕ is an involution on G n : ϕ(ϕ(w)) = w for w ∈ G n .

Moreover for any word

where k -K ∈ {0, 1}.

By definition, the lengths of prefixes w ′ d and w

Moreover Lemmas 17, 19 and 22 match exactly the conditions (i), (ii) and (iii) which characterize the set G n . It leads to the estimate

Consequently we get

Finally as

the total contribution of of L n \ aL n-1 to the mean value of the standard right factor is

concluding the proof of Proposition 12 and Theorem 10.

Algorithms and experimental results

In this section we give two linear algorithms. The first one generates a random Lyndon words of a given length n over a q-ary alphabet and the second one computes the standard factorization of a Lyndon word.

Recall that, from Theorem 2, for any word x, there is a factorization

where r ≥ 0, n 1 , . . . , n r ≥ 1, and ℓ 1 > • • • > ℓ r are Lyndon words.

Our algorithms are based on the function LyndonFactorization(x, k, pos) which computes in linear time the decomposition of a word x into decreasing

// position of the next factor until (pos

The algorithm RandomLyndonWord computes uniformly a Lyndon word over a q-letter alphabet since RandomWord(n) generates a random word of length n and each Lyndon word of length n has exactly n conjugates.

Lemma 25

The average complexity of RandomLyndonWord(n) is linear.

PROOF. Each execution of the repeat...until loop is done in linear time. The condition is not satisfied when u is a conjugate of a periodic word v p with p > 1. This happens with probability O( n q n/2 ). Thus the loop is executed a bounded number of times in the average. 2 Lemma 26 Let w = αℓ be a Lyndon word of length greater than 1 and whose first letter is α. Let ℓ 1 . . . ℓ k be the factorization of ℓ into a nonincreasing sequence of Lyndon words. The right factor of w in its standard factorization is ℓ k .

PROOF. By Theorem 2 on page 3, ℓ k is the smallest suffix of ℓ, thus it is the smallest proper suffix of w. 2

The following algorithm computes the right factor of a Lyndon word ℓ which is not a letter: