Va L Érie Berth É

Hitoshi Nakada
email: nakada@math.keio.ac.jp

AND Rie Natsui
email: natsui@fc.jwu.ac.jp

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

FINE COSTS FOR THE EUCLID ALGORITHM ON POLYNOMIALS AND FAREY MAPS

Keywords: Laurent formal power series, finite field, continued fractions, Farey map, bitcomplexity, cost function, combinatorial analysis, bivariate generating functions

This paper studies digit-cost functions for the Euclid algorithm on polynomials with coefficients in a finite field, in terms of the number of operations performed on the finite field Fq. The usual bit-complexity is defined with respect to the degree of the quotients; we focus here on a notion of 'fine' complexity (and on associated costs) which relies on the number of their non-zero coefficients. It also considers and compares the ergodic behavior of the corresponding costs for truncated trajectories under the action of the Gauss map acting on the set of formal power series with coefficients in a finite field. The present paper is thus mainly interested in the study of the probabilistic behavior of the corresponding random variables: average estimates (expectation and variance) are obtained in a purely combinatorial way thanks to classical methods in combinatorial analysis (more precisely, bivariate generating functions); some of our costs are even proved to satisfy an asymptotic Gaussian law.

We also relate this study with a Farey algorithm which is a refinement of the continued fraction algorithm for the set of formal power series with coefficients in a finite field: this algorithm discovers 'step by step' each non-zero monomial of the quotient, so its number of steps is closely related to the number of non-zero coefficients. In particular, this map is shown to admit a finite invariant measure in contrast with the real case. This version of the Farey map also produces mediant convergents in the continued fraction expansion of formal power series with coefficients in a finite field.

Introduction

We fix a positive integer q which is a power of a prime number p, and we consider the field F q of cardinality q. It is well-known that the theory of continued fractions extends in a natural way the classical real framework to polynomials and formal power series with coefficients in the finite field F q . See for instance the survey [START_REF] Berthé | On continued fraction expansions in positive characteristic: equivalence relations and some metric properties[END_REF]. Similarly as in the real case, we have in this framework an intimate correspondence between the Euclidean algorithm and continued fraction expansions. We study and compare here digit-cost functions for the Euclidean algorithm, on the one hand, and for truncated trajectories for the Gauss map acting on the set of formal power series, on the other hand.

1.1. Euclid's algorithm on polynomials. Let us first recall the Euclidean algorithm for polynomials in F q [X]. For P and Q ∈ F q [X]withdegQ>deg P ≥ 0, the Euclidean division computes a pair (A, R)w i t hR = 0 or deg R<deg P for which Q = AP + R. The Euclidean algorithm is a sequence of Euclidean divisions; by setting R 0 := Q, R 1 := P, one gets

R 0 = A 1 R 1 + R 2 ,R 2 = 0 or deg R 2 < deg R 1 .
If R 2 = 0, then we can find, again, a pair of polynomials (A 2 ,R 3 ) such that

R 1 = A 2 R 2 + R 3 ,R 3 = 0 or deg R 3 < deg R 2 .
We can continue this procedure of divisions R k-1 = A k R k + R k+1 until the -th step where we obtain a remainder R +1 = 0. The last non-zero remainder R is a largest common divisor (polynomial) of R 0 and R 1 . In particular, R 0 and R 1 are coprime when deg R =0(i.e.,R ∈ F q The research of the second author was supported in part by Grant-in Aid for Scientific research (No.24340020) of Japan Society for the Promotion of Science. The research of the third author was supported in part by Grant-in Aid for Scientific research (No.23740088) of Japan Society for the Promotion of Science.

with R = 0). The Euclidean algorithm builds the continued fraction expansion of the fraction R 1 /R 0 , that is,

R 1 R 0 = 1 A 1 + 1 A 2 + •••+ 1 A .
Remark that the fraction R k+1 /R k is defined by the ending part of the continued fraction expansion, namely

R k+1 R k = 1 A k+1 + 1 A k+2 + •••+ 1 A .
We will use the notation L(P, Q)=L(R 1 ,R 0 )= for the length (i.e., the number of polynomial divisions) of the Euclidean algorithm. We also set L(0,Q) := 0.

Extended gcd and Bezout's coefficients. We similarly recall basic facts concerning the extended Euclidean algorithm. Let P and Q in F q [X], with 0 ≤ deg P<deg Q. Let := L(P, Q).

The extended Euclidean algorithm produces a pair of polynomials (S, T ) such that (1) gcd(P, Q)=SQ -TP with the help of the sequences (P k ,Q k ) defined as

(2) P -1 =1,P 0 =0,P k+1 = A k+1 P k

+ P k-1 ,Q -1 =0,Q 0 =1,Q k+1 = A k+1 Q k + Q k-1 .
Indeed, since the sequence (R k ) 0≤k≤ produced by the Euclidean algorithm satisfies

R 0 = Q, R 1 = P, R k+2 = R k -A k+1 • R k+1 , for 0 ≤ k ≤ ,
the equality (-1) k R k = P k-1 Q -Q k-1 P holds for any k with 0 ≤ k ≤ and yields [START_REF] Baladi | Euclidean algorithms are Gaussian[END_REF] for k = , with S =(-1) P -1 ,T =(-1) Q -1 .

Then, the computation (2) of the Bezout pair (S, T ) follows exactly the same lines as the computation of the fraction P -1 /Q -1 ,w h i c hd e fi n e st h e( -1)-th convergent of P/Q, that is,

P -1 Q -1 = 1 A 1 + 1 A 2 + •••+ 1 A -1 .
Cost of a division. We are interested in the cost of the Euclidean algorithm, where the cost is the total number of operations performed in F q . Since the algorithm is a sequence of divisions, we first focus on the cost of a single division on the pair (P, Q)w i t hd e gP<deg Q of the form Q = AP + R,w i t hR = 0 or deg R<deg P . One has deg Q =d e gA +degP . Such a division is performed with various operations on the field F q (divisions, products, subtractions, shifts). The number of most of the operations needed depends on the number of monomials which are present in the divisor P and the quotient Q. For any non-zero polynomial P , ν(P ) stands for the number of non-zero coefficients of P , i.e., the number of non-zero monomials in P . Of course, one has ν(P ) ≤ 1+degP , but, we wish to evaluate more precisely the number of operations over F q which are performed during the division Q = AP + R, as summarized in the following table.

Number of divisions in F q ν(A) Number of products in F q ν(A) • ν(P ) Number of subtractions in F q ν(A) • ν(P ) Upper bound for the number of shifts ν(A) • (deg Q + 1) Total number of operations in the field F q O(ν(A)

• (deg Q + 1))
The realistic bit-complexity of the Euclidean division would completely take into account the sparse representation of polynomials and would be related to the product ν(A)•ν(P ). Nevertheless, we have not succeeded to deal with this quantity in our cost estimates, as detailed in Remark 1 below.

Costs in the polynomial case. When the set of inputs is Ω={(P, Q) ∈ F q [X] 2 : Q monic,P= 0 or deg P<deg Q}, the execution of the (extended) Euclid Algorithm on the input pair (P, Q) ∈ Ωi sd e fi n e db yt h e number of steps := L(P, Q), and the three finite sequences of quotients (A k ) 1≤k≤ , remainders (R k ) 0≤k≤ and denominators (Q k ) 1≤k≤ ,w i t h

Q k := den 1 A 1 + 1 A 2 + ...+ 1 A k , deg Q k = k j=1 deg A j , R k =den 1 A k+1 + 1 A k+2 + •••+ 1 A • gcd(P, Q), deg R k = j=k+1 deg A j + deg gcd(P, Q), 0 ≤ k ≤ -1,R = gcd(P, Q).
We have now gathered all the required material in order to define our costs for both the Euclidean and the extended Euclidean algorithm on the input (P, Q).

Definition 1 (Costs in the polynomial case).

(i) The total number of non-zero monomials in the set of the quotients is

N (P, Q)= k=1 ν(A k ).
(ii) The usual bit-complexity B (as defined e.g. in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF])a n dt h efine bit-complexity φ of the Euclid algorithm on the input (P, Q) are

B(P, Q)= k=1 (1 + deg A k ) • (1 + deg R k ),φ (P, Q)= k=1 ν(A k ) • (1 + deg R k ).
(iii) The costs B and φ of the extended Euclid algorithm correspond to the the extra bitcomplexity for computing Bezout's coefficients, in their usual or fine versions

B(P, Q)= -1 k=1 (1 + deg A k ) • (1 + deg Q k-1 ),φ (P, Q)= -1 k=1 ν(A k ) • (1 + deg Q k-1 ).
(iv) The costs B + B,a n dφ + φ are the costs of the extended Euclidean algorithm, in their usual or fine version. They are called total costs.

1.2. Continued fractions. We let denote by F q (X), F q ((X -1 )), L the set of rational fractions, the set of Laurent formal series of the variable 1/X, and the subset of F q ((X -1 )) of series of negative degree, respectively. Here the degree of a non-zero element f ∈ F q ((X -1 )) with

f = a n X n + a n-1 X n-1 + ••• ,a n =0
is defined as deg f = n. We also define the degree of 0 ∈ F q by deg 0 = -∞ as usual. The norm of f is then defined as |f | = q deg f .

The analog of the Gauss map T on L is defined as

T (f )= 1 f - 1 f for f =0,T (0) = 0,
where [ • ] stands for the polynomial part for formal power series. In all that follows, the map T will be referred to as the Gauss map, by abuse of language. Then, the Gauss map builds the continued fraction expansion of f , that is,

f = 1 A 1 + 1 A 2 + ••• with A k = 1 T k-1 (f ) ,k ≥ 1.
The analog of the Gauss measure is the Haar measure µ L (normalized to 1 on L): it is ergodic and T -invariant.

Total costs on L. When f is a rational fraction P/Q of F q (X)w i t hd e gP<deg Q, it can be viewed as an element of L, and the iteration of the Gauss map on P/Q exactly coincides with the Euclid Algorithm on (P, Q): the trajectory of P/Q under the action of T arrives at 0 in a finite number of steps and stops there. In the general case of an element f , the trajectory is infinite, but we are interested by the truncated trajectories which are stopped at depth n, i.e., after n steps:

T n (f ):=(f, T(f ),...T n (f )).
The truncated continued fraction at depth n leads to a finite continued fraction expansion and produces a fraction equal to the n-th convergent of f , that is,

P n Q n = 1 A 1 + 1 A 2 + ••• 1 A n .
The computation of the pair (P n ,Q n ) follows the general recurrence already seen in ( 2), and we are interested in evaluating the cost of this computation in L (assuming that the sequence of partial quotients (A k ) has already been computed). We thus let denote by N n (f ) the total number of non-zero monomials in the sequence of partial quotients (A 1 ,A 2 ,...,A n ), and we also consider the bit-complexity costs needed for computing the n-th convergent, in their two versions. These costs are to be compared respectively to the costs introduced in (i) and (iii) above for the polynomial case.

Definition 2 (Costs in the continued fraction case).

(i) The total number of non-zero monomials in the sequence of partial quotients

(A 1 ,A 2 ,...,A n ) is N n (f ):= n k=1 ν(A k ).
(ii) The usual bit-complexity B n and the fine bit complexity φ n are

B n (f )= n k=1 (1 + deg A k ) • (1 + deg Q k-1 ),φ n (f )= n k=1 ν(A k ) • (1 + deg Q k-1 ).
1.3. Probabilistic models. We deal within two models, namely a discrete and a continuous one.

• The discrete model is defined by the sequence of finite sets Ω m of polynomials, with

Ω m = {(P, Q) ∈ F q [X] 2 : P = 0 or 0 ≤ deg P<deg Q = m, Q : monic}, (3)
endowed with the uniform probability denoted as P m . The expectation and the variance in this model are respectively denoted as E m and V m . We are interested there by the probabilistic behavior of costs N, B, φ, B,φ, in the finite set Ω m , for m tending to infinity. • The continuous model deals with the set L endowed with its Haar measure µ L .W es t u d y some costs which are relative to the truncated trajectory of f ∈ L at depth n, i.e., the costs N n ,B n and φ n . We consider in this case almost everywhere behavior when the truncation degree n tends to infinity.

Methodology. In the discrete model, the study of the fine costs uses classical methods from analytic combinatorics developed in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF] (such as recalled in Section 2). In the continuous model (see Section 4), we use the ergodic theorem, together with a suitable extension of the function ν (that counts the number of non-zero monomials) to the set L. Note that the ergodic theorem, which is well-suited for the study of truncated trajectories, does not provide any error term. We introduce in this paper (Section 5) an additive (also said subtractive in the continued fraction literature) version of the Gauss map, called here Farey map by analogy with the real case, which discovers the non-zero monomials of each quotient one by one. Then, this map can be used to study the function ν. The main difficulty relies in the fact that we need a transformation that gives a particular role to the constant term of the polynomial. We stress the fact that the definition of this map is not canonical, and there are indeed two natural definitions. We provide an explicit expression of an invariant measure for this map (see Theorem 8) which is absolutely continuous with respect to the Haar measure, and we show that it is a finite measure, in contrast to the original Farey map, which has an infinite absolutely continuous invariant measure with respect to Lebesgue measure. We then deduce metric results that can be applied to the study of the cost functions we are considering here. This map is also interesting per se because it gives rise to a notion of mediant convergents for F q ((X)) (see Section 6).

A brief overview of the literature. Many costs describing the execution of the Euclidean algorithm (in the discrete model), and of the continued fraction algorithm (in the continuous model), have been widely studied, in the classic number case, and also in the polynomial case.

The reader can find an historical account of the literature on the number case, both for the average and distributional analysis of costs, in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF] or [START_REF] Vallée | Dynamical analysis of a class of Euclidean algorithms[END_REF][START_REF] Vallée | Euclidean Dynamics[END_REF][START_REF] Ustinov | Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm[END_REF] and in the references therein. It is in particular known since [START_REF] Dixon | The number of steps in the Euclidean algorithm[END_REF][START_REF] Dixon | A simple estimate for the number of steps in the Euclidean algorithm[END_REF][START_REF] Heilbronn | On the average length of a class of finite continued fractions, Number Theory and Analysis[END_REF] that the average length of the Euclidean algorithm is linear with respect to the logarithm of the numbers taken as input, with the multiplicative constant being equal to the inverse of the entropy of the Gauss map multiplied by 2, with the factor 2 corresponding to the dimension, i.e., the number of parameters under consideration. For results in distribution concerning the length (i.e., for an asymptotic Gaussian law), see [START_REF] Hensley | The number of steps in the Euclidean algorithm[END_REF], and also [START_REF] Baladi | Euclidean algorithms are Gaussian[END_REF][START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF][START_REF] Vallée | Dynamical analysis of a class of Euclidean algorithms[END_REF][START_REF] Vallée | Euclidean Dynamics[END_REF] for a detailed distributional analysis, also involving more general cost functions.

We focus here on the polynomial case, where the study is simpler. Indeed there are no carries and the topology is ultrametric. Over F q [X], the length L of the Euclidean algorithm for polynomials is very precisely studied: on the set of polynomials with degree at most m, its mean and its variance are linear with respect to the degree m (see for instance [START_REF] Flajolet | Analytic combinatorics[END_REF][START_REF] Ma | Analysis of Euclidean algorithms for polynomials over finite fields[END_REF][START_REF] Norton | Precise analyses of the right-and left-shift greatest common divisor algorithms for GF (q)[x[END_REF] and [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF]). Its distribution is discussed in [START_REF] Knopfmacher | The exact length of the Euclidean algorithm in Fq[X][END_REF][START_REF] Friesen | The statistics of continued fractions for polynomials over a finite field[END_REF], where it is proven to be binomial. Note in particular that the mean of L is exactly (q -1)/q • m on the set of polynomials with degree less than m; the constant (q -1)/q equals 2/h where h is the entropy of the Gauss map, that is, 2q/(q -1). Furthermore, the usual bit-complexities B, B,B + B are studied in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF], where they are proven to obey an asymptotic Gaussian law. In particular,

E m [B]=m 2 2q -1 2q +O(m), V m [B]=m 3 q -1 3q 2 +O(m 2 ), P m 1 m 2 B - 2q -1 2q ≥ 1/ε = O ε 2 m .
However, the fine bit-complexity φ has not been previously handled.

The results in the polynomial case are obtained via analytic combinatorics (see [START_REF] Flajolet | Analytic combinatorics[END_REF]), with the direct study of bivariate generating functions. In the integer case, the non-ultrametricity of the topology prevents the direct use of generating functions, which are replaced by Dirichlet series. However there is a strong parallelism between the two studies. It is indeed observed in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF] that results in the polynomial case could be obtained via the use of transfer operators (as in the integer case) within the framework of dynamical analysis, which is the central tool in the number case. This is due to the common framework between the integer and the polynomial case, given by the underlying dynamical system, namely the Gauss map, with the branches of the dynamical systems being affine for the polynomial case leading to a dynamical system without memory. For a detailed discussion on the parallelism between the integer and the polynomial case, both for the results and the methods, see Section 6 in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF].

There is a further parallelism that occurs, both in the integer and in the polynomial case, between the probabilistic behavior for costs in the discrete model and in the continuous model, that is, for orbits of rational entries and for truncated trajectories under the action of the Gauss map. As highlighted in [START_REF] Baladi | Euclidean algorithms are Gaussian[END_REF][START_REF] Vallée | Euclidean Dynamics[END_REF], executions of the Euclidean algorithm behave on average similarly to the way truncated real trajectories behave on average (this also extends to distributions), and the probabilistic behavior of gcd algorithms related to rational trajectories is quite similar to the behavior of their continuous counterparts, related to generic trajectories.

We stress the fact that concerning the ultrametric version of the Farey map, its invariant measure is finite, unlike in the usual real case.

Description of the results. Here, we wish to study the costs N, φ, φ in the discrete model, and N n ,φ n in the continuous model. As in the previously described studies, we deal in the discrete model with the probabilistic behavior of finite trajectories on the set of pairs of polynomials Ω m (see ( 3)), and in the continuous model, we deal with truncated trajectories and obtain results which hold almost everywhere.

For finite trajectories in the discrete model, we obtain (namely in Theorems 1, 3, below), first for the cost N ,

E m [N ]=m • 2(q -1) q , V m [N ]=m 2(q -1) q 2 + O(1), P m 1 m N -2 q -1 q ≥ 1/ε = O ε 2 m
and both for costs φ or φ,

E m [φ]=m 2 q -1 q +O(m), V m [φ]=m 3 2(q -1) 3q 2 +O(m 2 ), P m 1 m 2 φ - q -1 q ≥ 1/ε = O ε 2 m .
We obtain also asymptotic Gaussian laws for the costs L, D, N and φ + φ (namely in Theorems 2, 4, below).

For truncated trajectories, we obtain the following results that hold for a.e. f ∈ L:

lim n→∞ N n deg Q n (f )=2• q -1 q and lim n→∞ 1 deg 2 Q n φ n (f )= q -1 q ,
which correspond respectively to Theorem 5 and 6 below.

There results confirm the fact that the probabilistic behavior of gcd algorithms related to rational trajectories is quite similar to the behavior of their continuous counterparts, related to generic trajectories, which was already observed for the bit-complexity [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF].

Remark 1. A more realistic bit-complexity of the Euclidean division would be provided by the study of the product ν(A) • ν(P ). Nevertheless, we have not succeeded to deal with this quantity in our cost estimates. Indeed, we know how to handle each factor ν(A k ), or deg A k . However, we do not know how to handle ν(R k ) or ν(Q k ), whereas it is easy to deal with their degrees, equal to the sum of the degrees of A j . Our fine complexity φ can be considered as an intermediate complexity, between the usual bit complexity and the complexity

k=1 ν(A k ) • ν(R k ), that is, k=1 (deg A k + 1)(deg R k + 1) ≤ φ(P, Q) ≤ k=1 ν(A k ) • ν(R k ).
Contents. Let us briefly describe the contents of the paper. We first consider the discrete model associated with polynomials in Section 2 by recalling the methods of analytic combinatorics based on generating functions. Elementary costs are considered (the cost N in particular) as a warm-up.

We then discuss in more details the average behavior of the fine-bit complexity costs φ and φ + φ in Section 3. Section 4 is devoted to the continuous model. We obtain, via the ergodic theorem, the almost everywhere behavior of the total number of non-zero coefficients N n (f ) and of the fine bit-complexity φ n (f ). In Section 5 we introduce and discuss two versions for a Farey map, and we show how to apply the corresponding metric results to recover the statistical study of cost functions. The Farey map is lastly seen to produce mediant convergents in the continued fraction expansion in the Appendix (Section 6).

Probabilistic estimates of cost functions via analytic combinatorics methodology

In this section, we show how to deduce information concerning the probabilistic behavior of cost functions in the discrete model. Here, we use classical methods in analytic combinatorics. We first recall in Section 2.1, 2.2 and 2.3 the basic approach used for the study of additive costs, such as developed e.g. in [START_REF] Flajolet | Analytic combinatorics[END_REF][START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF][START_REF] Vallée | Euclidean Dynamics[END_REF]. Then, Section 2.4 is devoted to the study of some basic costs defined on polynomials, whereas Section 2.5 and 2.6 analyse the corresponding simple additive costs related to the execution of the Euclidean algorithm for pairs of polynomials.

2.1. Basic generating functions. Recall that

Ω={(P, Q) ∈ F q [X] 2 : Q monic,P= 0 or deg P<deg Q }.
The size of a pair (P, Q) ∈ Ω is equal by definition to deg Q, and the subset Ω m formed by the elements of Ω of size m (with m ≥ 0) has cardinality |Ω m | = q 2m . Then, the generating function

T Ω (z) of Ω is T Ω (z):= m≥0 |Ω m |z m = 1 1 -q 2 z .
As it is well known (see for instance [START_REF] Flajolet | Analytic combinatorics[END_REF], Example IX.15), an element (P, Q) of Ω is uniquely determined, through Euclid's algorithm, by the finite sequence of the quotients (A 1 , ••• ,A )(where each A i is of degree at least one), together with its gcd (which is here monic).

(If P = 0, then the sequence (A 1 , ••• ,A )i se m p t y . ) W et h u si n t r o d u c et h es e t s G = {P ∈ F q [X]:d e gP ≥ 1} and U = {P ∈ F q [X]:P is monic},
where G is the set of possible quotients, and U is the set of possible gcd's. Euclid's algorithm thus provides the following bijection

(4) Ω = Seq(G) •U,
where Seq(G) stands for the set of finite sequences of elements of G.

The generating functions of the sets G and U are easily determined, namely

U (z)= 1 1 -qz ,G (z)=(q -1) 1 1 -qz -1 = (q -1)qz 1 -qz . Note that 1 1 -G(z) = 1 -qz 1 -q 2 z .
We thus check the indentity

(5) T Ω (z)= 1 1 -G(z) • U (z)
which 'copies' the bijection (4).

2.2. The general approach. Our general approach follows the main following lines, that are classical in analytic combinatorics. For more details, see also [START_REF] Flajolet | Analytic combinatorics[END_REF][START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF][START_REF] Vallée | Euclidean Dynamics[END_REF]. Let c be a cost defined on the set G⊂F q [X], and define the following additive cost C relative to the execution of the Euclidean algorithm on the input (P, Q) ∈ Ω ( 6)

C(P, Q):= L(P,Q) i=1 c(A i ),
where A i = A i (P, Q) are the quotients and L(P, Q) is the number of steps of Euclid's algorithm. We wish to obtain probabilistic estimates for the cost C on the set Ω, for instance evaluate its expectation As the cost C is an additive cost associated with the cost c defined on the set G,w et h e nd e d u c e from (5) a relation between these generating functions, namely [START_REF] Friesen | The statistics of continued fractions for polynomials over a finite field[END_REF] T

C (z, u)= 1 1 -S c (z, u) • U (z).
We are interested in three costs of type C, namely the cost L, the cost D and the cost N respectively related to the following costs c equal to [START_REF] Heilbronn | On the average length of a class of finite continued fractions, Number Theory and Analysis[END_REF] 1,d := 1 + deg,ν .

Section 2.4 provides a simple expression of the generating functions of type S c associated with these three costs, then we will handle the costs C = L, C = D, C = N , via their generating functions of type T C , in Section 2.5 and 2.6, where their asymptotic Gaussian law will be established. But before handling these cases, we will recall in the next section how to deduce estimates for the expectation and the variance from the generating functions. The series S (c) (z),T (C) (z) are obtained by taking the derivative of S c (z, u),T C (z, u)w i t hr e s p e c t to u, at u = 1, i.e., ( 9)

S (c) (z)= ∂ ∂u S c (z, u)| u=1 ,T (C) (z)= ∂ ∂u T C (z, u)| u=1 .
We thus deduce from ( 7) that ( 10)

T (C) (z)=S (c) (z) • 1 1 -G(z) 2 • U (z).
The expectations E m [c], E m [C] are now obtained via the extraction of the coefficient of z m in the generating functions S (c) and T (C) , that is,

E m [c]= [z m ]S (c) (z) (q -1)q m , E m [C]= [z m ]T (c) (z) q 2m .
In the same vein, the series S (c 2 ) (z),T (C 2 ) (z) are related to the second derivative, via the equalities ( 11)

S (c 2 ) (z) -S (c) (z)= ∂ 2 ∂ 2 u S c (z, u)| u=1 ,T (C 2 ) (z) -T (C) (z)= ∂ 2 ∂ 2 u T C (z, u)| u=1 .
The expectations

E m [c 2 ], E m [C 2
] are now obtained via the extraction of the coefficient of z m in the generating functions S (c 2 ) and T (C 2 ) .

2.4. Costs c on G. We now consider the three costs c defined in [START_REF] Heilbronn | On the average length of a class of finite continued fractions, Number Theory and Analysis[END_REF].

Lemma 1. The generating functions S c (z, u) for the three costs of interest are

S 1 (z, u)=uG(z),S d (z, u)=uG (zu),S ν (z, u)=uG z u q -1 q + 1 q .
The cumulative generating functions are

S (1) (z)=G(z),S (d) (z)=G(z)+zG (z) S (ν) (z)=G(z)+ q -1 q zG (z).
Proof. Let us recall that [z m u k ]S c (z, u)=|{P ∈G :d e gP = m and c(P )=k}| . The variable u in S 1 (z, u) occurs with power 1 for every polynomial of G,w h i c hy i e l d sS 1 (z, u)=uG(z). For the cost d = 1 + deg, one gets S d (z, u)=uG(zu), where the multiplication of the term G(zu)b y u corresponds to 1, and the mutiplication by u in G(uz) corresponds to the degree. Lastly, for the cost ν that counts the number of non-zero monomials, the multiplication of the G term by u corresponds to the leading term (which is non-zero), whereas the multipication of z by u q-1 q + 1 q in the G term takes into account the remaining monomials. Recall that G(z)=(q -1) • ( 1 1-qz -1). For each polynomial of a given degree, there are (q -1)/q choices for the non-zero terms, and one choice over q for the zero terms.

We then deduce from ( 9) and ( 11) the following on G m :

E m [1] = 1, E m [d]=m +1, E m [ν]=1+ q -1 q • m, V m [ν]= q -1 q 2 • m.
Note that these costs are easy to study in a direct way. For instance, the variable ν -1i st h e sum of m Bernoulli variables of parameter (q -1)/q, that is, the distribution of ν -1 is binomial. 2.5. Expectation and variance for costs C on Ω. Here, the costs of interest are of the form

C(P, Q)= (P,Q) i=1 c(A i ),
and involve the value of the cost c on the quotients A i = A i (P, Q) of the Euclidean algorithm. The following theorem is a direct application of ( 10) and [START_REF] Ito | Algorithms with mediant convergents and their metrical theory[END_REF].

Theorem 1. On the set Ω m , the expectation and the variance of the costs L, D, N satisfy

E m [L]=m q-1 q , V m [L]=m q-1 q 2 E m [D]=m 2q-1 q + O(1), V m [D]=m q-1 q 2 + O(1) E m [N ]=2m q-1 q + O(1), V m [N ]=2m q-1 q 2 + O(1). Furthermore, for C ∈{L, D, N } (12) P m 1 m (C -E m [C]) ≥ 1/ε = O ε 2 m .
Proof. We deduce (12) from a direct application of Chebyshev inequality.

2.6. Asymptotic normal laws for costs C on Ω. We follow here Definition 1 of [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF].

Definition 3 (Asymptotic Gaussian law). Let R be a cost defined on Ω.T h ec o s tR is said to follow an asymptotic Gaussian law if there exist two sequences of real numbers (a m ) m , (b m ) m ,a n d a sequence (r m ) m of functions r m : R → R,w i t hlim m→∞ sup{r m (y):y ∈ R} =0, for which

P m (P, Q) ∈ Ω m : R(P, Q) -a m √ b m ≤ y = 1 √ 2π y -∞ e -t 2 /2 dt + r m (y).
The expectation E m [R] and the variance V m [R] then satisfy

E m [R] ∼ a m , V m [R] ∼ b m .
Theorem 2. The three costs L, D, N follow an asymptotically Gaussian law on Ω.

Proof. We consider here a cost C ∈{L, D, N }. The expectation of the random variable u C (for u a complex number close to 1) on the set Ω m satisfies

E m [u C ]= [z m ]T C (z, u) [z m ]T C (z, 1) = 1 q 2m [z m ]T C (z, u)w i t h T C (z, u)= U (z) 1 -S c (z, u)
.

By Lemma 1, we know that, for any of the three costs c, the generating function S c (z, u) is always of the form S c (z, u)=uG(zρ), with

ρ = 1 (for c = 1),ρ = u (for c = d =1+deg),ρ = u • q -1 q + 1 q (for c = ν).
One then checks that T C (z, u) can be written in the form

T C (z, u)= U (z) 1 -uG(zρ) = 1 -qzρ (1 -qz)(1-qzρ(u(q -1) + 1))
.

Then, in each case, as a function of the variable z, the generating function T C (z, u) has two poles, namely

z c = 1 qρ(u(q -1) + 1)
, and z = 1 q .

When u is close to 1, the first pole z c (which depends on the cost c via the value of ρ) is close to 1/q 2 : it is thus the dominant one, and

[z m ]T C (z, u)=(qρ(u(q -1) + 1)) m • 1 -qz c ρ 1 -qz c • (1 + O ((qz c ) m )) .
Then, uniformly on a complex neighborhood of u = 1, one has

E m [u C ]=A c (u) • B c (u) m 1+O 1 κ m c
where A(u), B(u) are analytic at u = 1, and

B c (u)=ρ u q -1 q + 1 q ,κ c ∼ 1 q .
It remains to apply the quasi-power theorem (see [START_REF] Hwang | On convergence rates in the central limit theorems for combinatorial structures[END_REF] and Theorem IX-8 in [START_REF] Flajolet | Analytic combinatorics[END_REF]) which gives a central limit theorem with speed of convergence for random variables whose moment generating function has a 'quasi-power' structure. It thus applies to each random variable C provided that the coefficient of the variance V m [C] is not zero, which is true for the three cases under consideration.

E m [φ]= q -1 q • m 2 + O(m) V m [φ]= 2 3 q -1 q 2 • m 3 + O(m 2 ). Furthermore (13) P m 1 m 2 φ - q -1 q ≥ 1/ε = O ε 2 m .
The same estimates hold for the fine complexity φ.

We recall the similar results which have been previously obtained in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF] for the classical bit complexity B

E m [B]= 2q -1 2q • m 2 + O(m) V m [B]= q -1 3q 2 • m 3 + O(m 2 ).
Proof. Remark first that the estimates of Theorem 3 also hold for φ and for φ since the two fractions 1

A 1 + 1 A 2 + •••+ 1 A and 1 A + 1 A 2 + •••+ 1 A 1
have the same denominator. For a general additive cost C (associated with the cost c as in ( 6)), we can adopt a viewpoint that is different from the one developed in Section 2, first in order to recover [START_REF] Hwang | On convergence rates in the central limit theorems for combinatorial structures[END_REF].

We first fix a length L, that is, we work with finite sequences of L quotients in G L . We consider the cost C i := c(A i ), defined on the set G L , for a given i with 1 ≤ i ≤ L. The cumulative generating function of the cost C i on the class Ω [L]

:= G L ×U is G i-1 (z) • S (c) (z) • G L-i (z) • U (z),
by recalling that S (c) (z) is the cumulative generating function of cost c on the set G. Finally, the cumulative generating function T (C) (z) of the cost C on the class Ω is obtained by taking the sum over all the indices (i, L)w i t hi ≤ L,w h i c hy i e l d s ( 14)

T (C) (z)= 1 1 -G(z) • S (c) (z) • 1 1 -G(z) • U (z),
and we recover [START_REF] Hwang | On convergence rates in the central limit theorems for combinatorial structures[END_REF]. This will be the viewpoint we now adopt in the present proof.

Recall that

φ(P, Q)= L(P,Q) i=1 ν(A i ) • (1 + deg R i ), deg R i = L(P,Q) j=i+1 deg A j + deg gcd(P, Q).
For a given integer i with 1 ≤ i ≤ L, the generating function of the cost ν(A i ) • u 1+deg Ri on the class G L ×U is as previously (compare with ( 14))

G i-1 (z) • S (ν) (z) • u • G L-i (uz) • U (uz).
Then, the generating function of the cost

L(P,Q) i=1 ν(A i ) • u 1+deg Ri
on the class Ω is obtained by taking the sum over all the indices (i, L)w i t h1≤ i ≤ L,w h i c h yields

1 1 -G(z) • S (ν) (z) • u • 1 1 -G(uz) • U (uz).
Finally, the cumulative generating function T (φ) (z) of the cost φ on Ω is obtained by taking the derivative with respect to u at u = 1, which yields

E m [φ]= 1 q 2m [z m ]T (φ) (z)= q -1 q • m 2 + q -2 q • m + O(1).
For the variance, we follow an extension of the previous approach which is proposed for instance in [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF][START_REF] Vallée | Euclidean Dynamics[END_REF] in the framework of the study of additive costs associated with Euclidean algorithms for integers, when handling the expectation E m [φ 2 ] in order to produce an estimate concerning the variance. The cost φ 2 is written as

φ 2 =2 i<j≤L ν(A i )(1 + deg R i ) • ν(A j )(1 + deg R j )+ i≤L ν(A i ) 2 (1 + deg R i ) 2 .
We will distinguish two cases, namely pairs i<j, then pairs i = j.

Non-diagonal terms. We first fix a length L and consider for any pair i<j≤ L an intermediate cost of the form

ν(A i ) • u 1+deg Ri • ν(A j ) • v 1+deg Rj ,
whose generating function on the class Ω [L] = G L ×U is equal to

G i-1 (z) • S (ν) (z) • u • G j-i-1 (uz) • S (ν) (uz) • v • G L-j (uvz) • U (uvz).
Taking the sum over all the indices (i, j, L)w i t h1≤ i<j≤ L gives

1 1 -G(z) • S (ν) (z) • u 1 -G(uz) • S (ν) (uz) • v 1 -G(uvz) • U (uvz).
Then, the cumulative generating function of the part of the cost φ 2 relative to the pairs i = j is obtained by taking the derivative with respect to u and v at u = 1 and v = 1, and then by multiplying by 2. Its general term in [z m ] satisfies

(q -1) 2 q 2 • q 2m m 4 + 2 3q 2 (q -6)(q -1) • m 3 q 2m + O(m 2 ).
Diagonal terms. For the diagonal pairs i = j, we consider the cost ν 2 (A i ) • u 1+deg Ri on the class Ω [L] , for 1 ≤ i ≤ L, and we take the sum over all the pairs (i, L)w i t hi ≤ L, that is,

1 1 -G(z) • S (ν 2 ) (z) • u • 1 1 -G(uz) • U (uz).
Then, the cumulative generating function of the part of the cost φ 2 relative to the pairs i = j is obtained by taking the sum of the first derivative and the second derivative of the previous expression with respect to u at u = 1, and its general term in [z m ] satisfies 2 3q 2 (2q + 1)(q -1) • m 3 q 2m + O(m 2 q 2m ).

We deduce that

V m [φ]= 2(q -1) 3q 2 • m 3 + O(m 2 ).
Lastly, ( 13) is a direct consequence of Chebyshev inequality.

3.2.

Asymptotic Gaussian law for the total fine complexity. The asymptotic normal laws for costs φ or φ seem to be more difficult to obtain. Nevertheless the total fine complexity φ + φ can be proven to be asymptotically Gaussian.

Theorem 4. On the set Ω,t h ec o s tφ + φ is asymptotically Gaussian.

We will prove below that the cost φ + φ decomposes as the sum of several costs. The main part will be provided by the cost X := N (P, Q) • deg Q, which is asymptotically Gaussian, according to Theorem 2. We then will prove that the other terms are asymptotically more concentrated, that is, their respective variances are negligible with respect to the variance of X. The proof of Theorem 4 then relies on the following result. Proposition 1. [START_REF] Lhote | Gaussian laws for the main parameters of the Euclid algorithms[END_REF] Two costs X, Z defined on Ω are said to be variance equivalent with order

1/n if V n [X -Z]=1/n • (V n [X]
) when n tends to ∞. We assume furthermore that X admits an asymptotic Gaussian law. Then Z admits also an asymptotic Gaussian law with a variance that satisfies

V n [Z]=V n [X] • (1 + O( 1/n)).
Proof. Let us prove now Theorem 4. One has, according to Definition 1,

(φ + φ)(P, Q)= -1 k=1 ν(A k ) • (2 + deg Q k-1 +degR k )+ν(A )(1 + deg R ), with = L(P, Q). Consequently (φ + φ)(P, Q)= k=1 ν(A k ) • (2 + deg Q k-1 +degR k ) -ν(A )(1 + deg Q -1 ). The equality deg Q k-1 +degR k =degQ -deg A k entails the relation (φ + φ)(P, Q)=N (P, Q) • deg Q +2N (P, Q) - k=1 ν(A k ) • deg A k -ν(A )(1 + deg Q -1 ).
The conclusion of the theorem follows from Proposition 1 applied to

X = N (P, Q) • deg Q by noticing that V m [N (P, Q) • deg Q]=Ω(m 3
), and then successively to the terms of

Z -X =2N (P, Q) - k=1 ν(A k ) • deg A k -ν(A )(1 + deg Q -1 ),
by proving that their respective variance is in O(m 2 ) (or even in O(m)).

• We first consider the main term which corresponds to the cost

X = N (P, Q) • deg Q.T h e variance of X is equal to m 2 V m (N ), that is, by Theorem 1 V m (X)=m 2 • V m [N ]=m 3 • 2(q -1)/q 2 + O(m 2 ).
Furthermore, the asymptotic Gaussian law holds for N (Theorem 2), which implies the asymptotic Gaussian law for X.

• We recall from Theorem 1 that V m [N ]=O(m).
• We then consider the additive cost associated with the cost ν(A)

• deg A. By noticing that ν(A) • deg A ≤ (1 + deg A) 2 , we get V m k=1 ν(A k ) • deg A k ≤ E m i,j≤ ν(A i ) • deg A i • ν(A j ) • deg A j ≤ E m i,j≤ (1 + deg A i ) 2 • (1 + deg A j ) 2 =2E m i<j≤ (1 + deg A i ) 2 • (1 + deg A j ) 2 + + E m i≤ (1 + deg A i ) 4 .
Similarly as in the proof of Theorem 3, if we fix a length ≥ 1, the generating function corresponding to the pairs i = j is

G i-1 • S (d 2 ) (z) • G j-i-1 • S (d 2 ) (z) • G -j • U (z).
Taking the sum overall the indices 1 ≤ i<j≤ yields the generating function

1 1 -G(z) 3 • (S (d 2 ) (z)) 2 • U (z).
Similarly, the cumulative generating function corresponding to the diagonal pairs i

= j is 1 1 -G(z) 2 • S (d 4 ) (z) • U (z).
In the first case, the expectation is in O(m 2 ), and in the second case, it is in O(m). • Finally, it remains to consider the cost = ν(A l )(1 + deg Q l-1 ). One has

V m [ν(A )(1 + deg Q l-1 )] ≤ E m (ν(A l )(1 + deg Q l-1 )) 2 ≤ m 2 • E m [ν 2 (A )].
Similarly as in the proof of Theorem 3, if we fix a length ≥ 1, the generating function of the cost ν 2 (A )i s

G -1 • S (ν 2 ) (z) • U (z). Taking the sum over ≥ 1 yields the generating function 1 1 -G(z) • S (ν 2 ) (z) • U (z), wich provides E m [ν 2 (A )] = O(1) and V m [ν(A )(1 + deg Q -1 )] = O(m 2 ).

Study of the main cost functions of interest in the continuous model

We now consider the continuous model, that is, L endowed with the Haar measure µ L , together with the costs N n and φ n related to truncated trajectories T n (f ) under the action of the Gauss map, with

T n (f )=(f, T(f ), ••• ,Tn(f )).
In particular, we are interested in the behavior of the random variable ν that counts the number of non-zero coefficients in partial quotients.

4.1. The Gauss map and the topology of the set L. We first need preliminary results concerning the behavior of the Gauss map with respect to cylinders (see Definition 4 below). These results will also be used in Section 5.3.

Recall that, for f ∈ F q ((X -1 )), the degree is equal to the opposite of the valuation of the series f , namely,

deg f = -m if and only if f = b m X -m 1+ 1 X • g with b -m =0, deg g ≤ 0.
We also recall that the notation L stands for the subset of F q ((X -1 )) formed with elements f with deg f<0, and, for m ≥ 1, we set

L m := {f ∈ L :d e gf = -m}.
We now want to get a simple expression of the Gauss map T :

L → L, f → 1 f - 1 f ([•]
stands for the polynomial part for formal power series) (see Proposition 2 below). For that purpose, we introduce the following notation.

We fix ≥ 1. For an element f ∈ F q ((X -1 )), let π =( π 0 ,π 1 ,...π -1 ) be the element of F q which defines, together with the dominant coefficient γ(f ), the 'beginning' of f (of length ) formed with the part of f with indices -k ∈ [deg f, deg f + ]. Note that π depends on f and . More precisely, if m =deg f (m ≥ 1), then f can be written in the form

(15) f = γ(f )X -m 1+ 1 X • π 1 X + X -(m++1) g, deg g ≤ 0,
where π is the polynomial of degree at most -

1 related to π, π(X)=π 0 + π 1 X + ...π -1 X -1 .
When f decomposes as in [START_REF] Norton | Precise analyses of the right-and left-shift greatest common divisor algorithms for GF (q)[x[END_REF], its inverse 1/f satisfies

1 f = X m γ(f )     1 1+ 1 X • π 1 X     + X m--1 h, with deg h ≤ 0.
Then the 'beginning part' of 1/f formed with its terms of index k ∈ [m, m -] only involves the powers π k of the polynomial π, with exponents k ≤ , and more precisely the polynomials

π [k] := π k mod X -k ,i . e . , 1 f = X m γ(f ) 1+ k=1 (-1) k X -k • π [k] (1/X) + X m--1 h.
Note that the beginning part of 1/f formed with the terms with power k ∈ [m, m-] only depends on the pair (γ(f ),π(f )). Hence, with π ∈ F q , we associate θ ∈ F q via its polynomial θ,w h i c hi s itself defined as

Xθ(X)= k=1 (-1) k X k • π [k] (X).
For each , the map ψ : F q → F q ,π → θ defines an involutive bijection of F q onto itself. In particular, one has ψ(0 )=0 . There is a precise relation between the polynomial [1/f ] and the sequence π defined in [START_REF] Norton | Precise analyses of the right-and left-shift greatest common divisor algorithms for GF (q)[x[END_REF] for = m =deg f .W h e nf decomposes as in [START_REF] Norton | Precise analyses of the right-and left-shift greatest common divisor algorithms for GF (q)[x[END_REF], the integer part [1/f ] is completely defined by the sequence ψ(π), namely, 1

f = X m γ(f ) 1+ 1 X ψ(π) 1 X .
Definition 4 (Cylinders). For a ∈ F q , and for a sequence π ∈ F q , we consider the cylinder E [-m,a,π] which gathers the elements f ∈ L m which are written as in [START_REF] Norton | Precise analyses of the right-and left-shift greatest common divisor algorithms for GF (q)[x[END_REF], with γ(f )=a.

The set L m is the union of all the cylinders E [-m,a,π] ,w h e na varies in F q , π describes the set F q , and takes all values larger than or equal to 1. Moreover the measure of each cylinder is equal to q -(m+) , and the measure of L m equals (q -1)q -m . Proposition 2. For each m ≥ 1, the mapping defined on L m with values in F q × F m q which associates with f the polynomial [1/f ] is a surjection which is constant on each cylinder E [-m,a,π] with π ∈ F m q and a ∈ F q . Proof. It is a direct consequence of the equivalence [START_REF] Schweiger | Ergodic theory of fibred systems and metric number theory[END_REF] f

∈ E [-m,a,π] ⇐⇒ 1 f ∈ E [m,1/a,ψ(π)] . 4.2. Study of cost N n . The cost N n is defined as N n (f )= n k=1 ν 1 T k-1 (f )
. If we now define ν on L by [START_REF] Ustinov | Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm[END_REF] ν(f

):=ν([1/f ]),
the cost N n is defined as

N n (f )= n k=1 ν(T k-1 f ),
and this is just the total cost of the truncated trajectory

T n (f )={f, T(f ), ••• ,T n (f )} related to the basic cost ν. Theorem 5. For µ L -a.e. f ,o n eh a s lim n→∞ 1 n N n (f )=2, lim n→∞ 1 n deg Q n (f )= q q -1 , lim n→∞ N n deg Q n (f )=2• q -1 q .
Proof. With Proposition 2, and for each m ≥ 1, the distribution of ν -1 on L m is the same as the distribution of ν on F m q which is a binomial distribution. In particular the expectation of ν on F m q equals m(q -1)/q. Then, the expectations of ν -1 and ν on L satisfy

E[ν -1] = m≥1 q -1 q m m q -1 q =1, E[ν]=2.
Remark that the expectation ofdeg on L equals (see also [START_REF] Berthé | On continued fraction expansions in positive characteristic: equivalence relations and some metric properties[END_REF])

E[-deg] = m≥1 q -1 q m m = q -1 q .
Then the ergodic theorem applied to the two functions ν -1 and deg yields the result.

4.3.

Fine bit-complexity. We now consider the fine bit complexity φ n relative to the computation of the n-th convergent of an element of L defined as

φ n (f )= n k=1 ν(A k ) • (1 + deg Q k-1 ).
It can also be expressed with the degrees of the quotient A j as

φ n (f )= n k=1 ν(A k ) •   1+ k-1 j=1 deg A j   = n k=1 ν(A k )+ n k=1 ν(A k ) k-1 j=1 deg A j .
Then, we apply the following result:

Proposition 3. Let (V n ) and (W n ) be stationary and ergodic sequences of non-negative valued random variables on a probability space (Ω, F,P) with finite expectations µ V and µ W , respectively. For P -a.e. ω ∈ Ω, we have

lim N →∞ 1 N 2 N k=1 V k N j=k+1 W j = 1 2 µ V µ W .
Proof. Let us fix ε>0. From the individual ergodic theorem, there exists a positive integer M 0 such that for any integer M ≥ M 0 , the following holds:

1 M M i=1 V i -µ V <ε, 1 M M i=1 W i -µ W <ε.
Let N ≥ M 0 be a positive integer. One has

N t=1 V t t s=1 W s = M0-1 t=1 V t t s=1 W s + N t=M0 V t t s=1 W s .
We take now N large enough (with N ≥ M 0 ) for ( 18)

1 N M0-1 t=1 V t ≤ ε and 1 N 2 M0-1 t=1 V t t s=1 W s ≤ ε.
For t ≥ M 0 , one has

t (µ W -ε) ≤ t s=1 W s ≤ t (µ W + ε).
Since the random variables take non-negative values, one gets

(19) ( N t=M0 tV t )(µ W -ε) ≤ N t=M0 V t t s=1 W s ≤ ( N t=M0 tV t )(µ W + ε).
By applying Abel's transform, one gets

N t=1 tV t = N ( N t=1 V t ) - N -1 t=1 t s=1 V s .
One has

N (µ v -ε) ≤ N t=1 V t ≤ N (µ v + ε).
We also take N large enough (with

N ≥ M 0 ) for 0 ≤ M0-1 t=1 t s=0 V s ≤ N 2 ε and 0 ≤ M0-1 t=1 tV t ≤ N 2 ε.
Hence we get

(N -1) 2 -M 2 0 2 (µ v -ε) ≤ N -1 t=M0 t s=1 V s ≤ N -1 t=1 t s=1 V s ≤ N (N -1) 2 (µ v + ε) -N 2 ε.
This yields that

N 2 ε - (N -1) 2 -M 2 0 2 (µ v + ε)+N 2 (µ v -ε) ≤ N t=1 tV t ≤ N 2 (µ v + ε) - (N -1) 2 -M 2 0 2 (µ v -ε). Since N t=1 tV t -N 2 ε ≤ N t=M0 tV t ≤ N t=1
tV t , this yields, together with ( 18) and ( 19), that lim

N →∞ 1 N 2 N t=1 V k t s=1 W s = 1 2 µ V µ W .
We then conclude by noticing that lim

N →∞ 1 N 2 N k=1 V k k j=1 W j +l i m N →∞ 1 N 2 N k=1 V k N j=k+1 W j =l i m N →∞ 1 N 2 N k=1 V k   N j=1 W j   = µ W µ V .
. Applying Proposition 3 to the sequences V k = ν(A k ) (of non-zero coefficients of A n ) and W k =degA k with respective expectations 2 and q/q -1 (by Theorem 5) leads to the result: Theorem 6. For µ L -a.e. f ∈ L, we have

lim n→∞ 1 n 2 φ n (f )= q q -1 , lim n→∞ 1 (deg Q n (f )) 2 • φ n (f )= q -1 q .
This result has to be compared to Theorem 3 to confirm the parallelism of the results in the discrete model and in the continuous one. The following corollary is deduced from the fact that a.e. convergence implies convergence in probability: Corollary 1. For any ε>0 and η>0, there exists a positive integer n 0 such that for any n ≥ n 0 we have

µ L {f ∈ L : 1 (deg Q n (f )) 2 • φ n (f ) - q -1 q >ε} <η.
The previous results confirm the analogy between the behavior of generic truncated trajectories and rational trajectories. Furthermore, we can also consider the costs applied to the pair of polynomials (P n ,Q n ). More precisely, for f ∈ L, let P n := Pn γ(Pn) and

Q n := Qn γ(Qn) for n ≥ 1. We have Q n monic and ( P n , Q n ) ∈ Ω m with deg( Q n )=m. One has φ( P n , Q n )=φ n (f ).
One proves similarly as previously the following results concerning φ( P n , Q n ) by noticing that P n and Q n are coprime.

Theorem 7. For µ L -a.e. f ∈ L, we have

lim n→∞ 1 n 2 φ( P n , Q n )= q q -1 ,l i m n→∞ 1 (deg Q n (f )) 2 • φ( P n , Q n )= q -1 q .
Corollary 2. For any ε>0 and η>0, there exists a positive integer n 0 such that for any n ≥ n 0 we have

µ {f ∈ L : 1 (deg Q n (f )) 2 • φ( P n , Q n ) - q -1 q >ε} < 1 -η.
Remark 2. The analogy between the discrete and the continuous models can also be illustrated as follows. For any fixed polynomial A in G and for any fixed i ≥ 1, one has 1

q 2m •|{(P, Q) ∈ Ω m : A i (P, Q)=A}| → m→∞ µ L ({f ∈ L : A i (f )=A}), that is, for a.e. f ∈ L, A i (f )= lim m→∞ P m [A i (P, Q)=A]. Indeed, {f ∈ L : A i (f )=A} = T -i+1 ({f ∈ L : A 1 (f )=A}). By T -invariance of the Haar measure, one has µ L (T -i+1 ({f ∈ L : A 1 (f )=A})) = q 2deg(A)
. Now, we take the cost c i,A defined on Ω as follows:

c i,A (P, Q) = 1 if and only if A i (P, Q)=A. The corresponding cumulative generating function is 1 1 -G(z) • z deg(A) • U (z)=T Ω (z) • z deg(A) , which yields that E m [c i,A ]= 1 q 2m •|{(P, Q) ∈ Ω m : A i (P, Q)=A}| = 1 q 2 deg(A) .

Fa r e y m a p s

The aim of this section is to relate the function ν with a Farey type algorithm: this algorithm can be considered as a refinement of the continued fraction algorithm; it discovers step by step each non-zero monomial of partial quotients; its number of steps is thus closely related to the parameter ν. More precisely, we will consider two Farey algorithms (see Section 5.2 and 5.3) because of the particular role played by the constant term of polynomial terms. 5.1. General Farey maps. In the number case (see e.g. [START_REF] Feigenbaum | Presentation functions, fixed points, and a theory of scaling function dynamics[END_REF]), the Farey map is defined on the unit interval as

F R (x)=        x 1 -x 0 ≤ x ≤ 1 2 1 -x x 1 2 <x≤ 1. It satisfies F R [0, 1/2] = F R (1/2,
1] = [0, 1]: the map F R is complete on each of its two branches. If we denote, for x ∈ (0, 1), by t(x)t h efi r s tt i m ew h e r ex leaves the interval ( 12 , 1] to enter the interval [0, 1/2], namely

t(x)=min{n ≥ 1:F n-1 R (x) ∈ ( 1 2 , 1]},
we obtain

F t(x) R (x)= 1 x - 1
x which is the Gauss map (in the number case). Furthermore, the equality j(x)=[1/x] holds, and shows that the number of steps j(x) performed by F R is equal to the partial quotient [1/x]: the Farey map F R goes [1/x] -1 times through the first branch defined on [0, 1/2], and goes through the second branch only during the last step.

There are two possibilities for defining a Farey map on F q ((X -1 )) according to the way the constant term of the polynomial [1/f ] is handled (see Section 5.2 and 5.3 below for more details). Note that the set L on which the Gauss map T is naturally defined does not contain series with non-zero constant terms. We thus will work with the two following subsets of F q ((X -1 ))

J = {f ∈ F q ((X -1 )) : deg f ≤ 0}, L = {f ∈ F q ((X -1 )) : deg f<0}
with their respective normalized Haar measures µ J and µ L (both sets are compact abelian groups with respect to the addition law '+') which are related by

µ L (A)=q • µ J (A)
for any Borel subset A of L.T h e i rd i ff e r e n c es e tJ \ L is the subset J (0) defined as

J (0) = {f ∈ F q ((X -1 )) : deg f =0} which is of positive measure in J.
Remark 3. The situation is different in the real case, since the counterparts of J, namely the interval [0, 1], and of L, the interval [0, 1), differ from a subset of zero measure. Here, the Gauss map T could be defined on J,b u tT (J)=L. This is one of the reasons that makes us work with J and L. 5.2. Farey map on J. We first define a map F J , defined on J, which handles constant monomials as other monomials, and that thus counts them. As its real counterpart F R , it has two branches, defined on two subsets denoted as J 1 and J 2 : the choice of the branch depends on whether the number ν(f )=µ([1/f ]) of non-zero monomials which remain to be computed in the polynomial [1/f ] is yet larger than 1, or equal to 1.

We use here the notation of Section 4.1. The Farey map F J discovers the monomials of [1/f ] one by one. The first one is the monomial (1/γ(f ))X -deg f , and when we subtract this monomial to 1/f , we obtain the series ( 20)

G(f )= 1 f - X -deg f γ(f ) ,
with γ(f ) being the dominant coefficient of f , and there are two possibilities for deg G(f ). Indeed, if deg G(f ) ≥ 0, the quotient [1/f ] is not completely computed, and we continue the computation with 1/G(f ). In this case, the quotient [1/f ] contains at least two monomials, and thus ν(f ) ≥ 2.

Otherwise, if deg G(f ) < 0, the quotient [1/f ] is complete; this means that ν(f ) = 1, and we apply the map T for computing the following quotient. We thus let:

J 1 := {f ∈ J : ν(f ) ≥ 2} = {f ∈ J :d e g G(f ) ≥ 0} J 2 := {f ∈ J : ν(f )=1} = {f ∈ J :d e g G(f ) < 0} F (f )=          1 G(f ) if deg G(f ) ≥ 0 1 f - 1 f if deg G(f ) < 0. Proposition 4. Let f ∈ J. We set t(f )=min i ≥ 1:F i-1 J (f ) ∈ J 2
the first time when the trajectory of f under the map F leaves the set J 1 to enter the set J 2 . Then, t(f ) equals the number of non-zero monomials contained in the polynomial [1/f ].

5.3.

Farey map on L. The relation

F t(f ) J (f )=T (f )= 1 f - 1 f ,
together with the fact that T is Haar measure preserving (i.e., µ L -invariant), prove that F J has an absolutely continuous invariant measure with respect to µ J , which is ergodic. This measure will be denoted as µ J . Indeed, this follows from the fact that an invariant measure for a jump transformation gives an invariant measure for the original transformation, and the ergodicity of these two transformations are equivalent to each other (see [START_REF] Schweiger | Ergodic theory of fibred systems and metric number theory[END_REF]). However, this measure is not equal to µ J since µ J (J (0) )= q -1 q ,F -1 J (J (0) ) L, and µ J (L)= 1 q .

The map F J is thus not µ J -preserving. In order to give an explicit expression for the ergodic absolutely continuous invariant measure µ F J for F J (see Theorem 2 below), we now introduce the induced map of F J on L, denoted as F L , for which µ L will be proved to be invariant (see Proposition 5). This will lead us to consider the constant term of the partial quotient in a separate way. Let us recall that that we have initially defined the map F on the set J (and not on its subset L) because of the need to deal with the constant term (of zero degree) when producing in an additive way the monomials of [1/f ].

We now define another Farey map F L on the set L as follows

F L (f )=          1 G(f ) if deg G(f ) > 0 1 f - 1 f if deg G(f ) ≤ 0.
Then,

F L (f )=    F J (f )i f F J (f ) ∈ L F 2 J (f )i fF J (f ) ∈ J (0) . One checks that F L is the induced transformation of F J to L.I n d e e d ,i fF J (f ) ∈ J (0) ,w i t hf ∈ L, this implies that F J (f ) ∈ J 2 , and F 2 J (f )=T (f ) ∈ L.
As in the previous section, we then relate this map to the number ν(f ) of non-constant monomials in [1/f ]( t h ed i ff e r e n c eb e t w e e n ν(f ) and ν(f ) is that ν(f ) does not take into account the constant term of [1/f ]). One has deg G(f ) ≤ 0 if and only if there exists b in F q such that [1/f ]=X -deg f + b. This means ν(f ) = 1. We then set

L 1 := {f ∈ L :d e g G(f ) > 0} = {f ∈ L : ν(f ) ≥ 2}, L 2 := {f ∈ L :d e g G(f ) ≤ 0} = {f ∈ L : ν(f )=1}, F 1,L (f )=F L (f )= 1 G(f ) for f ∈ L 1 ,F 2,L (f )=F L (f )= 1 f - 1 f for f ∈ L 2 .
The map F L is now related to ν(f ). We have also:

L 2 = i≥1 a∈F * q b∈Fq {f ∈ L :[ 1 /f ]=aX i + b}.
Proposition 5. The map F L is µ L -preserving.

To prove this proposition, we need Lemma 2 and 3 below which deal respectively with the two possible types of preimage of a given cylinder set (see Definition 4). We use here the notation of Section 4.1.

Lemma 2. The measure of the inverse transform of any cylinder E

[-k,a,π] (with k ≥ 0) by the first branch F 1,L satisfies µ L (F -1 1,L (E [-k,a,π] )) = 1 q +1 • µ L (E [-k,a,π] ), for k ≥ 1, µ L (F -1 1,L (E [0,a,π] )) = q q +1 • µ J (E [0,a,π] ).
Proof. Observe first that, here, E [-k,a,π] is a cylinder of L or of J (0) , according to the value k.

Let f ∈ L m with γ(f )=b and 1/G(f ) ∈ E [-k,a,π] ,w i t hk ≥ 0 and π ∈ F q . Then, by [START_REF] Schweiger | Ergodic theory of fibred systems and metric number theory[END_REF],

G(f ) ∈ E [k,1/a,ρ] with ρ = ψ(π), the inequality m ≥ k + 1 holds and 1 f = X m γ(f ) + G(f )= X m b + 1 a X k 1+ 1 X ρ 1 X + X -(k++1) g, deg g ≤ 0 = X m b 1+ b a 1 X 1 X m-k-1 1+ 1 X ρ 1 X + X -(k++1) g.
If we define the sequence θ via its polynomial θ defined as

θ(X)= b a X m-k-1 1+Xρ(X) ,
5.4. Metric theory of the Farey map F J . So far, we have obtained the invariant measure for the induced map F L . We now want to give an explicit expression for the invariant measure of F J .

Remark 5. One has F -1

J A = F -1 L A for any Borel subset A of J (0) . Lemma 2 implies µ L (F -1 J A)=q • µ J (A) • 1 q +1
for any Borel subset A of J (0) . In particular, we see that

µ L (F -1 J J (0) )= q q +1 • µ J (J (0) )= q q +1 q -1 q = q -1 q +1 .
Theorem 8. Let µ J be the measure defined on J by µ

J (A)= q +1 2q µ L (A ∩ L)+ q q +1 µ J (A ∩ J (0) )
for any Borel subset A of J.T h em e a s u r e µ J is an invariant probability measure for F J . Furthermore, it is finite and the map F J is ergodic w.r.t. µ F J . In particular, µ J (J 2 )=1/2.

Proof. Obviously q+1 2q is the normalizing constant. Indeed one checks that µ

J (J)=µ L (L)+ q q +1 µ J (J (0) )=1+ q q +1 q -1 q = 2q q +1 . It is thus enough to show that µ L (F -1 J A ∩ L)+ q q +1 µ J (F -1 J A ∩ J (0) )=µ L (A ∩ L)+ q q +1 µ J (A ∩ J (0) ) for any Borel subset A of J. Assume first A ⊂ J (0) . One has F -1 J A = F -1 1,J A ⊂ L. Furthermore, F -1 J A = F -1 L A (since A ⊂ J (0) ). According to Remark 5, one gets µ L (F -1 J A)=q • µ J (A) • 1 q+1 . Hence µ L (F -1 J A∩L)+ q q +1 µ J (F -1 J A∩J (0) )=µ L (F -1 J A)= q q +1 µ J (A)=µ L (A∩L)+ q q +1
µ J (A∩J (0) ).

Suppose now that A ⊂ L. In this case, we have, according to Remark 5

µ L (F -1 J A ∩ L)+ q q +1 µ J (F -1 J A ∩ J (0) ) = µ L (F -1 J A ∩ L)+µ L (F -1 J (F -1 J A ∩ J (0) )) = µ L (F -1 J A ∩ L)+µ L (F -2 J A ∩ F -1 J J (0) ) Since (F -1 J A ∩ L) ∩ F -1 J J (0) = ∅,w eh a v e µ L (F -1 J A ∩ L)+µ L (F -2 J A ∩ F -1 J J (0) )=µ L (F -1 L A)=µ L (
A) which shows the desired assertion concerning the invariance of µ J .

Let us prove now that µ J (J 2 )=1/2. We have

J 2 = J (0) ∪ (J 2 \ J (0) )w i t h J 2 \ J (0) = ∞ m=1
{f ∈ L m :d e gG(f ) < 0} , and µ J (J (0) )=(q -1)/(2q). We now compute the the measure of each set {f ∈ L m :d e gG(f ) < 0}.I ff ∈ L m ,w i t hγ(f )=a and deg G(f

) < 0, its inverse 1/f satisfies 1 f = X m a + G(f )w i t h d e g G(f ) < 0
Then 1/f belongs to the cylinder E [m,1/a,0 m ] whose measure equals q -2m . Hence

µ J (J 2 \ J (0) )= q +1 2q ∞ m=1 q -1 q 2m = 1 2q .
Remark 6 (Non-zero coefficients of partial quotients). Observe that we can use the previous results, and in particular the finiteness of the invariant measure µ J , for recovering the estimate of Theorem 5 concerning the behavior of the total number of non-zero coefficients of partial quotients in the continued fraction expansion of f , that is, for µ L -a.e. f , one has

lim n→∞ 1 n N n (f )=2.
Indeed, consider the trajectory Q(f ) of f under the action of F J , that is,

Q(f )=(f, F J (f ),F 2 J (f ),...,F n J (f ),...), and let Q m (f )=(f, F J (f ),F 2 J (f ),...,F m J (f )
). We let denote by t 1 (f ) the first time where the trajectory Q(f ) of f under the action of F J goes out of J 2 , that is,

t 1 (f )=min{m ≥ 1:F m-1 J (f ) ∈ J 2 },
and by t k (f )t h ek-th time where the trajectory Q(f ) of f goes out of J 2 . One has

N n (f )= n i=1 t i (f ).
Consider a fixed integer n, an integer m which belongs to the interval [t n (f ),t n+1 (f ) -1]. Then, the trajectory Q m (f ) goes n times through J 2 at times N 1 (f ),N 2 (f ),...N n (f ), so that

n = m i=1 1 J2 (F J i f ).
Because F J is ergodic w.r.t. 1 J2 (F i J f )=µ F J (J 2 )=1/2 for µ J -a.e. f , which also means for µ L -a.e. f . Finally, the inequality N n (f ) ≤ m<N n+1 (f ) entails the equality lim m→∞ (1/n)N n (f )=2.

Appendix: Mediant convergents of formal power series

The aim of this section is to show that the map F J produces the mediant convergents in the continued fraction expansion. For connections between the Farey map and mediant convergents in the classical case, see e.g. [START_REF] Ito | Algorithms with mediant convergents and their metrical theory[END_REF]. Let us first recall what is meant by mediant convergents in the classical case. Let x be an irrational number, 0 <x<1, with simple continued fraction of the form One has

x = 1 a 1 + 1 a 2 + ••• ,
p n q n = 1 a 1 + •••+ 1 a n
and p n+1 = a n+1 p n + p n-1 q n+1 = a n+1 q n + q n-1

for n ≥ 1. The mediant convergents (also called intermediate convergents) are defined by u n,j = jp n + p n-1 v n,j = jq n + q n-1

for 1 ≤ j<a n+1 . A simple calculation shows x -u n,j v n,j < a n+1 +1-j q n+1 (j • q n + q n-1 ) , 1 ≤ j<a n+1 .

If we put j = a n+1 , the above formula gives x -p n+1 q n+1 < 1 q 2 n+1 .

Mediant convergents thus interpolate pn qn and pn+1 qn+1 .

We now define an analog of the notion of 'mediant convergent' for formal power series. Let f ∈ L with continued fraction expansion

f = 1 A 1 + 1 A 2 + ••• ,A i ∈ F q [X] \ F q ,i ≥ 1.
Its principal convergents satisfy:

  P n-1 P n Q n-1 Q n   =   01 1 A 1   •••   01 1 A n   ,n ≥ 1,
and

P n+1 = A n+1 P n + P n-1 Q n+1 = A n+1 Q n + Q n-1 .
We write A n+1 = b t(n+1,1) X t(n+1,1) + b t(n+1,2) X t(n+1,2) + •••+ b t(n+1,un+1) X t(n+1,un+1) , t(n +1, 1) > ••• >t(n +1,u n+1 ) ≥ 0,b t(n+1,i) =0, 1 ≤ i ≤ u n+1 . In the process of calculation of A n+1 ,thecoefficien tsb t(n+1,1) ,...,b t(n+1,un+1) are determined step by step in decreasing order of powers. According to this point of view, we define the mediant convergents by [START_REF] Vallée | Euclidean Dynamics[END_REF] U n,j =(b t(n+1,1) X t(n+1,1) + •••+ b t(n+1,j) X t(n+1,j) )P n + P n-1 V n,j =(b t(n+1,1) X t(n+1,1) Proposition 6. For al l n and for all j with 1 ≤ j<u n+1 ,o n eh a s f -U n,j V n,j = q t(n+1,j+1) |Q n+1 | 2 .

+ •••+ b t(n+1,j) X t(n+1,j) )Q n + Q n-
Proof. We put S n+1,j = j i=1 b t(n+1,i) X t(n+1,i) , and

f n+1 = 1 A n+2 + 1 A n+3 + ••• .
One has deg f n+1 < 0. It is easy to see that

f = P n f n+1 + P n+1 Q n f n+1 + Q n+1 .
Hence we have f -Un,j Vn,j = Pnfn+1+Pn+1 Qnfn+1+Qn+1 -Un,j Vn,j = (PnVn,j -QnUn,j )fn+1+(Pn+1Vn,j -Qn+1Un,j ) (Qnfn+1+Qn+1)Vn,j .

Since deg Q n+1 =degV n,j , one has

|(Q n f n+1 + Q n+1 )V n,j | = |Q n+1 | 2 .
Moreover, the norm of the numerator of the right hand side term is equal to

|P n+1 V n,j -Q n+1 U n,j | = |(A n+1 P n + P n-1 )(S n+1,j Q n + Q n-1 ) -(A n+1 Q n + Q n-1
)(S n+1,j P n + P n-1 )| = |A n+1 (P n Q n-1 -Q n P n-1 )+S n+1,j (Q n P n-1 -P n Q n-1 )| = q t(n+1,j+1)

since P n Q n-1 -P n-1 Q n = -(P n+1 Q n -P n Q n+1 ).
This completes the proof of the proposition. We also introduce the following associated matrices for f ∈ J

M J (f )=                  10
X -deg f γ(f ) 1   if f ∈ J 1   01 1 1 f   if f ∈ J 2 .
The following proposition (which is a direct consequence of Proposition 4) states that the map F J indeed produces the mediant convergents:

  E m [C] and its variance V m [C] on the subset Ω m , or else, determine its asymptotic distribution on Ω m when m →∞ . Then, we aim at relating the behavior of cost C on Ω to the behavior of the basic cost c on G. Let us note that, by abuse of notation, we use the same notation E m [ . ] and V m [ . ], both for costs c and C defined respectively on G m and Ω m .I t i s natural for instance to compare the expectation E m [C] and its variance V m [C] on the subset Ω m with their counterparts on the subset G m of G made of the polynomials with degree m, namely the expectation E m [c] and the variance V m [c] of the cost c on the subset G m . We introduce the bivariate generating functions S c (z, u),T C (z, u) respectively relative to the cost c on the set G, and to the cost C on the set Ω. Their general terms are [z m u k ]S c (z, u)=|{P ∈G :d e gP = m and c(P )=k}| , [z m u k ]T C (z, u)=|{(P, Q) ∈ Ω:d e gQ = m and C(P, Q)=k}| .

2. 3 .

 3 Cumulative generating functions. We now deal with the cumulative generating functions. The first one, denoted by S (c) (z), is relative to the cost c on the set G, and the second one, denoted by T (C) (z), is relative to the cost C on the set Ω. Their general terms are respectively equal to P ∈G, deg P =m c(P ), (P,Q)∈Ω, deg Q=m C(P, Q).

3 . 1 .Theorem 3 .

 313 Study of the fine-bit complexity in the discrete model 3.Expectation and variance of the fine bit-complexity. Now we consider the average and the variance of the fine bit-complexity. On the set Ω m , the expectation and the variance of the fine complexity φ satisfy

µ J and according to Theorem 5

 5

where a i , i ≥ 1 ,

 1 are positive integers. The principal convergents pn qn , n ≥ 1, are defined by 

1 for 1 ≤ 10 b 1 

 11101 j<u n+1 . Note that deg U n,j =degP n+1 deg V n,j =degQ n+1 for 1 ≤ j<u n+1 . This definition corresponds to the following matricial decomposition: t(n+1,1) X t(n+1,1) t(n+1,un+1) X t(n+1,un+1)   , which can be compared to the analogous decomposition in the real case:

Remark 7 .

 7 Since t(n +1, 1) >t(n +1, 2) > ••• >t(n +1,u n+1 ) ≥ 0 and deg V n,j =degQ n+1 ,we may say that (Un,jVn,j :1≤ j<u n+1 ) interpolate the principal convergents ( Pn Qn : n ≥ 1).

the sequence θ depends on ρ (and then on π) together with (m, b) and it belongs to F m-k+ q . Furthermore, 1/f belongs to the cylinder E [m,b,θ] and f belongs to the cylinder E [-m,1/b,ψ -1 (θ)] . Finally, we have proven that

is a disjoint union of cylinders where the polynomials ψ -1 (θ) are of degree mk -1+.S i n c e there are q -1 possible choices for b ∈ F q , we deduce that

which yields the assertion of the lemma.

Remark 4. For any pair (a, π), the equalityF -1

Proof. Recall that, in this case, there

If we define the sequence θ via its polynomiall θ as

the sequence θ depends on (c, π) together with (i, a, b) and belongs to F k+i+ q . Moreover, when (c, π, i)i sfi x e d ,t h es e q u e n c e sθ associated with different values of the pair (a, b) are distinct. Furthermore, 1/f belongs to the cylinder E [i,a,θ] and f belongs to the cylinder E [-i,1/a,ψ(θ)] .W e thus have

This is a disjoint union. Since there are q -1 possible choices for a and q possibilities for b,w e deduce that

which yields the assertion of the lemma.

Proof. Let us prove Proposition 5. It is enough to show that

) for any cylinder set E [k,a,π] of L. According to Lemma 2 and Lemma 3, we get

which shows the assertion of Proposition 5.

Proposition 7. Let

for f ∈ L. Furthermore, for all n, u n = ν(A n ).