Rational approximation

Revision as of 09:10, 24 June 2006 by Fedja (talk | contribs) (Proof of Dirichlet's theorem)

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.