Download PDF - Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de GaussAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss

Authors 1

Affiliations

  1. GREYC-URA 1526, Département d'Informatique, Université de Caen, 14032 Caen Cedex, France

Bibliography

  1. [Ba] K. I. Babenko, On a problem of Gauss, Soviet Math. Dokl. 19 (1978), 136-140.
  2. [Br] A. Broise, Aspects stochastiques de certains systèmes dynamiques : transformations dilatantes de l'intervalle, fractions continues multidimensionnelles, Ph.D. Thesis, Université de Rennes, 1994.
  3. [DV] H. Daudé and B. Vallée, An upper bound on the average number of iterations of the LLL algorithm, Theoret. Comput. Sci. 123 (1994), 95-115.
  4. [DFV] H. Daudé, P. Flajolet and B. Vallée, An analysis of the Gaussian algorithm for lattice reduction, in: Algorithmic Number Theory (Ithaca, N.Y., 1994), Lecture Notes in Comput. Sci. 877, Springer, 1994, 144-158. Version longue en Rapport de Recherche du Laboratoire GREYC de l'université de Caen, à paraître dans Combinatorics, Probability and Computing.
  5. [Di] J. H. Dixon, The number of steps in the Euclidean algorithm, J. Number Theory 2 (1970), 414-422.
  6. [Fa] C. Faivre, Distribution of Lévy constants for quadratic numbers, Acta Arith. 61 (1992), 13-34.
  7. [FV] P. Flajolet and B. Vallée, Continued fraction algorithms, functional operators and structure constants, Conférence invitée à la 7e Conférence Fibonacci, Graz, juillet 96, Rapport de Recherche INRIA 2931 (juillet 96).
  8. [Ga] C. F. Gauss, Recherches arithmétiques, 1807, réimprimé par Blanchard, Paris, 1953.
  9. [Gr1] A. Grothendieck, Produits tensoriels topologiques et espaces nucléaires, Mem. Amer. Math. Soc. 16 (1955).
  10. [Gr2] A. Grothendieck, La théorie de Fredholm, Bull. Soc. Math. France 84 (1956), 319-384.
  11. [Hei] H. Heilbronn, On the average length of a class of continued fractions, in: Number Theory and Analysis, P. Turán (ed.), Plenum, New York, 1969, 87-96.
  12. [He] D. Hensley, The number of steps in the Euclidean algorithm, J. Number Theory 49 (1994), 142-182.
  13. [Hw] H.-K. Hwang, Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques, Ph.D. Thesis, Ecole Polytechnique, Palaiseau, 1994.
  14. [KS] M. Kaib and C. P. Schnorr, A sharp worst-case analysis of the Gaussian lattice basis reduction algorithm for any norm, J. Algorithms, to appear.
  15. [Kr] M. Krasnosel'skiĭ, Positive Solutions of Operator Equations, Chap. 2, Noordhoff, Groningen, 1964.
  16. [Ku] R. Kuzmin [R. O. Kuz'min], Sur un problème de Gauss, Atti del Congresso internazionale dei matematici, Bologna, 1928, Vol. 6, 83-89.
  17. [Lag] J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), 142-186.
  18. [Lam] D. Lamé, Note sur la limite du nombre de divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers, C. R. Acad. Sci. 19 (1845), 867-870.
  19. [LLL] A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 513-534.
  20. [Le] P. Lévy, Sur la loi de probabilité dont dépendent les quotients complets et incomplets d'une fraction continue, Bull. Soc. Math. France 57 (1929), 178-194.
  21. [Ma1] D. H. Mayer, Continued fractions and related transformations, in: Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, T. Bedford, M. Keane and C. Series (eds.), Oxford University Press, 1991, 175-222.
  22. [Ma2] D. H. Mayer, On composition operators on Banach spaces of holomorphic functions, J. Funct. Anal. 35 (1980), 191-206.
  23. [Ma3] D. H. Mayer, Spectral properties of certain composition operators arising in statistical mechanics, Comm. Math. Phys. 68 (1979), 1-8.
  24. [Ma4] D. H. Mayer, On the thermodynamic formalism for the Gauss map, Comm. Math. Phys. 130 (1990), 311-333.
  25. [Ma5] D. H. Mayer, Approach to equilibrium for locally expanding maps in Rk, Comm. Math. Phys. 95 (1984), 1-15.
  26. [MR] D. Mayer and G. Roepstorff, On the relaxation time of Gauss' continued fraction map. I. The Hilbert space approach, J. Statist. Phys. 47 (1987), 149-171, II. The Banach space approach (transfer operator approach), J. Statist. Phys. 50 (1988), 331-344.
  27. [Mi] G. A. Misyavichyus [G. Misevičius], Estimate of the remainder in the limit theorem for the denominators of continued fractions, Litovsk. Mat. Sb. 21(3) (1987), 63-74 (in Russian).
  28. [Mo] T. Morita, Local limit theorem and distribution of periodic orbits of Lasota-Yorke transformations with infinite Markov partition, J. Math. Soc. Japan 46 (1994), 309-343.
  29. [Ph] W. Philipp, Some metrical theorems in number theory II, Duke Math. J. 37 (1970), 447-488. Errata, Duke Math. J., 788.
  30. [RS] A. Rockett and P. Szűsz, Continued Fractions, World Scientific, Singapore, 1992.
  31. [Va1] B. Vallée, Gauss' algorithm revisited, J. Algorithms 12 (1991), 556-572.
  32. [Va2] B. Vallée, Algorithms for computing signs of 2 × 2 determinants: dynamics and average-case algorithms, Les Cahiers Du GREYC, Université de Caen, 1996.
  33. [Wi] E. Wirsing, On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces, Acta Arith. 24 (1974), 507-528.
Acta Arithmetica
1997/81/2
Export to PBN, Opens in new tab
Pages:
101-144
Main language of publication
French
Received
1995-07-12
Accepted
1996-12-23
Published
1997
Exact and natural sciences