Ok, so if I’m going to talk about Farey sequences and the Riemann hypothesis for MaBloWriMo, then Farey sequences are probably a good place to start.

Let us say that the -th **Farey sequence** is the sequence of fractions where and and are relatively prime (so that is in “lowest terms”). Let’s denote this sequence by . The first few are:

.

There’s sort of a nice way to get from one Farey sequence to the next: add fractions incorrectly.

The **mediant** of the fractions and is defined to be the fraction . It turns out that the mediant of two fractions always lies between them, which you can check by taking differences and noticing they have the correct sign. Now, to make the sequence , knowing the sequence , you simply include all the existing terms, and any mediants of successive terms that have a denominator no bigger than . So, for example, consider above. We consider the fractions obtained by adding to this sequence the mediants:

and then we throw out any fraction whose denominator is bigger than 5, giving us

.

There’s a little something to worry about in this process. Well, probably a few little somethings. The one I’ve got in mind is: are the mediants always reduced? However, you might also ask: are we sure we get all of the fractions this way?

To begin to answer these, let me change the subject. Look at any of the Farey sequences listed above, and pick any two successive terms in that sequence. Call them and , and let’s say that we’ve picked out indices so that . Now compute . Done? You got , didn’t you? This happens no matter what Farey sequence you are in, and no matter which successive terms you take. You always find that, with the notation above, . This is fairly interesting.

We already knew that, for example, and were relatively prime. And for a pair of relatively prime integers, there always exist integers such that . Conversely, if you can find such a pair of integers, then and are relatively prime. What’s perhaps a little surprising is that, in this case, the and happen to show up in the next term of the Farey sequence: and .

Armed with the observation that the difference between successive terms has a 1 in the numerator, in even just the first Farey sequence, , we can proceed by induction on to show that if are successive terms in then: (1) , and also (2) the mediant of these fractions is reduced. Therefore, if the mediant has a denominator no bigger than , it will get included in .

Does this process of expanding one Farey sequence to the next by throwing in mediants actually give us all of the terms of the next Farey sequence? That is, if is a fraction in reduced form, is it the mediant of two successive fractions from ?

Let me answer that by considering what I’ll call weighted mediants (a name I just made up, it may or may not show up in your favorite reference). Let me say that the -weighted mediant of fractions is the fraction . I’ll assume . So, for example, the normal mediant, defined above, is just the -weighted mediant. I claim that: (1) every weighted mediant lies between the two original fractions, (2) every fraction between two successive terms in a Farey sequence can be obtained as a weighted mediant.

Claim (1) is easy, just take appropriate differences and note that they have the appropriate sign, as before. For claim (2), suppose , where are successive terms in a Farey sequence, so that . Our goal is to find so that and . The assumption means that we can, indeed, find integers satisfying this condition, namely: and .

So, back to the question about obtaining every fraction in by taking mediants from . We need to show that if and is relatively prime to , then is the mediant of two successive fractions in . Well, certainly lies between two of them, say and in keeping with our notation, and we have just shown that it may therefore be obtained as some weighted mediant (we want it to be the -weighted mediant). Since the denominator of the -weighted mediant is , the smallest denominator is obtained only with the -weighted (i.e., normal) mediant. This denominator must be at least , because otherwise the fraction would show up in some Farey sequence before . As is obtainable as a weighted mediant, it must be the -weighted mediant, which is what we wanted to show. Let’s call it a day.

Tags: farey, mablowrimo

November 5, 2009 at 9:12 pm |

[…] By sumidiot Now that we’ve got some foundations laid for Farey sequences and rational approximations, let’s put pictures to some […]

November 8, 2009 at 8:02 pm |

[…] the things I wanted to say was based on some things I didn’t say about Farey sequences when I talked about them a few days ago. So I thought I’d go back and fill in that gap, and save Ford circles for […]

December 3, 2009 at 9:23 pm |

[…] been a while, so perhaps we should recall some basics about the Farey sequences. The -th Farey sequence, denoted […]

April 21, 2012 at 7:38 am |

for the F5 sequence you missed one fraction …2/3 3/4 4/5 1/1

April 21, 2012 at 5:00 pm |

@wolfdegrade that I did, thanks. corrected (and the line above it)

November 25, 2016 at 7:06 pm |

[…] https://sumidiot.wordpress.com/2009/11/03/farey-sequences/ […]