distance formula in Farey graph?

Question

Consider the usual "Farey graph", i.e. the 1-skeleton of the (essentially unique) triangulation of the disk by ideal triangles. If one insists that 1/0, 0/1, and 1/1 are vertices of a triangle then the vertices of this graph are naturally in bijective correspondence with the rationals, together with a single point 1/0. Another name for this is the "Hatcher-Thurston complex", or "pants complex" or "curve complex" associated to simple, closed, unoriented curves on a torus (or punctured torus, or four-punctured sphere, with appropriate modifications to the definitions).

Is there a reference for a formula for the (combinatorial) distance function d(p/q, r/s) in this graph? There seem to be plenty of references to connections to continued fractions and intersection numbers, but I've been unable to locate an explicit statement with a formula.

Answer 1

Given $p/q, r/s \in \mathbb{Q}$, where $\gcd(p,q)=\gcd(r,s)=1$, choose the triangles in the Farey tessellation whose interior intersects the geodesic connecting $p/q$ and $r/s$ in $\mathbb{H}^2$:

If $ps-qr=1$, then $d(p/q,r/s)=1$ and there is a geodesic of the Farey tessellation connecting the two points. Otherwise, there will be a non-trivial triangle intersecting the geodesic. The triangles may be grouped together into maximal collections of triangles sharing a common vertex (a "pivot"). Let $p_i$ be the number of triangles in the $i$th group. Associated to this sequence of grouped triangles is a canonical sequence $[p_1,p_2, \ldots, p_k]$, where $p_1>1, p_k>1$. Define $l([p_1,p_2,\ldots,p_k])=d(p/q,r/s)$.

Note that the sequence of triangles $[1,p_2, \ldots, p_k]$ is the same as the sequence $[1+p_2, \ldots, p_k]$, since the lone triangle shares a vertex with the pivot of the adjacent group, which is why we may assume that $p_1>1$, and similarly $p_k>1$.

The formula for the the Farey distance is computed inductively by $l([p_1,p_2,\ldots,p_k]) = 1+ l([p_2,\ldots,p_k])$, and for $k=1$, $l([p_1])= 2$ (we are assuming that $p_1>1$ when $k=1$, since otherwise $d(p/q,r/s)=1$). Here, if $p_2=1$, then $l([p_2,\ldots,p_k])=l([1+p_3,\ldots,p_k])$. To prove this formula, one can see that a shortest path from $p/q$ to $r/s$ must go through the adjacent pivot to $p/q$. If not, a case-by-case analysis shows that one can find a shorter path, unless $p_1=2$ and the path goes through the lower two edges of the first group of triangles. But then one can take an equal length path going through the first pivot.

To relate this to the continued fraction expansion, use an element of $A\in PGL_2(\mathbb{Z})$ such that $A(p/q)=\infty$, and $0\leq A(r/s) \leq 1/2$. Then $d(p/q,r/s)=d(A(p/q),A(r/s))=d(\infty,A(r/s))$. To compute the triangle sequence in this case, we may use the continued fraction expansion for $A(r/s)$ to get $[p_1,\ldots,p_k]$ via $A(r/s)=1/(p_1+1/(p_2+1/(\cdots +1/p_k)\cdots )))$:

In this example, $p/q=\infty=1/0$, $r/s=2/5$, and the continued fraction is $[2,2]$, since $2/5=1/(2+1/2)$.

Answer 2

The distance from $1/0$ to $p/q$ in the Farey diagram is some function of the continued fraction for $p/q$, which determines the strip of triangles in the diagram joining $1/0$ and $p/q$. If all the terms in the continued fraction are at least $2$ then the distance is the length of the continued fraction, but if some terms are $1$ then the distance can be less than the length. For example, if the first, third, fifth, ... terms are all $1$ then the distance is about half the length of the continued fraction, and similarly if the even-numbered terms are all $1$. It should be possible to describe the distance explicitly in terms of the locations of $1$'s in the continued fraction, though I don't know if it's a neat answer. I would not be surprised if this has been worked out somewhere, but I don't know a reference.

Incidentally, the first place in the literature where the Farey diagram was written down explicitly seems to be an 1894 paper by Hurwitz in the Math. Annalen, on the reduction of binary quadratic forms. Farey series are of course older, from the early 1800s.

Answer 3

Just to record a nice fact, related to the answers already given: if $r, s$ are distinct slopes on the torus, then their Farey distance is bounded above by $\log_2(\iota(r,s)) + 1$, where $\iota(r, s)$ is the geometric intersection number (which is also the unsigned algebraic intersection number). A moment's thought shows that this bound is not tight.

Nonetheless, writing the bound this way can be useful.