Content-Type: multipart/mixed; boundary="-------------0604160413609" This is a multi-part message in MIME format. ---------------0604160413609 Content-Type: text/plain; name="06-119.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="06-119.keywords" transfer operators, local limit theorem, continued fraction, dioohantine condition, euclidean algorithm ---------------0604160413609 Content-Type: application/x-tex; name="local.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="local.tex" \documentclass[10pt]{amsart} \usepackage{amsmath, latexsym} \usepackage{amssymb,amsthm} \usepackage{amscd, %showkeys } %\usepackage[dvips]{graphicx} %%%%%%% New theorems %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \theoremstyle{definition} \newtheorem*{definition}{Definition} \renewcommand{\theenumi}{\alph{enumi}} %%%%%%% Symbols %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\Pr{\operatorname{\mathbb P}} \def\VN{\operatorname{\mathbb V}} \def\EN{\operatorname{\mathbb E}} \def\complex{\mathbb{C}}% Complex number \def\real{\mathbb{R}}% Real number \def\integer{\mathbb{Z}}% Integer \def\disk{\mathbf{D}}% Disk \def\T{\mathbb{T}}% Torus \def\B{\mathbb{B}}% \def\supp{\mathrm{supp}}% Support \def\AA{\mathcal{A}} \def\BB{\mathcal{B}} \def\CC{\mathcal{C}} \def\DD{\mathcal{D}} \def\EE{\mathcal{E}} \def\FF{\mathcal{F}} \def\GG{\mathcal{G}} \def\HH{\mathcal{H}} \def\II{\mathcal{I}} \def\JJ{\mathcal{J}} \def\KK{\mathcal{K}} \def\LL{\mathcal{L}} \def\MM{\mathcal{M}} \def\NN{\mathcal{N}} \def\OO{\mathcal{O}} \def\PP{\mathcal{P}} \def\QQ{\mathcal{Q}} \def\RR{\mathcal{R}} \def\SS{\mathcal{S}} \def\TT{\mathcal{T}} \def\UU{\mathcal{U}} \def\VV{\mathcal{V}} \def\WW{\mathcal{W}} \def\Lip{\mathrm{Lip}} \def\id{\mathrm{Id}} \def\sp{\mathrm{sp}} \def\bQ{\mathbf{Q}} \newcommand{\sob}[1]{_{W_*^{#1}}}% \newcommand{\hol}[1]{_{C_*^{#1}}}% %%%%%%% \newcommand{\cout}[1]{} % Just cut. %%%%%%% Comment \newcommand{\comment}[1]{\marginpar{\footnotesize #1}} %Comment %\newcommand{\comment}[1]{} \begin{document} \title [A local limit theorem for Euclidean algorithms] {A local limit theorem with speed of convergence for Euclidean algorithms and diophantine costs} \author{Viviane Baladi and A\"icha Hachemi} \address{CNRS-UMR 7586, Institut de Math\'e\-ma\-ti\-ques Jussieu, Paris, France} \email{baladi@math.jussieu.fr} \address{CNRS-UMR 7586, Institut de Math\'e\-ma\-ti\-ques Jussieu, Paris, France} \email{hachemi@math.jussieu.fr} \date{\today} \begin{abstract} For large $N$, we consider the ordinary continued fraction of $x=p/q$ with $1\le p \le q\le N$, or, equivalently, Euclid's gcd algorithm for two integers $1\le p \le 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 $\integer_+^*$ of possible digits, asymptotically for $N \to \infty$. 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 Vall\'ee, as well as bounds of Dolgopyat and Melbourne on transfer operators. For smooth enough observables (depending on the diophantine condition) we attain the optimal speed. \end{abstract} \thanks{Part of this work was done during the trimester ``Time at Work" in Institut Henri Poincar\'e, Paris, 2005. Warm thanks to Fr\'ederic Naud, who pointed out to us the paper of Ian Melbourne, and to Eda Cesaratto who found a mistake in \cite{BV} and explained how to fix it. A.H. benefitted from a Gauthier-Villars Fellowship, via AFFDU. Both authors are partially supported by the ACI-DynamicAL, CNRS} \maketitle %%%%%%%%%%%%%%%%%%%%% \section{Introduction and statement of results} Every rational $x\in ]0, 1]$ admits a finite continued fraction expansion \begin {equation}\label{cfx} x= \frac{1}{{ m_1+ \frac{1}{{ m_2+ \frac{1}{~ \ddots +\frac {1} {m_{P} }~} }}}} \, , \quad m_j=m_j(x) \in \integer_+^*\, ,\, \, P=P(x) \in \integer_+^*\, . \end{equation} Continued fraction expansions can be viewed as trajectories of the Gauss map $$ T: (0, 1] \rightarrow [0, 1] \, , \quad T(x):= \frac 1 x - \bigl [ \frac 1 x \bigr ] \, .$$ (Here, $[ y ]$ is the integer part of $y \in \real^*_+$.) Indeed, if $x\ne 0$ is rational, then $T^P(x)=0$ for some $P=P(x)\ge 1$, which is the depth of the continued fraction, and the digits $m_j=m_j(x)\in \integer_+^*$ appearing in (\ref{cfx}) are just $$ m_{j}(x) =\biggl [ {\frac {1}{T^{j-1} (x) }}\biggr ]\, ,\quad 1\le j \le P(x) \, . $$ Clearly, this is equivalent to execution of Euclid's gcd algorithm: For two integers $1\le p \le q$, write $q_1=q$, $p_1=p$ and $q_1=m_1p_1+r_1$ with $m_1=m_1(p/q)\in \integer_+^*$ and a remainder $r_1\in \integer_+$ so that $r_1 < p_1$. If $r_1=0$ we are done, and $p={\rm gcd}(p,q)$, with $P(p/q)=1$. If $r_1\ne 0$, set $p_2=r_1$ and $q_2=p_1$, and iterate this procedure until the remainder $r_P$ vanishes for some $P=P(p/q)\ge 2$. Then $p_P={\rm gcd}(p,q)$, and $m_j=m_j(p/q)$ for $1\le j \le P$. Note that $m_{P(p/q)}=1$ if and only if $p=q$. We shall call {\it cost} any (nonidentically zero) function $ c : \integer_+^*\to \real $. Given such $c$, we associate to each rational $x=p/q\in (0,1]$ the following {\it total cost:} \begin{equation}\label{bir} C(x)= \sum_{j= 1}^{P(x)} c(m_{j}(x) ) \, . \end {equation} Our goal is to describe the probabilistic behaviour of the total cost associated to the ordinary (Gauss) continued fraction (\ref{cfx}) (and some of its ``fast" variants). Before stating our results, we explain our probabilistic setting, and recall previous works. Consider $\tilde \Omega := \{(p,q)\in (\integer_+^* )^ 2 \, , \frac p q \in (0,1] \}$, and $\Omega := \{(p,q) \in \tilde \Omega \mid {\rm gcd}\, (p,q)=1 \} $, and endow the sets $\tilde \Omega_N := \{(p,q)\in \tilde \Omega \mid q\le N\}$, and $\Omega_N := \{(p,q) \in \Omega\mid q\le N\} $ with uniform probabilities $\widetilde \Pr_{N}$ and $\Pr_{N}$, respectively. We shall state our results for $\Pr_N$, but, as observed e.g. in \cite{BV} (see (2.18)), they also hold for $\widetilde \Pr_{N}$. Note that if $(p,q)\in \Omega_N$ we can write $C(p,q)$ and $P(p,q)$ instead of $C(p/q)$ and $P(p/q)$. As usual, the expectation $\EN_N(C)$ denotes $\sum_{(p,q)\in \Omega_N} \Pr_N((p,q)) C(p,q)$ and the variance $\VN_N(C)$ is $\EN_N(C^2)- (\EN_N(C))^2$. We shall use the following conditions on a cost function $c$: \begin{align*} \begin{cases} c \mbox{ is of moderate growth if there exists } \nu >0 \mbox{ so that } \\ \qquad\qquad \qquad\qquad\qquad \sum_{m\in \integer^*_+} e^{\nu c(m)} m^{-2+\nu} <\infty\, , \\ c \mbox{ has moments up to order } k \ge 1 \mbox { if there exists } \nu >0 \mbox{ so that }\\ \qquad\qquad \qquad\qquad\qquad \sum_{m\in \integer^*_+} c(m)^k m^{-2+\nu} <\infty \, . \end{cases} \end{align*} Of course, if $c$ is of moderate growth then it has moments up to arbitrary order $k$. \begin{remark} If $c(m)=O(\log(m))$ then $c$ is of moderate growth, while if $c(m)=O(m^{-\nu'+1/k})$ for some $k\ge 1$ and some $\nu' >0$ then $c$ has moments up to order $k$. The terminology comes from the fact that $T$ has a unique absolutely continuous invariant measure $\mu_1$ on $[0,1]$, with a positive analytic density $f_1$ (see also Section~2), so that, writing $c_*(x)=c(m)$ if $x\in (1/(m+1), 1/m]$, we have that $\int ( c_*(x))^\ell\, d\mu_1(x)$ is well-defined for positive integers $\ell\le k$ if $c$ has moments up to order $k$. (See also \cite{BV}, and Lemma ~\ref{lemma11} below for the need to use $\nu >0$.) \end{remark} Introducing a dynamical approach (centered around the one-dimensional map $T$) and using Ruelle-type transfer operators $\mathbf H_{s}=\mathbf H_{s,0}$ to study this problem (see Section 2 below for a definition of the transfer operators), Brigitte Vall\'ee obtained in a series of papers (see e.g. \cite{Va2} for references) precise results for the asymptotics of the expectation $\EN_N(C)$ and other moments. For example, if $c$ is of moderate growth, there is $\mu(c) \in \real$ (with $\mu(c)\ne 0$ if $\int c_*(x)\, d\mu_1(x)\ne 0$) so that \begin{equation}\label{average} \lim_{N\to \infty} \frac{\EN_N(C)}{\log N}=\mu(c) \, . \end{equation} We refer to the recent work \cite{BV} for more information, a historical discussion including references to the work of Heilbronn and Dixon and previous work of Vall\'ee. Among other things it was proved in \cite{BV} that if $c$ is of moderate growth then there exists $\delta(c)\in \real_+^*$ so that \begin{equation}\label{average'} \lim_{N\to \infty} \frac{\VN_N(C)}{\log N}=(\delta(c))^2\, . \end{equation} \begin{remark} To get (\ref{average}--\ref{average'}) it suffices to assume that $c$ has moments up to order $2$. See Lemma ~\ref{basic} below. \end{remark} The article [1] also contains the following {\it central limit theorem} \cite[Theorem 3]{BV}: For each cost $c$ of moderate growth, there is $M_1(c)\ge 1$ so that for any integer $N\ge 1$, and any $y \in \real$: \begin{align}\label{CLT} \biggl | \Pr_{N} \biggl ( \frac {C(p,q) - \mu(c) \log N}{ \delta (c) \sqrt {\log N}} \le y\biggr)- \frac {1} {\sqrt {2\pi} } \int_{- \infty}^y e^{-x^2/2}\, dx \biggr | \le \frac {M_1(c)}{\sqrt {\log N}} \, , \end{align} where $\mu(c)\in \real$ and $\delta(c)>0$ are the same as in (\ref{average}). The speed of convergence $(\log N)^{-1/2}$ in the above central limit theorem is optimal, as is clear from the saddle point-argument in the proof. This speed is the equivalent in our setting of the speed of convergence in the central limit theorem for independent indentically distributed random variables \cite{Feller}. (Hensley \cite{He} obtained a central limit theorem for $c\equiv 1$, more than a decade before \cite{BV}, but with a $O((\log N)^{-1/24})$ bound on the rate of convergence.) In order to prove (\ref{CLT}), new methods were used, adapted from important work of Dolgopyat \cite{Do2}, to obtain bounds on the resolvent $(\id-\mathbf H_{s,w})^{-1}$ of the transfer operator $\mathbf H_{s,w}$, with $(s,w)\ne (1,0)$, when the complex parameter $s$ varies in a half-plane containing $1$, but the complex parameter $w$ is close to zero. We refer to \cite{BV} (in particular Theorem 2 there) for more details. A cost function $c$ is called {\it lattice}, if there exists $(L,L_0)\in \real_+^*\times \real_+$, with $L_0/L\in [0,1)$ so that $(c-L_0)/L$ is integer-valued. If $c$ is lattice but not constant, the largest possible $L$ is called the {\it span} of $c$ and the corresponding $L_0$ is called the {\it shift} of $c$. If $c$ is constant we take span $L=|c|$ and shift $L_0=0$. \footnote{The definition of lattice stated in \cite{BV} and \cite{Ha} should be replaced there by this one.} A cost function is called {\it nonlattice} if it is not lattice. If the cost is lattice with $L_0=0$ and enjoys moderate growth, then the following {\it local limit theorem} (\cite[Theorem 4]{BV}) holds: For $x\in \real$ and $N\in \integer_+^*$, put \begin{equation}\label{qx} \bQ(x,N)=\mu(c) \log N + \delta(c) x \sqrt{\log N}\, , \end{equation} then, there is $M_2(c)\ge 1$ so that for every $x\in \real$ and all integers $N\ge1$ \begin{align} \label{six} \biggl |\sqrt{\log N} \cdot \Pr_{N} \bigl ((C(p,q)- \bQ(x,N))\in (-\frac L 2, \frac L 2] \bigr ) -\frac {e^{-x^2/2}} {\delta(c) \sqrt {2 \pi} } \biggr | \le \frac {M_2(c) } {\sqrt{\log N}} \, . \end{align} (See \cite[\S 5.4]{BV} for the case $L_0\ne 0$.) Again, the constants $\mu(c)\in \real$ and $\delta(c)>0$ are the same as in (\ref{average}), and the speed of convergence is optimal. The proof uses operators $\mathbf H_{s,i\tau}$ where the complex parameter $s$ varies in a half-plane, and the real parameter $\tau$ lies in the bounded interval $[-\pi/L,\pi/L)$. Very recently, using Breiman's method to handle noncompactness issues, the second author of the present paper obtained \cite[Th\'eor\`eme~3]{Ha} a local limit theorem: For every nonlattice \footnote{The assumption that $c$ is nonlattice has been inadvertently omitted from \cite[Th\'eor\`eme~3]{Ha}: this assumption is necessary to allow arbitrarily large $L$ in \cite[Lemma~2]{Ha}, as is clear e.g. from the proof of \cite[Proposition~1(iii)]{BV}.} cost function $c$ of moderate growth, for each compact interval $J$ and every $x \in \real$, we have, writing $|J|$ for the length of $J$, and for $\mu(c)\in \real$ and $\delta(c)>0$ as in (\ref{average}): \begin{align}\label{LLT0} \lim_{N \to \infty} & \biggl |\sqrt{\log N} \cdot\Pr_{N} \bigl ( (C(p,q) - \bQ(x,N) ) \in J \bigr ) -|J |\frac {e^{-x^2/2}} {\delta(c) \sqrt {2 \pi } } \biggr | = 0 \, . \end{align} \begin{remark}Lemma~\ref{basic} and the arguments in Section 4 below show that the moderate growth assumption for (\ref{CLT}), (\ref{six}), and (\ref{LLT0}) can be replaced by the requirement that $c$ has moments up to order $3$. \end{remark} \smallskip The purpose of the present article is to obtain a local limit theorem with control of the speed of convergence in the nonlattice case. Inspired by an important paper of Dolgopyat \cite{Do} on decay of correlations for Axiom A flows (see also Naud \cite{Na} for a reader-friendly account) and guided by Melbourne's \cite{Me} version of Dolgopyat's bounds in a context closer to ours, we introduce {\it diophantine} conditions on the cost function. (See \cite{Bre, Bre2} for diophantine conditions in a related, but different, probabilistic context, and \cite{Ca} for a previous ``nonlattice of order $p$" condition.) The countable set of digits $m\in \integer_+^*$ is in bijection with the set $\HH$ of inverse branches of $T$, through $m \mapsto (y\mapsto \frac{1}{y+m})$. We may thus view the cost function $c$ as a function on $\HH$. For integer $p\ge 2$ and any subset $\HH_0$ of $\HH$, write $\HH_0^1=\HH_0$ and $\HH_0^p=\{ h\circ \tilde h \mid h \in \HH_0\, ,\tilde h\in \HH_0^{p-1} \}$. Then, we extend $c$ to a function on $\HH^p$ by setting, for $h=h_p\circ \cdots \circ h_2\circ h_1\in \HH^p$, \begin{equation}\label{extend} c(h)=\sum_{j=1}^p c(h_j)\, , \end{equation} \begin{definition} Let $\eta \ge 2$. The cost $c$ is {\it diophantine} of exponent $\eta$ if there are a finite subset $\HH_0\subset \HH$ and $\beta_0\ge 1$ so that for, any sequences $\tau_k\in \real$, $t_k\in \real$, $\theta_k\in [0,2\pi)$, with $\lim_{k\to \infty}|\tau_k|= \infty$ but $\sup_k|t_k|<\infty$, and for any $M\ge 1$ and $\beta \ge \beta_0$, there exists $x=h_x(x)$ for some $h_x\in \HH_0^p$ with $p\ge 1$ minimal, so that $$ \mbox{dist} \bigl (\tau_k [\beta \log |\tau_k|] c(h_x)+t_k [\beta \log |\tau_k|] \log |h'_x| +p \theta_k, 2\pi \integer\bigr ) \ge \frac{M p}{|\tau_k|^\eta}\, . $$ \end{definition} It is easy to check that any diophantine cost is nonlattice. Recall (\ref{qx}). Our main result is the following local limit theorem with speed of convergence: \begin{theorem}\label{main} For any diophantine cost function $c$ with moments up to order $3$: There exists $\epsilon \in (0,1/2]$ (depending on the diophantine exponent $\eta$ of $c$) so that for each compact interval $J\subset \real$ there exists a constant $M_J>0$ so that for every $x \in \real$ and all integers $N\ge 1$: \begin{align*} &\biggl | \sqrt{\log N } \Pr_N \bigl (\bigl ( C(p,q)-\bQ(x,N)\bigr )\in J \bigr ) - |J| \frac {e^{-x^2/2}}{\delta(c) \sqrt {2\pi}} \biggr | %\\ %&\qquad\qquad\qquad\qquad \qquad \qquad\qquad \qquad \qquad \le \frac {M_J}{(\log N)^\epsilon}\, . \end{align*} There exists $r\ge 1$ (depending on the diophantine exponent $\eta$ of $c$) so that for any compactly supported $\psi\in C^r(\real)$, there exists a constant $M_{\psi}>0$ so that for every $x \in \real$ and all integers $N\ge 1$: \begin{align*} &\biggl |\sqrt{\log N } \EN_N\bigl ( \psi\bigl (C(p,q) - \bQ(x,N)\bigr ) \bigr ) - \frac {e^{-x^2/2}}{\delta(c) \sqrt {2\pi}} \int \psi(y)\, dy\biggr | \le \frac {M_{\psi}}{\sqrt{\log N}}\, . \end{align*} \end{theorem} The second claim of the theorem says that we attain the optimal speed in the local limit theorem for smooth enough compactly supported observables $\psi$. Our proof gives that $\epsilon$ in the first claim is rather smaller than $\eta^{-1}<1/2$. If the cost is nonlattice but not diophantine, we expect that arbitrarily slow convergence can take place in the local limit theorem, in the spirit of \cite{Ru}. In Appendix A, we describe two other (fast) continued fraction algorithms, the {\it centered algorithm} and the {\it odd algorithm,} for which Theorem ~\ref{main} holds, with exactly the same proof. %\begin{remark} %The proof of the first claim of Theorem~\ref{main} gives a result %for bounded and integrable $\psi$ in the spirit of the second claim, %replacing $1/2$ by $\epsilon$. %\end{remark} \begin{remark}\label{Edege} If $c$ has moments up to order $k+1\ge 4$, a little more work should yield finite Edegeworth expansions \cite{Feller} (see also \cite{Bre}) of order $k$ for compactly supported $\psi\in C^r(\real)$. (The remainder term being $O((\log N)^{-k/2})$.) In this case, the condition on the differentiability $r$ of $\psi$ will depend not only on the diophantine exponent of $c$, but also on the desired order $k$ for the Edegeworth expansion. \end{remark} We next discuss genericity of the diophantine condition in Theorem~\ref{main}. Recall that a vector $x \in \real^d$ for $d\ge 1$ is {\it diophantine} of exponent $\eta_0 \ge d$ if there exists $M >0$ so that for each $(q_1, \ldots, q_d)\in \integer^d_*$ $$ \inf_{p \in \integer} \bigl |p-\sum_{k=1}^d x_k q_k \bigr |\ge \frac{M }{(\max_k |q_k|)^{\eta_0}}\, . $$ For each $\eta_0 >d$, the set of diophantine vectors of exponent $\eta_0$ has full Lebesgue measure in $\real^d$ (see e.g. \cite{Cass}). (For $\eta_0 \eta_0\ge 2$. Assume that there are four periodic points $x_1$, $x_2$, $x_3$, $x_4$ in $(0,1)$ for $T$, of respective minimal periods $p_1\ge 1$, $p_2\ge 1$, $p_3\ge 1$, and $p_4\ge 1$, with $h_j(x_j)=x_j$ for $h_j \in \HH^{p_j}$, so that, setting $c_j=c(h_j)$ and $$\widetilde L_j= p_j c_1-p_1 c_j \, ,\quad \widehat L_j=p_j\log |h'_1| -p_1\log |h'_j|\, , \quad j=2, 3, 4 \, , $$ and putting $L_2=\widetilde L_2\widehat L_3\widetilde L_4-\widehat L_2 \widetilde L_3\widehat L_4$, $ L_3=\widetilde L_2\widehat L_2(\widehat L_4-\widetilde L_4)$, $L_4=\widetilde L_2\widehat L_2(\widetilde L_3 -\widehat L_3)$, then $\widetilde L_3\ne 0$, $L_4\ne 0$, and $\frac{\widetilde L_2}{\widetilde L_3}$ and $\bigl (\frac{L_2}{L_4},\frac{L_3}{L_4}\bigr )$ are diophantine of exponent $\eta_0$. Then $c$ is diophantine of exponent $\eta$. \end{lemma} \begin{remark}\label{generic} Fix $\eta >2$. Choose four periodic points $x_j=h_j(x_j)\in (0,1]$ of $T$, with pairwise disjoint orbits (and $h_j\in \HH^{p_j}$). Then it is not difficult (see \cite[Cor. 2.4]{Me}) to deduce from Lemma~\ref{diophfour} that for Lebesgue almost every $(c_1, c_2, c_3, c_4)$ in $\real_+^4$, any cost $c$ so that $c(h_j)=c_j$ is diophantine of exponent $\eta$ (use Fubini). Therefore, the diophantine condition on the cost $c$ deserves to be called generic if $\eta >2$. \end{remark} \begin{remark} Lemma~\ref{diophfour} uses four periodic orbits, like in \cite{Me}, with additional complications due to the fact that the numbers $\widehat L_j$ are not integers. In the simpler cases studied by Dolgopyat \cite{Do} and Naud \cite{Na} %(where the analogue of the set $\HH$ %of inverse branches of $T$ is finite) it is possible to formulate a sufficient diophantine condition involving only two periodic orbits. \end{remark} \smallskip The paper is organised as follows: In Section~2, we adapt the estimates of Dolgopyat--Melbourne (\cite{Do}, \cite{Me}) to our setting to get bounds (Proposition~\ref{propres}) for the norm of $(\id - \mathbf{H}_{\sigma+it,i\tau})^{-1}$ for large $|\tau|$, bounded $|t|$, and $\sigma > 1-\delta(\tau)$ for small $\delta(\tau)$, under the diophantine assumption on $c$. Lemma~\ref{diophfour} is also proved in Section ~2. In Section~3, we first recall previous material from \cite{BV}, in particular the connection between $(\id - \mathbf{H}_{\sigma+it,i\tau})^{-1}$ and the moment generating function $\overline \EN_N( e^{i\tau C})$ of smoothened models (via the Perron formula and bivariate Dirichlet series), as well as estimates on $\overline \EN_N( e^{i\tau C})$ for bounded $|\tau|$. We then deduce from Proposition~\ref{propres} our key estimate (Corollary~\ref{cor4}), on $\overline \EN_N( e^{i\tau C})$ for large $|\tau|$. The proof of Theorem~\ref{main} is carried out in Section~4 by reducing to a study of $\int_\real \hat \chi_J(\tau) e^{-i\tau \bQ(x,N)}\overline \EN_N(e^{i\tau C}) \, d\tau$, respectively $\int_\real \hat \psi(\tau) e^{-i\tau \bQ(x,N)}\overline \EN_N(e^{i\tau C}) \, d\tau$ (with $\hat\phi$ the Fourier transform of $\phi$), and decomposing the integral over $\tau\in \real$ into four domains, over which we apply the estimates from Section 3. %(Since the bounds for $|\tau|\le 2$ are the same as %those in \cite{Ha}--\cite{BV}, we do not spell them out %in full detail, for the sake of conciseness, choosing instead %to concentrate on $|\tau|> 2$ in Section 4.) %Note that our arguments, especially in Sections 2 and 3, are quite %different from those in \cite{Bre} and \cite{Bre2}. %%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Dolgopyat-Melbourne estimates for $\mathbf H_{\sigma+it,i\tau}$} Let us first introduce some notation. Put $I=[0,1]$, and $\Lip(I)=\{u : I \to \complex \mid \|u\|_{L^\infty}+ \Lip(u)< \infty\}$, with $\Lip(u)$ the smallest Lipschitz constant of $u$. (If $u$ is not Lipschitz then we put $\Lip(u)=\infty$.) It is well-known (see \cite{BV} for references) that there exists $\rho <1$, $K\ge 1$ and $\widehat K\ge 1$ so that for all $m\in \integer_+^*$ and all $h \in \HH^m$ \begin{equation}\label{rho} \sup |h'|\le K \rho^m \, , \quad |h''(x)|\le \widehat K |h'(x)|\, , \, \forall x \in I \, . \end{equation} In this section, we focus on $|t|\le t_0$, for some fixed $t_0>0$, and $|\tau|\ge 2$, since other values of $t$ and $\tau$ are covered in previous works, as explained in the next section. For $\tau \in \real$ and $s=\sigma+it$, with $t\in \real$, $\sigma \in \real$ with $\sigma >1/2$, put for $u \in \Lip(I)$ and $x\in I$ \begin{equation}\label{opp} \mathbf H_{s,i\tau} (u )(x)= \sum_{h \in \HH} e^{i\tau c(h)} |h'(x)|^s u(h(x))\, . \end{equation} We have for the same $s$, $\tau$ and each $m\ge 1$, recalling the extension $c:\HH^m\to \real$ from (\ref{extend}), $$ \mathbf H^m_{s,i\tau}( u )(x)= \sum_{h \in \HH^m} e^{i\tau c(h)} |h'(x)|^s u(h(x))\, . $$ Letting $f_1$ be the fixed point of $\mathbf H_{1,0}$ so that $\int_I f_1(x)\, dx=1$ (in fact, $f_1(x)=(\log 2)^{-1}(1+x)^{-1}$), we put for all $t\in \real$ and $\tau\in \real$ $$ \widetilde{ \mathbf H}_{1+it,i\tau}(u)= \frac{\mathbf H_{1+it,i\tau}(f_1 u)}{f_1}\, . $$ By definition, we have $\|\widetilde {\mathbf H}^m_{1+it,i\tau}(u)\|_{L^\infty} \le \|u\|_{L^\infty}$, for all $m\in \integer_+^*$, and all real $t$ and $\tau$. It is not very difficult to show that for each $t\in \real$ there is $K(t)\ge 1$ so that \begin{equation} \label{Lasota-Yorke} \Lip(\widetilde {\mathbf H}^m_{1+it,i\tau}(u))\le K(t)\|u\|_{L^\infty}+ K \rho^m \Lip(u)\, ,\forall m\in \integer_+^*\, , \, \forall \tau\in \real\, . \end{equation} It will be convenient to use the following norm on $\Lip(I)$: $$ \|u\|_{\Lip}=\max \bigl \{\|u\|_{L^\infty},\frac{1}{2\sup_{|t|\le t_0}K(t)}\Lip(u)\bigr \}\, . $$ Indeed, recalling (\ref{rho}) and setting $n_0=[ \log K/\log(1/ \rho)] +1$, we have for all $\tau\in \real$ and all $t\in [-t_0, t_0]$ \begin{align} \nonumber &\|\widetilde {\mathbf H}^m_{1+it,i\tau}\|_{\Lip} \le K\rho ^m+ 1\, , \forall m \ge 1 \, ,\\ \label {bd1}&\|\widetilde {\mathbf H}^m_{1+it,i\tau}\|_{\Lip}\le 1 \, ,\forall m\ge n_0 \, . \end{align} \smallskip The main result of this section is: \begin{proposition}\label{propres} If the cost function $c$ is diophantine, then there are $M_0 \ge 1$, $\xi_0 \in (0,1)$, and $\alpha>0$ so that for each $|\tau|\ge 2$, all $|t|\le t_0$, and every $\sigma \ge 1-\xi_0 |\tau|^{-\alpha}$ $$ \|(\id-\mathbf H_{\sigma+it,i\tau})^{-1}\|_{\Lip}\le M_0 |\tau|^\alpha \, . $$ \end{proposition} (No growth assumption is required on $c$. The proof gives a value of $\alpha$ larger than the diophantine exponent $\eta$ of $c$.) Before we prove the proposition, by a slight modification of the argument of Dolgopyat \cite{Do}, as adapted by Melbourne \cite[\S3]{Me} to the case of infinitely many branches, we need further notation and a couple of preliminary lemmas. If $\HH_0\subset \HH$, we let $I_0=I_0(\HH_0)$ be the invariant Cantor set for $T$ associated to $\HH_0$, i.e., $I_0=\{x \in I\mid T^m(x)\in \widetilde I_0\, , \forall m \in \integer_+\}$ for $\widetilde I_0=\cup_{h\in \HH_0}h([0,1])$. Then, we set $\Lip(I_0)=\{u :I_0\to \complex \mid \Lip(u)<\infty\}$. Finally, for $\tau \in \real$ and $u\in L^\infty(I)$, we set for $x\in (0,1]$, denoting by $h_x$ the element of $\HH$ so that $x\in h_x([0,1))$, $$ \MM_{t,\tau} u(x)= |T'(x)|^{it} e^{-i\tau c(h_x)} u ( T(x))\, . $$ We may now state and prove the first lemma: \begin{lemma}\label{lemma2} Let $I_0(\HH_0)$ be associated to a finite set $\HH_0\subset \HH$. Let $\eta_1 >0$ and $\beta_0\ge 1$. Then there exist $\alpha_1 >0$, $\beta_1 >\beta_0$ and $K_0 \ge 1$ so that the following is true for each $|t|\le t_0$ and every $|\tau|\ge 2$, setting $n(\tau)=[ \beta_1 \log |\tau|]$: Suppose that there exists $v_0=v_{0,\tau,t}\in \Lip(I)$ with $\|v_0\|_{\Lip}\le 1$ so that \begin{equation}\label{ass1} |\widetilde {\mathbf H}_{1+it, i\tau}^{jn(\tau)} (v_0)(x)| \ge 1- \frac{1} {|\tau|^{\alpha_1}}\, , \forall x \in I_0\, , j=0, 1, 2 \, . \end{equation} Then there exist $\theta_{\tau,t} \in [0, 2\pi)$ and $w_{\tau,t} :I_0\to \complex$, with $|w_{\tau,t}(x)|=1$ for all $x$ and \begin{equation} \biggl | \MM^{n(\tau)}_{t,\tau} w_{\tau,t} (x)- e^{i\theta_{\tau,t}} w_{\tau,t}(x) \biggr | \le \frac{K_0} {|\tau|^{\eta_1}} \, , \quad \forall x \in I_0\, . \end{equation} \end{lemma} \begin{proof} (See Lemma 3.12 and \S3.3 in \cite{Me} adapted from \cite[Section 8]{Do}.) In this proof, we fix $t$ and $\tau$, and we write $n$ for $n(\tau)$. Letting $v_0$ be as in (\ref{ass1}), put for $j=0, 1, 2$ $$ v_j=\widetilde {\mathbf H}^{jn}_{1+it, i\tau} (v_0) \, ,\quad \,\, s_j=|v_j| \, . $$ Our assumption (\ref{ass1}) implies that \begin{equation}\label{bd2} 1- \frac{1}{|\tau|^{\alpha_1}}\le s_j(x)\le 1 \, , \forall x \in I_0\, , j=0, 1, 2 \, . \end{equation} In particular, we may define $w_j(x)=\frac {v_j(x)}{s_j(x)}$ for $x\in I_0$ and $j=0,1,2$ (and we have $|w_j|\equiv1$ on $I_0$). Note for further use that (\ref{bd1}) implies that there is a constant $K_1\ge 1$ (which does not depend on $t$ or $\tau$) so that $\|w_j \|_{\Lip(I_0)}\le K_1$ for $j=0, 1, 2$ (first show that $\|v_j \|_{\Lip(I)}$ is uniformly bounded). Since $ s_1(x)= \frac{1}{w_1(x)} \widetilde {\mathbf H}^n_{1+it,i\tau}(s_0w_0)(x) $, and $\widetilde {\mathbf H}_{1,0}({\mathbf {1}})=\mathbf {1}$ (with ${\mathbf {1}}$ the constant function $\equiv 1$), the bound (\ref{bd2}) for $j=1$ implies that for all $x\in I_0$ \begin{align*} \sum_{h \in \HH^n} \frac{f_1(h(x))}{f_1(x)} |h'(x)| \biggl ( 1- \frac{|h'(x)|^{it}}{w_1(x)} e^{i \tau c(h)} s_0(h(x)) w_0(h(x)) \biggr ) \le \frac{1}{|\tau|^{\alpha_1}} \, . \end{align*} It is not difficult to see that the real part of each term in the above sum is nonnegative. Hence, using also that $f_1\circ h/f_1$ is bounded from above and from below, uniformly in $h\in \HH^n$, we can find a constant $K_2$ (which does not depend on $\tau$) so that for each $h \in \HH^n$ and every $x \in I_0$ $$ 0\le 1- s_0(h(x)) \Re \biggl ( \frac {|h'(x)|^{it} e^{i\tau c(h)} w_0(h(x))}{w_1(x)}\biggr ) \le \frac{K_2}{|h'(x)| |\tau|^{\alpha_1}} \, . $$ Since $s_0(h(x))\le 1$, the above bound implies that for each $h \in \HH^n$ and every $x \in I_0$ $$ 0\le 1-\Re \biggl ( \frac {|h'(x)|^{it} e^{i\tau c(h)} w_0(h(x))}{w_1(x)} \biggr ) \le \frac{K_2}{|h'(x)||\tau|^{\alpha_1}} \, . $$ Using the fact that for any complex number $z$ of modulus $1$ we have $|1-z|=\sqrt{2} (1-\Re z)^{1/2}$, we find a constant $K_3$, independent of $\tau$, so that for each $h \in \HH^n$ and every $x \in I_0$ $$ \biggl |w_1(x)- |h'(x)|^{it} e^{i\tau c(h)} w_0(h(x))\biggr | \le \frac{K_3}{|h'(x)|^{1/2}|\tau|^{\alpha_1/2}} \, . $$ From now on, we restrict our attention to branches $h\in \HH_0^n$. For such a branch, we have $|h'(x)|\ge K_4 ^{-n}$ where $K_4=\sup_{h_0 \in \HH_0} \sup |h_0'|^{-1}>1$ depends only on $\HH_0$. Therefore, recalling that $n=[ \beta_1 \log |\tau|]$, if $\alpha_1$ and $\beta_1>\beta_0$ satisfy \begin{equation}\label{cond1} \alpha_1- \beta_1 \log (K_4) > 2 \eta_1\, , \end{equation} then there is a constant $K_5$ (independent of $\tau$) so that for each $x \in I_0$, setting $h_x$ to be the element of $\HH^n_0$ so that $x \in h_x([0,1))$, \begin{equation}\label{eq0} \biggl |w_1(T^{n}(x))- |(T^n)'(x)|^{-it} e^{i\tau c(h_x)} w_0(x)\biggr | \le \frac{K_5}{|\tau|^{\eta_1}} \, . \end{equation} A similar argument gives $K_6$, independent of $\tau$, so that if (\ref{cond1}) holds and $x \in I_0$ \begin{equation}\label{eq00} \biggl |w_2(T^n(x))- |(T^n)'(x)|^{-it} e^{i\tau c(h_x)} w_1(x)\biggr | \le \frac{K_6}{|\tau|^{\eta_1}} \, . \end{equation} Fix an arbitrary $x_0\in I_0$ and define $\theta_{0}=\theta_{0}(\tau,t)$ (recall that the $w_j$ depend on $\tau$ and $t$ and that $n=n(\tau)$) in $[0, 2\pi)$ by $$ e^{i \theta_{0}}= w_0(x_0) |(T^n)'(x_0)|^{-it}e^{i\tau c(h_{x_0})}\, . $$ Let $h_{x_0}\in \HH_0^n$ be so that $x_0 \in h_{x_0}([0,1))$. Observe next that (\ref{eq0}) and the fact that $T^{n}(x)=T^{n}(x_{x_0})$ and $h_{x_0}=h_{x_{x_0}}$ for $x_{x_0}=h_{x_0}(T^{n}(x))$ imply that for all $x\in I_0$ \begin{align*} &|w_1(T^n(x))- e^{i \theta_{0}} |\\ &\, \,\quad \le \frac{K_5}{|\tau|^{\eta_1}}+ |w_0(x_{x_0})- w_0(x_0) | + | |(T^n)'(x_{x_0})|^{-it} - |(T^n)'(x_0)|^{-it} |\, . \end{align*} Now, on the one hand, since $|h''/h'|\le \widehat K$, with $|h'|\le K\rho^n$, and since $|t|\le t_0$, and $|T^n(x)-T^n(x_0)|\le 1$, there is a constant $K_7$, independent of $\tau$ and $h$, so that \begin{align*} \bigl ||h_{x_0}'(T^n(x))|^{it} - |h_{x_0}'(T^n(x_0))|^{it} \bigr | \le K_7\cdot \rho^{n(\tau)} \, , \end{align*} and on the other hand, since $|x_{x_0}-x_0|\le \rho^n$ and $x_{x_0}\in I_0$ if $x\in I_0$, we have \begin{align*} |w_0(x_{x_0})- w_0(x_0) | \le K_1 \cdot \rho^{n(\tau)}\, . \end{align*} Therefore, if (\ref{cond1}) holds, and in addition \begin{equation}\label{cond2} \beta_1 > \frac {\eta_1}{\log (1/\rho)}\, , \end{equation} then we have \begin{align}\label{eq1} |w_1(T^n(x))- e^{i \theta_{0}} | \le \frac{K_1+K_5+K_7}{|\tau|^{\eta_1}}\, , \, \quad \forall x \in I_0\, . \end{align} Next, defining $\theta_1=\theta_1(t,\tau)\in [0,2\pi)$ by $$ e^{i \theta_{1}}= w_1(x_0) |(T^n)'(x_0)|^{-it}e^{i\tau c(h_{x_0})} \, , $$ the previous argument gives that if (\ref{cond1}) and (\ref{cond2}) hold then \begin{align}\label{eq2} \bigl |w_2(T^n(x))- e^{i \theta_{1}} \bigr | \le \frac{K_1+K_6+K_7}{|\tau|^{\eta_1}}\, , \quad \forall x \in I_0\, . \end{align} Putting together (\ref{eq1}) and (\ref{eq2}), we find for $\theta_{t,\tau}=\theta_0-\theta_1$ and all $x \in I_0$ \begin{align}\label{eq3} |e^{-i \theta_{t,\tau}} w_1(T^n(x))- w_2(T^n(x)) | \le \frac{2K_1+K_5+K_6+2K_7}{|\tau|^{\eta_1}}\, . \end{align} Taking $\alpha_1$ and $\beta_1$ so that (\ref{cond1}) and (\ref{cond2}) hold, and substituting (\ref{eq3}) into (\ref{eq00}) we see that the function $w=w_1$ satisfies the conclusion of the lemma for $K_0=2K_1+K_5+2K_6+2K_7$. \end{proof} We need another lemma: \begin{lemma}\label{lemma3} Let $I_0(\HH_0)$ be associated to a finite set $\HH_0\subset \HH$. For each $\alpha_1>0$ and $\beta_1 >0$, there exist $\alpha>0$ and $M_0\ge 1$ so that the following hold for each $|\tau|\ge 2$ and $|t|\le t_0$: Suppose that for each $v \in \Lip(I)$ with $\|v\|_{\Lip}\le 1$ there exists $x_0\in I_0$ and $j_0\le [3 \beta_1 \log |\tau|]$ so that \begin{equation}\label{hyp} |\widetilde {\mathbf H}^{j_0}_{1+it, i\tau}(v)(x_0)| \le 1- \frac {1}{|\tau|^{\alpha_1}}\, , \end{equation} then $ \| (\id - \mathbf H_{1+it,i\tau})^{-1} \|_{\Lip} \le M_0 |\tau|^\alpha $. \end{lemma} \begin{remark} The proof of Lemma~\ref{lemma3} uses heavily the fact that $s=1+it$ and breaks down if $s=\sigma+it$ with $\sigma< 1$. \end{remark} \begin{proof} (See Lemma 3.13 in \cite{Me}, adapted from \cite[Section 7]{Do}.) In this proof we fix $t$ and $\tau$ and write $n=n(\tau)=[3\beta_1 \log |\tau|]$. Let $v\in \Lip(I)$ be so that $\|v\|_{\Lip}\le 1$. It suffices to show that $(\id - \widetilde {\mathbf H}_{1+it,i\tau})^{-1} (v)$ exists and $\| (\id - \widetilde {\mathbf H}_{1+it,i\tau})^{-1}( v) \|_{\Lip} \le M_0 |\tau|^\alpha$ for some $\alpha>0$ and $M_0\ge 1$ which do not depend on $\tau$ or $t$. For $j_0=j_0(v,\tau)\le n$ as in (\ref{hyp}), we put $$ u_0 = \widetilde {\mathbf H}_{1+it,i\tau}^{j_0} (v) \mbox{ and } u= \widetilde {\mathbf H}_{1+it,i\tau}^{n}( v) \, . $$ We have $\| u_0\|_{L^\infty}\le 1$ and (recalling (\ref{bd1})) $\max\{ \| u_0\|_{\Lip},\| u\|_{\Lip}\}\le 1+K\rho$. By (\ref{hyp}), there is $x_0\in I_0$ (depending on $v$) so that, putting $\bar K=2(1+K\rho)\sup_{|t|\le t_0}K(t)$ \begin{equation}\label{first} |u_0 (x)|\le 1- \frac {1}{2|\tau|^{\alpha_1}}\, , \,\, \forall x\in I_{x_0}:=\{x \in I \mid|x-x_0|\le \frac{1}{ \bar K|\tau|^{\alpha_1}}\}\, . \end{equation} Recall that $\mu_1$ is the absolutely continuous probability measure on $I$ with density $f_1$ (which is $T$-invariant). By definition, the dual of $\widetilde {\mathbf H}_{1,0}$ fixes $\mu_1$. Put $m_0=m_0(\tau)=[ \frac{\alpha_1 \log|\tau|+\log (K \bar K)} {\log (1/\rho)}]+1$, then the element $h_{x_0}\in \HH_0^{m_0}$ so that $x_0\in h_{x_0}([0,1))$ is such that $h_{x_0}(I)\subset I_{x_0}$. Therefore, $\mu_1(I_{x_0})\ge \mu_1(h_{x_0}(I))$. By definition of $\mu_1$, we have (recalling (\ref{rho})) \begin{equation}\label{second} \mu_1(h_{x_0}(I)) \ge K_8^{-1} |h_{x_0}'(x_0)|\ge K_8^{-1} K_4^{-m_0(\tau)} \ge K_9^{-1} |\tau|^{-\alpha_1 \frac {\log (K_4)}{\log (1/\rho)}}\, , \end{equation} with constants $K_8\ge 1$, $K_9 \ge 1$, and $K_4\ge 1$ (recall the proof of Lemma~\ref{lemma2}) independent of $\tau$ and $t$. Putting $$ \alpha_2=\alpha_1^2\frac {\log (K_4)}{\log (1/\rho)}>0\, , $$ and decomposing $I=I_{x_0}\cup (I\setminus I_{x_0})$, we deduce from (\ref{first}) and (\ref{second}) that \begin{align}\label{L1bd} \|u\|_{L^1(\mu_1)}&\le \| u_0 \|_{L^1(\mu_1)} \le \bigl (1- \frac {1}{2|\tau|^{\alpha_1}}\bigr ) \mu_1(I_{x_0})+ 1-\mu_1(I_{x_0})=1- \frac {\mu_1(I_{x_0})}{2|\tau|^{\alpha_1}}\\ \nonumber &\le 1- K_9^{-1}|\tau|^{- \alpha_2}\, . \end{align} We next upgrade the $L^1$ estimate (\ref{L1bd}), first into an $L^\infty$ bound, and later into a Lipschitz estimate. For this, setting $n_1=[\beta_2 \log |\tau|]$, for $\beta_2>1$ to be determined later, we get from the spectral decomposition (see e.g. \cite{BV} for references) $$ \widetilde {\mathbf H}^m_{1,0}(w)=\int w\, d\mu_1 +\mathbf{R}_{1,0}^m (w)\, , $$ with $\|\mathbf{R}^m_{1,0}\|_{\Lip}\le K_{10} \hat \rho^m$, for some $\hat \rho <1$ and all $m\ge 1$, that \begin{align*} \|\widetilde {\mathbf H}^{n_1(\tau)}_{1+it,i\tau} (u)\|_{L^\infty} &\le \|\widetilde {\mathbf H}^{n_1(\tau)}_{1,0} |u|\|_{L^\infty} \le \int |u|\, d\mu_1 + K_{10} \hat \rho^{n_1}\||u|\|_{\Lip} \\ &\le 1- K_9^{-1}|\tau|^{- \alpha_2} + (1+K\rho)K_{10} \hat \rho^{n_1} \, . \end{align*} Then, if $\beta_2 > \alpha_2$ is large enough (depending on $\rho$, $\hat\rho$, $K_9$ and $K_{10}$, but not on $\tau$) we have $$ \|\widetilde {\mathbf H}^{n(\tau)+n_1(\tau)}_{1+it,i\tau} (v)\|_{L^\infty}= \|\widetilde {\mathbf H}^{n_1(\tau)}_{1+it,i\tau} (u)\|_{L^\infty}\le 1- K_{11}^{-1}|\tau|^{- \alpha_2}\, , $$ for $K_{11}\ge 1$ independent of $\tau$. Using (\ref{Lasota-Yorke}), we get for $n_2(\tau)=[\beta_3 \log |\tau|]$ with large enough $\beta_3>3\beta_1+\beta_2$ that $$ \|\widetilde {\mathbf H}^{n_2(\tau)}_{1+it,i\tau} (v)\|_{\Lip} \le 1- (2K_{11})^{-1}|\tau|^{- \alpha_2}\, . $$ Thus, since $v$ was arbitrary, $\|(\id-\widetilde {\mathbf H}^{n_2(\tau)}_{1+it,i\tau} )^{-1}\|_{\Lip} \le 2K_{11} |\tau|^{\alpha_2}$. Finally, using $$(\id -\mathbf A)^{-1}= (\id+\mathbf A+\mathbf A^2+\cdots +\mathbf A^{n_2-1}) (\id-\mathbf A^{n_2})^{-1}\, , $$ and (\ref{bd1}), we find for every $\alpha > \alpha_2$ a constant $M_0\ge 1$, independent of $\tau$ and $t$, so that $ \|(\id-\widetilde {\mathbf H}_{1+it,i\tau} )^{-1}\|_{\Lip}\le M_0 |\tau|^\alpha $. \end{proof} We may finally prove the proposition: \begin{proof}[Proof of Proposition~\ref{propres}] The statement is trivial for $\sigma >1$, because the spectral radius of $\mathbf H_{\sigma+it, i\tau}$ is then $<1$ (see e.g. \cite{BV}). For $\sigma\le 1$, we follow \cite[\S 3.2, \S3.3]{Me}: Let us first consider the case $\sigma=1$, proceeding by contradiction. It is known (see \cite[Lemma 9]{BV}) that $( \id-\mathbf H_{1+it, i\tau})^{-1}$ is bounded on $\Lip$ for each $t\in \real$ and $|\tau|\ge 2$, we only need to control the asymptotics as $\tau\to \infty$. Let $I_0(\HH_0)$ be associated to a nonempty finite set $\HH_0\subset \HH$. Fix $\eta_1>\eta$ and $\beta_0\ge 1$. Then take and $\alpha_1$, $\beta_1>\beta_0$, $K_0$ as in Lemma~\ref{lemma2}. Finally, take $\alpha$ and $M_0$ from Lemma~\ref{lemma3}. Assume that for each $M\ge M_0$ the bound $\|(\id-\mathbf H_{1+it, i\tau})^{-1}\|_{\Lip} \le M|\tau|^\alpha$ is violated for some $\tau=\tau(M)$ and $t=t(\tau)$ with $|\tau|>2$ and $|t|\le t_0$. By taking a sequence $M_k\to \infty$ we get sequences $t_k$ and $\tau_k$ with $|\tau_k|$ tending to infinity. Then Lemma~\ref{lemma3} implies that the hypothesis (\ref{ass1}) of Lemma~\ref{lemma2} is satisfied for each $(t,\tau)=(t_k,\tau_k)$ and for $\eta_1$. Therefore there are $\theta_k=\theta_{\tau_k,t_k} \in [0, 2\pi)$ and $w_k=w_{\tau_k,t_k} :I_0 \to \complex$, with $|w_k(x)|=1$ for all $x\in I_0$ and, setting $n_k=[\beta_1 \log |\tau_k|]$, \begin{equation*} \biggl | \MM^{n_k}_{t_k,\tau_k} w_{k} (x)- e^{i\theta_{k}} w_{k}(x) \biggr | \le \frac{K_0} {|\tau_k|^{\eta_1}} \, , \quad \forall x \in I_0\, . \end{equation*} If $x=h_x(x)\in I_0$ for $h_x\in \HH_0^p$ has minimal period $p\ge 1$, setting $c_x=c(h_x)$, we get \begin{equation*} \biggl | |h_x' |^{-it_k n_k} e^{-i\tau_k n_k c_x} w_{k} (x)- e^{ip\theta_{k}} w_{k}(x) \biggr | \le \frac{p K_0} {|\tau_k|^{\eta_1}} \, . \end{equation*} Since $|w_{k} (x)|=1$, we find integers $\ell_k(x)=\ell(t_k,\tau_k,x)$ with $|\ell_k|=O(|\tau_k|\log |\tau_k|)$ and a constant $D_0\ge 1$, independent of $k$ and $x$, so that \begin{equation}\label{three} |-t_k n_k\log |h' _x| -\tau n_k c_x-p \theta_{k}- 2\pi \ell_k(x) |\le pD_0 |\tau_k|^{-\eta_k} \, . \end{equation} Since $\eta_1>\eta$ and $\beta_0$ were arbitrary, this contradicts our diophantine assumption on $c$ when $k\to \infty$. If $\sigma \in (1-\xi_0 |\tau|^{-\alpha_1},1)$, we put $s=\sigma+it$ and we write $$ (\id-\widetilde {\mathbf H}_{s,i\tau})^{-1} =(\id-\widetilde {\mathbf H}_{1+it,i\tau})^{-1}(\id-\mathbf A_{s,\tau})^{-1} $$ with $\mathbf A_{s,\tau}=(\widetilde{ \mathbf H}_{s,i\tau}- \widetilde {\mathbf H}_{1+it,i\tau}) (\id-\widetilde {\mathbf H}_{1+it,i\tau})^{-1}$. It is not very difficult to prove that for each $\sigma_0 >1/2$ there is a constant $K_{12}\ge 1$ so that $$ \|\widetilde {\mathbf H}_{\sigma+it,i\tau}- \widetilde {\mathbf H}_{1+it,i\tau}\|_{\Lip} \le K_{12} (1-\sigma)\, , \forall \sigma \in (\sigma_0,1]\, , \, \, \forall |t|\le t_0\, , \, \, \forall \tau \in \real\, . $$ (Use the bijection $\ell \mapsto h_\ell$ between $\ell\in \integer_+^*$ and $h_\ell \in \HH$, from the introduction and the fact that $|h_\ell'|\le \ell^{-2}$.) Thus, using the already treated case $\sigma=1$, we get that $\|\mathbf A_{s,\tau}\|_{\Lip}\le M_0 K_{12} (1-\sigma) |\tau|^\alpha$ for all $\sigma >1$ and all $|\tau|\ge 2$. This implies that there is $\xi_0\in (0,1)$ so that $\|\mathbf A_{s,\tau}\|_{\Lip}\le 1/2$ for $\sigma \ge 1- \xi_0 |\tau |^{-\alpha}$, and the result follows. \end{proof} It remains to prove Lemma~\ref{diophfour} stated in the introduction: \begin{proof}[Proof of Lemma~\ref{diophfour}] (See e.g.\cite[\S13]{Do} or \cite[Cor. 2.4]{Me}.) Consider the smallest $\HH_0\subset \HH$ containing all points in the orbits of the four periodic points $x_j$, and let $\beta_0\ge 1$ be fixed. Let $\eta>\eta_0$ and assume that $c$ is not diophantine of exponent $\eta$. It follows that there are $\beta \ge \beta_0$, $D\ge 1$, sequences $\tau_k$, $\theta_k$, and $t_k$, and integers $\ell_{k,j}=\ell_j(t_k,\tau_k)$ so that, putting $n_k=[\beta \log|\tau_k|]$, \begin{equation}\label{three'} |-t_k n_k \log |h' _j|-\tau_k n_k c(h_j)-p_j \theta_{k}- 2\pi \ell_{k, j }|< D |\tau_k|^{-\eta} \, , \, \, j=1, 2, 3, 4 \, ,\, \forall k\, . \end{equation} Set $\tilde \ell_{k,j}=p_j\ell_{k,1}-\ell_{k,j}p_1\in \integer$ for $j=2$, $3$, $4$. We find by eliminating $\theta_{k}$ from (\ref{three'}) a constant $\widetilde D \ge 1$, independent of $k$, so that \begin{align}\label{four} &|\tau_k n_k \widetilde L_j +t_k n_k\widehat L_j -2\pi \tilde \ell_{k,j} |< \widetilde D |\tau_k|^{-\eta}\, ,\, \, j=2, 3, 4 \, ,\, \, \forall k\, . \end{align} Since $\widetilde L_3\ne 0$, if $t_k=0$ we may assume (up to taking a large enough $k$, i.e., a larger $\tau_k$) that $\tilde \ell_{k,3}\ne 0$. Then, since $\tilde \ell_{k,3}=O(|\tau_k|\log |\tau_k|)$, eliminating $\tau_k n_k$ from (\ref{four}) for $j=2$ and $j=3$ gives $\widetilde D$ (independent of $k$) so that $$ \biggl |\tilde \ell_{k,3} \frac {\widetilde L_2}{\widetilde L_3}- \tilde \ell_{k,2}\biggr |< \widetilde D |\tau_k|^{-\eta}\, ,\, \, \forall k \, . $$ Since $\tilde \ell_{k,3}=O(|\tau_k|\log |\tau_k|)$ the above bound contradicts the diophantine assumption on $\widetilde L_2/\widetilde L_3$ when we let $k \to \infty$. If $t_k\ne 0$, eliminating $t_kn_k$ from (\ref{four}), we find \begin{align*} |\tau_k n_k ( \widehat L_j\widetilde L_2-\widetilde L_j\widehat L_2) -2\pi(\widehat L_j \tilde \ell_{k,2} -\widehat L_2 \tilde \ell_{k,j })|< \widehat D |\tau_k|^{-\eta} \, ,\, \, j=3, 4\, , \, \, \forall k \, . \end{align*} Eliminating $\tau_k n_k$ from the above identities we find a constant $\widehat D$, which does not depend on $k$, so that $$ |\tilde \ell_{k,2} L_2 + \tilde \ell_{k,3} L_3 + \tilde \ell_{k,4} L_4| < \widehat D|\tau_k|^{-\eta}\, ,\, \forall k \, . $$ Since $\max(\tilde \ell_{k,2}, \tilde \ell_{k,3})=O(|\tau_k|\log |\tau_k|)$, the above bound for $k \to \infty$ contradicts our diophantine assumption on $(L_2/L_4, L_3/L_4)$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%% \section{Bounds on the moment generating function $\EN_N(e^{i\tau C})$ for smoothed costs} In this section, after recalling the methodology developed by Vall\'ee in a series of papers (see e.g. \cite{Va}), as well as some useful lemmas from \cite{BV}, we formulate in Corollary~\ref{cor4} a crucial consequence of Proposition~\ref{propres}. The relevant sequence of L\'evy moment generating functions is (see (\ref{gener})--(\ref{startpsi}) in the next section) ${\EN}_N(e^{i\tau C})$ for $N\in \integer_+$, with $\tau \in \real$. To study this sequence of functions of $\tau$, we introduce a bivariate Dirichlet series: \begin{equation}\label {S} S(s, i\tau) := \sum_{(p, q)\in \Omega}\frac {1} {q^s} e^{i\tau C(p,q)} \, ,\, s=\sigma+it\, ,\, \sigma >2\, ,\, t\in \real \, , \tau\in \real\, . \end{equation} Now, on the one hand, denoting by ${\mathbf {1}}$ the constant function $\equiv 1$ on $I$, is not very difficult to check (see e.g. \cite{BV}) that \begin{equation}\label{Dirichlet} S(2s, i\tau) = \mathbf F_{s, i\tau} (\id- \mathbf H_{s, i\tau})^{-1} ({\mathbf {1}}) (0)\, , \end{equation} with $\mathbf F_{s, i\tau} (u)(x)=\sum_{h \in \HH'} e^{i\tau c(h)} |h'(x)|^s u(h(x))$, where $\HH' \subset \HH$ contains all inverse branches of $T$ except $y\mapsto 1/(y+1)$. On the other hand, the Perron formula of order two (\cite{Ell}, see e.g. \cite{BV} for an application in the present context) gives that for each $D >1$ \begin{equation}\label{Perron} \Psi_{i\tau}(N)= \frac{1}{2i\pi} \int_{D-i\infty}^{D+i\infty} S(2s, i\tau) \frac{N^{2s+1}}{s(2s+1)} ds \, , \end{equation} where $\Psi_{i\tau} (N)$ is the following Ces\`aro sum for the Dirichlet series: $$ \Psi_{i\tau} (N)= \sum_{q \le N} \Phi_{i\tau}(q)\, ,\mbox{ with } \Phi_{i\tau}(q)= \sum_{(p,q)\in \Omega_q} e^{i\tau C(p,q)} \, . $$ Our strategy will be to study $\Psi_{i\tau} (N)$, using (\ref{Dirichlet})--(\ref{Perron}) and spectral information on the transfer operators $\mathbf H_{s,i\tau}$. Clearly, $\EN_N(e^{i\tau C})=\Phi_{i\tau}(N)/\Phi_{0}(N)$. However, exploiting directly estimates on $\Psi_{i\tau} (N)$ to get bounds on $\Phi_{i\tau}(N)$ seems difficult, and it is convenient to introduce instead auxiliary ``smoothed" models as was done in \cite[Section 4.2]{BV}. The description given there was garbled --- fortunately without consequences: All lemmas, propositions and theorems of \cite{BV} and \cite{Ha} remain correct, except for \cite[Lemma 14]{BV} and \cite [Lemme 1 (a)]{Ha} which should be replaced by Lemma~\ref{lemma14} below. We give next the correct definition of the smoothening, as found by by Eda Cesaratto (see \cite{Cesa}): For a function $\xi: \integer_+^*\to [0,1]$ and any integer $N\ge 1$, consider $$ \overline \Omega_{N}(\xi)=\bigcup_{N-[N\xi(N)|\le Q\le N} \Omega_Q \times \{Q\} \, , $$ (noting that $\Omega_0=\emptyset$), endowed with the uniform probability $ \overline {\Pr}_N(\xi)$. Setting $$ \Pi(p,q,Q)=(p,q)\, , \mbox{ for }(p,q,Q)\in \overline \Omega_N(\xi)\, , $$ define \begin{align} \label {barphi} \overline \Phi_{i\tau } (\xi,N)=\overline \Phi_{i\tau } (N)&:= \sum_{(p,q,Q)\in \overline \Omega_{N}(\xi)}e^{i\tau C(\Pi (p,q,Q))}\\ \nonumber&= \sum_{Q = N- [ N \xi (N)] }^{ N} \sum_{q \le Q} \, \, \sum _{(p, q)\in \Omega_q} e^{i\tau C(p, q)}\, . \end{align} Then the moment generating function of the smoothed cost is just \begin{equation} \label {ratio} \overline {\EN}_N(\xi, e^{i\tau C}):=\overline {\EN}_{N}(\xi, e^{i\tau C\circ \Pi}) = \frac {\overline \Phi_{i\tau}(N)} {\overline \Phi_{0}(N)} \, . \end{equation} It is easy to check that \begin {equation} \label {trans1} \overline \Phi_{i\tau} (N) = \Psi_{i\tau} (N )- \Psi_{i\tau}(N- [ N \xi (N) ]-1) \, . \end{equation} This implies that estimates on $\Psi_{i\tau} (N )$ give bounds on $\overline \Phi_{i\tau} (N)$. It remains to compare $\overline {\Pr}_{N}(\xi)$ with the primary object of interest, ${\Pr}_{N}$, and this is the purpose of Lemma~14 from \cite{BV}, that we state here in its corrected form (see \cite{Cesa}): \begin{lemma}\label{lemma14} There are $\widehat M_0>0$ and $\widehat M\ge 1$ so that for all $\xi$ with $(\xi(N))^{-1}\le \widehat M_0 N/\log N$ we have $$ \biggl | \overline {\Pr}_N(\xi)(\Pi^{-1}{(E)} )- {\Pr}_N(E) \biggr |\le \widehat M \cdot \xi(N) \, ,\, \, \forall \, E\subset \Omega_N \, , \, \forall N \in \integer_+^*\, . $$ \end{lemma} \begin{proof}[Sketch of proof] First show that there is $\widetilde M\ge 1$ so that for all $N$ and all $(p,q)\in \Omega_{N-[N\xi(N)]}$ $$ \biggl | \frac{\overline {\Pr}_N(\xi)(\Pi^{-1}{((p,q))} )}{ {\Pr}_N((p,q))}- 1 \biggr |\le \widetilde M \cdot \xi(N)\, . $$ Then prove $\Pr_N(\Omega_N\setminus\Omega_{N-[N\xi(N)]})=O(\xi(N))$ and $\overline \Pr_N(\xi)(\Pi^{-1}(\Omega_N\setminus\Omega_{N-[N\xi(N)]})) =O( \xi(N))$. \end{proof} If $\xi$ satisfies the conditions of the above lemma, then it is easy to see that for any $F :\Omega_N \to \complex$ \begin{equation}\label{consequence} |\overline {\EN}_{N}(\xi,F \circ \Pi)-{\EN}_{N}(F)|\le \max |F|\cdot \widehat M \cdot \xi(N) \, . \end{equation} We shall work with two smoothenings. The first one, $\xi_1(N)= N^{-\gamma_0}$, for some small $\gamma_0\in (0,1)$ to be introduced in Lemma~\ref{lemma11}--\ref{lemma15} below, was used already in \cite{BV}. The second one appears only in the proof of Corollary~\ref{cor4} for $|\tau|\ge 2$. \smallskip In the proof of Theorem~\ref{main} in the next section, we will have to deal with $\overline {\EN}_N(\xi_1,e^{i\tau C})$ for arbitrary $\tau \in \real$. The arguments for $\tau$ in a compact set (we shall use $|\tau|\le 2$ to fix ideas) are the same as those in \cite{BV} for the case of lattice costs. Before stating the corresponding results from \cite{BV}, let us mention an easy lemma which allows us to work with moment assumptions instead of moderate growth assumptions on the cost. If an operator has a simple eigenvalue $\lambda$ of modulus equal to its spectral radius, and if in addition the rest of the spectrum is contained in a disc of strictly smaller radius, we say that $\lambda$ is a {\it dominant eigenvalue.} For example, $1$ is the dominant eigenvalue of $\mathbf H_{1,0}$ acting on $\Lip$. \begin{lemma}\label{basic} If $c$ has moments up to order $k$ for some $k \ge 1$, there exist $\nu_0\in (0,1)$ and $\nu_1\in (0,1/2)$ so that $(s,i\tau)\mapsto \mathbf H_{s,i\tau}$ is continuous (as an operator on $\Lip$) on $$ \WW:=\{ (s,i\tau) \in \complex \times i\real \mid |s-1|< \nu_1\, , |\tau|< \nu_0\}\, , $$ and the dominant eigenvalue of $\mathbf H_{s,i\tau}$ acting on $\Lip$ is a continuous function $\lambda(s,i\tau)$ on $\WW$, which is analytic in $s$ for each $\tau$. In addition, the (rank one) spectral projector $\mathbf P_{s,i\tau}$ for $\mathbf H_{s,i\tau}$ and $\lambda(s,i\tau)$ depends continuously on $(s,i\tau)\in \WW$, and there is a uniquely defined continuous function $\sigma: (-\nu_0,\nu_0) \to \complex$, with $\sigma(0)=1$ and $\lambda(\sigma(\tau), i\tau)\equiv 1$. In fact, the functions $i\tau\mapsto \mathbf H_{s,i\tau}$, $i\tau\mapsto \mathbf F_{s,i\tau}$, $i\tau\mapsto \log \lambda(s,i\tau)$, $i\tau \mapsto \partial_s \lambda(s,i\tau)$, $i\tau\mapsto \mathbf P_{s,i\tau}$, and $i\tau \mapsto \sigma(\tau)$ are $k$ times differentiable, uniformly in $s$ for $(s,i\tau)\in \WW$. Their derivatives of order $0\le \ell \le k$ are analytic functions of $s$, uniformly in each fixed $\tau$ for $(s,i\tau)$ in $\WW$. \end{lemma} \begin{proof} See e.g. \cite[Proposition 0]{BV} for the case of moderate growth, where all objects are analytic both in $s$ and $i\tau$. The continuous extension statements for $\lambda(s,i\tau)$ and $\mathbf P_{s,i\tau}$ follows from the (easily checked) fact that if we let $\mathbf H_{s,i\tau}$ act on the Banach space $\Lip(I)$, then there is $\WW$ so that $(s,i\tau) \mapsto \mathbf H_{s,i\tau}$ is continous on $\WW$ for the corresponding operator topology. Analyticity in $s$ is clear, and we have $\partial_s \lambda(1,0)\ne 0$ as in \cite{BV}, so that the implicit function theorem gives a continuous function $\sigma(i\tau)$ as claimed. Finally, up to taking smaller $\WW$, the moment assumption on $c$ implies that, for each $|s-1|<\nu_1$, and $\ell \le k$, the $\ell$th derivative of $i\tau \mapsto \mathbf H_{s,i\tau}$, which is just $\sum_{h \in \HH} (c(h))^\ell e^{i\tau c(h)} |h'(x)|^s$, is a bounded operator on $\Lip$, which is continuous in $(s,i\tau)\in \WW$. \end{proof} The following result is a small modification of Lemma 11 from \cite{BV}: \begin{lemma}\label{lemma11} If the cost $c$ has moments up to order $k\ge 3$, letting $\nu_0\in (0,1)$, $\mathbf P_{s,i\tau}$ and $\sigma:(-\nu_0,\nu_0)\to \complex$ be as in Lemma ~\ref{basic}, there exist $\tilde\gamma_0\in (0,1)$ and $\gamma_1\in (0,1/2)$ so that for each $\gamma \in (0,\tilde \gamma_0)$, setting $\xi_1(N)=N^{-\gamma_0}$, we have for all $N \in \integer^*_+$ \begin{equation} \overline {\EN}_N (\xi_1,e^{i\tau C}) =\frac {E(i\tau)}{E(0)\sigma(i\tau)} N^{2(\sigma(i\tau)-\sigma(0))} \bigl ( 1 + O(N^{-\gamma_1})\bigr )\, , \quad \forall |\tau|< \nu_0\, , \end{equation} where the $O(N^{-\gamma_1})$ term is uniform in $\tau$, and $\tau\mapsto E(i\tau)$ is the $C^k$ function $$ E(i\tau)= \frac{-1} {(\partial_s \lambda)(\sigma(i\tau),i\tau)} \mathbf F_{\sigma(i\tau),i\tau} \circ \mathbf P_{\sigma(i\tau),i\tau} ({\mathbf{1}}) (0) \, . $$ \end{lemma} \begin{proof} The correction in the definition of the smoothening corresponds to replacing the incorrect formula $[N\xi(N)]^{-1}(\Psi_{i\tau} (N )- \Psi_{i\tau}(N- [ N \xi (N) ]))$ for $\overline \Phi_{i\tau}(N)$ given in \cite[(4.6)]{BV} by (\ref{trans1}). This is immaterial because the proof in \cite{BV} uses (\ref{ratio}), so the factors $[N\xi(N)]$ cancel out, while the difference $\Psi_{i\tau}(N- [ N \xi (N) ])-\Psi_{i\tau}(N- [ N \xi (N) ]-1)$ is negligible. Since $i\tau$ is purely imaginary, we do not require the moderate growth assumption and we can apply Lemma~\ref{basic} to adapt the proof of Lemma~11 in \cite{BV}. \end{proof} The following claim is a small modification of Lemma 15 from \cite{BV}, we shall apply it to $\nu_0$ from Lemma~\ref{lemma11} and $L=2$ in Section~4: \begin{lemma}\label{lemma15} Let $c$ be nonlattice and let $\tilde \gamma_0>0$ be given by Lemma~\ref{lemma11}. For every $L > \nu_0>0$, there exist $\gamma_0\in (0,\tilde \gamma_0)$, $\gamma_2\in (0,1/2)$ and $\widetilde M\ge 1$ so that, letting $\xi_1(N)=N^{-\gamma_0}$, we have for all $N \in \integer^*_+$ \begin{equation} |\overline {\EN}_N (\xi_1, e^{i\tau C})| \le \frac{\widetilde M}{N^{\gamma_2}}\, , \quad \forall |\tau| \in [ \nu_0, L]\, . \end{equation} \end{lemma} \begin{proof} By the last sentence of \cite[Proposition ~1]{BV}, for a nonlattice cost, there exists $\sigma_1 <1$ (depending on $\nu_0>0$ and $L$) so that $1 \notin \sp(\mathbf H_{\sigma+it, i\tau})$ (acting on $\Lip$) for all $|\tau| \in (\nu_0, L)$, all $t\in \real$, and all $\sigma> \sigma_1$. Then, the proof of \cite[Lemma~15]{BV} gives the claimed estimate. The moderate growth assumption is not used because $i\tau$ is purely imaginary. The correction in the definition of the smoothing is immaterial, as explained in Lemma~\ref{lemma11}. \end{proof} The proofs of Lemmas~11 and 15 in \cite{BV} (implicit in Lemmas~\ref{lemma11} and \ref{lemma15}) use estimates on the growth of $(\id-\mathbf H_{s,i\tau})^{-1}$, where $\tau$ is bounded, but where $s=\sigma+it$, with $|t|$ large, and $\sigma > \sigma_1$ with $\sigma_1<1$. These estimates are inspired from another important article of Dolgopyat \cite{Do2}, and use the fact that the Gauss map is ``uniformly" away from a piecewise affine map (see the condition ``UNI" in \cite{BV} for a precise formulation of this property and more details). \smallskip We now move on to ``large" values of $\tau$. We shall prove that Proposition~\ref{propres} implies the following estimate: \begin{corollary}\label{cor4} Let $c$ be diophantine, let $\alpha >0$ be given by Proposition~\ref{propres} and let $\xi_1(N)=N^{-\gamma_0}$ for $\gamma_0$ from Lemmas~\ref{lemma11}--\ref{lemma15}. For each $\alpha'>\alpha$ there exists $K'\ge 1$ so that \begin{equation}\label{cllaim} |\overline {\EN}_N(\xi_1, e^{i\tau C})| \le K' N^{-|\tau|^{-\alpha'}} \, , \, \, \forall N \in \integer^*_+\, ,\, \, \forall |\tau|\ge 2\, . \end{equation} \end{corollary} \begin{proof} Fix $|\tau|\ge 2$ and $\alpha'>\alpha$, and introduce an auxiliary smoothening (only used in this proof) \begin{equation} \xi_2(N)=N^{-|\tau|^{-\alpha'}}\, . \end{equation} By (\ref{consequence}) and the triangle inequality we have for all $N\in \integer_+^*$ $$ |\overline {\EN}_{N}(\xi_1, e^{i\tau C})-\overline {\EN}_{N}(\xi_2, e^{i\tau C}) | \le \widehat M_1 N^{-\gamma_0}+ \widehat M_2 N^{-|\tau|^{\alpha'}} \, , $$ where $\widehat M_1$ and $\widehat M_2$ are uniform in $|\tau|\ge 2$. It thus suffices to prove the claimed estimate (\ref{cllaim}) for $\overline {\EN}_{N}(\xi_2, e^{i\tau C})$. As explained in the beginning of this section, our first goal is to obtain estimates on $\Psi_{i\tau}(N)$. Recall that we write $s=\sigma+it$ and let $\xi_0\in (0,1)$ be given by Proposition~\ref{propres}. We first claim that for any $\mathcal T >0$, and each $D >1$ the function $s\mapsto S(2s,\tau)$ is holomorphic in $$ \UU_{\mathcal T}:=\{\sigma+it\mid |t|\le \mathcal T\, ,\quad \sigma \in [1-\xi_0 |\tau|^{-\alpha}, D]\}\, . $$ Recalling (\ref{Dirichlet}), it suffices to study $(\id-\mathbf H_{s, i\tau})^{-1}( {\mathbf{1}} )$ for $(s,i\tau)\in \UU_{\mathcal T}$. There is $t_0>0$, independent of $c$, so that if $|t|\ge t_0$, Theorem~2 in \cite{BV} gives $M\ge 1$ and $\bar \alpha \in (0,1/5)$ (both independent of $t$, $\tau$, and $\sigma$) so that \footnote{It is claimed in \cite{BV} that one may take $t_0 =\rho^{-2}$, but this is in fact not clear. Note in particular that the second and third inequalities in line 5 of \cite[p.362]{BV} are true only if $M_0$ is replaced by $M_0 (M_1)^k$, so that $t_0$ must be taken large enough.} \begin{equation}\label{decay} \sup\bigl | (\id- \mathbf H_{s, i\tau}) ^ {-1}( {\mathbf{1}} )\bigr | \le M |t|^{\bar \alpha} \, , \end{equation} and in particular $s\mapsto \mathbf F_{s, i\tau} (\id-\mathbf H_{s, i\tau})^{-1}( {\mathbf{1}} )(0)$ is analytic in $\{s\in \UU_{\mathcal T} \mid |t|\ge t_0\}$. If $|t|\le t_0$, we may apply Proposition~\ref{propres}, using the diophantine condition, and we get that $s\mapsto \mathbf F_{s, i\tau}(\id-\mathbf H_{s, i\tau})^{-1}( {\mathbf{1}} )(0)$ is analytic in $\{s\in \UU_{\mathcal T} \mid |t|\le t_0\}$. \smallskip Next, by Cauchy's theorem $$ \int_{\partial \UU_{\mathcal T}} S(2s, i\tau) \frac{N^{2s+1}}{s(2s+1)} \, ds =0\, , \forall N\in \integer_+^*\, . $$ Clearly (\ref{decay}) implies that $\int_{\partial \UU_{\mathcal T}, \Im s=\pm {\mathcal T}} S(2s, i\tau) \frac{N^{2s+1}}{s(2s+1)} \, ds \to 0$ as $\mathcal T\to \infty$, uniformly in $N\in \integer_+^*$. By Perron's formula (\ref{Perron}), the integral along the right-hand-side border $\Re s=D$ of $\UU_{\mathcal T}$ tends to $\Psi_{i\tau}(N)$. Finally, it is not very difficult to see that Proposition~\ref{propres} implies that there is $K_{13}\ge 1$ (depending on $\alpha'$ and $\alpha$, but not on $\tau$) with $$ |\int_{\partial \UU_{\mathcal T}, \Re s=1-\xi_0 |\tau|^{-\alpha}} S(2s, i\tau) \frac{N^{2s+1}}{s(2s+1)} \, ds| \le 4 M_0 |\tau|^\alpha N^{3-2|\tau|^{-\alpha}}\le K_{13} N^{3-2|\tau|^{-\alpha'}} \, . $$ Combining the observations in this paragraph with (\ref{trans1}) and the definition of $\xi_2(N)$ gives a constant $K_{14}\ge 1$, independent of $N$ and $\tau$, so that $$ |\overline \Phi_{i\tau} (N)|\le K_{14} N^{3-|\tau|^{-\alpha'}} \, , $$ where $\overline \Phi_{i\tau} (N)$ denotes in this proof the value (\ref{barphi}) for $\xi=\xi_2$. We claim that $\overline \Phi_0(N)= \Theta(N^3)$: The proof of this is the same as that of \cite[(4.9)]{BV}, taking into account the correction (\ref{trans1}) and noting that the moderate variation condition from \cite[Lemma~10]{BV} holds for $G(N):=\xi_2(N)=N^{-|\tau|^{-\alpha'}}$, with $(G(N))^{-1}=O(N)$, and that \cite[(4.3)]{BV} holds replacing $w$ there by $i\tau$ and $O(N^{-2\hat \alpha_0})$ by $O(G(N))$. Finally, we end the proof by applying (\ref{ratio}) for $\xi=\xi_2$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{main}} By Lemma~\ref{lemma14}, it suffices to prove Theorem~\ref{main} for $\overline \Pr_N=\overline \Pr_N(\xi_1)$ and $\overline \EN_N=\overline \EN_N(\xi_1)$, where the smoothening is $\xi_1(N)=N^{-\gamma_0}$, with $\gamma_0>0$ as in Lemma~\ref{lemma11} and Lemma~\ref{lemma15}. Letting $\chi_J$ denote the characteristic function of the interval $J$, and recalling (\ref{qx}), our starting point to prove the first claim of the theorem is standard: \begin{align} \nonumber &\overline \Pr_N((C(\cdot)-\bQ(x,N))\in J)=\sum_{(p,q,Q)\in \overline \Omega_N} \chi_J(C(p,q)-\bQ(x,N)) \cdot \overline \Pr_N(p,q,Q)\\ \label{gener} &\qquad\qquad\qquad=\sum_{(p,q,Q)\in \Omega_N} \overline \Pr_N((p,q,Q))\cdot \frac{1}{2\pi} \int_{\real} e^{i\tau(C(\cdot)-\bQ(x,N))} \hat \chi_J(\tau) \, d\tau \\ \nonumber &\qquad\qquad\qquad= \frac{1}{2\pi}\int_{\real} \hat \chi_J(\tau)e^{-i\tau \bQ(x,N}) \overline \EN_N (e^{i\tau C}) \, d\tau . \end{align} (We used $(2\pi)\psi(y)=\int \hat\psi(\tau)e^{i\tau y}\, d\tau$, where $\hat \psi(\tau)=\int e^{-i\tau x}\psi(x)\, dx$ is the Fourier transform of a locally supported bounded $\psi$.) Similarly, for the second claim, we shall use \begin{align} \nonumber\overline \EN_N(\psi(C(\cdot)-\bQ(x,N)))&=\sum_{(p,q,Q)\in \overline \Omega_N} \psi(C(\cdot)-\bQ(x,N)) \cdot \overline \Pr_N(p,q,Q)\\ \label{startpsi} &=\frac{1}{2\pi}\int_{\real} \hat \psi(\tau)e^{-i\tau \bQ(x,N)} \cdot \overline \EN_N (e^{i\tau C}) \, d\tau\, . \end{align} Since $\hat \chi_J(\tau)$ does not decay fast enough when $\tau\to \infty$, it will be necessary to regularise $\chi_J$. For this reason, the proof of the second claim of Theorem~\ref{main} is easier, and we shall start with this. %%%%%%%%%%%% \subsection{The case of smooth $\psi$} \label{psismooth} By (\ref{startpsi}) it suffices to analyse $$ I(N)= \sqrt{\log N}\int_{\real}\hat \psi(\tau) e^{-i\tau \bQ(x,N)} \cdot \overline \EN_N (e^{i\tau C}) \, d\tau\, . $$ Recalling $\nu_0\in (0,1)$ from Lemma~\ref{lemma11}, let us decompose the real axis into \begin{equation}\label{decompose} |\tau|< \nu_0\, ,\quad |\tau|\in [\nu_0,2]\, ,\quad |\tau|\in [2, L_N]\, \quad |\tau|> L_N\, , \end{equation} where $L_N>2$ will be determined later. (We shall have $L_N\to \infty$ as $N\to \infty$.) The decomposition (\ref{decompose}) gives rise to four integrals $I(N)=I_1(N)+I_2(N)+I_3(N)+I_4(N)$. The integral $I_1(N)$ over $|\tau|< \nu_0$ is the dominant term, and can be handled by exploiting Lemma~\ref{lemma11}. More precisely, the saddle-point argument in \cite[Section 3]{Ha} (see \cite[\S 5.1]{BV} for the lattice case) can be applied verbatim \footnote{In particular, the moderate growth assumption on $c$ is not necessary in \cite[Th\'eor\`eme 3]{Ha}. It is however necessary to assume that $c$ is nonlattice (this hypothesis is missing in \cite{Ha}).}: First note that the function $\EE(i\tau):=E(i\tau)/(E(0)\sigma(i\tau))$ is $C^1$ (it is in fact $C^3$ by Lemma~\ref{basic}) on $(-\nu_0,\nu_0)$, so that $\EE(i\tau)=1+ \OO(|\tau|)$. Note also that $\sigma(i\tau)$ is a $C^3$ function of $\tau$, by our assumption on the moments of $c$ and Lemma~\ref{basic}, with $\sigma(0)=1$, $\sigma'(0)=\mu(c)/2$, and $\sigma''(0)=(\delta(c)^2)/2\ne 0$ (see \cite[Lemma 12]{BV}, noting that we can replace $w$ by $i\tau$ in (4.13--4.14) there), and we can use a Taylor expansion of degree two with a remainder which is $O(|\tau|^3)$. Then decompose $|\tau|< \nu_0$ into $|\tau|< \tau_N$ and $|\tau|\in [\tau_N ,\nu_0)$ with \begin{equation}\label{tauN} \tau_N=\biggl ( \frac{\log \log N}{\delta_0\log N}\biggr )^{1/2} \end{equation} where $\delta_0>0$ depends on $\nu_0$, but not on $N$ or $\tau$ (see \cite[(5.3)]{BV}. (We may assume that $N$ is large enough to ensure $\tau_N<\nu_0$.) We find $M_{1,\psi} \ge 1$ (depending on $\sup_\tau |\hat \psi(\tau)| \le \sup|\psi| \cdot |J|$, where $J=\supp(\psi)$) so that for all $x\in \real$ and all $N\in \integer_+^*$ $$ \biggl |\frac{I_1(N)}{2\pi}- \hat \psi (0) \frac{e^{-x^2/2}}{\delta(c)\sqrt {2\pi}}\biggr | \le \frac{M_{1,\psi} }{\sqrt{\log N}}\, . $$ (Of course, $\hat \psi (0)= \int \psi(y)\, dy$.) Note that the error term $O((\log N)^{-1/2})$ above cannot be improved. However, as observed in Remark~\ref{Edege}, if $c$ enjoys moments of order $4$ or higher, replacing $\bQ(x,N)$ by a series with more terms is possible, and produces a smaller error term, giving an Edegeworth expansion. The integral $I_2(N)$ over $|\tau|\in [\nu_0,2]$ can be handled by exploiting Lemma~\ref{lemma15}, similarly to what was done previously in \cite[Section 3]{Ha} (see also \cite[\S 5.2]{BV} for the case of lattice costs, and note that the moderate growth assumption on $c$ is not needed): It is easy to see that for each $\gamma_3 \in(0, \gamma_2)$, there exists $M_{2,\psi} \ge 1$ (depending on $\sup_\tau |\hat \psi(\tau)|$) so that for all $x$ and all $N$ \begin{align*} |I_2(N) |&= \sqrt{\log N} |\int_{|\tau|\in [\nu_0, 2]}\hat \psi(\tau) e^{-i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C}) \, d\tau|\\ &\le M_{2,\psi} N^{-\gamma_3} \, . \end{align*} Clearly, the error term above is $O((\log N)^{-d})$ for arbitrarily large $d \ge 1/2$. The last two integrals are more interesting. Let us assume that $$ r >\alpha+1\, , $$ with $\alpha> 0$ from Proposition~\ref{propres} (recall that $\alpha$ depends on $\eta$ from the diophantine condition). Letting $\alpha''\in (\alpha,r-1)$ , we put \begin{equation} L_N= (\log N)^{1/\alpha''} \, . \end{equation} Then, Corollary ~\ref{cor4} implies that for each $\alpha' \in (\alpha, \alpha'')$ there is $M_{3,\psi}\ge 1$, so that for all $x$ and all $N$ \begin{align}\label{II3} |I_3(N) |&=\sqrt{\log N}|\int_{|\tau|\in [2, L_N]}\hat \psi(\tau) e^{-i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C}) \, d\tau|\\ \nonumber &\le M_{2,\psi} \sqrt{\log N}L_N N^{-L_N^{-\alpha'}}\\ \nonumber &\le M_{2,\psi} (\log N)^{1/2+ 1/\alpha''} e^{-(\log N)^{1- \alpha'/\alpha''}}\le \frac{ M_{3,\psi} }{(\log N)^{1/2}}\, . \end{align} The error term above is in fact $O((\log N)^{-d})$ for arbitrarily large $d \ge 1/2$. For each integer $m\le r$ there is $M^{(m)}_{\psi}$ so that $|\hat \psi(\tau)|\le M^{(m)}_{\psi}|\tau|^{-m}$ for all $|\tau|\ge 2$ (just use integration by parts). Finally since $r \ge \alpha' +1$ by our assumption on $r$, and since $|e^{-i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C})|\le 1$, we find, taking an integer $m \in( \alpha''+1,r]$, a constant $M_{4,\psi}\ge 1$ so that for all $N \in \integer_+^*$ \begin{align}\label{I4p} |I_4(N) |&=\sqrt{\log N} \bigl |\int_{|\tau|\ge L_N}\hat \psi(\tau) e^{-i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C}) \, d\tau \bigr |\\ \nonumber &\le M^{(m)}_{\psi}\sqrt{\log N} (\log N)^{-(m-1)/\alpha''} \le \frac{M_{4,\psi} }{(\log N)^{1/2}}\, . \end{align} Putting together the estimates on $I_1$, $I_2$, $I_3$ and $I_4$ ends the proof of the second claim of Theorem~\ref{main}. Up to taking a larger value of $m$ (if $r$ is large enough) the error term in (\ref{I4p}) can be made $O((\log N)^{-d})$ for arbitrarily large $d\ge 1/2$. %%%%%%%%%%%%%% \subsection{The case of $\chi_J$} We shall approximate the dirac delta by using Gaussian distributions, writing, for small $\delta >0$, $$ \Delta_\delta(x)=\delta^{-1} \Delta(x/\delta) \mbox{ with } \Delta(x)= \frac{1}{\sqrt{\pi}} e^{-x^2} \, . $$ For further use, note: \begin{lemma}\label{decay2} There is $D_0\ge 1$ so that for every $\psi\in L^1(\real)$ with $y\psi(y)\in L^1(\real)$, setting $ \psi_{\delta}= \psi * \Delta_\delta$, the Fourier transform of $\psi_\delta$ satisfies: \begin{align}\label{hatpsi} &|\hat \psi_\delta(\tau)| \le D_0\int |\psi (y)|\, dy \cdot e^{-\delta^2 \tau^2} \le D_0\int |\psi (y)|\, dy \, , \, \, \forall \delta >0\,, \tau \in \real\, , \\ \label{hatpsi2}& \Lip(\hat\psi_\delta)\le D_0\bigl (\int |y \psi (y)|\, dy+\int |\psi (y)|\, dy\bigr ) \, , \, \, \forall \delta > 0 \, . \end{align} In addition, if $\psi$ is Lipschitz, we have \begin{equation}\label{converge} \sup_x | \psi(x) -\psi_\delta(x)|\le D_0 \, \Lip(\psi) \cdot \delta\, , \, \, \forall \delta >0 \, . \end{equation} \end{lemma} \begin{proof} To show (\ref{hatpsi}--\ref{hatpsi2}), use $\hat\psi_{\delta}(\tau)=\hat \psi(\tau) \cdot \widehat \Delta_\delta(\tau) $, and recall that the Fourier transform $\widehat \Delta_\delta(\tau)$ of $\Delta_\delta$ is $$ \widehat \Delta_\delta(\tau)=e^{-\delta^2 \tau^2}\, . $$ To show (\ref{converge}), use $\int \Delta_\delta(y)\, dy=1$ to write \begin{align*} |\psi(x) -\psi_\delta(x)|= \bigl |\int_{\real} \Delta_\delta(y) (\psi(x)-\psi(x-y))\, dy\bigr | \le \Lip(\psi) \int_{\real} \Delta_\delta(y) |y| \, dy\, , \end{align*} and note that $\int_{\real_+} \frac{y}{\sqrt{\pi}\delta} e^{-\frac{y^2}{\delta^2}} \, dy=O(\delta) $. (Just write $z=y/\delta$.) \end{proof} Write $J=[a,b]$. For small $\delta \in (0, (b-a)^2/4)$, in view of applying the previous lemma, we first approximate $\chi_J$ by two compactly supported Lipschitz functions $\psi^+=\psi^{+,\delta}_J:\real \to[0,1]$ and $\psi^-=\psi^{-,\delta}_J:\real\to [0,1]$, as follows. The function $\psi^+$ is $\equiv 1$ on the interval $[a-\sqrt \delta,b+\sqrt\delta]$, it is $\equiv 0$ outside of $[a-2\sqrt \delta,b+2\sqrt\delta]$, and it is affine with slope $\pm \delta^{-1/2}$ on the two remaining intervals. Similarly, $\psi^-$ is $\equiv 1$ on $[a+2\sqrt\delta,b-2\sqrt\delta]$ it is $\equiv 0$ outside of $[a+\sqrt \delta,b-\sqrt\delta]$, and it is affine with slope $\pm \delta^{-1/2}$ on the two remaining intervals. We have that $\int \psi^\pm (y)\, dy= |J|+O(\sqrt \delta)$ and $\int |y|\psi^\pm (y)\, dy\le 4 |J|^2$. In addition \begin{align*} \overline \EN_N(\psi^-(C(\cdot)-\bQ(x,N))) &\le \overline \Pr_N((C(\cdot)-\bQ(x,N))\in J)\\ &\le \overline \EN_N(\psi^+(C(\cdot)-\bQ(x,N))) \, . \end{align*} Next, we consider the regularisation by convolution $$ \psi^{\pm}_{ \delta}= \psi^{\pm,\delta}_J*\Delta_\delta\, , \mbox{ with } \delta=\delta_N=(\log N)^{-2\epsilon} \, , $$ with $\epsilon >0$ to be determined later. Since $\Lip (\psi^\pm)=\delta^{-1/2}$, the bound (\ref{converge}) from Lemma~\ref{decay2} gives $$ \bigl | \overline \EN_N(\psi^{\pm}(C(\cdot)-\bQ(x,N)))- \overline \EN_N(\psi^{\pm}_\delta(C(\cdot)-\bQ(x,N))) \bigr | \le D_0 \sqrt \delta\le D_0 (\log N)^{-\epsilon}\, . $$ Therefore, by (\ref{gener}), it suffices to analyse $$ I^\pm_\delta(N)= \sqrt{\log N}\int_{\real}\hat \psi^\pm_{\delta}(\tau) e^{-i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C} ) \, d\tau\, . $$ We consider the decomposition (\ref{decompose}) of $\real$, for $L_N$ to be determined later, and the four associated integrals $I^\pm_\delta(N)=I_{\delta,1}^\pm(N)+I_{\delta,2}^\pm(N)+ I_{\delta,3}^\pm(N)+I_{\delta, 4}^\pm(N)$. Introducing $\tau_N$ like in (\ref{tauN}), and using in addition the uniform bound (\ref{hatpsi2}) on the Lipschitz constant of $\hat \psi^\pm_{\delta}(\tau)$ in order to see that $$ \sup_{|\tau|\le \tau_N} |\hat \psi^\pm_{\delta}(0)-\hat \psi^\pm_{\delta}(\tau)|\le M_J \cdot \tau_N\, , $$ we find $M_{1,J} \ge 1$ (using Lemma~\ref{basic} as in \S~\ref{psismooth} and the weak claim in (\ref{hatpsi}) to bound $\sup |\hat \psi^\pm|$) so that for all $x\in \real$ and all $N\in \integer_+^*$ \begin{equation}\label{dominant} \biggl |\frac{I^\pm_{\delta,1}(N)} {2\pi}- \hat \psi^\pm_{\delta} (0) \frac{e^{-x^2/2}}{\delta(c)\sqrt {2\pi}}\biggr | \le \frac{M_{1,J} }{(\log (N))^{1/2}}\, . \end{equation} (The term $O((\log N)^{-1/2})$ in the above expression cannot be improved.) Note that \begin{equation}\label{dom2} \hat \psi^\pm_{\delta} (0)= \int \psi^\pm_{\delta} (y)\, dy= \int \psi^\pm_\delta (y)\, dy =|J|+ O(\sqrt \delta_N) =|J|+O((\log N)^{-\epsilon})\, . \end{equation} Just like in \S~\ref{psismooth}, since $c$ is nonlattice, for each $\gamma_3 \in(0, \gamma_2)$, there exists $M_{2,J} \ge 1$ (using the weak bound from (\ref{hatpsi})) so that for all $x\in \real$ and all $N\in \integer_+^*$ \begin{align}\label{I2} |I^\pm_{\delta,2}(N) |\le M_{2,J} N^{-\gamma_3} \, . \end{align} Take $\alpha'' >\alpha$, with $\alpha$ from Corollary~\ref{cor4}, and put $L_N= (\log N)^{1/\alpha''}$. (We may assume $\alpha'' >2$.) Then, Corollary ~\ref{cor4} (with the weak bound from (\ref{hatpsi})) implies that (see (\ref{II3})) for each $\alpha' \in (\alpha, \alpha'')$ there is $M_{3,J}\ge 1$ so that for all $x\in \real$ and all $N\in \integer_+^*$ \begin{align} \nonumber |I^\pm_{\delta,3}(N) |&=\sqrt{\log N} |\int_{|\tau|\in [2, L_N]}\hat \psi^\pm_\delta(\tau) e^{-i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C} ) \, d\tau|\\ \label{I3} &\le \frac{ M_{3,J} }{(\log N)^{1/2}}\, . \end{align} Finally if $$2\epsilon < (\alpha'')^{-1}$$ then\footnote{We may take a smaller value of $\delta_N$, but our argument requires $\inf_N (\delta_N L_N)>0$.} $\delta_N L_N> \log \log N$, and, since $|e^{-i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C} )|\le 1$ we find, using the strong bound from (\ref{hatpsi}), that there are constants $\widetilde M_{4,J}\ge 1$ and $M_{4,J}\ge 1$ so that for all $x\in \real$ and all $N\in \integer_+^*$ \begin{align}\label{I4} |I^\pm_{\delta,4}(N) |&=\sqrt{\log N}|\int_{|\tau|\ge L_N}\hat \psi(\tau) e^{ -i\tau \bQ(x,N)} \overline \EN_N (e^{i\tau C}) \, d\tau|\\ \nonumber &\le \widetilde M_{4,J} \sqrt{\log N}L_N e^{- (\delta L_N)^2} \le \widetilde M_{4,J} \sqrt{\log N}L_N e^{- (\log \log N)^2}\\ \nonumber &\le \frac{ M_{4,J}}{(\log N)^{1/2}}\, . \end{align} Putting together (\ref{dominant}--\ref{I2}--\ref{I3}--\ref{I4}) we have proved the first claim of Theorem~\ref{main}, for $ \epsilon \in (0, 1/(2\alpha'')) $. %%%%%%%%%%%%%%%%%%%%% \begin{appendix} \section{The centered and odd euclidean algorithms} Let us describe two variants $\KK$ and $\OO$ of the classical continued fraction (\ref{cfx}), for rational $x\in (0,1]$. Both of them are of the form \begin {equation}\label{cfx2} x= \frac{1}{{ m_1+ \frac{\varepsilon_1}{{ m_2+ \frac{\varepsilon_2}{~ \ddots +\frac {\varepsilon_{P-1}} {m_{P} }~} }}}} \, , \,\, m_j \in \integer_+^*\, , P\in \integer_+^*\, , \epsilon_J\in \{-1,1\}\, . \end{equation} The first one is the {\it centered} algorithm $\KK$, for which all digits $m_j$ are $\ge 2$. It is described by the following centered division algorithm, for integers $p$ and $q$ with $1\le p \le q/2$: write $q=mp+\epsilon r$, with $m \in \integer_+^*$, $\epsilon \in \{-1,1\}$, and integer $r$ with $\epsilon r \in [-p/2,p/2]$. If $r=0$ we take $m_{1,\KK}(p/q)=m$, $P_\KK(p/q)=1$, and we are done. Otherwise, we put $m_1=m$, $\epsilon_1=\epsilon$, $p_2=r_1=r$, and $q_2=p_1$, and we iterate until $r_{P_\KK}=0$, constructing the $m_{j,\KK}(p/q)$ and $\epsilon_{j,\KK}(p/q)$ along the way. The associated dynamical system on $(0,1/2]$ satisfies $T_\KK(p/q)=r/p$ and is just $$ T_\KK(x)= \bigl | \frac 1 x - A_\KK\bigl (\frac 1 x\bigr ) \bigr | \, , $$ where $A_\KK(y)$ is the nearest integer to $y$, i.e., the unique integer $m$ so that $y-m \in [-1/2,1/2)$. The second one is the {\it odd} algorithm $\OO$, for which all digits $m_j$ are odd. It is described by the following odd division algorithm, for integers $1\le p \le q$: write $q=mp+\epsilon r$, with odd $m \in \integer_+^*$, $\epsilon \in \{-1,1\}$, and an integer $r$ with $\epsilon r \in [-p,p]$. If $r=0$ we take $m_{1,\OO}(p/q)=m$, $P_\OO(p/q)=1$, and we are done. Otherwise, we put $m_1=m$, $\epsilon_1=\epsilon$, $p_2=r_1=r$, and $q_2=p_1$, and we iterate until $r_{P_\OO}=0$, constructing the $m_{j,\OO}(p/q)$ and $\epsilon_{j,\OO}(p/q)$along the way. The associated dynamical system on $(0,1]$ satisfies $T_\OO(p/q)=r/p$ and is just $$ T_\OO(x)= \bigl |\frac 1 x - A_\OO\bigl (\frac 1 x\bigr ) \bigr | \, , $$ where $A_\OO(y)$ is the nearest odd integer to $y$, i.e., the unique odd integer $m$ so that $y-m \in [-1,1)$. We refer e.g. to \cite[Section 2]{BV} for more information on these two algorithms and their associated interval maps $T_\KK$ and $T_\OO$. Letting $\HH_\KK$ and $\HH_\OO$ denote the set of inverse branches of $T_\KK$ and $T_\OO$, respectively, it turns out that the corresponding transfer operators $\mathbf H_{s,i\tau, \KK}$ and $\mathbf H_{s,i\tau, \OO}$ enjoy the same properties as those of the operator $\mathbf H_{s,i\tau}$ associated to the ordinary euclidean division and (\ref{cfx}). (See \cite[Section 2]{BV} for the invariant densities $f_{1,\OO}$ and $f_{1,\KK}$, the constants $\rho_\OO$ and $\rho_\KK$, etc., and also \cite[Proposition~0]{BV} as well as \cite[\S3.4]{BV} for the condition "UNI.") In particular, all statements in Sections 2 and 3 of the present paper hold, replacing the Gauss map $T$ by $T_\OO$ or $T_\KK$, up to changing the constants. The proof in Section 4 can be followed for both algorithms, and finally we see that Theorem~\ref{main} is true also for the centered and odd algorithms, up to replacing $\mu(c)$ and $\delta(c)$ by appropriate constants $\mu_\KK(c)$, $\delta_\KK(c)>0$ or $\mu_\OO(c)$, $\delta_\OO(c)>0$. \end{appendix} %%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{amsplain} \begin{thebibliography}{10} \bibitem{BV} V. Baladi and B. Vall\'ee, \textit{Euclidean algorithms are Gaussian,} J. Number Theory {\bf 110} (2005) 331--386. \bibitem{Bre} E. Breuillard, \textit{Distributions diophantiennes et th\'eor\`eme limite local sur $\real^d$,} Probab. Theory Relat. Fields {\bf 132} (2005) 39--73. \bibitem{Bre2} E. Breuillard, \textit{Local limit theorems and equidistribution of random walks on the Heisenberg group,} Geom. funct. anal. {\bf 15} (2005) 35--82. \bibitem{Ca} H. Carlsson, \textit{Remainder term estimates of the renewal function,} Ann. Probab. {\bf 11} (1983) 143--157. \bibitem{Cass} J.W.S. Cassels, \textit{An Introduction to Diophantine Approximation,} Cambridge Tracts in Mathematics and Mathematical Physics, No. 45. Cambridge University Press, New York, 1957. \bibitem{Cesa} E. Cesaratto, \textit{Remarks and extensions on ``Euclidean algorithms are Gaussian'' by Baladi-Vall\'ee,} in preparation (2006). \bibitem{Do} D. Dolgopyat, \textit{Prevalence of rapid mixing in hyperbolic flows,} Ergodic Theory Dynam. Systems {\bf 18} (1998) 1097--1114. \bibitem{Do2} D. Dolgopyat, \textit{On decay of correlations in Anosov flows,} Ann. Math. {\bf 147} (1998) 357--390. \bibitem{Ell} W. Ellison and F. Ellison, \textit{Prime Numbers,} John Wiley \& Sons, Inc., New York, Hermann, Paris (1985). \bibitem{Feller} W. Feller, \textit{An Introduction to Probability Theory and its Applications,} Vol. II, John Wiley \& Sons, Inc., New York-London-Sydney (1971). \bibitem{Ha} A. Hachemi, \textit{Un th\'eor\`eme de la limite locale pour des algorithmes Euclidiens,} Acta Arithm. {\bf 117} (2005) 265--276. \bibitem{He} D. Hensley, \textit{The number of steps in the Euclidean algorithm,} J. Number Theory {\bf 49} (1994) 142--182. \bibitem{Me} I. Melbourne, \textit{Rapid decay of correlations for nonuniformly hyperbolic flows,} preprint (2005) to appear Trans. Amer. Math. Soc. \bibitem{Na} F. Naud, \textit{Analytic continuation of a dynamical zeta function under a Diophantine condition,} Nonlinearity {\bf 14} (2001) 995--1009. \bibitem{Ru} D. Ruelle, \textit{Flots qui ne m\'elangent pas exponentiellement,} C.R. Acad. Sci. {\bf 296} (1983) 191--193. \bibitem {Va} B. Vall\'ee, \textit{Euclidean Dynamics}, Discrete Continuous Dynam. Systems {\bf 15} (2006) 281-352. \bibitem{Va2} B. Vall\'ee, \textit{Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems,} Colloque International de Th\'eorie des Nombres (Talence, 1999). J. Th\'eor. Nombres Bordeaux {\bf 12} (2000) 531--570. \end{thebibliography} \end{document} ---------------0604160413609--