|
|
|
The nth Farey Sequence, Fn, is the sequence of rational numbers a/b, such that GCD(a,b)=1, and 0 ≤ a ≤ b ≤ n. For example,
F5 is {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1}
If a/b and c/d are successive terms of a Farey sequence, then bc - ad=1. That is, the product of the means minus the product of the extremes is 1.
The denominators, b and d, of adjacent elements of a Farey sequence are coprime, because numbers x and y exist such that bx+dy=1. In fact, x and y are the numerators (the first one negative) of these adjacent elements.
Similarly, the numerators, a and c, of adjacent elements of a Farey sequence are coprime, because ax+cy=1, where x=-d and y=b.
The "mediant" of two fractions expressed in lowest terms, a/b and c/d, is (a+c)/(b+d). For example,
the mediant of 2/5 and 1/2 is (2+1)/(5+2) = 3/7
Each element of a Farey Sequence that has two neighbors is the mediant of those two neighbors. For example, in F5, 3/5 lies between 1/2 and 2/3, and 3/5 is the mediant of 1/2 and 2/3.
Let a/b, c/d, e/f be successive elements of a Farey Sequence,
so bc-ad=1 and de-cf=1.
Thus bc-ad+cf-de=0.
Rearranging this, d(a+e)=c(b+f), so c/d=(a+e)/(b+f)
This fact can be used to find Fn+1 given Fn. For each pair of successive elements of Fn in which the sum of their denominators equals n+1, the mediant can be inserted between them to form Fn+1. The mediants formed this way will always be in lowest terms because both the denominators and numerators of adjacent elements of a Farey Sequence are coprime, and the sum of two coprime numbers is coprime to each of them.
Letting
F6 = {y1/x1, y2/x2, ...}
the (x,y) pairs are plotted on a lattice, occupying the first half of the first
quadrant (i.e. the first octant). To complete the starburst, this
sequence is repeated seven more times with reflections about the line y=x and
the axes.
The
image to the right shows F5, extended the same way, and blown up so
you can see the sequence of triangles formed with the origin and two successive
elements of a F5.
I will call a lattice triangle a "Farey Triangle" if its vertices are (0,0), (x1,y1), and (x2,y2), or one of its seven other reflections, where x1/y1 and x2/y2 are adjacent elements of a Farey sequence. The Farey Triangles in the diagram to the right are the thin triangles with yellow interior and one vertex at the origin.
It is fairly easy to see that the area of each of the Farey triangles is
1/2. Since its vertices are (0,0), (a,b), (c,d), its area
is |ad-bc|/2. And since a/b and c/d are successive elements of a Farey
sequence, |ad-bc|=1, proving the result.
From the origin, we will call a lattice point (x,y) "visible" if GCD(x,y)=1. Two lattice points (x1,y1), (x2,y2), in which the largest x- or y- coordinate (in absolute value) is n, will be called n-Farey-adjacent if, from the point of view of the origin, no other lattice point with coordinates no larger than n is visible between them.
A triangle formed by the origin and two n-Farey-adjacent lattice points is a Farey triangle, and (as proved above) has an area of 1/2.
Conversely, a lattice triangle whose longest side's longest component measures n units, and whose border contains only the three lattice points of its vertices, and whose interior has no lattice points is congruent to a Farey triangle, because viewed from one end of its longest side, the other two vertices are n-Farey-adjacent.
Mathworld: Farey Sequence
Cut-the-knot: Farey Sequence and its application to Pick's Theorem
Pick's Theorem, for finding the area of lattice polygons.
The area of a triangle with vertices (0,0), (a,b), (c,d) is |ad-bc|/2.
See also Recurrence Relation
The webmaster and author of this Math Help site is Graeme McRae.