×

Euclidean algorithms are Gaussian. (English) Zbl 1114.11092

Summary: We obtain a central limit theorem for a general class of additive parameters (costs, observables) associated to three standard Euclidean algorithms, with optimal speed of convergence. We also provide very precise asymptotic estimates and error terms for the mean and variance of such parameters. For costs that are lattice (including the number of steps), we go further and establish a local limit theorem, with optimal speed of convergence. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various other techniques: Dirichlet series, Perron’s formula, quasi-powers theorems, and the saddle-point method. Such dynamical analyses had previously been used to perform the average-case analysis of algorithms. For the present (dynamical) analysis in distribution, we require estimates on transfer operators when a parameter varies along vertical lines in the complex plane. To prove them, we adapt techniques introduced recently by D. Dolgopyat in the context of continuous-time dynamics [Ann. Math. (2) 147, No. 2, 357–390 (1998; Zbl 0911.58029)].

MSC:

11Y16 Number-theoretic algorithms; complexity
37A45 Relations of ergodic theory with number theory and harmonic analysis (MSC2010)
37C30 Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc.
60F05 Central limit and other weak theorems
68W40 Analysis of algorithms

Citations:

Zbl 0911.58029
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aaronson, J.; Denker, M., Local limit theorems for partial sums of stationary sequences generated by Gibbs-Markov maps, Stochastic Dynam., 1, 193-237 (2001) · Zbl 1039.37002
[3] Babenko, K. I., On a problem of Gauss, Soviet Math. Doklady, 19, 1, 136-140 (1978) · Zbl 0389.10036
[4] Baladi, V., Positive transfer operators and decay of correlations, Advanced Series in Nonlinear Dynamics (2000), World Scientific: World Scientific Singapore
[7] Bourdon, J.; Daireaux, B.; Vallée, B., Dynamical analysis of \(\alpha \)-Euclidean algorithms, J. Algorithms, 44, 246-285 (2002) · Zbl 1030.11074
[8] Brent, R. P., Analysis of the Binary Euclidean algorithm, (Traub, J. F., Algorithms and Complexity, New Directions and Recent Results (1976), Academic Press: Academic Press New York) · Zbl 0311.90065
[12] Chernov, N., Markov approximations and decay of correlations for Anosov flows, Ann. Math., 147, 2, 269-324 (1998) · Zbl 0911.58028
[13] Collet, P., Some ergodic properties of maps of the interval, Dynamical systems, (Proceedings of the first UNESCO CIMPA School on Dynamical and Disordered Systems. Proceedings of the first UNESCO CIMPA School on Dynamical and Disordered Systems, Temuco, Chile, 1991 (1996), Hermann: Hermann Paris)
[14] Delange, H., Généralisation du Théorème d’Ikehara, Ann. Sci. ENS, 71, 213-242 (1954) · Zbl 0056.33101
[15] Dixon, J. D., The number of steps in the Euclidean algorithm, J. Number Theory, 2, 414-422 (1970) · Zbl 0206.33502
[16] Dolgopyat, D., On decay of correlations in Anosov flows, Ann. Math., 147, 357-390 (1998) · Zbl 0911.58029
[17] Ellison, W.; Ellison, F., Prime Numbers (1985), Hermann: Hermann Paris · Zbl 0624.10001
[18] Finch, S. R., Mathematical Constants (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1054.00001
[22] Heilbronn, H., On the average length of a class of continued fractions, (Turan, P., Number Theory and Analysis (1969), Plenum: Plenum New York), 87-96 · Zbl 0212.06503
[23] Henrici, P., (Applied and Computational Complex Analysis, vol. 2 (1974), Wiley: Wiley New York)
[24] Hensley, D., The number of steps in the Euclidean algorithm, J. Number Theory, 49, 2, 142-182 (1994) · Zbl 0811.11055
[26] Hwang, H.-K., Large deviations for combinatorial distributionsI, Central limit theorems, Ann. Appl. Probab., 6, 297-319 (1996) · Zbl 0863.60013
[27] Hwang, H.-K., On convergence rates in the central limit theorems for combinatorial structures, European J. Combin., 19, 329-343 (1998) · Zbl 0906.60024
[28] Kato, T., Perturbation Theory for Linear Operators (1980), Springer: Springer Berlin
[29] Khinchin, A. I., Continued Fractions (1964), University of Chicago Press: University of Chicago Press Chicago · Zbl 0117.28601
[33] Lévy, P., Sur les lois de probabilité dont dépendent les quotients complets et incomplets d’une fraction continue, Bull. Soc. Math. France, 57, 178-194 (1929) · JFM 55.0916.02
[34] Mayer, D. H., Continued fractions and related transformations, (Bedford, T.; Keane, M.; Series, C., Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces (1991), Oxford University Press: Oxford University Press Oxford), 175-222 · Zbl 0755.58034
[35] Nagaev, S. V., Some limit theorems for stationary Markov chains, Theor. Probab. Appl., 2, 378-406 (1957)
[36] Parry, W., Bowen’s equidistribution theory and the Dirichlet density theorem, Ergodic Theory Dynam. Systems, 4, 117-134 (1984) · Zbl 0567.58014
[37] Parry, W.; Pollicott, M., Zeta Functions and the Periodic Orbit Structure of Hyperbolic Dynamics (1990), Astérisque · Zbl 0726.58003
[38] Pollicott, M.; Sharp, R., Exponential error terms for growth functions on negatively curved surfaces, Amer. J. Math., 120, 1019-1042 (1998) · Zbl 0999.37010
[40] Rieger, G. J., Über die Schrittanzahl beim Algorithmus von Harris und dem nach nachsten Ganzen, Arch. Math., 34, 421-427 (1980) · Zbl 0448.10004
[41] Ruelle, D., Thermodynamic Formalism (1978), Addison Wesley: Addison Wesley Reading, MA
[42] Schweiger, F., Ergodic Theory of Fibred Systems and Metric Number Theory (1995), Oxford Science Publications, Clarendon Press: Oxford Science Publications, Clarendon Press Oxford · Zbl 0819.11027
[43] Stein, E., Harmonic AnalysisReal Variable Methods, Orthogonality and Oscillatory integrals (1993), Princeton University Press: Princeton University Press Princeton
[44] Tenenbaum, G., Introduction to Analytic and Probabilistic Number Theory (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0788.11001
[45] Vallée, B., Dynamical sources in information theoryfundamental intervals and word prefixes, Algorithmica, 29, 262-306 (2001) · Zbl 1009.94003
[46] Vallée, B., Dynamics of the binary Euclidean algorithmfunctional analysis and operators, Algorithmica, 22, 4, 660-685 (1998) · Zbl 0914.68106
[47] Vallée, B., Dynamique des fractions continues à contraintes périodiques, J. Number Theory, 2, 183-235 (1998) · Zbl 0918.11047
[48] Vallée, B., Dynamical analysis of a class of Euclidean algorithms, Theor. Comput. Sci., 297, 1-3, 447-486 (2003) · Zbl 1044.68164
[49] Vallée, B., Digits and continuants in Euclidean algorithms, Ergodic versus Tauberian theorems, J. Thèo. Nombres Bordeaux, 12, 531-570 (2000) · Zbl 0973.11079
[50] Vardi, I., A relation between Dedekind sums and Kloosterman sums, Duke Math. J., 55, 189-197 (1987) · Zbl 0623.10025
[51] Wirsing, E., On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces, Acta Arith., 24, 507-528 (1974) · Zbl 0283.10032
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.