# WYA: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.

## Contents

- 1 Introduction
- 2 Notation
- 3 The method of neighbors and median
- 3.1 Definitions
- 3.2 First results
- 3.3 Hurwitz theorem
- 3.4 Squeezing irrational numbers between neighbors
- 3.5 Another proof of Hurwitz Theorem (further insight)
- 3.5.1 Reduction to x > 0
- 3.5.2 Two cases
- 3.5.3 The top-top-bot case
- 3.5.4 The relevant neighborhoods
- 3.5.5 Neighborhood B
- 3.5.6 Neighborhood C (first C-inequality)
- 3.5.7 Neighborhood D
- 3.5.8 Early yield (Hurwitz Theorem)
- 3.5.9 Neighborhood C (second C-inequality)
- 3.5.10 Neigborhood C (the combined inequality)

- 4 Divisibility
- 5 Relatively prime pairs of integers
- 6 Matrix monoid
- 7 Rational representation

## 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 10^{5} 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

- the

- 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