The Farey sequence of order is the ascending sequence of irreducible fractions between 0 and 1, whose denominators do not exceed . This sequence was discovered by Charles Haros in 1806, but Augustin-Louis Cauchy named it after geologist John Farey.
Thus belongs to if and , the numbers 0 and 1 are included in the forms and . For example,
Following are the characteristic properties of Farey sequence (for proofs refer §3.3, §3.4 and §3.7 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers):
- If and are two successive terms of , then .
- If , and are three successive terms of , then .
- If and are two successive terms of , then the mediant of and falls in the interval .
- If , then no two successive terms of have the same denominator.
The Stern-Brocot tree, which we saw earlier while understanding the working of clocks, is a data structure showing how the sequence is built up from 0 (=0/1) and 1 (=1/1) by taking successive mediants.
Now, consider a circle of unit circumference, and an arbitrary point of the circumference as the representative of 0 (zero), and represent a real number by the point whose distance from , measured round the circumference in the anti-clockwise direction, is .
Plainly all integers are represented by the same point , and numbers which differ by an integer have the same representative point.
Now we will divide the circumference of the circle in the following manner:
- We take the Farey sequence , and form all the mediants of the successive pairs , . The first and last mediants are and . The mediants naturally do not belong themselves to .
- We now represent each mediant by the point . The circle is thus divided up into arcs which we call Farey arcs, each bounded by two points and containing one Farey point, the representative of a term of . Thus is a Farey arc containing the one Farey point .
The aggregate of Farey arcs is called Farey dissection of the circle. For example, the sequence of mediants for , say is
And hence the Farey disscetion looks like:
Let . If is a Farey point, and, are the terms of which precede and follow , then the Farey arc around is composed of two parts, whose lengths are
respectively. Now , since and are unequal (using the point (4.) stated above)and neither exceeds ; and (using the point (3.) stated above). We thus obtain:
Theorem: In the Farey dissection of order , there , each part of the arc which contains the representative has a length between and .
For example, for we have:
Using the above result, one can prove the following result about rational approximations (for more discussion, see §6.2 of Niven-Zuckerman-Montgomery’s An Introduction to the Theory of Numbers):
Theorem: If is a real number, and a positive integer, then there is an irriducible fraction such that and
One can construct a geometric proof of Kronceker’s theorem in one dimension using this concept of Farey dissection. See §23.2 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers for details.