Farey Sequences

Today we shall look at a class of sequences with a rich and deep history beginning from their earliest appearance in a problem that appeared in the Ladies’ Diary, which have numerous applications in number theory and combinatorics, and are lately making an appearance in math Olympiad problems.

The Farey sequence of order $n$ , denoted $\mathcal{F}_n$ is the sequence of completely reduced fractions, usually between 0 and 1, which have denominators less than or equal to $n$ , arranged in order of increasing size. For example,

\mathcal{F}_8 = \left \{\frac{0}{1}, \frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7},\frac{1}{3}, \frac{3}{8}, \frac{2}{5},\frac{3}{5}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3},\frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}, \frac{1}{1}\right \}

1. Basic Properties

First, observe that the terms which appear in the Farey sequence of order $n$ have denominators $1,2,\dots , n$ (which is of course obvious from the definition) and since they are completely reduced, the numerators are coprime to the denominators. Thus, there exists exactly $\phi(i)$ fractions with denominator $i$ for all $1 < i \le n$ and indeed, the Farey sequence of order $n$ has exactly $\sum_{i=1}^n \phi(i)+1$ terms.

Summing across the fractions with the same denominator by pairing, it is also not hard to show that the sum of fractions in the Farey sequence of order $n$ is equal to $\frac{1}{2}\left[1+\sum_{i=1}^n \phi(i)\right]$ , solving this unsourced problem from AoPS.

We shall now look at a few well known properties of the Farey sequences.

Theorem 1 (Farey Neighbours)

The fractions $\frac{a}{b}$ and $\frac{c}{d}$ are neighbours in a Farey sequence if and only if $\frac{a}{b}-\frac{c}{d}=\frac{1}{bd}$ or equivalently, $bc-ad=1$ .

We give two proofs of this result, each interesting in it’s own right.

First proof, bounding. Consider a term $\frac{a}{b} < 1$ in a Farey sequence. We shall determine the next term in the Farey sequence. Since $\gcd(a,b)=1$ , there exists integers $x$ and $y$ satisfying the equation,

$ax-by=1$

by Bezout’s Lemma. In particular, if $(x_0,y_0)$ is a pair of solutions, then all pairs of the form $(x_0+rb,y_0+ra)$ where $r$ is an integer are also solutions. We can now consider $r$ such that $n-b < y_0+rb \le n$ and look at the pair $c=y_0+rb$ and $d=x_0+ra$ . Since this is a pair of solutions to the above equation, $c < d < n$ so $\frac{c}{d}$ is a member of $\mathcal{F}_n$ .

Clearly, $\frac{c}{d} = \frac{a}{b}+\frac{1}{bd} > \frac{a}{b}$ so $\frac{c}{d}$ appears after $\frac{a}{b}$ in $\mathcal{F}_n$ . Now, let $\frac{a}{b}<\frac{c'}{d'}$ be the next term in the Farey sequence $\mathcal{F}_n$ . If this is distinct from $\frac{c}{d}$ , then $\frac{a}{b}< \frac{c'}{d'}< \frac{c}{d}$ and we have

$\frac{c}{d} - \frac{c'}{d'} = \frac{cd'-c'd}{dd'} \ge \frac{1}{dd'}$ and $\frac{c'}{d'} - \frac{a}{b}=\frac{bc'-ad'}{bd'} \ge \frac{1}{bd'}$ .

However, this is an immediate contradiction since

$\frac{1}{bd} = \frac{ac-bd}{bd} = \frac{c}{d}- \frac{a}{b} = \left(\frac{c}{d} - \frac{c'}{d'}\right) + \left(\frac{c'}{d'} - \frac{a}{b}\right) \ge \frac{1}{dd'}+\frac{1}{bd'} = \frac{b+d}{bdd'} > \frac{n}{bdd'} \ge \frac{1}{bd}$ .

where $b+d>n$ follows by our choice of $r$ . $\square$

Second proof, geometric. The idea is to represent the fraction $\frac{a}{b}$ by the ordered pair of integers $(b,a)$ and throw it on the lattice plane.

We say a point is visible if the line segment $OP$ does not contain any lattice points in it’s strict interior. It is not hard to see that the point $P(x, y)$ is visible if and only if $\gcd(x, y) = 1$ . This means that the set of fractions in the Farey sequences of order at most $n$ corresponds exactly to the set of visible points in the region $\Delta$ bounded by the lines $y = 0$ , $x = n$ and $y = x$ .

Now, consider a moving line $\ell$ passing through the origin $O$ and rotating clockwise. It is clear that passes through the visible points $P(x, y)$ in decreasing order of $\frac{y}{x}$ since $\tan \angle (\ell, \ell_x) = \frac{y}{x}$
where $\ell_x$ denotes the $x$ −axis.

Let $A(x_a, y_a)$ and $B(x_b, y_b)$ be two points on which lands consecutively. Since there exists no visible points within the angle $\angle (OA, OB)$ it is not hard to see that there exists no visible points (and hence no lattice points) within the parallelogram $OACB$ . By Pick’s Theorem it then follows that the area of the parallelogram $OACB$ is 1.

We can alternately calculate the area of the parallelogram $OACB$ as,

$[OACB] = |x_ay_b-x_by_a|$

which implies the result. $\square$

This is already sufficient to solve the following interesting problem given at a mock for the China National HS Math League and 2002 Kürschák Problem 2 which uses the cool result that the ratios of consecutive Fibonacci numbers are also consecutive Farey fractions.

An immediate corollary of this result is the fact that if the fractions $\frac{a}{b} < \frac{p}{q} < \frac{c}{d}$ are a trio of neighbours in a Farey sequence, then $\frac{p}{q} = \frac{a+c}{b+d}$ which can be verified by applying the above property on each pair of neighbours.

Another observation is that $\frac{a+c}{b+d}$ must be completely reduced since otherwise, this fraction lies strictly between $\frac{a}{b}$ and $\frac{c}{d}$ and has denominator at most $\frac{b+d}{2}<d$ .

Theorem 2 (Mediant Property)

If $\frac{a}{c}$ and $\frac{c}{d}$ are neighbours in a Farey sequence then the first term that appears between them as the order of the Farey sequence is incremented is their mediant, $\frac{a+c}{b+d}$ .

Proof. If exactly one new fraction appears between $\frac{a}{b}$ and $\frac{c}{d}$ this follows from the above corollary. Hence, at least two new fractions must appear. However it is not hard to see
that the newly added terms in the Farey sequence of order $n$ must all have denominator $n$.

If $\frac{a}{b} < \frac{m}{n}<\frac{m+\epsilon}{n}< \frac{c}{d}$ for some strictly positive integer $\epsilon < n-m$ note that $mb - an \ge 1$ and $md + \epsilon d \le cn$ so

$\frac{cn-\epsilon d}{d} \ge m \ge \frac{an+1}{b}$

and we have $(bc-ad)n > (b\epsilon +1)d$ which since $bc-ad=1$ by the Farey neighbour’s condition implies

$n > (b \epsilon +1)d \ge (b+1)d> b+d$

which is a clear contradiction. $\square$

Surprisingly, this result has also appeared in recent olympiads, most notably as 2024 Mexico TST Problem 1.

This result is crucial since it allows us to iteratively construct all terms that appear in a Farey sequence (and by extension all rationals between 0 and 1).

Starting with $\frac{0}{1}$ and $\frac{1}{1}$ , placed at either end of a segment of length 1, in each step write the mediants of each pair of neighbouring fractions at the midpoint of their positions. Optionally, one can write the fractions generated in each step in a new level. This structure is sometimes refered to as the Stern-Brocot tree (when all edges are deleted except those between a fraction and it’s two children) or the Neighbour’s graph of Farey fractions. Given below is the graph upto 5 generations, with terms greater than 1 included.

We can immediately note that this graph is outerplanar — in each stage, the newly added vertices are connected to two neighbouring vertices which belong to the outer face. Since it is well known that outerplanar graphs on $n$ vertices have at most $2n-3$ edges, this immediately solves 2020 USAMO Problem 4.

Another important application of the Farey sequence is it’s connection to continued fractions and rational approximations.

2. Diophantine Approximations

By the denseness of the rational numbers, we know that for every irrational number $x$ and $\epsilon > 0$ , there exists integers $p$ and $q$ with

$\left | \frac{p}{q}-x\right |<\epsilon$ .

For example, consider $\sqrt{2} = 1.41421356237...$ . Clearly, $\frac{141421}{100000}$ is a really good rational approximation but this is pointless. The goal is to obtain as close an approximation as possible, using small denominators.

Theorem 3 (Weak Diophantine Approximation)

For every positive irrational number $\alpha$ , there exists infinitely many pairs of integers $(p,q)$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{2q}$ .

Proof. The idea is to consider for each positive integer $q_0$ , the positive integer $p_0$ such that $\frac{p_0-1}{q_0} < \alpha < \frac{p_0}{q_0}$ and pick the fraction which is closer to $\alpha$ . The interval $\left(\frac{p_0-1}{q_0},\frac{p_0}{q_0}\right)$ is of length $\frac{1}{q_0}$ meaning that our approximation is off by at worst $\frac{1}{2q_0}$ , as desired. $\square$

First of all, the fact that such an approximation exists for every positive integral denominator $q$ is a red light, and indeed these approximations are not very good. For example, to get an approximation for $\sqrt{2}$ that is at most $1 \times 10^5$ off, we need to use a denominator of at least $5000$ which is barely any better than what we started with.

Using the knowledge of Farey fractions however, it is possible to significantly improve this approximation.

Theorem 4 (Strong Diophantine Approximation)

For every positive irrational number $\alpha$ , there exists infinitely many pairs of integers $(p,q)$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{2q^2}$ .

Proof. We only consider the case when $0 < \alpha < 1$ , it is easy to see that the others follow by shifting. Since $\alpha$ is in this range, it must lie strictly between two terms of the Farey sequence of order $n$ , say $\frac{a}{b} < \alpha < \frac{c}{d}$ .

By the AM-GM inequality we know that

$\frac{1}{2b^2}+\frac{1}{2d^2} \ge \frac{1}{bd} = \frac{c}{d}-\frac{a}{b}$ ,

the latter equality following from the Farey Neighbour’s theorem. However this means

$\left |\frac{c}{d}-\alpha \right| + \left |\frac{a}{b}-\alpha\right| = \frac{c}{d} - \frac{a}{b} \le \frac{1}{2b^2}+\frac{1}{2d^2}$

so one of the inequalities $\left |\frac{a}{b}-\alpha\right|\le \frac{1}{2b^2}$ and $\left |\frac{c}{d}-\alpha\right|\le \frac{1}{2d^2}$ must hold. Moreover, as the order of the Farey sequence increases, every rational number between 0 and 1 appears, and we obtain infinitely many (increasingly better) approximations of $\alpha$ . $\square$

Surprisingly, we can do yet better solely employing Farey fractions by being a little smarter.

Theorem 5 (Hurwitz’s Approximation)

For every positive irrational number $\alpha$ , there exists infinitely many pairs of integers $(p,q)$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{\sqrt{5}q^2}$ .

Proof. As before, consider the case when $0 < \alpha < 1$ and let $\alpha$ lie strictly between the Farey neighbours $\frac{a}{b}$ and $\frac{c}{d}$ . In particular, since $\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$ it is clear that $\alpha$ must lie strictly within one of these two intervals. Without loss of generality, assume it lies strictly between $\frac{a+c}{b+d}$ and $\frac{c}{d}$ .

Working towards a contradiction, assume that each of the inequalities $\left |\frac{c}{d}-\alpha\right|\ge \frac{1}{\sqrt{5}d^2}$ , $\left |\frac{a}{b}-\alpha\right|\ge \frac{1}{\sqrt{5}b^2}$ and $\left |\frac{a+c}{b+d}-\alpha\right|\ge \frac{1}{\sqrt{5}(b+d)^2}$ hold.

However, adding the third inequality with each of the other two in turn yields,

$\frac{1}{bd} = \frac{c}{d}-\frac{a}{b} \ge \frac{1}{\sqrt{5}}\left(\frac{1}{b^2}+\frac{1}{d^2}\right)$

and

$\frac{1}{d(b+d)} = \frac{c}{d}-\frac{a+b}{c+d} \ge \frac{1}{\sqrt{5}}\left(\frac{1}{d^2}+\frac{1}{(b+d)^2}\right)$

utilizing both the Farey neighbours and Mediant properties. Thus, $b^2+d^2 \le \sqrt{5}bd$ and $d^2 + (b+d)^2 \le \sqrt{5}d(b+d)$ . Summing these two inequalities we have,

$\sqrt{5}d(2b+d) \ge 2b^2+3d^2+2bd$ which rearranges to $0 \ge \frac{1}{2}\left((\sqrt{5}-1)d-2b\right)^2$ which is a clear violation of the trivial inequality unless equality holds. However, equality cannot hold since $\sqrt{5}$ is irrational, and the result follows. $\square$

It is in fact also known that $\sqrt{5}$ is the best constant $c$ such that for every irrational number $\alpha$ , there exists infinitely many integers $p,q$ such that $\left|\frac{p}{q}-\alpha\right|< \frac{1}{cq^2}$ . This is because for larger $c$ , the ‘golden ratio’ $\phi= \frac{\sqrt{5}+1}{2}$ ceases to have infinitely many approximations. This is part of the reason why the golden ratio is said to be in some sense ‘the most irrational number’.

The equality case is also quite interesting since one can show that all rational approximations of $\phi$ satisfying Hurwitz’s approximation are those which are ratios of consecutive Fibonacci numbers.

3. Ford Circles

Since any discussion on Farey sequences is incomplete without mentioning Ford circles, we shall point out a few connections between the two.

Ford circles are a set of circles whose centers are at $\left(\frac{p}{q},\frac{1}{2q^2}\right)$ and have radius $\frac{p}{q}$ for every completely reduced fraction $\frac{p}{q}$ between 0 and 1.

Theorem 6 (Ford Circles)

Two Ford circles are either disjoint or tangent to each other. In particular, the Ford circles for two completely reduced fractions are tangent if and only if these fractions are neighbours of some Farey sequence.

Proof. We employ Cartesian coordinates. With the center and radii all known, this is but a simple calculation. We know that two circles intersect if and only if the sum of their radii is less than the distance between their centers.

However,

$\left(\frac{a}{b}-\frac{c}{d}\right)^2 + \left(\frac{1}{2b^2}+\frac{1}{2d^2}\right)^2 - \left(\frac{1}{2b^2}+\frac{1}{2d^2}\right)^2=\left(\frac{a}{b}-\frac{c}{d}\right)^2 - \frac{1}{b^2d^2}$

which is negative if and only if $\left|\frac{a}{b}-\frac{c}{d}\right|<\frac{1}{bd}$ or simply $|ad-bc|<1$ which is a clear contradiction, and in particular tangency holds if and only if $|ad-bc|=1$ which is precisely the Farey neighbours condition.

Farey Sequences

1. Basic Properties

2. Diophantine Approximations

3. Ford Circles

Published by Lasitha Jayasinghe

Leave a comment Cancel reply

1. Basic Properties

2. Diophantine Approximations

3. Ford Circles

Share this:

Related

Published by Lasitha Jayasinghe

Leave a comment Cancel reply