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

Brigitte Vallée

Acta Arithmetica (1997)

  • Volume: 81, Issue: 2, page 101-144
  • ISSN: 0065-1036

How to cite

top

Brigitte Vallée. "Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss." Acta Arithmetica 81.2 (1997): 101-144. <http://eudml.org/doc/207058>.

@article{BrigitteVallée1997,
author = {Brigitte Vallée},
journal = {Acta Arithmetica},
keywords = {continued fraction algorithm; Gauss algorithm; convergence; Gaussian law; asymptotic distribution of the number of iterations; Ruelle-Mayer operators},
language = {fre},
number = {2},
pages = {101-144},
title = {Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss},
url = {http://eudml.org/doc/207058},
volume = {81},
year = {1997},
}

TY - JOUR
AU - Brigitte Vallée
TI - Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss
JO - Acta Arithmetica
PY - 1997
VL - 81
IS - 2
SP - 101
EP - 144
LA - fre
KW - continued fraction algorithm; Gauss algorithm; convergence; Gaussian law; asymptotic distribution of the number of iterations; Ruelle-Mayer operators
UR - http://eudml.org/doc/207058
ER -

References

top
  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. Zbl0796.11024
  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. Zbl0841.11063
  5. [Di] J. H. Dixon, The number of steps in the Euclidean algorithm, J. Number Theory 2 (1970), 414-422. Zbl0206.33502
  6. [Fa] C. Faivre, Distribution of Lévy constants for quadratic numbers, Acta Arith. 61 (1992), 13-34. Zbl0749.11035
  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). Zbl0981.11044
  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. Zbl0811.11055
  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. Zbl0473.68030
  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. Zbl0488.12001
  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. Zbl55.0916.02
  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. Zbl0428.47016
  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. Zbl0714.58018
  25. [Ma5] D. H. Mayer, Approach to equilibrium for locally expanding maps in R k , 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. Zbl0658.10057
  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. Zbl0824.60017
  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. Zbl0925.11038
  31. [Va1] B. Vallée, Gauss' algorithm revisited, J. Algorithms 12 (1991), 556-572. Zbl0779.11065
  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. Zbl0283.10032

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.