Some Facts About Continued Fractions

That Should Be Better Known

J. O. Shallit

University of Waterloo

I. Introduction.

In this report I will give proofs of some simple theorems concerning continued fractions that are known to the cognoscenti, but for which proofs in the literature seem to be missing, incomplete, or hard to locate. In particular, I will give two proofs of the following “folk theorem”: if θ is an irrational number whose continued fraction has bounded partial quotients, then any non-trivial linear fractional transformation of θ also has bounded partial quotients. The second proof is of interest because it uses the connection between continued fractions and finite automata first enunciated by G. N. Raney [R].

I will assume that the reader knows basic facts about continued fractions, at the level of [HW, Chapter X].

Note to the reader: It is intended that this report will eventually form a part of a longer article with the same name, written in collaboration with A. J. van der Poorten.

II. Some Notation.

In this report, θ denotes an irrational number. We let

θ = [a_{0}, a_{1}, a_{2}, …]

be the simple continued fraction expansion of θ. We write

\frac{p_{n}}{q_{n}} = [a_{0}, a_{1}, …, a_{n}],

the n-th convergent. We define

a′_{n} = [a_{n}, a_{n+1}, a_{n+2}, …],

the n-th complete quotient. We also define

∥θ∥ = min(θ − ⌊θ⌋, ⌈θ⌉ − θ),

Typeset by AMS-TEX 2 J. O. SHALLIT

Research supported in part by a grant from NSERC .

the distance between θ and the nearest integer. Finally, we define

K(θ) = sup_{k≥1} a_{k},

the largest partial quotient in the continued fraction for θ. If K(θ) < ∞, we say θ has bounded partial quotients.

III. Badly approximable numbers

In this section, we obtain a precise relation between K(θ) and the degree to which θ can be approximated by rationals. Theorem 1.

Let r ≥ 1, and suppose q∥qθ∥ ≥ \frac{1}{r} for all q ≥ 1. Then K(θ) < r. Proof.

Let p_{n}/q_{n} be a convergent to θ with n ≥ 1. Since

|\frac{p_{n}}{q_{n}} − θ| < \frac{1}{a_{n+1}q_{n}^{2}} ,

(see, e.g. [HW, Thm. 171]), we see

q_{n}|p_{n} − q_{n}θ| < \frac{1}{a_{n+1}} .

Now clearly ∥q_{n}θ∥ ≤ |p_{n} − q_{n}θ|, so

\frac{1}{r} ≤ q_{n}∥q_{n}θ∥ ≤ q_{n}|p_{n} − q_{n}θ| < \frac{1}{a_{n+1}} ,

and thus a_{n+1} < r for all n ≥ 0, and hence K(θ) < r. Theorem 2.

Let r ≥ 1 and suppose K(θ) ≤ r. Then

q∥qθ∥ ≥ \frac{1}{r + 2}

for all q ≥ 1. Proof.

We prove the contrapositive. Suppose there exists a q ≥ 1 such that

q∥qθ∥ < \frac{1}{r + 2}.

Let p be an integer such that ∥qθ∥ = |qθ − p|. Then q|qθ − p| < \frac{1}{r+2}. Thus

|θ − \frac{p}{q}| < \frac{1}{(r + 2)q^{2}} < \frac{1}{2q^{2}} ,

from which it follows (see, e.g. [HW, Thm. 184]) that p/q is a convergent to θ, say p/q = p_{n}/q_{n}. Thus p = ap_{n}, q = aq_{n} for some integer a ≥ 1.

Now from [HW, Thm. 163], we have

|q_{n}θ − p_{n}| = \frac{1}{a′_{n+1}q_{n} + q_{n−1}} .

Hence

\frac{1}{r + 2} > q∥qθ∥ = q|qθ − p|

= aq_{n}|aq_{n}θ − ap_{n}| ≥ q_{n}|q_{n}θ − p_{n}|

≥ \frac{1}{a′_{n+1} + \frac{q_{n−1}}{q_{n}}}

≥ \frac{1}{(a_{n+1} + 1) + 1}.

Thus we conclude a_{n+1} > r and so K(θ) > r.

A weaker form of Theorem 2, with a worse constant, was given by Hardy and Wright [HW, Thm. 187].

Theorems 1 and 2 above were essentially proved by W. M. Schmidt [S, pp. 22-23], but the proof provided is a little vague in spots. One can also deduce the theorems by filling in the details in [B, p. 47].

IV. Bounded partial quotients and linear fractional transformations

Definition.

We say θ is of type < r if q∥qθ∥ ≥ \frac{1}{r} for all integers q ≥ 1.

Theorem 3.

Let a, b be integers with a ≥ 1, |b| ≥ 1. If θ is of type < M, then \frac{a}{b}θ is of type < |ab|M.

Proof.

We prove the contrapositive. Assume

q∥q \frac{a}{b}θ∥ < \frac{1}{|ab|M}

4 J. O. SHALLIT

for some q ≥ 1.

Now there exists an integer p such that ∥q \frac{a}{b}θ∥ = |q \frac{a}{b}θ − p|. Thus

q |q \frac{a}{b}θ − p| < \frac{1}{|ab|M} ,

and so, multiplying by |ab|, we get

qa|qaθ − pb| < \frac{1}{M} .

Hence qa∥qaθ∥ < \frac{1}{M}. Corollary 4.

K(\frac{a}{b}θ) < |ab|(K(θ) + 2). Theorem 5.

Let a, b be integers with |a| ≥ 1, b ≥ 1. If θ is of type < M, then θ + \frac{a}{b} is of type < b^{2}M. Proof.

We prove the contrapositive. Assume that

q∥q(θ + \frac{a}{b})∥ < \frac{1}{b^{2}M}

for some q ≥ 1.

Then there exists an integer p such that

∥q(θ + \frac{a}{b})∥ = |q(θ + \frac{a}{b}) − p|.

Thus

q |q(θ + \frac{a}{b}) − p| < \frac{1}{b^{2}M}

and so, multiplying by b^{2}, we get

qb|qbθ + qa − pb| < \frac{1}{M} .

Hence qb∥qbθ∥ < \frac{1}{M}. Corollary 6.

K(θ + \frac{a}{b}) < b^{2}(K(θ) + 2).

I have not been able to find these results given explicitly in the literature. Theorems similar to Theorems 3 and 5 were given by Cusick and Mendès France [CMF]. Instead of studying sup_{q≥1} q∥qθ∥, they studied lim sup_{q→∞} q∥qθ∥, which is somewhat more natural. Also see Perron [P].

Chowla [C] proved in 1931 that K(\frac{a}{b}θ) < 2ab(K(θ) + 1)^{3}, a bound much weaker than that obtained above.

Theorem 7.

K(\frac{1}{θ}) ≤ \{ \begin{matrix}K(θ), & if 0 < θ < 1 \\ max(K(θ), ⌊θ⌋), & if θ > 1 \\ K(θ) + 1, & if −1 < θ < 0 \\ max(K(θ) + 2, −⌊θ⌋ − 2), & if θ < −1. \end{matrix}

Proof.

As in [K, Ex. 4.5.3.10], we see that

(a) If 0 < θ < 1, then θ = [0, a_{1}, a_{2}, …] and 1/θ = [a_{1}, a_{2}, …].

(b) If θ > 1, then θ = [a_{0}, a_{1}, …] and 1/θ = [0, a_{0}, a_{1}, …].

(c) If −1/2 < θ < 0, then θ = [−1, 1, a_{2}, a_{3}, a_{4}] and 1/θ = [−(a_{2} + 2), 1, a_{3} − 1, a_{4}, …]. (Note: this collapses to [−(a_{2} + 2), a_{4} + 1, a_{5}, …] if a_{3} = 1.)

(d) If −1 < θ < −1/2, then θ = [−1, a_{1}, a_{2}, a_{3}, …], where a_{1} ≥ 2, and 1/θ = [−2, 1, a_{1} − 2, a_{2}, …]. (Note: this collapses to [−2, a_{2} + 1, a_{3}, …] if a_{1} = 2.)

(e) If θ < −1, then θ = [a_{0}, a_{1}, a_{2}, …], where a_{0} ≤ −2, and 1/θ = [−1, 1, −(a_{0} + 2), 1, a_{1} − 1, a_{2}, …]. (Note: this collapses to [−1, 2, a_{1} − 1, a_{2}, …] if a_{0} = −2 and a_{1} ≥; to [−1, 1, −(a_{0} + 2), a_{2} + 1, a_{3}, …] if a_{1} = 1 and a_{0} ≤ −3, and to [−1, a_{2} + 2, a_{3}, …] if a_{0} = −2 and a_{1} = 1.)

Theorem 8.

Let a, b, c, d be integers with ad − bc ≠ 0. Then θ has bounded partial quotients iff \frac{aθ+b}{cθ+d} has bounded partial quotients.

Proof.

⇒: If c = 0, this follows from Corollaries 4 and 6. If c ≠ 0, then

\frac{aθ + b}{cθ + d} = \frac{b − \frac{ad}{c}}{cθ + d} + \frac{a}{c},

and the result follows from Corollaries 4 and 6.

⇐: Let τ = \frac{aθ+b}{cθ+d}. Then θ = \frac{dτ−b}{−cτ+a}, and the result follows from the argument above.

I do not know any proof of Theorem 8 in the literature.

V. Another proof using Raney’s theorem.

In this section, I show how to obtain Theorem 8 directly from the continued fraction expansion of θ, using a theorem of Raney [R]. This idea was suggested to me by J. C. Lagarias. For those who are familiar with formal languages, the proof will recall the proof of the so-called “pumping lemma’ for regular sets; see [HU].

Recall the LR-expansion of an irrational number θ. If

θ = [a_{0}, a_{1}, a_{2}, …],

then its LR-expansion is

R^{a_{0}}L^{a_{1}}R^{a_{2}}L^{a_{3}} · · · .

The letters L and R are shorthand for the matrices

L = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) and R = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) .

Raney proved that the LR-expansion of τ = \frac{aθ+b}{cθ+d} can be deduced from that of θ with the aid of a finite-state transducer. The transitions of this transducer correspond to certain products of matrices. When we write an expression such as

(1)  ARL = LR^{3}B,

we mean that this transducer, in state A, accepts the string RL as input and outputs LR^{3}, and then changes to state B. The expression (1) can also be viewed simply as an identity on 2 × 2 matrices; e.g. where

A = ( \begin{matrix}2 & 1 \\ 1 & 3 \end{matrix} ) and B = ( \begin{matrix}5 & 0 \\ 0 & 1 \end{matrix} ) .

Note that all state matrices are invertible.

In what follows, we regard an expression such as LRL both as a string of length 3, and a certain 2 × 2 matrix representing a product of the matrices L and R. In particular, we use |W | to denote the length, or number of symbols, in the string W.

Second Proof of Theorem 8.

Consider the transducer mapping the LR-expansion of θ to that of τ. Let m denote the maximum number of R’s in any string output by a transition. Let the transducer have s states.

Suppose θ has partial quotients bounded by B, and ad − bc ≠ 0. Assume, contrary to what we want to prove, that τ = \frac{aθ+b}{cθ+d} has unbounded partial quotients. Then its LR-expansion must contain arbitrarily long strings of R’s or L’s (not necessarily both). Without loss of generality, assume it contains arbitrarily long strings of R’s. Thus we may choose a substring in the LR-expansion of τ of at least B(m + 3)(s + 1) consecutive R’s. Partition this string into s + 1 groups of B(m + 3) R’s, as follows:

\underbrace{\overbrace{RR ⋯ R}^{B(m+3)} \overbrace{RR ⋯ R}^{B(m+3)} ⋯ \overbrace{RR ⋯ R}^{B(m+3)}}_{s+1 groups}

Consider the first group, and the corresponding part of the LR-expansion of θ that is transduced to get this string of B(m + 3) R’s. Partition it into sections according to the states S_{1}, S_{2}, …, S_{k+1} encountered in the transduction:

\underbrace{RR ⋯ R} ^{S_{1}} \underbrace{RR ⋯ R}_{i_{1}}^{W_{1}} ^{S_{2}} \underbrace{RR ⋯ R}_{i_{2}}^{W_{2}} ^{S_{3}} ⋯ \underbrace{RR ⋯ R}_{i_{k}}^{W_{k}} ^{S_{k+1}} \underbrace{RR ⋯ R}

From the definition of the transducer, we have

S_{1}W_{1} = R^{i_{1}}S_{2}
S_{2}W_{2} = R^{i_{2}}S_{3}
⋮
S_{k}W_{k} = R^{i_{k}}S_{k+1}.

I claim that the words W_{j} cannot consist of all L’s or all R’s. For if they did, then since

|W_{1}W_{2} ⋯ W_{k}| ≥ B(m + 1),

the LR-expansion of θ would contain at least B \frac{m+1}{m} consecutive L’s or R’s, a contradiction.

In the same manner, we can list the first state of the transducer encountered in each of the s + 1 groups. Since the transducer has precisely s distinct states, at least one state (call it B_{1}) must be repeated. Thus we have

B_{1}X_{1} = R^{j_{1}}B_{2}
B_{2}X_{2} = R^{j_{2}}B_{3}
⋮
B_{s+1}X_{s+1} = R^{j_{s+1}}B_{1},

and the string X_{1}X_{2} ⋯ X_{s+1} contains at least one L and one R. Thus we see

B_{1}X_{1}X_{2} ⋯ X_{s+1} = R^{j_{1}}B_{2}X_{2} ⋯ X_{s+1}
= R^{j_{1}}R^{j_{2}}B_{3}X_{3} ⋯ X_{s+1}
= ⋯ = R^{j_{1}}R^{j_{2}} ⋯ R^{j_{s+1}}B_{1}.

Let X = X_{1}X_{2} ⋯ X_{s+1} and j = j_{1} + j_{2} + ⋯ + j_{s+1}. Considered as a string, X contains at least one L and one R. Therefore, considered as a matrix, all of X’s entries are ≥ 1. On the other hand,

R^{j} = ( \begin{matrix}1 & j \\ 0 & 1 \end{matrix} ) .

Letting

B_{1} = ( \begin{matrix}e & f \\ g & h \end{matrix} ) ,

we have

( \begin{matrix}e & f \\ g & h \end{matrix} ) ( \begin{matrix}x_{11} & x_{12} \\ x_{21} & x_{22} \end{matrix} ) = ( \begin{matrix}1 & j \\ 0 & 1 \end{matrix} ) ( \begin{matrix}e & f \\ g & h \end{matrix} ) .

Hence

gx_{11} + hx_{21} = g
hx_{12} + hx_{22} = h.

Since x_{11}, x_{12}, x_{21}, x_{22} ≥ 1, we have g = h = 0. But then det(B_{1}) = 0, which contradicts the fact that all the transition matrices are invertible. This contradiction (essentially) completes the proof.

I say “essentially” because there is one small point that remains to be cleared up: Raney’s transducer does not work for arbitrary matrices, but only for the so-called “doublybalanced” ones. As Raney shows, however, the general linear fractional transformation can be mapped into the doubly-balanced case by changing a finite number of terms at the beginning of the LR-expansion for θ. Clearly this does not change the (supposed) unboundedness of the partial quotients for τ. Now we are really done with the proof.

References

[B]. A. Baker, A Concise Introduction to the Theory of Numbers, Cambridge University Press, 1984.

[C]. S. D. Chowla, Some problems of diophantine approximation (I), Math. Zeitschrift 33 (1931), 544–563.

[CMF]. T. W. Cusick and M. Mendès France, The Lagrange spectrum of a set, Acta Arith. 34 (1979), 287–293.

[HW]. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1985.

[HU]. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

[K]. D. E. Knuth, The Art of Computer Programming, V. II (Seminumerical Algorithms), Addison-Wesley, 1981.

[P]. O. Perron, Über die Approximation irrationaler Zahlen durch rationale, Sitz. Heidelberg. Akad. Wiss. XII A (4. Abhundlung) (1921), 3–17.

[R]. G. N. Raney, On continued fractions and finite automata, Math. Annalen 206 (1973), 265-283.

[S]. W. Schmidt, Diophantine Approximation, Lecture Notes in Mathematics, vol. 785, Springer-Verlag, 1980.

J. O. Shallit Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1 Canada

E-mail: shallit@graceland.waterloo.edu