Francis Bonahon

# The Farey-Ford tessellation and circle packing

The animated circles on the home page of my web site represent one of the most beautiful objects in mathematics, the combination of the Farey-Ford tessellation and circle packing. Here is a quick description.

Consider the number line as the x-axis in the plane, and look at all the rationals p/q on this number line. (Recall that a rational number is one that can be written as the quotient p/q of two integers p and q). For every such rational number p/q, draw a circle Cp/q of diameter 1/q2 that touches the x-axis exactly at p/q, and sits above this x-axis. This looks like a strange idea, but observe the outcome.
 -3/1 -5/2 -2/1 -3/2 -1/1 -1/2 0/1 1/2 1/1 3/2 2/1 5/2 3/1

We see that the circles Cp/q touch each other in a funny pattern. It is here convenient to add the top horizontal line of the picture, and to consider it as the "circle" C1/0 of infinite radius that touches the x-axis at the infinity point 1/0. This collection of circles, with disjoint interiors, is the Farey-Ford circle packing.

We will zoom in to investigate these patterns, but first let us add some features. Whenever the circles Cp/q and Cr/s touch each other, connect the numbers p/q and r/s by a semi-circle centered on the x-axis, as in

 -3/1 -5/2 -2/1 -3/2 -1/1 -1/2 0/1 1/2 1/1 3/2 2/1 5/2 3/1

Note that these semi-circles pass exactly through the points where the circles Cp/q and Cr/s touch each other. The color coding is a little difficult to explain here, but we can observe that the semi-circles decompose the half-plane sitting above the x-axis into curved triangles, each delimited by three semicircles of different colors. This decomposition of the upper half-plane is known as the Farey-Ford tessellation. ("Tessellation" is a fancy mathematical word for "tiling", and mathematicians think of the above triangles as similar to the tiles of a kitchen floor.)

Let's zoom between 0 and 1/2 in the above picture. We obtain

 0/1 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 1/2

and then again

 1/4 5/19 4/15 3/11 5/18 2/7 5/17 3/10 4/13 5/16 1/3

if we zoom some more between 1/4 and 1/3.

What we observe (and can be proved) is the following.
1. The circles Cp/q and Cr/s touch each other exactly when |ps-qr|=1.
2. When three circles Cp/q , Cr/s and Ct/u with p/q < r/s < t/u, then r = p+t and s = q+u. Namely, the middle term r/s = (p+t)/(q+u) is the "freshman addition" of the other two terms p/q and t/u (I hope you know that this is not the way you are supposed to add fractions).
The above "addition" of fractions is known as the Farey addition, after John Farey (1766–1826) who experimentally discovered a similar phenomenon when one lists all rational number p/q with |q| less that a given number (and knew nothing about circle packings or tessellations). The real discoverer (in 1928) of the Farey-Ford tessellation and circle packing is Lester Randolph Ford (1886–1967). The Farey-Ford tessellation and circle packing have many more interesting properties and appear in many branches of mathematics, from hyperbolic non-euclidean geometry to number theory. One reason is that they are closely related to the group SL2(Z) of 2-by-2 matrices with integer coefficients and determinant 1. Want to know more? An excellent reference is of course Chapter 8 of my book Low-dimensional geometry: from euclidean surfaces to hyperbolic knots.

Now, you are going to say that this is not exactly the original picture of circles moving within a circle. For this, we need to deform the half-plane delimited by the x-axis into the interior of the circle of radius 1 centered at the origin. The map f from the plane to itself defined by
f(x,y) = ( -(x2+y2-1)/(x2+y2+1) , 2x/(x2+y2+1) )
does just that. In fact, f sends every circle in the plane to a circle (interpreting a straight line as a circle of infinite radius), and in particular sends the upper half-plane to the interior of the unit circle. If we draw the images under f of the circles and semi-circles of the Farey-Ford tessellation and circle packing, we obtain

which looks more like what we wanted. Incidentally, the map f is better expressed in terms of the complex coordinate z = x+iy, where it becomes
f(z) = -(z-i)/(z+i).
In hyperbolic geometry, it provides an isometry between the upper half-plane model and the disk model for the hyperbolic plane.

Wait, wait! These circles are not moving. Well, here we jump from mathematics to art. The Farey-Ford tessellation and circle packing are invariant under horizontal translation of 1, and our coloring scheme under horizontal translation of 3. If we perform these translations in small increments, and combine them in an animated file, we get

We now just need to apply the above map f to go from the upper half-plane to the interior of the circle, et voilà. The mathematical content is the same as before, but it's clearly prettier.