- 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 .
How many elements are in ?
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, .
Show that for any two fractions it holds that . Then show that for two neighbours in the equality holds.
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.
Let be three neighbours in . Show that .
Will be added later.
Show that the sequence of denominators of elements of is palindromatic.
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 .
Prove Dirichlet’s theorem: Let . Then there exist infinitely many fractions such that .
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.
Draw the sequence of denominators of for .
Check the Wiki post for similar pictures.