Séminaire du 15 mars 04, Brigitte Vallée.

Les algorithmes d'Euclide sont Gaussiens

Nous obtenons une loi limite gaussienne pour une classe de paramètres additifs associées à trois algorithmes d'Euclide, avec une vitesse de convergence optimale, ainsi que des expressions asymptotiques très précises pour l'espérance et la variance. Pour des paramètres à valeurs entières (comme le nombre d'itérations, le nombre d'occurrences d'un chiffre fixé, ou la longueur du codage binaire du développement en fraction continue), nous obtenons également un Théorème Local Limite, toujours avec une vitesse de convergence optimale.

Nous utilisons des méthodes d'analyse dynamique. Voyant un algorithme d'Euclide comme un système dynamique (restreint à des entrées rationnelles), nous combinons des outils ``dynamiques", comme les opérateurs de transfert, avec des techniques variées~: séries de Dirichlet, formule de Perron, théorème des quasi-puissances, méthode du col. Pour la présente analyse en distribution, nous avons de plus besoin d'estimations liées à l'opérateur de transfert lorsque le paramètre varie le long de droites verticales dans le plan complexe. Nous obtenons de telles estimations en adaptant à notre contexte des techniques récentes que Dolgopyat a introduites dans le contexte de la dynamique à temps continu. (Travail commun avec Viviane Baladi, Université Paris VII et CNRS.)