Difference between revisions of "Rational approximation"
m (in trivial theorem, pq --> p/q) |
(→Proof of Dirichlet's theorem) |
||
| Line 10: | Line 10: | ||
Let <math>n\ge 1</math> be any integer. Then there exists a rational number <math>\frac pq</math> such that <math>1\le q\le n</math> and <math>\left|x-\frac pq\right|<\frac 1{nq}</math>. | Let <math>n\ge 1</math> be any integer. Then there exists a rational number <math>\frac pq</math> such that <math>1\le q\le n</math> and <math>\left|x-\frac pq\right|<\frac 1{nq}</math>. | ||
==Proof of Dirichlet's theorem== | ==Proof of Dirichlet's theorem== | ||
| − | Consider the [[fractional part]]s <math>\{1\cdot x\}, \{2\cdot x\},\dots, \{n\cdot x\}</math>. They all belong to the half-open interval <math>[0,1)</math>. Represent the interval <math>[0,1)</math> as the union of <math>n</math> subintervals <math>[0,1)=\left[0,\frac 1n\right)\cup\dots\cup\left[\frac{n-1}{n},1\right),</math>. | + | Consider the [[fractional part]]s <math>\{0\cdot x\},\{1\cdot x\}, \{2\cdot x\},\dots, \{n\cdot x\}</math>. They all belong to the half-open interval <math>[0,1)</math>. Represent the interval <math>[0,1)</math> as the union of <math>n</math> subintervals <math>[0,1)=\left[0,\frac 1n\right)\cup\left[\frac 1n,\frac 2n\right)\cup\dots\cup\left[\frac{n-1}{n},1\right),</math>. Since we have <math>n+1</math> fractional parts and only <math>n</math> subintervals, the [[pigeonhole principle]] implies that there are two integers <math>0\le k<\ell\le n</math> such that <math>\{kx\}</math> and <math>\{\ell x\}</math> belong to the same interval. But then the difference <math>(\ell-k)x</math> differs by less than <math>\frac 1n</math> from some integer number <math>p</math>: <math>|(\ell-k)x-p|<\frac 1n</math>. Dividing by <math>q=\ell-k</math>, we get <math>\left|x-\frac pq\right|<\frac1{nq}</math>. |
| + | ==Corollary== | ||
''to be continued'' | ''to be continued'' | ||
Revision as of 00:08, 24 June 2006
Contents
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 ![$\left[qx-\frac12,qx+\frac12\right]$](http://latex.artofproblemsolving.com/4/4/3/4434ff4e3265c50511c19f182f9011a52005b5ea.png)
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
to be continued
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.
