Mathematics
The Farey Sequence and Rational Approximation to Irrationals
Quick fact
In the Farey sequence of order n, any two consecutive fractions a/b and c/d satisfy bc – ad = 1, a property that ensures every irrational number can be approximated by a Farey fraction with error less than 1/d², where d is the denominator.
Why this is interesting
Imagine you want to approximate the square root of 2 as a simple fraction. Where do you even start? The Farey sequence gives a surprisingly elegant way to find the best possible rational approximations with small denominators.
Read the full explanation
Understanding The Farey Sequence and Rational Approximation to Irrationals
The Farey sequence of order n is the list of all reduced fractions between 0 and 1 whose denominators are at most n, arranged in increasing order. For example, the Farey sequence of order 5 is: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1. Notice that each fraction is in lowest terms. A key feature is the mediant: the fraction (a+c)/(b+d) formed from two fractions a/b and c/d. When you have two consecutive fractions in a Farey sequence, their mediant lies exactly between them, and its denominator is the sum of their denominators. This mediant often appears as the next term when you increase the order. The sequence is built by repeatedly inserting mediants between neighboring fractions whose denominators sum to the new order. This gives a simple, mechanical way to generate all reduced fractions up to a given denominator.
A deeper explanation
The Farey sequence's power for rational approximation comes from a remarkable property: for any irrational number x, you can find a fraction a/b in the Farey sequence of order n (with denominator ≤ n) such that |x – a/b| < 1/b². This is essentially Dirichlet's approximation theorem. The reason lies in the spacing of consecutive Farey fractions. If a/b and c/d are consecutive in a Farey sequence, then bc – ad = 1, which means the gap between them is exactly 1/(bd). Any irrational number x must lie between two consecutive Farey fractions of order n. Let these be a/b and c/d, with denominators b and d both ≤ n. The distance from x to the closer one is at most half the gap: 1/(2bd). Now, the larger of b and d is ≥ √(bd), so the denominator of the closer fraction, say q, is at least √(bd). Thus the error is at most 1/(2bd) ≤ 1/(2q²) < 1/q². Moreover, the mediants that appear in the Farey sequence are exactly the fractions that provide the best rational approximations in the sense that no fraction with a smaller denominator is closer. This reveals a deep connection between the Farey order and the continued fraction expansion of the irrational number. Understanding this mechanism shows why the Farey sequence is not just a curiosity but a fundamental tool in number theory, with applications in diophantine approximation, cryptography, and even in designing efficient algorithms for rational approximation.