## 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 out 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, 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: ,

### 5 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 [...]