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

DOI10.1214/07-AIHP140zbMATH Open1231.37015arXivmath/0604341OpenAlexW3101414622MaRDI QIDQ731697FDOQ731697

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)

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}_{+}^{*}$ 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.

Full work available at URL: https://arxiv.org/abs/math/0604341

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

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)

Cites Work

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

Cited In (5)

• Un théorème de la limite locale pour des algorithmes Euclidiens
• 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
• Alternative proofs of linear response for piecewise expanding unimodal maps
• Superpolynomial and polynomial mixing for semiflows and flows

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)