# distance formula in Farey graph?

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.

-
When $p/q=1/0$ then this distance is essentially the number of steps in the Euclidean algorithm for $r$ and $s$ (and the general case reduces to this via $SL_2(\mathbb{Z})$-equivariance). Now I don't know if there is a "formula" for the number of steps in the Euclidean algorithm starting at $r$ and $s$ ( save perhaps for the phrase "the number of steps in the Euclidean algorithm starting at $r$ and $s$:-)). –  Robin Chapman Jul 22 '10 at 20:34
Let $a$ and $b$ be integers such that $ap+bq=1$. Then the distance is the length of the continued fraction expansion of $(ar+bs)/(ps-qr)$, where $\infty$ has length zero. Dually, it is the number of Ford circles that intersect the vertical line with real part $(ar+bs)/(ps-qr)$. –  S. Carnahan Jul 22 '10 at 20:45
Dear @Alexey Ustinov, please do not edit more than three old posts each day, as they get bumped to the front page: see this meta thread. You have edited over ten old posts in the past 24 hours. Also, this question could use several tags which are more relevant than the the tag 'continued-fractions'. –  Ricardo Andrade Dec 12 '13 at 17:42
@Ricardo Andrade: Sorry, now I realize this rule. –  Alexey Ustinov Dec 13 '13 at 0:56

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)$.

-
That's a very nice simple inductive formula. It could be fun to work out whether it can be translated into a reasonable closed form answer. –  Allen Hatcher Jul 25 '10 at 2:46
The figures in this answer don't appear for me (XP and firefox). –  BS. Jul 25 '10 at 12:45
hmmm, not sure what's wrong. Here's the links: math.berkeley.edu/~ianagol/tree2.pdf dl.dropbox.com/u/8592391/pivotseq2.pdf math.berkeley.edu/~ianagol/convex.pdf Are you able to download these? –  Ian Agol Jul 25 '10 at 16:44
I switched the figures to jpeg files - maybe the pdf files weren't displaying in your browser? –  Ian Agol Jul 26 '10 at 5:16
This works fine now. The problem was indeed pdf files : I pen them outside firefox. Thanks ! –  BS. Jul 26 '10 at 10:39

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.

-

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.

-