Number theory/Signed Articles/Elementary diophantine approximations: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Wlodzimierz Holsztynski
imported>John Stephenson
m (John Stephenson moved page WYA:Elementary diophantine approximations to Number theory/Signed Articles/Elementary diophantine approximations without leaving a redirect: article from old initiative)
 
(68 intermediate revisions by 2 users not shown)
Line 6: Line 6:


How well can real numbers (all of them or the special ones) be approximated by rational numbers? A typical Diophantine approximation result states:
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
'''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</math>&nbsp; is rational &nbsp; <math>\Leftrightarrow</math> &nbsp; there exists a real number C > 0 such that


:::<math>|a - \frac{x}{y}| > \frac{C}{y}</math>
:::<math>\left|a - \frac{x}{y}\right| > \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>
for arbitrary integers <math>\ (x,y)</math>&nbsp; such that <math>\ y>0</math>&nbsp; and <math>\ a\ne \frac{x}{y};</math>


* ([[Adolph Hurwitz]]) &nbsp; <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
* ([[Adolph Hurwitz]]) &nbsp; <math>\ a</math>&nbsp; is irrational &nbsp; <math>\Leftrightarrow</math> &nbsp; there exist infinitely many pairs of integers <math>\ (x,y)</math>&nbsp; such that <math>\ y>0</math>&nbsp; and
 
:::<math>\left|a - \frac{x}{y}\right| < \frac{1}{\sqrt{5}\cdot y^2}.</math>
 


:::<math>|a - \frac{x}{y}| < \frac{1}{\sqrt{5}\cdot y^2}.</math>
'''Remark'''&nbsp; Implication &nbsp; <math>\Leftarrow</math> &nbsp; of the first part of the theorem is a simple and satisfaction bringing exercise.


== Notation ==
== Notation ==
Line 43: Line 47:
== The method of neighbors and median ==
== 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 simplicity 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;&nbsp;fully crisp notions will be developed in the next sections, they will involve 2-dimensional vectors and 2x2 matrices. This section is still introductory. It is supposed to provide quick insight into the topic.
In this section we will quickly obtain some results about approximating irrational numbers by rational. 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;&nbsp;fully crisp notions will be developed in the next sections, they will involve 2-dimensional vectors and 2x2 matrices. This section is still introductory. It is supposed to provide quick insight into the topic.
 
=== Definitions ===
   
   
Fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with integer numerators and natural denominators, are called '''neighbors''' (in the given order) &nbsp; <math>\Leftarrow:\Rightarrow</math>
Fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with integer numerators and natural denominators, are called '''neighbors''' (in the given order) &nbsp; <math>\Leftarrow:\Rightarrow</math>
Line 53: Line 59:
* If &nbsp;<math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d}</math>&nbsp; are neighbors then&nbsp; <math>\ a\cdot b\ge 0</math> &nbsp; ( i.e. &nbsp;<math>\frac{a}{c}\cdot \frac{b}{d}\ \ge  0</math> ).
* If &nbsp;<math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d}</math>&nbsp; are neighbors then&nbsp; <math>\ a\cdot b\ge 0</math> &nbsp; ( i.e. &nbsp;<math>\frac{a}{c}\cdot \frac{b}{d}\ \ge  0</math> ).


* Let <math>\ a,b,c,d\in\mathbb{N}.</math> &nbsp; Fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d}</math>&nbsp; are neighbors &nbsp; <math>\Leftrightarrow</math> &nbsp; fractions <math>\frac{d}{b}</math>&nbsp; and <math>\frac{c}{a}</math>&nbsp; are neighbors.
* Let <math>\ a,b,c,d\in\mathbb{N}.</math> &nbsp; Fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d}</math>&nbsp; are neighbors &nbsp; <math>\Leftrightarrow</math> &nbsp; fractions <math>\frac{d}{b}</math>&nbsp; and <math>\frac{c}{a}</math>&nbsp; are neighbors &nbsp; <math>\Leftrightarrow</math> &nbsp; fractions <math>\frac{-b}{d}</math>&nbsp; and <math>\frac{-a}{c}</math>&nbsp; are neighbors.
 


'''Examples:'''
'''Examples:'''
Line 64: Line 71:


::: <math>\frac{a}{c}\ >\ x\ >\ \frac{b}{d}</math>&nbsp;
::: <math>\frac{a}{c}\ >\ x\ >\ \frac{b}{d}</math>&nbsp;
'''Definition'''&nbsp; A pair of neighboring fractions <math>\left(\frac{a}{c},\frac{b}{d}\right),</math>&nbsp; with integer numerators and natural denominators, is called a ''top pair'' &nbsp; <math>\Leftarrow:\Rightarrow\ c > d.</math> &nbsp; Otherwise it is called a ''bottom pair''.
Thus now we have notions of top/bottom neighbors and of top/bottom pairs of neighbors.
* Let&nbsp; <math>\left(\frac{a}{c},\frac{b}{d}\right),</math>&nbsp; be a pair of neighbors. Then&nbsp; <math>\left(\frac{a}{c},\frac{a+b}{c+d}\right)</math>&nbsp; is a top pair of neighbors, and&nbsp; <math>\left(\frac{a+b}{c+d},\frac{b}{d}\right)</math>&nbsp; is a bottom pair of neighbors.
&nbsp;


=== First results ===
=== First results ===


'''Theorem'''&nbsp; Let fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with integer numerators and natural denominators, be neighbors. Then
'''Theorem'''&nbsp; Let fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with integer numerators and natural denominators, be neighbors. Then
:* if integers <math>\ t>0</math>&nbsp; and <math>\ s</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>
:* if integers <math>\ t>0</math>&nbsp; and <math>\ s</math>&nbsp; are such that &nbsp; <math>\ \frac{a}{c} > \frac{s}{t} > \frac{b}{d},</math> &nbsp; then &nbsp; <math>t \ge c+d;</math>


:* the '''median''' &nbsp;<math>\frac{a+b}{c+d}</math>&nbsp; is a bottom neighbor of &nbsp;<math>\frac{a}{c},</math>&nbsp; and a top neighbor of&nbsp; <math>\frac{b}{d};</math>&nbsp;
:* the '''median''' &nbsp;<math>\frac{a+b}{c+d}</math>&nbsp; is a bottom neighbor of &nbsp;<math>\frac{a}{c},</math>&nbsp; and a top neighbor of&nbsp; <math>\frac{b}{d};</math>&nbsp;
Line 78: Line 94:
:and
:and


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




Line 95: Line 111:


which is the first part of our theorem.
which is the first part of our theorem.


The second part of the theorem is obtained by a simple calculation, straight from the definition of the neighbors.
The second part of the theorem is obtained by a simple calculation, straight from the definition of the neighbors.


the first inequality of the third part of the theorem is instant:
 
The first inequality of the third part of the theorem is instant:


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


Next, either
Next,


:<math>\frac{a}{c}\ >\ x\ >\ \frac{a+b}{c+d}</math>
or
:<math>\frac{a+b}{c+d}\ >\ x\ >\ \frac{b}{d}</math>


and we get the respective required inequality in each case:
:::<math>\left(\frac{1}{c}-\frac{1}{d}\right)^2\ \ge\ 0</math>
 
hence
 
::<math>\frac{1}{2\cdot c^2}+\frac{1}{2\cdot d^2}\ \ge\ \frac{1}{c\cdot d}\ =\ \frac{a}{c}-\frac{b}{d}</math>
 
 
::::<math> =\ \left|\mathit{Span}(\frac{a}{c},\frac{b}{d})\right|</math>
 
and
 
::<math>\frac{b}{d}+\frac{1}{2\cdot d^2}\ \ge\ \frac{a}{c}-\frac{1}{2\cdot c^2}</math>


::<math>\frac{a}{c}-x\ <\ \frac{1}{c\cdot (c+d)}\ \le\ \frac{1}{c\cdot (c+1)}</math>
i.e.


or, respectively,
<math>\mathit{Span}\left(\frac{a}{c},\frac{a}{c}-\frac{1}{2\cdot c^2}\right)\ \cup\ \mathit{Span}\left(\frac{b}{d}+\frac{1}{2\cdot d^2},\frac{b}{d}\right)\ \backslash\ \mathbb{Q}\ \supseteq\  \mathit{Span}\left(\frac{a}{c},\frac{b}{d}\right)\ \backslash\ \mathbb{Q}</math>


::<math>x-\frac{b}{d}\ <\ \frac{1}{d\cdot (c+d)}\ \le\ \frac{1}{d\cdot (d+1)}</math>


'''End of proof'''
'''End of proof'''
'''Corollary'''&nbsp; Let fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with integer numerators and natural denominators, be neighbors. Then, if integers <math>\ t>0</math>&nbsp; and <math>\ s</math>&nbsp; are such that &nbsp; <math>\ \frac{a}{c} > \frac{s}{t} > \frac{b}{d},</math> &nbsp; then either
* <math>s=a+b\quad\and\quad t=c+d;</math>
or
* <math>t\ \ge\ c+d+\min(c,d)\ >\ c+d</math>


&nbsp;
&nbsp;


=== Squeezing irrational numbers between neighbors ===
=== Hurwitz theorem ===
 
:Let &nbsp;<math>\ x\in \mathbb{R}</math>&nbsp; be an arbitrary irrational number. Then
 
::::<math>\left|x-\frac{s}{t}\right|\ <\ \frac{1}{\sqrt{5}\cdot t^2}</math>
 
:for infinitely many different <math>\ s,t\in\mathbb{Z} \backslash \{0\}.</math>


Let <math>\ x > 0</math>&nbsp; be an irrational number, We may always squeeze it between the extremal neighbours:


:::<math>\frac{1}{0}\ >\ x\ >\ \frac{0}{1}</math>
==== Lemma 1 ====


But if you don't like infinity (on the left above) then you may do one of the two things:
Let&nbsp; <math>\ c,d\in\mathbb{N}.</math>&nbsp; Let&nbsp; <math>\ C:=c+d.</math>&nbsp; Then:


:<math>x > 1\quad\quad\Rightarrow\quad\quad\frac{n+1}{1} > x > \frac{n}{1}</math>


:::<math>c^2-\sqrt{5}\!\cdot\! c\!\cdot\! d+d\,^2\ >\ 0</math>
or
or
:::<math>C\,^2-\sqrt{5}\cdot\! C\!\cdot\! d+d\,^2\ >\ 0</math>
'''Proof of lemma 1'''&nbsp; It's easy to show that&nbsp; <math>\sqrt{2}\cdot c \ne \sqrt{3-\sqrt{5}}\cdot d.</math>&nbsp; Thus the square of&nbsp; <math>\ X := \sqrt{2}\cdot c - \sqrt{3-\sqrt{5}}\cdot d</math>&nbsp; is positive. Now,
:::<math>\sqrt{2}\cdot \sqrt{3-\sqrt{5}}\ =\ \sqrt{5}-1</math>
which means that we may write&nbsp; <math>\ X^2</math>&nbsp; as follows:
:<math>2\!\cdot\! c^2\ -\ 2\!\cdot\!(\sqrt{5}-1)\cdot c\!\cdot\! d\ +\ (3-\sqrt{5})\!\cdot\! d\,^2\ >\ 0</math>
i.e.
:<math>(c^2-\sqrt{5}\cdot c\cdot d+d^2)\ +\ (C^2-\sqrt{5}\cdot C\cdot d+d^2)\ >\ 0</math>
and lemma 1 follows.&nbsp; '''End of proof'''
==== Lemma 2 ====
Let&nbsp; <math>\ a,b\in\mathbb{Z}</math>&nbsp; and&nbsp; <math>\ c,d\in\mathbb{N}.</math>&nbsp; Let&nbsp; <math>\ A:=a+b</math>&nbsp; and&nbsp; <math>\ C:=c+d.</math>&nbsp; Furthermore, let fractions&nbsp; <math>\frac{a}{c},\frac{b}{d},</math>&nbsp; be neighbors, and let:
:::<math>\frac{A}{C}\ >\ x\ >\ \frac{b}{d}</math>
where&nbsp;<math>\ x</math>&nbsp; is real. Then one of the following three inequalities holds:
:::* <math>0\ <\ \frac{a}{c}-x\ <\ \frac{1}{\sqrt{5}\cdot c^2}</math>
:::* <math>0\ <\ \frac{A}{C}-x\ <\ \frac{1}{\sqrt{5}\cdot C^2}</math>
:::* <math>0\ <\ x-\frac{b}{d}\ <\ \frac{1}{\sqrt{5}\cdot d^2}</math>


:<math>x < 1\quad\quad\Rightarrow\quad\quad\frac{1}{n} > x > \frac{1}{n+1}</math>


'''Proof'''&nbsp; There are two cases along the inequalities of Lemma 1. Let's assume the first one, which is equivalent to:


where in each of these two cases&nbsp; <math>\ n\in \mathbb{N}</math> &nbsp; is a respective unique positive integer.


It was mentioned in the previous section ('''''First results''''') that if fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with positive (or non-negative) integer numerators and denominators are neighbors then also the top and the bottom (''bot'' &nbsp;for short) pair:
:<math>\frac{1}{\sqrt{5}\cdot c^2} + \frac{1}{\sqrt{5}\cdot d\,^2}\ >\ \frac{1}{c\cdot d}\ =\ \frac{a}{c}-\frac{b}{d}\ =\ \left|\mathit{Span}\left(\frac{a}{c},\frac{b}{d}\right)\right|</math>


*<math>\mathit{top}\!\left(\frac{a}{c},\frac{b}{d}\right)\ :=\ \left(\frac{a}{c},\frac{a+b}{b+d}\right)</math>


and
Thus


*<math>\mathit{bot}\!\left(\frac{a}{c},\frac{b}{d}\right)\ :=\ \left(\frac{a+b}{c+d},\frac{b}{d}\right)</math>


::<math>\frac{b}{d}+\frac{1}{\sqrt{5}\cdot d\,^2}\ >\ \frac{a}{c}-\frac{1}{\sqrt{5}\cdot c^2}</math>


are both pairs of neighbors.


Let <math>\ A_0</math>&nbsp; be a pair of neighbors, and <math>\ x\in \mathit{Span}(A_0)</math> &mdash; an irrational number. Assume that pairs of neighbors <math>\ A_0,\dots,A_{n-1}</math>&nbsp; are already defined, and that they squeeze <math>\ x,</math> i.e. that <math>\ x\in\mathit{Span}(A_k)</math>&nbsp; for each <math>\ k=0,\dots,n-1.</math>&nbsp; Then we define <math>\ A_n</math>&nbsp; as the one of the two pairs: <math>\ \mathit{top}(A_{n-1})</math> &nbsp;or&nbsp; <math>\ \mathit{bot}(A_{n-1}),</math> &nbsp;which squeezes <math>\ x.</math>&nbsp; Thus for every positive irrational number we have obtained an infinite sequence of pairs of neighbors, each squeezing the given irrational number more and more. Thus for arbitrary irrational <math>\ x</math>&nbsp; there exist fractions of integers <math>\ \frac{s}{t},</math>&nbsp; with arbitrarily large denominators, such that
which means that


:::<math>\left|x - \frac{s}{t}\right|\ <\ \frac{1}{t\cdot(t+1)}</math>
::<math>\mathit{Span}\left(\frac{a}{c},\frac{a}{c}-\frac{1}{\sqrt{5}\cdot c^2}\right)\ \cup\ \mathit{Span}\left(\frac{b}{d}+\frac{1}{\sqrt{5}\cdot d\,^2},\frac{b}{d}\right)\ \supseteq\ \mathit{Span}\left(\frac{a}{c},\frac{b}{d}\right)</math>


(apply theorem from section '''''First results'''''). Let's get a sharper result:


First of all, since <math>\ x</math> is irrational, the direction top-bottom of the sequence of pairs of neighbors changes infinitely many times, i.e.
::::<math>\supseteq\ \mathit{Span}\left(\frac{A}{C},\frac{b}{d}\right)</math>


:<math>A_{n+1} = \mathit{top}(A_n),\quad\quad A_{n+2} = \mathit{rgt}(A_{n+1})</math>
Thus lemma 2 is proven when the first inequality of lemma 1 holds. By replacing in the above proof the lower case&nbsp; <math>\ a,c,</math>&nbsp; by the upper case&nbsp; <math>\ A,C,</math>&nbsp; we obtain the proof when the second inequality of lemma 1 holds.


'''End of proof''' (of lemma 2)


for infinitely many values of &nbsp;<math>n\in\mathbb{Z}_+,</math> &nbsp; '''and'''
==== Lemma 2' ====


:<math>A_{n+1} = \mathit{bot}(A_n),\quad\quad A_{n+2} = \mathit{lft}(A_{n+1})</math>
Let&nbsp; <math>\ a,b\in\mathbb{Z}</math>&nbsp; and&nbsp; <math>\ c,d\in\mathbb{N}.</math>&nbsp; Let&nbsp; <math>\ A:=a+b</math>&nbsp; and&nbsp; <math>\ C:=c+d.</math>&nbsp; Furthermore, let fractions&nbsp; <math>\frac{a}{c},\frac{b}{d},</math>&nbsp; be neighbors, and let:


:::<math>\frac{a}{c}\ >\ x\ >\ \frac{A}{C}</math>


for infinitely many values of &nbsp;<math>n\in\mathbb{Z}_+</math>&nbsp; as well. Thus there are infinitely many different <math>\ n</math>&nbsp; of each of the two kinds. The other two kinds (which may or may not actually occur) are described by conditions:
where&nbsp;<math>\ x</math>&nbsp; is real. Then one of the following three inequalities holds:


:<math>A_{n+1} = \mathit{top}(A_n),\quad\quad A_{n+2} = \mathit{top}(A_{n+1})</math>
:::* <math>0\ <\ x - \frac{b}{d}\ <\ \frac{1}{\sqrt{5}\cdot d\,^2}</math>


and


:<math>A_{n+1} = \mathit{bot}(A_n),\quad\quad A_{n+2} = \mathit{bot}(A_{n+1})</math>
:::* <math>0\ <\ x-\frac{A}{C} <\ \frac{1}{\sqrt{5}\cdot C^2}</math>




Let <math>\ A_n := (\frac{a}{c},\,\frac{b}{d})</math>&nbsp; be a pair of neighbors for which the top-top property above holds, i.e. for which <math>\ x</math>&nbsp; is squeezed between a pair of neighbors as follows:
:::* <math>0\ <\ \frac{a}{c}\ <\ \frac{1}{\sqrt{5}\cdot x^2}</math>


:::<math>\frac{a}{c}\ >\ x\ >\ \frac{2\cdot a+b}{2\cdot c+d}</math>


Then
'''Proof'''&nbsp; It's similar to the proof of lemma 2. Or one may apply lemma 2 to&nbsp; <math>\ x':=-x,\ a':=-b,\ b':=-a,</math>&nbsp; and&nbsp; <math>\ c':=d,\ d':=c</math>, which would provide us with the respective fraction&nbsp; <math>\frac{s'}{t'}.</math>&nbsp; Then the required&nbsp; <math>\ s,t,</math>&nbsp; are given by&nbsp; <math>s:=-s',\ t:=t'.</math>


::<math>0\ <\ \frac{a}{c}-x\ <\ \frac{1}{c\cdot(2\cdot c+d)}\ <\ \frac{1}{2\cdot c^2}</math>
'''End of proof''' (of lemma 2')


&nbsp;


Similarly, in the bot-bot case we get
==== Proof of Hurwitz theorem ====


::<math>0\ <\ x-\frac{b}{d}\ <\ \frac{1}{d\cdot(c+2\cdot d)}\ <\ \frac{1}{2\cdot d^2}</math>
When &nbsp;<math>\ x</math>&nbsp; is irrational, then it is squeezed between infinitely many different pairs of neighbors (see part two of the theorem from the '''''First results''''' section). They provide infinitely many different required fractions&nbsp; <math>\frac{s}{t}</math>&nbsp; (see lemma 2 and 2' above; but it is not claimed, nor true, that different pairs of neighbors provide different required fractions).


'''End of proof'''


Thus if the top-top or the bot-bot case holds infinitely many times then there exist infinitely many fractions of natural numbers&nbsp; <math>\frac{s}{t}</math>&nbsp; such that:
&nbsp;


::: <math>\left|x-\frac{s}{t}\right|\ <\ \frac{1}{2\cdot t^2}</math>
=== Squeezing irrational numbers between neighbors ===


On the other hand, if cases top-top and bot-bot happen only finitely many times then starting with an <math>\ n</math>&nbsp; we get an infinite alternating top-bot-top-bot-... sequence:
Let <math>\ x > 0</math>&nbsp; be an irrational number, We may always squeeze it between the extremal neighbours:


:<math>A_{n+1} = \mathit{top}(A_n),\quad A_{n+2} = \mathit{bot}(A_{n+1}),\quad A_{n+3} = \mathit{top}(A_{n+1})\quad\dots</math>
:::<math>\frac{1}{0}\ >\ x\ >\ \frac{0}{1}</math>


Then the new neighbor of the <math>\ A_{n+k}</math>&nbsp; pair (i.e. the median of the previous pair <math>\ A_{n+k-1}</math>)&nbsp; is equal to
But if you don't like infinity (on the left above) then you may do one of the two things:
 
:<math>x > 1\quad\quad\Rightarrow\quad\quad\frac{n+1}{1} > x > \frac{n}{1}</math>


::<math>e_{k}\ :=\ \frac{F_{k+1}\cdot a + F_{k}\cdot b}{F_{k+1}\cdot c + F_{k}\cdot d}</math>
or


for every <math>\ k=1,2,\dots,</math>&nbsp; where <math>\ F_{t}</math>&nbsp; are the [[Fibonacci number]]s. It is known that
:<math>x < 1\quad\quad\Rightarrow\quad\quad\frac{1}{n} > x > \frac{1}{n+1}</math>


:::<math>\lim_{k\rightarrow\infty}\frac{F_{k+1}}{F_k}\ =\ \Phi\ :=\ \frac{\sqrt{5}+1}{2}</math>
hence


::<math>x\ =\ \lim_{k\rightarrow\infty}e_k\ =\ \frac{\Phi\cdot a+b}{\Phi\cdot c+d}</math>
where in each of these two cases&nbsp; <math>\ n\in \mathbb{N}</math> &nbsp; is a respective unique positive integer.


Thus
It was mentioned in the previous section ('''''First results''''') that if fractions <math>\frac{a}{c}</math>&nbsp; and <math>\frac{b}{d},</math>&nbsp; with positive (or non-negative) integer numerators and denominators are neighbors then also the top and the bottom (''bot'' &nbsp;for short) pair:


:::<math>\frac{a}{c}-x\ =\ \frac{1}{c\cdot(\Phi\cdot c+d)}</math>
*<math>\mathit{top}\!\left(\frac{a}{c},\frac{b}{d}\right)\ :=\ \left(\frac{a}{c},\frac{a+b}{b+d}\right)</math>


and
and


:::<math>x-\frac{b}{d}\ =\ \frac{\Phi}{(\Phi\cdot c+d)\cdot d}</math>
*<math>\mathit{bot}\!\left(\frac{a}{c},\frac{b}{d}\right)\ :=\ \left(\frac{a+b}{c+d},\frac{b}{d}\right)</math>
 
 
are both pairs of neighbors.
 
Let <math>\ A_0</math>&nbsp; be a pair of neighbors, and <math>\ x\in \mathit{Span}(A_0)</math> be an irrational number. Assume that pairs of neighbors <math>\ A_0,\dots,A_{n-1}</math>&nbsp; are already defined, and that they squeeze <math>\ x,</math> i.e. that <math>\ x\in\mathit{Span}(A_k)</math>&nbsp; for each <math>\ k=0,\dots,n-1.</math>&nbsp; Then we define <math>\ A_n</math>&nbsp; as the one of the two pairs: <math>\ \mathit{top}(A_{n-1})</math> &nbsp;or&nbsp; <math>\ \mathit{bot}(A_{n-1}),</math> &nbsp;which squeezes <math>\ x.</math>&nbsp; Thus for every positive irrational number we have obtained an infinite sequence of pairs of neighbors, each squeezing the given irrational number more and more. Thus for arbitrary irrational <math>\ x</math>&nbsp; there exist fractions of integers <math>\ \frac{s}{t},</math>&nbsp; with arbitrarily large denominators, such that
 
:::<math>\left|x - \frac{s}{t}\right|\ <\ \frac{1}{\sqrt{5}\cdot t^2}</math>
 
(see section '''''Hurwitz theorem''''').
 
If cases top-top and bot-bot happen only finitely many times then starting with an <math>\ n</math>&nbsp; we get an infinite alternating top-bot-top-bot-... sequence:
 
:<math>A_{n+1} = \mathit{top}(A_n),\quad A_{n+2} = \mathit{bot}(A_{n+2}),\quad A_{n+3} = \mathit{top}(A_{n+1})\quad\dots</math>
 


If &nbsp;<math>\ d > \frac{c}{\Phi}</math>&nbsp; then
Then the new neighbor of the <math>\ A_{n+k}</math>&nbsp; pair (i.e. the median of the previous pair <math>\ A_{n+k-1}</math>)&nbsp; is equal to


::<math>0\ <\ \frac{a}{c} - x\ <\ \frac{1}{c^2}\cdot\frac{1}{\Phi+\frac{1}{\Phi}}\ =\ \frac{1}{\sqrt{5}\cdot c^2}</math>
::<math>e_{k}\ :=\ \frac{F_{k+1}\cdot a + F_{k}\cdot b}{F_{k+1}\cdot c + F_{k}\cdot d}</math>


and if &nbsp;<math>\ d < \frac{c}{\Phi},</math>&nbsp; i.e.&nbsp; <math>\ c > \Phi\cdot d,</math>&nbsp; then
for every <math>\ k=1,2,\dots,</math>&nbsp; where <math>\ F_{t}</math>&nbsp; are the [[Fibonacci number]]s, where


::<math>0\ <\ x-\frac{b}{d}\ <\ \frac{\Phi}{(\Phi^2+1)\cdot d^2}\ =\ \frac{1}{\sqrt{5}\cdot d^2}</math>
:::<math>\left(\frac{a}{c},\frac{b}{d}\right)\ :=\ A_n</math>


Since&nbsp; <math>\sqrt(5)>2,</math> and due to the earlier inequalities which have covered the top-top and the bot-bot cases, we have obtained the following theorem:
It is known that


* for arbitrary irrational number there exist infinitely many different fractions <math>\ \frac{s}{t},</math>&nbsp; with integer numerator and non-zero denominator, such that:
:::<math>\lim_{k\rightarrow\infty}\frac{F_{k+1}}{F_k}\ =\ \Phi\ :=\ \frac{\sqrt{5}+1}{2}</math>
:::<math>\left|x-\frac{s}{t}\right|\ <\ \frac{1}{2\cdot t^2}</math>
hence


However, we are close to replacing constant&nbsp; <math>\ 2</math>&nbsp; by &nbsp;<math>\sqrt{5}</math>&nbsp; in the above denominator. Let's do it:
::<math>x\ =\ \lim_{k\rightarrow\infty}e_k\ =\ \frac{\Phi\cdot a+b}{\Phi\cdot c+d}</math>


&nbsp;


=== Hurwitz theorem ===
But if our infinite alternation has started with ''bot'' :


* Let &nbsp;<math>\ x\in \mathbb{R}</math>&nbsp; be an arbitrary irrational number. Then
:<math>A_{n+1} = \mathit{bot}(A_n),\quad A_{n+2} = \mathit{top}(A_{n+2}),\quad A_{n+3} = \mathit{bot}(A_{n+1})\quad\dots</math>


:::<math>\left|x-\frac{s}{t}\right|\ <\ \frac{1}{\sqrt{5}\cdot t^2}</math>
Then we would have


for infinitely many different <math>\ s,t\in\mathbb{Z} \backslash \{0\}.</math>
::<math>x\ =\ \lim_{k\rightarrow\infty}e_k\ =\ \frac{a+\Phi\cdot b}{c+\Phi\cdot d}</math>


&nbsp;


=== Proof of Hurwitz Theorem ===
=== Another proof of Hurwitz Theorem (further insight) ===


==== Reduction to x > 0 ====
==== Reduction to x > 0 ====
Line 267: Line 353:


==== The top-top-bot case ====
==== The top-top-bot case ====
Let's consider the latter top-top-bot case. Let <math>\ \xi := \frac{d}{c}.</math>&nbsp; The squeeze by neighbors:
Let's consider the latter top-top-bot case. Let&nbsp; <math>\ \xi := \frac{d}{c}.</math>&nbsp; The squeeze by neighbors:


:::<math>\frac{a}{c}\ >\ x\ >\ \frac{2\cdot a+b}{2\cdot c+d}</math>
:::<math>\frac{a}{c}\ >\ x\ >\ \frac{2\cdot a+b}{2\cdot c+d}</math>
Line 312: Line 398:
Conclusion:
Conclusion:


  <math>0\ <\ \frac{a}{c}-x\ <\ \frac{2}{(5+2\cdot\xi)}\cdot\frac{1}{c^2}\quad\quad\Leftarrow\quad\quad x\in B</math>
  <math>0\ <\ \frac{a}{c}-x\ <\ \frac{2}{5+2\cdot\xi}\cdot\frac{1}{c^2}\quad\quad\Leftarrow\quad\quad x\in B</math>


==== Neighborhood C (first C-inequality) ====
==== Neighborhood C (first C-inequality) ====


Let&nbsp; <math>\ x\in C.</math>&nbsp; Then
Let&nbsp; <math>\ x\in C.</math>&nbsp; Then


:<math>\frac{a}{c}\ >\ \frac{3\cdot a+b}{3\cdot c+d}\ >\ \frac{5\cdot a+2\cdot b}{5\cdot c+2\cdot d}\ >\ x\ >\ \frac{7\cdot a+3\cdot b}{7\cdot c+3\cdot d}</math>
:<math>\frac{a}{c}\ >\ \frac{3\cdot a+b}{3\cdot c+d}\ >\ \frac{5\cdot a+2\cdot b}{5\cdot c+2\cdot d}\ >\ x\ >\ \frac{7\cdot a+3\cdot b}{7\cdot c+3\cdot d}</math>
Line 327: Line 414:
:<math>=\ \frac{3}{7+3\cdot\xi}\cdot\frac{1}{c^2}</math>
:<math>=\ \frac{3}{7+3\cdot\xi}\cdot\frac{1}{c^2}</math>


First C-conclusion:
<math>0\ <\ \frac{a}{c}-x\ <\ \frac{3}{7+3\cdot\xi}\cdot\frac{1}{c^2}\quad\quad\Leftarrow\quad\quad x\in C</math>
&nbsp;


==== Neighborhood D ====
==== Neighborhood D ====
Line 337: Line 431:




Let&nbsp; <math>\ C := 2\cdot c+d = (2+\xi)\cdot c.</math>&nbsp; Then
Let&nbsp; <math>\alpha := 2\cdot a+b</math> &nbsp; and &nbsp; <math>\gamma := 2\cdot c+d = (2+\xi)\cdot c.</math>&nbsp; Then
 
 
:<math>0\ <\ x-\frac{\alpha}{\gamma}\ =\ x-\frac{2\cdot a+b}{2\cdot c+d}</math>
 
:<math><\ \frac{1}{(7\cdot c+3\cdot d)\cdot(2\cdot c+d)}\ =\ \frac{1}{(7+3\cdot\xi)\cdot c\cdot\gamma}</math>
 
 
:<math>=\ \frac{2+\xi}{7+3\cdot\xi}\cdot\frac{1}{\gamma^2}</math>
 
 
Conclusion:
 
<math>0\ <\ x-\frac{\alpha}{\gamma}\ <\ \frac{2+\xi}{7+3\cdot\xi}\cdot\frac{1}{\gamma^2}\quad\quad\Leftarrow\quad\quad x\in D</math>
 
 
==== Early yield (Hurwitz Theorem) ====
 
Let's impatiently indulge ourselves in already getting some crude results from the above hard work (:-). The above three BCD-conclusions instantly imply:
 
* <math>0\ <\ \frac{a}{c}-x\ <\ \frac{2}{5}\cdot\frac{1}{c^2}\quad\quad\Leftarrow\quad\quad x\in B</math>
 
 
* <math>0\ <\ \frac{a}{c}-x\ <\ \frac{3}{7}\cdot\frac{1}{c^2}\quad\quad\Leftarrow\quad\quad x\in C</math>
 
 
*  <math>0\ <\ x-\frac{\alpha}{\gamma}\ <\ \frac{2}{7}\cdot\frac{1}{\gamma^2}\quad\quad\Leftarrow\quad\quad x\in D</math>
 
 
Since
 
:::<math>\max(\frac{2}{5},\,\frac{3}{7},\,\frac{2}{7})\ =\ \frac{3}{7}\ <\ \frac{1}{\sqrt{5}},</math>
 
each occurrence of the top-top-bot subsequence, i.e. of equalities:
 
 
:<math>A_{n+1} = \mathit{top}(A_n),\quad A_{n+2} = \mathit{top}(A_{n+1}),\quad A_{n+3} = \mathit{bot}(A_{n+2})\quad\dots</math>
 
provides a fraction&nbsp; <math>\frac{s}{t}\in \mathit{Span}(A_{n+3}),</math>&nbsp; with integer numerator and natural denominator, such that
 
:<math>\left|x-\frac{s}{t}\right|\ <\ \frac{3}{7}\cdot\frac{1}{t^2}\ <\ \frac{1}{\sqrt{5}}\cdot\frac{1}{t^2}</math>
 
 
The same is holds for every occurrence of the bot-bot-top sequence, which can be shown now mechanically by a proof similar to the proof of the top-top-bot case, or as follows: define the squeezing sequence of&nbsp; <math>\ -x</math>&nbsp; by:
 
::<math>B_n := (\frac{-b}{d},\frac{-a}{c})</math> &nbsp; &nbsp; for &nbsp; &nbsp; <math>A_n = (\frac{a}{c},\frac{b}{d})</math>
 
 
Let&nbsp; <math>\left(A_n,A_{n+1},A_{n+2},A_{n+3}\right)</math>&nbsp; be a bot-bot-top progression. Then&nbsp; <math>\left(B_n,B_{n+1},B_{n+2},B_{n+3}\right)</math>&nbsp; is a top-top-bot progression which squeezes&nbsp; <math>\ -x.</math> Thus
 
 
:<math>\left|(-x)-\frac{u}{w}\right|\ <\ \frac{3}{7}\cdot\frac{1}{w^2}\ <\ \frac{1}{\sqrt{5}}\cdot\frac{1}{w^2}</math>
 
 
for certain&nbsp; <math>\frac{u}{w}\in \mathit{Span}(B_{n+3}),</math>&nbsp; with integer numerator and natural denominator. Then&nbsp; <math>\frac{s}{t}\in\mathit{Span}(A_{n+3}),</math>&nbsp; for&nbsp; <math>\ (s,t):=(-u,w),</math>&nbsp; satisfies:
 
 
:<math>\left|x-\frac{s}{t}\right|\ <\ \frac{3}{7}\cdot\frac{1}{t^2}\ <\ \frac{1}{\sqrt{5}}\cdot\frac{1}{t^2}</math>
 
 
When another top-top-bot or bot-bot-top progression starts with a sufficiently large index&nbsp; <math>\ n',</math>&nbsp; then&nbsp; <math>\left|\mathit{Span}(A_{n'+3})\right| < \left|x-\frac{s}{t}\right|,</math>&nbsp; which means that the respective new approximation&nbsp; <math>\frac{s'}{t'}\in\mathit{Span}(A_{n'+3})</math>&nbsp; is different. It follows that if there are infinitely many progressions top-top-bot or bot-bot-bot then there are infinitely many fractions&nbsp; <math>\ \frac{s}{t},</math> which satisfy the inequality above. Thus we have obtained the following version of '''Hurwitz theorem''':
 
 
:'''Theorem'''&nbsp; Let&nbsp; <math>x\in\mathbb{R}\backslash\mathbb{Q}</math>&nbsp; be an arbitrary irrational number. Then inequality
 
:*<math>\left|x-\frac{s}{t}\right|\ <\ \frac{1}{\sqrt{5}}\cdot\frac{1}{t^2}</math>
 
:holds for infinitely many fractions&nbsp; <math>\ \frac{s}{t},</math>&nbsp; with integer numerator and natural denominator. Furthermore, if the squeezing sequence of&nbsp; <math>\ x</math> does not eventually alternate top-bot-top-bot-... till infinity, i.e. if it has infinitely many top-top or bot-bot progressions, then
 
:*<math>\left|x-\frac{s}{t}\right|\ <\ \frac{3}{7
}\cdot\frac{1}{t^2}</math>
 
:holds for infinitely many fractions&nbsp; <math>\ \frac{s}{t},</math>&nbsp; with integer numerator and natural denominator.
 
 
&nbsp;
 
==== Neighborhood C (second C-inequality) ====
 
Let&nbsp; <math>\ x\in C.</math>&nbsp; Then
 
 
:<math>\frac{5\cdot a+2\cdot b}{5\cdot c+2\cdot d}\ >\ x\ >\ \frac{7\cdot a+3\cdot b}{7\cdot c+3\cdot d}\ >\ \frac{2\cdot a+b}{2\cdot c+d}</math>
 
 
Thus, using the earlier conclusion for neighborhood <math>\ D</math>&nbsp; also for <math>\ C,</math>&nbsp; we obtain
 
 
 
:<math>0\ <\ x-\frac{\alpha}{\gamma}\ =\ x-\frac{2\cdot a+b}{2\cdot c+d}</math>
 
:<math><\ \frac{1}{(5\cdot c+2\cdot d)\cdot(7\cdot c+3\cdot d)}\ +\ \frac{2+\xi}{(7+3\cdot\xi)\cdot \gamma^2}</math>
 
 
:<math>=\ \frac{1}{(5+2\cdot\xi)\cdot(7+3\cdot\xi)}\cdot\frac{1}{c^2}\ +\ \frac{2+\xi}{(7+3\cdot\xi)\cdot \gamma^2}</math>
 
 
:<math>=\ \frac{(2+\xi)^2}{(5+2\cdot\xi)\cdot(7+3\cdot\xi)}\cdot\frac{1}{\gamma^2}\ +\ \frac{2+\xi}{(7+3\cdot\xi)\cdot \gamma^2}</math>
 
 
:<math>=\ \frac{2+\xi}{5+2\cdot\xi}\cdot\frac{1}{\gamma^2}</math>
 
 
Second C-conclusion:
 
<math>0\ <\ x-\frac{\alpha}{\gamma}\ <\ \frac{2+\xi}{5+2\cdot\xi}\cdot\frac{1}{\gamma^2}\quad\quad\Leftarrow\quad\quad x\in C</math>
 
 
==== Neigborhood C (the combined inequality) ====
 
Let:
 
:::<math>\xi_0\ :=\ \frac{\sqrt{61}-7}{6}</math>
 
Then
 
::<math>\frac{3}{7+3\cdot \xi_0}\ =\ \frac{2+\xi_0}{5+2\cdot\xi_0}\ =\ \frac{\sqrt{61}-7}{2}</math>
 
 
Thus for &nbsp;<math>\ \xi\ge\xi_0</math>:
 
 
:<math>\frac{3}{7+3\cdot \xi}\ \le\ \frac{\sqrt{61}-7}{2}</math>
 
 
and  for &nbsp;<math>\ \xi\le\xi_0</math>:
 
 
:<math>\frac{2+\xi}{5+2\cdot\xi}\ \le\ \frac{\sqrt{61}-7}{2}</math>
 


It follows that


:<math>0\ <\ x-\frac{2\cdot a+b}{C}\ =\ x-\frac{2\cdot a+b}{2\cdot c+d}</math>
* for one of the fractions&nbsp; <math>\frac{s}{t}\in\left\{\frac{a}{c},\,\frac{2\cdot a+b}{2\cdot c+d}\right\}</math>&nbsp;  the following inequality holds for every &nbsp;<math>\ x\in C:</math>


:<math><\ \frac{1}{(7\cdot c+3\cdot d)\cdot(2\cdot c+d)}\ =\ \frac{1}{(7+3\cdot\xi)\cdot c\cdot C}</math>


:::<math>\left|x-\frac{s}{t}\right|\ <\ \frac{\sqrt{61}-7}{2}</math>


:<math>=\ \frac{2+\xi}{7+3\cdot\xi}\cdot\frac{1}{C^2}</math>
(the choice of &nbsp;<math>\frac{s}{t}</math>&nbsp; depends on&nbsp; <math>\xi := \frac{d}{c}</math> ).


&nbsp;
&nbsp;
Line 524: Line 748:
and its length
and its length


:::<math>|M|\ :=\ \mathit{rat}(v)-\mathit{rat}(w)</math>
:::<math>diam(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.
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.
Line 531: Line 755:
:::<math>M\ :=\ \left[\begin{array}{cc}a & b\\ c & d\end{array}\right]\in\mathit{SO}(\mathbb{Z}_+, 2)</math>
:::<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>
then&nbsp; <math>\ diam(M) = \frac{1}{c\cdot d}</math>

Latest revision as of 08:40, 15 March 2021

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   Decimal fractions are used both as certain values, e.g. $5.85, and as approximations of the real numbers, e.g.   However, the field of all rational numbers is much richer than the ring of the decimal fractions (or of the binary fractions   which are used in the computer science). For instance, the famous approximation   has denominator 113 much smaller than 105 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   be an arbitrary real number. Then

  •   is rational     there exists a real number C > 0 such that

for arbitrary integers   such that   and

  • (Adolph Hurwitz)     is irrational     there exist infinitely many pairs of integers   such that   and


Remark  Implication     of the first part of the theorem is a simple and satisfaction bringing exercise.

Notation

  •   —   "equivalent by definition" (i.e. "if and only if");
  •   —   "equals by definition";
  •   —   "there exists";
  •   —   "for all";
  •   —   "  is an element of set ";

 

  •  —  the semiring of the natural numbers;
  •  —  the semiring of the non-negative integers;
  •  —  the ring of integers;
  •  —  the field of rational numbers;
  •  —  the field of real numbers;

 

 

  •   —   "  divides "   (i.e. );
  •  —  the greatest common divisor of integers   and

 

The method of neighbors and median

In this section we will quickly obtain some results about approximating irrational numbers by rational. 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)—this will not cause any problems; fully crisp notions will be developed in the next sections, they will involve 2-dimensional vectors and 2x2 matrices. This section is still introductory. It is supposed to provide quick insight into the topic.

Definitions

Fractions   and   with integer numerators and natural denominators, are called neighbors (in the given order)  

Fraction   is called the top neighbor of the other,   is called the bottom neighbor, and the interval   is called neighborhood; thus a neighborhood is an open interval such that its endpoints are neighbors.

  • If    and   are neighbors then    ( i.e.   ).
  • Let   Fractions   and   are neighbors     fractions   and   are neighbors     fractions   and   are neighbors.


Examples:

  • Fractions   and   are neighbors for every positive integer


  • Fractions   and   are neighbors for every positive integer

Thus it easily follows that for every positive irrational number   there exists a pair of neighbors    and    with positive numerators and denominators, such that:

 

Definition  A pair of neighboring fractions   with integer numerators and natural denominators, is called a top pair     Otherwise it is called a bottom pair.


Thus now we have notions of top/bottom neighbors and of top/bottom pairs of neighbors.

  • Let    be a pair of neighbors. Then    is a top pair of neighbors, and    is a bottom pair of neighbors.

 

First results

Theorem  Let fractions   and   with integer numerators and natural denominators, be neighbors. Then

  • if integers   and   are such that     then  
  • the median    is a bottom neighbor of    and a top neighbor of   
  • let    be an irrational number such that     then
and
      or      


Proof   Let     then

    and    

and

Multiplying this inequality by  gives

which is the first part of our theorem.


The second part of the theorem is obtained by a simple calculation, straight from the definition of the neighbors.


The first inequality of the third part of the theorem is instant:

Next,


hence


and

i.e.


End of proof


Corollary  Let fractions   and   with integer numerators and natural denominators, be neighbors. Then, if integers   and   are such that     then either

or

 

Hurwitz theorem

Let    be an arbitrary irrational number. Then
for infinitely many different


Lemma 1

Let    Let    Then:


or


Proof of lemma 1  It's easy to show that    Thus the square of    is positive. Now,



which means that we may write    as follows:


i.e.


and lemma 1 follows.  End of proof

Lemma 2

Let    and    Let    and    Furthermore, let fractions    be neighbors, and let:

where   is real. Then one of the following three inequalities holds:




Proof  There are two cases along the inequalities of Lemma 1. Let's assume the first one, which is equivalent to:



Thus



which means that


Thus lemma 2 is proven when the first inequality of lemma 1 holds. By replacing in the above proof the lower case    by the upper case    we obtain the proof when the second inequality of lemma 1 holds.

End of proof (of lemma 2)

Lemma 2'

Let    and    Let    and    Furthermore, let fractions    be neighbors, and let:

where   is real. Then one of the following three inequalities holds:




Proof  It's similar to the proof of lemma 2. Or one may apply lemma 2 to    and  , which would provide us with the respective fraction    Then the required    are given by 

End of proof (of lemma 2')

 

Proof of Hurwitz theorem

When    is irrational, then it is squeezed between infinitely many different pairs of neighbors (see part two of the theorem from the First results section). They provide infinitely many different required fractions    (see lemma 2 and 2' above; but it is not claimed, nor true, that different pairs of neighbors provide different required fractions).

End of proof

 

Squeezing irrational numbers between neighbors

Let   be an irrational number, We may always squeeze it between the extremal neighbours:

But if you don't like infinity (on the left above) then you may do one of the two things:

or


where in each of these two cases    is a respective unique positive integer.

It was mentioned in the previous section (First results) that if fractions   and   with positive (or non-negative) integer numerators and denominators are neighbors then also the top and the bottom (bot  for short) pair:

and


are both pairs of neighbors.

Let   be a pair of neighbors, and be an irrational number. Assume that pairs of neighbors   are already defined, and that they squeeze i.e. that   for each   Then we define   as the one of the two pairs:  or   which squeezes   Thus for every positive irrational number we have obtained an infinite sequence of pairs of neighbors, each squeezing the given irrational number more and more. Thus for arbitrary irrational   there exist fractions of integers   with arbitrarily large denominators, such that

(see section Hurwitz theorem).

If cases top-top and bot-bot happen only finitely many times then starting with an   we get an infinite alternating top-bot-top-bot-... sequence:


Then the new neighbor of the   pair (i.e. the median of the previous pair )  is equal to

for every   where   are the Fibonacci numbers, where

It is known that

hence


But if our infinite alternation has started with bot :

Then we would have

 

Another proof of Hurwitz Theorem (further insight)

Reduction to x > 0

Since

it is enough to prove Hurwitz theorem for positive irrational numbers only.

Two cases

Consider the sequence   of pairs of neighbors, which squeeze   from the previous section. The case of the infinite alternation top-bot-top-bot-... has been proved already. In the remaining case the bot-bot-top or top-top-bot progressions appear infinitely many times, i.e. there are infinitely many non-negative integers   for which

or


holds, where

 

The top-top-bot case

Let's consider the latter top-top-bot case. Let    The squeeze by neighbors:

shows that

This inequality provides the first insight (otherwise, we are not going to use it), so it deserves to be written cleanly as an implication:


The relevant neighborhoods

Consider the next two pairs of neighbors, pair   and pair   which squeeze   The relevant neighborhoods are:




 

Neighborhood B

Let    Then


and


Conclusion:


Neighborhood C (first C-inequality)

Let    Then



Thus using the calculation for neighborhood B also for C, we get


First C-conclusion:


 

Neighborhood D

Let    i.e.



Let    and     Then




Conclusion:



Early yield (Hurwitz Theorem)

Let's impatiently indulge ourselves in already getting some crude results from the above hard work (:-). The above three BCD-conclusions instantly imply:




Since

each occurrence of the top-top-bot subsequence, i.e. of equalities:


provides a fraction    with integer numerator and natural denominator, such that


The same is holds for every occurrence of the bot-bot-top sequence, which can be shown now mechanically by a proof similar to the proof of the top-top-bot case, or as follows: define the squeezing sequence of    by:

    for    


Let    be a bot-bot-top progression. Then    is a top-top-bot progression which squeezes  Thus



for certain    with integer numerator and natural denominator. Then    for    satisfies:



When another top-top-bot or bot-bot-top progression starts with a sufficiently large index    then    which means that the respective new approximation    is different. It follows that if there are infinitely many progressions top-top-bot or bot-bot-bot then there are infinitely many fractions  which satisfy the inequality above. Thus we have obtained the following version of Hurwitz theorem:


Theorem  Let    be an arbitrary irrational number. Then inequality
holds for infinitely many fractions    with integer numerator and natural denominator. Furthermore, if the squeezing sequence of  does not eventually alternate top-bot-top-bot-... till infinity, i.e. if it has infinitely many top-top or bot-bot progressions, then
holds for infinitely many fractions    with integer numerator and natural denominator.


 

Neighborhood C (second C-inequality)

Let    Then



Thus, using the earlier conclusion for neighborhood   also for   we obtain






Second C-conclusion:



Neigborhood C (the combined inequality)

Let:

Then


Thus for  :



and for  :



It follows that

  • for one of the fractions    the following inequality holds for every  


(the choice of    depends on  ).

 

Divisibility

Definition  Integer   is divisible by integer    

Symbolically:

   


When   is divisible by   then we also say that   is a divisor of   or that   divides

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

 

 

Remark  The above three properties show that the relation of divisibility is a partial order in the set of natural number    and also in   is its minimal, and   is its maximal element.

 

Relatively prime pairs of integers

Definition  Integers   and   are relatively prime       is their only common positive divisor.

  • Integers   and   are relatively prime  
  •   is relatively prime with every integer.
  • If   and   are relatively prime then also   and    are relatively prime.


Theorem 1  If   are such that two of them are relatively prime and   then any two of them are relatively prime.
Corollary  If   and   are relatively prime then also   and    are relatively prime.


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

as follows:

  •     and    
  •   for 
  •   for 

for every  


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,   and   is relatively prime.
  • For every pair of relatively prime, non-negative integers   and   there exist indices   and non-negative   such that:

Proof  Of course the pair

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

Now let   and   be a pair of relatively prime, non-negative integers. If   then   and the second part of the theorem holds. Continuing this unductive proof, let's assume that   Then   Thus

But integers   and   are relatively prime (see Corollary above), and

hence, by induction,

for certain indices   and non-negative   Furthermore:

It follows that one of the two options holds:

or

End of proof


Let's note also, that


where   is the r-th Fibonacci number.

Matrix monoid

Definition 1    is the set of all matrices

such that   and    where    Such matrices (and their columns and rows) will be called special.

  • If

then    and each of the columns and rows of M, i.e. each of the four pairs    is relatively prime.


Obviously, the identity matrix

belongs to     Furthermore,    is a monoid with respect to the matrix multiplication.

Example  The upper matrix and the lower matrix are defined respectively as follows:

  and  

Obviously   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:

and


Definition 2  Vectors

    and    

where   are called neighbors (in that order)     matrix formed by these vectors

belongs to    Then the left (resp. right) column is called the left (resp. right) neighbor.

Rational representation

With every vector

such that   let's associate a rational number

Also, let

for

Furthermore, with every matrix    let's associate the real open interval

and its length

where   is the left, and   is the right column of matrix M — 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

then