\section{The modular torus, the stable norm, and Markoff triples}
\label{sec:dictionary}

\subsection{The modular torus}
Let $F_2=\langle x,y\rangle$ be the free group on two generators and let
$\rho:F_2\to\SL_2(\bZ)$ be the representation defined by
\[
 A:=\rho(x)=\begin{pmatrix}2&1\\1&1\end{pmatrix},\qquad
 B:=\rho(y)=\begin{pmatrix}2&-1\\-1&1\end{pmatrix}.
\]
Then $\tr A=\tr B=\tr AB=3$ and $[A,B]=ABA^{-1}B^{-1}=-T^6$. Let $T'$ be the
transpose of $T$. Then $A=TT'$, $B=T^{-1}T'^{-1}$, $TAT^{-1}=AB$ and
$TBT^{-1}=A^{-1}$. Since $\PSL_2(\bZ)$ is generated by the images of $T$ and $T'$, and
$T'=T^{-1}A$, it is generated by the images of $T$, $A$ and $B$. As the
subgroup generated by $A$ and $B$ is normalized by $T$, its image
$\Gamma'$ in $\PSL_2(\bZ)$ is therefore normal.

The group $\Gamma'$ contains the commutator subgroup of $\PSL_2(\bZ)$,
because $\PSL_2(\bZ)/\Gamma'$ is generated by the image of $T$ and hence is
cyclic. It is contained in the commutator subgroup, because $A$ and $B$ map
to the identity in the abelianization $\bZ/6$ of $\PSL_2(\bZ)$: $T'$ is
conjugate to $T^{-1}$ in $\PSL_2(\bZ)$, so the images of $T$ and $T'$ in
$\bZ/6$ are inverse to each other, and $A=TT'$, $B=T^{-1}T'^{-1}$.

Thus $\Gamma'$ is the commutator subgroup of $\PSL_2(\bZ)$, of index six. It is
a free group of rank two, torsion free, with one cusp, and the quotient
$\mathbb T=\bH/\Gamma'$ is a complete hyperbolic once-punctured torus, the
\emph{modular torus}. The representation $\rho$ identifies $F_2$ with
$\pi_1(\mathbb T)$ and induces the isomorphism
$H_1(\mathbb T,\bZ)=F_2^{\mathrm{ab}}\cong\bZ^2$ sending $x,y$ to the standard
basis vectors $e_1,e_2$.

An element of $F_2$ is \emph{primitive} if it belongs to some free basis of
$F_2$; its class in $H_1(\mathbb T,\bZ)=\bZ^2$ is then a primitive
vector. We use the following classical facts from McShane and
Rivin~\cite{MR}.

\begin{enumerate}
\item[(F1)] (\cite{MR}*{Fact 2.2}) The map sending a primitive element to its homology class
induces a bijection between the set of conjugacy classes of primitive
elements of $F_2$, modulo inversion, and the set $\bZ^2_\prim/\{\pm1\}$ of
primitive vectors modulo sign. For a primitive vector $v$ we write $w_v$
for a primitive element of $F_2$ in the corresponding class; it is
well defined up to conjugacy and inversion.
\item[(F2)] (\cite{MR}*{Facts 2.2, 2.3 and Lemmas 2.4, 2.5}) The conjugacy classes of primitive elements, modulo
inversion, correspond bijectively to the free homotopy classes of
essential, non-peripheral, unoriented simple closed curves on $\mathbb T$,
and each such class contains a unique closed geodesic. The geodesic in
the class of $w_v$ has length
$N(v):=2\arcosh\bigl(|\tr\rho(w_v)|/2\bigr)$.
\item[(F3)] (\cite{MR}*{\S5}) The function $v\mapsto N(v)$ on
$\bZ^2_\prim$ extends uniquely to a norm $N$ on $\bR^2$, by homogeneity on
rational vectors and continuity. For independent integral vectors $h,g$
one has the strict inequality $N(h+g)<N(h)+N(g)$ \cite{MR}*{(5.2)}.
\end{enumerate}

Following \cite{DLN}, we call $N$ the \emph{stable norm} of the modular
torus, and $\ball=\{x\in\bR^2:N(x)\le1\}$ its unit ball. The strict inequality in (F3) implies that $\ball$ is
\emph{strictly convex}, that is, its boundary $\partial\ball$ contains no
line segment: a segment in $\partial\ball$ would span a two-dimensional
cone on which $N$ is linear, and this cone contains two independent
integral vectors $h,g$, for which then $N(h+g)=N(h)+N(g)$. Since $N$ is a
norm, there are constants with $c|x|\le N(x)\le C|x|$.

Two primitive vectors $u,v$ with $\det(u,v)=\pm1$ are called \emph{Farey
neighbours}. If $u,v$ are Farey neighbours, then $w_u,w_v$ can be chosen
to form a free basis of $F_2$ \cite{MR}*{Theorem 2.6}; then $w_uw_v$ is a
primitive element with homology class $u+v$, and by (F1) we may take
$w_{u+v}=w_uw_v$. For the holonomy matrices $U=\rho(w_u)$,
$V=\rho(w_v)$ the trace identity $\tr(UV)+\tr(U^{-1}V)=\tr U\tr V$ and the
Fricke identity
\begin{equation}\label{eq:fricke}
 (\tr U)^2+(\tr V)^2+(\tr UV)^2=\tr U\,\tr V\,\tr UV+\tr[U,V]+2
\end{equation}
hold. Since $[U,V]$ is conjugate to $[A,B]^{\pm1}=-T^{\pm6}$ (by Nielsen's
theorem~\cite{MKS}, the commutator of a free basis of $F_2$ is conjugate to
$[x,y]$ or its inverse), $\tr[U,V]=-2$.

\subsection{Labels}
For a primitive vector $v$ define its \emph{label}
\[
 m(v):=\tfrac13\,\tr\rho(w_v)\in\tfrac13\bZ .
\]
We shall see in Lemma~\ref{lem:dictionary} that $m(v)$ is a positive
integer, in fact a Markoff number, so that the length formula
\eqref{eq:length} is a restatement of (F2).

For Farey neighbours $u,v$, applying the trace identity
to $U,V$ gives
\begin{equation}\label{eq:fareytrace}
 m(u+v)+m(u-v)=3\,m(u)\,m(v),
\end{equation}
and \eqref{eq:fricke} with $\tr[U,V]=-2$ gives the \emph{Markoff relation}
\begin{equation}\label{eq:fricke-labels}
 m(u)^2+m(v)^2+m(u+v)^2=3\,m(u)\,m(v)\,m(u+v).
\end{equation}

Let
\[
 r=\begin{pmatrix}0&1\\-1&1\end{pmatrix},\qquad
 s=\begin{pmatrix}-1&1\\0&1\end{pmatrix},\qquad
 \cK=\langle r,s\rangle\subset\GL_2(\bZ),
\]
and let $\sect$ be the closed sector
\[
 \sect=\{(p,q)\in\bR^2:\ 0\le2p\le q\},
\]
consisting of the origin and the vectors of slope $p/q\in[0,1/2]$ in the
upper half-plane. By Lemma~\ref{lem:dictionary} below, $\cK$ preserves
labels and the norm $N$, and every $\cK$-orbit of primitive vectors meets
$\sect$ in exactly one vector. A \emph{sorted} Markoff triple is a Markoff triple $(a,b,c)$ with
$a\le b\le c$.

\subsection{Farey neighbours, the Farey tree, and Farey fans}\label{sec:farey}
We collect the elementary facts about Farey neighbours that are used
throughout; all of them are classical \cite{HardyWright}*{Chapter III}.
Recall that primitive vectors $u,v$ are Farey neighbours if
$\det(u,v)=\pm1$; then $u+v$ is primitive, and it is a Farey neighbour of
both $u$ and $v$. We call $u+v$ the \emph{mediant} of $u$ and $v$.

\emph{The Farey tree of the sector.} The boundary vectors $e_2=(0,1)$ and
$f:=(1,2)$ of $\sect$ are Farey neighbours. Starting from the pair $(e_2,f)$
and repeatedly inserting mediants produces a binary tree of primitive vectors of $\sect$: the root is
$e_2+f=(1,3)$, and a node $v$, obtained as the mediant of two Farey neighbours
$u$ and $u'$ (its \emph{Farey parents}, with $u$ of smaller slope than $u'$),
has the two children $u+v$ (with parents $u,v$) and $v+u'$ (with parents
$v,u'$).

Every primitive vector $v$ of $\sect$ with $v\ne e_2,f$ occurs exactly
once in this tree. Indeed $v=(p,q)$ with $0<2p<q$ can be written
$v=\alpha e_2+\beta f$ with $\alpha=q-2p>0$ and $\beta=p>0$ coprime, and the
subtractive Euclidean algorithm applied to $(\alpha,\beta)$ traces the unique
path from the root to $v$.

Moreover, if $v$ is not the root, then one of its
parents is the mediant of the other parent and of a third vector $u''$, and
then $u-u'=\pm u''$; $u''$ is an earlier node of the tree or one of $e_2,f$.
For the root, $u-u'=e_2-f=-(1,1)$.

\emph{Farey fans.} For an integer $H\ge1$, the \emph{Farey fan of level
$H$} is the finite set $\mathcal F_H$ of rays $\bR_{>0}v$ through the
primitive vectors $v$ with $\hgt(v)\le H$. The connected components of
$\bR^2\setminus\bigl(\{0\}\cup\bigcup\mathcal F_H\bigr)$ are open convex
cones, which we call the
\emph{Farey sectors of level $H$}. The two primitive vectors $u,v$ of height
at most $H$ spanning the boundary rays of a sector are Farey neighbours,
and their mediant has height $>H$ (otherwise its ray would lie inside the
sector).

In the octant $0\le p\le q$ the rays of $\mathcal F_H$ are the
rays of slope $p/q$ with $p/q$ in the Farey sequence of order $H$, and a
sector of level $H$ with boundary slopes $a/b<c/d$ ($bc-ad=1$, $b,d\le H$,
$b+d>H$) has slope width $1/(bd)$. The other octants are obtained by the
symmetries $(p,q)\mapsto(\pm p,\pm q),(q,p)$.

The number of sectors of
level $H$ is $\asymp H^2$, since the number of primitive vectors of height
at most $H$ is $\asymp H^2$. The fan $\mathcal F_1$ consists of the eight
rays through $\pm e_1,\pm e_2,\pm(e_1+e_2),\pm(e_1-e_2)$, the primitive
vectors of height one; the first six of these vectors have label $1$ and
the last two have label $2$. The fans are nested: $\mathcal F_H\subset\mathcal F_{H'}$ for
$H\le H'$, so every sector of level $H'$ is contained in a sector of level
$H$.

\subsection{The dictionary}
\begin{lemma}\label{lem:dictionary}
The following statements hold.
\begin{enumerate}
\item The group $\cK$ is dihedral of order twelve, and every $k\in\cK$
preserves the label and the norm: $m(kv)=m(v)$ for $v\in\bZ^2_\prim$ and
$N(kx)=N(x)$ for $x\in\bR^2$.
\item Every $\cK$-orbit in $\bZ^2_\prim$ meets $\sect$ in exactly one point.
\item The map sending $(0,1)$ to $(1,1,1)$, $(1,2)$ to $(1,1,2)$, and
every other primitive vector $v\in\sect$ to the sorted triple formed by
the labels of $v$ and of its two Farey parents, is a bijection from
$\bZ^2_\prim\cap\sect$ onto the set of sorted Markoff triples. Under this
bijection the largest coordinate of the triple is $m(v)$.
In particular $m(v)$ is a positive integer for every primitive $v$, and
the length formula \eqref{eq:length} holds.
\item As $L\to\infty$,
\begin{equation}\label{eq:Tlength}
 \#\{v\in\bZ^2_\prim\cap\sect:\ N(v)\le L\}\sim c_N L^2
\end{equation}
for a constant $c_N>0$.
\end{enumerate}
\end{lemma}

\begin{proof}
(a) One checks $r^3=-I$, $s^2=I$ and $srs=r^{-1}$, so $\cK$ is dihedral of
order twelve. The substitutions $(x,y)\mapsto(y^{-1},xy)$ and
$(x,y)\mapsto(x^{-1},xy)$ define automorphisms $\phi_1,\phi_2$ of $F_2$, and
$\rho\circ\phi_i$ has the same traces $(3,3,3)$ as $\rho$ on $x,y,xy$.

The representation $\rho$ is irreducible ($A$ and $B$ have no common
eigenvector), and an irreducible representation of $F_2$ in $\SL_2$ is
determined up to conjugacy by the traces of $x,y,xy$ (the classical
theorem of Fricke and Vogt; see \cite{Goldman}*{Theorem A}).

Hence $\rho\circ\phi_i$ is conjugate to $\rho$, and
$\tr\rho(\phi_i(w))=\tr\rho(w)$ for every $w\in F_2$. The automorphism
$\phi_i$ sends $w_v$ to a primitive element with homology class
$k_iv$, where $k_1=r$ and $k_2=s$ are the matrices induced on
$H_1=\bZ^2$ ($\phi_1$ induces $e_1\mapsto-e_2$, $e_2\mapsto e_1+e_2$, and
$\phi_2$ induces $e_1\mapsto-e_1$, $e_2\mapsto e_1+e_2$). Therefore $m(rv)=m(v)$
and $m(sv)=m(v)$ for all primitive $v$, hence $m(kv)=m(v)$ for $k\in\cK$,
and $N(kv)=N(v)$; by homogeneity and continuity $N\circ k=N$ on $\bR^2$.

(b) The element $-I=r^3$ lies in $\cK$, and $\cK/\{\pm I\}$ acts on slopes
by the two maps $\sigma\mapsto1/(1-\sigma)$ (induced by $r$) and
$\sigma\mapsto1-\sigma$ (induced by $s$). The six images of the interval
$[0,1/2]$ under this group of order six are the intervals
\[
 [0,\tfrac12],\ [\tfrac12,1],\ [1,2],\ [2,\infty],\ [\infty,-1],\ [-1,0]
\]
of $\bR\mathbb P^1$, which cover $\bR\mathbb P^1$ and have disjoint interiors.
The endpoints form the two orbits $\{0,1,\infty\}$ and $\{1/2,2,-1\}$, each
of which meets $[0,1/2]$ once. Hence every direction has exactly one
$\cK$-image of slope in $[0,1/2]$, and of the two primitive vectors on that
direction exactly one has $q>0$, since the slope is finite.

(c) We show that the map of (c) sends the Farey tree of $\sect$ to the tree
of sorted Markoff triples, root to root and children to children; such a
map of rooted binary trees is a bijection.

Let $v\in\sect$ be primitive, $v\ne e_2,f$, with Farey parents $u,u'$.
We claim: $m(u),m(u'),m(v)$ are positive integers, the sorted triple formed
by them is a Markoff triple with largest coordinate $m(v)$, and the triples
of the two children of $v$ are the two children of this triple.
By \eqref{eq:fareytrace} applied to the Farey neighbours $u,u'$ and the
relation $u-u'=\pm u''$ of \S\ref{sec:farey},
\[
 m(v)=3\,m(u)\,m(u')-m(u'')
\]
with $u''$ an earlier node or one of $e_2,f,(1,1)$; here $m(e_2)=\tr B/3=1$,
$m(f)=\tr(AB^2)/3=2$ ($AB^2$ is the holonomy of $f=e_1+2e_2$) and
$m(1,1)=\tr AB/3=1$. For the root $v=(1,3)$ this gives $m(v)=6-1=5$, and
$(1,2,5)$ is a Markoff triple with the two children $(1,5,13)$ and
$(2,5,29)$ attached to $(1,4)=e_2+v$ and $(2,5)=v+f$.

For a general node, induction along the tree together with the Markoff
relation \eqref{eq:fricke-labels} shows that $(m(u),m(u'),m(v))$ is a Markoff
triple. The child $u+v$, with parents $u,v$, has label $3m(u)m(v)-m(u')$,
and the child $v+u'$, with parents $v,u'$, has label $3m(v)m(u')-m(u)$. If
$(a,b,c)$ is the sorted triple formed by $m(u),m(u'),m(v)$, the triples of
the two children of $v$ are the two children $(a,c,3ac-b)$ and $(b,c,3bc-a)$ of $(a,b,c)$, and
$3ac-b\ge3c-b\ge2c>c$ shows that the new label is the largest coordinate.

On the other side, the sorted Markoff triples form a tree under the Vieta
involutions.
If $(a,b,c)$ is a sorted Markoff triple, then $c'=3ab-c=(a^2+b^2)/c$ is a
positive integer. If $(a,b)\ne(1,1)$, then the quadratic
$z^2-3abz+a^2+b^2$, whose roots are $c$ and $c'$, takes at $z=b$ the value
\[
 a^2-(3a-2)b^2<0,
\]
so $0<c'<b<c$. Hence the sorted rearrangement of $(c',a,b)$ is a sorted Markoff
triple with maximum $b<c$, the \emph{parent} of $(a,b,c)$, and $(a,b,c)$ is
one of the two children of its parent.

If $a=b$, the
equation forces $a=b=1$ and $c\in\{1,2\}$; if $b=c$ it forces
$a=b=c=1$. Hence every sorted triple other than $(1,1,1)$ and $(1,1,2)$
has $a<b<c$, two distinct sorted children and a unique parent. Descending
along parents leads to $(1,2,5)$, so the sorted triples other than
$(1,1,1)$ and $(1,1,2)$ form a binary tree rooted at $(1,2,5)$ in which
each triple occurs exactly once.

The map sending $v$ to the sorted triple formed by $m(u),m(u'),m(v)$ is a
map of rooted binary trees that respects the children, so it is a bijection.
Together with $e_2\mapsto(1,1,1)$ and $f\mapsto(1,1,2)$ this proves (c).
In particular every label is a positive integer, and the formula for
$N(v)$ in (F2) becomes the length formula \eqref{eq:length}.

(d) The region $\sect\cap L\ball$ is convex with perimeter $O(L)$, so the
number of lattice points in it is $\area(\sect\cap\ball)L^2+O(L)$. M\"obius
inversion over the common divisor of the coordinates gives
$\#(\bZ^2_\prim\cap\sect\cap L\ball)=\area(\sect\cap\ball)L^2/\zeta(2)+O(L\log L)$,
which is \eqref{eq:Tlength} with $c_N=\area(\ball)/(12\zeta(2))$; here we
used that $\ball$ is $\cK$-invariant by (a) and that the twelve images of
$\sect$ under $\cK$ tile the plane by (b).
\end{proof}

\begin{remark}
Lemma~\ref{lem:dictionary} identifies $T(X)$ with the number of primitive
vectors of $\sect$ with $N\le L$, and $D(X)$ with the number of
distinct values of $N$ on them, where $L=2\arcosh(3X/2)$; this is the form
in which Theorem~\ref{thm:main} is proved in \S\ref{sec:proof-main}.
\end{remark}