Lattices and Farey Sequences

The goal of this essay is to introduce the beautiful Farey sequences, and to prove a result about them using an ingenious geometric interpretation. (This is based on Essay 5 from Ross Honsberger's Ingenuity in Mathematics.)

The $n$-th Farey sequence $F_n$ is defined as the sequence of rational numbers in $[0;1]$ with denominator $\le n$ (written in reduced form). For example,

$$F_6=\left\{\frac01<\frac16<\frac15<\frac14<\frac13<\frac25<\frac12<\frac35<\frac23<\frac34<\frac45<\frac56<\frac11\right\},$$ $$F_7=\left\{\frac01,\color{red}{\frac17},\frac16,\frac15,\frac14,\color{red}{\frac27},\frac13,\frac25,\color{red}{\frac37},\frac12,\color{red}{\frac47},\frac35,\frac23,\color{red}{\frac57},\frac34,\frac45,\frac56,\color{red}{\frac67},\frac11\right\}.$$

We write the terms of a Farey sequence in reduced form because we have no reason to do otherwise. In the second line, I highlighted the new terms.

Some person who might or might have not been called Farey made the remarkable discovery any term in $F_n$ other than $0$ and $1$ can be composed by adding its two neighbors incorrectly (if you want to feel official, this is called the mediant of the two fractions). To be more exact, if three consecutive terms of $F_n$ are $\frac ab<\frac cd<\frac ef$ (in reduced form), then $\frac cd=\frac{a+e}{b+f}$. (This is very obvious for the red terms, but it holds for the rest as well.)

This appears very wondrous and hard to prove. It is. Problem-solving instinct tells us to multiply this out; we get $c(b+f)=d(a+e)$. Let's now try grouping onto one side the terms corresponding to consecutive fractions in the sequence, like $bc-ad=de-cf$. So we want to prove that for any pair of consecutive terms $\frac ab$ and $\frac cd$, the number $bc-ad$ is the same. Some calculations motivate us to conjecture that it is in fact always $1$!

Nice conjecture! Unfortunately, though, we're stumped here and need some heavier machinery. We had a spoiler, however, that we will use geometric interpretation.

Ugh, the title spoils it all. Let's take the points both of whose coordinates are integers. (Such points are called lattice points, and they form a lattice.) Namely, represent $\frac ab$ in reduced form with point $(a,b)$.

I’ll graph this for $F_4$:

How could this help? Well, we were looking at consecutive terms in the Farey sequence $F_n$, namely $\frac ab$ and $\frac cd$. If you recall the coordinate area formula of a triangle, you will find that the signed area of the triangle $T$ with vertices $(0,0)$, $(c,d)$ and $(a,b)$ is half of $$(0\cdot d+c\cdot b+a\cdot 0)-(c\cdot 0+a\cdot d+0\cdot b)=bc-ad,$$ and note that this signed area is positive because we chose the orientation so. Thus, if we prove that the (not signed, everyday) area of this triangle is $\frac 12$, we are done.

This is where the lattice comes into the picture. If we consider a triangle with its vertices at lattice points, then the shoelace formula tells us that its area is half of a positive integer. Hence, we are in fact trying to show that $T$ has minimal area. Let’s try to find some properties of $T$ which could lead us to prove this.

Well, $T$ couldn’t have minimal area if it could be split into smaller triangles. For example, if there is a lattice point on the perimeter of or inside $T$ (other than the vertices), we could connect that point with the vertices, splitting $T$ into at least $2$ lattice triangles, both with area $\ge \frac12$. It turns out that the converse holds as well: if $T$ has no extra lattice points on its perimeter or inside it (in this case, $T$ is called a primitive triangle), then $T$ as area $\frac 12$.

So, the remaining proof consists of two steps: $(1)$ show that $T$ is primitive, $(2)$ show that primitive triangles have area $\frac12$.

Proof of (1). First of all, note that there is no lattice point inside the segment connecting $(0,0)$ with $(a,b)$ (or $(c,d)$). This is easy: if there were another lattice point $(x,y)$, then we would have $\frac xy=\frac ab$, or $bx=ay$. But as $a$ and $b$ are relatively prime, $a\mid bx$ implies $a\mid x$, giving $x\ge a$, which contradicts $(x,y)$ being inside the segment. (Alternatively, just recall that $\frac ab$ was in reduced form.)

Furthermore, triangle $T$ lies within the triangle formed by lines $x=y$, $y=n$, and $x=0$, so if there were a lattice point $(x,y)$ in $T$ strictly inside the angle $(a,b)-(0,0)-(c,d)$, then it also would lie in this square. In other words, we’d have $0\le x< y\le n$ ($x<y$ because this point cannot lie on $x=y$). Also, considering the slopes of the appropriate lines, we’d find

$$\frac ab<\frac xy<\frac cd.$$

Hence, we have found a term of the Farey sequence $F_n$ between $\frac ab$ and $\frac cd$. Contradiction!

Proof of (2). This is interesting in its own right. We will provide an area formula in lattice geometry, as a corollary of the following idea.

Consider a simple (i.e. not self-intersecting) lattice polygon $P$ with $i$ lattice points on the inside and $j$ on the perimeter. Then any partition of $P$ into primitive triangles contains the same number of triangles.

The key idea is a double-counting of angles. Let there be $p$ primitive triangles, then the sum of their angles is $p\cdot 180^\circ$. Each of the $i+j$ lattice points will be vertices of these primitive triangles, by definition of the primitive triangle. Hence, the $180^\circ$ or $360^\circ$ or whatever angle around these lattice points will be divided among these primitive triangles. This establishes

$$p\cdot 180^\circ=i\cdot 360^\circ+(j-2)\cdot 180^\circ,$$

because the sum of the internal angles of a simple $j$-gon is $(j-2)\cdot 180^\circ$ (it may seem a bit unorthodox, but we may feel free to have collinear vertices!). Therefore,

$$p=2i+j-2.$$

This proves our claim.

What next?

We already know the area of a primitive triangle $T$ is $\ge \frac 12$. We can prove it is exactly $\frac 12$ by surrounding an $T$ by some polygon and taking two different partitions into primitive triangles. First, we look at a partition containing $T$ - there, each triangle has area $\ge \frac 12$. Second, we look at a partition into triangles where every triangle has area exactly $\frac 12$ (and hence is primitive). Now due to there being equally many triangles in both partitions, we find that the total area can be equal only if each triangle had area $\frac 12$ in the first partition as well. Consequently, $T$ must have area $\frac 12$.

This idea can be quickly implemented using a rectangle surrounding $T$. For the first partition, we draw a rectangle around $T$ as shown in the diagram below, and then keep splitting up non-primitive triangles by connecting an inner lattice point with the vertices until we can’t split up any more (this stops because the area of primitive triangles is $\ge \frac12$). And for the second partition, it suffices to divide a $1\times m$ rectangle into $2m$ triangles, which is easy.

This establishes that primitive triangles have area $\frac 12$ and completes our proof of the property of Farey sequences. Let’s celebrate by noting a corollary, called Pick’s theorem:

Pick’s theorem. The area of a simple lattice polygon $P$ with $i$ lattice points on the inside and $j$ on the perimeter is

$$[P]= i+\frac j2-1.$$

[IMO 2013, problem 6]

Let $n\geq 3$ be an integer, and consider a circle with $n+1$ equally spaced points marked on it. Consider all labellings of these points with the numbers $0,1,\dots, n$ such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels $a<b<c<d$ with $a+d=b+c$, the chord joining the points labelled $a$ and $d$ does not intersect the chord joining the points labelled $b$ and $c$.

Let $M$ be the number of beautiful labellings, and let $N$ be the number of ordered pairs $(x,y)$ of positive integers such that $x+y\leq n$ and $\gcd(x,y)=1$. Prove that $$M=N+1.$$

Prove that $F_n$ has $1+\sum_{m=1}^n \varphi(m)$ terms, where $\varphi$ is the totient function.

Check how we can partition a $1\times m$ rectangle into $2m$ triangles.

Also, prove that given $T$, such a partition is always possible (where $T$ is triangle $CPQ$):