Ford Circles

Now that we’ve got some foundations laid for Farey sequences and rational approximations, let’s put pictures to some of those claims, via Ford circles.

For every rational h/k, in reduced terms, draw a circle in the plane with center (h/k,1/(2k^2)) and radius 1/(2k^2). I’m not going to try to come up with a better picture for you than the one used on the Wikipedia page for Ford circles. (I tried embedding the picture below, but that didn’t work. So I’ll leave it to you to click the link.)

What’s so great about this construction? Well, you may recognize those radii as the error term in our discussion of rational approximations. The statement that for every irrational \omega there are infinitely many reduced fractions h/k such that |\omega-h/k|<1/(2k^2) is the same as saying that the vertical line x=\omega intersects infinitely many of the Ford circles. The improved bound 1/(\sqrt{5}k^2) can also be found by (very carefully) analyzing vertical lines passing through Ford circles (more specifically, the gaps between them), but I think for now I’m going to let that statement be for now. If you want, the proof via Ford circles is in [Rademacher], and a proof via continued fractions is in [Hardy and Wright]. The result is known as Hurwitz’s theorem.

What else can be said about Ford circles? Well, yesterday I was talking about neighbors in Farey sequences. It turns out that h/k and H/K are neighbors in a Farey sequence if and only if the Ford circles at h/k and at H/K are tangent to each other.

To see why this is true, consider the circles at h/k and H/K, with h/k<H/K so Hk-hK>0). Since we know the location of their centers, we can find an expression for the distance between those centers. The two circles will intersect iff the distance between the centers is no bigger than the sum of the radii of the two circles. Re-arranging terms (and working with squares to avoid square roots), you might look at d^2-(r_k+r_K)^2, where d is the distance between the centers, and r_k and r_K denote the (hopefully obvious) radii. The two circles will be tangent if this is 0, and won’t intersect if the difference is positive. More care needs to be used when talking about what happens if the difference is negative, but we’ll see momentarily that this doesn’t happen, so let’s forget it. So, it turns out that d^2-(r_k+r_K)^2 is ((Hk-hK)^2-1)/(k^2K^2). Since all the letters there are positive integers, we see that d^2-(r_k+r_K)^2\geq 0, with equality iff Hk-hK=1. This says, based on our work yesterday, precisely that two Ford circles intersect iff the fractions they correspond to are neighbors in a Farey sequence, and when this happens, they intersect at a single point (they are tangent to eachother).

This justifies the picture from above, then. The circles never overlap, and some of them are tangent.

It might be worth it to go back and justify why any vertical line at an irrational value slices through infinitely many of the Ford circles. To that end, let \omega\in (0,1) be irrational. The two circles at 0/1 and 1/1 both have radius 1/2, and so certainly x=\omega hits at least one Ford circle, kicking off an induction argument.

Suppose that x=\omega hits the Ford circle h/k. For the sake of argument, let us suppose that \omega>h/k, so the vertical line lies to the right of the center of the circle. Not much changes if the opposite inequality is true, so let’s just stick with this one. I aim to show that x=\omega hits a circle with a smaller radius, i.e. goes through a circle corresponding to a fraction with a bigger denominator than k. I claim that it hits one of the circles tangent to the circle at h/k. By the above, we know that these are the circles corresponding to neighbors of h/k in some Farey sequence. Since I’m thinking about circles to the right of h/k, these will be successors in the Farey sequence. Yesterday we said that all of these successors are (m,1)-weighted mediants of h/k with H/K where H/K is the successor of h/k in F_k (the first Farey sequence that h/k shows up in).

Consider, then, the circles corresponding to the (1,1), (2,1), (3,1),… weighted mediants of h/k with H/K. Let me call the circles C_1,C_2,\ldots, using C for the circle at h/k. It isn’t too much work to check the necessary inequalities to show that the center of C_1 is further right than the right-most point on C. I’ve already said, even if not directly, that for each n, C_n is tangent to C_{n+1}. So, if you want, you may start at the top of C_1, and move left along the tops of all the circles in turn, jumping from one to the next at points of tangency. How far can you go doing this? Well, if you take the limit as m\to\infty of the (m,1)-weighted mediant of h/k with H/K, you get h/k (l’Hospital!). So, the tops of the circles form an unbroken path from the top of C_1 to as close to h/k, on the right, as we care to get. The vertical line x=\omega, which passes through the right side of C, must surely pass through this path, and therefore at least one of the C_n.

That’s probably just about enough with Ford circles for now. I’m not sure what I’ll be writing about tomorrow. Hopefully something else fun. I would like to note that, as I was writing this post, I was excited to find a connection to continued fractions. I knew a connection should be there (and I’ll probably find plenty more later), and found it while asking “how can we tell which of the C_n does x=\omega pass through?”. I remembered from reading about continued fractions, [a_0;a_1,a_2,\ldots], that the “convergents”, [a_0;a_1,\ldots,a_n] are rationals p_n/q_n that give “best rational approximations”. Those should be the circles that x=\omega passes through, or so. And so if you pass through p_n/q_n, the next circle you should get to is p_{n+1}/q_{n+1}. Well, it turns out, there is a nice relationship between successive convergents. Namely, p_{n+1}=a_{n+1}p_n+p_{n-1} and q_{n+1}=a_{n+1}q_n+q_{n-1}. Look at that! It’s the (a_{n+1},1)-weighted mediant of p_n/q_n with p_{n-1}/q_{n-1}! Fantastic. Could this story get any better? I’m glad I’ve decided to find out this month.


Tags: , ,

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: