A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs

Baladi, Viviane ; Hachemi, Aïcha

Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008), p. 749-770 / Harvested from Numdam

Résumé

Nous considérons la fraction continue ordinaire de $x=p/q$ pour $1\le p\le q\le N$, ou, de manière équivalente, l’algorithme de pgcd d’Euclide pour deux entiers $1\le p\le q\le N$, 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 $\mathbb {Z}_+^*$ 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.

Abstract

For large $N$, we consider the ordinary continued fraction of $x=p/q$ with $1\le p\le q\le N$, or, equivalently, Euclid’s gcd algorithm for two integers $1\le p\le q\le N$, 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 $\mathbb {Z}_+^*$ of possible digits, asymptotically for $N\rightarrow \infty $. 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.

Détail

Publié le : 2008-01-01

MR 2446296 | Zbl 1231.37015

DOI : https://doi.org/10.1214/07-AIHP140
Classification:  11Y16,  60F05,  37C30

Bibliographie

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

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

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

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

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

[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 1653299 | Zbl 0918.58058

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

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

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

[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 2172207 | Zbl 1134.60323

[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 1209912 | Zbl 0784.60076

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

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

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

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

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

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

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

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

[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 1823202 | Zbl 0973.11079