\documentclass[12pt]{article}
\usepackage{amsmath, amsfonts}
\usepackage[dvips]{graphicx}
\title{Markov Numbers, Farey Sequences, and the Ptolemy Recurrence}
\author{Gabriel Carroll, Andy Itsara, Ian Le, James Propp, (others?)}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}{corollary}[section]
\begin{document}
\maketitle
\begin{abstract}
We need to put in an abstract, but we can do this last.
\end{abstract}
\section{Observations}
From the correspondence of Markov polynomials with the points $(a,b)$, $a$ and $b$ relatively prime,
we make several observations characterizing the snake graph corresponding to the point (a,b).
As stated earlier, the graph corresponding to this point (a,b) can
be created by triangulating all the squares through which a vector from the origin passes in
order to get to the point (a,b). To the entire snake graph, each square through which the vector passes
then contributes a pair of x and y edges forming a 2-by-2 block, for convenience here called
a unit, and 2 z-edges attached to opposite corners of the unit. The squares with a lower left corner at (0,0) or (a-1, b-1)
contribute only 1 z-edge as one does not consider the endpoints (0,0) and (a,b) in the graph derived from the triangulation.
\begin{figure}
\centering
\includegraphics[height=3in]{correspondence}
\caption{Correspondence between (3,2) and a Markov snake graph with its edge weightings.}
\end{figure}
\section{Counting Matchings of Snake Graphs}
As noted by [David Speyer??, paper?] it is possible to calculate the number of matchings of a given snake graph using a recursive relation similar to that used in calculating the numerator of a continued fraction. If the quotients of a continued fraction are $[a_1,a_2,a_3...]$, we can calculate its nth convergent, $P_n/Q_n$ with the following recurrence:
\begin{alignat}{3}
P_0 & = 1 \qquad P_1 & = a_1 \qquad & P_{n+1} & = a_{n}P_{n}+ P_{n-1} \nonumber \\
Q_0 & = 0 \qquad Q_1 & = 1 \qquad & Q_{n+1} & = a_{n}Q_{n}+ Q_{n-1} \nonumber
\end{alignat}
On a snake graph, note that any given corner yields two edges in a row. The number of matchings are unchanged if we replace these two edges by a single point. (reference to propp?) In this way, counting the number of matchings of a snake graph can be reduced the matchings of a graph that is a 2-by-k rectangle of vertices for some k.
Embedding this with a corner of the graph at the origin (0,0) and (k,0), then all pairs of points of the form (a,0), (a,1) are connected by either 1 or 2 edges while all other pairs of points are connected by at most 1 edge. Take the number of edges connecting (a,0) and (a,1), a=1...k as the quotients $[a_1, ..., a_k]$. Then using the recurrence for the numerator of a continued fraction, one attains the number of matchings.
To see why this is true, note that a matchings up to a particular (a,0) and (a,1) either has (a,0) connected to (a,1) or (a,0) connected to (a-1,0). The number of matchings of the former form is the number of edges connecting (a,0) to (a,1) times the number of matchings of the graph up to (a-1,0) and (a-1,1). The number of matchings of the latter form is equal to the number of matchings of (a-2,0) and (a-2,1), which gives us the same recurrence as above.
\begin{figure}
\centering
\includegraphics[height=1.5in]{snaketoquotient}
\caption{A Markov snake graph of 29 matchings in correspondence with the quotients [1,1,2,2,1,1].}
\end{figure}
In general, the number of matchings of a snake graph will be $P_k$, the numerator of the last convergent generated by quotients $[a_1,...,a_k]$ with $a_i$= 1 or 2. Looking at the vector $$ from (0,0) to (a,b), on any interval [x,x+,1] it either passes through a single unit square or two unit squares vertically on top of one another. In the former case, this contributes a pair of quotients 1,1 to the ordered list of quotients. In the latter case, the two squares vertically on top of one another contribute the pair of quotients 2,2 to the ordered list of quotients. Therefore, a markov snake has the additional property that $a_2k$,$a_{2k+1}$ is either 1,1 or 2,2. \\
\begin{figure}[h]
\centering
\includegraphics[height=2in]{vectorsnake}
\caption{The vector $<7,4>$ passes through either 1 or 2 squares at each x coordinate. This corresponds to pairs of quotients.}
\end{figure}
\section{Some Properties of M(a,b)}
Let the Markov number corresponding to the point (a,b) in the plane be denoted M(a,b). We show true here several properties on their relative magnitudes.
\begin{lemma}
Let
$$L_1 =[a_1,...a_i,2,2,a_i+3,...,a_k]$$
and
$$L_2 =[a_1,...a_i,1,1,1,1,a_i+3,...,a_k]$$. Then the numerator of the last convergent generated by $L_1$ is less than the numerator of the last convergent generated by $L_2$.
\end{lemma}
\textbf{Proof.} This is a simple calculation. Let y be $P_{i-1}$ and x be $P_{i}$. then in the first case we get $P_{i+1} = 2x+y$ and $P_{i+2} = 5x + 2y$. In the second case we get that $P_{i+3}=3x+2y$ and $P_{i+4}=5x+3y$. As a result, the remaining numerators of the convergents generated by $L_1$ will be less than those generated by $L_2$. $\square$
\begin{lemma}
Let $$L_1 = [a_1, \ldots, a_i, 2, 2, 1, 1, \ldots,a_n]$$ and $$L_2= [a_1, \ldots, a_i, 1, 1, 2, 2, \ldots,a_n]$$
Then the numerator of the last convergent generated by $L_1$ is less than the numerator of the last convergent
generated by $L_2$
\end{lemma}
\textbf{Proof.} This is a similar calculation as the previous lemma. $\square$
\begin{prop}
Let $a**2c$ is 1. Then it is clear that $$M(c,b) = [q_1,q_2,...,q_{2c}] < [p_{1'},p_{2'},...,p_{2(c+a)'}] < [p_1,p_2,...,p_{2(c+a)}] = M(c+a,b)$$ $\square$ \\
\begin{figure}
\centering
\includegraphics[height=0.5in]{leftshift}
\caption{Applying lemma 2 shifts the "2,2" pairs of $[p_1 \cdots p_{2(c+a)}]$ to the left with $[p_{1'} \cdots p_{2(c+a)'}] < [p_1 \cdots p_{2(c+a)}]$. See Proofs of Propositions ?.2 and ?.3.}
\end{figure}
\begin{prop} Let $a**