A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs
Annales de l'I.H.P. Probabilités et statistiques, Volume 44 (2008) no. 4, pp. 749-770.

For large N, we consider the ordinary continued fraction of x=p/q with 1pqN, or, equivalently, Euclid’s gcd algorithm for two integers 1pqN, putting the uniform distribution on the set of p and qs. We study the distribution of the total cost of execution of the algorithm for an additive cost function c on the set + * of possible digits, asymptotically for N. If c is nonlattice and satisfies mild growth conditions, the local limit theorem was proved previously by the second named author. Introducing diophantine conditions on the cost, we are able to control the speed of convergence in the local limit theorem. We use previous estimates of the first author and Vallée, and we adapt to our setting bounds of Dolgopyat and Melbourne on transfer operators. Our diophantine condition is generic (with respect to Lebesgue measure). For smooth enough observables (depending on the diophantine condition) we attain the optimal speed.

Nous considérons la fraction continue ordinaire de x=p/q pour 1pqN, ou, de manière équivalente, l’algorithme de pgcd d’Euclide pour deux entiers 1pqN, avec N grand et p et q distribués uniformément. Nous étudions la distribution du coût total de l’exécution de l’algorithme pour un coût additif c sur l’ensemble + * des «digits» possibles, lorsque N tend vers l’infini. Le théorème de la limite locale a été démontré par le deuxième auteur si c est non réseau et satisfait une condition de croissance modérée. En imposant une condition diophantienne sur le coût, nous parvenons à contrôler la vitesse de convergence dans ce théorème de la limite locale. Pour cela nous utilisons des estimées obtenues par le premier auteur et Vallée, et nous adaptons à notre problème des bornes de Dolgopyat et Melbourne sur les opérateurs de transfert. Notre condition diophantienne est générique (par rapport à la mesure de Lebesgue). Pour des observables assez régulières (par rapport à la condition diophantienne), nous obtenons la vitesse optimale.

DOI: 10.1214/07-AIHP140
Classification: 11Y16,  60F05,  37C30
Keywords: euclidean algorithms, local limit theorem, diophantine condition, speed of convergence, transfer operator, continued fraction
@article{AIHPB_2008__44_4_749_0,
     author = {Baladi, Viviane and Hachemi, A{\"\i}cha},
     title = {A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     pages = {749--770},
     publisher = {Gauthier-Villars},
     volume = {44},
     number = {4},
     year = {2008},
     doi = {10.1214/07-AIHP140},
     zbl = {1231.37015},
     mrnumber = {2446296},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1214/07-AIHP140/}
}
TY  - JOUR
AU  - Baladi, Viviane
AU  - Hachemi, Aïcha
TI  - A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2008
DA  - 2008///
SP  - 749
EP  - 770
VL  - 44
IS  - 4
PB  - Gauthier-Villars
UR  - http://archive.numdam.org/articles/10.1214/07-AIHP140/
UR  - https://zbmath.org/?q=an%3A1231.37015
UR  - https://www.ams.org/mathscinet-getitem?mr=2446296
UR  - https://doi.org/10.1214/07-AIHP140
DO  - 10.1214/07-AIHP140
LA  - en
ID  - AIHPB_2008__44_4_749_0
ER  - 
%0 Journal Article
%A Baladi, Viviane
%A Hachemi, Aïcha
%T A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2008
%P 749-770
%V 44
%N 4
%I Gauthier-Villars
%U https://doi.org/10.1214/07-AIHP140
%R 10.1214/07-AIHP140
%G en
%F AIHPB_2008__44_4_749_0
Baladi, Viviane; Hachemi, Aïcha. A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs. Annales de l'I.H.P. Probabilités et statistiques, Volume 44 (2008) no. 4, pp. 749-770. doi : 10.1214/07-AIHP140. http://archive.numdam.org/articles/10.1214/07-AIHP140/

[1] V. Baladi and B. Vallée. Euclidean algorithms are Gaussian. J. Number Theory 110 (2005) 331-386. | MR | Zbl

[2] E. Breuillard. Distributions diophantiennes et théorème limite local sur Rd. Probab. Theory Related Fields 132 (2005) 39-73. | MR | Zbl

[3] E. Breuillard. Local limit theorems and equidistribution of random walks on the Heisenberg group. Geom. Funct. Anal. 15 (2005) 35-82. | MR | Zbl

[4] H. Carlsson. Remainder term estimates of the renewal function. Ann. Probab. 11 (1983) 143-157. | MR | Zbl

[5] J. W. S. Cassels. An Introduction to Diophantine Approximation. Cambridge Univ. Press, New York, 1957. | MR | Zbl

[6] E. Cesaratto. Erratum to “Euclidean algorithms are Gaussian” by Baladi-Vallée. Submitted for publication, 2007.

[7] D. Dolgopyat. Prevalence of rapid mixing in hyperbolic flows. Ergodic Theory Dynam. Systems 18 (1998) 1097-1114. | MR | Zbl

[8] D. Dolgopyat. On decay of correlations in Anosov flows. Ann. Math. 147 (1998) 357-390. | MR | Zbl

[9] W. Ellison and F. Ellison. Prime Numbers. Wiley, New York, 1985. | MR | Zbl

[10] W. Feller. An Introduction to Probability Theory and its Applications. Vol. II. Wiley, New York, 1971. | MR | Zbl

[11] S. Gouëzel. Berry-Esseen theorem and local limit theorem for non uniformly expanding maps. Ann. Inst. H. Poincaré Probab. Statist. 41 (2005) 997-1024. | Numdam | MR | Zbl

[12] Y. Guivarc'H and Y. Le Jan. Asymptotic winding of the geodesic flow on modular surfaces and continuous fractions. Ann. Sci. École Norm. Sup. (4) 26 (1993) 23-50. | Numdam | MR | Zbl

[13] A. Hachemi. Un théorème de la limite locale pour des algorithmes Euclidiens. Acta Arithm. 117 (2005) 265-276. | MR | Zbl

[14] D. Hensley. The number of steps in the Euclidean algorithm. J. Number Theory 49 (1994) 142-182. | MR | Zbl

[15] I. Melbourne. Rapid decay of correlations for nonuniformly hyperbolic flows. Trans. Amer. Math. Soc. 359 (2007) 2421-2441. | MR

[16] F. Naud. Analytic continuation of a dynamical zeta function under a Diophantine condition. Nonlinearity 14 (2001) 995-1009. | MR | Zbl

[17] M. Pollicott. On the rate of mixing of Axiom A flows. Invent. Math. 81 (1985) 413-426. | MR | Zbl

[18] D. Ruelle. Flots qui ne mélangent pas exponentiellement. C. R. Acad. Sci. 296 (1983) 191-193. | MR | Zbl

[19] R. Sharp. A local limit theorem for closed geodesics and homology. Trans. Amer. Math. Soc. 356 (2004) 4897-4908. | MR

[20] B. Vallée. Euclidean dynamics. Discrete Contin. Dyn. Syst. 15 (2006) 281-352. | MR | Zbl

[21] B. Vallée. Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems. Colloque International de Théorie des Nombres (Talence, 1999). J. Théor. Nombres Bordeaux 12 (2000) 531-570. | Numdam | MR | Zbl

Cited by Sources: