Math 115. Slides from the Lecture of November 29

Approximation to Irrational Numbers

Throughout today’s class:

ξ is an irrational number and ⟨a_{0}, a_{1}, … ⟩ is its simple continued fraction expansion.

Also:

h_{−2} = 0 , h_{−1} = 1 , h_{i} = a_{i}h_{i−1} + h_{i−2}  for all i ≥ 0
k_{−2} = 1 , k_{−1} = 0 , k_{i} = a_{i}k_{i−1} + k_{i−2}

Theorem 7.11. For all n ≥ 0 ,

|ξ − \frac{h_{n}}{k_{n}} | < \frac{1}{k_{n}k_{n+1}}  and  |k_{n}ξ − h_{n}| < \frac{1}{k_{n+1}} .

Proof. The first inequality holds because

|ξ − \frac{h_{n}}{k_{n}} | = |ξ − r_{n}| < |r_{n+1} − r_{n}| = \frac{1}{k_{n}k_{n+1}} .

The second inequality follows from the first by multiplying both sides by k_{n}. □

Corollary. |ξ − \frac{h_{n}}{k_{n}} | < \frac{1}{k_{n}^{2}} for all n ≥ 0 .

Proof. Indeed, k_{n+1} ≥ k_{n} for all n ≥ 0 . □

Theorem 7.13. Let a/b be a rational number (with a, b ∈ ℤ and b > 0 ).

(a). If n > 0 and |ξ − \frac{a}{b}| < |ξ − r_{n}| then b > k_{n}

(b). If n ≥ 0 and |bξ − a| < |k_{n}ξ − h_{n}| then b ≥ k_{n+1} .

Proof. We first show that (b) implies (a) by showing the contrapositive. Suppose (a) is false. Then:

(i) n > 0 , (ii) |ξ − \frac{a}{b}| < |ξ − r_{n}| , and (iii) b ≤ k_{n} .

Then (i) implies n ≥ 0 , and (ii) and (iii) imply:

|bξ − a| = b |ξ − \frac{a}{b}| < b|ξ − r_{n}| ≤ k_{n} |ξ − \frac{h_{n}}{k_{n}} | = |k_{n}ξ − h_{n}| ,

yet b ≤ k_{n} < k_{n+1} (by (iii) and (i)), so (b) is false.

To show (b), we prove the contrapositive. Assume that n ≥ 0 and b < k_{n+1} . First, we look for a rational number r such that

\frac{h_{n+1}r + h_{n}}{k_{n+1}r + k_{n}} = f_{n+2}(r) = \frac{a}{b} .

Letting r = y/x, this leads to equations

\begin{matrix}h_{n}x + h_{n+1}y = a \\ k_{n}x + k_{n+1}y = b \end{matrix} [ \begin{matrix}h_{n} & h_{n+1} \\ k_{n} & k_{n+1} \end{matrix} ] [ \begin{matrix}x \\ y \end{matrix} ] = [ \begin{matrix}a \\ b \end{matrix} ] .

Let M = [ \begin{matrix}h_{n} & h_{n+1} \\ k_{n} & k_{n+1} \end{matrix} ]. We know that det M = ±1 , so M^{−1} has integer entries, and

[ \begin{matrix}x \\ y \end{matrix} ] = M^{−1} [ \begin{matrix}a \\ b \end{matrix} ], so there is a unique solution (x, y) , and x, y ∈ ℤ.

Claim. x ≠ 0 , and x > 0 ⟺ y ≤ 0 .

Proof.

Case I. If y ≤ 0 , then k_{n}x = b − k_{n+1}y ≥ b > 0 , so x > 0 .

Case II. If y > 0 , then b < k_{n+1} ≤ k_{n+1}y, so k_{n}x = b − k_{n+1}y < 0 ; therefore x < 0 . □

Now since ξ is between r_{n} and r_{n+1} , k_{n}ξ − h_{n} and k_{n+1}ξ − h_{n+1} have opposite signs. Therefore x(k_{n}ξ − h_{n}) and y(k_{n+1}ξ − h_{n+1}) are either both ≥ 0 or both ≤ 0 .

Adding them gives

x(k_{n}ξ − h_{n}) + y(k_{n+1}ξ − h_{n+1}) = (k_{n}x + k_{n+1}y)ξ − (h_{n}x + h_{n+1}y) = bξ − a ;

therefore

|bξ − a| = |x(k_{n}ξ − h_{n}) + y(k_{n+1}ξ − h_{n+1})|

=^{!!} |x(k_{n}ξ − h_{n})| + |y(k_{n+1}ξ − h_{n+1})|

≥ |x(k_{n}ξ − h_{n})|

≥ |k_{n}ξ − h_{n}| . □