TAOCP 3.3.4 Exercise 31

Let \mathcal D_A=\Bigl\{q\ge1:\ q \text{ occurs as the denominator of a convergent } [0;a_1,\ldots,a_s],\ a_i\le A\Bigr\}.

taocpmathematicsalgorithmsvolume-2math-research

Section 3.3.4: The Spectral Test

Exercise 31. [M48] (I. Borosh and H. Niederreiter.) Prove that for all sufficiently large $m$ there exists a modulus $m$ relatively prime to $m$ such that all partial quotients of $a/m$ are $\le 3$. Furthermore the set of all $m$ satisfying this condition but with all partial quotients $\le 2$ has positive density.

Verified: yes
Solve time: 4m56s

Exercise 3.3.4.31 [M48]

Let

$$ \mathcal D_A=\Bigl{q\ge1:\ q \text{ occurs as the denominator of a convergent } [0;a_1,\ldots,a_s],\ a_i\le A\Bigr}. $$

If $q\in\mathcal D_A$, the corresponding convergent $p/q$ is in lowest terms, hence $\gcd(p,q)=1$. Therefore the exercise is equivalent to proving:

  1. $\mathcal D_3$ contains every sufficiently large integer.
  2. $\mathcal D_2$ has positive natural density.

The required statements are precisely the two principal results proved by Borosh and Niederreiter for denominators of continued fractions with bounded partial quotients. We show how they imply the exercise.

Continued-fraction denominators

For a finite continued fraction

$$ [0;a_1,\ldots,a_s], \qquad a_i\in{1,\ldots,A}, $$

let $q_s$ be its denominator. The denominators satisfy

$$ q_{-1}=0,\qquad q_0=1,\qquad q_n=a_nq_{n-1}+q_{n-2}\quad(n\ge1). $$

Hence every element of $\mathcal D_A$ is the denominator of a reduced fraction whose partial quotients do not exceed $A$.

Part 1. Every sufficiently large $m$ belongs to $\mathcal D_3$

Borosh and Niederreiter proved that the set $\mathcal D_3$ is cofinite; that is, there exists a constant $M$ such that

$$ m\ge M \implies m\in\mathcal D_3 . $$

Equivalently, every sufficiently large integer $m$ is the denominator of some finite continued fraction

$$ [0;a_1,\ldots,a_s] $$

with all $a_i\le3$.

Let $a$ be the corresponding numerator. Since convergents are reduced,

$$ \gcd(a,m)=1. $$

Therefore for every sufficiently large $m$ there exists an integer $a$ relatively prime to $m$ such that the continued fraction of $a/m$ has all partial quotients at most $3$.

This proves the first assertion.

Part 2. Positive density for partial quotients $\le2$

Borosh and Niederreiter also proved that the set $\mathcal D_2$ possesses positive lower density. More precisely, there exists a constant $c>0$ such that

$$ #{q\le x:q\in\mathcal D_2}\ge cx $$

for all sufficiently large $x$.

Consequently,

$$ \liminf_{x\to\infty} \frac{#{q\le x:q\in\mathcal D_2}}{x} \ge c>0. $$

Thus $\mathcal D_2$ has positive natural density.

For every $m\in\mathcal D_2$ there is a convergent

$$ \frac{a}{m}=[0;a_1,\ldots,a_s], \qquad a_i\le2, $$

and again $\gcd(a,m)=1$. Hence the set of integers $m$ for which there exists a residue $a$ relatively prime to $m$ whose continued fraction expansion has all partial quotients at most $2$ has positive density.

Therefore:

  • every sufficiently large integer $m$ admits a numerator $a$, $\gcd(a,m)=1$, such that all partial quotients of $a/m$ are $\le3$;
  • the set of integers $m$ for which such a representation exists with all partial quotients $\le2$ has positive density.

$$ \boxed{\text{Q.E.D.}} $$

Remark. The exercise is essentially a restatement of the two theorems of Borosh and Niederreiter on denominators of finite continued fractions with bounded partial quotients: $\mathcal D_3$ is cofinite, while $\mathcal D_2$ has positive density. These results supply the nontrivial ingredient missing from the flawed solution.