Farey Series

The Farey series FN is the set of all fractions in lowest terms between 0 and 1 whose denominators do not exceed N, arranged in order of magnitude. For example, F6 is

Farey series of order 6

N is known as the order of the series. Farey was a British geologist who in 1816 published the statement to the effect that in the Farey series the middle of any three successive terms is the mediant of the other two. The proof has been eventually supplied by Cauchy. The series nonetheless bears the name of Farey.

To see why the statement is correct, start with F1 which is 0/1, 1/1. In order to get F2, insert the mediant into F1: 0/1, 1/2, 1/1. For F3 we add two mediants: 0/1, 1/3, 1/2, 2/3, 1/1. To get F4 we also add only 2 fractions: 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1. Next, add 4 fractions to get F5: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1. As we already saw, it takes additional 2 fractions to get F6. The general rule is this: to move from FN-1 to FN add all possible mediants (that come out to be in the lowest terms) with N in the denominator. Since forming a mediant may only increase the denominator we are led to think that following this rule we indeed will get the whole of FN. To complete the proof recollect that the Stern-Brocot tree contains all positive fractions. So in the process of constructing Farey series no fraction will be missed either.

When N is prime, the rule adds N-1 fractions. In general, φ(N) fractions are added. For all reducible fractions m/N will have appeared in one of the earlier series. Check this with F7

The Farey series furnishes another proof of an important corollary of Euclid's algorithm: for integers m and n with gcd(m, n) = 1 and m ≤ n, there exist positive integers a and b such that ma - nb = 1. The proof again depends on the properties of the Stern-Brocot tree. For any two consecutive fractions m1/n1 and m2/n2 in the Farey series, m2n1 - m1n2 = 1. So, depending on which of m or n is larger, locate either m/n or n/m in a Farey series and select (as a/b) either the preceding or the following fraction.

An absolutely marvelous geometric interpretation of the Farey series has been invented by Lester R. Ford.

References

  1. A. Beck, M.N. Bleicher, D. W. Crowe, Excursions into Mathematics, A K Peters, 2000
  2. J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
  3. R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

|Contact| |Front page| |Contents| |Store| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

 62393659

Search by google: