A local limit theorem with speed of convergence for Euclidean algorithms and Diophantine costs

DOI10.1214/07-AIHP140MaRDI QIDQ731697zbMATH OpenOpenAlexFDO

Authors Viviane Baladi, Aïcha Hachemi

Publication date 8 October 2009

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0604341, https://eudml.org/doc/77990

zbMATH Keywords

continued fractionlocal limit theoremtransfer operatorspeed of convergenceDiophantine conditionEuclidean algorithms

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Analysis of algorithms (68W40) Functional analytic techniques in dynamical systems; zeta functions, (Ruelle-Frobenius) transfer operators, etc. (37C30) Number-theoretic algorithms; complexity (11Y16)

Abstract: For large $N$, we consider the ordinary continued fraction of $x=p/q$ with $1lepleqleN$, or, equivalently, Euclid's gcd algorithm for two integers $1lepleqleN$, 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 $mathbb{Z}_{+}^{\ast }$ of possible digits, asymptotically for $Noinfty$. 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. We use previous estimates of the first author and Vall'{e}e, and we adapt to our setting bounds of Dolgopyat and Melbourne on transfer operators. Our diophantine condition is generic (with respect to Lebesgue measure). For smooth enough observables (depending on the diophantine condition) we attain the optimal speed.

Recommendations

• The Euclid algorithm is ``totally Gaussian
• Euclidean algorithms are Gaussian
• Sharp Estimates for the Main Parameters of the Euclid Algorithm
• Diophantine approximations and local limit theorem in \(\mathbb R^d\)
• Analysis of fast versions of the Euclid algorithm

Cites work

• scientific article; zbMATH DE number 3125787 (Why is no real title available?)
• scientific article; zbMATH DE number 3842834 (Why is no real title available?)
• scientific article; zbMATH DE number 4012703 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• A local limit theorem for closed geodesics and homology
• Analytic continuation of a dynamical zeta function under a Diophantine condition
• Asymptotic winding of the geodesic flow on modular surfaces and continuous fractions
• Berry--Esseen theorem and local limit theorem for non uniformly expanding maps
• Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems
• Diophantine approximations and local limit theorem in \(\mathbb R^d\)
• Euclidean algorithms are Gaussian
• Euclidean dynamics
• Local limit theorems and equidistribution of random walks on the Heisenberg group
• On decay of correlations in Anosov flows
• On the rate of mixing of Axiom A flows
• Prevalence of rapid mixing in hyperbolic flows
• Rapid decay of correlations for nonuniformly hyperbolic flows
• Remainder term estimates of the renewal function
• The number of steps in the Euclidean algorithm
• Un théorème de la limite locale pour des algorithmes Euclidiens

Cited in

(5)

• Alternative proofs of linear response for piecewise expanding unimodal maps
• Superpolynomial and polynomial mixing for semiflows and flows
• A note on ``Euclidean algorithms are Gaussian by V. Baladi and B. Vallée
• Limit laws for rational continued fractions and value distribution of quantum modular forms
• Un théorème de la limite locale pour des algorithmes Euclidiens

This page was built for publication: A local limit theorem with speed of convergence for Euclidean algorithms and Diophantine costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q731697)