Farey sequence

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 \alpha\in\mathbb{R} (number we want to approximate) and an \varepsilon>0 (tolerable mistake), we want to find some \frac{p}{q}\in\mathbb{Q}, such that \left|\alpha-\frac{p}{q}<\varepsilon\right|. Recall that the set of rationals is dense in \mathbb{R}. Here, we will present two ways of finding such \frac{p}{q}. Another option, using continued fractions, will be covered in different posts on this site.

Approximations with a fixed denominator

Consider some q>\frac{1}{2\varepsilon}. Therefore, \varepsilon>\frac{1}{2q}. We can divide the real line into intervals \left[ \frac{k}{q},\frac{k+1}{q}\right), k\in\mathbb{Z}. Any \aplha\in\mathbb{R} belongs to exactly one such interval. We set \frac{p}{q} to be the closest endpoint.

What is the distance between \alpha and \frac{p}{q}? It is definitely at most half of the interval, i.e., at most \frac{1}{2q}. So,

    \[\left|\alpha-\frac{p}{q}<\right|<\frac{1}{2q}<\varepsilon.\]

We see that for every \alpha\in\mathbb{R}, and for every q\in\mathbb{N}, there exists some p\in\mathbb{Z}, such that \left|\alpha-\frac{p}{q}\right|<\frac{1}{2q}.

Approximations with a bounded denominator – Farey sequence

We can get better approximations if we consider bounded denominators instead of fixed. Assume that, WLOG, \alpha\in\left[0,1\right] – otherwise, we would consider decimal part \{\alpha\}=\alpha-\left\lfloor\alpha\right\rfloor.

Definition: Let n\in\mathbb{N}. Consider all fractions \frac{p}{q}\in\left[0,1\right], such that GCD(p,q)=1 and q\leq n. Having them arranged we denote them 0=f_0<f_1<...<f_m=1. A sequence (or a list) F_n=\{f_i|i=0,...,m\} is called the Farey sequence of order n.

Example: Farey sequence of order 6 is the following:

    \[0<\frac{1}{6}<\frac{1}{5}<\frac{1}{4}<\frac{1}{3}<\frac{2}{5}<\frac{1}{2}<\frac{3}{5}<\frac{2}{3}<\frac{3}{4}<\frac{4}{5}<\frac{5}{6}<1.\]

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

Theorem(Cauchy): Let \frac{a}{b}<\frac{c}{d} be two neighbours of F_n. Then bc-ad=1.

Proof: GCD(a,b)=1, since \frac{a}{b}\in F_n. By Bezout theorem there exist some x,y\in\mathbb{Z} such that bx-ay=1. Observe that if (x_0,y_0) is a solution of bx-ay=1, then (x_1,y_1)=(x_0+ra,y_0+rb) is also a solution for any r\in\mathbb{Z}:

    \[b(x_0+ra)-a(y_0+rb)=bx_0+bra-ay_0-arb=bx_0-ay_0=1.\]

For a suitable r there must exist a solution (x_1,y_1), such that 0\leq n-b<y_1\leq n (in particular, y_1>0 and y_1+b>n). We will show that \frac{x_1}{y_1}=\frac{c}{d}. Let us denote the equation bx_1-ay_1=1 by (*).

From (*) it follows that

    \[\frac{x_1}{y_1}-\frac{a}{b}=\frac{bx_1-ay_1}{by_1}=\frac{1}{by_1}>0.\]

(*) also implies that GCD(x_1,y_1)=1: any common divisor of x_1 and y_1 divides bx_1-ay_1=1, hence, it must be 1. So, we have shown that the denominator of \frac{x_1}{y_1} is less then or equal to n and \frac{x_1}{y_1}>\frac{a}{b}. However, the smallest such fraction is, by definition, \frac{c}{d}, therefore \frac{x_1}{y_1}\geq\frac{c}{d}.

For the sake of contradiction, assume that the inequality is strict, i.e., \frac{x_1}{y_1}>\frac{c}{d}. Then we have

    \[\frac{x_1}{y_1}-\frac{c}{d}=\frac{dx_1-cy_1}{y_1d}\geq\frac{1}{y_1d},\]

where the inequality comes from the fact that \frac{x_1}{y_1}>\frac{c}{d} impies dx_1-cy_1>0. Similarly, we have

    \[\frac{c}{d}-\frac{a}{b}=\frac{bc-ad}{bd}\geq\frac{1}{bd}.\]

Adding these two together, we receive

    \[\frac{1}{by_1}=\frac{bx_1-ay_1}{by_1}=\frac{x_1}{y_1}-\frac{a}{b}\geq\frac{1}{y_1d}+\frac{1}{bd}=\frac{b+y_1}{bdy_1}>\frac{n}{bdy_1}.\]

It follows that 1>\frac{n}{d}, hence d>n, which is a contradiction with the assumption that \frac{c}{d}\in F_n.

We conclude that \frac{x_1}{y_1}=\frac{c}{d}. Since both of the fractions are in the base form, we also have that x_1=c, y_1=d, and, finally, the desired statement now follows from (*).

Exercises

Exercise 1

How many elements are in F_n?

Solution

We know that, for any k>1, there is exactly \varphi(k) of elements of F_n with a denominator k, because of the GCD condition. Plus there are two more elements 0 and 1. Together, F_n=2+\sum_{k=2}^{n}\varphi(k).

Exercise 2

Show that for any two fractions \frac{a}{b}<\frac{c}{d} it holds that \frac{c}{d}-\frac{a}{b}\geq\frac{1}{bd}. Then show that for two neighbours in F_n 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 \frac{a}{b}<\frac{c}{d}<\frac{e}{f} be three neighbours in F_n. Show that \frac{c}{d}=\frac{a+e}{b+f}.

Solution

Will be added later.

Exercise 4

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

Solution

Proceed by induction. For n=1,2 the statement is obvious. Suppose it holds for n and we will prove it for n+1. We are adding fractions with denominator equal to n+1 to F_n. By the previous exercise we know that we add some \frac{k}{n+1} between neighbours \frac{a}{b} and \frac{c}{d} if and only if b+d=n+1. Since we assume the statement for n to hold, we can also add a fraction \frac{k'}{n+1} to the opposite side, where there are two neighbours \frac{c'}{d} and \frac{a'}{b}.

Exercise 5

Prove Dirichlet’s theorem: Let \alpha\in\mathbb{R}\setminus\mathbb{Q}. Then there exist infinitely many fractions \frac{p}{q} such that \left| \alpha-\frac{p}{q}\right|<\frac{1}{q^2}.

Solution

Let \alpha be irrational, n\in\mathbb{N}, and \frac{a}{b},\frac{c}{d} two neighbours in F_n such that \frac{a}{b}<\alpha<\frac{c}{d}. If b\leq d, then, by Cauchy’s theorem,

    \[\left| \alpha-\frac{a}{b}\right|<\frac{c}{d}-\frac{a}{b}=\frac{1}{bd}\leq\frac{1}{b^2}.\]

If b>d, then similarly, \left| \alpha-\frac{c}{d}\right|<\frac{1}{d^2}. The distance between two neighbours in F_n is at most \frac{1}{n^2}, so by increasing n, we get infinitely many desired fractions.

Exercise 6

Draw the sequence of denominators of F_n for n=6,10.

Solution

Check the Wiki post for similar pictures.

Leave a Reply

Your email address will not be published. Required fields are marked *