Difference between revisions of "Rational approximation"

Revision as of 21:13, 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

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 $x_1,\dots,x_m\in \mathbb R$ and $n\ge 1$ is an integer, then there exists an integer $q$ with $1\le q\le n^m$ and integers $p_1,\dots,p_m$ such that $\left|x_j-\frac {p_j}q\right|<\frac 1{nq}$

The proof is essentially the same except instead of considering $n+1$ numbers $\{kx\}$ , $k=0,\dots,n$ one has to consider $n^m+1$ vectors $(\{kx_1\},\dots,\{kx_m\})$ , $k=0,\dots, n^m$ in the unit cube $[0,1)^m$ divided into $n^m$ equal subcubes.

Another remark that can be useful in some problems is that, if $x$ is irrational, then you can find infinitely many solutions of the inequality $\left|x-\frac {p}q\right|<\frac C{q^2}$ with the denominator $q$ contained in any given arithmetic progression $a\ell+b$ ( $\ell\in\mathbb Z$ ) if the constant $C$ (depending on the progression) is large enough. To prove it, first, find infinitely many irreducible fractions $\frac PQ$ satisfying $\left|x-\frac PQ\right|<\frac 1{Q^2}$ . Then, for each such fraction, find two integers $u,v$ such that $0< u\le Q$ and $uP+vQ=1$ . Now note that $u$ and $Q$ are relatively prime, so we can find some integer $\alpha, \beta$ such that $\alpha u+\beta Q=b$ . Replacing $\alpha$ and $\beta$ by their remainders $\tilde\alpha$ and $\tilde\beta$ modulo $a$ , we get a positive integer $q=\tilde\alpha u+\tilde\beta Q$ satisfying $1\le q\le 2aQ$ and $|qx-(\tilde\beta P-\tilde\alpha v)|\le\tilde\alpha|ux+v|+\tilde\beta|Qx-P|\le \tilde\alpha u\left|x-\frac PQ\right|+\frac{\tilde\alpha}Q+\frac {\tilde\beta}Q\le \frac {3a}Q\le \frac {6a^2}q$ . Thus, setting $p=\tilde\beta P-\tilde\alpha v$ , we get $\left|x-\frac pq\right|<\frac {6a^2}{q^2}$ .

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 $x_1,\dots,x_m$ and $\delta>0$ , one can find a positive integer $q$ such that each of the numbers $qx_1, qx_2,\dots, qx_m$ differs from some integer by less than $\delta$ . 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 $\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 3: / Line 3: @@
 ==Trivial theorem==
 Every real number <math>x</math> can be approximated by a rational number <math>\frac{p}{q}</math> with a given denominator <math>q\ge 1</math> with an error not exceeding <math>\frac 1{2q}</math>.
-==Proof==
+===Proof===
 Note that the closed interval <math>\left[qx-\frac12,qx+\frac12\right]</math> has length <math>1</math> and, therefore, contains at least one integer. Choosing <math>p</math> to be that integer, we immediately get the result.
 ----
@@ Line 9: / Line 9: @@
 ==Dirichlet's theorem==
 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>\{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==
+===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>.
-==Proof of the corollary==
+===Proof of the corollary===
 For each <math>n\ge 1</math>, find a (possibly reducible) fraction <math>\frac {P_n}{Q_n}</math> with <math>1\le Q_n\le n</math> such that <math>\left|x-\frac {P_n}{Q_n}\right|<\frac 1{nQ_n}</math>. Let <math>\frac {p_n}{q_n}</math> be the same fraction as <math>\frac {P_n}{Q_n}</math> but reduced to its lowest terms. It is clear that <math>\frac 1{nQ_n}\le \frac 1{Q_n^2}\le \frac 1{q_n^2}</math>, so it remains to show that among the fractions <math>\frac {p_n}{q_n}</math> there are infinitely many different ones. But the distance from the <math>n</math>-th fraction to <math>x</math> does not exceed <math>\frac 1n</math>, which can be made arbitrarily small  if we take large enough <math>n</math>. On the other hand, if the fractions <math>\frac {p_n}{q_n}</math> were finitely many, this distance couldn't be made less than the distance from the irrational number <math>x</math> to some finite set of rational numbers,  i.e., less than some positive constant.
-==Discussion==
+===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.
 ----
@@ Line 25: / Line 25: @@
 Another remark that can be useful in some problems is that, if <math>x</math> is irrational, then you can find infinitely many solutions of the inequality <math>\left|x-\frac {p}q\right|<\frac C{q^2}</math> with the denominator <math>q</math> contained in any given arithmetic progression <math>a\ell+b</math> (<math>\ell\in\mathbb Z</math>) if the constant <math>C</math> (depending on the progression) is large enough. To prove it, first, find infinitely many irreducible fractions <math>\frac PQ</math> satisfying <math>\left|x-\frac PQ\right|<\frac 1{Q^2}</math>. Then, for each such fraction, find two integers <math>u,v</math> such that <math>0< u\le Q</math> and <math>uP+vQ=1</math>. Now note that <math>u</math> and <math>Q</math> are relatively prime, so we can find some integer <math>\alpha, \beta</math> such that <math>\alpha u+\beta Q=b</math>. Replacing <math>\alpha</math> and <math>\beta</math> by their [[remainder]]s <math>\tilde\alpha</math> and <math>\tilde\beta</math> modulo <math>a</math>, we get a positive integer <math>q=\tilde\alpha u+\tilde\beta Q</math> satisfying <math>1\le q\le 2aQ</math> and  <math>|qx-(\tilde\beta P-\tilde\alpha v)|\le\tilde\alpha|ux+v|+\tilde\beta|Qx-P|\le
 \tilde\alpha u\left|x-\frac PQ\right|+\frac{\tilde\alpha}Q+\frac {\tilde\beta}Q\le \frac {3a}Q\le \frac {6a^2}q</math>. Thus, setting <math>p=\tilde\beta P-\tilde\alpha v</math>, we get <math>\left|x-\frac pq\right|<\frac {6a^2}{q^2}</math>.
+===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 <math>x_1,\dots,x_m</math> and <math>\delta>0</math>, one can find a positive integer <math>q</math> such that each of the numbers <math>qx_1, qx_2,\dots, qx_m</math> differs from some integer by less than <math>\delta</math>. 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 <math>\alpha</math> is an [[algebraic number]] of degree <math>n</math>, then there are only finitely many rational numbers <math>\frac{p}{q}</math> satisfying the following inequality:
 <math>\Bigg|\alpha-\frac{p}{q}\Bigg| \le\frac{1}{q^n}</math>. This gives us the following corollary: <math>\sum_{n=0}^\infty 10^{-n!}</math> is a [[transcendental number]], known as [[Liouville's constant]].

Page

Toolbox

Search