- 06-119 Viviane Baladi and Aicha Hachemi
- A local limit theorem with speed of convergence
for Euclidean algorithms and diophantine costs
(78K, AMS LaTeX)
Apr 16, 06
(auto. generated ps),
of related papers
Abstract. For large N, we consider the ordinary continued fraction
of x=p/q with 1<= p <= q<= N, or, equivalently, Euclid's
gcd algorithm for two integers 1<= p <= q\le N,
putting the uniform distribution on the set of p and q's.
We study the distribution of the total cost of execution
of the algorithm for an additive cost function
c on the set Z_+ of possible digits,
asymptotically for N going to infinity.
If c is nonlattice
and satisfies mild growth conditions, the local limit theorem was
proved previously by the second named author.
Introducing diophantine conditions on the cost, we are
able to control the speed of convergence in the local limit
theorem, by using previous estimates of the first author
and Valleee, as well as bounds of Dolgopyat and Melbourne on