Lucas Mercier
email: mercier@phare.normalesup.org

Philippe Chassaing
email: chassaingph@gmail.com

THE HEIGHT OF THE LYNDON TREE

Keywords: 2000 Mathematics Subject Classification. 60F05, 60C05, 68R15, 05A05 Random word, Lyndon word, Lyndon tree, binary search tree, branching random walk, Yule process, Galton-Watson process

We consider the set Ln of n-letters long Lyndon words on the alphabet A = {0, 1}. For a random uniform element Ln of the set Ln, the binary tree L(Ln) obtained by successive standard factorizations of Ln and of the factors produced by these factorizations is the Lyndon tree of Ln. We prove that the height Hn of L(Ln) satisfies

in which the constant ∆ ⋆ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers (∆ ⋆ ≃ 5.092 . . . ). The convergence is the convergence in probability of random variables.

1. Introduction 1.1. Lyndon words and Lyndon trees. We recall some notations of [START_REF] Lothaire | Combinatorics on words[END_REF] for readability. For an alphabet A, A n is the set of n-letters words, and the language, i.e. the set of finite words, {∅} ∪ A ∪ A 2 ∪ A 3 ∪ . . . , is denoted by A ⋆ . The length of a word w ∈ A ⋆ is denoted by |w|. A total order, ≺, on the alphabet A, induces a corresponding lexicographic order, again denoted by ≺, on the language A ⋆ : the word w 1 is smaller than the word w 2 (for the lexicographic order, w 1 ≺ w 2 ) at one of the following conditions: either w 1 is a prefix of w 2 , or there exist words p, v 1 , v 2 in A ⋆ and letters a 1 ≺ a 2 in A, such that w 1 = pa 1 v 1 and w 2 = pa 2 v 2 . For any factorization w = uv of w, vu is called a rotation of w, and the set w of rotations of w is called the necklace of w. A word w is primitive if |w| = # w .

The notion of Lyndon word has many equivalent definitions, to be found, for instance, in [START_REF] Lothaire | Combinatorics on words[END_REF].

Definition 1 (Lyndon word). A word w is Lyndon if w is primitive and is the smallest element of w .

Example. The word w = aabaab is the smallest in its necklace w = {aabaab, abaaba, baabaa} but is not Lyndon; baac is not Lyndon, nor acba or cbaa, but aacb is Lyndon.

Here is a recursive characterization of Lyndon words: Proposition 1. One-letter words are Lyndon. A word w with length n ≥ 2 is a Lyndon word if and only if there exists two Lyndon words u and v such that w = uv and u ≺ v.

Among such decompositions of w, the decomposition with the longest second factor (or suffix) v is called the standard decomposition.

Example. 0011 = (001)(1) = (0)(011) is a Lyndon word with two such decompositions. The latter is the standard decomposition.

The set of Lyndon words is denoted by L, and we set L n = L ∩ A n . The Lyndon tree (cf. [START_REF] Hohlweg | Lyndon words, permutations and trees[END_REF], also called standard bracketing tree by some authors, e.g. [START_REF] Barcelo | On the action of the symmetric group on the free Lie algebra and the partition lattice[END_REF]) of the Lyndon word w is a binary tree obtained by iteration of the standard decomposition: Definition 2 (Lyndon tree). For w ∈ L, the Lyndon tree L(w) of w is a labeled finite binary tree defined as follows:

• if |w| = 1, L(w) has a unique node labeled w, and no edges; • if (u, v) is the standard decomposition of w, then L(w) is the binary tree with label w at its root, L(u) as its left subtree and L(v) as its right subtree.

Remark 1. The labels of the leaves of a Lyndon tree are letters. Also, the label of an internal node is the concatenation of the labels of its two children, and, if |w| = n, L(w) is a rooted binary tree with n leaves, and n -1 internal nodes.

In general, the height of a rooted tree T, denoted h(T), is the maximal distance between the root of T and one of its leaves.

1.2. Result. The asymptotic behavior of the size of the right and left subtrees of L(L n ), for n large, have been studied in [START_REF] Bassino | The standard factorization of Lyndon words: an average point of view[END_REF][START_REF] Chassaing | Asymptotic behavior of some factorizations of random words[END_REF], for L n a random element of L n . The height h(L(L n )) of L(L n ) is of interest for analysis of algorithms and cryptanalysis , cf. [SSM92, SR03, BCN05], but it seems to have resisted analysis up to now. For a 2-letter alphabet, say A = {0, 1}, and for n ≥ 1, let L n denote a uniform random word in L n . Let (A(n, k)) n,k denote the Eulerian numbers, i.e. A(n, k) is the number of permutations σ of n symbols having exactly k descents (k places where σ(i) ≥ σ(i + 1)) . Set Ξ(θ) = lim (eλ ln 2) ν ln 2 ν ν 2 λ + Ξ(λµ),

∆ ⋆ = sup λ,µ,ν>0 (1+ν+µ)
ln 2+Ψ(λ,µ,ν) λ(ln 2) 2 = 5.092 . . .

See Lemma 4 or [START_REF] Giladi | Eulerian number asymptotics[END_REF]p. 299] for an expression of Ξ. We shall prove that:

Theorem 1. h(L(L n )) ln n P -→ ∆ ⋆ .
Conditionally given their lengths, the two factors of the standard decomposition of a uniform Lyndon word are not independent, and they are not uniform Lyndon words either, which seems to preclude a recursive approach to the proof of this Theorem. We shall rather use a coupling method: in Section 2 we sketch the main steps of the construction, on the same probability space, of a random Lyndon tree, and of two well studied trees, the binary search tree of a random uniform permutation, and a Yule tree, in such a way that the height of the Lyndon tree is closely related to some statistics of the two other trees. Then Theorem 1 follows from a large deviation result presented in Section 3.

Coupling results

2.1. Reduction to a Bernoulli source. If the word u is primitive but is not Lyndon, the Lyndon tree L(u) of u is the Lyndon tree of the unique Lyndon word in the necklace u of u, in short L(u) is the Lyndon tree of the Lyndon word of u. If u is periodic, we define the Lyndon word of u as the word 0 |u|-1 1, and L(u) is defined accordingly. Then the following algorithm:

• let W ∞ be an infinite word of uniformly random characters, obtained through the binary expansion of a number U uniformly distributed on [0, 1]; • let W n be the word W ∞ truncated after n letters, and let L n be the Lyndon word of W n . produces a n-letters long random Lyndon word L n . Conditionally, given that W n is primitive, this random Lyndon word L n is uniform on L n , but the unconditional distribution of L n fails to be uniform due to the small probability that W n is periodic. However, the total variation distance between the probability distribution of L n and the uniform distribution on L n is O 2 -n/2 (cf. e.g. [CZA10, Lemma 2.1]), thus any property that holds true asymptotically almost surely with respect to either distribution, holds true a.a.s. for both. From now on, we shall consider that L n is produced by the previous algorithm.

Poissonization.

In the first steps of the recursive construction of L(L n ), the sizes of the factors of the successive standard decompositions are predicted by the positions of the longest runs of 0's, and the structure of the top levels of L(L n ) is given by the lexicographic comparisons between the suffixes of L n beginning at these longest runs. But when n is large, the number of runs of 0's is typically n/4, and several among these runs are tied for the title of the longest run. Actually the lengths of the runs behave pretty much as a sample of n/4 i.i.d. geometric random variables with parameter 1/2, and, according to [START_REF] Brands | On the number of maxima in a discrete sample[END_REF], for any strictly increasing sequence n k such that lim k log 2 n k -⌊log 2 n k ⌋ = α ∈ [0, 1), the probability p m,n k that m ≥ 1 among the n k elements of such a sample are tied for the maximum is given, approximately, by (1) p m,n k ≃ j∈Z e -2 α+j (2 α+j-1 ) m m! .

Thus the number of ties does not converge in distribution, but has a set of limit distributions indexed by α ∈ R/Z. Such a complex behavior does not bode well, so we shall rather analyze a transform of this problem, in the form of the Lyndon tree of a word with random length. Consider the finite word W ℓ formed by a letter 1 followed by the truncation of W ∞ at the position τ ℓ of the ℓth 0 in the first run of ℓ consecutive 0's of W ∞ . Then W ℓ is primitive, and L ℓ denotes the Lyndon word of W ℓ , i.e.:

W ℓ = 1 010110 . . . 1 ℓ0s 000000 prefix of W∞ and L ℓ = ℓ0s 000000 1 010110 . . . 1 prefix of W∞ .
If τℓ is the position of the last 1 before τ ℓ , L ℓ is the concatenation of 0 ℓ 1 and of the truncation of the word W ∞ at position τℓ . Now, there exists a unique longest run of 0's in W ℓ as well as in L ℓ , and this run is ℓ letters long, to be compared with the behavior revealed by (1). Moreover, if Z k denotes the number of runs longer than ℓk -1, then Z 0 = 1 and (Z j ) 0≤j≤ℓ-1 is a Galton-Watson process with offspring distribution 2 -k 1 1 k≥1 , so that Z j has a geometric distribution with parameter 2 -j , see for instance [START_REF] Devroye | A limit theory for random skip lists[END_REF]. The family tree of this Galton-Watson process gives a lot of information on L(L ℓ ), leading ultimately to the proof of Theorem 2 below. The replacement of L(W n ) by L(L ℓ ), motivated by (1), has deeper consequences, initially unexpected to us: embedded in L(L ℓ ), appears a Yule family tree (see Section 2.5.2), and with this Yule tree come, besides several useful Galton-Watson trees, some Poisson point processes that leads to the Poisson-like formula (4). The asymptotic analysis of (4) finally leads to the computation of ∆ ⋆ . Thus the replacement of L(W n ) by L(L ℓ ) can be seen as some kind of poissonization.

Note that τ ℓ , the length of L ℓ up to one unit, has a geometric distribution of order ℓ , cf. [BK02, p. 10], and, typically, grows exponentially fast with ℓ:

E[|L ℓ |] = 2 ℓ+1 -1.
Thus, expectedly, the typical height of the Lyndon tree of L ℓ grows linearly with ℓ:

Theorem 2. h(L(L ℓ )) ℓ P -→ ℓ→∞ ∆ ⋆ ln 2.
In Section 4 we deduce Theorem 1 from Theorem 2: choosing ℓ(n) = log 2 nε n in such a way that P τ ℓ(n) ≥ n is small, and that, with a large probability, W ℓ(n) is a factor of W n , we compare carefully L(W ℓ(n) ) and L(W n ). We set

∆ • = ∆ ⋆ × ln 2.
Sections 2 and 3 are devoted to the proof of Theorem 2.

Figure 2. For L 5 = 0 5 1 3 0 3 101 4 0 4 1 8 0 2 1 2 , the tree T 5 = L 2 (L 5 ) has 6 needles and 4 blades. In brown, its contour traversal.

2.3. Reduction to a skeleton. In the top levels of the tree L(L ℓ ), the successive standard decompositions of the Lyndon word L ℓ , at the smallest suffixes of L ℓ , split the word L ℓ at the longest runs of 0's. For ℓ large enough, the longest runs are sparse enough to preserve some degree of independence between the factors. This is not true anymore at the lowest levels of the tree L(L ℓ ). For this reason, it is easier to split the study of the Lyndon tree in two parts: the first one focuses on the top of the tree, where the runs of 0's are still above a threshold a ℓ , and the second part studies a forest of shrubs at the bottom of the tree, each of them labeled with a factor of L ℓ that contains only runs of 0's shorter than the threshold. The top part is a tree itself (a subtree of L(L ℓ )), and each shrub of the forest at the bottom of L(L ℓ ) is rooted at (or grafted on) a leaf of the top tree. We follow here the same path as [START_REF] Broutin | An analysis of the height of tries with random weights on the edges[END_REF], our shrubs playing the same rôle as their spaghetti-like subtrees. Let us define by induction the tree above the threshold k, with k ≥ 1: Definition 3 (Top tree). If w denotes a Lyndon word, L k (w) is a finite labeled binary tree built recursively according to the following set of instructions:

• if w has one factor 0 k or less (thus 0 k+1 is not a factor of w), L k (w) is a single node, labeled w; • otherwise, let (u, v) be the standard decomposition of w. Then the root of L k (w) has label w, the left subtree of L k (w) is L k (u) and the right subtree is L k (v). L k (w) is called the top tree associated to w, with threshold k.

Set

T ℓ = L a ℓ (L ℓ ). The threshold a ℓ depends on ℓ. It has to be large enough for the top tree to retain the independence properties between the factors, but small enough that we can handle the shrubs, though they lack these nice independence properties. We shall assume that a ℓ ↑ ∞ and a ℓ = o(ℓ).

2.4.

A binary search tree. Let s k (w) denote the suffix of the finite word w with length |w|k + 1, and let σ w (k) be the rank of s k (w) once the sequence (s j (w)) 1≤j≤|w| is sorted in increasing lexicographic order. Then a word w is Lyndon if and only if σ w (1) = 1, and in this case, according to [START_REF] Hohlweg | Lyndon words, permutations and trees[END_REF], L(w) is the binary search tree of the permutation σ w . Note that according to [START_REF] Sedgewick | An introduction to the analysis of algorithms[END_REF]p. 362], it should rather be called the heap-ordered tree of σ w , see Section 2.5.2 and Figure 6. The asymptotic behavior of the height of the binary search tree of a random uniform permutation (not different from that of the corresponding heap-ordered tree, cf. [SF13, p. 364, Th. 7.1]) is well studied [START_REF] Devroye | A note on the height of binary search trees[END_REF][START_REF] Matthew | Almost sure asymptotics for the random binary search tree, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms[END_REF], but the distribution of σ Ln or of σ L ℓ is all but uniform. In this Section, we produce a coupling between σ L ℓ and a random uniform permutation. In the next Sections we inspect the relations between the heap-ordered trees of these two random permutations.

Let us take a closer look at T ℓ : observe that if w ∈ L, then 0w ∈ L, and the two factors of the standard factorization of 0w are 0 and w. Thus either a leaf v of T ℓ has label 0, and v is called a needle, or the label of v is a factor of w beginning with 0 a ℓ 1, and v is called a blade. The number N ℓ of blades of T ℓ has a geometric distribution with parameter 2 -ℓ+a ℓ , and the set of blades has a natural order related to the contour traversal (see Figure 2), that allows to identify it to [[1, N ℓ ]]. Note that the number of needles has a simple expression in terms of a Galton-Watson process with geometric offspring distribution. In the analysis of the shape of T ℓ , the configuration of the needles is a special concern, and the following bound will help at some point. Let g(v) denote the number of needles on the path between a blade v and the root ∅ of L k (w), and let M (w) be the length of the longest run of 0's in w . Then

Lemma 1. For any blade v of L k (w), g(v) ≤ M (w) -k.
Proof. For any interior node ν of L k (w), let g(ν) denote the natural extension of g to the interior nodes of L k (w) and let m(ν) be the length of the longest run of 0's in the label f (ν) of ν. Then, if ν is not a needle of L k (w), g(ν) + m(ν) does not decrease on the edge towards the root, for

• either the father µ of ν has the label 0f (ν), in which case g(ν) = 1 + g(µ) and m(ν) = -1 + m(µ);

• or f (µ) = 0f (ν), in which case g(ν) = g(µ) and m(ν) ≤ m(µ). Thus m(∅) + g(∅) = M (w) ≥ m(v) + g(v) = g(v) + k.
We shall need some notations: in the contour traversal of T ℓ , there exists a sequence of n va ℓ ≥ 0 needles between a blade v and the previous blade (or between v and the root, if there exists no previous blade). The concatenation, starting at this sequence of needles, included, of the labels of the leaves in the order of the contour traversal of T ℓ , is a suffix s(v) of L ℓ that can be written 0 nv 1 t v , the run 0 nv being maximal in the sense that 0 nv+1 1 t v is not a suffix of L ℓ .

The words of the sequence (t v ) 1≤v≤N ℓ have different lengths, being proper suffixes of each other, so they are all different, and we can give a reformulation of the algorithm that produces T ℓ , or more generally L k (w), in terms of the family T ℓ = ((n v , t v )) 1≤v≤N ℓ of the blades (with labels 0 k 1 t v ), in which only the n v 's and the relative order of the t v 's matter. With this reformulation of the algorithm, a slight perturbation of the t v 's produces a new tree, S ℓ , that is easier to handle than T ℓ due to its property of independence of labels, but that has essentially the same profile as T ℓ (i.e. it has the same repartition of blades with respect to the height). Let ǫ (j) denote the sequence of integers defined, for j ∈ I, by

ǫ (j) i = δ i,j .
For R a totally ordered set, N 0 × R inherits a lexicographic order, ≺, from R:

(n, t) ≺ (m, u) if n > m or if n = m and t < u. Let B = (l i , r i ) 1≤i≤N (resp. L = (l i ) 1≤i≤N , R = (r i ) 1≤i≤N
) be a finite sequence of elements of N 0 × R (resp. N 0 , R), with no repetitions in the sequence R. Assume that l j ≥ k for each j, and that (l 1 , r 1 ) is the smallest element of B, for ≺. Definition 4. The Lyndon tree L k (B) is defined by induction by:

(1) If N = 1 and l 1 = k, L k (B) has no edge and its unique vertex, with label (k, r 1 ), is a blade. (2) Otherwise, consider the new sequence B ′ formed from Lǫ (1) and R and let i 0 denote the index of the smallest element in B ′ , for ≺.

(a) If i 0 = 1, then L k (B) is the binary tree with a needle (labeled 0) as its left child and L k (B ′ ) as its right child. (b) If i 0 ≥ 2, then the binary tree L k (B) has L k ((l i , r i ) 1≤i≤i0-1 ) for left subtree, and L k ((l i+i0 , r i+i0 ) 0≤i≤N -i0 ) for right subtree.

Remark 2. Since (l i +1) is strictly decreasing at each recursive call to instruction (2), and since the l i 's are not allowed to drop under level k, L k (B) is well-defined as long as the r i 's are distinct. The N blades of L k (B) are labeled (k, r i ) 1≤i≤N , and, during the contour traversal, they appear in this order.

Remark 3. For R = {t v | 1 ≤ v ≤ N ℓ } and T ℓ = ((n v , t v ))
1≤v≤N ℓ defined in this section, L a ℓ (T ℓ ) = T ℓ , or more precisely, the shapes are the same, but the labels are different. When the label of some node of L a ℓ (T ℓ ) is (k, t v ), the corresponding label of T ℓ is the prefix of 0 k 1t v that stops with the last 1 before the next occurrence of 0 k . For the analysis of T ℓ , the fact that the t v 's are suffixes of t 1 , precluding any form of independence, is bothering. In order to fix the problem, in T ℓ , we replace the sequence (t v ) 1≤v≤N ℓ with a new sequence (s v ) 1≤v≤N ℓ of infinite binary words, close to the t v 's but independent, defined as follows: let (ζ i ) i∈N be an i.i.d. sequence of uniform infinite words, independent of T ℓ and let s v be the concatenation of p v , the prefix formed by the first a ℓ letters of t v , with ζ v . When t N ℓ is shorter than a ℓ letters, p N ℓ is completed with the appropriate number of 0's, before the concatenation with ζ N ℓ . This way, we obtain a new sequence S ℓ = ((n v , s v )) 1≤v≤N ℓ , and we set S ℓ = L a ℓ (S ℓ ) . Differences between T ℓ and S ℓ occurs scarcely, only when at least a ℓ letters are used to distinguish two suffixes, so that T ℓ and S ℓ are close, in a sense stated precisely in Proposition 4. We have: Proposition 2. The probability distribution of S ℓ is given by:

(1) n 1 = ℓ, and for v ≥ 2, n v -a ℓ is a geometric random variable with parameter 1 2 , conditioned to be smaller than ℓa ℓ ; (2) s v is a copy of W ∞ ;

(3) For all v, n v and s v are independent; (4) N ℓ is geometric with parameter 2 a ℓ -ℓ ;

(5) N ℓ and the sequence (n v , s v ) v∈N are independent; (6) (n v , s v ) v∈N is a sequence of i.i.d. random variables.

In terms of words, this can be rephrased as follows: Proposition 3. The sequence of words Sℓ = (0 nv-a ℓ 1s v ) 2≤v≤N ℓ , followed by the word 0 n1-a ℓ 1s 1 , is distributed as a sequence of copies of W ∞ , observed until the first occurrence of the prefix 0 ℓ-a ℓ , this first occurrence 0 n1-a ℓ 1s 1 being eventually truncated of any 0 in excess of 0 ℓ-a ℓ 1 . . . , so that n 1 = ℓ.

Proof of Proposition 2. Consider the word W ′ ∞ = 0 ℓ 1W ∞ and let x j , j ≥ 1, be the jth letter in W ′ ∞ , let ñk denote the length of the kth maximal run of 0's longer than a ℓ -1 in W ′ ∞ , let τ k be the position of the letter 1 ending this kth run of 0's, so that x τ k -1 x τ k ends the kth occurrence of the pattern 0 a ℓ 1 in W ′ ∞ . Let Ñℓ be the number of runs of 0's longer than a ℓ -1 before the second run longer than ℓ -1 occurs, and let pk = x τ k +1 x τ k +2 . . . x τ k +a ℓ . Then (x ℓ+1+j ) j≥1 is a Bernoulli process, the τ j 's are stopping times for the related filtration, and

Ñℓ = N ℓ , (ñ v , pv ) 1≤v≤N ℓ = (n v , p v ) 1≤v≤N ℓ ,
by definition. But since τ k + a ℓ + 1 ≤ τ k+1 , (ñ v , pv ) v≥1 is an i.i.d. sequence, with pv uniform on {0, 1} a ℓ and independent of ñv , and ñva ℓ geometric. This entails the six points of Proposition 2.

Due to Proposition 3, conditionally given N ℓ , the ranks of the terms of the sequence Sℓ = (0 nv-a ℓ 1s v ) 2≤v≤N ℓ with respect to the lexicographic order form a uniform permutation on N ℓ -1 symbols. This permutation is quite close to the random non-uniform permutation induced by the family (s(v)) 2≤v≤N ℓ of suffixes of L ℓ . As a consequence, the subtree U ℓ of S ℓ induced by the root and the blades, once the needles and the first blade erased, forms the binary search tree of a uniform permutation, a well studied random tree: for instance, a coupling between the Yule process and the binary search tree leads to a precise analysis of the depths of the leaves of the binary search tree, see [START_REF] Chauvin | Martingales and profile of binary search trees[END_REF]. The depths of blades in S ℓ , though they depend on their depths in U ℓ , are also affected by the positions of the needles, and we need to tweak the arguments of [START_REF] Chauvin | Martingales and profile of binary search trees[END_REF] in order to include the needles in their analysis.

In Section 2.5 we prove that the coupling between T ℓ and S ℓ is tight enough that the depths of leaves of T ℓ and S ℓ share the same asymptotic behavior, at some level of detail, see Proposition 4 below. The proof of Proposition 4 relies on a coupling between S ℓ and a Yule process, described in Section 2.5.3. This coupling is also the key to the analysis of the depths of blades in S ℓ , which are expressed as functionals of the Yule process, see Section 2.6.

Set p N ℓ = t N ℓ , and if v < N ℓ , set t v = p v 0 nv+1 1t v+1 , so that (0 nv 1p v ) 1≤v≤N ℓ is a factorization of L ℓ and (0 a ℓ 1p v ) 1≤v≤N ℓ is a sequence of Lyndon words. One obtains the Lyndon tree L(L ℓ ) when one grafts each shrub t

(v) = L(0 a ℓ 1p v ) on T ℓ , t(v) replacing the corresponding blade v of T ℓ .
Remark 4. Due to Proposition 4, the tree A ℓ obtained by grafting the shrubs t(v)'s on the corresponding blades of S ℓ (rather than T ℓ ) is very close in height to L(L ℓ ). But t(v) depends on S ℓ only through the prefix p v of p v and p v is short compared to p v when a ℓ grows (for

|p v | = a ℓ while E [|p v |] ≃ 2 a ℓ
). This has a crucial consequence for the study of the heights H v 's of the shrubs t(v)'s at the bottom of the tree: in Section 3.2 we shall see that (H v ) 1≤v≤N ℓ behave like a sample of independent geometric random variables with parameter 1/2, essentially independent from S ℓ .

2.5. The distance between T ℓ and S ℓ . For a blade v ∈ [[1, N ℓ ]], let h v (resp. hv ) be its height in S ℓ (resp. in T ℓ ). Set

d v = h v -hv , D ℓ = max 1≤v≤N ℓ d v .
Then Proposition 4.

lim ℓ P D ℓ ≥ ℓ √ a ℓ = 0.
The proof of Proposition 4 uses branching random walks arguments, as in [START_REF] Biggins | Chernoff 's theorem in the branching random walk[END_REF], and a coupling of S ℓ with a Yule process. For 1 ≤ i < j ≤ N ℓ , the case when t i ≺ t j while s i ≻ s j is called an inversion between i and j. In order to bound D ℓ , we need to track inversions. Let ̟ ℓ = 2 -a ℓ and let U i be the real number with dyadic expansion s i (according to point (2) of Proposition 2, U i is uniformly distributed on [0, 1]). We have: Lemma 2. If there is an inversion between i and j then s i and s j coincide on the first a ℓ letters, and U i and U j are in the same dyadic interval with width ̟ ℓ .

Proof. Since t i and t j are at least a ℓ -letters long by definition and since t i (resp. t j ) coincides with s i (resp. s j ) on the first a ℓ letters, then the outcome of the comparisons t i ≺≻ t j and s i ≺≻ s j can be different only if it is decided after the first a ℓ letters, which entails, by definition of the lexicographic order, that the 4 words have the same a ℓ -letters long prefix.

A Galton-Watson process.

Lemma 2 allows to compute an upper bound on D ℓ that depends only on S ℓ , and functionals of S ℓ are more tractable than functionals of T ℓ for several reasons. One of them is the description of S ℓ in terms of a Galton-Watson process with geometric offspring distribution: due to points (1), (4) and (5) of Proposition 2, (n v+1a ℓ + 1) 1≤v≤N ℓ -1 is distributed as a sample of i.i.d. geometric random variables, observed until the last time when all the terms of the sequence are smaller than ℓa ℓ . Then the first terms in T ℓ or in S ℓ , (n 1 , t 1 ) = (ℓ, t 1 ) and (n 1 , s 1 ), are seen as the ancestors, and the indices v such that

n v ≥ ℓ -k form generation k. More precisely, if n v ≥ ℓ -k, and if the next index that belongs to generation k is w, the offspring of (ℓ -k, t v ) at generation k + 1 is formed by (ℓ -k -1, t v )
and by the nodes (n j , t j ) or (n j , s j ) such that v < j < w and n j = ℓk -1. Let us call the set

F k,v = {(ℓ -k, t v ), (ℓ -k -1, t v )} ∪ {(n j , t j ) | v < j < w and n j = ℓ -k -1} = {(ℓ -k, s v ), (ℓ -k -1, s v )} ∪ {(n j , s j ) | v < j < w and n j = ℓ -k -1}
the family of (ℓk, t v ) or of (ℓk, s v ). Due to the memoryless property of the geometric distribution, the probability

p n that (ℓ -k, s v ) has O k,v = n children satisfies P (O k,v = n) = 2 -n 1 1 n≥1 ,
t j ) j is in- creasing while (s j ) j is decreasing, resulting in (d(ω)|ω ∈ O k,w ) = (1, 1, 2).
see for instance [Dev92, page 601] for an explanation. This process stops at generation ℓa ℓ .

We call GW ℓ the family tree of the Galton-Watson process described in this paragraph. The tree GW ℓ depends only on the sequence (n j ) j , and can be seen as the tree induced by some nodes of S ℓ , or of T ℓ , indifferently, including the blades. The differences between S ℓ and T ℓ can be analyzed at the level of the binary subtrees S k,w (resp. T k,w ) induced by the family F k,w in S ℓ (resp. in T ℓ ), for the only comparisons that involve the t j 's or the s j 's are inside the families, the other comparisons being settled by inspections of the first terms n j 's of the labels, that are the same in S ℓ and in T ℓ .

The subtrees S k,w and T k,w have one needle, the other leaves beginning with one of the elements of the offspring

O k,w = F k,w \ {(ℓ -k, t w )}. For such a leaf ω = (ℓ -k -1, t j ) ∈ O k,w , let d(ω)
denote the modulus of the difference between the height of ω in T k,w and the height of (ℓk -1, s j ) in S k,w . Then a bound for d v is given by the sum of the d(ω) on the path between the blade v and the A sample of exponential random variables, until hitting t, and the related tree E t (in which the pink horizontal lines are to be seen as vertices rather than as edges).

root. Thus the Galton-Watson tree GW ℓ underlies a branching random walk with positive steps d(ω)'s, and the rightmost position of this branching random walk gives an upper bound for D ℓ . Note that the independence of the steps d(ω) is questionable at this stage of the proof, see Section 2.5.3.

A Yule process.

According to Lemma 2, there are differences between T k,w and S k,w only if some of the U j 's involved in the comparisons at step (2) of Algorithm 4 are in the same dyadic interval with width ̟ ℓ = 2 -a ℓ . An additional condition is that the results of these comparisons change the leader, i.e. the smallest element in B ′ , at step (2) of Algorithm 4. But the leader does not change if it belongs to a different dyadic interval. It turns out that the family F k,v can be seen as a Galton-Watson process itself, elements of the different dyadic intervals being the generations. Such nested Galton processes with geometric progeny typically appear in Yule processes. In this section, we define a Yule process in terms of the sequence T ℓ , and in Section 2.5.3 we shall see how a bound for D ℓ can be derived from this Yule process. In Section 2.6, we show how to represent the height of a blade of S in term of this Yule process, a representation that is essential for the computation of the height of the Lyndon tree, through the large deviation results of Section 3.

A Yule process Y (cf. [AN72, page 109] or [START_REF] Aldous | Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today[END_REF]) models a population in which each individual lives forever, and gives birth to a new individual according to a Poisson process with rate ρ. We assume that the population starts at time 0 with a single individual, called the ancestor. One can keep track of the history of the population through the Yule tree Y [CKMR05], a family tree of the population, in which a vertical life line is drawn downward, for each individual, starting at an ordinate given by minus the date of birth, on the left of the life line of its father, and is connected to the life line of its father by a dotted horizontal line. Let Y t denote the family tree Y truncated at time t, i.e. at ordinate -t.

This representation comes handy for the description of a correspondence between the Yule tree and a sample Y = (Y n ) n≥1 of i.i.d. exponential random variables with rate ρ. Consider the sequence Z (t) defined by:

T t = inf{n ≥ 1 | Y n ≥ t}, Z (t) = (Z (t) k ) 0≤k≤Tt-1 = (t, Y 1 , Y 2 , . . . , Y Tt-1 ).
Then picture each term Z (t) k of the sequence Z (t) by a vertical line of the corresponding length Z (t) k , drawn at abscissa T tk, and connect, through an horizontal We do not know a reference for Proposition 5, that is part of the folklore on the topic. For the binary search tree, however, there exists a well studied analog: the shape of the heap-ordered tree 1 H σ of a random permutation σ has the same distribution as the shape of the related binary search tree. If we see σ as a word on the alphabet [[n]], H σ is the Lyndon tree of the word 0σ and can also be obtained through the construction by vertical lines that leads to E t , if one starts with the sample (f (0), f (σ(1)), f (σ(2)), . . . , f (σ(n))) (in which f is any positive strictly decreasing function) rather than with Z (t) , cf. Fig. 6. 2.5.3. Representation of S ℓ in terms of a Yule process. Let us denote by U v the real number whose dyadic development is 0 nv-a ℓ 1s v . Due to Proposition 3,

U = (U 2 , U 3 , . . . , U N ℓ , U 1 )
is distributed as a sequence of uniform random variables observed until a term belongs to [0, 2 -ℓ+a ℓ ], this last term being eventually multiplied by a power of 2, so as to belong to ]2 -ℓ+a ℓ -1 , 2 -ℓ+a ℓ ]. As a consequence, the sequence X image of U by the mapping

X i = -log 2 U i
is distributed as a sequence of exponential random variables observed until a term belongs to [ℓa ℓ , +∞[, this last term being eventually shifted by an integer, so as to belong to [ℓa ℓ , ℓa ℓ + 1[. Then the construction of Section 2.5.2, based on the sequence (ℓa ℓ , X 2 , X 3 , . . . , X N ℓ ), gives a Yule family tree Y ℓ-a ℓ with lifetime ℓa ℓ , and with intensity ρ = ln 2. Then the tree induced by the points of Y ℓ-a ℓ whose distance to the root is an integer between 0 and ℓa ℓ is GW ℓ . Also, removing the nodes of GW ℓ splits Y ℓ-a ℓ into connected components Y (x) , one for each interior node x = (ℓk, s v ) of GW ℓ , connected components that are independent and distributed as Y 1 (still with intensity ln 2). The set of leaves of

Y (x) is O k,v .
1 See for instance [START_REF] Sedgewick | An introduction to the analysis of algorithms[END_REF]p. 362]. 2.

3.

Figure 7. 1. S (2) and T (2) are equal in this example in which the blades of the family belong to 5 dyadic intervals a, b, c, d, e sorted in lexicographic order: the only a being interleaved between the 2 b's, comparisons between the 2 b's do not matter. Then we show two possible shapes (2. and 3.) for the subtree below bccddcceee, depending on the outcomes of comparisons t i ≷ t j and

s i ≷ s j . The fluctuation d(E) is 7 -2 = (k c -1) + + (k e -1) + , without (k d -1) + , for no d is involved in this part of the tree. 2.5.4. Proof of Proposition 4. For some element (n j , s j ), j > v, of O k,v , n j = ℓ -k -1. Also, s j is the dyadic expansion of Ũj = 2 ℓ-a ℓ -k U j -1 = 2 ℓ-a ℓ -k-Xj -1,
and Ũj belongs to the dyadic interval [m2 -a ℓ , (m + 1)2 -a ℓ ) if and only if

Xj = {X j } = X j -ℓ + k + a ℓ + 1 ∈ I m ,
in which the intervals

I m = [-log 2 1 2 + (m + 1)2 -a ℓ -1 ; -log 2 1 2 + m2 -a ℓ -1 ) satisfy 0≤m<2 a ℓ I m = [0, 1).
In turn, the points of Y (k,w) with ordinates

y m = -log 2 1 2 + m2 -a ℓ -1 , 0 ≤ m < 2 a ℓ ,
induce Galton-Watson subtrees GW (k,w) whose offspring distribution changes at each generation, and, at generation m, is a geometric distribution with parameter

p m = 1 2 + m2 -a ℓ -1 1 2 + (m + 1)2 -a ℓ -1 = 1 - 1 2 a ℓ + m + 1 .
Incidentally, Y (k,w) is distributed as Y 1 and it is built from the sample of exponential random variables Xj , for (ℓk -1, s j ) ∈ O k,w . Keeping in mind Lemma 2, note that differences between T ℓ and S ℓ occur only at the level of the families of GW (k,w) , because, if (n i , s i ) and (n j , s j ) are not in the same family but Ũi and Ũj are in the same dyadic interval, then

• either n j = n i , and the comparisons between (n j , s j ) and (n i , s i ), or between (n j , t j ) and (n i , t i ), have the same output, for only the n j ' s are involved, • either n j = n i , but in the sequence S ℓ , between (n j , s j ) and (n i , s i ), there exists some element (n k , s k ) such that n k > n i , and the standard factorization will cut the label just before (n k , s k ) in both trees, or before a similar element, independently of an eventual inversion between i and j, • or (n i , s i ) and (n j , s j ) are in the same family of GW ℓ , i.e. n j = n i = ℓ-k-1, and (n i , s i ) and (n j , s j ) are in the same subtree GW (k,w) but in the sequence S ℓ , between (n j , s j ) and (n i , s i ), there exists some element (n k , s k ) such that Xk is in some interval I m1 while Xi and Xj are in some I m2 with m 2 > m 1 . Then (n i , s i ) and (n j , s j ) land in different subtrees before an eventual inversion between them can produce a difference between T ℓ and S ℓ .

Inside such a family of GW (k,w) , inversion may occur between any couple of leaves, and may produce differences between the corresponding subtrees T (k,w) and S (k,w) of T ℓ and S ℓ , so that the operation L can produce any binary tree, as far as we know, only the number f of leaves of these 2 binary subtrees of T (k,w) and S (k,w) being given: thus the maximal depth of a leave is f -1 and the minimal depth is 1, if f > 1. In any case the difference between the depth of a leave in GW (k,w) and in the corresponding subtree of T ℓ is bounded by (f -2) + . Note that in a family at level m, the probability of difference between T ℓ and S ℓ is thus bounded by

O (1 -p m ) 2 = O 2 -2a ℓ ,
which is pretty small. There is an exception, in which the bound is (f -1) + rather than (f -2) + , when the only needle of S (k,w) happens, at some level m 0 that depends on the label of the ancestor of Y (k,w) . This precludes the Markov property of branching random walks but stochastic monotonicity alleviates the problem.

Let us give a formal argument: consider

m ℓ (θ) = E   1≤v≤N ℓ e θdv   ,
and assign to each blade v the position

-d v . Let Z (n) t
denote the number of blades of generation n with a position to the left of t. Then, as in [Big77, page 634],

P (D ℓ ≥ t) = P Z (ℓ) -t ≥ 1 ≤ E[Z (ℓ) -t ] ≤ e -θt m ℓ (θ). (2) Set p = 1 -2 -a ℓ = 1 -ε ≤ min {p m | 0 ≤ m ≤ 2 a ℓ -1} F (p, θ) = k≥1 ke θ(k-2)+ p(1 -p) k-1 = p(1 -e -θ ) + pe -θ (1 -e θ ε) 2 G(p, θ) = k≥1 ke θ(k-1)+ p(1 -p) k-1 = p (1 -e θ ε)
The key to the proof of Proposition 4, in the spirit of [Big77, Corollary (3.4)], is the next Lemma:

Lemma 3. For θ ≥ 0, m ℓ (θ) ≤ G(1-ε,θ) F (1-ε,θ) F (1 -ε, θ) 1/ε ℓ-a ℓ .
Given Lemma 3, setting t = ℓ √ a ℓ in (2), and e 2θ ℓ = 2 a ℓ = 1 ε , and using

F (p, θ ℓ ) = 1 + ε + 3ε √ ε + 2ε 2 + 2ε 2 √ ε + . . . G(p, θ ℓ ) = 1 + 2 √ ε + 2ε + 2ε √ ε + . . . one obtains P D ℓ ≥ ℓ √ a ℓ ≤ e -θ ℓ t m ℓ (θ ℓ ) ≤ exp -ℓ √ a ℓ ln √ 2 + O(ℓ) ,
which ends the proof of Proposition 4.

Proof of Lemma 3. Let us consider the words of {0, 1} a ℓ as an increasing sequence

w 0 ≺ w 1 ≺ • • • ≺ w -1+ 1 ε . Given k ∈ [[0, ℓ-a ℓ ]] and m ∈ [[0, 1 ε [[,
the factorizations of the sequences S ℓ and T ℓ in subsequences that start with some term lexicographically smaller than (k +a ℓ , w m ) and end just before the next one are the same, due to Proposition 2. These factorizations transfer to the sequence (X j ) 1≤j≤N ℓ : here the factors are subsequences that begin with some X j larger than k + y m and end just before the next one. The next level of factorization (fragmentation) is described by the subtrees of Y ℓ with leaves at level k + y m+1 (i.e. at time ℓky m+1 ) and ancestors at level k + y m . Each of these subtrees h is in bijection with binary subtrees of S ℓ and of T ℓ with the same number O h of leaves (needles excluded), but eventually different shapes, leading to different depths of their leaves, relatively to the 2 subtrees. We argued that O h has a geometric distribution with parameter p m ≥ p, independently of the other subtrees, and that for each leaf, the difference in depth is bounded by (O h -2) + , in the absence of a needle, and by (O h -1) + , in presence of a needle. The uniform bound (O h -1) + would be easier to handle, fitting perfectly in the context of branching random walks, but it is too crude for our purposes.

In each subtree Y (k,w) , there are 2 a ℓ levels of subtrees of type h, and there exists exactly one needle, in some subtree located on the right at a level m(w) such that {X w } ∈ I m(w) : this level m(w) depends on the levels of the tree Y ℓ that are closer to the root of Y ℓ . Let us bound the differences in depth of each leaf of a subtree h at level m(w) of Y (k,w) by d h = (O h -1) + , and let us bound by d h = (O h -2) + the differences in depth of each leaf of the subtrees h of Y (k,w) at other levels than m(w). Let us call Y k the part of Y ℓ that is at a distance of root smaller or equal than k. Then, given Y k , the conditional distribution of Y (k,w) endowed with elementary displacements d h from the roots to the leaves of each subtree h, is that of a non homogeneous branching random walk. Thus, if δ (k,w) j denotes the difference in depth for the leaf j between S (k,w) and T (k,w) , then

E   j e θδ (k,w) j Y k   ≤ G(p m(w) ,θ) F (p m(w) ,θ) 2 a ℓ -1 m=0 F (p m , θ).
Note that F and G are decreasing in p, for the geometric distribution is stochastically decreasing in its parameter. Thus, by stochastic monotonicity,

E   j e θδ (k,w) j Y k   ≤ G(1-ε,θ) F (1-ε,θ) F (1 -ε, θ) 1/ε . Now, let us denote by d (k) i
the difference in depth of a leaf i = (k, w) between L ℓ-k (T ℓ ) and L ℓ-k (S ℓ ), and assume that j is a generic leaf of S (k,w) or T (k,w) , indifferently. Then

d (k+1) j ≤ d (k) i + δ i j , and
E   j e θd (k+1) j   ≤ E   e θd (k) i j e θδ i j   = E   e θd (k) i E   j e θδ i j Y k     ≤ E e θd (k) i G(1-ε,θ) F (1-ε,θ) F (1 -ε, θ) 1/ε .
Lemma 3 follows by induction.

2.6. Depths of leaves of the Lyndon tree in terms of the Yule process. As observed for instance in [CKMR05, Lemma 2.1], Y ℓ-a ℓ seen as a planar tree, with no edge length, or with edge length 1, is a random binary search tree. That is to say, U ℓ is a random binary search tree, for the planar tree structures of Y ℓ-a ℓ and U ℓ depend only on the relative order of the words 0 nv-a ℓ 1s v for U ℓ , and of the real numbers X v for Y ℓ-a ℓ , through the same algorithm, and the mapping 0 nv-a ℓ 1s v -→ X v is monotone. Thus the depth of the blade v in the binary search tree U ℓ induced by S ℓ is the depth of the leaf v corresponding to X v in Y ℓ-a ℓ . Now, the difference between the depth of the blade v in U ℓ and its depth in S ℓ is the number of needles on the path to the root, whose expression is given by Proposition 6 below. For a given blade v of S ℓ , consider the marked point process Π v formed by the vertices of Y ℓ-a ℓ on the path from v to the root, the leaf v and the root excluded. This path is naturally identified with [0, ℓa ℓ ], the leaf being at 0 and the root at ℓa ℓ , for instance, and the mark being 0 or 1, respectively, according to the side of the branching, say left or right, leading to a decomposition

Π v = Π (0) v ∪ Π (1) v .
By convention, the mark for both points 0 and ℓa ℓ is one, and unless mentioned In S ℓ , the sign +1 marks the presence of a needle, while in Y ℓ-a ℓ the lengths of the sticks are rather 2 Yi = 1/U i : a needle occurs above the branchings ab, cd, hm, mn because, in Y ℓ-a ℓ , the corresponding first stick is at least twice longer than the second, and above hj because the factor is larger than 4. otherwise, they are not included in the point processes. For a point process π =

{ξ 1 < ξ 2 < • • • < ξ k-1 < ξ k } in some interval [0, m], G(π) denotes (3) G(π) = k+1 r=1 ⌊ξ r -ξ r-1 ⌋,
in which ξ k+1 = m and ξ 0 = 0. We have

Proposition 6. For 1 ≤ v ≤ N ℓ , 0 ≤ h v -(#Π v + 1 + G(Π (1) v )) ≤ 1.
Proof. Here #Π v + 1 accounts for the depth of v in U ℓ , ⌊ξ 1 ⌋ is n va ℓ , and one can check that ⌊ξ rξ r-1 ⌋ = a if the corresponding labels w r and w r-1 satisfy (n wra, s wr ) ≺ (n wr-1 , s wr-1 ) but (n wra -1, s wr ) ≻ (n wr-1 , s wr-1 ), in which case the corresponding edge in U ℓ is obtained by erasing a needles of S ℓ . In order for the relation in Proposition 6 to be exact, the point ξ k+1 at the top should be X 1 , while it is defined by ξ k+1 = m = ℓa ℓ here. The inequality 0

≤ X 1 -ℓ + a ℓ < 1 entails that 0 ≤ h v -(#Π v + 1 + G(Π (1) v )) ≤ 1.
The special rôle of Π

(1) v in Proposition 6 reflects the asymmetry of the Lyndon tree. Since G(Π (1) v ) tends to be large when #Π

(1) v is small, and small when #Π

(1) v is large, the difference between the height and the saturation level should be smaller for the Lyndon tree than for the binary search tree.

From now on, we shall assume that the depth h v of a leaf v of S ℓ is given by

h v = #Π v + 1 + G(Π (1)
v ), since this does not affect the limit in Theorem 2.

Proof of Theorem 2

In Section 3.1 we prove the key formula (4) about the Yule tree Y ℓ . In fine, through the couplings between T ℓ and S ℓ on one hand, between Y ℓ and S ℓ on the other hand (cf. Propositions 4 and 6), Proposition 7 allows to describe the profile of T ℓ , i.e. the repartition of the leaves of T ℓ according to their depth. Section 3.2 presents a sketch of the proof of Theorem 2. The rest of Section 3 is devoted to a detailed proof of Theorem 2.

3.1. A many-to-one formula. A leaf v of Y ℓ is said to be of type (m, n, A) if its left (resp. right) depth in Y ℓ is m (resp. n) and if its point process Π

(1) v belongs to A. Let π ℓ,m,n,A denote the average number of leaves of type (m, n, A) in Y ℓ and let U n,ℓ denote the uniform probability distribution on the simplex

{0 < ξ 1 < ξ 2 < • • • < ξ n < ℓ}. Then Proposition 7. (4) π ℓ,m,n,A = (ℓ ln 2) m+n 2 -ℓ m!n! U n,ℓ (A).
Up to a factor 2 m+n , the right hand of (4) is the probability that two independent Poisson processes on [0, ℓ], with intensity ρ/2 = ln √ 2, Π (0) (resp. Π (1) ), have m (resp. n) points, and that Π (1) belongs to A. This could be seen as an elementary instance of the many-to-one formula for branching random walks, cf. [START_REF] Hardy | A spine approach to branching diffusions with applications to L p -convergence of martingales[END_REF].

Proof. Consider the probability p that a random direction of a random Yule tree Y ∞ produces a leaf of type (m, n, A). On one hand, conditioning first on Y ∞ , the probability is the number of such leaves times the probability 2 -m-n of the path to one of these leaves, so that, going to expectations,

p = 2 -m-n π ℓ,m,n,A .
On the other hand, consider the random walk, on Y ∞ , of a particle with life time ℓ: the particle chooses left or right at birth times that form Poisson process with intensity ρ = ln 2 on [0, ℓ], and due to the colouring theorem (cf. Kingman, Ch. 5) the times when the particle goes left (resp. right) form two independent Poisson processes Π (0) and Π (1) with intensity ρ/2. Then p is the probability that #Π (0) = m, #Π (1) = n, and Π (1) ∈ A. Thus:

p = (ℓ ln 2) m 2 -m-ℓ/2 m! (ℓ ln 2) n 2 -n-ℓ/2 n! U n,ℓ (A) .
When A g is the set of point processes Π on [0, ℓ] such that G(Π) = g, we set π ℓ,m,n,Ag = π ℓ,m,n,g .

Sketch of proof.

To sketch the final argument, that follows [START_REF] Broutin | An analysis of the height of tries with random weights on the edges[END_REF], it will be convenient to think of Ψ(λ, µ, ν) as the following limit:

(5) Ψ(λ, µ, ν) = lim n n -1 ln (π ℓ,m,n,g ) , when the sequence (λ n , ν n , µ n ) = (ℓ/n, m/n, g/n) converges to (λ, ν, µ). Thus the number of blades of type (m, n, g) in S ℓ would be, approximately:

e nΨ(λ,µ,ν) = e ℓΨ(λ,µ,ν)/λ .

Results in the direction of formula (5), sufficient for our purposes, are proven in Section 3.3. On each blade v of type (m, n, g) of S ℓ , with depth

m + n + g = 1 + ν + µ λ ℓ,
we graft the shrub t(v). In Section 3.4, we prove that the maximum height of a set of k such shrubs behaves like the maximum of a sample of k independent geometric random variables with parameter 1/2, i.e. the maximum is essentially log 2 k. As a consequence, the total height of the highest leaf in any shrub that is grafted on a blade of type (m, n, g) in S ℓ is approximately m + n + g + log 2 e nΨ(λ,µ,ν) = (1+ν+µ) ln 2 + Ψ(λ,µ,ν)

λ ln 2 ℓ. Set ∆(λ, µ, ν) = ((1 + ν + µ) ln 2 + Ψ(λ, µ, ν))/λ ln 2. Then the highest leaf in the tree A ℓ is approximately ∆ • ℓ high, in which (6) ∆ • = sup λ,µ,ν>0 ∆(λ, µ, ν).
The supremum is obtained for ν = 2λ ln 2, leading to

∆ • = sup λ,µ>0
∆(λ, µ, 2λ ln 2).

Finally, due to Proposition 4, the same is true when the shrubs are grafted on the blades of T ℓ , producing L(L ℓ ) instead of A ℓ .

Remark Under U n,ℓ , rather than the ξ j 's, we shall consider the vector γ of gaps between the order statistics, defined by γ j = ξ jξ j-1 , 1 ≤ j ≤ n + 1, and γ = (γ j ) j , with the convention that ξ 0 = 0 and ξ n+1 = ℓ. The random vector γ is uniformly distributed on the simplex

D n,ℓ =    n+1 j=1
x j = ℓ and ∀j, x j ≥ 0    , and its distribution is denoted U n,ℓ again. Also, set ρ = (ρ j ) 1≤j≤n+1 , in which

ρ j = ⌊γ j ⌋.
Then G = |ρ|. The probability U n,ℓ (ρ = r) depends only on |r| and is given by:

U n,ℓ (ρ = r) = n! ℓ -n P   ℓ -|r| -1 < n j=1 U j < ℓ -|r|   ,
in which the U i 's are a sequence of i.i.d. random variables uniform on [0, 1], P (. . . ) is the Lebesgue measure of the domain {ρ = r}, and ℓ n /n! is the Lebesgue measure of D n,ℓ . In order to take advantage of the symmetric rôle of the ρ j 's, let β = (β j ) j≥0 be defined by

β j = # {1 ≤ i ≤ n + 1 | ρ i = j} , so that |β| = n + 1, and β = |ρ| = G(ξ). Then U n,ℓ (β = b) = n! ℓ n |b| b P   ℓ -b -1 < n j=1 U j < ℓ -b   ,
and (4) becomes

π ℓ,m,n,g = ℓ m (ln 2) m+n m! 2 ℓ P   ℓ -g -1 < n j=1 U j < ℓ -g   b =g |b| b . (7) Set p n,m = P   m -1 < n j=1 U j < m   and t n,g = b =g,|b|=n+1 |b| b ,
so that (7) can be written

π ℓ,m,n,g = ℓ m (ln 2) m+n m! 2 ℓ p n,ℓ-g t n,g .
From stronger results on the asymptotics of the Eulerian numbers (denoted here (A(k, n)) 0≤k≤n ), that can be found in [START_REF] Giladi | Eulerian number asymptotics[END_REF][formulas (6.12) to (6.16), page 299] 2 , we know that Lemma 4. For 0 < θ < 1, the limit:

Ξ(θ) = lim n 1 n ln p n,θn
exists and is given by

Ξ(θ) = ln sinh α -α coth α + 1 -ln α, in which α is given implicitly by -α -1 + 1 + coth α = 2θ. 2 According to [Tan73], A(k, n) = n! p n,k+1 .
On the other hand, for distributions b such that b j ≃ c j (n + 1), |c| = 1, and c = µ, we expect that

1 n ln |b| b = H (c) + o(1).
Following the lines of Lemma 8.3.1 in [Ash65, p. 238], one obtains that

H (c) ≤ H d (µ) = (1 + µ) ln(1 + µ) -µ ln µ,
in which d (µ) is the geometric distribution with expectation µ. As usual in large deviation theory, only the leading term of t n,µn , provided by c = d (µ) , contributes to the limit of n -1 ln t n,µn , so that we expect the following behavior:

n -1 ln t n,µn ≃ H d (µ) .
Together with (4), this would lead to the following expression for Ψ:

Ψ(λ, µ, ν) = H d (µ) + Φ(λ, ν) + Ξ(λ -µ), in which Φ(λ, ν) = lim n 1 n ln ℓ m (ln 2) m+n m! 2 ℓ = ln (eλ ln 2) ν ln 2 ν ν 2 λ .
The analysis of the contribution of the shrubs rests on more or less precise upper and lower bounds for n -1 ln (π ℓ,m,n,g ), to which the rest of the Section is devoted.

3.3.2.

Lower bound for n -1 ln π ℓ,m,n,g . The lower bounds for p n,g and t n,g do not need to be very precise for our purposes: for p n,g the "lower bound" given by the existence of the limit in Lemma 4 is precise enough. With µ = g/n, according to our heuristic considerations, the lower bound for t n,g provided by any term |b| b such that b is close to d (µ) n should be good enough. The sequence c (k) defined by

• c (k) j = d (µ) j for j ≤ k. • c (k) k+1 = j>k d (µ) j = 1 -i≤k c (k) i • c (k) i = 0 for i ≥ k + 2. satisfies H(c (k) ) -H(d (µ) ) = µ 1+µ k+1 k ln µ + (1 + µ) ln µ 1+µ , c (k) = µ 1 -( µ 1+µ ) k+1 .
Consider then the sequence of integers b (n) defined by

• ∀i ≤ k, b (n) i = ⌊c (k) i (1 + n)⌋, • b (n) k+1 = n + 1 -i≤k b (n) i , • b (n) i = 0 pour i ≥ k + 2, so that b (n) i -(n + 1)nc (k) i ≤    1 if i ≤ k, k + 1 if i = k + 1, 0 if i ≥ k + 2.
Thus,

b (n) ≤ (n + 1) c (k) + (k + 1)(b (n) k+1 -(n + 1)c (k) k+1 ) ≤ (n + 1) c (k) + (k + 1) 2 ≤ (n + 1)µ + (k + 1) 2 .
On the other hand, since b (n) is obtained, from (n + 1) c (k) , by transport of mass from i ≤ k towards k + 1, we have b (n) ≥ (n + 1) c (k) , and as a consequence

b (n) ≥ (n + 1)µ 1 -( µ 1+µ ) k+1 .
Due to the variations of ϕ(x) = x ln xx, and due to the inequality:

(8) | ln(n!) -ϕ(n)| ≤ ln(4n),
that holds for n ≥ 1, we obtain that:

| ln |b (n) | b (n) -(1 + n)H(d (µ) )| ≤ (n + 1)|H(c (k) ) -H(d (µ) )| + 4k ln(5n) = O(ln 2 n),
if one chooses k, n ≥ 5, and also k = c ln n for c large enough, namely c ln(1

+ 1 µ ) > 1, so that |H(c (k) ) -H(d (µ) )| is small enough. Now b n satisfies b n = µn + δ, instead of
µn. This is corrected by transferring a mass δ from 1 to 0, say, i.e. considering b n + (δ, -δ, 0, 0, . . . ), causing thus a variation δ ln(1

+ 1 µ ) + Θ µ ( 1 n ) of ln |b| b .
Here δ is O(ln 2 n), thus at least one term of the sum t n,g is equal to exp(nH(d (µ) ) + O(ln 2 n)), so that (9) t n,g ≥ exp(nH(d (µ) ) + O(ln 2 n)).

Owing to (8), we also have nΦ(λ, ν)ln ℓ m (ln 2) m+n m! 2 ℓ ≤ ln(4m) = ln(4νn). (10) Thus, owing to Lemma 4 and relations (9), (10), we obtain: Proposition 8. For 0 < ε < 0.05, when T is large enough, the set

L T,ε = {(m, n, g) | π T,m,n,g > e εn and m + n + g + log 2 π T,m,n,g > (∆ • -ε)T } is not empty.
Proof. First we prove that, for any ε ∈ (0, 0.05), the set Set ci = ci n , so that 1 ≥ |c| ≥ τn-µ τn . For c ∈ F µ,n , thanks to (8), we have ln

D ε = (λ, µ, ν) ∈ (0, +∞) 3 | Ψ(λ, µ, ν) > 2ε and ∆(λ, µ, ν) > ∆ • -ε/2
(c!) ≥ n(ln(n) -1)(1 -µ τn ) -nH (c) -(1 + τ n ) ln(4n). For τ n =
√ µn, this leads to: Proof.

ln(c!) ≥ n(ln(n) -1) -nH (c) -(1 + 2 √ µn) ln 4n.
Set d i = |a| β i (1+β) i+1 1 1 i≥0 , so that |d| = |a| and d = |a|β. Then H (a) = i≥0 a i ln di ai - i≥0 a i (ln |a| 1+β + i ln β 1+β ) ≤ - i≥0 a i (ln |a| 1+β + i ln β 1+β ) = -|a| ln |a| + (|a| + a ) ln(1 + β) -a ln β.
Choosing β = a /|a|, i.e. d = a , leads to the first inequality. Finally, for 0 ≤ y ≤ 1 and x ≥ 0, (y + x) ln(y + x) ≤ (1 + x) ln(1 + x).

Using that µ -→ H d (µ) is increasing, we obtain, for c ∈ F µ,n ,

H (c) ≤ H d ( c ) -2|c| ln |c| ≤ H d (µ) + 2(1 -|c|) ≤ H d (µ) + 2 µ n , so that ln(c!) ≥ n ln n -n -nH d (µ) -(1 + 2 √ µn) ln 12n.

This leads to

Proposition 10. For a sequence such that |b| = n + 1 and b = µn = g,

ln |b| b ≤ n H d (µ) + (3 + 2 √ g) ln(12n).
b j = # {1 ≤ i ≤ n + 1 | r i = j} .
Now each sequence r can be partially sorted to form a new sequence σ(r) as follows:

• the first terms of σ(r) are the terms of r smaller than τ n , sorted in increasing order; • the other terms follow, and they retain their relative order in the sequence r. Then δ • σ = δ and the preimage of an element b such that b = µn has at least one element in

σ(δ -1 ({ b = µn})). Thus # { b = µn} ≤ #σ(δ -1 ({ b = µn})) ≤ (n + 2) τn+1 × (µn) µn/τn ,
the first term of the product on the right because an increasing sequence is well described by its distribution, here (b j ) 0≤j≤τn , the second term for the length of the second part of the sequence is shorter than µn/τ n due to the Markov inequality, and each of its terms is smaller than µn and larger than τ n . As long as n ≥ 2, the choice τ n = √ µn leads to:

(11) # { b = g} ≤ µ √ g (n + 2) 1+2 √ g ≤ (4ng) √ g × 2n.
3.3.5. Upper bound for p n,ℓ-g . Trite computations lead to the next Proposition:

Proposition 11. For 0.5 < θ < 1,

P   θn < n j=1 U j   = P   (1 -θ)n > n j=1 U j   ≤ e nΞ(θ) .
Proof. Set S n = n j=1 U j , ε = 2θ -1 > 0 and t > 0. From the Markov inequality, we obtain that:

P (θn ≤ S n ) ≤ E e t(2U -1) n e -tεn ≤ e nh(t) , in which
h(t) = ln sinh(t) e -tε t . Then ∂h ∂t = coth(t) -ε - 1 t ,
and since t → coth(t) -1 t is continuous strictly increasing from -1 to 1, h is minimal when t = α in which α is defined by

coth(α) -ε -α -1 = 0. Finally h(α) = ln sinh(α) -α coth(α) + 1 -ln(α) = Ξ(θ).
For θ < 0.5 use that 1 -U j 's are uniform, and that Ξ(θ) = Ξ(1θ).

Corollary 1. For n ≥ 1, ln p n,ℓ-g ≤ n(Ξ(λ -µ) + ρ n ), in which ρ n = Ξ(λ -µ -δ n ) -Ξ(λ -µ), 0 ≤ δ n = (-∞, λ -µ -1 2 ] ∩ [0, 1 n ] ≤ 1 n .
3.3.6. Conclusion. Combining Proposition 10 and (11), we obtain that, as long as n ≥ 2:

ln t n,g ≤ n H d (µ) + (3 + 2 √ g) ln(24ng), With (10)
, this gives Proposition 12. For (λ, µ, ν) = (ℓ, g, m)/n, as long as n ≥ 2, one has:

r ℓ,m,n,g ln 2 = ln π ℓ,m,n,g -ℓ Ψ(λ,µ,ν) λ ≤ nρ n + (3 + 2 √ g) ln(24ng) + ln(4m).
3.4. Contribution of the shrubs. The proof of Theorem 2 has two final steps, contained in the next sections.

Lower bound for h(L(L ℓ )).

Proposition 13. For any ε > 0,

lim ℓ P h(L(L ℓ )) ≤ (∆ • -ε)ℓ = 0.
Proof. Keeping in mind Section 2.5, we observe that

|h(A ℓ ) -h(L(L ℓ ))| ≤ D ℓ .
Thus, according to Proposition 4, we only need to prove that

lim ℓ P (h(A ℓ ) ≤ (∆ • -ε)ℓ) = 0.
Working with A ℓ , we can use the representation of the depth of blades S ℓ through a Yule process, as in Section 2.6. Let B denote the infinite complete binary tree with the language A ⋆ = {0, 1} ⋆ as set of vertices, and {(w, wa) | (w, a) ∈ A ⋆ × A} as edge set, ∅ being the root. We shall see the infinite family tree Y of the Yule process as B endowed with edge lengths that form an i.i.d. family of exponential random variables with parameter ln 2. In this setting, we shall interpret the distance between w ∈ A ⋆ and the root ∅ as the date of the death of w, and the length of the last edge of the path from the root to w as the lifetime of w. An interior point of this last edge inherits the label w of the vertex sitting at the end of the edge.

For any T > 0, we shall consider a new tree D T defined as follows:

• the vertices of D T are the points of Y at distance nT from the root (for any n ≥ 0); they are almost surely interior points of some edges; • a generic edge (x, y) of D T satisfies the following properties:

the distance between x and y in Y is T ; -the labels of x and y are of the form (w, ws) with (w, s) ∈ A ⋆ × A ⋆ . If points at distance nT from the root form the n-th generation of a population, then D T is the family tree of a Galton-Watson process with offspring distribution 2 -T (1 -2 -T ) k-1 1 1 k≥1 and average offspring size 2 T . Each individual w ∈ A ⋆ living at time nT possesses, attached to him, the Yule family tree Y (w) with life time T that describes his progeny between times nT and (n + 1)T . Consider then, for each descendent v = ws of w living at time (n + 1)T , its marked point process Π w,ws on [0, T ] induced by Y (w) : this allows to decide whether ws is a descendent of w of type (m, n, A) or not. When ws is a descendent of w of type (m, n, A) in Y (w) , we say that the edge (w, ws) of D T is open. Erasing the closed edges of D T , one obtains a forest F whose connected components are independent Galton-Watson trees with average offspring size π T,m,n,A . In the sequel, A is the set A g of point processes Π on [0, T ] such that G(Π) = g, and we set

π T,m,n,Ag = π T,m,n,g = π T .
With the help of Proposition 8, for T large enough, one can choose (m

T , n T , g T ) = (m, n, g) ∈ L T,ε , such that π T > e T ε/λ > 1 and ρ = m + n + g + log 2 π T > (∆ • -ε)T. (12)
As a consequence, the connected components of F are supercritical. Since their offspring is bounded by a geometric distribution, according to the Kesten-Stigum Theorem, almost surely, one of the connected components, rooted at a random but finite distance R × T of the root of Y, is infinite and satisfies

lim k Z k π -k T = C,
in which Z k is the size of generation k of the said component, and C is random but almost surely positive. Finally, the number X k of elements of type (k -R)(m, n, g) at time kT in Y is not smaller than Z k-R , thus it satisfies a.s.

lim inf k 1 k ln X k ≥ ln π T .
This entails that, for η > 0 and c = -η + ln π T ,

lim k P X k ≤ e ck = 0.
Set k = ⌊(ℓa ℓ )/T ⌋ and let S be the set of shrubs grafted on the blades of S ℓ that belong to the progeny, at time ℓa ℓ , of the X k leaves of Y kT . The set S contains Zℓ ≥ X k shrubs, and all the corresponding blades have a depth larger than k (m + n + g), according to Proposition 6. We shall prove that the highest among the Zℓ shrubs in S has a height M ℓ given, approximately, by

M ℓ ≃ log 2 Zℓ ≃ ck ln 2 ≃ ⌊ℓ/T ⌋ log 2 π T ≃ Ψ • ℓ ln 2 , then we shall use the fact that (13) h(A ℓ ) ≥ k (m + n + g) + M ℓ .
In general, a shrub contains at least one run of 1's, but with a probability 2 -a ℓ , thus the height H v of a shrub t(v) is larger than the length of, say, its last run of 1's, i.e. stochastically larger than a geometric distribution with parameter 1/2. Now, roughly speaking, the probability p r,α,a that ar i.i.d. shrubs are all lower than (1α) log 2 r is smaller than the probability that ar i.i.d. geometric random variables are all smaller than (1α) log 2 r, i.e.

p r,α,a ≤ (1 -2 -1-(1-α) log 2 r ) ar (14) ≤ exp(-r -(1-α) /2) ar = exp(-ar α /2),
for a > 0, 0 < α < 1. However we are not interested here in a sample of Zℓ i.i.d. shrubs with the typical distribution, i.e. with the distribution associated with a Bernoulli word observed until the first occurence of 0 a ℓ : each shrub t(v) ∈ S is selected according to the height h v ≃ m v + n v + g v of the corresponding blade v, and h v is determined by the operation of the algorithm L a ℓ on the sequence S ℓ = ((n w , s w )) 1≤w≤N ℓ , see Definition 4, while t(v) = L(0 a ℓ 1p v ). Now s v and p v have the same a ℓ -letters long prefix p v , their respective suffixes, ζ v and ζv , being independent. Furthermore ζv is independent of S ℓ , and as a consequence ζv and h v are independent. The probability that ζv begins with the prefix 101 is thus 1/8, and this insures that the last run of 1's in p v is a factor of ζv and does not depend on h v . Let Z be the number of shrubs t(v) ∈ S such that ζv begins with 101: conditionally given Zℓ , Z has a binomial distribution with parameters Zℓ and 1/8. The maximal height H ℓ in the sample of Zℓ shrubs is thus stochastically larger than the maximum of Z i.i.d. geometric random variables with parameter 1/2, and satisfies, for any α > 0, .

Π ℓ = P (H ℓ ≤ (1 -α)ck/
The probabilities on the right hand side vanish when ℓ grows, and so does Π ℓ . Owing to (13),

P (h(A ℓ ) ≤ γ ℓ ) ≤ Π ℓ , in which γ ℓ = k m + n + g + (1-α)c ln 2
.

But due to k = ⌊(ℓa ℓ )/T ⌋, and owing to our choice of (m, n, g), cf. (12),

γ ℓ = ρ -(1-α)η+α ln π T ln 2 k ≥ (∆ • -ε)(ℓ -a ℓ ) -(1-α)η+α ln π T ln 2 ⌊(ℓ -a ℓ )/T ⌋ -(∆ • -ε)T.
Since α and η are arbitrary positive numbers, for a suitable choice,

γ ℓ ≥ (∆ • -2ε)ℓ,
for ℓ large enough, which concludes the proof.

Upper bound for h(L(L ℓ )).

Proposition 14. For any ε > 0,

lim ℓ P h(L(L ℓ )) ≥ (∆ • + ε)ℓ = 0.
Proof. Again, according to Proposition 4, we only need to prove that

lim ℓ P (h(A ℓ ) ≥ (∆ • + ε)ℓ) = 0.
A shrub t(v) is the Lyndon tree of a Bernoulli word observed until the first occurence of 0 a ℓ , and as such it comes with a sequence of i.i.d. geometric random variables (the lengths of the runs of 0's) observed until the hitting time of [a ℓ , +∞): this sequence yields a Galton-Watson tree GW a ℓ (v) with geometric offspring distribution, that has a ℓ generations, as described by Figure 3. Based on GW a ℓ (v), one can define a branching random walk BGW a ℓ (v) as follows: when the offspring of an individual has size N , each of the N scions jumps N steps in the same direction, say to the left. Then the height H v of t(v) is stochastically smaller than the leftmost position M v of BGW a ℓ (v) at generation a ℓ : the height of a binary tree with n leaves is smaller than n -1 and then one has to account for at most one needle in each family of GW a ℓ (v), so N leaves plus one needle entails that the depth of each of the N scions is at most the depth of its father plus N . Assume that the positions of the members of generation a ℓ for BGW a ℓ (v) form a point process (X i ) i∈I . Then, as usual, for 0 ≤ θ < ln 2, and x ≥ 3,

P (M v ≥ x) ≤ e -θx E e θMv ,
and

E e θMv ≤ E i∈I e θXi = E N e θN a ℓ = 2e θ (2-e θ ) 2 a ℓ . It entails that P (M v ≥ xa ℓ ) ≤ inf 0≤θ<ln 2 2e θ(1-x) (2-e θ ) 2 a ℓ = 2 -x-2 (x -1) 1-x (x + 1) 1+x a ℓ ≤ 2 -x (ex/2) 2 a ℓ ,
in which the equality of the second line holds for x ≥ 3, while the last inequality holds for x ≥ 1. Thus both the conditional probabilities given the first a ℓ characters of the word, and, as a consequence, the conditional probability given the height of the root, satisfy:

P (H v ≥ xa ℓ | . ) ≤ 2 a ℓ 2 -x (ex/2) 2 a ℓ , ≤ 2 -x e 2 x 2 a ℓ .
As a consequence, the maximal height H S of any set S of shrubs selected according to the position of their roots in S ℓ satisfies P H S ℓ ≥ ξ/ ln 2 ≤ |S| e -ξℓ/a ℓ (eξℓ/a ℓ ln 2) 2 a ℓ ≤ e ln |S|-ξℓ+2a ℓ ln(ξℓ) , (15) as long as ξℓ ≥ 3a ℓ ln 2.

Let Z ℓ,m,n,g denote the number of blades of type (ℓ, m, n, g) in S ℓ , and let H ℓ,m,n,g (resp. H ℓ,m,n,g ) denote the maximal height among the corresponding set of shrubs (resp. the height of the highest leaf of A ℓ that has an ancestor among the Z ℓ,m,n,g leaves of type (ℓ, m, n, g)). According to Propositions 4 and 6,

h(L(L ℓ )) ≃ h(A ℓ ) = max {H ℓ,m,n,g | m, n, g ∈ N} = max {m + n + g + H ℓ,m,n,g | m, n, g ∈ N} .
As a consequence,

P (h(A ℓ ) ≥ (∆ • + 2ε)ℓ) ≤ m,n,g∈N P (H ℓ,m,n,g ≥ (∆ • + 2ε)ℓ) (16) Set δ(λ, µ, ν) = ∆ • -∆(λ, µ, ν) ≥ 0.
For an arbitrary choice of α, the Markov inequality yields that P Z ℓ,m,n,g ≥ 2 αℓ ≤ e -αℓ ln 2+ln π ℓ,m,n,g , Thus, if S stands for the set of blades of type (ℓ, m, n, g) in S ℓ , (15) entails that, for ε > 0, P (H ℓ,m,n,g ≥ (∆ • + 2ε)ℓ) ≤ e αℓ ln 2-ξℓ+2a ℓ ln(ξℓ) + P Z ℓ,m,n,g ≥ 2 αℓ in which ξ = (∆ • + 2ε -1+µ+ν λ ) ln 2 = (δ(.) + 2ε + Ψ(.) λ ln 2 ) ln 2. The choice

α = ∆ • + ε -1+µ+ν λ leads to P (H ℓ,m,n,g ≥ (∆ • + 2ε)ℓ) ≤ 2 -εℓ+2a ℓ log 2 (ξℓ) + 2 -(ε+δ(.))ℓ+r ℓ,m,n,g , (17)
provided that ξℓ ≥ 3a ℓ ln 2, since we need (15) to hold. In view of ( 16) and ( 17), we need

• to reduce the domain of summation in (16),

• and to check that r ℓ,m,n,g is uniformly o(ℓ) on the reduced domain. First point: for η > 0, set T ℓ,η = (m, n, g) | n ≥ ηℓ, m+n ℓ ln 2 ∈ 1 3 , 5 , and ηℓ + ln π ℓ,m,n,g ≥ 0 , and note that #T ℓ,η ≤ 25ℓ 3 . Lemma 5. For η small enough, the probability that a leaf of A ℓ higher than (∆ • + 2ε)ℓ grows from a blade outside T ℓ,η vanishes when ℓ grows, and

P (h(A ℓ ) ≥ (∆ • + 2ε)ℓ) ≤ o(1) + m,n,g∈T ℓ,η P (H ℓ,m,n,g ≥ (∆ • + 2ε)ℓ) .
Proof. First we prove that the average number π ℓ+ (resp. π ℓ-) of blades of type (m, n, g) with m+n ≥ 5ℓ ln 2 (resp. with m+n ≤ (ℓ ln 2)/3) vanishes when ℓ grows, and so does the probability that there exist such blades: due to (4),

π ℓ+ = k≥5ℓ ln 2 (ℓ ln 2) k 2 k-ℓ k! , π ℓ-= 0≤k≤(ℓ ln 2)/3 (ℓ ln 2) k 2 k-ℓ k! .
If X follows the Poisson distribution with parameter ℓ ln 2, we have:

π ℓ+ = E 2 X 1 X≥5ℓ ln 2 , π ℓ-= E 2 X 1 X≤(ℓ ln 2)/3 ,
and, for any t > 0,

π ℓ+ ≤ E 2 X e t(X-5ℓ ln 2) = exp[(e t+ln 2 -1 -5t)ℓ ln 2].
A suitable choice of t leads to lim ℓ π ℓ+ = 0, and similar inequalities yields that lim ℓ π ℓ-= 0. In what follows, we consider only blades of type (m, n, g) with aℓ ≤ m + n ≤ bℓ, in which a = (ln 2)/3 and b = 5 ln 2. Set

π ℓ,m,n = g π ℓ,m,n,g = (ℓ ln 2) m+n 2 -ℓ m!n! , (18)
and let π η be the expectation of the number of blades such that ηℓ + ln π ℓ,m,n,g < 0: it satisfies, for any t ∈ (0, 1),

π η ≤ aℓ ≤ m + n ≤ bℓ, (ℓ -n) + ≤ g ≤ ℓ π ℓ,m,n,g e -t(ηℓ+ln π ℓ,m,n,g ) = e -tηℓ aℓ ≤ m + n ≤ bℓ, (ℓ -n) + ≤ g ≤ ℓ π 1-t ℓ,m,n,g ≤ ℓe -tηℓ aℓ≤m+n≤bℓ π 1-t ℓ,m,n ≤ b 2t ℓ 1+2t e -tηℓ   aℓ≤m+n≤bℓ π ℓ,m,n   1-t = b 2t ℓ 1+2t e -tηℓ E 2 X 1 aℓ≤X≤bℓ 1-t = b 2t ℓ 1+2t exp(-ℓ(t(η + b ln 2) -b ln 2)).
Choosing 1 > t > (1 + η b ln 2 ) -1 , we see that π η vanishes as ℓ grows, and so does the probability of existence of blades such that ηℓ + ln π ℓ,m,n < 0 and aℓ ≤ m + n ≤ bℓ.

For the bounds we have in mind, Ξ has to be Lipshitz continuous around arg max ∆, i.e. its argument λµ has to be bounded away from 0 and 1. This should be easy because Ξ goes to -∞ when its argument is close to 0 or 1, leaving then little chance to ∆ to be at its maximum. There is chance, however, for ∆ to be large even if Ξ is close to -∞: if n is very small, and thus λ very large, Ξ/λ could be small, and ∆ could eventually be close to its maximum even though Ξ is close to -∞. The next Lemma fixes this problem: consider the set Sη of blades such that ηℓ + ln π ℓ,m,n ≥ 0 and n ≤ ηℓ, for 0 < η < ln 2, and let H η,ℓ denote the maximal height among the leaves of A ℓ that have an ancestor in Sη . Then we have: Lemma 6. For any ε > 0, there exist η > 0 such that

lim ℓ P (H η,ℓ ≥ (1 + ln 2 + ε)ℓ) = 0.
Proof. Owing to (8) and (18), 0 ≤ (ηln 2)ℓϕ(n)ϕ(m) + (m + n) ln(ℓ ln 2) + ln 16mn.

Using that cϕ( x c ) = ϕ(x)x ln c, for c = ℓ ln 2 we obtain:

0 ≤ ηℓ -c -cϕ( m c ) -cϕ( n c ) + 2 ln(2bℓ) ≤ c -1 -ϕ( m ℓ ln 2 ) -ϕ( η ln 2 ) + η ln 2 + 2 ln(2bℓ) ℓ ln 2 (19)
Since x -→ -1-ϕ(x) reaches its maximum, 0, when x = 1, then η small and ℓ large entails that |mℓ ln 2| has to be small, for the left hand size to be nonnegative. More precisely, for any ε > 0, one can choose η > 0, independent of m, n, ℓ, in such a way that, for ℓ large enough, (19) holds only if m ∈ ℓ(ln 2 ± ε), by strict convexity and smoothness of ϕ: solve 1 + ϕ(u) = 2( η ln 2ϕ( η ln 2 )). For η small enough, the 2 solutions r 1 and r 2 are close enough to 1, so that r 1 ≤ m ℓ ln 2 ≤ r 2 entails m ∈ ℓ(ln 2 ± 2ε). Then one can choose ℓ large enough, so that 2 ln(2bℓ)

ℓ ln 2 ≤ η ln 2 -ϕ( η ln 2 ).
Then the depth m+n+g of a blade v ∈ S is at most ℓ(ln 2+ε+η +1), since g ≤ ℓ.

On the other hand, the expected number πη of blades in S is smaller than exp(ℓ(η(ln ln 2)ϕ(η))): again let X, Y be i.i.d. and Poisson distributed with parameter ℓ ln 2/2, so that we have:

πη = E 2 X+Y 1 X≤ηℓ = 2 ℓ/2 E 2 X 1 X≤ηℓ .
Again, for any t > 0, for instance for t = η ln 2 , πη ≤ 2 ℓ/2 E 2 X e t(ηℓ-X) = exp[ℓ(tη + e -t ln 2)] (20

) = exp[ℓ(η(ln ln 2) -ϕ(η))]. Set ξ = η(ln ln 2) -ϕ(η).
Then, due to (15), the probability that the taller shrub planted on a blade of S is at least

P H η,ℓ ≥ (1 + ln 2 + ε + η + 3 ξ ln 2 )ℓ = 0.
in which ε + η + 3 ξ ln 2 is arbitrarily close to 0 for η small. We proved that, with a large probability, there exists no blade with m+n ℓ ln 2 outside [a, b], and no blade with m+n ℓ ln 2 inside [a, b] but η + ln π ℓ,m,n,g < 0. Then we proved that, with a large probability, a leaf of A ℓ with depth larger than (1 + ln 2)ℓ does not grow from a blade such that η + ln π ℓ,m,n,g ≥ 0 but n ≤ ηℓ. This concludes the proof since ∆ • = 3.5... > 1 + ln 2.

Inside T ℓ,η , we have (5 ln 2) -1 ≤ λ ≤ η -1 and 0 ≤ ν ≤ 5λ ln 2. We always have 0 ≤ λµ ≤ 1, but λµ has to be bounded away from 0 and 1, in order for nρ n and r ℓ,m,n,g to be small. This holds true due to 0 ≤ ηℓ + ln π ℓ,m,n,g = ηℓ + nΨ(λ, µ, ν) + r ℓ,m,n,g ln 2

≤ ηℓ + n(Ψ(λ, µ, ν) + ρ n )) + (3 + 2 √ g) ln(24ng) + ln(4m).
Dividing by ℓ, for ℓ large enough, this insures that on T ℓ,η ,

H d (µ) + Φ(λ, µ, ν) + Ξ(λ -µ -δ n )) ≥ -2η 5
ln 2 , in which all the terms on the left hand side are bounded on T ℓ,η , but eventually Ξ. Thus, for ℓ large enough, on T ℓ,η , Ξ is bounded away from -∞, and λµ -1 n is bounded away from 0 and 1, which entails a Lipshitz condition on Ξ on the domain T ℓ,η . Thus, according to Proposition 12, on T ℓ,η , since n ≥ ηℓ, and λ ≤ η -1 ,

1 ℓ r ℓ,m,n,g ≤ 1 ℓ (2nρ n + (6 + 4 √ g) ln(24ng) + 2 ln(4m)) ≤ 10c ln 2 ηℓ + 10(ln(24)+2 ln ℓ) √ ℓ + 2 ln(20ℓ ln 2) ℓ in which c is the Lipshitz coefficient for Ξ. Also ξ = (∆ • + 2ε -1+µ+ν λ ) ln 2 ≤ (∆ • + 2ε -ln 2
3 ) ln 2, so that 2a ℓ log 2 (ξℓ) and r ℓ,m,n,g are uniformly o(ℓ) on the domain T ℓ,η . Finally ξ ≥ -η -1 ℓ ln π ℓ,m,n,g + (δ(.) + 2ε) ln 2 + Ψ(λ,µ,ν) λ = (δ(.) + 2ε) ln 2η -ln 2 ℓ r ℓ,m,n,g which ensures ξℓ ≥ 3a ℓ ln 2, and as a consequence (15), on the domain T ℓ,η , for ℓ large enough. These inequalities yield that lim ℓ (m,n,g)∈T ℓ P (H ℓ,m,n,g ≥ (∆ • + 2ε)ℓ) = 0.

Depoissonization of the length

In this Section, we derive Theorem 1 from Theorem 2, i.e. we replace the random length τ ℓ + 1 of W ℓ by the deterministic length of W n . A simple argument comes to mind: w.h.p. τ log 2 n-εn ≤ n -1 ≤ τ log 2 n+εn as long as 10, and this line of proof fails. We do not even know whether n → h(L(W n )) is stochastically increasing.

(21) ε n → +∞ and ε n = o(ln n) ; thus w.h.p. h(L(W log 2 n-εn )) ≤ h(L(W n )) ≤ h(L(W log 2 n+εn )). However, while ℓ → h(L(W ℓ )) is increasing, n → h(L(W n )) is not, see figure
In order to address these problems, let the integers α n , β n and γ n be defined by

α n = log 2 n -3ε n , β n = ⌈log 2 n -2ε n ⌉, γ n = ⌊log 2 n⌋
in which ε n meets conditions (21). Let us call long run of a word or of a necklace any maximal run that is at least α n -letters long. Consider the infinite random word W ∞ and its n-letters long prefix W n . A sequence Z = (Z i ) i≥1 of i.i.d. factors of W ∞ is defined as follows: for i ≥ 2, Z i begins just after the end of Z i-1 and, counting from the position of the first 1 of Z i , Z i stops with the α n -th 0 of the first long run after that first 1; Z 1 stops according to the same rule, but starts with the first letter of W ∞ . Each factor Z i can be written 0 Xi Y i , in which • Y i has the same distribution as W αn , cf. section 2.2,

• P (X i = k) = 2 -k-1 1 1 k≥0 ,
• Y i and X i are independent. The Lyndon word of Y i , denoted L i in what follows, is obtained by a rotation in which the right factor is 0 αn ; L i has the same distribution as L αn , cf. section 2.2. The X i 's account for the overshoots of each run not shorter than α n .

(,,,,) + Figure 11. Permuted concatenation of (T i ) 1≤i≤5 . The underlying tree L + has 3 unmarked leaves and the permutation is circular.

Definition 5. Let (T i ) 1≤i≤k be a finite sequence of planar trees, L + a planar tree with k marked leaves, naturally labeled by their rank (rank going clockwise, starting after the root), and σ a permutation of {1, 2 . . . k}. Then the tree obtained when one grafts to L + the tree T i , its root being substituted to the leaf of L + with label σ(i), for all i, is called the permuted concatenation of (T 1 , . . . , T k ) with underlying tree L + . For instance, for any integer-valued random variable N , L(Z 1 Z 2 . . . Z N ) is a permuted concatenation of the trees L(L i ). In this case the permutation is a circular one, and the underlying tree is a binary tree with N marked leaves, and N i=1 X i unmarked leaves (here these unmarked leaves are needles); thus the height of the underlying tree is at most N -1 + N i=1 X i . Consider the prefix W [n] of W ∞ obtained by concatenation of the factors Z i that are contained or overlap W n , say

W [n] = Z 1 Z 2 . . . Z N .
4.1. Lower bound. According to [START_REF] Balakrishnan | Runs and scans with applications[END_REF]p. 111,(4.19)], the position of the α nth 0 of the rth long run has expectation r2 1+αn -2 and a variance smaller than r(2 + 2 2+2αn ). So by Chebyshev's inequality, w.h.p. there exist at least 2 2εn long runs in W n , which entails successively that N ≥ 3, that L(L 2 ) is a subtree of L(W n ) and that h(L(W n )) ≥ h(L(L 2 )). For η > 0, set p n-= P h(L(Wn)) ln n ≤ ∆ ⋆η .

Thus

p n-≤ P (N ≤ 2) + P h(L(L2)) ln n ≤ ∆ ⋆η .

On the other hand, the height H i of L(L i ) has the same distribution as h(L(L αn )), thus, according to Theorem 2, for any ε > 0, for instance if 0 < ε < η, ) is a permuted concatenation of (L(L i )) 1≤i≤N , in which the underlying tree, L αn (W [n] ), has 1≤i≤N X i needles unmarked, and N marked leaves (or blades), Lemma 1 entails that:

h(L αn (W [n] )) ≤ N + max 1≤i≤N X i ,
which yields the following bound:

h(L(W [n] )) ≤ N + max 1≤i≤N X i + max 1≤i≤N H i .
Thus, if t n = o(ln n) and if n is large enough, p n+ ≤ P (N ≥ t n ) + t n P H1 ln n ≥ ∆ ⋆ + η + P max 1≤i≤tn X i > 2 log 2 t n .

Since N -1 is smaller than the number X of occurrences of the pattern 0 αn in W n , that satisfies E [X + 1] = (nα n + 1)2 -αn + 1 ≤ 2 3εn , we have P N ≥ 3 3εn ≤ ( 2 3 ) 3εn . According to Theorem 2, for η > 0,

X i > 2 log 2 t n ≤ 1 -(1 -2 t 2 n ) tn ≤ -t n ln(1 -2 t 2 n ),
and the choice t n = 3 3εn gives the desired result.

Proof of (23). Let us call huge run of a word any maximal run of 0's of its necklace that is at least β n -letters long. Let now N (resp. Ñ ) stand for the number of huge runs contained in the necklace of W n (resp. of W [n] ); as in Section 4.1, w.h.p. N and Ñ grow at least like 2 εn . We shall prove that, w.h.p., N = Ñ and that, w.h.p., the Lyndon factors L1 , L2 , . . . LN (resp. L1 , L2 , . . . LN ) induced by these huge runs have the same lexicographic order. The convention here is that L1 (or L1 for that matter) begins with the first letter of the first huge run in W n , and ends with the last letter before the second huge run in W n . This way, typically, LN (resp. LN ) straddles the end of W n (resp. W [n] ), for, in W n , or in W [n] as well, w.h.p., the run of 0's that straddles the end of the word is not huge:

• in W n the length of this run is stochastically smaller than the sum of two X i 's, thus the probability that it is huge is smaller than 2 -βn/2 ; • since W [n] ends with a run of exactly α n 0's, a run straddling the end of W [n] is huge only if the run of 0's at the beginning of W ∞ is longer than ε n , i.e. with probability 2 -εn .

Thus N = Ñ w.h.p., and Li = Li for 1 ≤ i ≤ N -1. Also, w.h.p., there exists no huge run in the last β n + √ n characters of W n , the (L( Li )) 1≤i≤N ) with the same underlying tree and the same permutation, and the height of their leaves are the same, but perhaps if the label of the leaf is a letter from LN or LN . Finally, we prove that w.h.p. at least one of the highest leaves, say v ⋆ , of L(W n ) is not labeled with a letter from the factor LN . This is due to the following facts:

(1) if 1 ≤ x n < y n ≤ n, then with a probability at least yn-xn n , at least one of the highest leaves of L(W n ) is between x n and y n ;

(2) we can choose x n , y n so that, simultaneously, 1-yn-xn n = o(1), and, w.h.p., LN does not overlap [[x n , y n ]].

Since the previous highly likely events insure that all the leaves from Li , i < N have the same height in L(W n ) and in L(W [n] ), the height of v ⋆ in L(W [n] ) is h(L(W n )), which entails (23).

Let us prove points (1) and (2). Let w be a primitive word of {0, 1} n and let w denote its necklace. Conditionnally, given that W n ∈ w , W n is uniform on w . Let Π = {Π i , 1 ≤ i ≤ k} ⊂ [[1, n]] be the set of positions of the labels of the highest leaves of L(w). The ℓ-th element of w (obtained after the permutation of a ℓ-letters long suffix of w with the corresponding nℓ-letters long prefix) fills the condition of point (1) iff ℓ ∈ [[x n , y n ]] -Π. Now [[x n , y n ]] -Π is an union of intervals of Z n with the same width y n -x n thus this reunion has exactly y n -x n +1 elements if there exists only one highest leaf (this never happens for a binary tree), but else it has more elements. It follows that for any primitive word w, P (W n meets condition (1)|W n ∈ w ) ≥ yn-xn+2 n , which takes care of point (1) for n large enough (recall e.g. [CZA10, Lemma 2.1]).

For point (2), consider the position L (resp. R) of the 0 with rank β n in the first huge run of W ∞ (resp. the position of the 0 ranked β n in the first huge run of W ∞ , going backward from the last letter of W n ). For R to be fully defined you need to see W ∞ as a doubly infinite sequence of random characters. If LN overlaps [[x n , y n ]] then Lβ n ≥ x n or R ≤ y n . Also L and n + 1 -R follow the geometric distribution of order β n (cf. [BK02, p. 17, (2.18)]) whose expectation (resp. variance) are 2 1+βn -2, 2 3+2βn (1 -(2β n + 5)2 -2-βn + 2 -2-2βn ), with the consequence that, by Chebyshev's inequality, for n large enough,

P L ≥ (1 + ρ n √ 2)2 1+βn ≤ ρ -2 n .
One can choose ρ n ≃ 2 εn so that x n = (1 + ρ n √ 2)2 1+βn = n2 -εn , and one can also take n + 1y n = x n , so that

P (L ≥ x n ) + P (R ≤ y n ) ≤ 2ρ -2
n , and 1 -yn-xn n = 2 1-εn -1 n , which proves point (2).

Figure 1 .

 1 Figure 1. a. A = {a, b} and L(a 3 b 4 ), b. A = {1, 2, . . . , 9} and L(174352698).

  n, ⌊θn⌋)/n!), Ψ(λ, µ, ν) = ln (1+µ) 1+µ µ µ

Figure 3 .Figure 4 .

 34 Figure 3. Here ℓ = 4 and a ℓ = 1. Top figure: a sample s =(n va ℓ + 1) 2≤v≤N ℓ = 12312231311111131212 of the geometric distribution, stopped before the first value larger than 3, value that is reduced to n 1 = 4, and is used as a prefix of s. Below, the corresponding Galton-Watson tree GW ℓ .

  Figure5. A sample of exponential random variables, until hitting t, and the related tree E t (in which the pink horizontal lines are to be seen as vertices rather than as edges).

Figure 6 .

 6 Figure6. A. The permutation σ = (5, 8, 6, 1, 3, 2, 4, 7). B. The heap-ordered tree H σ . C. The Lyndon tree L(0σ) built from H σ . D. The Lyndon tree L(0σ) built from f (0σ), here f (x) = 9x.

Figure 8 .

 8 Figure8. Trees S ℓ and Y ℓ-a ℓ . In S ℓ , the sign +1 marks the presence of a needle, while in Y ℓ-a ℓ the lengths of the sticks are rather 2 Yi = 1/U i : a needle occurs above the branchings ab, cd, hm, mn because, in Y ℓ-a ℓ , the corresponding first stick is at least twice longer than the second, and above hj because the factor is larger than 4.

3. 3 .

 3 Asymptotic behavior of n -1 ln π ℓ,m,n,g . 3.3.1. Heuristic considerations. For a finite or infinite sequence of non negative numbers b = (b j ) j∈I⊂N0 , let us denote |b| = j∈I b j , b = j∈I jb j , and H(b) = -j∈I b j ln(b j ), and if the entries are integers, set: b! = b i ! and |b| b = |b| ! b i ! , whenever they are defined. If |b| = 1, H(b) is the Shannon entropy of b.

3 . 3 . 3 .

 333 contains a box. Consider the two functions ∆(λ, µ) = ∆(λ, µ, 2λ ln 2) and Ψ(λ, µ) = Ψ(λ, µ, 2λ ln 2). When ∆ reaches its maximum ∆ • , the corresponding value of Ψ, Ψ • , is positive. Actually, { ∆ ≥ 5 ln 2} entails { Ψ ≥ 0.1}. The domain {(λ, µ)| ∆ > 5 ln 2} is bounded and bounded away from λ = 0. Both Ψ and ∆ are Lipschitz continuous as functions of ν on any domain (λ, µ, ν)| ∆ > 5 ln 2 and |ν -2λ ln 2| ≤ η with η not too large. This entails that D ε contains a box. Thus it contains points of the form (T, g, m)/n as long as T is large enough. If (T, g, m)/n ∈ D ε , Lemma 4 and relations (9), (10) entail that if T is large enough then (m, n, g) ∈ L T,ε . Uniform upper bound on each term of t n,g . For a sequence such that |b| = n + 1 and b = µn, the Markov inequality entails that i≤τn b i ≥ τn-µ τn n. Set F µ,n = c c i = 0 for i ≥ τ n + 1 and n ≥ |c| ≥ τn-µ τn n, c ≤ µn . Then inf b =µn b! ≥ inf c∈Fµ,n c! for the truncation, after the τ n th term, of a sequence b such that b = µn produces an element c of F µ,n such that b! ≥ c!.

  Now, following the lines of Lemma 8.3.1 in [Ash65, p. 238], one obtains that Proposition 9. If |a| ≤ 1, H (a) ≤ (|a| + a ) ln(|a| + a ) -2|a| ln |a|a ln a , ≤ H d ( a ) -2|a| ln |a|.

3. 3 . 4 .

 34 Upper bound for # { b = µn}. As in Section 3.3.1, let us see each sequence b such that b = µn as the distribution δ(r) of a sequence of integers r = (r j ) 1≤j≤n+1 such that |r| = µn, in the sense that

Figure 9 .Figure 10 .

 910 Figure 9. Domains ∆(λ, µ, ν) > 4.95 and ∆(λ, µ, ν) > 5, with x = coth(λµ) -1 λ-µ , y = λ, and z = ν.

  lim n P h(L(L2)) αn ≤ (∆ ⋆ε) ln 2 = 0which, together with the previous inequality, gives lim n p n-= 0.4.2. Upper bound. The upper bound for Theorem 1 follows at once from the next proposition:Proposition 15. For any η > 0, there exists a sequence (ε n ) that meets conditions (21), and such thatL(W n )) ≥ h(L(W [n] )) = 0.Proof of (22). Let us prove that the sequencep n+ = P h(L(W [n] )) ln n ≥ ∆ ⋆ + 2η vanishes. Since L(W [n]

  (L γn )) γ n ≥ (∆ ⋆ + η) ln 2 = 0.We can thus choose a sequence ε n that fulfills conditions (21) in such a way that 3 3εn = o(ln n) and lim n3 3εn P h(L(L γn )) γ n ≥ (∆ ⋆ + η) ln 2 = 0. But since h(L(L k )) is stochastically increasing in k, we have lim n 3 3εn P h(L(L αn )) log 2 n ≥ (∆ ⋆ + η) ln 2 = 0.Finally P max 1≤i≤tn

  -βn = o(1), and a √ n-letters long pattern does not appear twice in W n , the probability being bounded by n 2 2 - √ n = o(1). It follows that, though different, LN and LN begin with the same huge run, and have the same first √ n characters after their initial huge run. As a consequence, the outcome of the lexicographic comparison between LN (resp. LN ) and Li , being known before reading the √ n-th character of LN (resp. LN ), is the same in both cases. So, L(W n ) and L(W [n] ) are permuted concatenations of (L( Li )) 1≤i≤N (resp.

  3 ξℓ ln 2 tall vanishes with ℓ: we haveP H S ≥ 3 ξℓ ln 2 ≤ P | S| ≥ e 2 ξℓ + P H S ≥ 3 ξℓ ln 2 and | S| ≤ e 2 ξℓ≤ e -ℓ ξ + e -ξℓ+2a ℓ ln(3 ξℓ) ,

	as long as ξℓ ≥ a ℓ ln 2. This leads to
	lim ℓ

Acknowledgements

The second author thanks Julien Clément for introducing him to the probabilistic analysis of Lyndon words and trees, 10 years ago 3 , and Anne Briquet, Nicolas Broutin, Luc Devroye, Cyril Nicaud for renewing recently his interest after some years of unsuccessful attempts. Some discussions with Brigitte Chauvin were specially helpful.


Alice Hazotte
email: alice.hazotte@univ-nantes.fr

Thierry Lebeau

Peron Olivier

Saito Takumi

Abdelouas Abdesselam

Role of bacteria on the desorption of cesium from illite

Introduction

As a result of the nuclear accident in Fukushima, various radioactive elements such as cesium were dispersed in the atmosphere before being deposited on the soil within a distance of 80km around the nuclear power plant. Cesium with half-life of 30 years and properties similar to potassium accumulates in the clays, especially illite, of the upper soil horizons. Among soil remediation methods, phytoextraction is the most appropriate one as it can be achieved in situ without any change of the biophysicochemical properties of the soil. Cesium uptake by plants depends on sorption/desorption reactions to/from the soil particles and on biogeochemical processes in the rhizosphere. The coupling of bioaugmentation with phytoextraction is likely to increase the bioaccessibility of radionuclides and their accumulation in plants. Illite powder was spiked 0,1 mM or 1 mM of CsCl : after analyse by ICP-MS-HR and tyndallization of illite (3 cycles at 75 °C separated by 24h of cooling), sterile solution of CsCl (100 mM) was used for treat illite with this concentrations. Suspensions of Cs-treated illite in NaCl (0,1 mM) media and in Dworkin and Foster (DF) minimum media [START_REF] Dworkin | Experiments with microorganisms which utilize ethane and hydrogen[END_REF] were used for monitoring Cs-desorption. First, 0,04 mM citrate and 0,04 mM oxalate and then Pseudomonas fluorescens free and immobilized in dialysis membrane was tested as desorbing agents. 1 ml of suspension was taken after 1, 2, 4, 8, 24h and 2, 4, 6, 8, 10, 15 days and analysed by ICP-MS.

Conclusion et perspectives

Material and methods

Results

• Results do not provide for Cs desorption from illite by oxalic and citric acid in these concentrations.

• Citric acid and oxalic acid do not provide to remove Cs from illite. This confirms the study of [START_REF] Wendling | Cesium Desorption from Illite as Affected by Exudates from Rhizosphere Bacteria[END_REF] in which it is shown that oxalic acid and citric acid does not allow desorbing Cs illite when in low Csconcentrations [START_REF] Wendling | Cesium Desorption from Illite as Affected by Exudates from Rhizosphere Bacteria[END_REF].

Perspectives

•

Analyse illite weathering by MET and MEB to determine interlayers size before and after bacteria addition and to observe the biofilm • Use this experiment to desorbe strontium and americium from illite and then from contaminated soil.

Fig 2 :Fig 1 :Fig 2 :

 212 Fig 2 : Kinetic cesium desorption in NaCl media by free or immobilized bacteria. Initial Cs concentration in illite was approximately 0,1 mM (a) and 1 mM (b).