Farey Sequences

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 n-th Farey sequence is the sequence of fractions h/k where 0\leq h\leq k\leq n and h and k are relatively prime (so that h/k is in “lowest terms”). Let’s denote this sequence by F_n. The first few are:

F_1: 0/1\quad 1/1

F_2: 0/1 \quad 1/2\quad 1/1

F_3: 0/1\quad 1/3\quad 1/2\quad 2/3\quad 1/1

F_4: 0/1\quad 1/4\quad 1/3\quad 1/2\quad 2/3\quad 3/4\quad 1/1.

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

The mediant of the fractions h_1/k_1 and h_2/k_2 is defined to be the fraction (h_1+h_2)/(k_1+k_2). 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 F_{n+1}, knowing the sequence F_n, you simply include all the existing terms, and any mediants of successive terms that have a denominator no bigger than n+1. So, for example, consider F_4 above. We consider the fractions obtained by adding to this sequence the mediants:

0/1\quad 1/5\quad 1/4\quad 2/7\quad 1/3\quad 2/5\quad 1/2\quad 3/5\quad 2/3\quad 5/7\quad 3/4 \quad 4/5\quad 1/1

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

F_5: 0/1\quad 1/5\quad 1/4 \quad 1/3\quad 2/5\quad 1/2\quad 3/5\quad 2/3\quad 3/4 \quad 4/5\quad 1/1.

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 h_1/k_1 and h_2/k_2, and let’s say that we’ve picked our indices so that h_1/k_1 < h_2/k_2. Now compute h_2/k_2 - h_1/k_1. Done? You got 1/(k_1k_2), 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, h_2k_1-h_1k_2=1. This is fairly interesting.

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

Armed with the observation that the difference between successive terms has a 1 in the numerator, in even just the first Farey sequence, F_1, we can proceed by induction on n to show that if h_1/k_1 < h_2/k_2 are successive terms in F_n then: (1) h_2k_1-h_1k_2=1, and also (2) the mediant of these fractions is reduced. Therefore, if the mediant has a denominator no bigger than n+1, it will get included in F_{n+1}.

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 m/n is a fraction in reduced form, is it the mediant of two successive fractions from F_{n-1}?

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 (a,b)-weighted mediant of fractions h_1/k_1 < h_2/k_2 is the fraction (ah_1+bh_2)/(ak_1+bk_2). I’ll assume a,b,h_1,h_2,k_1,k_2>0. So, for example, the normal mediant, defined above, is just the (1,1)-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 h_1/k_1<p/q<h_2/k_2, where h_1/k_1,h_2/k_2 are successive terms in a Farey sequence, so that h_2k_1-h_1k_2=1. Our goal is to find a,b so that p=ah_1+bh_2 and q=ak_1+bk_2. The assumption h_2k_1-h_1k_2=1 means that we can, indeed, find integers satisfying this condition, namely: a=-k_2p+h_2q and b=k_1p-h_1q.

So, back to the question about obtaining every fraction in F_n by taking mediants from F_{n-1}. We need to show that if m/n<1 and m is relatively prime to n, then m/n is the mediant of two successive fractions in F_{n-1}. Well, m/n certainly lies between two of them, say h_1/k_1 and h_2/k_2 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 (1,1)-weighted mediant). Since the denominator of the (a,b)-weighted mediant is ak_1+bk_2, the smallest denominator is obtained only with the (1,1)-weighted (i.e., normal) mediant. This denominator must be at least n, because otherwise the fraction would show up in some Farey sequence before F_n. As m/n is obtainable as a weighted mediant, it must be the (1,1)-weighted mediant, which is what we wanted to show. Let’s call it a day.


Tags: ,

8 Responses to “Farey Sequences”

  1. Ford Circles « ∑idiot's Blog Says:

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

  2. Neighbors in Farey Sequences « ∑idiot's Blog Says:

    […] 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 […]

  3. Finale! « ∑idiot's Blog Says:

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

  4. wolfRAMM (@wolfdegrade) Says:

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

  5. sumidiot Says:

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

  6. Farey Sequence Proof – See, Learn, Think Says:

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

  7. César Says:

    One key step in your proof is the weighted mediants thing. May you explain how did you get that idea? Thanks.

  8. sumidiot Says:

    Honestly, I have no idea where those weighted mediants came from, sorry.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: