×

A local limit theorem with speed of convergence for Euclidean algorithms and Diophantine costs. (English) Zbl 1231.37015

Summary: For large \(N\), we consider the ordinary continued fraction of \(x=p/q\) with \(1\leq p\leq q\leq N\), or, equivalently, Euclid’s gcd algorithm for two integers \(1\leq p\leq q\leq N\), putting the uniform distribution on the set of \(p\) and \(q\)’s. 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.

MSC:

37C30 Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc.
11Y16 Number-theoretic algorithms; complexity
60F05 Central limit and other weak theorems
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML

References:

[1] V. Baladi and B. Vallée. Euclidean algorithms are Gaussian. J. Number Theory 110 (2005) 331-386. · Zbl 1114.11092
[2] E. Breuillard. Distributions diophantiennes et théorème limite local sur R d . Probab. Theory Related Fields 132 (2005) 39-73. · 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. · Zbl 1083.60008
[4] H. Carlsson. Remainder term estimates of the renewal function. Ann. Probab. 11 (1983) 143-157. · Zbl 0507.60081
[5] J. W. S. Cassels. An Introduction to Diophantine Approximation . Cambridge Univ. Press, New York, 1957. · 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. · Zbl 0918.58058
[8] D. Dolgopyat. On decay of correlations in Anosov flows. Ann. Math. 147 (1998) 357-390. JSTOR: · Zbl 0911.58029
[9] W. Ellison and F. Ellison. Prime Numbers . Wiley, New York, 1985. · Zbl 0624.10001
[10] W. Feller. An Introduction to Probability Theory and its Applications . Vol. II. Wiley, New York, 1971. · 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. · 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. · Zbl 0784.60076
[13] A. Hachemi. Un théorème de la limite locale pour des algorithmes Euclidiens. Acta Arithm. 117 (2005) 265-276. · Zbl 1067.37024
[14] D. Hensley. The number of steps in the Euclidean algorithm. J. Number Theory 49 (1994) 142-182. · Zbl 0811.11055
[15] I. Melbourne. Rapid decay of correlations for nonuniformly hyperbolic flows. Trans. Amer. Math. Soc. 359 (2007) 2421-2441. · Zbl 1184.37024
[16] F. Naud. Analytic continuation of a dynamical zeta function under a Diophantine condition. Nonlinearity 14 (2001) 995-1009. · Zbl 1067.37026
[17] M. Pollicott. On the rate of mixing of Axiom A flows. Invent. Math. 81 (1985) 413-426. · Zbl 0591.58025
[18] D. Ruelle. Flots qui ne mélangent pas exponentiellement. C. R. Acad. Sci. 296 (1983) 191-193. · Zbl 0531.58040
[19] R. Sharp. A local limit theorem for closed geodesics and homology. Trans. Amer. Math. Soc. 356 (2004) 4897-4908. JSTOR: · Zbl 1330.37026
[20] B. Vallée. Euclidean dynamics. Discrete Contin. Dyn. Syst. 15 (2006) 281-352. · 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. · Zbl 0973.11079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.