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 in to figure out what terms in it was the mediant of? Well, we could, of course, list the terms in , in order, and then pick the two that surround the value . I’m after another way.
Since is supposed to be reduced, and are relatively prime, and so there are integers and such that (this usually (in my mind) gets written with a “+”, not a “-”, but just change the sign of your ). Once you’ve found such a pair , all of the other pairs that satisfy the same equation are of the form , where is any integer. Among the , there is only one in the interval . Abusing notation a bit, or assuming you picked well to start, let’s call this value , and its partner . I claim that is the term directly before in .
Before talking about , I should have checked that . If this is not the case, then means , in which case we are in which is just 0/1 and 1/1. Not much interesting going on there. So let’s go ahead and assume .
Now, the linear equation gets re-written to show that (so the fractions are at least in the correct order). Messing about with inequalities some more, you can check that , and since and are relatively prime (they satisfy the linear equation), the fraction is actually in . Let be the predecessor of in (we want to show ). Since it is a neighbor, we showed last time that then . But now we’re saying that all solutions of the equation have a fixed form. That is, and for some integer . But if then is not in , and so is not in . So and , and we’re done.
Man, ok, so, after all that, we now know how to find the term before in . I’ll call it , sticking with our notation above. What about the term after ? You could play mostly the same games as above, I suppose. Or, if the successor is , then we know that and , since we made as a mediant. So and , easy enough. [Update 20091109: You have to be careful with this. The above method for finding the successor to in only works because you are in . If you look for successors in in , where , this method, using the predecessor, is wrong. For example, 1/4 is the predecessor of 1/3 in , but the fraction (1-1)/(3-4) suggested by the previous method is clearly NOT the sucessor of 1/3 in ]
So we know the neighbors of in . What is the next Farey sequence when 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 . So the next neighbor is , which doesn’t show up until . The newest neighbor after that will be the mediant with this new neighbor, i.e., , in . Continuing on, we see that all of the neighbors are of the form , for some positive integer . I called these -weighted mediants (of and ) yesterday.
The story goes pretty much the same on the right side. I called the neighbor on the right, in , . The next neighbors will be , , etc. These are the -weighted mediants of and .
We can put both of these into the same statement by noticing that the mediant of with is the same as the mediant of with . In other words, all of the neighbors of , in all of the Farey sequences, can be written as weighted mediants of with . They will have numerators of the form and denominators of the form . Guess what? These are exactly all of the solutions to . Go back a few paragraphs, it’s the same thing I said there.
In summary, the neighbors to , in any Farey sequence, are in one-to-one correspondence with solutions to .
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.