Difference between revisions of "Rational approximation"

Revision as of 09:10, 24 June 2006

Introduction

The main theme of this article is the question how well a given real number $x$ can be approximated by rational numbers. Of course, since the rationals are dense on the real line, we, surely, can make the difference between $x$ and its rational approximation $\frac pq$ as small as we wish. The problem is that, as we try to make $\frac pq$ closer and closer to $x$ , we may have to use larger and larger $p$ and $q$ . So, the reasonable question to ask here is how well can we approximate $x$ by rationals with not too large denominators.

Trivial theorem

Every real number $x$ can be approximated by a rational number $\frac{p}{q}$ with a given denominator $q\ge 1$ with an error not exceeding $\frac 1{2q}$ .

Proof

Note that the closed interval $\left[qx-\frac12,qx+\frac12\right]$ has length $1$ and, therefore, contains at least one integer. Choosing $p$ to be that integer, we immediately get the result.

So, the interesting question is whether we can get a smaller error of approximation than $\frac 1q$ . Surprisingly enough, it is possible, if not for all $q$ , then, at least for some of them.

Dirichlet's theorem

Let $n\ge 1$ be any integer. Then there exists a rational number $\frac pq$ such that $1\le q\le n$ and $\left|x-\frac pq\right|<\frac 1{nq}$ .

Proof of Dirichlet's theorem

Consider the fractional parts $\{0\cdot x\},\{1\cdot x\}, \{2\cdot x\},\dots, \{n\cdot x\}$ . They all belong to the half-open interval $[0,1)$ . Represent the interval $[0,1)$ as the union of $n$ subintervals $[0,1)=\left[0,\frac 1n\right)\cup\left[\frac 1n,\frac 2n\right)\cup\dots\cup\left[\frac{n-1}{n},1\right),$ . Since we have $n+1$ fractional parts and only $n$ subintervals, the pigeonhole principle implies that there are two integers $0\le k<\ell\le n$ such that $\{kx\}$ and $\{\ell x\}$ belong to the same interval. But then the difference $(\ell-k)x$ differs by less than $\frac 1n$ from some integer number $p$ : $|(\ell-k)x-p|<\frac 1n$ . Dividing by $q=\ell-k$ , we get $\left|x-\frac pq\right|<\frac1{nq}$ .

Corollary

If $x$ is irrational, then there are infinitely many irreducible fractions $\frac pq$ such that $\left|x-\frac pq\right|<\frac 1{q^2}$ .

Proof of the corollary

For each $n\ge 1$ , find a (possibly reducible) fraction $\frac {P_n}{Q_n}$ with $1\le Q_n\le n$ such that $\left|x-\frac {P_n}{Q_n}\right|<\frac 1{nQ_n}$ . Let $\frac {p_n}{q_n}$ be the same fraction as $\frac {P_n}{Q_n}$ but reduced to its lowest terms. It is clear that $\frac 1{nQ_n}\le \frac 1{Q_n^2}\le \frac 1{q_n^2}$ , so it remains to show that among the fractions $\frac {p_n}{q_n}$ there are infinitely many different ones. But the distance from the $n$ -th fraction to $x$ does not exceed $\frac 1n$ , which can be made arbitrarily small if we take large enough $n$ . On the other hand, if the fractions $\frac {p_n}{q_n}$ were finitely many, this distance couldn't be made less than the distance from the irrational number $x$ to some finite set of rational numbers, i.e., less than some positive constant.

Discussion

to be continued

Liouville Approximation Theorem

We can generalize Dirichlet's theorem as follows: If $\alpha$ is an algebraic number of degree $n$ , then there are only finitely many rational numbers $\frac{p}{q}$ satisfying the following inequality: $\Bigg|\alpha-\frac{p}{q}\Bigg| \le\frac{1}{q^n}$ . This gives us the following corollary: $\sum_{n=0}^\infty 10^{-n!}$ is a transcendental number, known as Liouville's constant.

@@ 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>.
 ==Proof of Dirichlet's theorem==
-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>.
+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|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==
 If <math>x</math> is [[irrational number|irrational]], then there are infinitely many irreducible fractions <math>\frac pq</math> such that <math>\left|x-\frac pq\right|<\frac 1{q^2}</math>.

Page

Toolbox

Search