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 numbers by rational numbers. 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 $\ {\frac {k}{10^{n}}}.$  Decimal fractions are used both as certain values, e.g. $5.85, and as approximations of the real numbers, e.g. $\ \pi \approx 3.14159.$  However, the field of all rational numbers is much richer than the ring of the decimal fractions (or of the binary fractions $\ {\frac {k}{2^{n}}},$  which are used in the computer science). For instance, the famous approximation $\ \pi \approx {\frac {355}{113}}$  has denominator 113 much smaller than 10⁵ 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  Let $\ a$  be an arbitrary real number. Then

• $\ a$  is rational if and only if there exists a real number C > 0 such that

$|a-{\frac {x}{y}}|>{\frac {C}{y}}$

for arbitrary integers $\ (x,y)$  such that $\ y>0$  and $\ a\neq {\frac {x}{y}};$

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a}   is irrational if and only if there exist infinitely many pairs of integers $\ (x,y)$  such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y>0}   and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |a - \frac{x}{y}| < \frac{1}{\sqrt{5}\cdot y^2}.}

Notation

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Leftarrow:\Rightarrow\ }   —   "equivalent by definition" (i.e. "if and only if");
• $:=\$   —   "equals by definition";
• $\exists$   —   "there exists";
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall}   —   "for all";
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in A\ }   —   "$a\$  is an element of set $\ A$";

 

• $\mathbb {N} \ :=\ \{1,2\dots \}$  —  the semiring of the natural numbers;
• $\mathbb {Z} _{+}\ :=\ \{0,1,\dots \}$  —  the semiring of the non-negative integers;
• $\mathbb {Z} \ :=\ \{-2,-1,1,2\dots \}$  —  the ring of integers;
• $\mathbb {Q}$  —  the field of rational numbers;
• $\mathbb {R}$  —  the field of real numbers;

 

• $x|y\$   —   "$x\$  divides $\ y$";
• $\gcd(a,b)\$  —  the greatest common divisor of integers $\ a$  and $\ b.$

 

Divisibility

Definition  Integer $\ a$  is divisible by integer $\ b$   $\Leftarrow :\Rightarrow \$   $\exists _{c\in \mathbb {Z} }\ a=b\cdot c$

Symbolically:

$b|a\$   $\Leftarrow :\Rightarrow \$   $\exists _{c\in \mathbb {Z} }\ a=b\cdot c$

When $\ a$  is divisible by $\ b$  then we also say that $\ b$  is a divisor of $\ a,$  or that $\ b$  divides $\ a.$

• The only integer divisible by $\ 0$  is $\ 0$  (i.e. $\ 0$  is a divisor only of $\ 0$).
• $0\$  is divisible by every integer.
• $1\$  is the only positive divisor of $\ 1.$
• Every integer is divisible by $\ 1$  (and by  $\ -1$).

 

• $a|b\ \Rightarrow (-a|b\ \land \ a|\!-\!\!b)$
• $a|b>0\ \Rightarrow a\leq b$

 

• $a|a\$
• $(a|b\ \land \ b|c)\ \Rightarrow \ a|c$
• $(a|b\ \land \ b|a)\ \Rightarrow \ |a|=|b|$

Remark  The above three properties show that the relation of divisibility is a partial order in the set of natural number  $\mathbb {N} ,$  and also in $\mathbb {Z} _{+}$ — $\ 1$  is its minimal, and $\ 0$  is its maximal element.

• $(a|b\ \land \ a|c)\ \Rightarrow \ (a\,|\,b\!\cdot \!d\ \land \ a\,|\,b\!+\!c\ \land \ a\,|\,b\!-\!c)$

 

Relatively prime pairs of integers

Definition  Integers $\ a$  and $\ b$  are relatively prime   $\Leftarrow :\Rightarrow \$   $\ 1$  is their only common positive divisor.

• Integers $\ x$  and $\ 0$  are relatively prime   $\Leftrightarrow \ |x|=1.$
• $1\$  is relatively prime with every integer.
• If $\ a$  and $\ b$  are relatively prime then also $\ a$  and  $\ -b$  are relatively prime.

Theorem 1  If $\ a,b,c\in \mathbb {Z}$  are such that two of them are relatively prime and $\ a+b=c,$  then any two of them are relatively prime.

Corollary  If $\ a$  and $\ b$  are relatively prime then also $\ a$  and  $\ |a-b\,|$  are relatively prime.

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

$(\nu _{k,n}:k\in \mathbb {Z} _{+},\ 0\leq n\leq 2^{k})$

as follows:

• $\nu _{0,0}:=0\$     and     Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_{0,1} :=1\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_{k+1,2\cdot n}\ :=\ \nu_{k,n}}   for  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\le n\le 2^k\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_{k+1,2\cdot n+1}\ :=\ \nu_{k,n}+\nu_{k,n+1}}   for  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\le n < 2^k\ }

for every  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k=0,1,\dots.}

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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \nu_{k,n}}   and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \nu_{k,n+1}}   is relatively prime.
• For every pair of relatively prime, non-negative integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a}   and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b}   there exist indices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\in\mathbb{Z}_+}   and non-negative Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n<2^k}   such that:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a,b\}\ =\ \{\nu_{k,n},\nu_{k,n+1}\}}

Proof  Of course the pair

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{\nu_{0,0},\nu_{0,1}\}\ =\ \{0,1\}}

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

Now let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a}   and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b}   be a pair of relatively prime, non-negative integers. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a+b=1}   then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \{a, b\}=\{0,1\}=\{\nu_{0,0},\nu_{0,1}\},}   and the second part of the theorem holds. Continuing this unductive proof, let's assume that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a+b>1.}   Then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \min(a,b) > 0.}   Thus

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \max(a,b) < a+b}

But integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c := \min(a,b)}   and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d := |a-b|}   are relatively prime (see Corollary above), and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c+d\ =\ max(a,b)\ <\ a+b}

hence, by induction,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{c,d\}\ =\ \{\nu_{k,n},\nu_{k,n+1}\}}

for certain indices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\in\mathbb{Z}_+}   and non-negative Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n<2^k.}   Furthermore:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a,b\}\ =\ \{\min(a,b), \max(a,b)\}}

It follows that one of the two options holds:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a,b\}\ =\ \{\nu_{k+1,2\cdot n},\nu_{k+1,2\cdot n+1}\}}

or

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a,b\}\ =\ \{\nu_{k+1,2\cdot n+1},\nu_{k+1,2\cdot n+2}\}}

End of proof

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max_{\quad 0\le n \le 2^k}\nu_{k,n}\ =\ F_{k+1}}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ F_r}   is the r-th Fibonacci number.

Matrix monoid Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{SO}(\mathbb{Z}_+, 2)}

Definition 1  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{SO}(\mathbb{Z}_+, 2)}   is the set of all matrices

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M\ :=\ \left[\begin{array}{cc}a & b\\ c & d\end{array}\right]}

such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a,b,c,d\in\mathbb{Z}_+,}   and  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \det(M) = 1,}   where  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \det(M) := a\cdot b - c\cdot d.}

Obviously, the identity matrix

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{I}\ :=\ \left[\begin{array}{cc}1 & 0\\ 0 & 1\end{array}\right]}

belongs to   Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{SO}(\mathbb{Z}_+, 2).}   Furthermore,  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{SO}(\mathbb{Z}_+, 2)}   is a monoid with respect to the matrix multiplication.

Example  The left matrix and the right matrix are defined respectively as follows:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}\ :=\ \left[\begin{array}{cc}1 & 1\\ 0 & 1\end{array}\right]}   and   Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{R}\ :=\ \left[\begin{array}{cc}1 & 0\\ 1 & 1\end{array}\right]}

Obviously Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mathcal{L},\mathcal{R}\in \mathit{SO}(\mathbb{Z}_+,2).}   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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M\cdot \mathcal{L}\ =\ \left[\begin{array}{cc}a & a+b\\ c & c+d\end{array}\right]}

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M\cdot \mathcal{R}\ =\ \left[\begin{array}{cc}a+b & b\\ c+d & d\end{array}\right]}

Definition 2  Vectors

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[\begin{array}{cc}a\\ c\end{array}\right]}     and     Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[\begin{array}{cc}b\\ d\end{array}\right]}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a,b,c,d\in\mathbb{Z}_+,}   are called neighbors (in that order)   Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Leftarrow:\Rightarrow}   matrix formed by these vectors

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M\ :=\ \left[\begin{array}{cc}a & b\\ c & d\end{array}\right]}

belongs to  Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{SO}(\mathbb{Z}_+, 2).}   Then the left (resp. right) column is called the left (resp. right) neighbor.