## 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 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.