Manfred Madritsch

Brigitte Vallée

Modelling the LLL Algorithm by Sandpiles

come   L'archive ouverte pluridisciplinaire

Introduction

Lenstra, Lenstra, and Lovász designed the LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] in 1982 for solving integer programming problems and factoring polynomials. This algorithm belongs to the general framework of lattice basis reduction algorithms and solves a general problem: Given a basis for a lattice, how to find a basis for the same lattice, which enjoys good euclidean properties? Nowadays, this algorithm has a wide area of applications and plays a central algorithmic role in many areas of mathematics and computer science, like cryptology, computer algebra, integer linear programming, and number theory. However, even if its overall structure is simple (see Figure 1), its general probabilistic behaviour is far from being well understood. A precise quantification of the main parameters which are characteristic of the algorithms -principally, the number of iterations and the geometry of reduced bases-is yet unknown. The works of Gama, Nguyen and Stehlé [START_REF] Gama | Predicting Lattice Reduction[END_REF][START_REF] Nguyen | LLL on the average[END_REF] provide interesting experiments, which indicate that the geometry of the output seems to be largely independent of the input distribution, whereas the number of iterations is highly dependent on it. The article of Daudé and Vallée [START_REF] Daudé | An upper bound on the average number of iterations of the LLL algorithm[END_REF] provides a precise description of the probabilistic behaviour of these parameters (number of iterations, geometry of the output), but only in the particular case in which the vectors of the input basis are independently chosen in the unit ball. This input distribution does not arise naturally in applications. In summary, the first works [START_REF] Gama | Predicting Lattice Reduction[END_REF][START_REF] Nguyen | LLL on the average[END_REF] study general inputs, but do not provide proofs, whereas the second one [START_REF] Daudé | An upper bound on the average number of iterations of the LLL algorithm[END_REF] provides proofs, but for non realistic inputs. Furthermore, none of these studies is dedicated to the fine understanding of the internal structure of the algorithm. The LLL algorithm is a multidimensional extension, in dimension n, of the Euclid algorithm (obtained for n = 1) or the Gauss algorithm (obtained for n = 2). In these small dimensions, the dynamics of the algorithms is now well understood and there exist precise results on the probabilistic behaviour of these algorithms [START_REF] Vallée | Euclidean Dynamics, Discrete and Continuous Dynamical Systems[END_REF][START_REF] Vallée | Probabilistic analyses of lattice reduction algorithms[END_REF][START_REF] Vera | Analyses de l'algorithme de Gauss[END_REF] which are obtained by using the dynamical systems theory, as well as its related tools. However, even in these small dimensions, the dynamics is rather complex and it does not seem possible to directly describe the fine probabilistic properties of the internal structure of the LLL algorithm in an exact way. This is why we introduce here a simplified model of the LLL algorithm, which is based on a regularity hypothesis: Whereas the classical version deals with a decreasing factor which may vary during the algorithm, the simplified version assumes this decreasing factor to be constant. Of course, this appears to be a strong assumption, but we provide arguments towards this simplification. This assumption leads us to a classical model, the sandpile model, and this provides another argument for such a simplification. Sandpile models are instances of dynamical systems which originate from observations in Nature [START_REF] Jensen | Self-organized criticality[END_REF]. They were first introduced by Bak, Tang and Wiesenfeld [START_REF] Bak | Self-organized criticality: An explanation of the 1/f noise[END_REF] for modelling sandpile formations, snow avalanches, river flows, etc.. By contrast, the sandpiles that arise in a natural way from the LLL algorithm are not of the same type as the usual instances, and the application of sandpiles to the LLL algorithm thus needs an extension of classical results.

Plan of the paper. Section 1 presents the LLL algorithm, describes a natural class of probabilistic models, and introduces the simplified models, based on the regularity assumption. Section 2 provides arguments for the regularity assumption. Then, Section 3 studies the main parameters of interest inside the simplified models, namely the number of iterations, the geometry of reduced bases, and the independence between blocks. Section 4 then returns to the actual LLL algorithm, within the probabilistic models of Section 1, and exhibits an excellent fitting between two classes of results : the proven results in the simplified model, and the experimental results that hold for the actual LLL algorithm. This explains why these "regularized" results can be viewed as a first step for a probabilistic analysis of the LLL algorithm.

1 The LLL algorithm and its simplified version.

1.1. Description of the algorithm. The LLL algorithm considers a Euclidean lattice L given by a system B of n linearly independent vectors in the ambient space R p (n ≤ p). It aims at finding a reduced basis B formed with vectors that are almost orthogonal and short enough. The algorithm operates with the matrix P which expresses the system B as a function of the Gram-Schmidt orthogonalized system B * ; the generic coefficient of the matrix P is denoted by m i,j . The lengths ℓ i of the vectors of the basis B ⋆ and the ratios r i between successive ℓ i , i.e.

r i := ℓ i+1 ℓ i , with ℓ i := b ⋆ i . (1)
play a fundamental role in the algorithm. The algorithm aims at obtaining lower bounds on these ratios, by computing a s-Siegel reduced basis B that fulfills, for

any i ∈ [1..n -1], the Siegel condition S s (i), | m i+1,i | ≤ 1 2 , r i := ℓ i+1 ℓ i ≥ 1 s , with s > s 0 = 2 √ 3 . (2)
In the classical LLL algorithm, a stronger condition, the Lovasz condition L t (i), The version of the LLL algorithm studied here directly operates with the Siegel conditions (2). However, the behaviours of the two algorithms are similar, as it is shown in [START_REF] Akhavi | Random lattices, threshold phenomena and efficient reduction algorithms[END_REF], and they perform the same two main types of operations:

| m i+1,i | ≤ 1 2 , ℓ 2 i+1 + m 2 i+1,i ℓ 2 i ≥ 1 t 2 ℓ 2 i (with t > 1), (3)
(i) Translation (i, j) (for j < i). 1 The vector b i is translated with respect to the vector b j by : b i := b i -⌊m i,j ⌉b j , with ⌊x⌉ := the integer closest to x. This translation does not change ℓ i , and entails the inequality |m i,j | ≤ (1/2).

(ii) Exchange (i, i + 1). When the condition S s (i) is not satisfied, there is an exchange between b i and b i+1 , which modifies the lengths ℓ i , ℓ i+1 . The new value ľi is multiplied by a factor ρ and satisfies

ľ2 i := ℓ 2 i+1 +m 2 i+1,i ℓ 2 i , so that ľi = ρ ℓ i with ρ 2 = ℓ 2 i+1 ℓ 2 i +m 2 i+1,i , (4)
while the determinant invariance implies the relation ľi ľi+1 = ℓ i ℓ i+1 , hence the equality ľi+1 = (1/ρ) ℓ i+1 . This entails that ρ defined in (4) satisfies

ρ ≤ ρ 0 (s) with ρ 2 0 (s) = 1 s 2 + 1 4 < 1; (5)
The "decreasing factor" ρ plays a crucial rôle in the following. Figure 1 describes the standard strategy for the LLL algorithm, where the index i is incremented or decremented at each step. However, there exist other strategies which perform other choices for the next position of reduction, which can be any index i for which Condition S s (i) does not hold (See Section 2). Each execution conducted by a given strategy leads to a random walk. See Figure 9 for some instances of random walks in the standard strategy.

i := 1; While i < n do If b qi -b qi+1 ≤ 1, then i := i + 1 else qi := qi -α; qi+1 := qi+1 + α; i := max(i -1, 1); Figure 1
. Two versions of the LLL algorithm. On the left, the classical version, which depends on parameters s, ρ, with ρ0(s) defined in [START_REF] Daudé | An upper bound on the average number of iterations of the LLL algorithm[END_REF]. On the right, the additive version, which depends on the parameter α :=log s ρ, with α0 :=log s ρ0(s).

What is known about the analysis of the LLL algorithm?

The main parameters of interest are the number of iterations and the quality of the output basis. These parameters depend a priori on the strategy. There are classical bounds, which are valid for any strategy, and involve the potential D(B) and the determinant det B defined as

D(B) = n i=1 ℓ i i , det(B) = n i=1 ℓ i .
Number of iterations. This is the number of steps K where the test in step 2 is negative. There is a classical upper bound for K which involves the potential values, the initial one D(B) and the final one D( B), together with the constant ρ 0 (s) defined in [START_REF] Daudé | An upper bound on the average number of iterations of the LLL algorithm[END_REF]. We observe that K can be exactly expressed with the potential values and the mean α of the values α :=log s ρ used at each iteration

K(B) = 1 α(B) log s D(B) D( B) , so that K(B) ≤ 1 α 0 log s D(B) D( B) , (6)
where α 0 :=log s ρ 0 (s) is the minimal value of α.

Quality of the output. The first vector b 1 of a s-Siegel reduced basis B is short enough; there is an upper bound for the ratio γ(B) between its length and the n-th root of the determinant,

γ(B) := || b 1 || det(B) 1/n ≤ s (n-1)/2 . ( 7
)
The two main bounds previously described in ( 6) and ( 7) are worst-case bounds, and we are interested here in the "average" behaviour of the algorithm: What are the mean values of the number K of steps and of the output parameter γ?

1.3. Our probabilistic model. We first define a probabilistic model for input bases, which describe realistic instances, of variable difficulty. We directly choose a distribution on the actual input instance, which is formed with the coefficients m i,j of the matrix P, together with the ratios r i . As Ajtai in [START_REF] Ajtai | Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem[END_REF], we consider lattice bases of full-rank (i.e, n = p) whose matrix B is triangular: in this case, the matrix P and the ratios r i are easy to compute as a function of b i := (b i,j ),

r i = b i+1,i+1 b i,i , m i,j = b i,j b j,j .
Furthermore, it is clear that the main parameters are the ratios r i , whereas the coefficients m i,j only play an auxilliary rôle. As Ajtai suggests it, we choose them (for j < i) independently and uniformly distributed in the interval [-1/2, +1/2]. Since Ajtai is interested in worst-case bounds, he chooses very difficult instances where the input ratios r i are fixed and very small, of the form r i ∼ 2 -(a+1)(2n-i) a with a > 0. Here, we design a model where each ratio r i is now a random variable which follows a power law :

∀i ∈ [1..n -1], ∃θ i > 0 for which P [r i ≤ x] = x 1/θi for x ∈ [0, 1]. ( 8
)
This model produces instances with variable difficulty, which increases when the parameters θ i become large. This distribution arises in a natural way in various frameworks, in the two dimensional case [START_REF] Vallée | Probabilistic analyses of lattice reduction algorithms[END_REF] or when the initial basis is uniformly chosen in the unit ball. See [START_REF] Vera | Analyses de l'algorithme de Gauss[END_REF] for a discussion about this probabilistic model.

An additive version.

First, we adopt an additive point of view, and thus consider the logarithms of the main variables (log s is the logarithm to base s),

q i := log s ℓ i , c i := -log s r i = q i -q i+1 α := -log s ρ, (9)
Then, the Siegel condition becomes q i ≤ q i+1 + 1 or c i ≤ 1, and the exchange in the LLL algorithm is rewritten as (see Figure 1. right)

If q i > q i+1 + 1, then [ qi = q i -α, qi+1 = q i+1 + α]. (10)
In our probabilistic model, each c i follows an exponential law of the form

P[c i ≥ y] = s -y/θi for y ∈ [0, +∞[ with E[c i ] = θ i log s . ( 11
)
This model is then called the Exp-Ajtai(θ) model. Remark that, if we restrict ourselves to non-reduced bases, we deal with the Mod-Exp-Ajtai(θ) distribution,

P[c i ≥ y + 1] = s -y/θi for y ∈ [0, +∞[, with E[c i ] = 1 + θ i log s . (12)
1.5. The regularized version of the LLL algorithm. The main difficulty of the analysis of the LLL algorithm is due to the fact that the decreasing factor ρ defined in (4) can vary throughout the interval [0, ρ 0 (s)]. For simplifying the behaviour of the LLL algorithm, we assume that the following Regularity Hypothesis holds (R): (R). The decreasing factor ρ (and thus its logarithm α :=log s ρ) are constant.

Then, Equation (10) defines a sandpile model which is studied in Section 3.

There are now three main questions:

-Is Hypothesis (R) reasonable? This is discussed in Section 2.

-What are the main features of the regularized versions of the LLL algorithm, namely sandpiles? This is the aim of Section 3.

-What consequences can be deduced for the probabilistic behaviour of the LLL algorithm? This is done in Section 5 that transfers results of Section 4 to the framework described in Section 2 with the arguments discussed in Section 4.

2 Is the LLL algorithm regular?

2.1. General bounds for α. Since the evolution of the coefficients m i+1,i seems less "directed" by the algorithm, we may suppose them to be uniformly distributed inside the [-1/2, +1/2] interval, and independent of the Siegel ratios.

The average of the square m 2 is then equal to 1/12, and if we assume m 2 to be constant and equal to 1/12, then the value of α satisfies (with s near

s 0 = 2/ √ 3), - 1 2 log s0 3 4 + 1 12 ≤ α := - 1 2 log s0 r 2 + 1 12 ≤ - 1 2 log s0 1 12 .
Then α ∈ [0.5, 8.5] most of the time. This fits with our experiments.

2.2. General study of parameter α. We must make precise the regularity assumption. Of course, we cannot assume that there is a universal value for α :=log s ρ, and we describe the possible influence of four variables on the parameter α, when the dimension n becomes large: We consider three main strategies Σ : -The standard strategy Σ s chooses i := Min N (j) -The random strategy Σ r chooses i at random in N (j) -The greedy strategy Σ g chooses the index i ∈ N (j) for which the ratio r i is minimum.

The study of α decomposes into two parts. First, we study the variations of α during one execution, due to the position i or the time j. Second, we consider the variable α, defined as the mean value of α during one execution, and study the influence of the input distribution, the strategy, and the dimension on α.

We consider a set B of input bases, and we determine a maximal value M of α for this set of inputs. In order to deal with fixed intervals for positions, times, and values, we choose three integers X, Y, Z, and we divide -the interval [1.

.n] of positions into X equal intervals of type

I x with x ∈ [1..X], -the interval [1..K] of times into Y equal intervals of type J y with y ∈ [1..Y ], - the interval [0, M ] of values into Z equal intervals. of type L z with z ∈ [1..Z]
Then the parameters α x , α y are respectively defined as the restriction of α for i ∈ I x , (resp. for j ∈ J y ).

Distribution of the variable α.

Here, the parameter Θ of the input distribution and the strategy Σ ∈ {Σ s , Σ r , Σ g } are fixed, . and we consider a set N of dimensions. We first consider the global variable α, study its distribution, [START_REF] Boneh | Cryptanalysis of RSA with private key d less than N ≤ 0.292[END_REF] The curves are associated to • for Σs (standard), for Σg (greedy), and for Σr (random). On the right, the functions x → A x . In the middle, the functions y → α y . On the left, the distribution of α. and its mean, for each n ∈ N [See Figure 2(1)]. We observe that the distribution of α gets more and more concentrated when the dimension grows, around a value which appears to tend to 2.5.

2.4.

Variations of α during an execution. Figure 2(2) describes the two functions x → α x and y → α y , for each dimension n ∈ N . Figure 2(3) provides (for n = 20) a description of the distribution of parameters α x , α y for various values of (x, y). We observe that the variations of the functions y → α y and x → α x are small, and become smaller when the dimension n increases. The distributions of α x and α y are also concentrated, at least for y's not too small and for central values of x.

Influence of the strategy.

Here, for n = 20, we investigate the influence of the strategy on the functions

x → A x , y → α y , z → P[α ∈ L z ].
The experimental results, reported in Figure 2(4), show the important influence of the strategy on the parameter α. They are of independent interest, since, to the best of our knowledge, the strategy is not often studied. There are two groups: On the one hand, the standard strategy2 is the least efficient: it performs a larger number of steps, and deals with a parameter α whose value is concentrated below α = 5. On the other hand, the other two ones, (random and greedy) are much more efficient, with a much smaller number of steps; they deal with values of α which vary in the whole interval [START_REF] Daudé | An upper bound on the average number of iterations of the LLL algorithm[END_REF]20] and decrease with the discrete time. These two strategies (random and greedy) must be used if we wish more efficient algorithms. If we wish simulate with sandpiles the LLL algorithm under these two strategies, we have to consider different values of α, for instance, at the beginning, in the middle and at the end of the execution.

2.6. Influence of the input distribution. We study the influence of the parameter Θ of the Exp-Ajtai distribution on α. We first recall what happens in two dimensions, where the LLL algorithm coincides with the Gauss algorithm. The paper [START_REF] Vallée | Probabilistic analyses of lattice reduction algorithms[END_REF] studies this algorithm when the input c :=log s r follows an exponential law with mean θ and proves that the number of steps K of the Gauss algorithm follows a geometric law of ratio λ(1 + 1/θ), where λ(s) is the dominant eigenvalue of the transfer operator associated to the Gauss algorithm.

The relations

-log s P[K ≥ k] ∼ -log s P [c ≥ kα] ∼ E θ [α] θ k entail that the mean E θ [α] depends on θ as E θ [α] ∼ -θ log s λ 1 + 1 θ .
Then, properties of the pressure3 imply that the function

E θ [α] satisfies E θ [α] ∼ |λ ′ (1)| log s for θ → ∞, and E θ [α] ∼ 2 log s log(1 + √ 2) for θ → 0,
where |λ ′ (1)| ∼ 3.41 equals the entropy of the Euclid centered algorithm. This entails that, in two dimensions, the mean value E[α] varies in the interval [START_REF] Vera | Analyses de l'algorithme de Gauss[END_REF]23].

Led by the dynamical point of view, we set a conjecture which extends the previous two-dimensional property to any dimensions.

Entropy Conjecture. Consider the probabilistic Exp-Ajtai(θ) model in n dimensions. Then, for θ → ∞, the mean of the variable α tends to the entropy E n of the dynamical system underlying the LLL algorithm.

lim θ→∞ E (θ,n) [α] = E n log s
3 Study of the sandpile model.

There are three main questions about the RLLL algorithm : (Q1) Does the RLLL algorithm depend on the strategy? (Q2) How does the behaviour of the RLLL algorithm depend on the value of parameter α? What about the number of iterations? the output configuration? Are there lower bounds on average in relations ( 6) and ( 7)? (Q3) Does there exist a characterisation for two blocks to be independent in the RLLL algorithm? We can run the execution of the LLL algorithm, both on the block B -formed with the first vectors and on the block B + formed on the last vectors The two blocks B -and B + are said to be independent if the total basis formed by concatening the two reduced bases B -and B + is reduced.

Here, we answer these three main questions. As we already said previously, the additive version of the regularized algorithm (see Figure 1.right) deals with the sandpile model. Even if this model is very well known, the modelling of the RLLL algorithm gives rise to non classical instances of sandpile models.

Main objects for sandpiles.

Here, H, h denote strictly positive real numbers. A sandpile model Q n (q, H, h) describes all the possible evolutions of the configuration q = (q 1 , . . . , q n ) under the action of functions f i

f i (q) =     
q jh if j = i and q iq i+1 > H, q j + h if j = i + 1 and q iq i+1 > H, q j else. We associate to q := (q 1 , . . . , q n ) the configuration c := ∆(q) formed with the differences between the components,

c i = q i -q i+1 for i ∈ [1..n -1].
The strategy graph, denoted by G(q, H, h), is a directed graph whose vertices are all the configurations that are reachable from q; there is an edge from u to v (with u = v) if there exists an index i ∈

[1..n -1] for which v = f i (u).
The energy E and the total mass M of the configuration q are defined by

E(q) = n i=1 i • q i , and M (q) = n i=1 q i , (13)
and satisfy M (f i (q)) = M (q), E(f i (q)) = E(q) + h.

3.2.

Various kinds of sandpiles. The usual sandpiles are basic and decreasing:

Definition 1. (i) A sandpile q is basic if the configuration ∆(q) is integral and parameters (H, h) equal (1, 1) (ii) A sandpile is (H, h)-integral if the components c i of c := ∆(q) belong to the same discrete line H + Zh (iii) A basic sandpile q is decreasing if the components of c := ∆(q) are positive (c i ≥ 0). It is strictly decreasing if c is strictly positive. On the contrary, it is increasing if all the components of c are negative.

The sandpiles used in the RLLL algorithm are not basic. However, the following result shows that any general sandpile is isomorphic to a basic sandpile.

Proposition 1. The mapping ψ : q → q ′ defined by

c ′ i := 1 - H -c i h , q ′ n = 0 ( 14
)
transforms a general sandpile into a basic sandpile. Moreover, the two graphs G(q, H, h) and G(ψ(q), 1, 1) are isomorphic.

A general sandpile q is decreasing (resp. strictly decreasing, increasing) if ψ(q) is decreasing (resp. strictly decreasing, increasing). A general sandpile decomposes into strictly decreasing configurations, separated by increasing configurations.

Definition 2. Two adjacent strictly decreasing sandpiles q -, q + are independent if the configuration obtained by concatening the two final configurations q -and q + is a final configuration.

Study of a general sandpile.

Here, we obtain (easy) extensions of results of Goles and Kiwi who considered only in [START_REF] Goles | Games on line graphs and sandpiles[END_REF] basic decreasing sandpiles.

Theorem 1. The following holds for any sandpile Q(q, H, h): (i) The graph G(q, H, h) is finite, with a unique final configuration q. The length of a path q → q is the same for any path. This is the number of steps T (q),

T (q) = 1 h [E( q) -E(q)] = 1 2h n-1 i=1 i(n -i) (c i -c i ) (ii) If Q n (q, H, h
) is decreasing, then the components of the output configuration c satisfy H -2h < c i ≤ H, and the number of iterations satisfy

0 ≤ T (q) - 1 2h n-1 i=1 i(n -i) (c i -H) ≤ 2A(n) with A(n) := n n 2 -1 12
(iii) If Q n (q, H; h) is strictly decreasing, then there exists j ∈ [1..n-1] for which ∀i = j, Hh < c i ≤ H, and H -2h < c j ≤ Hh, and the number of steps T (q) satisfies

0 ≤ T (q) -A(n) + 1 2h n-1 i=1 i(n -i) (c i -H) ≤ 1 8 n 2
(iv) For a general sandpile Q n (q, H, h), the output configuration satisfies

H -2h < c i ≤ H if c i > H -h, c i ≥ c i if c i ≤ H -h and the number of steps T (q) satisfies 1 2h n-1 i=1 i(n -i)(c i -H + h) ≤ T (q) ≤ 1 2h n-1 i=1 i(n -i) max(c i -H + h, 0) (v)
A sufficient condition for two adjacent sandpiles Q p (q -, H, h), Q n (q + , H, h) to satisfy the independence condition of Definition 2 is

1 p M (q -) - 1 n M (q + ) ≤ n + p 2 (H -h) -h
and for a sandpile (H, h)-integral:

1 p M (q -) - 1 n M (q + ) ≤ n + p 2 H -2h.
4 Returning to lattices.

We now return to the LLL algorithm, with the framework of Section 1, and apply the results of Section 3 to the so-called ρ-regular executions of the LLL algorithm, for which the decreasing factor is constant and equal to ρ. We recall that, in this case, the execution of the algorithm in dimension n can be viewed as a sandpile model Q n (q, 1, α) associated to a parameter α :=log s ρ, and an initial configuration q related to the lengths ℓ i of the orthogonalised basis B ⋆ of the input basis B via the equalities q i := log s ℓ i . The main objects associated to the basis B, namely the potential D(B) or the determinant det(B) are then related to the energy E(q) or the total mass M (q), E(q) = log s D(B), M (q) = log s det(B).

We are interested in two kinds of input bases: (i) We first study totally non-reduced bases, for which Condition S s (i) is never satisfied on the input. In this case, the sandpile is strictly decreasing. [Sections 4.1 and 4.2] (ii) We then study a general input basis, which is a sequence of blocks, some of them are totally non-reduced, and other ones are totally reduced [Section 4.3]

We compare here the results that are proven for regular executions of the LLL algorithm, (by an easy transfer of results of Section 3) and the experimental results that are performed on general executions of the algorithm. We will see that there is a good fitting between these two kinds of results. This good fitting has two main consequences:

-This provides an indirect validation of the property : "The executions of the LLL algorithm are very often regular enough".

-This shows that long experiments on the LLL algorithm can be simulated by fast computations in the sand pile model (with a good choice of parameter α).

As in Section 3, we study the final configurations, the number of steps, and the independence of blocks.

4.1. Final configurations. When the initial basis is totally non reduced, the sandpile is strictly decreasing. Then, with Theorem 1 (ii), each output Siegel ratio r i and the first vector of the output basis satisfy

ρs ≤ 1 r i = ℓ i ℓ i+1 ≤ s, ρ(s • ρ) (n-1)/2 ≤ γ( B) = || b 1 || (det L) 1/n ≤ s (n-1)/2 . (15)
Then, we have proven:

Theorem 2. Consider a totally non reduced basis B on which the execution of the LLL algorithm is ρ-regular. Then, the output parameter γ( B) defined in ( 7)

satisfies 2 n -1 log s γ( B) ∈ [1 -α, 1], with α := -log s ρ.
This is compatible with experiments done on general executions by Nguyen and Stehlé [START_REF] Nguyen | LLL on the average[END_REF], which show that there is a mean value β ∼ 1.04 , such that, for most of the output bases B, the ratio γ( B) is close to β (n-1)/2 . The relation β ∼ s √ ρ is then plausible, so that the "usual" ρ would be close to 0.81.

Number of iterations.

Suppose that the (totally non reduced) input basis follows the Mod-Exp-Ajtai(θ) distribution. Then, the configuration c ′ associated to c via Theorem 1 follows a geometric law,

P[c ′ i ≥ 1 + k] = ρ k/θ , E[c ′ i -1] = ρ 1/θ 1 -ρ 1/θ ,
and Theorem 1 (iii) entails: Theorem 3. Consider an input basis B, which follows the Mod-Exp-Ajtai distribution of parameter θ. If the execution of the LLL algorithm in dimension n is ρ-regular on the basis B, the number of iterations satisfies

K n (ρ, θ) ∼ n 3 12α ρ 1/θ 1 -ρ 1/θ (n → ∞).
If the Entropy Conjecture of Section 3.6 is true, then

lim θ→∞ K n (θ) ∼ θ log s 12 n 3 E 2 n
where E n is the entropy of the LLL algorithm.

This results fits with the experiments done for general executions of the LLL algorithm by Nguyen and Stehlé [START_REF] Nguyen | LLL on the average[END_REF]. In particular, for the choice of Ajtai, namely θ = n a , the experiments show a number of iterations of order Θ(n 3+a ).

4.

3. An instance of the independence property. The question of the independence between blocks is important. We now describe such an instance of this phenomenon in the framework of Coppersmith's method. In the paper [START_REF] Boneh | Cryptanalysis of RSA with private key d less than N ≤ 0.292[END_REF], Boneh and Durfee present a method for breaking the RSA cryptosystem based on Coppersmith's method. Coppersmith's method uses the LLL algorithm in order to find a small root of a polynomial modulo an integer E. For the cryptanalysis of RSA, one deals with the public exponent E. We let L := log s E.

The initial configuration is formed with m + 1 blocks, indexed from k = 0 to m. The k-th block has length k + 1, is (1, α)-integral, and the components c i of the configuration c are equal to L/2. However, the total configuration is not totally decreasing, but the (second) sufficient condition of Theorem 1 (v) is always true. Then, Theorem 1(v) entails:

Theorem 4. Suppose that the execution of the LLL algorithm is ρ-regular on the Coppersmith lattice described in [START_REF] Boneh | Cryptanalysis of RSA with private key d less than N ≤ 0.292[END_REF]. Then, the blocks of the lattice are always independent, and the reduction can be done in parallel on each block. The number of iterations K p performed in this parallel strategy is then

K p = m 3 12α L 2 -1 to be compared to K s = m i=1 K i ∼ m 4 48α L 2 -1 ,
which is the number of steps in the sequential strategy. Of course, the execution of the LLL algorithm on the Boneh-Durfee lattice cannot be totally regular : the first vector of the reduced lattice basis would be the first vector of the initial basis, and the method would fail! However, it is possible to compare (see [START_REF] Georgieva | Étude expérimentale de l'algorithme LLL sur certaines bases de Coppersmith[END_REF]) the result of Theorem 4 to an execution of the actual LLL algorithm on a Boneh-Durfee lattice (see Figure 3 left). We first see that, on each block, the number of iterations is quite large (the blocks are totally non reduced) and this fits with the order Θ(k 3 ) which is proven for a ρ-regular execution. We also remark that the blocks are not independent but almost independent: the basis obtained by concatening the reduced bases of each block is not totally reduced, but few reduction steps are needed for reducing it, as Figure 3 (right) shows it. Such a strategy, whose first step can be performed in a parallel way, is very efficient in this case Conclusion. This paper presents a simplified model of the LLL algorithm, under a "regularity" hypothesis which assumes that the decreasing factor ρ is constant. Of course, this hypothesis does not exactly hold in the reality, and we have provided experimental results about its validity. We have also explained why this simplified model is very useful for understanding the LLL algorithm in an intuitive way, and for testing (at least qualitative) conjectures on the algorithm. The excellent fitting of this model on a class of Coppersmith lattices is also striking.

In fact, the sandpile model represents a good compromise between simplicity and adequation to the reality.

  (a) The input distribution of Exp-Ajtai type is described by Θ = (θ 1 , . . . , θ n-1 ). (b) The position i ∈ [1..n(B) -1] is the index where the reduction occurs. (c) The discrete time j ∈ [1..K(B)] is the index when the reduction occurs, (d) The strategy defines the choice of the position i at the j-th iteration, inside the set N (j) which gathers the indices for which Condition S(i) is not satisfied.

1 ( 1 )( 2 ) 5 ( 3 )

 11253 The distribution of the parameter α for n = 5 (•); n = 10 ( ); n = 15 ( ); n = 20 ( ) The two functions y → α y (left, with Y = 20) and x → α x (right, with X = 5), for n = 5 (•); n = 10 ( ); n = 15 ( ); n = 20 ( ) On the left, the distribution of α y with Y = 20 and y = 2 (•); 5 ( ); 10 ( ); 15 ( ); 20 ( ) On the right, the distribution of α x with X = 5 and x = 1 (•); 2 ( ); 3 ( ); 4 ( ); 5 ( )

Figure 2 .

 2 Figure 2. Experiments about the Regularity Hypothesis: Study of the global parameter α. Influence of position and time. Influence of the strategy for n = 20.

Figure 3 .

 3 Figure 3. On the left, the random walk of the actual LLL algorithm on a Coppersmith lattice of dimension 21 (related to m = 5). On the right, the random walk of the execution of the LLL algorithm on the basis formed by the concatenation of the reduced blocks.

  must be fulfilled for all i ∈ [1..n -1]. When s and t are related by the equality 1/t 2 = (1/4) + 1/s 2 , Condition L t (i) implies Condition S s (i).

In the usual LLL algorithm, all the translations (i + 1, j) are performed at each step when the condition Ss(i) is satisfied. These translations do not change the length ℓi+1, but are useful to keep the length of bi+1 small. Here, we look at the trace of the algorithm only on the ℓi, and the translations (i + 1, j), with j < i, are not performed.

We have not reported the results relative to the anti-standard strategy which chooses i := Max N (j), but they are of the same type as the standard one.

In dynamical systems theory, the pressure is the logarithm of the dominant eigenvalue.

Acknowlegments. This research was supported by the LAREDA Project (LAttice REDuction Algorithms: Dynamics, Probability, Experiments) of the ANR (French National Research Agency). The authors thank Ali Akhavi, Julien Clément, Mariya Georgieva, Fabien Laguillaumie, Loïck Lhote, Damien Stehlé, Antonio Vera, and the whole group LAREDA for interesting discussions on the subject.


Mathieu Roux Lmno
email: mathieu.roux@unicaen.fr

Brigitte Vallée
email: brigitte.vallee@unicaen.fr

Information theory : Sources, Dirichlet series, and realistic analyses of data structures

Most of the text algorithms build data structures on words, mainly trees, as digital trees (tries) or binary search trees (bst). The mechanism which produces symbols of the words (one symbol at each unit time) is called a source, in information theory contexts. The probabilistic behaviour of the trees built on words emitted by the same source depends on two factors: the algorithmic properties of the tree, together with the information-theoretic properties of the source. Very often, these two factors are considered in a too simplified way: from the algorithmic point of view, the cost of the Bst is only measured in terms of the number of comparisons between words -from the information theoretic point of view, only simple sources (memoryless sources or Markov chains) are studied. We wish to perform here a realistic analysis, and we choose to deal together with a general source and a realistic cost for data structures: we take into account comparisons between symbols, and we consider a general model of source, related to a dynamical system, which is called a dynamical source. Our methods are close to analytic combinatorics, and our main object of interest is the generating function of the source Λ(s), which is here of Dirichlet type. Such an object transforms probabilistic properties of the source into analytic properties. The tameness of the source, which is defined through analytic properties of Λ(s), appears to be central in the analysis, and is precisely studied for the class of dynamical sources. We focus here on arithmetical conditions, of diophantine type, which are sufficient to imply tameness on a domain with hyperbolic shape.

Plan of the paper. We first recall in Section 1 general facts on sources and trees, and define the probabilistic model chosen for the analysis. Then, we provide the statements of the main two theorems (Theorem 1 and 2) which establish the possible probabilistic behaviour of trees, provided that the source be tame. The tameness notions are defined in a general framework and then studied in the case of simple sources (memoryless sources and Markov chains). In Section 2, we focus on a general model of sources, the dynamical sources, that contains as a subclass the simple sources. We present sufficient conditions on these sources under which it is possible to prove tameness. We compare these tameness properties to those of simple sources, and exhibit both resemblances and differences between the two classes.

1 Probabilistic behaviour of trees built on general sources.

1.1. General sources. Throughout this paper, an ordered (possibly infinite denumerable) alphabet Σ := {a 1 , a 2 , . . . , a r } is fixed.

A probabilistic source, which produces infinite words of Σ N , is specified by the set {p w , w ∈ Σ ⋆ } of fundamental probabilities p w , where p w is the probability that an infinite word begins with the finite prefix w. It is furthermore assumed that π k := sup{p w : w ∈ Σ k } tends to 0, as k → ∞.

As it is usual in the domain of analytic combinatorics, well described in [START_REF] Flajolet | Analytic Combinatorics[END_REF], our analyses involve the generating function of the source, here of Dirichlet type, first introduced in [START_REF] Vall Ée | Dynamical sources in information theory: Fundamental intervals and word prefixes[END_REF] and defined as

Λ(s) := ∑ w∈Σ ⋆ p s w , Λ (k) (s) := ∑ w∈Σ k p s w . (1)
Since all the equalities Λ (k) (1) = 1 hold, the series Λ(s) is divergent at s = 1, and the probabilistic properties of the source can be expressed in terms of the regularity of Λ near s = 1, as it is known from previous works [START_REF] Vall Ée | Dynamical sources in information theory: Fundamental intervals and word prefixes[END_REF] and will be recalled later. For instance, the entropy h(S ) relative to a probabilistic source S is defined as the limit (if it exists) that involves the previous Dirichlet series

h(S ) := lim k→∞ -1 k ∑ w∈Σ k p w log p w = lim k→∞ -1 k d ds Λ (k) (s) | s=1 . (2)
1.2. Simple sources: memoryless sources and Markov chains. A memoryless source, associated to the (possibly infinite) alphabet Σ, is defined by the set (p j ) j∈Σ of probabilities, and the Dirichlet series Λ, Λ (k) are expressed with

λ (s) = ∑ i∈Σ p s i , under the form Λ (k) (s) = λ (s) k , Λ(s) = 1 1 -λ (s) . (3)
A Markov chain associated to the finite alphabet Σ, is defined by the vector R of initial probabilities (r i ) i∈Σ together with the transition matrix P := [(p i| j ) (i, j)∈Σ×Σ ]. We denote by P(s) the matrix with general coefficient p s i| j , and by R(s) the vector of components r s i . Then

Λ(s) = 1 + t 1 • (I -P(s)) -1 • R(s). ( 4
)
If, moreover, the matrix P is irreducible and aperiodic, then, for any real s, the matrix P(s) has a unique dominant eigenvalue λ (s).

In both cases, the entropy satisfies h(S ) = -λ ′ (1).

1.3. The first main data structure: the trie. A trie is a tree structure which is used as a dictionary in various applications, as partial match queries, text processing tasks or compression. This justifies considering the trie structure as one of the central general purpose data structures of Computer Science. See [START_REF] Gonnet | Handbook of Algorithms and Data Structures: in Pascal and C[END_REF] or [START_REF] Sedgewick | Algorithms in C, Parts 1-4[END_REF] for an algorithmic study of this structure.

The trie structure compares words via their prefixes: it is based on a splitting according to symbols encountered. If X is a set of (infinite) words over Σ, then the trie associated to X is defined recursively by the rule: Trie(X ) is an internal node where are attached the tries Trie(X \ a 1 ), Trie(X \ a 2 ), . . . , Trie(X \ a r ). Here, the set X \ a denotes the subset of X consisting of strings that start with the symbol a stripped of their initial symbol a; recursion is halted as soon as X contains less than two elements: if X is empty, then Trie(X ) is empty; if X has only one element X, then Trie(X ) is a leaf labelled with X.

For |X | = n, the trie Trie (X ) has exactly n branches, and the depth of a branch is the number of (internal) nodes that it contains. The path-length equals the sum of the depth of all branches: this is the total number of symbols that need to be examined in order to distinguish all elements of X . Divided by the number of elements, it is also by definition the cost of a positive search (i.e. searching for a word that is present in the trie). The size of the tree is the number of its internal nodes. Adding to the size, the cardinality of X gives the number of prefixes necessary to isolate all elements of X . It gives also a precise estimate of the place needed in memory to store the trie in a real-life implementation. In this paper, we focus on two trie parameters: the size and the path-length.

1.4. The second main data structure: the binary search tree (Bst). We revisit here this wellknown structure. Usually, this kind of tree contains keys and the path length of this tree measures the number of key comparisons that are needed to build the tree, and sort the keys by a method closely related to QuickSort. This usual cost -the number of key comparisons-is not realistic when the keys have a complex structure, in the context of data bases or natural languages, for instance. In this case, it is more convenient to view a key as a word, and now, the cost for comparing two words (in the lexicographic order) is closely related to the length of their largest common prefix, called the coincidence.

The convenient cost of the bst is then the total number of symbol comparisons between words that are needed to build it; this is a kind of a weighted path length, called the symbol path-length of the Bst, also equal to the total symbol cost of QuickSort. For instance, for inserting the key F in the Bst of Figure 1, the number of key comparisons equals 3, whereas the number of symbol comparisons equals 18 (7 for comparing F to A, 8 for comparing F to B and 1 for comparing F to C). This is this symbol path length that is studied in the following.

Figure 1: On the left, a trie built on sixteen words of {a, b} ⋆ . On the right, a binary search tree built on seven words of {a, b} ⋆ .

1.5. Average-case analysis: exact expressions of the three mean costs. The average-case analysis of structures (or algorithms) aims characterizing the mean value of their parameters under a well-defined probabilistic model that describes the initial distribution of its inputs. Here, we adopt the following quite general model: we work with a finite sequence X of infinite words independently produced by the same general source S , and we wish to estimate the mean value of the parameters when the cardinality n of X becomes large. Here, in the paper, we focus on three main parameters, two for Trie(X ) and one for Bst(X ). When restricted to simple sources, there exist many works that study the trie parameters (see [START_REF] Flajolet | The ubiquitous digital tree[END_REF][START_REF] Jacquet | Analysis of digital tries with Markovian dependency[END_REF][START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Szpankowski | Average-Case Analysis of Algorithms on Sequences[END_REF]) or the symbol path length for Bst (see [START_REF] Fill | The number of bit comparisons used by Quicksort: An average-case analysis[END_REF]). The same studies, in the case of a general source, are done in [START_REF] Cl Ément | Dynamical sources in information theory: A general analysis of trie structures[END_REF] for the Trie and in [START_REF] Vall Ée | The number of symbol comparisons in Quick-Sort and QuickSelect[END_REF] for the Bst, and are summarized as follows:

Theorem 1 [Clément, Fill, Flajolet, Vallée]. Let S be a general source. Consider a finite sequence X of n infinite words independently produced by S . Then the expectations of the size R of Trie(X ), the path length C of Trie(X ), the symbol path-length B of the binary search tree Bst(X ) are all expressed under the form

T (n) = n ∑ k=2 (-1) k n k ϖ T (k), (5)
where the function ϖ T (s) is a Dirichlet series which depends on the parameter T and is closely related to the Dirichlet series Λ(s) of the source S , defined in ( 1)

ϖ R (s) = (s -1) Λ(s), ϖ C (s) = s Λ(s), ϖ B (s) = 2 s(s -1) Λ(s). (6)
This result provides exact expressions for the mean values of parameters of interest, that are totally explicit for simple sources, due to formulae given in [START_REF] Cesaratto | Gaussian distribution of trie depth for dynamical sources[END_REF] or in [START_REF] Cl Ément | Dynamical sources in information theory: A general analysis of trie structures[END_REF]. As we now wish to obtain an asymptotic form for these mean values, these nice exact expressions are not easy to deal with, due to the presence of the alternate sum. The Rice formula, described in [START_REF] Örlund | Lec ¸ons sur les équations linéaires aux différences finies[END_REF][START_REF] Örlund | Vorlesungen über Differenzenrechnung[END_REF] and introduced by Flajolet and Sedgewick [START_REF] Flajolet | Mellin transforms and asymptotics: finite differences and Rice's integrals[END_REF] into the analytic combinatorics domain, transforms an alternate sum into an integral of the complex plane, provided that the sequence of numerical values ϖ(k) lifts into an analytic function ϖ(s).

Let T (n) be a numerical sequence which can be written as in [START_REF] Dolgopyat | On decay of correlations in Anosov flows[END_REF], where the function ϖ T (s) is analytic in ℜ(s) > C, with 1 < C < 2, and is there of polynomial growth with order at most r. Then the sequence T (n) admits a Nörlund-Rice representation, for n > r + 1 and any C < d < 2.

T (n) = 1 2iπ -d+i∞ -d-i∞ ϖ T (-s) n! s(s + 1) • • • (s + n) ds (7)
1.6. Importance of tameness of sources. The idea is now to push the contour of integration in [START_REF] Fayolle | On a functional equation arising in the analysis of a protocol for a multi-accessbroadcast channel[END_REF] to the right, past -1. This is why we consider the possible behaviours for the function ϖ T (s) near ℜs = 1, more precisely on the left of the line ℜs = 1. Due to the close relations between the functions ϖ T (s) and the Dirichlet series Λ(s) of the source given in [START_REF] Dolgopyat | Prevalence of rapid mixing in hyperboloic flows (I) Ergodic Theory and Dynamical Systems[END_REF], it is sufficient to consider possible behaviours for Λ(s) itself. We will later show why the behaviours that are described in the following definition, already given in [START_REF] Vall Ée | The number of symbol comparisons in Quick-Sort and QuickSelect[END_REF] 1 , and shown in Figure 2, arise in a natural way for a large class of sources.

Definition 1 Let R be a region that contains the half-plane ℜs ≥ 1.

A source S is R-entropic if Λ(s) is meromorphic on R with a simple pole at s = 1, simple, whose residue involves the entropy h(S ) under the form 1/h(S ).

A source is R-tame if (i) it is R-entropic, -(ii) Λ(s) has no other pole than s = 1 in R, -(iii) Λ(s) is of polynomial growth in R as |s| → +∞.
A source is (a) strongly-tame (S-tame in shorthand) of abscissa δ if there exists a vertical strip R of the form ℜ(s) > 1δ , with δ > 0, where Λ(s) is Rtame. (b) hyperbolically tame (H-tame in shorthand) of exponent α if there exists a hyperbolic region R, with A, B, α > 0

R := s = σ + it; |t| ≥ B, σ > 1 - A t α s = σ + it; σ > 1 - A B α , |t| ≤ B , where Λ(s) is R-tame.
A source S is periodic of abscissa δ , if there exists a vertical strip R of the form ℜ(s) > 1δ , with δ > 0, where Λ(s) is R entropic and admits a singularity at a point 1 + it 0 , for some real t 0 > 02 .

For an entropic source, the Dirichlet series ϖ T (s) has a pole of order 0 (for the Trie size, cost R), a pole of order 1 (for the Trie path length, cost C), a pole of order 2 (for the Bst symbol path length, cost B). 1.7. Average-case analysis: asymptotic expressions of the three mean costs. Now, the following result shows that the shape of the tameness region (described by the order, the abscissa, the exponent) essentially determine the behaviour of the Rice integral in [START_REF] Fayolle | On a functional equation arising in the analysis of a protocol for a multi-accessbroadcast channel[END_REF], and thus the asymptotic behaviour of our main parameters of interest: It provides a dictionary which transfers the tameness properties of the source into asymptotic properties of the sequence T (n). The following theorem gathers and makes more precise results that are already obtained in [START_REF] Cl Ément | Dynamical sources in information theory: A general analysis of trie structures[END_REF] or [START_REF] Vall Ée | The number of symbol comparisons in Quick-Sort and QuickSelect[END_REF] : Fill, Flajolet, Vallée]. The asymptotics of each cost T (n) of interest, relative to a parameter of a tree built on a general source S , and defined in Theorem 1, is of the general following form T (n) = P T (n) + E(n). The "principal term" P T (n) involves the entropy h(S ) under the form

Theorem 2 [Clément,
P R (n) = 1 h(S ) n, P C (n) = 1 h(S ) n log n + an, P B (n) = 1 h(S ) n log 2 n + bn log n + cn,
together with some other constants a, b, c. The "error term" E(n) admits the possible following forms, depending on the tameness of the source

(a) If S is S-tame with abscissa δ 0 , then E(n) = O(n 1-δ ), for any δ < δ 0 . (b) If S is H-tame with exponent α 0 , then E(n) = n • O(exp[-(log n) α ]) for any α < 1/(α 0 + 1). (c) If S is periodic with abscissa δ 0 , then E(n) = n • Φ(log n) + O(n 1-δ ), for any δ < δ 0 ,
where n • Φ(log n) is the part of the expansion brought by the family of the non real poles located on the vertical line ℜs = 1, and involves a periodic function Φ.

Note that the "error term" E(n) is not always ... an actual error term: in the case of the trie size, for a periodic source, the fluctuation terms given by E(n) arise in the main term. However, in all the other cases, the term E(n) is indeed an error term. The main term of the principal term always involves a constant equal to 1/h(S ), and the order of the main term depends on the tree parameter: it is always of the form n log k n, and the integer k equals the order of the pole s = 1 for the Dirichlet series ϖ T (s) : one has k = 0 for the Trie size, k = 1 for the Trie path length, and k = 2 for the Bst symbol path length. This result proves that, with respect to the number of symbol comparisons, the Bst is much less efficient than the Trie.

1.8. Tameness of simple sources. We show that tameness properties that are described in Definition 1 arise in a natural way for simple sources. Even if S-tameness never occurs for simple sources, we will see later that it "often" occurs for most of more "complex" sources. We now focus on the memoryless case, defined by the probabilities P = (p 1 , p 2 , . . . , p r ), to which we associate the ratios α k, j := log p j /log p k .

Then, tameness properties depend on arithmetic properties of the ratios α k, j .

Proposition 1 Any simple source (memoryless source or irreducible aperiodic Markov chain) is entropic. A memoryless source is periodic if and only, for any fixed k, all the real numbers α k, j are rationals with the same denominator.

We now focus on non-periodic memoryless sources, where there exists, amongst all the reals α k, j , at least one real α k, j which is irrational. In this case, there is no other pole of Λ(s) than s = 1 on the vertical line ℜs = 1 but there exist poles of Λ which are arbitrary close to the vertical line ℜs = 1. This entails that a simple source is never strongly tame. The distribution of distances of the poles with respect to the vertical line ℜs = 1 depends on the degree of approximability of the family α by rationals, as it was first remarked in [START_REF] Fayolle | On a functional equation arising in the analysis of a protocol for a multi-accessbroadcast channel[END_REF]. We recall some notions on diophantine approximations (see for instance [START_REF] Lagarias | Best simultaneous Diophantine approximations I: Growth rates of best approximation denominators[END_REF]). The irrationality exponent of a real x is defined by

ω(x) := sup α, x - p q ≤ 1 q 2+α for an infinite number of pairs (p, q) ∈ N 2 .
A number x is diophantine if its irrationality exponent is finite. The following result provides a characterisation of H-tameness for simple sources. It can be found in a more precise form in [START_REF] Flajolet | Digital Trees and Memoryless Sources: from Arithmetics to Analysis[END_REF], where the authors revisit previous results of [START_REF] Lapidus | Fractal Geometry, Complex Dimensions and Zeta Functions: Geometry and Spectra of Fractal Strings[END_REF].

Theorem 3 [Flajolet, Roux, Vallée]. A memoryless source is H-tame if and only it is diophantine. Moreover, there is a relation between the exponent α of H-tameness and the irrationality exponent µ(P): one can choose as α any real strictly greater than 2µ(P) + 2, and it is in a precise sense the best possible choice.

With the general Theorem 2, together with Propositions 1 and 2, we can precisely describe the asymptotic probabilistic behaviour of two main tree data structures built on words produced by memoryless sources. Generally speaking, Theorem 2 can be applied to tree structures built on a general source as soon as its tameness may be studied. The following of the paper describes a general class of sources, which contains the simple sources, for which tameness properties can be precisely studied. We will see that tameness of these general sources may be quite different from tameness of simple sources.

2 Tameness of dynamical sources.

We first define the class of dynamical sources and explain their relation with simple sources. Then, we recall the expression of the Dirichlet series Λ(s) as a function of the secant transfer operator of the underlying dynamical systems. Finally, we exhibit sufficient conditions on the underlying dynamical system under which it is possible to prove tameness properties [Theorem 4 for S-tameness, and Theorem 5 for H-tameness].

Definition of dynamical sources.

A dynamical source, defined in [START_REF] Vall Ée | Dynamical sources in information theory: Fundamental intervals and word prefixes[END_REF] is closely related to a dynamical system on the interval. The system is complete when each restriction is surjective, i.e., T (I m ) = I . The system is Markovian when each interval T (I m ) is a union of intervals I j .

A dynamical system, together with a distribution G on the unit interval I , defines a probabilistic source, which is called a dynamical source and is now described (See also Fig. 1 at the end). The map T is used as a shift mapping, and the mapping τ whose restriction to each I m is equal to m, is used for coding. The words are emitted as follows [see Figure 3]: To each real x, (except for a denumerable set), one associates the trajectory T (x) = (x, T (x), T 2 (x), . . . T j (x), . . . ), which gives rise, via the mapping τ to the word

M(x) ∈ Σ N , M(x) = (m 1 (x), m 2 (x), . . . , m n (x), . . . ) with m j (x) = τ(T j-1 (x)).
Given a prefix w ∈ Σ ⋆ , the set I w of all reals x for which the word M(x) begins with the prefix w is an interval, the fundamental interval associated to w, and the measure of this interval (with respect to distribution G), is the fundamental probability p w of the source. In the case of a complete system, one denotes by h [m] the local inverse of T restricted to I m and by H the set

H := {h [m] , m ∈ Σ} of all local inverses. Each local inverse of the k-th iterate T k is then associated to a word w = m 1 m 2 . . . m k ∈ Σ k ; it is of of the form h [w] := h [m 1 ] • h [m 2 ] . . . h [m k ] ,
and

I w = h [w] (I ), p w = |G(h [w] (1)) -G(h [w] (0))|. ( 8
)
The set of all the inverse branches of

T k is H k = {h [w] ; w ∈ Σ k }.
For h ∈ H k , the number k is called the depth of h and it is denoted by p(h). We denote by H ⋆ := ∪ k≥0 H k the set of all inverse branches.

Such sources may possess a high degree of correlations, due to the geometry of the branches and also to the shape of branches.

The geometry of the branches is defined by the respective positions of "horizontal" intervals I m with respect to "vertical" intervals J ℓ := T (I ℓ ) and allows to describe the set S m formed with symbols which can be possibly emitted after symbol m. The geometry of the system then provides a first access to the correlation between successive symbols. In particular, in a complete system, any symbol of Σ can be emitted after any symbol m, and thus the equality S m = Σ always holds.

The shape of the branches, and more precisely, the behavior of derivatives |h ′ m | has also a great influence on correlations between symbols. For a fixed geometry of the branches, a system with affine branches is "less correlated" than the other systems with the same geometry. The contraction properties of H , (i.e., the fact that |h ′ m | < 1) are also essential, since they give rise to chaotic behaviour of the trajectories.

2.2. Simple sources viewed as dynamical sources. All memoryless sources and all Markov chain sources belong to the general framework of dynamical sources and correspond to a piecewise linear shift, under this angle of dynamical sources. For instance, the standard binary system is obtained by T (x) = {2x} ({•} is the fractional part). More precisely:

-A memoryless source is a complete dynamical source, with affine branches and a uniform initial distribution, -A Markov chain is a Markovian dynamical source, with affine branches and a family of uniform initial distributions on each J j .

Figure 3 shows three instances of simple sources, viewed as dynamical sources.

However, as soon as the derivatives h ′ of the branches are not constant, there exist correlations between successive symbols, and the dynamical source is no longer simple. Dynamical sources with a non-linear shift allow for correlations that depend on the entire past. A main instance is the dynamical source relative to the Gauss map, represented in Figure 3, which underlies the Euclid Algorithm and is defined on the unit interval via the shift T We here consider the case of a complete dynamical system: if f = f 0 denotes the initial density on I , and f 1 the density on I after one iteration of T , then f 1 can be written as

T (0) = 0, T (x) = 1 x - 1 x (x = 0). ( 9
)
f 1 = H[ f 0 ]
, where H is defined by

H := ∑ h∈H H (h) with H (h) [ f ](x) := |h ′ (x)| f • h(x).
The transfer operator extends the density transformer; it depends on a complex parameter s,

H s = ∑ h∈H H (h),s with H (h),s [ f ](x) := |h ′ (x)| s • f • h(x), (10)
and coincides with H when s = 1. Here, we are interested by generating the fundamental probabilities, whose expression is provided in [START_REF] Fill | The number of bit comparisons used by Quicksort: An average-case analysis[END_REF] in the case of a complete dynamical system. The main tool is a generalized version of the transfer operator -the secant transfer operator-introduced by Vallée in [START_REF] Vall Ée | Dynamical sources in information theory: Fundamental intervals and word prefixes[END_REF]. This operator involves the secant function of inverse branches (instead of their derivatives), it acts on functions F of two variables; for s ∈ C, and h ∈ H , we first define the component secant operator H (h),s as

H (h),s [F](x, y) := h(x) -h(y) x -y s F(h(x), h(y)), (11)
and the secant transfer operator is defined as

H s := ∑ h∈H H (h),s , (12)
Denote by diag F the function defined by diag F(x) := F(x, x). The equality

H s [F](x, x) = H s [diag F](x)
holds on the diagonal x = y and shows that the secant operator is an extension of the plain transfer operator. Moreover, multiplicative properties of secants then entail the relation

H k s = ∑ h∈H k H (h),s so that H k s [F](x, y) = ∑ h∈H k h(x) -h(y) x -y s F(h(x), h(y)).
Finally, the Dirichlet series can be expressed as a quasi-inverse of the secant operator: this is a nice extension of the expressions obtained for simple sources, in [START_REF] Cesaratto | Gaussian distribution of trie depth for dynamical sources[END_REF][START_REF] Cl Ément | Dynamical sources in information theory: A general analysis of trie structures[END_REF].

Proposition 2 [Vallée]. For a complete dynamical source, relative to a shift T and a distribution G, the Dirichlet series of the source admits an alternative expression which involves the quasi-inverse of the secant operator, defined in [START_REF] Flajolet | Digital Trees and Memoryless Sources: from Arithmetics to Analysis[END_REF] applied to the function L s , where L is the secant of the distribution G,

Λ(s) = (I -H s ) -1 [L s ](0, 1), with L(x, y) := G(x) -G(y)
xy .

Tameness of dynamical sources.

Here, we consider subclasses of dynamical sources, for which the quasi-inverse has nice spectral properties. This will entail, with Proposition 2, nice properties for the function Λ(s), from which one deduces tameness properties. The main results are as follows: There exist natural instances of dynamical sources which are S-tame, or H-tame. A "random" dynamical source is "very often" S-tame: this happens as soon as its inverse branches have "not too often" the same "shape".

A dynamical source can be periodic only if it "closely resembles" a memoryless source. A dynamical source is H-tame if, informally speaking, its arithmetical properties are the same as the arithmetical properties of a H-tame memoryless source. More precisely, we define three (large) subclasses of dynamical sources -the Good Class, the UNI Class, the DIOP Class-for which we can describe the tameness in an informal setting. The UNI Class has been already studied and described in previous works [5, 1, 2, 3]. The original part of our work is related to the DIOP Class, for which we revisit and extend previous results described in [START_REF] Dolgopyat | Prevalence of rapid mixing in hyperboloic flows (I) Ergodic Theory and Dynamical Systems[END_REF][START_REF] Melbourne | Rapid decay of correlations for nonuniformly hyperbolic flows[END_REF][START_REF] Naud | Analytic continuation of a dynamical zeta function under a diophantine condition[END_REF]. We first state the main tameness results for dynamical sources in an informal way:

Theorem. All the sources of the Good-UNI Class are S-tame. All the sources of the Good-DIOP Class are H-tame. A source of the Good Class may be periodic only if it is conjugated to a source with affine branches.

2.5. The Good Class. We first define the Good Class, for which the shift is expansive, and gives rise to a chaotic behaviour for the trajectories.

Definition 3 [Good Class]. A dynamical system of the interval (I , T ) belongs to the Good Class if it is complete, with a set H of inverse branches which satisfies the following: (G1)

The set H is uniformly contracting, i.e., there exists a constant ρ < 1, for which

∀h ∈ H , β h := sup{|h ′ (x)|; x ∈ I } ≤ ρ.
(G2) There is a constant A > 0, so that every inverse branch h ∈ H satisfies |h ′′ | ≤ A|h ′ |.

(G3) There exists σ 0 < 1 for which the series ∑ h∈H β s h converges on ℜs > σ 0 . The essential condition is (G1). The bounded distortion property (G2) and the property (G3) are technical conditions that always fulfilled for a finite alphabet Σ.

When the dynamical system belongs to the Good Class, the transfer operators (tangent and secant) act on spaces of functions of C 1 class. They admit dominant spectral properties for s near the real axis, together with a spectral gap. This implies that, for s near 1, the function Λ(s) is meromorphic for s with a small imaginary part, and admits a simple pôle at s = 1. ∆(h,k) denotes the "distance" between two inverse branches h and k of same depth, defined as

∆(h, k) = inf x∈I |Ψ ′ h,k (x)| with Ψ h,k (x) = log h ′ (x) k ′ (x) . ( 13
)
The distance ∆(h, k) is a measure of the difference between the "shape" of the two branches h, k. The UNI Condition, stated as follows [START_REF] Dolgopyat | On decay of correlations in Anosov flows[END_REF], is a geometric condition which expresses that the probability that two inverse branches have almost the same "shape" is very small: For a source with affine branches, the "distance" ∆ is always zero, and the probabilities of Assertion (U1) are all equal to 1. Such a source never satisfies the Condition UNI. Conversely, a dynamical source of the Good-UNI Class cannot be conjugated to a source with affine branches, as it is proven by Baladi and Vallée [START_REF] Baladi | Euclidean algorithms are Gaussian[END_REF]. Then, the condition UNI excludes all the simple sources, which cannot be S-tame. The strength of the Condition UNI is due to the fact that this condition is sufficient to imply strong tameness :

Theorem 4 [Dolgopyat, Baladi-Vallée, Cesaratto-Vallée] When the dynamical system of the Good Class satisfies the condition UNI, it gives rise to a S-tame source.

There are natural instances of sources that belong to the Good-UNI Class, for instance the Euclidean dynamical system defined in ( 9), together with two other dynamical systems, of the Euclidean type.

2.7. The diophantine conditions. The Good-UNI Class gathers systems which are quite different from systems with affine branches. The DIOP Condition "copies" the behaviour of memoryless sources, when they are H-tame. In this case, we recall that there exists a ratio log p i /log p k which is diophantine, i.e., whose irrationality exponent is finite.

The DIOP condition is an arithmetical condition, which extends this condition to a system of the Good Class. For an inverse branch h, one denotes by h ⋆ its unique fixed point (such a point exists and is unique for a system of the Good Class), by p(h) its depth, and one lets, for h, k, ℓ in H ⋆ ,

c(h) = log |h ′ (h ⋆ )| p(h) , c(h, k) = c(h) c(k) , c(h, k, ℓ) = c(h) -c(k) c(h) -c(ℓ) .
We can now state the definition of diophantine dynamical sources:

Definition 5 [DIO2 and DIOP3]. A dynamical source is 2-diophantine ([DIOP2] in shorthand) if

there exist two branches h et k of H ⋆ for which the ratio c(h, k) is diophantine. A dynamical source is 3-diophantine ([DIOP3] in shorthand) if there exist three branches h, k and ℓ of H ⋆ for which the ratio c(h, k, ℓ) is diophantine

The following result proves that these conditions are sufficient to entail H-tameness of associated sources. This is the main contribution of Roux' PhD thesis [START_REF] Roux | Séries de Dirichlet[END_REF]. The appendix contains hints on the proof, that will be detailed in the long version.

Theorem 5 [Dologopyat, Naud, Melbourne, Roux-Vallée] (a) A dynamical system of the Good Class, which is moreover DIOP3, gives rise to a H-tame source. (b) A dynamical system of the Good Class, which is moreover DIOP2, gives rise to a H-tame source.

2.8. A little piece of history. Dolgopyat, in two seminal papers [START_REF] Dolgopyat | On decay of correlations in Anosov flows[END_REF][START_REF] Dolgopyat | Prevalence of rapid mixing in hyperboloic flows (I) Ergodic Theory and Dynamical Systems[END_REF], introduces the Conditions UNI and DIOP2. He proves that, under these conditions, the quasi-inverse of the plain (tangent) transfer operator has nice properties in a region on the left of the line {ℜs = 1}: when the UNI Condition holds, the region is a vertical strip, and when the DIOP2 Condition holds, the region is of hyperbolic type. However, he does not consider the case of an infinite number of branches, and his results are extended to this case by Baladi and Vallée in [START_REF] Baladi | Euclidean algorithms are Gaussian[END_REF][START_REF] Baladi | Exponential decay of correlations for surface semi-flows without finite Markov partitions[END_REF] for the UNI condition, and by Melbourne [START_REF] Melbourne | Rapid decay of correlations for nonuniformly hyperbolic flows[END_REF] in the case of the DIOP condition, who introduces the DIOP3 Condition. However, in order to deal with the Dirichlet series Λ(s), one needs to extend the previous proofs to the secant operator. This have been done by Cesaratto and Vallée in [START_REF] Cesaratto | Gaussian distribution of trie depth for dynamical sources[END_REF] for the UNI Condition. Here, we deal with the DIOP conditions and we perform two extensions: we consider a possible infinite alphabet, we deal both with the DIOP3 (where we use a method due to Melbourne [START_REF] Melbourne | Rapid decay of correlations for nonuniformly hyperbolic flows[END_REF]) and the DIOP2 condition (where we use a method due to Naud [START_REF] Naud | Analytic continuation of a dynamical zeta function under a diophantine condition[END_REF]). We also extend these results to the secant operator.

3 Some hints on the proof of Theorem 5.

Since the Dirichlet series Λ(s) is expressed with the quasi-inverse of the secant operator H s we study the behaviour of this quasi-inverse on the vertical line ℜs = 1. It is closely related to the behaviour of the operators M t , M t defined by

M t [ f ](x) := |T ′ (x)| it f • T (x), M t [F[(x, y) := T (x -T (y) x -y it F(T (x), T (y)).
3.1. Various possibilities for the spectral radius of the operator H s on ℜs = 1. The beginning point is the following proposition, that is classical for the tangent operator, and can be easily extended to the secant operator.

Proposition 3. Consider a dynamical system of the Good Class and its secant transfer operator H s , acting on the space C 1 (I × I ) for a parameter s of the form s = 1 + it 0 , with t 0 = 0. (a) For a complex number λ of modulus 1, the two conditions are equivalent:

(a1) The complex number λ belongs to the spectrum Sp H 1+it 0 .

(a2) The complex number λ -1 is an eigenvalue of M t 0 .

(b) Assume that there exists t 0 = 0 for which the condition (a2) is satisfied. Then, there exist a = 0 and b for which the quantities c(h)b all belong to the Z-module Za.

(b1) If λ is a root of unity, then all the ratios c(h, k) are rationals.

(b2) If λ is any complex number of modulus 1, all the ratios c(h, k, ℓ) are rationals.

(c) If one of the two conditions is satisfied (c1) there exists a ratio c(h, k) which is not rational, (c2) For any t = 0, the spectrum of the operator M t does not contain λ = 1.

then, the quasi-inverse (I -H s ) -1 is analytic on ℜs = 1 except at s = 1 where it has a simple pole.

(d) If one of the two conditions is satisfied (d1) there exists a ratio c(h, k, ℓ) which is not rational, (d2) For any t = 0, the spectrum of the operator M t does not contain any λ with |λ | = 1, then, the spectral radius of H s is strictly less than 1 on {s; ℜs = 1, s = 1} and, for any λ of modulus 1, the quasi-inverse (Iλ H s ) -1 is analytic on the line ℜs = 1 except at s = 1 where it admits a simple pole.

Reinforcement of conditions (c), (d).

The main question is now as follows: if one of the conditions (c1) or (d1) or (c2) or (d2) is replaced by a stronger condition, is it possible to obtain a conclusion about tameness, of the following kind: (R) There exists a region on the left of the vertical line ℜs = 1 on which the quasi-inverse (I -H s ) -1 is analytic except at s = 1 (where it admits a simple pole), and is of polynomial growth for t = ℑs → ∞.

We deal here with the Banach space C

A possible reinforcement DIOP3 of the condition (d1) is "There exists a triple (h, k, ℓ) for which c(h, k, ℓ) is diophantine". A possible reinforcement (d3) of the condition (d2) is: "The operator M t does not admit a system of almost eigenfunctions" for which a more formal statement will be provided later. We will also see that these two reinforcements are not independent since the implication DIOP3 ⇒ (d3) holds A possible reinforcement DIOP2 of the condition (c1) is "There exists a pair (h, k) for which c(h, k) is diophantine". A possible reinforcement (c3) of the condition (c2) is: "The operator M t does not admit a system of almost invariant functions" for which a more formal statement will be provided later. We will also see that these two reinforcements are not independent since the implication DIOP2 ⇒ (c3) holds Theorem 5(b).

[DIOP2] Consider a dynamical source of the Good Class, with a possibly infinite denumerable alphabet, with a contraction ratio ρ < 1 and a pression function s → L(s) 3 . Consider the real ν 1 defined from the pressure function by the two equations

(1 -σ 1 )L ′ (σ 1 ) + L(σ 1 ) = log ρ, ν 1 = -L ′ (σ 1 ).
If there exists a pair {h, k}, with ν 0 = max{c(h), c(k)}, for which c(h, k) is diophantine with exponent µ, then R(t) is of polynomial growth, with an exponent strictly larger than 4µ + 3 + ν 2µ + 4 | log ρ| with ν = max(ν 0 , ν 1 ). We consider properties which are satisfied only on subsets of the unit square I × I and only in an approximative way, and, for a given imaginary part t, these subsets, and the approximation will depend on t (in a polynomial way), and there are various parameters (α, β , γ, δ ) for the possible exponents.

One lets n(β ,t) := ⌈β log |t|⌉, n(θ ,t) := ⌈θ log |t|⌉ and considers the following subsets of H ⋆ ,

H (t, θ ) := H n(θ ,t) , H (t, β , δ ) := h ∈ H n(β ,t) ; min{|h ′ (x)|, x ∈ I } ≥ 1 t δ .
The following subsets of I × I are called "fundamental unions"

I (t, β , δ ) := h∈H (t,β ,δ ) h(I ) × h(I ), I (t, β , δ , θ ) := h∈H (t,β ,δ ) ℓ∈H (t,θ ) h • ℓ(I ) × h • ℓ(I ).
3 the pression is the logarithm of the dominant eigenvalue λ (s)

In the proof, there are various subsets which intervene: Subsets A , related to the notion of "almost eigenfunctions" -subsets C relared to the notion of "almost invariant functions" -subsets E which approximate subsets A \ C -subsets B related to the behaviour of the iterate of the operator -Subsets F related to the growth of the quasi-inverse of the secant operator. The final subset of interest is the subset F , and the other ones form a chain of subsets which will be compared to F in the proof. The first three ones involve the approximate subset I (t, β , δ , θ ).

The set A (α, β , δ , θ ) gathers all the reals t for which there exists a pair (w t , η t ) that satisfies,

|M n(β ,t) t [w t ](x, y) -η t w t (x, y)| ≤ 1 t α , for any (x, y) ∈ I (t, β , δ , θ ). (15)
The set C (α, β , γ, δ , θ , k 0 ) gathers all the reals t for which there exists a pair (w t , η t ) that satisfies

|η k 0 t -1| ≤ 1 t γ . |M n(β ,t) t [w t ](x, y) -η t w t (x, y)| ≤ 1 t α , for any (x, y) ∈ I (t, β , δ , θ ). (16)
The set E (α, β , γ, δ , θ , k 0 ) gathers the reals t for which there exists a pair (w t , η t ) that satisfies

|η k 0 t -1| > 1 t γ , |M n(β ,t) t [w t ](x, y) -η t w t (x, y)| ≤ 1 t α , for any (x, y) ∈ I (t, β , δ , θ ). (17)
The inclusion

A (α, β , δ , θ ) \ C (α, β , γ, δ , θ , k 0 ) ⊂ E (α, β , γ, δ , θ , k 0 ) holds.
Let ψ be the invariant function of H 1 . The set B(α, β , θ ) gathers all the reals t for which there exists u t , with ||u t || (t) ≤ 1, that satisfies, for any n ≤ 3n(β ,t) and any (x, y) ∈ I (t, θ ),

|H n 1+it [ψu t ](x, y)| ≥ ψ(x, y) 1 - 1 t α .
The set F (α) gathers the reals t for which the quasi-inverse is of polynomial growth with exponent α F (α) := {t, R(t) ≤ t α }.

We wish to prove that there exists α for which F c (α) is bounded.

3.5. Relation between diophantine properties, subsets A and C . There are two main results, described in Lemma 0 (with subset A ) and Lemma 1 (with subset C ).

Lemma 0. Consider a triple (h, k, ℓ) ∈ H 3 and a real α > 1. If there exists a triple (β , δ , θ ) with δ β > max{c(h), c(k), c(ℓ)}, [START_REF] Melbourne | Rapid decay of correlations for nonuniformly hyperbolic flows[END_REF] for which A (α, β , δ , θ ) is unbounded, then c(h, k, ℓ) has an irrationality exponent at least equal to α -1.

If c(h, k, ℓ) is diophantine with exponent µ, then for any 4-uple (α, β , δ , θ ) avec α > µ + 1, et (β , δ ) which satisfies [START_REF] Melbourne | Rapid decay of correlations for nonuniformly hyperbolic flows[END_REF], the subset A (α, β , δ , θ ) is bounded.

Lemma 1. Consider a pair (h, k) ∈ H 2 and a real µ > 1. If there exists a 6-uple (α, β , γ, δ , θ , k 0 ) with min(α, γ) = µ, and δ β > max{c(h), c(k)}, [START_REF] Naud | Analytic continuation of a dynamical zeta function under a diophantine condition[END_REF] for which the subset C (α, β , γ, δ , θ , k 0 ) is unbounded, then c(h, k) has an irrationality exponent at least equal to µ -1.

If c(h, k) is diophantine with exponent µ, then, for each 6-uple (α, β , γ, δ , θ , k 0 ) with min(α, γ) > µ + 1 et (β , δ ) that satisfies [START_REF] Naud | Analytic continuation of a dynamical zeta function under a diophantine condition[END_REF], the subset C (α, β , γ, δ , θ , k 0 ) is bounded.

In the following of the proof, we use the notion of weak inclusion between two subsets L et M de R. For any 5-uple (α, β , γ, δ , θ ) which satisfies the relations

α > γ, β ≥ α + 1 | log ρ| , θ ≥ 2α + δ + 1 | log ρ| , δ β > ν 1 ,
there exists an integer k 0 for which the weak inclusion F c (2α + δ ) ⊂ C (α, β , γ, δ , θ , k 0 ) holds.

Figure 2 :

 2 Figure 2: Three possible domains where the function ϖ(s) is analytic and of polynomial growth.

Definition 2 A

 2 dynamical system of the interval I := [0, 1] is defined by a mapping T : I → I (called the shift) for which (a) there exists a finite alphabet Σ, and a topological partition of I with disjoint open intervals (I m ) m∈Σ , i.e. I = m∈Σ I m . (b) The restriction of T to each I m is a C 2 bijection from I m to T (I m ).

Figure 3 :

 3 Figure 3: (Up) A dynamical system, with Σ = {a, b, c} and a word M(x) = (c, b, a, c . . .) -(Down) Two memoryless sources and a Markov chain, viewed as dynamical sources. The continued fraction source.

2. 6 .

 6 The UNI Condition. One first defines a probability Pr n on each set H n × H n , in a natural way, and lets Pr n {(h, k)} := |h(I )| • |k(I )|, where |J | denotes the length of the interval J . Furthermore,

Definition 4 [

 4 Condition UNI]. A dynamical system (I , T ) satisfies the UNI condition if its set H of inverse branches satisfies the following (U1) For any a ∈]0, 1[, and for any integer n, one has Pr n [ ∆ ≤ ρ an ] << ρ an . (U2) Each h ∈ H is of class C 3 and for any n, there exists B n for which |h ′′′ | ≤ B n |h ′ | for any h ∈ H n .

3 . 6 .Lemma 2 .Lemma 3 . 1 Lemma 4 . 1 3. 7 .Lemma 5 . 1 | log ρ| , δ β > ν 1 ,Lemma 6 .

 362314175116 The subset L is said to be weakly included in M [this is denoted by L ⊂ M ] if there exists t 1 ∈ R for which L ∩ [t 1 , +∞[⊂ M ∩ [t 1 , +∞[. Relations between subsets A and F . Lemma 2 compares subsets B and A whereas Lemma 3 compares subsets B and F . Lemmas 2 and 3 are summarized in Lemma 4 which compares subsets A and F . Lemmas 0 and 4 together prove Theorem 5(a). For any4-uple (α, β , δ , θ ) that satisfies β | log ρ| ≥ α + 1, the weak inclusion B(α 1 , β , θ ) ⊂ A (α, β , δ , θ ) holds, for any α 1 > 2α + δ . For any triple (α 1 , β , θ ) that satisfies θ | log ρ| ≥ α 1 + 1, the weak inclusion B c (α 1 , β , δ ) ⊂ F (α 2 ) holds for any α 2 > 2α 1 + For any 4-uple (α, β , δ , θ ) that satisfies β | log ρ| ≥ α + 1, θ | log ρ| ≥ 2α + δ + 1, the weak inclusion F c (α 2 ) ⊂ A (α, β , δ , θ) holds, for any α 2 > 4α + 2δ + Relation between subsets E and F . This relation is described in Lemma 5. One considers the logarithm L(s) of the dominant eigenvalue λ (s) of the operator H s and the real ν 1 defined from the pressure function by the two equations(1σ 1 )L ′ (σ 1 ) + L(σ 1 ) = log ρ, ν 1 = -L ′ (σ 1 ).For any 5-uple (α, β , γ, δ , θ ) which satisfies the relationsα > γ, β ≥ α +there exists an integer k 0 for which the weak inclusionsE (α, β , γ, δ , θ , k 0 ) ⊂ F (2α), and thus F c (2α) ⊂ A c (α, β , δ , θ ) ∪ C (α, β , γ, δ , θ , k 0 ) hold.3.8. Relation between subsets C and F . One gathers the conclusions of Lemmas 4 and 5 in Lemma 6. Lemmas 1 et 6 together prove Theorem 5(b). One considers the logarithm L(s) of the dominant eigenvalue λ (s) of the operator H s and the real ν 1 defined from the pressure function by the two equations (1σ 1 )L ′ (σ 1 ) + L(σ 1 ) = log ρ, ν 1 = -L ′ (σ 1 ).

  1 (I × I ) formed with functions of class C 1 on the unit square, endowed with the norm ||.|| 1 defined by ||u|| 1 := sup |u(x, y|+sup ||u ′ (x, y)||, but we also use a norm ||.|| (t) which depends on the imaginary part t of s, defined by ||u|| (t) := sup |u(x, y| + (1/|t|) sup ||u ′ (x, y)||.

			Our
	main object of study is
	R(t) := (I -H 1+it ) -1	(t)	.

  3.3. Precise statement of Theorem 5.There are two theorems, one for each condition DIOP2 or DIOP3.

	Theorem 5(a). [DIOP3] Consider a dynamical source of the Good Class, with a possibly infinite denu-
	merable alphabet, with a contraction ratio ρ < 1. If there exists a triple {h, k, ℓ}, with ν = max{c(h), c(k),
	c(ℓ)}, for which c(h, k, ℓ) is diophantine with exponent µ, then R(t) is of polynomial growth, with an
	exponent strictly larger than
	4µ + 3 + ν	2µ + 4 | log ρ|	.

There are slight differences between the two definitions but the "spirit" is the same.

This implies that ϖ(s) admits singularities at all the points 1 + ikt 0 for any integer k, and is of polynomial growth on a family of horizontal lines t = t k with t k → ∞, and on vertical lines ℜ(s) = 1δ ′ with some δ ′ < δ

Acknowledgements. This work takes place inside the ANR project MAGNUM [Méthodes Algorithmiques pour la Génération Non Uniforme: Modèles et Applications] [ANR 2010 BLAN 0204] .


Julien Clément

Loïck Lhote

Brigitte Vallée

Entropy for dynamical sources

Keywords: Entropy, dynamical systems, transfer operators

teaching and research institutions in France or abroad, or from public or private research centers.

1 Dynamical sources.

In information theory contexts, data items are (infinite) words that are produced by a common mechanism, called a source. Real-life sources are often complex objects. We introduce here a general framework of sources related to dynamical systems theory which can be viewed as a generalization of numeration systems. This model goes beyond the cases of memoryless and Markov chains, it can describe nonmarkovian processes, where the dependency on past history is unbounded, and as such, it attains a high level of generality. A probabilistic dynamical source is defined by five elements: (a) an alphabet Σ, finite or denumerable, (b) a topological partition of I := [0, 1] with disjoint open intervals (I m ) m∈Σ , (c) an encoding mapping σ which is constant and equal to m on each I m , (d) a shift mapping T whose restriction to I m is a bijection of class C 2 from I m to J m := T (I m ). The local inverse of T | Im is denoted by h m , (e) a real density f on interval I, and its associated distribution function F . The dynamical system S := (I, T ), defined by the first four elements, associates to a real number x ∈ I the word M (x) := (σx, σT x, σT 2 x, . . . ) (Fig. 1). Then, the choice of the density f (or the distribution F ) on the interval I induces a probabilistic setting on the set M (I) of source words. Correlations. Such sources may possess a high degree of correlations, due to the geometry of the branches and also to the shape of branches. The geometry of the branches is defined by the respective positions of intervals I m with respect to intervals J ℓ and allows to describe the set of symbols possibly emitted after a given symbol. The system is complete if any interval J m equals I. It is markovian, if any interval J m is an union of intervals I ℓ . More generally, the following property is essential: (P 1) [Topologically mixing] For any pair of symbols (b, e), there exists n 0 ≥ 1 such that, for any n ≥ n 0 , there is a word of length n which begins with symbol b and finishes with symbol e.

The shape of the branches h m , related to various properties of derivatives h ′ m , has also a great influence on correlations between symbols: (P 2) [Contraction] There exists δ < 1 such that, for any m ∈ Σ, for any x ∈ I, one has : |h ′ m (x)| ≤ δ < 1. (P 3) [Strong contraction] There exist x 0 ∈ I and two open disks D S and D L of same center x 0 and respective radii R S < R L , with ]0, 1[ ⊂ D L , such that any inverse branch h m admits an analytic expansion to D L and strictly maps Fig. 1. On the left: A dynamical system, with a partition coded with Σ = {a, b, c} and a word produced by a dynamical system M (x) = (c, b, a, c . . .). In the middle: two classical sources resp. related to the binary expansion, or the continued fraction expansion. On the right, an example of a trie on alphabet Σ = {a, b, c} built on the set of words {abaa, acb, ccaca, ccbb, ccccca}.

D L inside D S (i.e., h m (D L ) ⊂ D S ). (P 4) [Bounded distorsion] ∃K, ∀m ∈ Σ, ∀x ∈ I, |h ′′ m (x)| ≤ K |h ′ m (x)|.
Classical sources. The classical sources (memoryless sources, or Markov chains) are related to particular dynamical sources; a memoryless source corresponds to a complete system, with affine branches, and a uniform initial density. A Markov chain corresponds to a markovian system, with affine branches and an initial density which is piecewise constant on each I m .

Dirichlet series of fundamental measures. We consider in the sequel a complete system. The branches of T k , and also its inverse branches, are then indexed by Σ k , and, for any

w = m 1 . . . m k ∈ Σ k , the mapping h w := h m1 • h m2 • • • • • h m k is a C 2 bijection from I onto I w = h w (I).
All the words that begin with the same prefix w correspond to real numbers x that belong to the same interval I w . The probability p w that a word begins with prefix w is called the fundamental probability of w.

The Dirichlet series of fundamental probabilities, defined (for complex s) as

Λ k (S F , s) := w∈Σ k p s w , Λ(S F , s) := w∈Σ ⋆ p s w (1)
will play a fundamental rôle in the source statistics.

Generation of p s w . To each prefix w, one associates an operator, denoted by G s,[w] , defined with the secant H w relative to branch h w ,

H w (x, y) := h w (x) -h w (y) x -y ,
which acts on functions L of two variables (x, y) ∈ I × I as

G s,[w] [L](x, y) := H s w (x, y) L(h w (x), h w (y)
). If now the function L is the secant of the distribution F , the relation

p s w = |F (h w (0)) -F (h w (1))| s = G s,[w] [L s ](0, 1)
explains why the operator G s,[w] is called the generating operator of w.

Generating operators. The generating operator relative to a collection L of words is defined as the sum of all the generating operators relative to the words of L. For two prefixes w, w ′ , the relation p w.w ′ = p w p w ′ is no longer true when the source has some memory, and is replaced by the following composition property

G s,[w.w ′ ] = G s,[w ′ ] • G s,[w] , (2)
so that unions and cartesian products of collections of words translate into sums and compositions of the generating operators. The generating operator G s := m∈Σ G s,[m] related to the alphabet Σ plays a fundamental rôle here. By Eq. ( 2), the k-th iterate G k s generates all the words of length k, and the quasi-inverse (I -G s ) -1 generates all the finite words. Then, alternative expressions for the Dirichlet series defined in Eq. (1) hold:

Λ k (S F , s) = G k s [L s ](0, 1), Λ(S F , s) = (I -G s ) -1 [L s ](0, 1). ( 3
)
Asymptotic properties of powers G k s of the transfer operator will be needed and they are closely related to dominant spectral properties of operator G s . In the same vein, we are interested by the location of poles of the quasi-inverse (I -G s ) -1 , that is, values s for which 1 is a spectral value of G s . Under quite general hypotheses on the dynamical system, the following holds: Decomposable sources. A dynamical system S is said to be decomposable with respect to a Banach space L iff the transfer operator G s , when acting on L, possesses for real s > s 0 (with s 0 < 1) a unique dominant eigenvalue λ(s) (real positive) separated from the remainder of the spectrum by a spectral gap. A source S F formed with a decomposable system S (with respect to L) and a function F whose secant belongs to L is said to be decomposable.

Properties of decomposable sources. For such sources, one has: (a) When s is near the real axis, Λ k (S F , s) asymptotically behaves as the k-th power of λ(s). There exists µ < 1, such that, when s is near a real s 0

Λ k (S F , s) = a(s) • λ(s) k • [1 + O(µ k )],
with a uniform O.

(b) The function s → Λ(S F , s) is analytic in the plane ℜ(s) > 1, and it has a simple pole at s = 1, with a residue equal to -λ ′ (1).

Sufficient conditions for decomposability. A markovian dynamical system on a finite alphabet satisfying (P 1) and (P 2) is decomposable, with respect to the space C 1 p (I) of piecewise functions of class C 1 . A complete dynamical system on a (possibly infinite) alphabet satisfying (P 2), (P 4) is decomposable, with respect to the space C 1 (I) of functions of class C 1 . A complete dynamical system on a (possibly infinite) alphabet satisfying (P 3), (P 4) is decomposable, with respect to the space of analytic functions on D S .

There are two kinds of "exceptional" sources, both related to exceptional properties of the pressure Λ(s) := log λ(s). The first one arises when the pressure Λ(s) is periodic and the second when the pressure Λ(s) is affine. They intervene as exceptions respectively for Result C and Result B. However we prove that an exceptional source is conjugated either to a memoryless source or to a Markov chain. Hence a "complex" source cannot be exceptional.

2 Main statistics for decomposable sources.

Entropy. The entropy rate h(S F ) of the source S F is defined as the limit, if it exists, of a quantity that involves probabilities p w ,

h(S F ) := lim k→∞ -1 k w∈Σ k p w log p w = lim k→∞ -1 k d ds Λ k (S F , s)| s=1 .
Result A. The entropy h(S F ) of a decomposable source S F equals -λ ′ (1). It only depends on the mechanism S.

Distribution of prefixes with fixed length k. The distribution of the fundamental probabilities of the words of Σ k is studied via the random variable ℓ k defined as a step function, constant on any fundamental interval I w of depth k and equal to p w . We use the moment generating function

E [exp(s log ℓ k )] = E [ℓ s k ] which is closely related to Λ k (S F , s): E [ℓ s k ] = w∈Σ k p s w p w = w∈Σ k p 1+s w = Λ k (S F , 1 + s).
Then, when S F is decomposable, the moment generating function behaves nearly like the k-th power of function λ(1 + s). The central limit theorem of probability theory asserts that exact large powers induce Gaussian laws in the asymptotic limit. Here, we shall use an extension of the central limit theorem to "quasi-powers" due to [START_REF] Hwang | On convergence rates in the central limit theorems for combinatorial structures[END_REF], valid provided that Λ ′′ (1) is not zero. We know that this is the case for the decomposable sources that do not behave like an unbiaised memoryless source [see [START_REF] Vallée | Dynamical sources in Information Theory: Fundamental Intervals and Word prefixes[END_REF]].

Result B. The distribution of probabilities of words of Σ k follows asymptotically a log-normal law, for all not affine sources. This proves a strong "equipartition property", in the flavour of the Shannon-MacMillan-Breimann Theorem. The dominant behaviours of the mean and the variance involve the derivatives of Λ(s) := log λ(s) at s = 1: the mean is asymptotic to kΛ ′ (1) = kλ ′ (1) and the variance is asymptotic to kΛ

′′ (1) = k[λ ′′ (1) -λ ′ (1) 2 ].
Average shape of a trie. In pattern matching problems, an essential data structure is a digital tree, called trie, which plays the rôle of a dictionary. The internal nodes are used for directing the search, and the leaves contain the words of the dictionary. There are as many leaves as words in the dictionary (see Fig. 1). Trie analysis aims at describing the average shape of a trie (size S, external path length P ); it is is extensively done in the case of classical sources (see Szpankowski (2004)). In our context, a trie is built on a set Y of n words or equivalently on a set X of reals {x 1 , x 2 , . . . , x n } for which Y = M (X). Such a trie is completely defined by the internal nodes which actually exist. These nodes are labelled by prefixes w for which the cardinality N w of I w ∩ X is at least two (which means that at least two words share a common prefix). The probability that node n w exists is just P[N w ≥ 2] while the contribution of node n w to the external path length is

E[N w | N w ≥ 2].
If we wish the contributions of set X to two disjoint intervals I w and I w ′ be independent, we are led to first work in a Poisson model: first, one draws the cardinality N of the set X with respect to a Poisson law of parameter z, then one independently draws the N reals with respect to density f . In this case, the random variable N w itself follows a Poisson law of parameter p w z, and the two expectations admit the following expressions

E[P (z) ] = w∈Σ ⋆ p w z(1 -e pwz ), E[S (z) ] = w∈Σ ⋆ 1 -e pwz (1 + p w z),
that are harmonic sums of the form A(z) = w λ w g(µ w z). The convenient tool is the Mellin transform which transforms an harmonic sum into a product and gives access to the asymptotic behaviour of E[P (z) ] and E[S (z) ] through the Dirichlet series Λ(S F , s), and particularly its singular behaviour near ℜs = 1, and its residue h(S). Then, Depoissonization techniques allow to return to the Bernoulli model (where the number n of words is fixed). One obtains:

Result C. The shape parameters of a trie [size, external length path] built on n words [independently drawn from the source] admit as asymptotic mean (for n → ∞) the following quantities which involve the entropy

E[S n ] ∼ n h(S) , E[P n ] ∼ n log n h(S) .
For sources that behaves like meoryless sources, the main asymptotic term of E[S n ] involves a periodic function of log n of small amplitude.

Computing the spectral constants. All the previous results involve the dominant eigenvalue λ(s). Except for simpler sources, this function does not admit a closed form, and it is important to obtain proven numerical values for the first two derivatives of the pressure function at s = 1.

For sources with strong contraction (P 3), the transfer operator acts on holomorphic functions, and can be viewed as an infinite matrix M s , whose coefficient of index(i, j) is the coefficient of (

z-x 0 ) i in G s [(Z-x 0 ) j , (T -x 0 ) j ](z, z).
In particular, the truncated matrix M (n),s where the indices i, j are less than n, is an approximation of G s (in a precise sense), and its dominant eigenvalue λ n (s) provides an approximate for λ(s).

Result D. Let λ(s) be the dominant eigenvalue of a strongly contracting decomposable source. Then, there exist an integer n 0 , and a constant K (which depend on s), such that for all n ≥ n 0 , the matrix M (n),s admits a unique simple dominant eigenvalue λ (n) (s) that satisfies

|λ(s) -λ (n) (s)| ≤ K R S R L n .
For instance, in the case of the Euclidean dynamical source (for which the entropy h(S) equals π 2 /(6 log 2) ∼ 2.37), this result allows to compute with a garanteed precision the value λ ′′ (1) ∼ 9.08037.

Bibliographic notes. Dynamical sources have been introduced by [START_REF] Vallée | Dynamical sources in Information Theory: Fundamental Intervals and Word prefixes[END_REF], who proved the first two results of Section 2. Some hypotheses for proving decomposability are made precise in [START_REF] Chazal | Erratum to "Dynamical sources in information theory: fundamental intervals and word prefixes[END_REF], and a general decomposability criterion is proven in Chazal and Maume (2004). Tries analysis is performed by [START_REF] Clément | Dynamical sources in Information Theory: Analysis of general tries[END_REF]. The method for approximating λ(s) is due to [START_REF] Daudé | An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction[END_REF]. This method was validated later by [START_REF] Lhote | Computation of a Class of Continued Fraction Constants[END_REF] who proved Result D. The continued fraction expansion motivates the introduction of dynamical sources. For a specific treatment of this case, see [START_REF] Flajolet | Continued Fractions, Comparison Algorithms, and Fine Structure Constants[END_REF], where a relation between the shape of tries and the Riemann hypothesis is exhibited...