Neighbors in Farey Sequences

I was reading about Ford circles today, and was planning on writing about them. But then I noticed that one of 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 tomorrow.

So what did I skip? Well, I mentioned that to get from one Farey sequence to the next, you throw in mediants whose denominators aren’t too big. Is there a way, given a fraction $h/n$ in $F_n$ to figure out what terms in $F_{n-1}$ it was the mediant of? Well, we could, of course, list the terms in $F_{n-1}$ , in order, and then pick the two that surround the value $h/n$ . I’m after another way.

Since $h/n$ is supposed to be reduced, $h$ and $n$ are relatively prime, and so there are integers $s$ and $t$ such that $hs-nt=1$ (this usually (in my mind) gets written with a “+”, not a “-”, but just change the sign of your $t$ ). Once you’ve found such a pair $(s,t)$ , all of the other pairs that satisfy the same equation are of the form $(s+mn,t+mh)$ , where $m$ is any integer. Among the $s+mn$ , there is only one in the interval $[0,n)$ . Abusing notation a bit, or assuming you picked well to start, let’s call this value $s$ , and its partner $t$ . I claim that $t/s$ is the term directly before $h/n$ in $F_n$ .

Before talking about $t/s$ , I should have checked that $s\neq 0$ . If this is not the case, then $hs-nt=1$ means $n=1$ , in which case we are in $F_1$ which is just 0/1 and 1/1. Not much interesting going on there. So let’s go ahead and assume $s>0$ .

Now, the linear equation $hs-nt=1$ gets re-written $h/n-t/s=1/(ns)$ to show that $h/n>t/s$ (so the fractions are at least in the correct order). Messing about with inequalities some more, you can check that $0\leq t<s$ , and since $s$ and $t$ are relatively prime (they satisfy the linear equation), the fraction $t/s$ is actually in $F_n$ . Let $a/b$ be the predecessor of $h/n$ in $F_n$ (we want to show $a=t,b=s$ ). Since it is a neighbor, we showed last time that then $hb-na=1$ . But now we’re saying that all solutions of the equation $hx-ny=1$ have a fixed form. That is, $b=s+mn$ and $a=t+mh$ for some integer $m$ . But if $m\neq 0$ then $b$ is not in $[0,n)$ , and so $a/b$ is not in $F_n$ . So $m=0$ and $a=t,b=s$ , and we’re done.

Man, ok, so, after all that, we now know how to find the term before $h/n$ in $F_n$ . I’ll call it $t/s$ , sticking with our notation above. What about the term after $h/n$ ? You could play mostly the same games as above, I suppose. Or, if the successor is $T/S$ , then we know that $h=t+T$ and $n=s+S$ , since we made $h/n$ as a mediant. So $T=h-t$ and $S=n-s$ , easy enough. [Update 20091109: You have to be careful with this. The above method for finding the successor to $h/n$ in $F_n$ only works because you are in $F_n$ . If you look for successors in $h/k$ in $F_n$ , where $k<n$ , this method, using the predecessor, is wrong. For example, 1/4 is the predecessor of 1/3 in $F_5$ , but the fraction (1-1)/(3-4) suggested by the previous method is clearly NOT the sucessor of 1/3 in $F_5$ ]

So we know the neighbors of $h/n$ in $F_n$ . What is the next Farey sequence when $h/n$ gets a new neighbor? Let’s stick to the next time it gets a new neighbor “on the left” (less than itself). We know that when that happens, it had to be because we made the mediant with the old neighbor, our friend $t/s$ . So the next neighbor is $(t+h)/(s+n)$ , which doesn’t show up until $F_{s+n}$ . The newest neighbor after that will be the mediant with this new neighbor, i.e., $(t+2h)/(s+2n)$ , in $F_{s+2n}$ . Continuing on, we see that all of the neighbors are of the form $(t+mh)/(s+mn)$ , for some positive integer $m$ . I called these $(1,m)$ -weighted mediants (of $t/s$ and $h/n$ ) yesterday.

The story goes pretty much the same on the right side. I called the neighbor on the right, in $F_n$ , $T/S$ . The next neighbors will be $(h+T)/(n+S)$ , $(2h+T)/(2n+S)$ , etc. These are the $(m,1)$ -weighted mediants of $h/n$ and $T/S$ .

We can put both of these into the same statement by noticing that the $(1,-m)$ mediant of $t/s$ with $h/n$ is the same as the $(m-1,1)$ mediant of $h/n$ with $T/S$ . In other words, all of the neighbors of $h/n$ , in all of the Farey sequences, can be written as $(1,m)$ weighted mediants of $t/s$ with $h/n$ . They will have numerators of the form $a=t+mh$ and denominators of the form $b=s+mn$ . Guess what? These are exactly all of the solutions to $hx-ny=1$ . Go back a few paragraphs, it’s the same thing I said there.

In summary, the neighbors to $h/n$ , in any Farey sequence, are in one-to-one correspondence with solutions to $hx-ny=1$ .

If I knew what I were doing, I could probably have gotten to this statement a bit more quickly. But I don’t remember the last time I knew what I was doing, so there you have it.

About these ads

Tags: farey, mablowrimo

This entry was posted on November 5, 2009 at 3:50 am and is filed under Play. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to “Neighbors in Farey Sequences”

Jaime Says:
November 5, 2009 at 9:51 am | Reply
Farey sequences are a cool subject indeed, I’m thoroughly enjoying your series on them. When you find time, go back to Euler’s Flying Circus and give 192 and 198 a try…

198 is arguably the hardest problem posted at Project Euler if you look at how long its been posted and how many people have got it right. Yet it’s quite straightforward to solve once you know all you now know…
- sumidiot Says:
  November 5, 2009 at 7:18 pm | Reply
  Thanks for the encouragement! And for the pointer to fun Project Euler problems. I wasn’t to get to those two for a while, working my way through in order. By the time I got there, I’d probably forget all of the math I’d need to solve them. It might be a few days, but I’ll attack those two next.
- sumidiot Says:
  November 9, 2009 at 10:07 am | Reply
  Curse you Jaime! I’ve been working on 198, and spending far too much time on it. I’ve got 3 “solutions” going, but all of them are too slow to ramp up to the bound 10^8. Got an idea how to improve things… but not sure when I should let myself get back to the problem, versus doing “real work”.
Problem 198 – Ambiguous Numbers « Leonhard Euler’s Flying Circus Says:
December 9, 2009 at 11:32 pm | Reply
[...] I’m getting to this problem a little out of order. Jaime told me to. I was talking about Neighbors in Farey Sequences, on another blog, and he said this problem would fit well with what I was doing. In fact, if you [...]

∑idiot's Blog

Neighbors in Farey Sequences

Like this:

4 Responses to “Neighbors in Farey Sequences”

Leave a Reply Cancel reply

Follow “∑idiot's Blog”