×

Continued fraction algorithms, functional operators, and structure constants. (English) Zbl 0981.11044

Summary: Continued fractions lie at the heart of a number of classical algorithms like Euclid’s greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a 2-dimensional generalization. This paper surveys the main properties of functional operators – transfer operators – due to Ruelle and Mayer (also following Lévy, Kuzmin, Wirsing, Hensley, and others) that describe precisely the dynamics of the continued fraction transformation. Spectral characteristics of transfer operators are shown to have many consequences, like the normal law for logarithms of continuants associated to the basic continued fraction algorithm and a purely analytic estimation of the average number of steps of the Euclidean algorithm. Transfer operators also lead to a complete analysis of the “Hakmem” algorithm for comparing two rational numbers via partial continued fraction expansions and of the “digital tree” algorithm for completely sorting \(n\) real numbers by means of their continued fraction representations. As a consequence, a small number of “structure constants” appear to govern the behaviour of a variety of continued fraction based algorithms.

MSC:

11Y55 Calculation of integer sequences
68W10 Parallel algorithms in computer science
37C30 Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc.
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Decimal expansion of the Vallée constant.

References:

[1] Avnaim, F.; Boissonnat, J.-D.; Devillers, O.; Preparata, F.; Yvinec, M., Evaluation of a new method to compute signs of determinants, (11th Annual ACM Symp. on Computational Geometry. 11th Annual ACM Symp. on Computational Geometry, 1995 (1997)), C16-C17, Full paper to appear in Algorithmica
[2] Babenko, K. I., On a problem of Gauss, Sov. Math. Dokl., 19, 1, 136-140 (1978) · Zbl 0389.10036
[3] (Bedford, T.; Keane, M.; Series, C., Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces (1991), Oxford University Press: Oxford University Press Oxford) · Zbl 0743.00040
[4] Beeler, M.; Gosper, R. W.; Schroeppel, R., (HAKMEM, Memorandum 239 (1972), M.I.T., Artificial Intelligence Laboratory)
[5] Billingsley, P., Probability and Measure (1986), Wiley · Zbl 0649.60001
[6] Bogomolny, E. B.; Carioli, M., Quantum maps from transfer operators, Physica D, 67, 88-112 (1993) · Zbl 0795.58038
[7] Daudé, H.; Flajolet, P.; Vallée, B., An average-case analysis of the Gaussian algorithm for lattice reduction, Combin. Probab. Comput. (1997), to appear · Zbl 0921.11072
[8] Dixon, J. D., The number of steps in the Euclidean algorithm, J. Number Theory, 2, 414-422 (1970) · Zbl 0206.33502
[9] Efrat, I., Dynamics of the continued fraction map and the spectral theory of \(SL (2,Z)\), Invent. Math., 114, 207-218 (1993) · Zbl 0811.11037
[10] Faivre, C., Distribution of Lévy’s constants for quadratic numbers, Acta Arithmetica, 61, 1, 13-34 (1992) · Zbl 0749.11035
[11] Finch, S., Favorite mathematical constants (1995), Available under World Wide Web at
[12] Flajolet, P.; Gourdon, X.; Dumas, P., Mellin transforms and asymptotics: harmonic sums, Theoret. Comput. Sci., 144, 1-2, 3-58 (1995) · Zbl 0869.68057
[13] Heilbronn, H., On the average length of a class of continued fractions, (Turan, P., Number Theory and Analysis (1969), Plenum Press: Plenum Press New York), 87-96 · Zbl 0212.06503
[14] Hensley, D., The Hausdorff dimensions of some continued fraction Cantor sets, J. Number Theory, 33, 182-198 (1989) · Zbl 0689.10060
[15] Hensley, D., The number of steps in the Euclidean algorithm, J. Number Theory, 49, 2, 142-182 (1994) · Zbl 0811.11055
[16] Hwang, H.-K., Théorèmes limites pour les structures combinatoires et les fonctions arithmetiques, (PhD thesis (1994), École Polytechnique)
[17] Kato, T., Perturbation Theory for Linear Operators (1980), Springer: Springer Berlin
[18] Khinchin, A. I., Continued Fractions (1964), University of Chicago Press: University of Chicago Press Chicago, A translation of the Russian original published in 1935. · Zbl 0117.28601
[19] Knuth, D. E., The Art of Computer Programming, (Sorting and Searching, vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0191.17903
[20] Knuth, D. E., The Art of Computer Programming, (Seminumerical Algorithms, vol. 2 (1981), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0191.17903
[21] Krasnoselskii, M., Positive Solutions of Operator Equations (1964), P. Noordhoff: P. Noordhoff Groningen
[22] Lorch, E. R., Spectral Theory (1962), Oxford University Press: Oxford University Press New York · Zbl 0151.19702
[23] Mahmoud, H., Evolution of Random Search Trees (1992), Wiley: Wiley New York · Zbl 0762.68033
[24] Mayer, D.; Roepstorff, G., On the relaxation time of Gauss’s continued fraction map. I. The Hilbert space approach, J. Statist. Phys., 47, 1/2, 149-171 (1987) · Zbl 0658.10057
[25] Mayer, D.; Roepstorff, G., On the relaxation time of Gauss’s continued fraction map. II. The Banach space approach (transfer operator approach), J. Statist. Phys., 50, 1/2, 331-344 (1988) · Zbl 0658.10058
[26] Mayer, D. H., On a ζ function related to the continued fraction transformation, Bull. Soc. Math. France, 104, 195-203 (1976) · Zbl 0328.58011
[27] 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
[28] Milne-Thomson, L. M., The Calculus of Finite Differences (1933), Chelsea: Chelsea New York, Reprinted from the original edition, London · Zbl 0008.01801
[29] Mischyavichyus, G. A., Estimate of the remainder in the limit theorem for the denominators of continued fractions, Litovskiĭ Matematic̆eskĭ Sbornik, 21, 3, 63-74 (1987)
[30] Morita, T., Local limit theorem and distribution of periodic orbits of Lasota-Yorke transformations with infinite Markov partitions, J. Math. Soc. Japan, Vol. 47, 1, 191-192 (1997), Corrections in · Zbl 0838.60021
[31] Perron, O., (Die Lehre von der Kettenbrüchen, vol. 1 (1954), Teubner: Teubner Stuttgart)
[32] Philipp, W., Ein zentraler Grenzwertsatz mit Anwendungen auf die Zahlentheorie, Zeitschrift für Wahrscheinlichkeitstheorie, 8, 195-203 (1967) · Zbl 0155.25001
[33] Rockett, A.; Szúsz, P., Continued Fractions (1992), World Scientific: World Scientific Singapore · Zbl 0925.11038
[34] Ruelle, D., Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval, (CRM Monograph Series, vol. 4 (1994), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0805.58006
[35] Sitaramachandrarao, R., A formula of S. Ramanujan, J. Number Theory, 25, 1-19 (1987) · Zbl 0606.10032
[36] Tenenbaum, G., (Introduction à la théorie analytique des nombres, vol. 13 (1990), Institut Élie Cartan: Institut Élie Cartan Nancy, France)
[37] Vallée, B., Opérateurs de Ruelle-Mayer généralisés et analyse des algorithmes d’Euclide et de Gauss, Acta Arithmetica, LXXXI.2, 101-144 (1997) · Zbl 0880.11059
[38] Vallée, B., Algorithms for computing signs of 2 × 2 determinants: dynamics and average-case analysis, (European Symposium of Algorithms (ESA) (1997)), To appear in · Zbl 1477.68496
[39] Vallée, B., Dynamique des fractions continues à contraintes périodiques, Les cahiers du GREYC (1997), Université de Caen, submitted.
[40] Wirsing, E., On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces, Acta Arithmetica, 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.