June 7, 2008

Farey Sequences and the Stern-Brocot Tree

Posted by John Baez

guest post by Tim Silverman

I want to discuss in more detail the modular curves $X\left(N\right)$, ${X}_{1}\left(N\right)$ and ${X}_{0}\left(N\right)$, that is, the quotients of the upper half plane $H$ by $\Gamma \left(N\right)$, ${\Gamma }_{1}\left(N\right)$ and ${\Gamma }_{0}\left(N\right)$ respectively (with cusps filled in). These are charismatic entities — for example, you may have seen Greg Egan’s movie of $X\left(7\right)$, also known as Klein’s quartic curve:

I also want to talk about the actions of the Hecke operators $$ and ${T}_{p}$ on modular forms—or at least the corresponding actions on modular curves. Alas, I don’t think I’m going to get there in this post, but I can at least make a start.

But before I talk about all that, I want to talk about Farey sequences!

I was introduced to Farey sequences by a maths teacher at school, when I was about 13 or so, one afternoon when I’d done all my work and was feeling bored. They’re a simple and cute idea, and I found them kind of fascinating, but, not being much of a number theory person, I never looked into them all that deeply. But one stumbles across these things in the oddest places.

What is a Farey sequence? It’s very simple. Take all the reduced fractions from 0 to 1 (inclusive) with denominators no larger than some maximum $n$. Now arrange them in order of increasing value. And that’s a Farey sequence. Thus Farey sequences include

$\frac{0}{1},\frac{1}{1}$

$\frac{0}{1},\frac{1}{2},\frac{1}{1}$

$\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1}$

and so on. Here’s the ninth Farey sequence:

$\frac{0}{1},\frac{1}{9},\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{2}{9},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{4}{9},\frac{1}{2},\frac{5}{9},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{7}{9},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8},\frac{8}{9},\frac{1}{1}$

There are some curious facts about Farey sequences. Here’s one: if $\frac{a}{b}$ and $\frac{c}{d}$ appear adjacent to one another in some Farey sequence, then $\mathrm{bc}-\mathrm{ad}=1$.

Here’s another: if $\frac{a}{b}$ and $\frac{c}{d}$ appear adjacent to one another in some Farey sequence, then the next fraction which gets inserted between them, as you work your way through the successive Farey sequences, is the fraction $\frac{a+c}{b+d}$. This funny combination is called the mediant of $\frac{a}{b}$ and $\frac{c}{d}$, since it always lies between them. By repeatedly taking mediants, we build up all Farey sequences, and hence get each rational number from $0$ to $1$ exactly once.

We can indicate the way that the mediant derives from two parent fractions by drawing lines from the parents to their mediant:

Farey Sequence as tree 0/1 1/1 1/2 1/3 2/3 1/4 3/4 1/5 4/5 2/5 3/5
A Farey sequence in tree form

Additionally, one of the parents must always derive from the other—it must have been inserted as a mediant itself at some earlier time. So if a fraction is connected to its parents by a pair of lines, the parents must also be connected to each other. So these lines actually make up a bunch of triangles, except at the top of the picture where everything starts. Taking the three numbers at the vertices of a triangle, any one of them can be derived from the other two either as their mediant, $\frac{a+b}{c+d}$, or as what we might call their ‘mediant difference’, $\mid \frac{a-b}{c-d}\mid$. In fact every pair of numbers joined by a line belongs to two triangles (one on either side of the line joining them), and one of the triangles will contain their mediant as its third point, while the other will contain their mediant difference instead!

So, can the Farey tree be extended to include fractions outside the interval $\left[0,1\right]$? That’s something we might be wondering, and the answer is Yes! In fact, this would have happened already if we hadn’t foolishly forgotten something: we’ve included fractions with denominators of $1$, $2$, $3$, etc, but we’ve forgotten to include fractions with denominator $0$! How could we have been so careless? Let us remedy this oversight at once!

Including the fraction $\frac{1}{0}$ right at the top of the tree, it turns out that we can actually derive $\frac{1}{1}$ from this together with $\frac{0}{1}$, as their mediant, and then we can get $\frac{2}{1}$ from $\frac{1}{0}$ and $\frac{1}{1}$, and so forth, and by building up mediants, we can get all non-negative rational numbers that way. The whole tree is called the Stern-Brocot tree.

Stern-Brocot tree 1/0 0/1 1/1 2/1 1/2 3/2 1/3 2/3 4/3 5/3 1/4 3/4 5/4 7/4 1/5 4/5 2/5 3/5 6/5 9/5 7/5 8/5
A piece of Stern-Brocot Tree

Once we’ve made these extensions, and added an edge connecting $\frac{1}{0}$ and $\frac{0}{1}$, we see that every fraction in the tree, including the ones right at the top, belongs to a triangle—in fact, it belongs to an infinite number of triangles! We can just keep forming new mediants from it with its new neighbours forever. However, an infinite number of triangles hanging off every vertex is rather unmanageable. Is there some way we can get a toy version, with only a finite number of triangles instead? For instance, suppose we mod out the fractions by some natural number $N$? That is, we mod out both numerator and denominator by $N$, taking care not to forget that $\frac{a}{b}=\frac{-a}{-b}$? Then many different $ℤ$-fractions will map to the same $ℤ/\left(N\right)$-fraction, and if we identify the corresponding points, and also, of course, identify the corresponding edges connecting corresponding points, then we will get something finite.

For instance, suppose we take the above tree mod $3$ (reducing the fractions where necessary to their lowest form, and bearing in mind that $1=-2$, so $\frac{1}{2}=\frac{-1}{-2}=\frac{2}{1}$). We get this:

Stern-Brocot Mod 3 1/0 0/1 1/1 2/1 2/1 0/1 1/0 1/0 1/0 1/0 1/1 0/1 2/1 1/1 2/1 2/1 1/1 0/1 0/1 0/1 2/1 1/1
A piece of Stern-Brocot Tree Mod 3

Or reducing mod $4$ (and bearing in mind that $-1=3$ and $-2=2$, we get this:

Stern-Brocot Mod 4 1/0 0/1 1/1 2/1 1/2 1/2 3/1 2/1 0/1 2/1 1/0 1/0 1/0 1/0 1/1 0/1 2/1 3/1 2/1 3/1 3/1 0/1
A piece of Stern-Brocot Tree Mod 4

The rule about mediants and mediant differences still applies, but sometimes, with all the swapping of signs, we’ve switched around which fraction relates to which how!

Anyway, with these trees in hand, all we need to do is identify the vertices and edges correctly, and we’ll get something interesting and finite. In fact, while we’re about it, why not fill in those triangles? Then we’ll get a compact surface! It will be triangulated, and in fact each vertex will be the apex of just $N$ triangles (this is completely obvious in the case of the vertex $\frac{1}{0}$, but it applies to all vertices). Or, dually, every vertex will stand at the centre of an $N$-gon, while each of the triangular faces gives rise, dually, to a vertex at which $3$ $N$-gons meet.

Wait a minute …

That sounds familiar …

Could it be … ?

Yes it is! The compact surface we have just constructed is none other than $X\left(N\right)$, the quotient of $H$ by $\Gamma \left(N\right)$. Quel surprise! The fractions mod $N$ correspond to the cusps, and we can make the dual tiling completely regular if we pick the right constant-curvature metric (which will need positive curvature for $N<6$, negative curvature for $N>6$, and will have to be flat for $N=6$).

In fact, this also works for the full Stern-Brocot tree, without any modding out, with fractions over all integers. We can see this either arithmetically or geometrically.

Arithmetically, replace the fraction $\frac{a}{b}$ by the element $\left(\begin{array}{c}a\\ b\end{array}\right)$ in ${ℤ}^{2}$. Of course, $\mathrm{SL}\left(2,ℤ\right)$ acts on this by ordinary matrix multiplication; indeed, $\mathrm{PSL}\left(2,ℤ\right)$ acts on it too, more nicely, since switching the signs of both numerator and denominator doesn’t affect the value of the fraction.

In particular, if we pick an element of $\mathrm{PSL}\left(2,ℤ\right)$ such as

$\left(\begin{array}{cc}a& b\\ c& d\end{array}\right),$

then those two starting fractions at the top of the tree, $\frac{0}{1}$ and $\frac{1}{0}$, will get sent, under the action of that group element, to a pair of fractions $\frac{a}{c}$ and $\frac{b}{d}$ such that $ad-bc=-1$. (That minus sign is a result of listing the fractions the ‘wrong’ way around). This same relation holds true of any two adjacent elements in a Farey sequence, and since some member of $\mathrm{PSL}\left(2,ℤ\right)$ is available to send $\frac{0}{1}$ and $\frac{1}{0}$ to any adjacent pair, we get all Farey sequences in this way—over all integers, not just in the interval $\left[0,1\right]$.

Now, $\frac{0}{1}$ and $\frac{1}{0}$ are joined to each other by an edge, and, being adjacent elements of a Farey sequence, so will their images be. In addition, each of $\frac{0}{1}$ and $\frac{1}{0}$ is also joined by an edge to $\frac{1}{1}$, their mediant. But the mediant of fractions corresponds simply to the sum in ${ℤ}^{2}$ (considered as a $ℤ$-module). And obviously the sum relation is preserved by $\mathrm{PSL}\left(2,ℤ\right)$. So if $\frac{0}{1}$ gets sent to $\frac{a}{c}$ and $\frac{1}{0}$ gets sent to $\frac{b}{d}$, then $\frac{1}{1}$ gets sent to the mediant of $\frac{a}{b}$ and $\frac{c}{d}$, meaning that the other two sides of that top triangle $\frac{0}{1}$-$\frac{1}{0}$-$\frac{1}{1}$ are also preserved—sent to sides of a triangle in the image.

So triangles are sent to triangles. Moreover, since the relation of being the mediant (or sum) of the other two vertices—as opposed to their mediant difference (or difference)—uniquely picks out one vertex of a given triangle, and since the sign of the determinant—or, more simply, which of the parent vertices is larger—uniquely picks an orientation of the triangle, each triangle is sent to another triangle in only one way. So $\mathrm{PSL}\left(2,ℤ\right)$ acts freely on the set of triangles, and of course preserves their relations.

Geometrically, as we can see from Don Hatch’s nice Hyperbolic Tesselations web page, the tilings of the hyperbolic plane by regular $n$-gons, $3$ meeting at each vertex, have a limiting case with a tiling by what one might call regular $ℤ$-gons, or regular $\infty$-gons, with an infinite number of sides! They appear in the website as {infinity, 3}:

Dually, we get a tiling by triangles, an infinite number of which meet at the ‘centre’ of each $ℤ$-gon. These triangles correspond precisely to the triangles in the Stern-Brocot tree. Rather confusingly, however, in the Poincaré disk model, the ‘centre’ of a $ℤ$-gon appears at the edge of the disk—that’s the sort of thing that happens when you have an infinite number of sides and are trying to show them all in a bounded region.

If we compare the Poincaré disk model of the hyperbolic plane with the ‘upper half-plane’ model, we see that the real line of the latter goes to the boundary circle of the former. The $ℤ$-gons, drawn in the Poincaré disk, are all tangent to the boundary circle, each with its own distinct point of tangency, and these points correspond precisely to the rational numbers (together with $\infty$). In turn, these rational numbers are the ones in the Stern-Brocot tree, i.e. at the vertices of the triangles, which can also be seen as tiling the hyperbolic plane, dually to the $ℤ$-gons. In this way, we also get to label each $ℤ$-gon by a unique rational number, and this is inherited when we go over to the version mod $N$—fractions also being reduced mod $N$.

Given all this, one way to try and understand the way that geometry and arithmetic interact in $X\left(N\right)$ is by working our way down the Stern-Brocot tree mod $N$, which will correspond to working our way outward from one of the $N$-gons in $X\left(N\right)$. What we’re going to see is a series of concentric circles of fractions with successively incrementing denominators.

But that, I think, is something for another post.

Posted at June 7, 2008 1:18 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1706

Re: Farey Sequences and the Stern-Brocot Tree

There seems to be a lot of beautiful classical geometry connected to such locally symmetric spaces, e.g. MacPherson and McConnell construct in:

“Classical projective geometry and modular varieties”, in “Algebraic analysis, geometry, and number theory” (Baltimore, MD, 1988)

cell complexes equivalent to (compactified) locally symm. spaces from configurations of projective geometry:

“Classical projective geometry was a beautiful field in mathematics. It died, in our opinion, not because it ran out of theorems to prove, but because it lacked organizing principles by which to select theorems that were important. Also, it was isolated from the rest of mathematics. Much of what we do may be regarded as direct continuation of nineteenth century synthetic geometry. In fact, we hope the new motivation of studying C-complexes will provide projective geometry with one organizational principle, and with one relation tying it to “mainstream” mathematics. We note … representable matroids, arrangements of hyperplanes, and motivic cohomology. A large part of this paper’s exposition is motivated by this dream of continuing classical projective geometry.”

Here is a related overview.

Posted by: Thomas Riepe on June 8, 2008 1:40 PM | Permalink | Reply to this

Re: Farey Sequences and the Stern-Brocot Tree

Posted by: Mike Stay on June 12, 2008 4:48 AM | Permalink | Reply to this

Re: Farey Sequences and the Stern-Brocot Tree

Great stuff, Tim!

I think it’s really cool how the Platonic solids and Klein’s quartic curve turn out to be modular curves $X\left(N\right)$ — especially since I was interested in all these things before I realized how they fit together!

And, it’s even better that triangulations of these curves $X\left(N\right)$ arise naturally from looking at the Stern–Brocot tree mod $N$. Only through a ‘Big Crunch’ that unifies lots of concepts like this will I ever be able to keep track of them all!

Posted by: John Baez on June 12, 2008 7:44 AM | Permalink | Reply to this

Re: Farey Sequences and the Stern-Brocot Tree

Tim, are you able to state the precise rules for reducing fractions modulo $N$? For $N=7$ I can’t figure out how to get a total of 24 fractions, which is what would seem to be needed for Klein’s quartic curve. The 48 non-zero points in ${ℤ}_{7}^{2}$ fall on just 8 rays of 6 points each, so obviously you’re doing a subtler identification than that, but I can’t figure out precisely what it is!

My naive rules would give:

$0/1\equiv 0/2\equiv 0/3\equiv 0/4\equiv 0/5\equiv 0/6$

$1/0\equiv 2/0\equiv 3/0\equiv 4/0\equiv 5/0\equiv 6/0$

$1/1\equiv 2/2\equiv 3/3\equiv 4/4\equiv 5/5\equiv 6/6$

$1/2\equiv 2/4\equiv 3/6\equiv 4/1\equiv 5/3\equiv 6/5$

$1/3\equiv 2/6\equiv 3/2\equiv 4/5\equiv 5/1\equiv 6/4$

$1/4\equiv 2/1\equiv 3/5\equiv 4/2\equiv 5/6\equiv 6/3$

$1/5\equiv 2/3\equiv 3/1\equiv 4/6\equiv 5/4\equiv 6/2$

$1/6\equiv 2/5\equiv 3/4\equiv 4/3\equiv 5/2\equiv 6/1$

Posted by: Greg Egan on July 5, 2008 10:38 AM | Permalink | Reply to this

Re: Farey Sequences and the Stern-Brocot Tree

Yes, you can cancel minus signs (because you can do this within fractions over $ℤ$) but you can’t cancel other units within $ℤ/\left(N\right)$ (that is, here, ${𝔽}_{7}$).

So you can identify, e.g., $\frac{1}{2}$ with $\frac{6}{5}$, but $\frac{2}{4}$ is something else.

So the 6 points on each line actually split up into 3 pairs, giving you $8×3=24$.

More generally, we can pick out the lines within $\left(ℤ/\left(N\right){\right)}^{2}$, the way you did, but then we split these up, ending up with half-the-size-of-the-group-of-units times as many cusps as you might expect. (So here, 3 times as many, since there are 6 units in ${𝔽}_{7}$).

This follows, I think, from the fact that all we are doing with our fractions over $ℤ$ is identifying integers $a$ with $a+N$; we don’t get extra cancellations as well.

This confused me a lot when I was first starting out on this.

I’m sweating blood trying to prepare the second article in this series, in which I talk about some of this stuff in more detail, but it’s slow work. Maybe next week I’ll have a little more time …

Posted by: Tim Silverman on July 5, 2008 3:50 PM | Permalink | Reply to this

Re: Farey Sequences and the Stern-Brocot Tree

Thanks, I get it now! And thanks for writing the article, it’s fascinating.

Posted by: Greg Egan on July 5, 2008 4:08 PM | Permalink | Reply to this

Re: Farey Sequences and the Stern-Brocot Tree

I posted a reply to this on the parallel thread on Modular Forms

Posted by: Gerard Westendorp on December 7, 2008 9:01 PM | Permalink | Reply to this

Re: Farey Sequences and the Stern-Brocot Tree

Thanks! It’s great to have lots of pictures like this.

Posted by: Tim Silverman on December 7, 2008 11:18 PM | Permalink | Reply to this
Read the post Pictures of Modular Curves (I)
Weblog: The n-Category Café
Excerpt: The first of a series of posts by Tim Silverman.
Tracked: September 16, 2010 7:40 AM
Read the post Pictures of Modular Curves (I)
Weblog: The n-Category Café
Excerpt: The first of a series of posts by Tim Silverman, with lots of pretty pictures.
Tracked: October 6, 2010 7:54 AM

Post a New Comment