\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 $<a,b>$ 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<b<c$. Then $M(c,b)<M(c,b+a).$
\end{prop}

\textbf{Proof.} M(c,b+a) will correspond to the matchings of a snake graph that consists of more unit than M(c,b) and it will be steeper. Using the construction outlined earlier, let the value of M(c,b+a) and M(c,b) be the numerator of the last convergent of $[p_1,p_2,...,p_{2c}]$ and $[q_1, q_2,...,q_{2c}]$ respectively.

\begin{figure}
\centering
\includegraphics[height=1.0in]{quotientsbox}
\end{figure}

 Now this quotients are identical up say the jth coordinate. As the snakes are symmetric, they are also identical past the (2c-j)th coordinate. Since M(c,b+a) generates a steeper snake, this means the two quotients immediately after the jth one are [...2,2...] for the snake of M(c,b+a), and [...1,1...] for the snake of M(c,b). By symmetry, the (2c-j-1)th and (2c-j-2)th quotients are also [...2,2...] and [...1,1...] for M(c,b+a) and M(c,b) respectively. \\

 The difference in steepness between the snake graphs of M(c,b+a) and M(c,b) also implies that between any two pairs of quotients [...2,2 ...  2,2 ...] in the quotients $[q_1,q_2,...,q_n]$, there is a pair of quotients 2,2 in $[p_1,p_2,...,p_n]$ either at the same position of one of the pairs of quotients or in between as suggested in the figure below.\\
                                                
Now apply lemma 2 on M(c,b) to M(c,b) in order to shift the 2's to the right so that they match up with those on M(c, b+a). This will make the new quotients of $[q_{1'},....,q_{n'}]$ match up with those of M(c,b+a) exactly except there will be quotients of $[q_{1'},....,q_{n'}]$ which are 1,1 where the quotients of M(c,b+a) are 2,2. It is easy to see now that $$M(c,b)=[q_1,...,q_n] < [q_{1'},....,q_{n'}] < [p_1,p_2,...,p_n] = M(c,b+a)$$ for $[q_{1'},....,q_{n'}]$ matches up exactly with $[p_1,p_2,...,p_n]$ except for it has less 2,2 pairs. $\square$

\begin{figure}[b]
\centering
\includegraphics[height=0.5in]{rightshift}
\caption{Applying lemma 2 shifts "2,2" entries to the right with the result $[q_1 \cdots q_n] < [q_{1'} \cdots q_{n'}]$}
\end{figure}

\newpage

\begin{prop}Let $a<b<c$. Then $M(c,b)<(c+a,b)$.
\end{prop}

Pf. M(c+a,b) will correspond to the matchings of a snake graph that consists of more units than M(c,b) and it will be less steep. As before, let M(c+a,b) and M(c,b) be the last numerators in $[p_1,p_2,...,p_{2(c+a)}]$ and $[q_1,q_2,...,q_{2c}]$ respectively.

As the snake of M(c+a,b) is of the same height as the snake of M(c,b), the quotients $[p_1,p_2,...,p_{2(c+a)}]$ will have the same number of 2,2 pairs as $[q_1,q_2,...,q_{2c}]$. Furthermore, as the snake generated by (c+a,b) is flatter than that generated by (c,b), we have for the kth 2,2 pair in  $[q_1,q_2,...,q_{2c}]$, the kth 2,2 pair of $[p_1,p_2,...,p_{2(c+a)}]$  is either at the same position or further to the right.

To prove the proposition, we apply lemma 2 to $[p_1,p_2,...,p_{2(c+a)}]$. We shift all the 2,2 pairs in $[p_1,p_2,...,p_{2(c+a)}]$ to the left so that we create $[p_{1'},p_{2'},...,p_{2(c+a)'}]$ with the property that its quotients match up with $[q_1,q_2,...,q_{2c}]$ to the $2c^{th}$ coordinate and $p_i$ for $i>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<b<c$, then $M(c,b)<M(c+a,b-a)$.
\end{prop}

Pf. M(c+a,b-a) will correspond to the matchings of a snake graph that consists of more "units" than M(c,b) and it will be less steep. Transforming the snake graphs of M(c+a,b-a) and M(c,b) into 2-by-n ladders yields quotients $[p_1,p_2,...,p_{2(c+a)}]$ and $[q_1,q_2,...,q_{2c}]$.
In $[q_1,q_2,...,q_{2c}]$, there are (b-1) pairs of 2,2 terms and (c - (b-1)) pairs of 1,1 terms.
In $[p_1,p_2,...,p_{2(c+a)}]$, there are (b-a) pairs of 2,2 pairs and (c+2a - (b-1)) pairs of 1,1 terms. $[p_1,p_2,...,p_{2(c+a)}]$ and $[q_1,q_2,...,q_{2c}]$ will look like the figure accompanying the previous proposition.

Taking the quotients $[p_1,p_2,...,p_{2(c+a)}]$ , we can generate $[p_{1'},p_{2'},...,p_{2(c+a)'}]$ as in the proof of lemma 2, except that it matches up with $[q_1,q_2,...,q_{2c}]$ only up to the first ((b-1)-a) pairs of 2,2 terms whereas in $[q_1,q_2,...,q_{2c}]$, there are (b-1) such pairs. To rectify this, apply lemma 1 $a$ times starting from the leftmost mismatch to wherever there is a 1,1 term in $[p_{1'},p_{2'},...,p_{2(c+a)'}]$ mismatched with a 2,2 term in $[q_1,q_2,...,q_{2c}]$. The net effect of each application of lemma 1 is a loss of two 1,1 pairs and a gain of one 2,2 pair. Thus after $a$ applications of lemma one we get 

\begin{eqnarray}
M(c,b) &=& [q_1,q_2,...,q_{2c}] = [p^{'}_{1},p^{'}_{2}, ...,p^{'}_{2c}]< \nonumber \\ 
&<& [p_{1'},p_{2'},...,p_{2(c+a)'}] < [p_1,p_2,...,p_{2(c+a)}]=M(c+a,b-a) \nonumber
\end{eqnarray}
$\square$

\section{Applications to Markov Polynomials}

Let s(a,b) be the Markov polynomial corresponding to the point (a,b) and the Markov number M(a,b). (Note: s(a,b) itself is a Laurent polynomial in x,y, and z.)

The vector from the origin to (a,b) then has to pass through $a$ squares horizontally to get to (a,b)
and $b$ squares vertically. The total number of squares that the vector passes through is then (a+b-1). This corresponds to a snake graph of width w=2a, height w=2b, and vertices n=4(a+b-1) in the original combinatorial model.
The powers of x,y,and z in the denominator of s(a,b) are then

\begin{center}
$x^{\frac{h-2}{2}} = x^{b-1}$,$y^{\frac{w-2}{2}} = y^{a-1}$, and $z^{\frac{n}{4}} = z^{a+b-1}$
\end{center}

As there is a correspondence between the points whose coordinates are
relatively prime and the powers of x and y in the denominator s(a,b) , 
it follows that the denominators of s(a,b) and s(c,d) are distinct for (a,b) $\neq$ (c,d). Note that determination of the power of z is not required to determine the denominators are distinct, but is included for the sake of completing the calculation.

From the proof of the combinatorial model for the Markov polynomials using cuts, 
it was noted that a given snake graph has a matching that contains all the x-edges and a matching that 
contains all the y-edges. By Proposition [!?!?!], for a$<$b$<$c, we have that M(b,c) $<$ M(b+a, c-a).

Now suppose we have two Markov polynomials whose numerators are equal. Call them s(p,q) and s(r,s). 
For both of their corresponding snake graphs, there exists a matching containing all x-edges and a matching containing all y-edges. Therefore the snakes must be 
built of the same number of units as there is a matching containing every x-edge and every y-edge. Therefore p+q = r+s since the total number of blocks is the same as the number of units that make up a snake. This means we can rewrite say s(r,s) as s(p+a, q-a). 
But M(p,q) $<$ M(p+a,q-a) so that the sum of the coefficients of s(p,q) would be less than the sum of the coefficients 
of s(p+a, q-a) = s(r,s). This is not possible. Thus we have that the numerators and the denominators of
 the Markov polynomials are distinct.

\begin{prop}
The polynomials s(a,b) are distinct. $\square$
\end{prop}
\end{document}