View source for Number theory/Signed Articles/Elementary diophantine approximations

The theory of diophantine approximations is a chapter of [[number theory]], which in turn is a part of [[mathematics]]. It studies the approximations of [[real number]]s by [[rational number]]s. This article presents an elementary introduction to diophantine approximations, as well as an introduction to number theory via diophantine approximations.

== Introduction ==

In the everyday life our civilization applies mostly (finite) decimal fractions <math>\ \frac{k}{10^n}.</math>&nbsp; Decimal fractions are used both as certain values, e.g. $5.85, and as approximations of the real numbers, e.g. <math>\ \pi \approx 3.14159.</math>&nbsp; However, the field of all rational numbers is much richer than the ring of the decimal fractions (or of the binary fractions <math>\ \frac{k}{2^n},</math>&nbsp; which are used in the computer science). For instance, the famous approximation  <math>\ \pi \approx \frac{355}{113}</math>&nbsp; has denominator 113 much smaller than 10<sup>5</sup> but it provides a better approximation than the decimal one, which has five digits after the decimal point.

How well can real numbers (all of them or the special ones) be approximated by rational numbers? A typical Diophantine approximation result states:

'''Theorem'''&nbsp; Let <math>\ a</math>&nbsp; be an arbitrary real number. Then

* <math>\ a</math>&nbsp; is rational if and only if there exists a real number C > 0 such that

:::<math>|a - \frac{x}{y}| > \frac{C}{y}</math>

for arbitrary integers <math>\ (x,y)</math>&nbsp; such that <math>\ y>0</math>&nbsp; and <math>\ a\ne \frac{x}{y};</math>

* <math>\ a</math>&nbsp; is irrational if and only if there exist infinitely many pairs of integers <math>\ (x,y)</math>&nbsp; such that <math>\ y>0</math>&nbsp; and

:::<math>|a - \frac{x}{y}| < \frac{1}{\sqrt{5}\cdot y^2}.</math>

== Notation ==

* <math>\Leftarrow:\Rightarrow\ </math>  &nbsp; &mdash; &nbsp;  "equivalent by definition" (i.e. "if and only if");
* <math>:=\ </math>  &nbsp; &mdash; &nbsp;  "equals by definition";
* <math>\exists</math> &nbsp; &mdash; &nbsp;  "there exists";
* <math>\forall</math> &nbsp; &mdash; &nbsp;  "for all";
* <math>a\in A\ </math> &nbsp; &mdash; &nbsp;  "<math>a\ </math>&nbsp; is an element of set <math>\ A</math>";
&nbsp;
* <math>\mathbb{N}\ :=\ \{1, 2 \dots\}</math>  &nbsp;&mdash;&nbsp;  the semiring of the natural numbers;
* <math>\mathbb{Z}_+\ :=\ \{0, 1, \dots\}</math>  &nbsp;&mdash;&nbsp;  the semiring of the non-negative integers;
* <math>\mathbb{Z}\ :=\ \{-2,-1,1, 2 \dots\}</math>  &nbsp;&mdash;&nbsp;  the ring of integers;
* <math>\mathbb{Q}</math> &nbsp;&mdash;&nbsp; the field of rational numbers;
* <math>\mathbb{R}</math> &nbsp;&mdash;&nbsp; the field of real numbers;
&nbsp;
*<math>x|y\ </math>  &nbsp; &mdash; &nbsp;  "<math>x\ </math>&nbsp; divides <math>\ y</math>";
* <math>\gcd(a, b)\ </math>  &nbsp;&mdash;&nbsp; the greatest common divisor of integers <math>\ a</math>&nbsp; and <math>\ b.</math>
&nbsp;

== The method of neighbors and median ==

In this section we will quickly obtain some results about approximating irrational numbers by rational (for the sake of simpplicity only positive numbers will be considered). To this end we will not worry about the details of the difference between a rational number and a fraction (with integer numerator and denominator)&mdash;this will not cause any problems. This section is still introductory. It is supposed to provide quickly some pleasure from the insight into the topic before getting into somewhat more involved considerations of the later sections.
 
Fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with non-negative numerators and positive denominators, are called '''neighbors''' (in the given order) &nbsp; <math>\Leftarrow:\Rightarrow</math>

:::<math>\frac{a}{c}-\frac{b}{d}\ =\ \frac{1}{c\cdot d}</math>

Fraction <math>\frac{a}{c}</math>&nbsp; is called the '''left neighbor''' of the other, and <math>\frac{b}{d}</math>&nbsp; is called the '''right neighbor'''.

'''Examples:'''
* Fractions <math>\frac{n}{1}</math>&nbsp; and <math>\frac{n+1}{1}</math>&nbsp; are neighbors for every positive integer <math>\ n.</math>


* Fractions <math>\frac{1}{n}</math>&nbsp; and <math>\frac{1}{n+1}</math>&nbsp; are neighbors for every positive integer <math>\ n.</math>

Thus it easily follows that for every positive irrational number <math>\ x</math>&nbsp; there exists a pair of neighbors&nbsp; <math>\frac{a}{c}</math>&nbsp; and &nbsp;<math>\frac{b}{d},</math>&nbsp; with positive numerators and denominators, such that:

::: <math>\frac{a}{c}\ >\ x\ >\ \frac{b}{d}</math>&nbsp;

=== First results ===

'''Theorem 1'''&nbsp; Let fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with positive integer numerators and denominators, be neighbors. Then
* if positive integers <math>\ s</math>&nbsp; and <math>\ t</math>&nbsp; are such that &nbsp; <math>\ \frac{a}{c} > \frac{s}{t} > \frac{b}{d},</math> &nbsp; then &nbsp; <math>t \ge b+d;</math>

* the '''median''' &nbsp;<math>\frac{a+b}{c+d}</math>&nbsp; is a right neighbor of &nbsp;<math>\frac{a}{c},</math>&nbsp; and a left neighbor of&nbsp; <math>\frac{b}{d};</math>&nbsp;

* let&nbsp; <math>\ x</math>&nbsp; be an irrational number such that &nbsp; <math>\frac{a}{c}\ >\ x\ >\ \frac{b}{d};</math> &nbsp; then

::<math>\max(\frac{a}{c}-x,\, x-\frac{b}{d})\ <\ \frac{1}{c\cdot d}</math>

and

:<math>\frac{a}{c}-x\ <\ \frac{1}{c\cdot (c+1)}</math> &nbsp; &nbsp; or &nbsp; &nbsp; <math>x-\frac{b}{d}\ <\ \frac{1}{d\cdot (d+1)}</math>

'''Proof'''&nbsp; Let &nbsp; <math>\ \frac{a}{c} > \frac{s}{t} > \frac{b}{d};</math> &nbsp; then

:<math>\frac{a}{c} - \frac{s}{t}\ \ge\ \frac{1}{c\cdot t}</math> &nbsp; &nbsp; and &nbsp; &nbsp; <math>\frac{s}{t} - \frac{b}{d}\ \ge\ \frac{1}{d\cdot t}</math>

and

:<math>\frac{1}{c\cdot t} + \frac{1}{d\cdot t}\ \le \frac{1}{c\cdot d}</math>

Multiplying this inequality by&nbsp; <math>c\cdot d\cdot t\ </math> gives

:::<math>t \ge c+d</math>

which is the first part of our theorem.

== Divisibility ==

'''Definition'''&nbsp; Integer <math>\ a</math>&nbsp; is divisible by integer <math>\ b</math> &nbsp; <math>\Leftarrow:\Rightarrow\ </math> &nbsp; <math>\exists_{c\in\mathbb{Z}}\ a=b\cdot c</math>

Symbolically:

:::<math>b|a\ </math> &nbsp; <math>\Leftarrow:\Rightarrow\ </math> &nbsp; <math>\exists_{c\in\mathbb{Z}}\ a=b\cdot c</math>


When <math>\ a</math>&nbsp; is divisible by <math>\ b</math>&nbsp; then we also say that <math>\ b</math>&nbsp; is a divisor of <math>\ a,</math>&nbsp; or that <math>\ b</math>&nbsp; divides <math>\ a.</math>

* The only integer divisible by <math>\ 0</math>&nbsp; is <math>\ 0</math>&nbsp; (i.e. <math>\ 0</math>&nbsp; is a divisor only of <math>\ 0</math>).
* <math>0\ </math>&nbsp; is divisible by every integer.
* <math>1\ </math>&nbsp; is the only positive divisor of <math>\ 1.</math>
* Every integer is divisible by <math>\ 1</math>&nbsp; (and by&nbsp; <math>\ -1</math>).
&nbsp;
* <math>a|b\ \Rightarrow (-a|b\ \and\ a|\!-\!\!b)</math>
* <math>a|b > 0\ \Rightarrow a\le b</math>
&nbsp;
* <math>a|a\ </math>
* <math>(a|b\ \and\ b|c)\ \Rightarrow\ a|c</math>
* <math>(a|b\ \and\ b|a)\ \Rightarrow\ |a|=|b|</math>

'''Remark'''&nbsp; The above three properties show that the relation of divisibility is a [[partial order]] in the set of natural number &nbsp;<math>\mathbb{N},</math>&nbsp; and also in <math>\mathbb{Z}_+</math> &mdash; <math>\ 1</math>&nbsp; is its minimal, and <math>\ 0</math>&nbsp; is its maximal element.

* <math>(a|b\ \and\ a|c)\ \Rightarrow\ (a\,|\,b\!\cdot\!d\ \and\ a\,|\,b\!+\!c\ \and\ a\,|\,b\!-\!c)</math>

&nbsp;

== Relatively prime pairs of integers ==

'''Definition'''&nbsp; Integers <math>\ a</math>&nbsp; and <math>\ b</math>&nbsp; are ''relatively prime'' &nbsp; <math>\Leftarrow:\Rightarrow\ </math> &nbsp; <math>\ 1</math>&nbsp; is their only common positive divisor.

* Integers <math>\ x</math>&nbsp; and <math>\ 0</math>&nbsp; are relatively prime &nbsp; <math>\Leftrightarrow\ |x| = 1.</math>
* <math>1\ </math>&nbsp; is relatively prime with every integer.
* If <math>\ a</math>&nbsp; and <math>\ b</math>&nbsp; are relatively prime then also <math>\ a</math>&nbsp; and &nbsp;<math>\ -b</math>&nbsp; are relatively prime.


:'''Theorem 1'''&nbsp; If <math>\ a,b,c \in \mathbb{Z}</math>&nbsp; are such that two of them are relatively prime and <math>\ a+b=c,</math>&nbsp; then any two of them are relatively prime.

:'''Corollary'''&nbsp; If <math>\ a</math>&nbsp; and <math>\ b</math>&nbsp; are relatively prime then also <math>\ a</math>&nbsp; and &nbsp;<math>\ |a-b\,|</math>&nbsp; are relatively prime.


Now, let's define inductively a table odd integers:

:::<math>(\nu_{k,n} : k\in \mathbb{Z}_+,\ 0\le n\le 2^k)</math>

as follows:

* <math>\nu_{0,0} := 0\ </math> &nbsp; &nbsp; and &nbsp; &nbsp; <math>\nu_{0,1} :=1\ </math>
* <math>\nu_{k+1,2\cdot n}\ :=\ \nu_{k,n}</math> &nbsp; for&nbsp; <math>0\le n\le 2^k\ </math>
* <math>\nu_{k+1,2\cdot n+1}\ :=\ \nu_{k,n}+\nu_{k,n+1}</math> &nbsp; for&nbsp; <math>0\le n < 2^k\ </math>

for every &nbsp;<math>\ k=0,1,\dots.</math>


The top of this table looks as follows:

:0 1
:0 1 1
:0 1 1 2 1
:0 1 1 2 1 3 2 3 1
:0 1 1 2 1 3 1 3 1 4 3 5 2 5 3 4 1

etc.

:'''Theorem 2'''
:* Every pair of neighboring elements of the table, <math>\ \nu_{k,n}</math>&nbsp; and <math>\ \nu_{k,n+1}</math> &nbsp; is relatively prime.
:* For every pair of relatively prime, non-negative integers <math>\ a</math>&nbsp; and <math>\ b</math>&nbsp; there exist indices <math>k\in\mathbb{Z}_+</math>&nbsp; and non-negative <math>\ n<2^k</math>&nbsp; such that:

::::<math>\{a,b\}\ =\ \{\nu_{k,n},\nu_{k,n+1}\}</math>

'''Proof'''&nbsp; Of course the pair

::<math>\{\nu_{0,0},\nu_{0,1}\}\ =\ \{0,1\}</math>

is relatively prime; and the inductive proof of the first statement of Theorem 2 is now instant thanks to Theorem 1 above.

Now let <math>\ a</math>&nbsp; and <math>\ b</math>&nbsp; be a pair of relatively prime, non-negative integers. If <math>\ a+b=1</math>&nbsp; then <math>\ \{a, b\}=\{0,1\}=\{\nu_{0,0},\nu_{0,1}\},</math>&nbsp; and the second part of the theorem holds. Continuing this unductive proof, let's assume that <math>\ a+b>1.</math>&nbsp; Then <math>\ \min(a,b) > 0.</math>&nbsp; Thus

:<math>\ \max(a,b) < a+b</math>

But integers <math>\ c := \min(a,b)</math>&nbsp; and <math>\ d := |a-b|</math>&nbsp; are relatively prime (see Corollary above), and

:<math>c+d\ =\ max(a,b)\ <\ a+b</math>

hence, by induction,

:::<math>\{c,d\}\ =\ \{\nu_{k,n},\nu_{k,n+1}\}</math>

for certain indices <math>k\in\mathbb{Z}_+</math>&nbsp; and non-negative <math>\ n<2^k.</math>&nbsp; Furthermore:

:<math>\{a,b\}\ =\ \{\min(a,b), \max(a,b)\}</math>

It follows that one of the two options holds:

:::<math>\{a,b\}\ =\ \{\nu_{k+1,2\cdot n},\nu_{k+1,2\cdot n+1}\}</math>
or
:::<math>\{a,b\}\ =\ \{\nu_{k+1,2\cdot n+1},\nu_{k+1,2\cdot n+2}\}</math>

'''End of proof'''


* <math>\max_{\quad 0\le n \le 2^k}\nu_{k,n}\ =\ F_{k+1}</math>


where <math>\ F_r</math>&nbsp; is the r-th [[Fibonacci number]].


== Matrix monoid <math>\mathit{SO}(\mathbb{Z}_+, 2)</math> ==

'''Definition 1'''&nbsp; <math>\mathit{SO}(\mathbb{Z}_+, 2)</math>&nbsp; is the set of all matrices

:::<math>M\ :=\ \left[\begin{array}{cc}a & b\\ c & d\end{array}\right]</math>

such that <math>\ a,b,c,d\in\mathbb{Z}_+,</math>&nbsp; and &nbsp;<math>\ \det(M) = 1,</math>&nbsp; where &nbsp;<math>\ \det(M) := a\cdot d - b\cdot c.</math>&nbsp; Such matrices (and their columns and rows) will be called '''special'''.

* If
:::<math>M\ :=\ \left[\begin{array}{cc}a & b\\ c & d\end{array}\right]\in\mathit{SO}(\mathbb{Z}_+, 2)</math>

then&nbsp; <math>\ a,d > 0,</math>&nbsp; and each of the columns and rows of M, i.e. each of the four pairs &nbsp;<math>(x,y) \in \{a,d\}\times \{b,c\},\ </math>&nbsp; is relatively prime.


Obviously, the identity matrix

:::<math>\mathcal{I}\ :=\ \left[\begin{array}{cc}1 & 0\\ 0 & 1\end{array}\right]</math>

belongs to &nbsp; <math>\mathit{SO}(\mathbb{Z}_+, 2).</math>&nbsp; Furthermore,&nbsp; <math>\mathit{SO}(\mathbb{Z}_+, 2)</math>&nbsp; is a [[monoid]] with respect to the matrix multiplication.

'''Example'''&nbsp; The ''left matrix'' and the ''right matrix'' are defined respectively as follows:

:<math>\mathcal{L}\ :=\ \left[\begin{array}{cc}1 & 1\\ 0 & 1\end{array}\right]</math> &nbsp; and &nbsp; <math>\mathcal{R}\ :=\ \left[\begin{array}{cc}1 & 0\\ 1 & 1\end{array}\right]</math>

Obviously <math>\ \mathcal{L},\mathcal{R}\in \mathit{SO}(\mathbb{Z}_+,2).</math>&nbsp; When they act on the right on a matrix M (by multipliplying M by itself), then they leave respectively the left or right column of M intact:

:::<math>M\cdot \mathcal{L}\ =\ \left[\begin{array}{cc}a & a+b\\ c & c+d\end{array}\right]</math>
and
:::<math>M\cdot \mathcal{R}\ =\ \left[\begin{array}{cc}a+b & b\\ c+d & d\end{array}\right]</math>


'''Definition 2'''&nbsp; Vectors

:::<math>\left[\begin{array}{c}a\\ c\end{array}\right]</math> &nbsp; &nbsp; and &nbsp; &nbsp; <math>\left[\begin{array}{c}b\\ d\end{array}\right]</math>

where <math>\ a,b,c,d\in\mathbb{Z}_+,</math>&nbsp; are called '''neighbors''' (in that order) &nbsp; <math>\Leftarrow:\Rightarrow</math> &nbsp; matrix formed by these vectors

:::<math>M\ :=\ \left[\begin{array}{cc}a & b\\ c & d\end{array}\right]</math>

belongs to&nbsp; <math>\mathit{SO}(\mathbb{Z}_+, 2).</math>&nbsp; Then the left (resp. right) column is called the left (resp. right) neighbor.


== Rational representation ==

With every vector

:::<math>v\ :=\ \left[\begin{array}{c}a\\ c\end{array}\right]</math>

such that <math>\ c\ne 0,</math>&nbsp; let's associate a rational number

:::<math>\mathit{rat}(v)\ :=\ \frac{a}{c}</math>

Also, let

:::<math>\mathit{rat}(v_{\infty})\ :=\ \infty</math>

for

:::<math>v_{\infty}\ :=\ \left[\begin{array}{c}1\\ 0\end{array}\right]</math>

Furthermore, with every matrix &nbsp;<math>M\in \mathit{SO}(\mathbb{Z}_+,2),</math>&nbsp; let's associate the real closed interval (it may include the point at plus infinity)

:::<math>\mathit{span}(M)\ :=\ [\mathit{rat}(w);\mathit{rat}(v)]</math>

and its length

:::<math>|M|\ :=\ \mathit{rat}(v)-\mathit{rat}(w)</math>

where <math>\ v</math>&nbsp; is the left, and <math>\ w</math>&nbsp; is the right column of matrix M &mdash; observe that the rational representation of the left column of a special matrix is always greater than the rational representation of the right column of the same special matrix.

* If
:::<math>M\ :=\ \left[\begin{array}{cc}a & b\\ c & d\end{array}\right]\in\mathit{SO}(\mathbb{Z}_+, 2)</math>

then&nbsp; <math>\ |M| = \frac{1}{c\cdot d}</math>