Rational approximation
Contents
[hide]Introduction
The main theme of this article is the question how well a given real number can be approximated by rational numbers. Of course, since the rationals are dense on the real line, we, surely, can make the difference between and its rational approximation as small as we wish. The problem is that, as we try to make closer and closer to , we may have to use larger and larger and . So, the reasonable question to ask here is how well can we approximate by rationals with not too large denominators.
Trivial theorem
Every real number can be approximated by a rational number with a given denominator with an error not exceeding .
Proof
Note that the closed interval has length and, therefore, contains at least one integer. Choosing to be that integer, we immediately get the result.
So, the interesting question is whether we can get a smaller error of approximation than . Surprisingly enough, it is possible, if not for all , then, at least for some of them.
Dirichlet's theorem
Let be any integer. Then there exists a rational number such that and .
Proof of Dirichlet's theorem
Consider the fractional parts . They all belong to the half-open interval . Represent the interval as the union of subintervals . Since we have fractional parts and only subintervals, the pigeonhole principle implies that there are two integers such that and belong to the same interval. But then the difference differs by less than from some integer number : . Dividing by , we get .
Corollary
If is irrational, then there are infinitely many irreducible fractions such that .
Proof of the corollary
For each , find a (possibly reducible) fraction with such that . Let be the same fraction as but reduced to its lowest terms. It is clear that , so it remains to show that among the fractions there are infinitely many different ones. But the distance from the -th fraction to does not exceed , which can be made arbitrarily small if we take large enough . On the other hand, if the fractions were finitely many, this distance couldn't be made less than the distance from the irrational number to some finite set of rational numbers, i.e., less than some positive constant.
Discussion
The Dirichlet's theorem can be generalized in various ways. The first way is that one can try to approximate several numbers simultaneously by fractions with common denominator. The exact statement is as follows.
If and is an integer, then there exists an integer with and integers such that
The proof is essentially the same except instead of considering numbers , one has to consider vectors , in the unit cube divided into equal subcubes.
Another remark that can be useful in some problems is that, if is irrational, then you can find infinitely many solutions of the inequality with the denominator contained in any given arithmetic progression () if the constant (depending on the progression) is large enough. To prove it, first, find infinitely many irreducible fractions satisfying . Then, for each such fraction, find two integers such that and . Now note that and are relatively prime, so we can find some integer such that . Replacing and by their remainders and modulo , we get a positive integer satisfying and . Thus, setting , we get .
Applications to problem solving
One common way to apply Dirichlet's theorem in problem solving is to use it in the following form: given finitely many numbers and , one can find a positive integer such that each of the numbers differs from some integer by less than . A typical example of such usage can be found in the article devoted to the famous Partition of a rectangle into squares problem.
Liouville Approximation Theorem
We can generalize Dirichlet's theorem as follows: If is an algebraic number of degree , then there are only finitely many rational numbers satisfying the following inequality: . This gives us the following corollary: is a transcendental number, known as Liouville's constant.
Hurwitz's theorem
For every irrational number there are infinitely many rationals m/n such that
Roth's theorem
For algebraic α, integers p and q; has finitely many solutions as ε>0.