imported>Wlodzimierz Holsztynski |
imported>Wlodzimierz Holsztynski |
Line 138: |
Line 138: |
|
| |
|
| '''End of proof''' | | '''End of proof''' |
| | |
| | |
| | * <math>\max_{\quad 0\le n \le 2^k}\nu_{k,n}\ =\ F_{k+1}</math> |
| | |
| | |
| | where <math>\ F_r</math> is the r-th [[Fibonacci number]]. |
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 if and only if there exists a real number C > 0 such that
![{\displaystyle |a-{\frac {x}{y}}|>{\frac {C}{y}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/669b355298532a783ebaab7c42a3835217876c8f)
for arbitrary integers
such that
and
is irrational if and only if there exist infinitely many pairs of integers
such that
and
![{\displaystyle |a-{\frac {x}{y}}|<{\frac {1}{{\sqrt {5}}\cdot y^{2}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de1182bc3f3b7b3186aacfa1719c7821cdb7aeb2)
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
";
— the greatest common divisor of integers
and ![{\displaystyle \ b.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3658546c70c97d710581246f2c4952e8d6997cb2)
Divisibility
Definition Integer
is divisible by integer
Symbolically:
![{\displaystyle \exists _{c\in \mathbb {Z} }\ a=b\cdot c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03c81b33594cf83ba2e5b7cd4b889ade2d3c1bd3)
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 ![{\displaystyle \ 1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cadcfff0f7aabf708593c25995db8a10af8f2535)
- Every integer is divisible by
(and by
).
![{\displaystyle a|b\ \Rightarrow (-a|b\ \land \ a|\!-\!\!b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e30ed473d47351c0ec679fc7510ffbaa8e1decde)
![{\displaystyle a|b>0\ \Rightarrow a\leq b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f646f9cdd4cfe3c175c6c88f7206376027e2cf2b)
![{\displaystyle a|a\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/255a27b35dd78e2626fce6914bdda12257d66807)
![{\displaystyle (a|b\ \land \ b|c)\ \Rightarrow \ a|c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6c55b5c611b91641fd56fcd938b7d360823d691)
![{\displaystyle (a|b\ \land \ b|a)\ \Rightarrow \ |a|=|b|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1bd7d2f3c0c6a3ac75bdf4fa3f8ac312b04d6a6)
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.
![{\displaystyle (a|b\ \land \ a|c)\ \Rightarrow \ (a\,|\,b\!\cdot \!d\ \land \ a\,|\,b\!+\!c\ \land \ a\,|\,b\!-\!c)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/751c84610824a2406fc0e64db460198c3e72070a)
Relatively prime pairs of integers
Definition Integers
and
are relatively prime
is their only common positive divisor.
- Integers
and
are relatively prime ![{\displaystyle \Leftrightarrow \ |x|=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6063982dda364a20a30bfcce524f4ce54fda8837)
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:
![{\displaystyle (\nu _{k,n}:k\in \mathbb {Z} _{+},\ 0\leq n\leq 2^{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9a78813dedc946a68507b5cc1f7c2315703d629)
as follows:
and ![{\displaystyle \nu _{0,1}:=1\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/63b4021472755c6b53856888a7d0ab52e915a089)
for ![{\displaystyle 0\leq n\leq 2^{k}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc256387ccca68a6686de17cb969fbef308f082b)
for ![{\displaystyle 0\leq n<2^{k}\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e2287f7be5314bb339a42b66ddbf060a2632322)
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:
![{\displaystyle \{a,b\}\ =\ \{\nu _{k,n},\nu _{k,n+1}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b28a3629723690a749ba0465275ff08a6a245c6)
Proof Of course the pair
![{\displaystyle \{\nu _{0,0},\nu _{0,1}\}\ =\ \{0,1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/070bcdcf7cb64763fe1196240e7cbe3c8bb890b3)
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
![{\displaystyle \ \max(a,b)<a+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6370fe61a81edcc3fb378de582bb1fd66ba532e6)
But integers
and
are relatively prime (see Corollary above), and
![{\displaystyle c+d\ =\ max(a,b)\ <\ a+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26e1002e93533dd91eb99a941d992ad280fb4bf2)
hence, by induction,
![{\displaystyle \{c,d\}\ =\ \{\nu _{k,n},\nu _{k,n+1}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdfcee9a88c41727a294fe6140cef17100f45e48)
for certain indices
and non-negative
Furthermore:
![{\displaystyle \{a,b\}\ =\ \{\min(a,b),\max(a,b)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e765d368991ecb27572ded2efcb29bf041f39f88)
It follows that one of the two options holds:
![{\displaystyle \{a,b\}\ =\ \{\nu _{k+1,2\cdot n},\nu _{k+1,2\cdot n+1}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1531f97030d2cecdd7ce42e3e367b9e9f55af032)
or
![{\displaystyle \{a,b\}\ =\ \{\nu _{k+1,2\cdot n+1},\nu _{k+1,2\cdot n+2}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a671e28c40bf9ad4b426d62e011a53d84f3b6273)
End of proof
![{\displaystyle \max _{\quad 0\leq n\leq 2^{k}}\nu _{k,n}\ =\ F_{k+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed567fd5338e27b9d3247a1d3599fb2d89df56bc)
where
is the r-th Fibonacci number.