Diophantine Approximations

Diophantine Approximations

by Ivan Niven

Paperback

$7.95
View All Available Formats & Editions
Use Standard Shipping. For guaranteed delivery by December 24, use Express or Expedited Shipping.

Product Details

ISBN-13: 9780486462677
Publisher: Courier Corporation
Publication date: 03/14/2008
Series: Dover Books on Mathematics Series
Pages: 80
Product dimensions: 5.30(w) x 8.40(h) x 0.20(d)

Read an Excerpt

Diophantine Approximations


By Ivan Niven

Dover Publications, Inc.

Copyright © 2008 Dover Publications, Inc.
All rights reserved.
ISBN: 978-0-486-16470-0


Contents

Title Page,
Copyright Page,
PREFACE,
NOTATION AND CONVENTIONS,
CHAPTER 1 - The Approximation of Irrationals by Rationals,
CHAPTER 2 - The Product of Linear Forms,
CHAPTER 3 - The Multiples of an Irrational Number,
CHAPTER 4 - The Approximation of Complex Numbers,
CHAPTER 5 - The Product of Complex Linear Forms,
BIBLIOGRAPHY,
Index,


CHAPTER 1

The Approximation of Irrationals by Rationals


1.1. The pigeon-hole principle

Given a real number θ, how closely can it be approximated by rational numbers? To make the question more precise, for any given positive ε is there a rational number a/b within ε of θ, so that the inequality

[absolute value of (θ - a/b)] < ε

is satisfiedθ The answer is yes because the rational numbers are dense on the real line. In fact, this establishes that for any real number θ and any positive e there are infinitely many rational numbers a/b satisfying the above inequality.

Another way of approaching this problem is to consider all rational numbers with a fixed denominator b, where b is a positive integer. The real number θ can be located between two such rational numbers, say

c/b ≤ < C + 1/b,

and so we have |θ - c/b| < 1/b. In fact, we can write

(1)

| θ - a/b| ≤ 1/2b

by choosing a = c or a = c + 1, whichever is appropriate. The inequality (1) would be strict, that is to say, equality would be excluded if θ were not only real but irrational. We shall confine our attention to irrational numbers θ because most of the questions about approximating rationals by rationals reduce to simple problems in linear Diophantine equations.

Now by use of the pigeon-hole principle (sometimes called the box principle) we can improve inequality (1) as in the following theorem. The pigeon-hole principle states that if n + 1 pigeons are in n holes, at least one hole will contain at least two pigeons.

THEOREM 1.1. Given any irrational number θ and any positive integer m, there is a positive integer b θ m such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The symbol a here denotes the integer nearest to bθ, so that the equality? bθ = | bθ - a| holds by the definition of the symbolism.

Proof: Consider the m + 2 real numbers

(2)

0, 1, θ - [θ], 2θ - [2θ, ..., mθ - [mθ]

lying in the closed unit interval. Divide the unit interval into m + 1 subintervals of equal length

(3)

j/m +1 ≤ x < j + 1/m + 1, j = 0, 1, 2, ..., m.

Since θ is irrational, each of the numbers (2) except 0 and 1 lies in the interior of exactly one of the intervals (3). Hence two of the numbers (2) lie in one of the intervals (3); thus there are integers k1, k2, h1, and h2 such that

We may presume that m? k2 > k1 0. Defining b = k2 - k1, a = h2 - h1, we have established the theorem.

Since (m + 1)-1< b-1, Theorem 1.1 implies that? bθ < b-1. Furthermore, this inequality is satisfied by infinitely many positive integers b for the following reason. Suppose there were only a finite number of such integers, say b1, b2,?, br with

||bjθ|| < bj-1 for j = 1, 2, ..., r.

Then choose the integer m so large that

1/m < ||bjθ||

holds for every j = 1, 2, ?, r. Then apply Theorem 1.1 with this value of m, and note that this process yields an integer b such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence b is different from each of b1, b2, ..., br. Also ?bθ? < b- 1, so there can be no end to the integers satisfying this inequality. The following corollary states what we have just proved.

COROLLARY 1.2. Given any irrational number θ, there are infinitely many rational numbers a/b, where a and b > 0 are integers, such that

(4)

|θ - a/b| < 1/b2.

Note that this result is a considerable improvement over inequality (1). It is natural to ask whether Corollary 1.2 can also be improved, for instance, by the replacement of 1/b2 by 1/b3. It cannot; in fact, Corollary 1.2 becomes false if 1/b2 is replaced by 1/b2+e for any positive ε. Nevertheless, although the exponent cannot be improved, this corollary can be strengthened by a constant factor in (4). Specifically 1/b2 can be replaced by, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and no larger constant can be used than [square root of 5]. This result, due to Hurwitz, is proved in the next section.


1.2. The theorem of Hurwitz

We first prove a preliminary result about Farey sequences. For any positive integer n, the Farey sequence Fn is the sequence, ordered in size, of all rational fractions a/b in lowest terms with 0 < b ? n. For example,

F7: ..., -1/6, -1/7, 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, ....

Of the many known properties of Farey sequences, only two are needed for our purposes, as follows.

THEOREM 1.3. If a/b and c/d are two consecutive terms in Fn, then, presuming a/b to be the smaller, bc - ad = 1. Furthermore, if θ is any given irrational number, and if r is any positive integer, then for all n sufficiently large the two fractions a/b and c/d adjacent to θ in Fn have denominators larger than r, that is, b > r and d > r.

Proof: The proof of the first part is by induction on n. If n = 1, then b = 1, d = 1, and c = a + 1, so that

bc - ad = a + 1 - a = 1.

Next we suppose that the result holds for Fn, and prove it for Fn+1. Let a/b and c/d be adjacent fractions in Fn. First we note that b + d? n + 1, since otherwise the fraction (a + c)/(b + d), reduced if necessary, would belong to Fn. But this is not possible since

a/b < a + c/b + d < c/d.

Now with respect to Fn+1 there are two possibilities: first that a/b and c/d are adjacent, and the second that some fraction or fractions lie between. In the first case there is nothing to prove because bc - ad = 1 by the induction hypothesis. In the second case, any such fraction, being in Fn+1 but not in Fn, has denominator n + 1. Denoting the fraction by k/(n + 1), we write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where u = c(n + 1) - dk? 1, v = bk - a(n + 1) ? 1. Our aim is to establish that u = 1 and v = 1. If on the contrary u > 1 or υ > 1 or both, then it follows that

1/bd > 1/d(n + 1) + 1/b(n + 1), n + 1 > b +d,

which is contrary to what was established earlier. Hence u = 1 and v = 1, and so

c/d - k/n + 1 = 1/d(n + 1), k/n + 1 - a/b = 1/b(n+1).

Finally, we observe that at most one fraction can occur between a/b and c/d in Fn+1. For if there were another fraction besides k/(n + 1) it must have the form h/(n + 1). Then the preceding argument implies that

h/n + 1 - a/b = k/n + 1 = 1/b(n + 1),

and hence

h/n + 1 - a/b = k/n + 1 - a/b; h = k

This completes the proof of the first part of Theorem 1.3.

To prove the second part, let m1, m2, ..., mr denote the integers nearest to θ, 2θ, ..., rθ. Choose n sufficiently large so that for every j= 1,2, ..., r,

1/n < |θ - mi/j|.

If q is any integer, then for every j = 1, 2, ?, r,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now the difference between adjacent fractions in Fn does not exceed 1/n, because Fn contains all fractions with denominator n, of which some are perhaps in reduced form. Hence if a/b and c/d are the fractions adjacent to θ in Fn, we see that

|θ - a/b| < |c/d - a/b| ≤ 1/n;

and

|θ - c/d| < |c/d - a/b| ≤ 1/n;

A comparison of these with the previous inequalities establishes that b > r and d > r, and the proof of Theorem 1.3 is complete.

Another result we shall need is the following.

LEMMA 1.4. There are no positive integers x and y which satisfy simultaneously the inequalities

(5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: If there were such integers, then from (5) it would follow that

0 ? x2 + y2 -[square root of 5] xy and 0 ? (2 -[square root of 5])(x2 + xy) + y2.

Adding these, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is false for rational x/y.

We are now in a position to prove a basic result (Hurwitz, 1891).

THEOREM 1.5. Given any irrational number θ there exist infinitely many rational numbers h/k in lowest terms such that

(6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Furthermore, this inequality is best possible in the sense that the result becomes false if [square root of 5] is replaced by any larger constant.

Proof: Locate θ between two consecutive fractions of the Farey sequence Fn, say a/b < θ < c/d with b and d positive. We consider two cases according to whether θ is greater or less than (a + c)/(b + d). In case θ > (a + c)/(b + d), we prove that not all three of the inequalities

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

can hold. For if we add the first and third of these, and then the second and third, we get (5) with x = d and y = b.

In the other case, θ < (a + c)/(b + d), we prove that not all three of the inequalities

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

can hold. For if we add the first and third of these, and then the first and second, we get (5) with x = b and y = d.

Hence the inequality (6) holds with h/k replaced by at least one of a/b, c/d, and (a + c)/(b + d). To prove that there are infinitely many solutions of (6) we argue as follows. Suppose there were only a finite number of solutions h/k, and we let r denote the maximum denominator among these solutions. Then the second part of Theorem 1.3 guarantees that for sufficiently large n the consecutive fractions a/b and c/d adjacent to θ in Fn have denominators greater than r. This process then gives a solution h/k to (6) of one of the three forms a/b, c/d, or (a + c)/(b + d). Now a/b and c/d are in lowest terms by definition of Farey sequences. Also (a + c)/b + d) is in lowest terms because

c(b+d) - d(a+c) = bc - ad = 1,

so that any common divisor of a + c and b + d is a divisor of 1. Thus the solution of (6) so obtained is in lowest terms and its denominator exceeds those of previously obtained solutions.

To complete the proof of the theorem we must show that [square root of 5] is the best possible constant. Before doing that, we remark on the proof thus far. The proof that (6) has infinitely many solutions has a slightly artificial aspect in that the inequalities (5) seem to have no motivating source. It might appear that some variation on the inequalities (5) would lead to better results. This is not the case, as we now show by establishing that the constant [square root of 5] in (6) is best possible.

Let θ0 and θ1, be defined by

θ0 = 1 + [square root of 5]/2,

so that

(x - θ0)(x - θ1) = x2 - x - 1.

For any integers h and k, with k > 0, we see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Also θ1 = θ0 - [square root of 5] and so

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

An application of the triangle inequality gives

(7)

1/k2 ≤ [absolute value of (h/k - θ0)] x {[absolute value of (h/k - θ0)] + [square root of 5]}

Now if for some positive number β there are infinitely many hj/kj, j = 1, 2, 3, ..., such that

(7a)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then kj -> ∞ as j -> ∞. Furthermore, from (7) we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence [square root of 5] is the largest possible constant in (6).

Thus the theorem is proved, and we note that the exponent 2 on the k2 in (6) is best possible. That is, if γ is any fixed real number > 2, and c is any positive constant, there are only finitely many h/k satisfying

| θ0 - h/k| < 1/ckγ

For if not, we could obtain infinitely many h/k satisfying (7a) with, say β = 3.

Next we formulate a simple consequence of Theorem 1.5.

COROLLARY 1.6. Given any real numbers a1, a2, b1, b2 with Δ[not equal to] 0, where Δ = |a1b2 - a2b1|, and given any positive ε, there are infinitely many pairs of integers h, k such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: If any one of a1, a2, b1, b2 is zero, or if a1/b1 or a2/b2, is rational, the result is immediate. So suppose that a1/b1 is irrational. Then let - a1/b1 play the role of θ in Theorem 1.5 and let h/k be any one of the rational numbers in that result. Define δ by

h/k + a1/b1 = δk2

so that |δ| < 5-1/2. Thus we have a1k + b1h = δb1/k and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This proves the corollary, because |b1b2|/k2 can be made arbitrarily small by taking k sufficiently large.


1.3. Asymmetric approximation

The inequality of Theorem 1.5 can be written in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that the rational numbers h/k are allowable in symmetric fashion about the irrational θ. Next we prove an asymmetric result.

THEOREM 1.7. Given any irrational number θ and any nonnegative real number τ, there exist infinitely many rational numbers h/k such that

(8)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Furthermore, the statement holds if θ - h/k in (8) is replaced by h/k - θ.

Note that Theorem 1.5 is a special case of this result, obtained by setting τ = 1. We note also that the second sentence of Theorem 1.7 follows at once from the first; for if the first sentence is applied to the irrational number -θ, the second part follows.

To prove Theorem 1.7 we begin with a preliminary result.

LEMMA 1.8. Let θ be any irrational number, and t any nonnegative real number. Let a/b and c/d be rational numbers with positive denominators such that bc - ad = 1 and

(9)

a/b < a + c/b + d < θ < c/d.

Then (8) holds with h/k replaced by at least one of a/b, (a + c)/(b + d), and c/d.

Proof: The argument is analogous to that in Theorem 1.5. Define λ and μ by

λ = (1 + 4τ)-1/2 and μ = τ(1 + 4τ)-1/2,

so that μ = (1 - λ2)/4λ and 0 < λ ? 1. Suppose that the lemma is false, so that

(10)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Adding the first and third of these inequalities and also the second and third, we conclude that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(11)

Adding these, we obtain

(12)

2λb2 + (2λ - 2)bd + (λ + 2μ - 1)d2 ≤ 0.

This quadratic form in b and d is seen to have discriminant zero since λ2 + 4λμ = 1. Hence the quadratic form is a perfect square. In fact, if (12) is multiplied by the positive number 2λ, the result can be written

{2λb + (λ - 1)d}2 ? 0.

Equality must hold here since the square of a real number cannot be negative. It follows that equality must hold throughout all the relations (12), (11), and (10). Furthermore, we see that

2λb + ([lambda - 1)d = 0, λ = d/d + 2b,

so that λ is rational. But the third relation in (10) is now

c/d - θ = λ/d2

This implies that θ is rational, which is a contradiction.

Thus Lemma 1.8 is proved, which we now use to prove Theorem 1.7.

First let a1/b1 and c1/d1, be the two consecutive fractions of the Farey series F1 between which θ lies. Then b1c1 - a1d1 = 1 by Theorem 1.3. In case the inequalities

a1/b1< a1 + c1/b1 + d1< θ < c1/d1

hold, then we apply Lemma 1.8 with a/b and c/d replaced by a1/b1, and c1/d1. Thus we would have one solution of (8). On the other hand, in case

a1/b1< θ < a1 + c1/b1 + d1< c1/d1

let the positive integer j be chosen so that

(13)

a1/b1< (j + 1)a1 + c1/(j + 1)b1 + d1< θ < ja1 + c1/jb1 + d1

This can be done because (ja1 + c1)/(jb1 + d1) tends to a1/b1 as j increases indefinitely. Then we can apply Lemma 1.8 with a/b and c/d replaced by a1/b1 and (ja1 + c1)/(jb1 + d1). The conditions (9) of the lemma are replaced by (13), and the condition bc - ad = 1 holds because

b1(ja1 + c1) - a1(jb1 + d) = b1c1 - a1d1, = 1.

Thus in this case also we have one solution of (8). Let h1/k1 denote the solution of (8) obtained by use of F1.

Next the second part of Theorem 1.3 is applied to choose n sufficiently large so that the two fractions of Fn adjacent to θ have denominators larger than k1. Thus we get a2/b2 and c2/d2 in Fn with

a2/b2< θ c2/d2

Then we repeat the preceding argument. That is, if

a2/b2< a2 + c2/b2 + d2< θ < c2/d2

we apply Lemma 1.8 directly. Otherwise we choose j so that

a2/b2< (j + 1)a2 + c2/(j + 1)b2 + d2< θ < ja2 + c2/jb2 + d2

In one case or the other we get a solution h2/k2 of (8) with k2 equal to one of

b2, d2, b2 + d2, jb2 + d2, (j + 1)b2 + d2.

It may be noted that all the fractions in the preceding inequalities are in lowest terms. For example,

b2(ja2 + c2) - a2(jb2 + d2) = b2c2 - a2d2 = 1,

so that the greatest common divisor of ja2 + C2 and jb2 + d2 is 1. Hence the solution h2/k2 of (8) is different from the first solution h1/k1.

Since this process can be repeated indefinitely, giving a new solution of (8) each time, the theorem is proved.

It might appear from an examination of the proof that a stronger or different result might be obtained by some refinement of the procedure leading from (11) to (12). That is, instead of simply adding the inequalities (11), what would happen if we used weighting factors in the addition process It is not difficult, however, to prove that nothing new can be obtained by such a procedure.

The following consequence of Theorem 1.8 is obtained by taking τ = 0.

COROLLARY 1.9. Given any irrational θ there are infinitely many rationals h/k such that

- 1/k2< θ - h/k < 0,

and also infinitely many rationals h/k such that

0 < θ - h/k < 1/k2.


1.4. Further results

The method of Section 1.1 can be extended to the problem of simultaneous approximation of several irrational numbers and the following result can thus be obtained at once. Given any n real numbers θ1 θ2, ?, θn, there exist infinitely many sets of integers (a1 a2, ?, an, b) with b positive such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all j = 1, 2, 3, ?, n. But even for n = 2 there is no analogue to Theorem 1.5 (Hurwitz, 1891) giving the best possible constant in the inequalities. For a general statement on this topic, see Davenport (1954a), and also Davenport (1954b).

The proof of Theorem 1.5 in Section 1.2 was suggested by work of Khintchine (1935) and LeVeque (1953). Theorem 1.7 in Section 1.3 is due to Segre (1945); the proof given here is by Niven (1962).

As an example of another result on asymmetric approximation we cite the following theorem of Robinson (1947): Given any irrational θ and any positive ε there are infinitely many rationals a/b such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 1.9, a standard result in the continued fraction approach to irrational numbers, implies Corollary 1.2, but not conversely. Eggan and Niven (1961) have pointed out that Corollary 1.9 is best possible in the following sense: Given any γ > 1 there are irrational numbers θ such that

0 < θ - a/b < 1/γb2

has no solutions in rational numbers a/b; a similar result holds for approximation with θ - a/b < 0. For other work on asymmetric or unsymmetric approximation see Olds (1946), Negoescu (1948), Robinson (1948), Tornheim (1955a), and Eggan (1961).

Another variation on Theorem 1.5 arises if the rational numbers a/b are restricted in some way, for example, if a and b must both be odd or if a and b must satisfy some more general congruence conditions. Results along these lines have been obtained by Scott (1940), Robinson (1940), Oppenheim (1941), Hartman (1949), Koksma (1951), Tornheim (1955b), and Eggan (1961).

Theorem 1.5 is an assertion about every irrational number θ. If the irrational number ([square root of 5] - 1)/2 and all numbers equivalent to it (in a sense explained in the next sentence) are deleted, then to each remaining irrational θ there are infinitely many rational numbers h/k satisfying

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Two real numbers θ and θ' are said to be equivalent if there exist integers p, q, r, s such that

θ' = pθ + q/rθ + s with ps - qr = [+ or -] 1.

Note that this is a so-called equivalence relation, and that the set of numbers equivalent to a fixed θ is countable. If next the number [square root of 2] and all equivalent numbers are also deleted from the set of irrational numbers, then to each remaining irrational number θ there are infinitely many rational numbers h/k satisfying

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This process can be continued, giving the Markoff chain of constants [square root of 5], [square root of 8], [square root of 221]/5, [square root of 1517]/13, ?, with limit 3. This theory is given in full detail in Cassels (1957, Chapter 2).


(Continues...)


Excerpted from Diophantine Approximations by Ivan Niven. Copyright © 2008 Dover Publications, Inc.. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Table of Contents


Notation and Conventions
1. The Approximation of Irrationals by Rationals
2. The Product of Linear Forms
3. The Multiples of an Irrational Number
4. The Approximation of Complex Numbers
5. The Product of Complex Linear Forms
Bibliography
Index

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews