A generalization of the Dirichlet approximation theorem for affine actions on the real line

Introduction

The Dirichlet approximation theorem states that, given a real number $u$ and a positive integer $N$, there exist integers $p,q$ with $0<q\leq N$ such that

In particular, if $u$ is irrational then $\left|p/q-u\right|<q^{-2}$ for infinitely many reduced fractions $p/q$. We give a formulation of this theorem in terms of semigroup actions which leads to natural generalizations.

Let $\Gamma$ be the free semigroup generated by two letters $\sigma$ and $\tau$, with identity $\lambda_0$ (the empty word). Given two maps $T_0,T_1:(0,\infty)\to(0,\infty)$, we obtain an action of $\Gamma$ on $(0,\infty)$ by letting $\sigma$ act as $T_0$ and $\tau$ act as $T_1$; words act as compositions, so that $(w_1w_2)(x)=w_1(w_2(x))$ (the rightmost letter acts first). We write $\gamma\in\Gamma(T_0,T_1)$ when we want to emphasize the choice of $T_0$ and $T_1$. The length $|\cdot|:\Gamma\to\mathbb{Z}_{\geq0}$ is defined by $|\lambda_0|=0$, $|\sigma|=|\tau|=1$ and $|w_1w_2|=|w_1|+|w_2|$. For $x,y>0$ we say that $y$ is reachable from $x$ if $y=\gamma(x)$ for some $\gamma\in\Gamma$, and we define the reachability function

with $R(x,y)=\infty$ if $y$ is not reachable from $x.

Since only finitely many words have a given length, “infinitely many $\gamma$” forces $|\gamma|\to\infty$ along the approximating words.

The Möbius pair

In Section 2 we take

Here $\gamma(1)$ is always a positive rational number, and Lemma 2.2 shows $R(1,p/q)\le p+q$; combined with (1) this shows that every irrational $u$ is approached at rate $O(|\gamma|^{-2})$. We prove Theorem 2.4 that every orbit is $O(n^{-1})$-dense in $[0,\infty)$, with the rate $n^{-2}$ at irrational targets. We then refine this in two directions. First (Theorem 2.5 and Corollary 2.6), the true rate at an irrational $u$ is governed by the continued fraction expansion of $u: it is exponential in $|\gamma|$ when $u$ has bounded partial quotients, and it is at least $\exp(-c|\gamma|/\log|\gamma|)$ for Lebesgue almost every $u$, for every $c<\pi^2/6$. Second (Proposition 2.9), for rational targets and rational starting points the exponent 1 is optimal: by an argument with the Stern–Brocot tree, $|\gamma(x)-k/l|\ge1/(l^2(s(x)+|\gamma|))$ whenever $\gamma(x)\ne k/l$, where $s(x)$ is the sum of the partial quotients of $x$.

The affine pair

In Section 3 we consider

Bergelson, Misiurewicz and Senti [4] showed that every orbit of this action is dense in $[0,\infty)$. Our main result (Theorem 3.8) is that every orbit is in fact exponentially dense: for every $x>0$ and $u\ge0$ there are infinitely many $\gamma$ with $|\gamma(x)-u|<C\lambda^{-|\gamma|}$ where $\lambda=\lambda(a,b)>1$ is explicit. The proof rests on an explicit normal form for $\gamma(x)$ (Lemma 3.1) and a greedy algorithm, and it does not distinguish between rational and irrational values of $\log_a b$. A counting argument (Proposition 2.11) shows that for almost every $u$ no rate faster than $\mu^{-|\gamma|}$ with $\mu>2$ is possible, so the exponential order is optimal.

We also give corrected versions of two earlier estimates: a Kronecker-type bound $|\gamma(x)-u|<(u+1)(t^{1/|\gamma|}-1)$ with $t=a^{12}b^4$ when $\log_a b$ is irrational (Theorem 3.2), and an exponential bound with exponent independent of $u$ when $\log_a b$ is rational (Theorem 3.6). Since $t^{1/n}-1\sim(\log t)/n$, the Kronecker-type bound is an $O(n^{-1})$ statement; it is superseded by Theorem 3.8, but its proof is short and the words it produces are very simple.

The contrast between the two sections is worth noting: for the Möbius pair rational targets are approached only at rate $n^{-1}$ (at least from rational starting points), whereas for the affine pair every target is approached exponentially fast.

Relation to the 3x+1 problem

The $3x+1$ (Collatz) problem asks whether iterating

eventually reaches 1 from every positive integer; see [12] for a survey. In our notation, with $a=2$ and $b=3$, a Collatz trajectory is a particular orbit segment of $\Gamma(T_0,T_1)$, namely one in which $T_0$ is applied exactly to even integers and $T_1$ exactly to odd integers. Thus the Collatz conjecture implies that 1 is reachable from every positive integer via $\Gamma(T_0,T_1)$; the converse is not clear, since the semigroup allows $T_1$ to be applied to even integers as well.

Moreover, any sequence $x_1,\ldots,x_m$ with $x_1 \in\mathbb{N}$, $x_m=1$ and $x_{i+1} \in\{T_0(x_i),T_1(x_i)\}$ consists of integers. Indeed, write $v_2$ for the 2-adic valuation on $\mathbb{Q}^{\times}$. If $v_2(x_i)<0$ then $v_2(T_0x_i)=v_2(x_i)-1<0$ and $v_2(T_1x_i)=v_2(3x_i+1)=v_2(x_i)<0$, so once a non-integer appears, all later terms are non-integers; since $x_m=1$ is an integer, no $x_i$ can be a non-integer.

Theorem 3.8 shows that, starting from any $x>0$, there are words $\gamma$ of arbitrarily large length $n$ with $|\gamma(x)-1|<C\lambda^{-n}$, where $\lambda=\lambda(2,3)\approx1.2133$.

Primes

In § 4 we discuss approximating real numbers by ratios of primes and by ratios of logarithms of primes, updating the discussion in light of the work of Goldston, Pintz and Yıldırım [8, 7], Zhang [18], Maynard [13] and Baker, Harman and Pintz [3].

The Möbius pair

Throughout this section $T_0(x)=1/x$ and $T_1(x)=x+1$.

Matrices and continued fractions

Associate to $T_0$ and $T_1$ the matrices

and to a word $\gamma=w_1\cdots w_n$ the product $M_\gamma=M_{w_1}\cdots M_{w_n}$. If $M_\gamma=\begin{pmatrix}A&B\\C&D\end{pmatrix}$ then $A,B,C,D$ are non-negative integers, $AD-BC=\pm1$, $C+D\ge1$, and

Every positive rational number $r$ has a unique canonical continued fraction expansion $r=[a_0;a_1,\ldots,a_k]$ with $a_0\ge0$, $a_1,\ldots,a_k\ge1$, and either $k=0$ (and then $a_0\ge1$) or $k\ge1$ and $a_k\ge2. We put

Proof. Let $r=[a_0;a_1,\ldots,a_k]$ be canonical. Then $T_1r=[a_0+1;a_1,\ldots,a_k]$ is canonical. If $a_0=0$ then $k\ge1$ and $T_0r=[a_1;a_2,\ldots,a_k]$ is canonical. If $a_0\ge1$ and $k\ge1$, then $T_0r=[0;a_0,a_1,\ldots,a_k]$ is canonical; if $a_0\ge2$ and $k=0$ then $T_0r=[0;a_0]$ is canonical; and if $r=[1]$ then $T_0r=r$. In all cases the sum of the partial quotients is preserved by $T_0$ and increased by one by $T_1$. □

Proof. The lower bound follows from Lemma 2.1, since $s(1)=1$ and each word reaching $r$ from $1$ contains at least $s(r)-1$ letters $\tau$. For the upper bound, put $z_k=a_k$ and $z_i=a_i+1/z_{i+1}$ for $i<k$, so that $z_0=r$. Then $z_k=T_1^{a_k-1}(1)$ and $z_i=T_1^{a_i}T_0(z_{i+1})$, so $r$ is reached from $1$ by a word of length $(a_k-1)+\sum_{i<k}(a_i+1)=s(r)+k-1$.

For the last statement, apply the bound on $p+q$ (one may also deduce it from (5)). If $p=q$ then $R(1,p/q)=0$. If $p>q$ then $p/q=T_1((p-q)/q)$, so $R(1,p/q)\le1+R(1,(p-q)/q)\le1+p$. If $1<p<q$ then $p/q=T_0T_1((q-p)/p)$, so $R(1,p/q)\le2+R(1,(q-p)/p)\le q+2\le p+q$. Finally, if $p=1$ then $1/q=T_0T_1^{q-1}(1)$ and $R(1,1/q)\le q$. □

Density

Define $Q:[0,\infty)\to\{1,2\}$ by $Q(u)=1$ if $u$ is rational and $Q(u)=2$ if $u$ is irrational.

Irrational targets and continued fractions

Let $u=[a_0;a_1,a_2,\ldots]$ be irrational, with convergents $p_k/q_k$, and put $S_k=a_0+a_1+\cdots+a_k$.

(b) If $a_i \le A$ for all $i \ge1$, then $|\gamma(x)-u| < C\varphi^{-2|\gamma|/(A+1)}$ for infinitely many $\gamma$, where $\varphi=(1+\sqrt{5})/2$ and $C=C(x,u)$.

(c) For Lebesgue almost every $u>0$ and every $c<\pi^2/6$, there are infinitely many $\gamma$ with $|\gamma(x)-u|<\exp(-c|\gamma|/\log|\gamma|)$.

Proof. (a) We have $q_1=a_1$ and, for $k\ge2$, $q_k=a_kq_{k-1}+q_{k-2}\ge(a_k+q_{k-1}-1)+q_{k-2}\ge a_k+q_{k-1}$, using $(a_k-1)(q_{k-1}-1)\ge0$ and $q_{k-2}\ge1$. Hence $q_k\ge a_1+\cdots+a_k=S_k-a_0\ge k$, and

By Theorem 2.5, $|\gamma_k(x)-u|<(x+1)q_k^{-2}\le4(x+1)(|\gamma_k|-a_0)^{-2}$, which is at most $C|\gamma_k|^{-2}$ for $k$ large. The words $\gamma_k$ are pairwise distinct, because the values $\delta_k(1)=p_k/q_k$ are distinct.

(b) Now $q_k\ge\varphi^{k-1}$ and $|\gamma_k|\le a_0+(A+1)k$, so

(c) By Lévy’s theorem, $\frac{1}{k}\log q_k\to\beta:=\frac{\pi^2}{12\log2}$ for almost every $u$. By Khinchin’s weak law for the sums of partial quotients, $S_k/(k\log k)\to1/\log2$ in measure; hence there is a fixed sequence $k_j\to\infty$ along which $S_{k_j}/(k_j\log k_j)\to1/\log2$ almost everywhere (see [10, 11]).

Fix $\eta>0$ and such a $u$. For $j$ large, $n_j:=|\gamma_{k_j}|\le(1+\eta)k_j\log k_j/\log2$, hence $k_j\ge\frac{\log2}{1+\eta}\frac{n_j}{\log n_j}$ (as $k_j\le n_j$), and

Choosing $\eta$ small in terms of $c<\pi^2/6$ gives the claim. □

Remark 2.7. Part (a) is the estimate $|\gamma(x)-u|\le C|\gamma|^{-2}$ asserted for irrational $u$ in Theorem 2.4. Parts (b) and (c) show that it is far from optimal for most $u$; for instance, for the golden ratio the orbit of $1$ approaches $\varphi$ exponentially fast. On the other hand, by Proposition 2.11 below, for almost every $u$ no rate $\mu^{-|\gamma|}$ with $\mu>2$ is possible.

Optimality for rational targets

We use the Stern–Brocot tree (see [9 §4.5]). Its nodes are the positive rationals, each occurring exactly once; the root is $1/1$, and the node $r=[a_0;a_1,\ldots,a_k]$ (canonical) has depth $s(r)-1$. Every node $u=k/l$ has a nearest left ancestor $k_L/l_L<u$ and a nearest right ancestor $k_R/l_R>u$ (with the conventions $0/1$ and $1/0$ at the boundary) such that $k=k_L+k_R$, $l=l_L+l_R$ and $kl_L-lk_L=k_Rl-l_Rk=1$; moreover, the rationals in the open interval $(k_L/l_L,k_R/l_R)$ are exactly the nodes of the subtree rooted at $u$.

and therefore

where we used $l_L\le l$ and $j+1\le D+1$.

Remark. 2.10. We expect the same lower bound, with a constant depending on $x$, for irrational starting points $x$, but we have not proved it.

A general upper limit on the rate

The following observation applies to any pair of maps.

The affine pair

Throughout this section $T_0(x)=x/a$ and $T_1(x)=bx+1$ with $a,b>1$, and $\sigma,\tau$ act as $T_0,T_1$. We put $\alpha=\log_a b>0$.

A normal form

The Kronecker-type estimate

We use the following inhomogeneous form of Kronecker’s theorem ([5, Ch. III, Thm. II], [16, §2.4]): if $\alpha$ is irrational and $\beta\in\mathbb{R}$, then there are infinitely many pairs of integers $(m,n)$ with $m > 0$ and

Proof. If $u=0$, then $\gamma=\sigma^m$ gives $\gamma(x)=xa^{-m}<t^{1/m}-1$ for $m$ large. Let $u>0$ and $\beta=\log_a((b-1)u)$. By (8) there are infinitely many pairs of positive integers $(m,n)$ with

and since $|\log_a(b^m-1)-m\alpha|=|\log_a(1-b^{-m})|<1/m$ for $m$ large,

Let $\eta=\sigma^n\tau^{m-1}$. Since $\tau^{m-1}(1)=(b^m-1)/(b-1)$, we have $\eta(1)=(b^m-1)/((b-1)a^n)$, and (11) says $|\log_a\eta(1)-\log_a u|<4/m$. Hence

Now let $\gamma=\eta\tau\sigma^m=\sigma^n\tau^m\sigma^m$, so that $\gamma(x)=\eta(bxa^{-m}+1)$. Since $\eta$ is affine with derivative $b^{m-1}a^{-n}$,

using $b^m a^{-n}=a^{m\alpha-n}<(b-1)ua^{3/m}$ from (10). The right side is exponentially small in $m$, so for $m$ large

Finally, (10) gives $n<(\alpha+1)m$ for $m$ large, hence $|\gamma|=2m+n<(\alpha+3)m$, and

Remark 3.3. Since $t^{1/n}-1\sim(\log t)/n$, Theorem 3.2 says that every orbit is $O(n^{-1})$-dense, with the explicit constant $|\gamma(x)-u|\lesssim4(u+1)(3\log a+\log b)/|\gamma|$.

Rational $\log_a b$

Proof. Let $d_0=\lceil u-1\rceil$ and $\rho_0=u-d_0\in(0,1]$. Given $\rho_k\in(0,a^{-k}]$, let $d_{k+1}=\lceil\rho_k a^{k+1}-1\rceil$ and $\rho_{k+1}=\rho_k-d_{k+1}a^{-k-1}$. Since $0<\rho_k a^{k+1}\leq a$, we get $0\leq d_{k+1}<\rho_k a^{k+1}\leq a$ and $\rho_{k+1}=a^{-k-1}(\rho_k a^{k+1}-d_{k+1})\in(0,a^{-k-1}]$. If $d_k=0$ for all $k\geq K$, then $\rho_k=\rho_K>0$ for $k\geq K$, contradicting $\rho_k\leq a^{-k}\to0$. $\square$

Proof. Note $\tau\sigma(z)=z+1$. For $k=0$ take $\eta=(\tau\sigma)^{d_0-1}$. For the inductive step write $P=\sum_{i=0}^{k+1}d_i a^{-i}=d_0+Q/a$ with $Q=\sum_{i=0}^{k}d_{i+1}a^{-i}$; if $\mu(1)=Q$ with $|\mu|\le k+2\sum_{i\ge1}d_i$ and $\mu'=a^{-k}$, then $\eta=(\tau\sigma)^{d_0}\sigma\mu$ satisfies $\eta(1)=P$, $|\eta|\le k+1+2\sum_{i\ge0}d_i$ and $\eta'=a^{-k-1}$.

Proof. The case $a=b$. If $u=0$, use $\gamma=\sigma^M$. Let $u>0$ and let $d_i$ be as in Lemma 3.4. For each $k$ with $d_k>0$, Lemma 3.5 gives $\gamma_k$ with $\gamma_k(1)=\sum_{i\le k}d_i a^{-i}$, $\gamma_k'=a^{-k}$ and

Then

The values $\gamma_k(1)$ are strictly increasing in $k$, so the $\gamma_k$ are distinct.

The general case. Let $c=\sum_{i=0}^{n_0-1}b^i$ and $\theta(z)=cz$. Then

because $T_1^{n_0}(y)=b^{n_0}y+c$. Applying the first case to $(S_0,S_1)$, with base $A$, to $v=x/c$ and $w=u/c$, we get infinitely many words $\mu$ in $S_0,S_1$ with $|\mu(v)-w|<C'A^{-|\mu'|/(2A+1)}$, where $|\mu'|$ is the length in $S_0,S_1$. Each such $\mu$ equals $\theta^{-1}\gamma\theta$ for a word $\gamma$ in $T_0,T_1$ with $|\gamma|\le\max\{m_0,n_0\}|\mu'|$, and $|\gamma(x)-u|=c|\mu(v)-w|$.

Exponential density for all $a,b>1$

Proof. The case $u=0$. We have $\log\lambda\le\log a$, because $\log\frac{a}{a-1} \le\log\frac{a^{2b}}{a-1}$. So $\gamma=\sigma^{M}$ gives

A greedy expansion. Let $u>0$. Set $\ell_{-1}=0$ and $r_{-1}=u$. For $j=0,1,2,\ldots$, given an integer $\ell_{j-1}$ and $r_{j-1}>0$, let $\ell_j^*$ be the least integer $\ell$ with $b^j a^{-\ell}<r_{j-1}$, and put

Since $\ell_j\ge\ell_j^*$ we have $t_j<r_{j-1}$, so $r_j>0$ and the recursion continues; also $0=\ell_{-1}\le\ell_0\le\ell_1\le\cdots$ and $r_j=u-\sum_{i\le j}t_i$. Call step $j$ free if $\ell_j=\ell_j^*$.

(i) If step $j$ is free, then $t_j\ge r_{j-1}/a$; hence $r_j\le(1-1/a)r_{j-1}$ and $r_j\le(a-1)t_j$. Indeed, by minimality of $\ell_j^*$, $a t_j=b^j a^{-(\ell_j^*-1)}\ge r_{j-1}$.

(ii) If step $j$ is free, so is step $j+1$. We must show $\ell_{j+1}^*\ge\ell_j$, i.e. that $\ell=\ell_j-1$ violates $b^{j+1}a^{-\ell}<r_j$. But $b^{j+1}a^{-(\ell_j-1)}=ab t_j>(a-1)t_j\ge r_j$ by (i).

(iii) Some step is free. If steps $0,\ldots,j$ are not free, then $\ell_0=\cdots=\ell_j=0$ and $t_i=b^i$, so $1+b+\cdots+b^j<u$. Hence the first free step $J$ satisfies $b^J\le1+(b-1)u$.

By (i)–(iii), for every $N>J$,

The words. For $N>J$ let $M_N=\max\{\ell_{N-1},\lceil\kappa N\rceil\}$ and let $\gamma_N$ be the word of Lemma 3.1 with data $N$, $\ell_0\le\cdots\le\ell_{N-1}$ and $M=M_N$. Then $L:=|\gamma_N|=N+M_N$ and

Put $\vartheta=\kappa-\alpha=\log_a\frac{a}{a-1}>0$, so that $a^{-\vartheta}=1-1/a$ and $\lambda=a^{\vartheta/(1+\kappa)}$.

Case $M_N=\ell_{N-1}$. By (14), $|\gamma_N(x)-u|\le\left(x+\frac{a-1}{b}\right)a^{N\alpha-M_N}$. Since $M_N\ge\kappa N$ and $\vartheta+\alpha=\kappa$, a direct computation gives

that is, $M_N-N\alpha\ge\vartheta L/(1+\kappa)$. Hence $|\gamma_N(x)-u|\le\left(x+\frac{a-1}{b}\right)\lambda^{-L}$.

Case $M_N=\lceil\kappa N\rceil>\ell_{N-1}$. Then $b^N a^{-M_N}\le a^{-\vartheta N}=(1-1/a)^N$, and by (14),

As $L\le(1+\kappa)N+1$, we have $(1-1/a)^N=\lambda^{-(1+\kappa)N}\le\lambda^{1-L}$.

In both cases $|\gamma_N(x)-u|\le C\lambda^{-|\gamma_N|}$ with $C=\lambda\left(x+u\left(\frac{a}{a-1}\right)^J\right)+\frac{a-1}{b}$, and the words $\gamma_N$, $N>J$, are distinct since they contain different numbers of letters $\tau$. Replacing $C$ by $2C$ gives strict inequality. □

Remark 3.9. (1) Theorem 3.8 makes no use of the arithmetic of $\log_a b$, and it supersedes Theorem 3.2 and, for small $a$, Theorem 3.6. For instance, $\lambda(2,3)\approx1.2133$ and $\lambda(2,2)=2^{1/3}$, whereas Theorem 3.6 gives $\rho=2^{1/5}$ when $a=b=2$; for $a=b=10$, on the other hand, Theorem 3.6 gives the larger base $10^{1/21}\approx1.116$ against $\lambda\approx1.053$.

(2) By Proposition 2.11, for almost every $u$ the base $\lambda$ in (13) can never exceed $2$; thus exponential density is the optimal order, although we have not tried to optimize $\lambda$. Numerical experiments suggest that the greedy words of the proof perform considerably better than the bound $\lambda^{-|\gamma|}$.

(3) The constant $C$ depends on $u$ only through $u\left(\frac{a}{a-1}\right)^J\le u(1+(b-1)u)^{\log_b\frac{a}{a-1}}$, a polynomial in $u$.

Prime approximation of real numbers

Let $p_n$ denote the $n$-th prime. Goldston, Pintz and Yıldırım [8] (see also [7]) proved that

equivalently $|p_{n+1}/p_n-1|=o(\log p_n/p_n)$ for infinitely many $n$. Zhang [18] proved that $\liminf(p_{n+1}-p_n)<\infty$, and Maynard [13] and the Polymath project [15] improved this to $\liminf(p_{n+1}-p_n)\le246$. Hence $|p_{n+1}/p_n-1|\le246/p_n$ for infinitely many $n$. This suggests the following.

The cases $u=0$ (take $p=2$) and $u=1$ (by the bounded gaps theorem) are known, the latter in the stronger form $|p/q-1|\le246/q$. A naive probabilistic model suggests that even $|p/q-u|<c/q$ should have infinitely many solutions for every $c>0$, since for each prime $q$ the interval $(uq-c,uq+c)$ should contain a prime with probability about $2c/\log q$, and $\sum_q1/\log q$ diverges.

Unconditionally, Baker, Harman and Pintz [3] proved that $[x-x^{0.525},x]$ contains a prime for all sufficiently large $x$. Choosing a prime $p$ in $[uq-(uq)^{0.525},uq]$ shows that, for every fixed $u>0$ and every sufficiently large $q$ (prime or not),

Assuming the Riemann Hypothesis, Cramér [6] showed $p_{n+1}-p_n=O(\sqrt{p_n}\log p_n)$, which improves (17) to $|p/q-u|\le Cuq^{-1/2}\log q$, still far from (16).

Ratios of logarithms of primes

We need a Mills-type lemma [14, 17]; we include the short proof.

From $q_n \leq\theta^{u^n} < q_n + 1$ and $\theta^{u^{n+1}} = \left(\theta^{u^n}\right)^u$ we get

The right inequality gives $u-\frac{\log q_{n+1}}{\log q_n}<\frac{\log(1+1/q_{n+1})}{\log q_n}<\frac{1}{q_{n+1}\log q_n}$. The left one gives

using $\log q_{n+1}<u\log(q_n+1)$ and $\log(1+1/q_n)<1/q_n$. □

The feature of Theorem 4.3 is that the approximations form a chain: each $q_n$ serves as the numerator of one approximation and the denominator of the next. For a single pair, a much stronger estimate holds for all $u>0$:

Proof. Let $X=q^u$ and pick a prime $p\in[X-X^{0.525},X]$ [3]. Then $0\leq\log X-\log p\leq-\log(1-X^{-0.475})\leq2X^{-0.475}$; divide by $\log q$. □

For $u>40/19$ we have $q^{-0.475u}=o(q^{-1})$, so Proposition 4.4 is stronger than (18) pair by pair; its proof, however, does not produce chains.

Finally, if $0<v<19/40$, applying Theorem 4.3 to $u=1/v$ gives a sequence of primes with

This implies $q_n>q_{n+1}^v\exp(-1/q_n)$, and therefore, for every fixed $\varepsilon>0$ and $n$ large,

References

Department of Mathematics and Statistics, Siena University, Loudonville, NY 12211

Email address: [email protected]