### Useful links

- Wiki post on Farey sequnce

We already know that every rational number can be written as a fraction with integer numerator and denominator, and its decadic expension is either finite or periodic. On the other hand, an irrational number has infinite and non-periodic decadic expansion. Therefore, for example, irrationals cannot be precisely represented in our computers. However, we can use different methods to approximate such numbers with a certain precision.

What do we mean by “approximating”? Well, we can use analytic point of view: for a given (number we want to approximate) and an (tolerable mistake), we want to find some , such that . Recall that the set of rationals is dense in . Here, we will present two ways of finding such . Another option, using continued fractions, will be covered in different posts on this site.

## Approximations with a fixed denominator

Consider some . Therefore, . We can divide the real line into intervals . Any belongs to exactly one such interval. We set to be the closest endpoint.

What is the distance between and ? It is definitely at most half of the interval, i.e., at most . So,

We see that for every , and for every , there exists some , such that .

## Approximations with a bounded denominator – Farey sequence

We can get better approximations if we consider bounded denominators instead of fixed. Assume that, WLOG, – otherwise, we would consider decimal part .

**Definition:** Let . Consider all fractions , such that and . Having them arranged we denote them . A sequence (or a list) is called the **Farey sequence of order** .

**Example:** Farey sequence of order is the following:

Farey sequence has a several interesting properties. The crucial one is so called Cauchy’s theorem.

**Theorem(Cauchy):** Let be two neighbours of . Then .

Proof: , since . By Bezout theorem there exist some such that . Observe that if is a solution of , then is also a solution for any :

For a suitable there must exist a solution , such that (in particular, y_1>0 and y_1+b>n). We will show that . Let us denote the equation by .

From it follows that

also implies that : any common divisor of and divides , hence, it must be . So, we have shown that the denominator of is less then or equal to and . However, the smallest such fraction is, by definition, , therefore .

For the sake of contradiction, assume that the inequality is strict, i.e., . Then we have

where the inequality comes from the fact that impies . Similarly, we have

Adding these two together, we receive

It follows that , hence , which is a contradiction with the assumption that

We conclude that . Since both of the fractions are in the base form, we also have that , and, finally, the desired statement now follows from .

## Exercises

#### Exercise 1

How many elements are in ?

#### Solution

We know that, for any , there is exactly of elements of with a denominator , because of the GCD condition. Plus there are two more elements and . Together, .

#### Exercise 2

Show that for any two fractions it holds that . Then show that for two neighbours in the equality holds.

#### Solution

We have already seen this in the proof of Cauchy’s theorem, and the same works in general. For the second part – just use the theorem.

#### Exercise 3

Let be three neighbours in . Show that .

#### Solution

Will be added later.

#### Exercise 4

Show that the sequence of denominators of elements of is palindromatic.

#### Solution

Proceed by induction. For the statement is obvious. Suppose it holds for and we will prove it for . We are adding fractions with denominator equal to to . By the previous exercise we know that we add some between neighbours and if and only if . Since we assume the statement for to hold, we can also add a fraction to the opposite side, where there are two neighbours and .

#### Exercise 5

Prove **Dirichlet’s theorem**: Let . Then there exist infinitely many fractions such that .

#### Solution

Let be irrational, , and two neighbours in such that . If , then, by Cauchy’s theorem,

If , then similarly, . The distance between two neighbours in is at most , so by increasing , we get infinitely many desired fractions.

#### Exercise 6

Draw the sequence of denominators of for .

#### Solution

Check the Wiki post for similar pictures.