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

Viviane Baladi; Aïcha Hachemi

Annales de l'I.H.P. Probabilités et statistiques (2008)

  • Volume: 44, Issue: 4, page 749-770
  • ISSN: 0246-0203

Abstract

top
For large N, we consider the ordinary continued fraction of x=p/q with 1≤p≤q≤N, or, equivalently, Euclid’s gcd algorithm for two integers 1≤p≤q≤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 ℤ+* 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.

How to cite

top

Baladi, Viviane, and 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 44.4 (2008): 749-770. <http://eudml.org/doc/77990>.

@article{Baladi2008,
abstract = {For large N, we consider the ordinary continued fraction of x=p/q with 1≤p≤q≤N, or, equivalently, Euclid’s gcd algorithm for two integers 1≤p≤q≤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 ℤ+* 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.},
author = {Baladi, Viviane, Hachemi, Aïcha},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {euclidean algorithms; local limit theorem; diophantine condition; speed of convergence; transfer operator; continued fraction; Euclidean algorithms; Diophantine condition},
language = {eng},
number = {4},
pages = {749-770},
publisher = {Gauthier-Villars},
title = {A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs},
url = {http://eudml.org/doc/77990},
volume = {44},
year = {2008},
}

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
PB - Gauthier-Villars
VL - 44
IS - 4
SP - 749
EP - 770
AB - For large N, we consider the ordinary continued fraction of x=p/q with 1≤p≤q≤N, or, equivalently, Euclid’s gcd algorithm for two integers 1≤p≤q≤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 ℤ+* 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.
LA - eng
KW - euclidean algorithms; local limit theorem; diophantine condition; speed of convergence; transfer operator; continued fraction; Euclidean algorithms; Diophantine condition
UR - http://eudml.org/doc/77990
ER -

References

top
  1. [1] V. Baladi and B. Vallée. Euclidean algorithms are Gaussian. J. Number Theory 110 (2005) 331–386. Zbl1114.11092MR2122613
  2. [2] E. Breuillard. Distributions diophantiennes et théorème limite local sur Rd. Probab. Theory Related Fields 132 (2005) 39–73. Zbl1079.60050MR2136866
  3. [3] E. Breuillard. Local limit theorems and equidistribution of random walks on the Heisenberg group. Geom. Funct. Anal. 15 (2005) 35–82. Zbl1083.60008MR2140628
  4. [4] H. Carlsson. Remainder term estimates of the renewal function. Ann. Probab. 11 (1983) 143–157. Zbl0507.60081MR682805
  5. [5] J. W. S. Cassels. An Introduction to Diophantine Approximation. Cambridge Univ. Press, New York, 1957. Zbl0077.04801MR87708
  6. [6] E. Cesaratto. Erratum to “Euclidean algorithms are Gaussian” by Baladi-Vallée. Submitted for publication, 2007. Zbl1250.11105
  7. [7] D. Dolgopyat. Prevalence of rapid mixing in hyperbolic flows. Ergodic Theory Dynam. Systems 18 (1998) 1097–1114. Zbl0918.58058MR1653299
  8. [8] D. Dolgopyat. On decay of correlations in Anosov flows. Ann. Math. 147 (1998) 357–390. Zbl0911.58029MR1626749
  9. [9] W. Ellison and F. Ellison. Prime Numbers. Wiley, New York, 1985. Zbl0624.10001MR814687
  10. [10] W. Feller. An Introduction to Probability Theory and its Applications. Vol. II. Wiley, New York, 1971. Zbl0219.60003MR270403
  11. [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. Zbl1134.60323MR2172207
  12. [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. Zbl0784.60076MR1209912
  13. [13] A. Hachemi. Un théorème de la limite locale pour des algorithmes Euclidiens. Acta Arithm. 117 (2005) 265–276. Zbl1067.37024MR2139006
  14. [14] D. Hensley. The number of steps in the Euclidean algorithm. J. Number Theory 49 (1994) 142–182. Zbl0811.11055MR1305088
  15. [15] I. Melbourne. Rapid decay of correlations for nonuniformly hyperbolic flows. Trans. Amer. Math. Soc. 359 (2007) 2421–2441. Zbl1184.37024MR2276628
  16. [16] F. Naud. Analytic continuation of a dynamical zeta function under a Diophantine condition. Nonlinearity 14 (2001) 995–1009. Zbl1067.37026MR1862808
  17. [17] M. Pollicott. On the rate of mixing of Axiom A flows. Invent. Math. 81 (1985) 413–426. Zbl0591.58025MR807065
  18. [18] D. Ruelle. Flots qui ne mélangent pas exponentiellement. C. R. Acad. Sci. 296 (1983) 191–193. Zbl0531.58040MR692974
  19. [19] R. Sharp. A local limit theorem for closed geodesics and homology. Trans. Amer. Math. Soc. 356 (2004) 4897–4908. Zbl1330.37026MR2084404
  20. [20] B. Vallée. Euclidean dynamics. Discrete Contin. Dyn. Syst. 15 (2006) 281–352. Zbl1110.68052MR2191398
  21. [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. Zbl0973.11079MR1823202

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.