\section{Introduction}
The {\it crosscap} number, or {\it nonorientable genus},  of a knot $K$ in the 3-sphere, denoted here as $\gamma(K)$,  was introduced by Clark in \cite{Clark_1978}. It is defined as the smallest  first Betti number of any embedded, compact, connected,  nonorientable surface in $S^3$ that spans $K$. For convenience, the crosscap number of the unknot is defined to be $0$. Clark observed that a knot has crosscap number equal to $1$ if and only if it bounds a M\"obius band and hence is a $(2, 2k+1)$-cable of some knot (the centerline of the M\"obius band). Thus the $(2, 2k+1)$-torus knot has crosscap number equal to $1$ for all $k$.

The crosscap number is not additive with respect to connected sum, however, Clark showed that for knots $K_1$ and $K_2$
\begin{equation}\label{connected sum bounds}
\gamma(K_1)+\gamma(K_2)-1 \le \gamma(K_1 \sharp K_2) \le \gamma(K_1)+\gamma(K_2).
\end{equation}
Clark also showed, that for any knot $K$
\begin{equation}\label{genus bound}
\gamma(K)\le 2 g(K)+1,
\end{equation}
where $g(K)$ is the genus of $K$. Clark asked if equality ever occurs in \eqref{genus bound}, and in \cite{Murakami_Yasuhara_1995}, Murakami and Yasuhara showed that this is the case for the  2-bridge knot $7_4$. This required them to compute $\gamma(7_4)=3$, a computation that has now been made {\sl much} easier by the work of Hatcher-Thurston \cite{HT:1985},  Bessho~\cite{Bessho_1994}, and Hirasawa-Teragaito~\cite{Hirasawa_Teragaito:2006}, who, taken together, provide a practical way to compute the crosscap number of any 2-bridge knot. In particular, one starts by using the work of Hatcher-Thurston to find all compressible, boundary incompressible surfaces that span the 2-bridge knot $K$. We now consider only those surfaces of minimum first Betti number, which we call $n$. Because of the relationship (which is  explained later in this paper) between 2-bridge knots, rational numbers, and continued fractions, it follows that $n$ is the length of the shortest continued fraction associated to $K$. If one of these surfaces is non-orientable, then the crosscap number of $K$ is $n$. If not, then it follows from \cite{Bessho_1994} that the crosscap number of $K$ is $n+1$. Starting with any continued fraction associated to $K$, Hirasawa and Teragaito determine a set of three ``moves'' that can be repeatedly applied to arrive at a shortest continued fraction for $K$, thus determining $n$. Morever, the shortest continued fraction also determines if the crosscap number is $n$ or $n+1$.

The crosscap number has also been computed for any alternating knot or link from a theoretical standpoint in \cite{Adams-Kindred}. Then, the specific case of alternating knots was addressed concretely and independently in \cite{Ito} and \cite{Kindred_2019}. In addition, crosscap number has been computed for any torus knot~\cite{Teragaito_2004} and any pretzel knot~\cite{Ichihara:2010}. For alternating links, $K$, lower and upper bounds for $\gamma(K)$ that depend on the Jones polynomial of $K$ are given in \cite{Kalfagianni_Lee:2016}. For alternating knots with 12 or fewer crossings, these bounds are often sufficient to determine $\gamma(K)$.

Building on the results of \cite{Hirasawa_Teragaito:2006}  together with \cite{Agol_2002}, \cite{ALSS_2020}, and \cite{ORS:2008}, we prove the following theorem.

\begin{theorem}\label{main theorem} If $K$ and $J$ are 2-bridge knots and $K>J$, then
$$\gamma(K)\ge 3 \gamma(J)-4.$$
\end{theorem}

Here, by $K\ge J$, we mean the partial order on prime knots defined by $K \ge J$ if there exists an epimorphism $f:\pi_1(S^3-K) \to \pi_1(S^3-J).$ It is clear that this relation is reflexive and transitive. Proving it is antisymmetric is nontrivial. Suppose that $f: \pi_1(S^3-K)\to  \pi_1(S^3-J)$ and $g: \pi_1(S^3-J)\to  \pi_1(S^3-K)$ are epimorphisms. Then, the composition $g \circ f$ is an isomorphism because knot groups are Hopfian (see \cite{Kawauchi}, Lemma~14.2.5). Hence $f$ is an isomorphism and $J=K$ because prime knots are determined by their knot groups \cite{Wh:1987}. It is worth noting that there are other partial orders defined on knots, see  \cite{Endo}, \cite{SW:2006}, \cite{Taniyama}. A closely related order for all knots (not just prime knots)  is given by Silver and Whitten in \cite{SW:2006}. They define $K \ge_p J$ if there is an epimorphism $f:\pi_1(S^3-K) \to \pi_1(S^3-J)$ that preserves peripheral structure. When $K \ge J$ and $K$ and $J$ are 2-bridge, then it follows from work of Agol, Ohtsuki-Riley-Sakuma, and Aimi-Lee-Sakai-Sakuma (summarized in Theorem~\ref{ORS theorem and converse}) that every epimorphism is induced by a branched fold map between the knot exteriors  and, hence, takes meridians to meridians and preserves peripheral structure. Therefore, the two partial orders agree on the set of 2-bridge knots. All of the epimorphisms determined in \cite{HKMS:2011} are meridional, that is,  taking meridians to meridians. In general, however, there are prime knots $J$ and $K$ with $J \ge K$ for which there is no meridional epimorphism \cite{CS:2016}.

A similar result to Theorem~\ref{main theorem} that relates the genera of the two knots has been proven by Suzuki and Tran, \cite{Suzuki_Tran:2018}. Namely, if $K$ and $J$ are 2-bridge knots and $K > J$, then $g(K)\ge 3 g(J)-1$, where $g(K)$ denotes the genus of the knot $K$.

Note that if the hypothesis of Theorem~\ref{main theorem} is relaxed to $K\ge J$, then the result is not true. Because $K\ge K$ for every knot $K$, if the theorem were true, it would imply that $\gamma(K)\ge 3 \gamma(K)-4$, or equivalently, that $2\ge \gamma(K)$ for every knot $K$, which is false. Following the proof of Theorem~\ref{main theorem} we classify all pairs $(K,J)$ for which the inequality is sharp.   There is some evidence that the result is still true even if the assumptions that $K$ and $J$ are 2-bridge knots is dropped. In~\cite{HKMS:2011} and~\cite{Kitano-Suzuki}, the authors determine the partial order denoted by $\ge$ on the set of prime knots with up to 11 crossings. In all cases where $K>J$, the conclusion of Theorem~\ref{main theorem} is true, even when $K$ and $J$ are not both 2-bridge knots.

\begin{question}[]
If $K$ and $J$ are prime but not necessarily 2-bridge knots and $K>J$, then is $\gamma(K)\ge 3 \gamma(J)-4$ still true? What if,
additionally, $K$ and $J$ are alternating?
\end{question}

In Section~\ref{continued fractions}, we summarize the results of \cite{Hirasawa_Teragaito:2006} that will be needed in this paper. Their analysis depends heavily on representing a 2-bridge knot $K$ by a shortest continued fraction. In Section~\ref{depth}, we recall the definition of the {\it depth} of a rational number defined by \cite{Hirasawa_Teragaito:2006} and use this to show how to derive the crosscap number directly from the unique even continued fraction representing $K$, thus eliminating the need to find a shortest continued fraction for $K$. Morover, as an alternative approach, we  give an algorithm for directly finding a shortest  continued fraction for $K$, thus bypassing the ``shortening moves'' introduced by Hirasawa-Teragaito. We then combine this with the work of \cite{Agol_2002}, \cite{ALSS_2020}, and \cite{ORS:2008} to prove Theorem~\ref{main theorem}.

\section{Continued Fractions, 2-Bridge Knots, and Crosscap \\Number}\label{continued fractions}

There is a well-established connection between 2-bridge knots, 4-plat diagrams, and continued fractions. We recall  the bare rudiments of this theory and refer the reader to \cite{Cromwell_2004}, \cite{HT:1985},  or \cite{Rolfsen_1990} for more information.
Every 2-bridge knot or link has a 4-plat diagram as in Figure~\ref{4plat}.  Here a box labeled $a_i$ denotes $(-1)^{i+1}a_i$ right-handed half-twists between the two strands entering and exiting the box. Note that a negative number of right-handed twists is equal to the opposite number of left-handed twists and vice-versa. In particular, if $a_i>0$ for all $i$,  or $a_i<0$ for all $i$, then the diagram in Figure~\ref{4plat} is alternating and minimal. That is, it represents a knot with crossing number equal to $|a_1 +a_2 +\dots +a_k|$. See \cite{Cromwell_2004}  for a more extensive description of this topic. The reader is also referred to the paper \cite{Kauffman_Lambropoulou:2003} by Kauffman and Lambropoulou. While not one of the first papers on the subject, their paper is noteworthy for its completeness,  approach, historical description of the topic,  and extensive bibliography.

\begin{figure}
   \centering
   \includegraphics[width=4in, angle=0]{Figures/4-plat.pdf}
   \caption{Standard 4-plat diagram of a 2-bridge knot.}
\label{4plat}
\end{figure}

The sequence $a_1, a_2, \dots, a_k$ gives rise to the reduced fraction $\frac{p}{q}$, via the continued fraction,
$$\frac{p}{q}=[a_1, a_2, \dots, a_k]=\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\ddots +\cfrac{1}{a_k}}}}.$$

This associates to each 4-plat diagram of a 2-bridge knot $K$,  a rational number $p/q$, with $0<p<q$, $q$ odd, and $\gcd(p,q)=1$. (In the case of a 2-bridge link, $p$ will be odd and $q$ even.) Clearly, we can work backwards from any such fraction to obtain a 2-bridge knot, which we denote $K_{p/q}$. Moreover, the fractions $p/q$ and $p'/q'$ represent ambient isotopic 2-bridge knots if and only if $q'=q$ and either  $p' \equiv p \text{ (mod $q$)}$ or $p'p\equiv 1 \text{ (mod $q$)}$. Because we will also consider a 2-bridge knot $K_{p/q}$ and its mirror image, $K_{-p/q}$,  as equivalent, the equivalence on fractions becomes $q'=q$ and either  $p' \equiv \pm p \text{ (mod $q$)}$ or $p'p\equiv \pm1 \text{ (mod $q$)}$.   Note that $\gamma(K_{p/q})=\gamma(K_{-p/q})$.

In Figure~\ref{plumbedBands}, we see that the knot depicted in Figure~\ref{4plat}, can be viewed  as the boundary of a surface obtained by plumbing together $k$ twisted bands, where the $i$-th  band has $a_i$ half twists.
Hence, each band is either an annulus, if $a_i$ is even, or a M\"obius band, if $a_i$ is odd, and the surface is orientable if and only if each $a_i$ is even. The surface strongly deformation retracts to the cores of the bands and hence  has first Betti number equal to $k$. If $a_i$ is even for all $i$, then the plumbed surface is orientable. However, in this case, Clark~\cite{Clark_1978} credits Mark Kidwell for the observation that introducing a single crossing to the knot diagram by means of a Reidemeister Type I move, corresponds to adding a M\"obius band to the Seifert surface, thus producing a nonorientable spanning surface for the same knot. This is illustrated in the last frame of Figure~\ref{plumbedBands}.

\begin{figure}
   \centering
   \includegraphics[width=4in, angle=0]{Figures/Surface.pdf}
   \caption{The knot $K_{4/15}$ and its nonorientable spanning surface.}
\label{plumbedBands}
\end{figure}

These surfaces are the natural starting point in trying to find a surface with minimal genus (in the orientable case) or minimal first Betti number (in the nonorientable case). As it happens, in both cases, we need look no further. Gabai proved that the minimal genus orientable surface for $K_{p/q}$ is the surface that arises from the continued fraction expansion for $p/q$ which contains all even and nonzero entries~\cite{Gabai_1985}. Similarly, Bessho~\cite{Bessho_1994} proved that the surface given by a shortest--length continued fraction expansion containing an odd integer, realizes the crosscap number. Moreover, if a shortest--length continued fraction produces an orientable surface, then adding a M\"obius band \`a la Kidwell, produces a surface realizing the crosscap number.

The connection between these surfaces associated to $K_{p/q}$ and the length of continued fraction expansions of $p/q$ motivates deeper understanding of continued fraction expansions. Given a fraction $p/q$, there are infinitely many ways to express it as a continued fraction. In an attempt to use only even integers (as mentioned in the result of Gabai), one can obtain  the following result (see Lemma~2.1 in \cite{GHS:2012}).
\begin{lemma} Suppose $0<p<q$, $\gcd(p,q)=1$, $p$ is even and $q$ is odd. Then there exists a unique continued fraction $p/q=[a_1, a_2, \dots, a_{2n}]$ where each $a_i$ is even and nonzero. We call this the {\bf even continued fraction} for $p/q$.
\end{lemma}
Finding this even continued fraction expansion for a given $p/q$ is a straightforward exercise that involves the Euclidean Algorithm (again, see  \cite{GHS:2012} for details).
By comparison, finding a {\em shortest--length} continued fraction expansion associated to $p/q$ is more difficult and such an expansion is not necessarily unique. Hirasawa and Teragaito  \cite{Hirasawa_Teragaito:2006} prove that a continued fraction expansion of $p/q$ can be shortened {\em if and only if} the expansion has one or more of the following three characteristics:
\begin{itemize}
\item Some $a_i$ in the continued fraction expansion is 0.
\item Some $a_i$ in the continued fraction expansion is $\pm 1$.
\item There exists a substring of $a_i$'s of the form $(2, -2)$ or $(2, -3, 2)$, or\\ $(-2, 3, -3, 2)$, and so on, where the entries in the substring alternate in sign, the substring begins and ends with elements of magnitude 2, and all other elements of the substring, of which there can be any number, including none, have magnitude 3. (We warn the reader  that this notation does not agree with that used by Hirasawa and Teragaito, who use a subtractive form of the continued fraction expression, rather than the additive form that we are using.)
\end{itemize}

Hirasawa and Teragaito define three shortening moves that can be applied to a continued fraction expansion in each of the three cases above. Of the three shortening moves, we will only need the exact description of the first move. The following Lemma is proven in  \cite{Hirasawa_Teragaito:2006}.

\begin{lemma}\label{collapsing zeroes} A zero can be removed from a continued fraction expansion as follows, $$p/q=r+[a_1, a_2, \dots, a_{i-1}, 0, a_{i+1}, a_{i+2}, \dots, a_n]=r+[a_1, a_2, \dots, a_{i-1}+ a_{i+1}, a_{i+2}, \dots, a_n],$$ for all $1<i<n$. (Here $r$ is any integer. We typically omit $r$ if $r=0$.)
\end{lemma}

The main results of \cite{Hirasawa_Teragaito:2006} give the following algorithm for computing $\gamma(K_{p/q})$, which rests on the above discussion.

\begin{algorithm}[Hirasawa--Teragaito]\label{HT algorithm}
To compute the crosscap number $\gamma(K)$ of the 2-bridge knot $K$:
\begin{enumerate}
\item Choose some fraction $p/q$ that represents $K$.
\item Choose some continued fraction expansion $p/q=r+[a_1, a_2, \dots, a_n]$ of length $n$ for $p/q$. This expansion can be shortened if and only if the expansion has one or more of the three characteristics mentioned above.
\item Through repeated application of the three shortening moves, transform the given continued fraction expansion into  a shortest length continued fraction expansion. (We continue here to denote a shortest continued fraction expansion as  $r+[a_1, a_2, \dots, a_n]$.)
\item Once a shortest length continued fraction expansion for $p/q$ has been found, if some $a_i$ is odd or equal to $\pm2$, then $\gamma(K_{p/q})=n$,  otherwise $\gamma(K_{p/q})=n+1$.
\end{enumerate}
\end{algorithm}
As an example, consider the knot $7_4$ which is the 2-bridge knot $K_{4/15}$. Note that $4/15=[4,-4]$. Because none of the entries are $0$, $\pm 1$,  or $\pm 2$, this continued fraction cannot be made shorter using the three shortening moves and hence is shortest. It follows that $\gamma(K_{4/15})=3$. A nonorientable spanning surface with minimal first Betti number is shown in Figure~\ref{plumbedBands}. We invite the reader to compare this with the much more difficult computation given in \cite{Murakami_Yasuhara_1995} which required proving that the crosscap number is not $2$ by first showing that the Goeritz matrix of any knot with crosscap number equal to $2$ has a certain form, and then showing that this form cannot be achieved by the knot $7_4$.

Computing the crosscap number as described in Algorithm~\ref{HT algorithm} has the slight drawback that  no direct instructions are given for finding a shortest--length continued fraction, although it is not hard to imagine an algorithmic scheme for the application of the three shortening moves.  In this paper, we discuss an alternative approach to computing the crosscap number using the unique even continued fraction expansion of $p/q$. This approach  avoids the need to find a shortest-length representative. As a result, we are able to give, later in the paper,  Algorithm~\ref{HSV algorithm} for computing crosscap number that we believe is more direct, simpler,  and faster than Algorithm~\ref{HT algorithm}. Moreover, Algorithm~\ref{HSV algorithm} also facilitates the comparison of the crosscap numbers of 2-bridge knots that are related by the partial order on all prime knots. While somewhat off the main course of this paper, and not needed for the proof of Theorem~\ref{main theorem},  we describe in Algorithm~\ref{grandparentpath} a very direct way to find a shortest continued fraction expansion of $p/q$. However, computer experimentation suggests that this approach is no faster than Algorithm~\ref{HSV algorithm}.

As already mentioned in the Introduction, we may define a partial order on the set of prime knots by declaring $K\ge J$ if there is an epimorphism $\phi:\pi_1(S^3-K) \to \pi_1 (S^3-J)$. Note that every knot is greater than or equal to both itself and the unknot.
In \cite{ORS:2008}, Ohtsuki, Riley and Sakuma systematically construct epimorphisms between 2-bridge knots.
In particular, they show that if $J$ corresponds to the fraction $p/q=[{\bf a}]$, and  $K$ corresponds to the fraction $p'/q'=[{\bf b}]$,  where the vector {\bf b} has the form
$${\bf b}=(\epsilon_1 {\bf a}, {\bf 2 c_1}, \epsilon_2 {\bf a}^{-1}, {\bf 2  c_2}, \epsilon_3 {\bf a}, {\bf 2  c_3}, \dots, \epsilon_n  {\bf a}^{(-1)^{n-1}}),$$
where each $\epsilon_i \in \{-1, 1\}$, each $c_i$ is an integer,  and if $c_i=0$ then $\epsilon_i=\epsilon_{i+1}$, then there is a {\sl branch fold map} from the complement of $K$ onto the complement of $J$. This map induces a meridional epimorphism from the group of $K$ to the group of the $J$. (Furthermore, the map preserves peripheral structure.) Here we use $({\bf a}, {\bf b})$ to represent the concatenation of the vectors {\bf a} and {\bf b}, denote the reverse of the vector $\bf a$ as ${\bf a}^{-1}$,  and  denote by ${\bf 2  c_i}$ the vector $(2 c_i)$ of length one. Ohtsuki, Riley and Sakuma's result motivates the following definition.

\begin{definition}\label{parsing} {\rm Let ${\bf a}, {\bf b}$ be vectors. We say that $\bf b$ {\bf admits a  parsing with respect to} $\bf a$ if
$${\bf b}=(\epsilon_1{\bf a}, {\bf2  c_1}, \epsilon_2 {\bf a}^{-1}, {\bf 2  c_2}, \epsilon_3 {\bf a}, {\bf 2  c_3}, \dots, \epsilon_n  {\bf a}^{(-1)^{n-1}}),$$
where each $\epsilon_i \in \{-1, 1\}$, each $c_i$ is an integer, and if $c_i=0$ then $\epsilon_i=\epsilon_{i+1}$.}

\end{definition}
It is easy to prove that if {\bf b} parses with respect to {\bf a}, then this parsing is unique.
If {\bf b} parses with respect to {\bf a}, then we call the vectors, ${\bf 2  c_i}$, {\bf a}-{\bf connectors}, or more simply, {\bf connectors}. The {\bf a}-connectors separate the  {\bf a}-{\bf tiles}: $\epsilon_1 {\bf a},  \epsilon_2 {\bf a}^{-1}, \dots,$ and $ \epsilon_n  {\bf a}^{(-1)^{n-1}}$. The next theorem forms the basis of our overall approach to the proof of Theorem~\ref{main theorem}.

\begin{theorem}\label{ORS theorem and converse}
Let $K$ and $K_r$ be 2-bridge knots where  $r = [\mathbf a]=[a_1, a_2, \dots , a_{m}]$ and $|a_i|>1$ for all $i$. Then $K \ge K_r$,  if and only if there exists $\tilde r=[{\bf b}]$ where $\bf b$ parses with respect to $\bf a$ using an odd number of tiles and $K=K_{\tilde r}$.
\end{theorem}

Theorem~\ref{ORS theorem and converse} follows directly from the work of Ohtsuki-Riley-Sakuma \cite{ORS:2008}, Agol \cite{Agol_2002}, and  Aimi-Lee-Sakai-Sakuma \cite{ALSS_2020}. In particluar, if $\tilde r = [\mathbf b]$ and $\mathbf b$ parses with respect to $\mathbf a$, then  Proposition~5.1 and Theorem~1.1 of \cite{ORS:2008} imply that $K_{\tilde r} \ge K_r$. Conversely, if $K=K_{\tilde r} \ge K_r$ where $r=p/q$, then by Proposition~8.1 of \cite{ALSS_2020} either
\begin{enumerate}
    \item[(1)] $\tilde r$ or $\tilde r+1$ belongs to the $\hat \Gamma _{p/q}$-orbit of  $p/q$ or $\infty$, or
    \item[(2)]$\tilde r$ or $\tilde r+1$ belongs to the $\hat \Gamma _{p'/q}$-orbit of  $p'/q$ or $\infty$, with $pp'\equiv 1 \text{ (mod $q$).}$
\end{enumerate}
Here $\hat\Gamma_r$ is the group of automorphisms of the Farey graph (defined in Section~\ref{depth}) generated by reflections in edges which have an endpoint equal to either $\infty$ or $r$ and, by Proposition~5.1 of \cite{ORS:2008}, the orbit of $r$ or $\infty$ is precisely those rationals $2c+[\mathbf b]$ where $\mathbf b$ parses with respect to $\mathbf a$. So case (1) gives the desired conclusion. For case (2), by considering equivalent orbits, it is not hard to show that we may assume that $|r'|<1$ which then implies that $p'/q=(-1)^{m-1}[\bf a^{-1}]$ or $p'/q=\pm 1+(-1)^{m-1}[\bf a^{-1}]$. If $p'/q=(-1)^{m-1}[\bf a^{-1}]$, then $\tilde r$ or $\tilde r+1$ corresponds to a vector that parses with respect to $\mathbf a^{-1}$. Finally, if $p'/q=\pm 1+(-1)^{m-1}[\bf a^{-1}]$, then it can be shown (by adjusting connectors appropriately) that there is an $\tilde s$ such that $K_{\tilde s}=K_{\tilde r}$ and $\tilde s$ corresponds to a vector that parses with respect to $\mathbf a^{-1}$.

\section{Depth}\label{depth}

There is a beautiful correspondence between continued fraction expansions of $p/q$ and edge paths from $1/0$ to $p/q$ in the {\it Farey Graph}  shown in Figure~\ref{farey graph}, where the graph is embedded in the Poincar\'e Disk (together with the circle at infinity).  Two fractions, $a/b$ and $c/d$,  in $\mathbb Q \cup \{\frac{1}{0}\}$ are connected by an edge in the Farey Graph if and only if $ad-bc=\pm 1$. The {\bf mediant}, or {\bf child},  of the two fractions $a/b$ and $c/d$ is defined to be $\frac{a+c}{b+d}$ and, therefore, it is connected by an edge to each of its {\bf parents}, $a/b$ and $c/d$. The entire graph can be generated recursively by taking mediants, starting from $1/0$ and $0/1$. (To generate the negative rational numbers, we start with $(-1)/0$ and $0/1$.) Perhaps the best reference for this material is Hatcher's excellent introduction to number theory from a geometric point of view~\cite{Hatcher}.

\begin{figure}[ht]
   \centering
   \includegraphics[width=4in]{Figures/FareyGraph4.pdf}
   \caption{The Farey Graph  and the path given by $3/4=[2,-2,2]$.}
\label{farey graph}
\end{figure}

Given a continued fraction expansion
$p/q=r+[a_1,a_2, \dots, a_n]$ where $|a_i|>1$  for all $i$,
let $p_0/q_0=r$ and, for $i>0$, define $p_i/q_i=r+[a_1,a_2, \dots, a_i]$. This defines the {\bf edge path}
$$\frac{1}{0} \to \frac{p_0}{q_0} \to \frac{p_1}{q_1} \to \dots \to \frac{p_n}{q_n},$$
which always proceeds, repeatedly,  from parent to child, except for the edge $\frac{1}{0} \to \frac{0}{1}$ in the case when $r=0$.
At the vertex $p_{i-1}/q_{i-1}$, the path turns through $|a_i|$ triangles  on the left side of the path if $(-1)^i a_i<0$ and on the right side if $(-1)^i a_i>0$.  Because of this, the entries $a_i$ are sometimes called the {\bf turning numbers}.

For example, the path from $1/0$ to $3/4$ corresponding to the expansion $3/4=[2,-2,2]$ is highlighted in Figure~\ref{farey graph}.  Consecutive edges are always separated by 2 triangles on the left because the turning numbers alternate in sign. In general,  the turning switches from one side of the path to the other when $a_i$ and $a_{i+1}$ have the same sign, and stays on the same side of the path when $a_i$ and $a_{i+1}$ have opposite signs.

Closely related to the length of the shortest path from $1/0$ to the fraction $p/q$ is the depth of $p/q$, which is defined in \cite{Hirasawa_Teragaito:2006} as follows.

\begin{definition}\label{definition of depth} The {\bf depth} of $p/q\in \mathbb Q \cup \{\frac{1}{0}\}$, denoted as $d(p/q)$,  is zero if $p/q\in \mathbb Z \cup \{\frac{1}{0}\}$. Otherwise, the depth of $p/q$ is one more than the minimum of the depths of its two parents.\end{definition}

It follows directly from the definition that the  depth of a child minus the depth of its parent is always zero or one. The following fact regarding depth is proven in \cite{Hirasawa_Teragaito:2006}.

\begin{lemma}\label{HT depth results} Suppose $p/q=r+[a_1,a_2, \dots, a_n]$ defines the edge path
$$\frac{1}{0} \to \frac{p_0}{q_0} \to \frac{p_1}{q_1} \to \dots \to \frac{p_n}{q_n},$$
from $1/0$ to $p/q$. The path is
a shortest path from $1/0$ to $p/q$ if and only if $d(p_i/q_i)=i$ for all $i\ge 0$.
\end{lemma}

Given a vector ${\bf a}=(a_1, a_2, \dots, a_m)$, we define its depth as $d({\bf a})=d(p/q)$ where $p/q=[{\bf a}]=[a_1, a_2, \dots, a_m]$.
Once the depth of $p/q$ has been determined, we can compute $\gamma(K_{p/q})$ from the even continued fraction expansion of $p/q$ using the following proposition (which is a restatement of Hirasawa and Teragaito's work).

\begin{proposition}\label{depth or depth plus one}Let $p/q=[{\bf a}]=[a_1, a_2, \dots, a_{2n}]$ be the unique even continued fraction expansion of  $p/q$. Then
$$\gamma \left(K_{p/q} \right) =\left\{ \begin{array}{ll}  d(p/q), & \mbox{if $a_i=\pm 2$ for some $i$,}\\d(p/q)+1, & \mbox{otherwise}. \end{array} \right.$$
\end{proposition}
\begin{proof} If $|a_i| \ge 4$ for all $i$, then none of Hirasawa and Teragaito's three shortening moves apply and hence this continued fraction expansion is shortest and defines a shortest path from $1/0$ to $p/q$. Thus by Lemma~\ref{HT depth results}, it follows that $d(p/q)=2n$. It now follows from Algorithm~\ref{HT algorithm} that $\gamma(K_{p/q})=2n+1=d(p/q)+1$. Otherwise, some $a_i=\pm 2$. If the even continued fraction is shortest, then again,  we obtain $\gamma(K_{p/q})=d(p/q)$.  If the even continued fraction expansion is not shortest, then a shortest one must contain an odd entry because the even continued fraction expansion is unique. If the length of a shortest continued fraction is $m$, then by Algorithm~\ref{HT algorithm} we have that $\gamma(K_{p/q})=m$ and, by Lemma~\ref{HT depth results}, we have that $m=d(p/q)$. Hence $\gamma(K_{p/q})=d(p/q)$.
\end{proof}

The depth of a fraction $p/q$ can be determined from a 2-complex $\mathcal T$ associated to an edge path. Suppose
$$\label{path}\frac{1}{0}\to \frac{0}{1} \to \frac{p_1}{q_1} \to \dots \to \frac{p_n}{q_n}=\frac{p}{q}$$
is the edge path determined by the fraction  $p/q=[a_1, a_2, \dots, a_n]$. As already described, at each vertex the path turns through a number of triangles on either the right or left side of the path. Let $\mathcal T$ be the union of these triangles. We can then determine the depth of each vertex of $\cal T$ recursively from the definition.

For example, consider $10/23=[2, 4, -2, 2]$.  This defines the edge path
$$\frac{1}{0} \to \frac{0}{1} \to \frac{1}{2} \to \frac{4}{9} \to \frac{7}{16} \to \frac{10}{23}.$$
The path and its associated 2-complex are shown in  of Figure~\ref{pathwithdepthandauxdata}. Above or below the fraction at each vertex, we display the depth of the fraction. The depths  are computed recursively using Definition~\ref{definition of depth}. In particular, the depth of $10/23$ is 3.  Notice that the edge path defined by $[2,4,-2,2]$ is not shortest; the depth does not increase by $1$ along the last edge of the path. A shorter path is given by $[2,3,3]$, which starts the same, but then goes from $1/2$ to $3/7$ to $10/23$.

\begin{figure}[htbp]
\begin{center}
   \includegraphics[width=3.0in, angle=90]{Figures/auxData.pdf}
\caption{The path associated to $[2, 4, -2, 2]$ with auxiliary data and depths displayed.}
\label{pathwithdepthandauxdata}
\end{center}
\end{figure}

Given $p/q=0+[a_1, a_2, \dots, a_n]$, we will now show that one can compute the depth of  $p/q$ directly from the turning numbers rather than having to draw the 2-complex as in Figure~\ref{pathwithdepthandauxdata} and then compute the depth of every vertex in the 2-complex.
To do this, we introduce the {\bf auxiliary data}, $(d_i, e_i)$ at each turning number $a_i$, as follows. Consider the two edges that terminate at vertex $p_i/q_i$ and which originate at the two parents of this fraction. One of these edges is  in the edge path, but the other is not. Define $d_i$ to be the change in depth along the edge from $p_{i-1}/q_{i-1}$ to $p_i/q_i$ and $e_i$ to be the change in depth along the edge from the other parent. It follows that both $d_i$ and $e_i$ lie in $\{0,1\}$ because each records the change in depth along an edge that points from a parent to a child in the Farey Graph. Thus, the possible values for $(d_i, e_i)$ are, a priori,  limited to $\{(0,0),(0,1),(1,0),(1,1)\}$. However, because our edge paths begin with $1/0\to 0/1$ we will not encounter a triangle with all integral vertices and, therefore, auxiliary data $(0,0)$ will not occur in this context. In Figure~\ref{pathwithdepthandauxdata}, we  have written the pairs $(d_i, e_i)$ in the relevant triangle at each vertex along the path. (In our figures, we have written $11$ for $(1,1)$, etc.).

Clearly, the depth of $p/q$ is the sum $d_1+d_2+\dots+d_n$ because the depth along the path starts at zero and each $d_i$ records the change in depth along one edge in the path.
If $p/q=0+[a_1, a_2, \dots, a_n]$, then we will assume that each $a_i$ is even and nonzero. It is now easy to show that $(d_1, e_1)=(1,1)$ if $|a_1|=2$ and   $(d_1, e_1)=(1,0)$ if $|a_1|\ge 4$. Thus, we can determine the initial auxiliary data from $a_1$. The next result tells us how $(d_i, e_i)$, the sign of $a_ia_{i+1}$,  and $|a_{i+1}|$ determine $(d_{i+1}, e_{i+1})$. This will allow for a recursive calculation of all the auxiliary data, and hence the depth of $p/q$.

\begin{lemma}\label{aux data depth} Suppose that $p/q=0+[a_1, a_2, \dots, a_{2n}]$ where each $a_i$ is even and nonzero.  If $|a_1|=2$, then  $(d_1, e_1)=(1,1)$; otherwise $(d_1, e_1)=(1,0)$. Then $(d_{i+1}, e_{i+1})$ for $i \ge 1$ is determined recursively by the following table:

\vspace{10pt}
\centerline{\rm
\begin{tabular}{|c|c|c|c|}
\hline
&$|a_{i+1}|=2 \text{ \small \&}$&$|a_{i+1}|=2 \text{ \small \&}$&$|a_{i+1}|\ge 4$\\
$(d_i, e_i)$&$a_ia_{i+1}>0$&$a_ia_{i+1}<0$&\\
\hline
(0,1)&(1,0)&(0,1)&(1,0)\\
(1,0)&(1,1)&(1,1)&(1,0)\\
(1,1)&(1,1)&(0,1)&(1,0)\\
\hline
\end{tabular}
}
\end{lemma}

Before proving this lemma, let us consider an example to illustrate how the lemma works. Consider $92/125=[2, -2, 2, 4, -4, 2]$. According to Lemma~\ref{aux data depth}, $(d_1, e_1) = (1,1)$ because $a_1=2$. Since $a_1a_2=-4$, we look in the last row of the table and the column headed by $|a_{i+1}|=2 $ and $a_ia_{i+1}<0$, to find that $(d_2, e_2)=(0,1)$. Continuing in this way, we see that the  associated sequence of auxiliary data is
$(1,1), (0,1), (0,1), (1,0), (1,0), (1,1)$
from which we conclude that the depth of $92/125$ is $1+0+0+1+1+1=4$.

\begin{proof}
We derive the various outcomes in the table for the case where $(d_i,e_i)=(1,1)$ by using Figure~\ref{aux data for 11}. Here we have imagined the last triangle in the 2-complex before advancing one more edge in the path. The last triangle is assumed to have auxiliary data $(1,1)$ and so the depths of its vertices are labeled accordingly, in this case, $d$, $d-1$, and $d-1$. The turning due to the sign of $a_ia_{i+1}$ and the magnitude of $a_{i+1}$, then leads us to the next value of auxiliary data.  Note  that both this figure and its mirror image are needed in general. Similar arguments (and figures) handle the other two cases, where $(d_i,e_i)$ is either $(0,1)$ or $(1,0)$.
\end{proof}
\begin{figure}[ht]
  \centering
   \includegraphics[width=2.5in,trim=0 100 0 0, clip]{Figures/triangles.pdf}
   \caption{Determining $(d_{i+1},e_{i+1})$ from $(d_i,e_i)=(1,1)$.}
\label{aux data for 11}
\end{figure}

Considering auxiliary data provides a straightforward proof of the following result which will be used in the proof of Theorem~\ref{main theorem}.\\

\begin{lemma}\label{reversing result} Suppose $\bf a$ is a vector of all even, nonzero  entries. Then
$d({\bf a})=d(- {\bf a})$ and $d({\bf a})=d({\bf a}^{-1}). $
\end{lemma}
\begin{proof} First note that the auxiliary data associated to $-{\bf a}$ is exactly the same as that associated to ${\bf a}$. Thus both have the same depth.
Next, it is well-known that both ${\bf a}$ and ${\bf a}^{-1}$ correspond to the same 2-bridge knot $K$. This is because the 4-plat diagrams determined by ${\bf a}$ and ${\bf a}^{-1}$, respectively, are related by a $180$ degree rotation. Thus both ${\bf a}$ and ${\bf a}^{-1}$ determine knots with the same crosscap number. Because one has an entry of $\pm 2$ if and only if the other one does, Proposition~\ref{depth or depth plus one} implies they must have the same depth.
\end{proof}

Returning to our definition of the auxiliary data, we introduce two  definitions that are slight variations. Given a vector $\bf a$ all of whose entries are even and nonzero, we can get a different sequence of auxiliary data by still using the table in Lemma~\ref{aux data depth} but by starting with different initial data. Define $d({\bf a}, 01)$ to be the depth derived by starting with initial data $(0,1)$, computing all subsequent auxiliary data according to the table in Lemma~\ref{aux data depth}, and then summing the first entry of each data pair. Similarly, let $d({\bf a}, 10)$ be the analogous depth obtained by using $(1,0)$ as the initial data.

\begin{lemma}\label{false depths} Suppose $\bf a$ is a vector of all even, nonzero  entries. Then
\begin{itemize}
\item $d({\bf a}, 11)-d({\bf a}, 01)\in \{0,1\}$,
\item $d({\bf a}, 11)-d({\bf a}, 10)\in \{-1,0\}$, and
\item $d({\bf a}, 10)-d({\bf a}, 01)\in \{0,1,2\}.$
\end{itemize}
\end{lemma}

\begin{proof} First note that the third conclusion follows from the first two because
$$d({\bf a}, 10)-d({\bf a}, 01)=d({\bf a}, 10)-d({\bf a}, 11)+d({\bf a}, 11)-d({\bf a}, 01).$$
To prove the first two assertions, we induct on the length of $\bf a$. If ${\bf a}=(a_1)$, the result is trivial. Now assume that ${\bf a}$ has length bigger than 1 and that the result is true for any shorter vector. Let ${\bf a}=(a_1, a_2, \dots, a_n)$ and ${\bf a}'=(a_2, a_3, \dots, a_n)$. We consider three cases, each corresponding to one of the three (output) columns of Lemma~\ref{aux data depth}.

For the first case, if $|a_2|=2$ and $a_1 a_2>0$, then by considering the three possible initial values for the auxiliary data $(d_1,e_1)$ we obtain that \\
$d({\bf a}, 11) =1+d({\bf a}', 11)$, $d({\bf a}, 10)=1+d({\bf a}', 11)$, and
$d({\bf a}, 01)=0+d({\bf a}', 10)$. Forming the appropriate differences and using the inductive hypothesis immediately gives the result. The proofs of the remaining two cases are similar.
\end{proof}

Returning to Algorithm~\ref{HT algorithm}, we now offer, in passing, a more direct method of finding a shortest continued fraction expansion for any fraction $p/q$. Given $p/q$, first note that it is straightforward to find its two parents in the Farey graph. To do this, first use the Euclidean Algorithm to express the greatest common divisor of $p$ and $q$ as $\pm 1=a q-b p$. Next, let $c=p-a$ and $d=q-b$. Thus the mediant of $a/b$ and $c/d$ is equal to $p/q$. Moreover, $ad-bc=a(q-b)-b(p-a)=aq-bp=\pm 1$. Thus, the fractions $a/b$ and $c/d$ are connected by an edge in the Farey graph. The idea now, starting with $p/q$, is to repeatedly move to the parent with smallest denominator.
This provides a simple algortihm to find a shortest path from $1/0$ to $p/q$.

\begin{algorithm}[]
\label{grandparentpath}
To find a shortest path in the Farey graph from $p/q$ to $1/0$:
\begin{enumerate}
\item If $\frac{p}{q}=\frac{n}{1}$, then a shortest path is $\frac{n}{1}\rightarrow \frac{1}{0}$.

    \item If $\frac{p}{q}= \frac{2k+1}{2}$, then a shortest path is $\frac{p}{q} \rightarrow \frac{k}{1} \rightarrow \frac{1}{0}$.
    \item If $q > 2$, then choose the parent with smallest denominator as the next vertex and repeat until we reach a denominator of $1$ or $2$. Then finish as in (1) or (2), respectively.
\end{enumerate}
\end{algorithm}

\noindent Lemma~\ref{HT depth results} (which is proven in \cite{Hirasawa_Teragaito:2006}) can be used to show that this generates a shortest path from $1/0$ to $p/q$. We leave the details to the reader.

The following lemma will be used in the proof of Theorem~\ref{main theorem}.

\begin{lemma}\label{isolation lemma} Suppose ${\bf a}$ and ${\bf b}$ are both vectors of all even, nonzero entries and that $c$ is an  integer with $|2c| \ge4$. If ${\bf A}=({\bf a}, 2c, {\bf b})$, then
$$d({\bf A}) = 1+  d({\bf a})+d({\bf b}).$$
\end{lemma}
\begin{proof} First note that the vector $\bf a$ contributes $d({\bf a})$ to the depth of $\bf A$. Let $(d_i,e_i)$ be the auxiliary data of $\bf A$ at $2c$. Because $|2c| \ge 4$, it follows from Lemma~\ref{aux data depth}, that $(d_i ,e_i) =(1,0)$.  Thus, the entry $2c$ contributes $+1$ to the depth of $\bf A$. We also have  that
$$ (d_{i+1},e_{i+1})=\left \{\begin{array}{cc} (1,1)& \text{if $|b_{1}|=2$,}\\ (1,0) & \text{if $|b_{1}|\ge 4$.}\end{array}\right.
$$
Thus, the first element $b_1$ of $\bf b$ has the same auxiliary data as it would if only its depth were being computed. So $\bf b$ contributes $d({\bf b})$ to the depth of $\bf A$. Therefore,
$d({\bf A}) = 1+  d({\bf a})+d({\bf b})$.
\end{proof}

The last result needed for Theorem~\ref{main theorem} is the following.

\begin{lemma} \label{depth of adding one more tile}Suppose ${\bf a}$ and ${\bf b}$ are both vectors of all even, nonzero entries and that $c$ is any integer. Let ${\bf A}=({\bf a},  2c, {\bf b})$, where we further assume that if $c=0$, then the last entry of ${\bf a}$ is equal to the first entry of ${\bf b}$. Then
$$d({\bf A})\ge d({\bf a})+d({\bf b})-1.$$
\end{lemma}
\begin{proof} We break the proof into multiple cases.

\noindent{\bf Case I:} $c=0$. \\
Let ${\bf A}'$ be obtained from ${\bf A}$ by removing $2c$ as in Lemma~\ref{collapsing zeroes}. If
${\bf a}=(a_1,a_2,\dots, a_m)$ and ${\bf b}=(a_m, b_2, \dots, b_n)$, then ${\bf A}'=(a_1,a_2, \dots, a_{m-1}, 2a_m, b_2,\dots, b_n)$. We also have $d({\bf A})=d({\bf A}')$ since these vectors determine the same fraction. Now $|2a_m|\ge 4$ because $|a_m|\ge 2$.  Therefore,  by Lemma \ref{isolation lemma}, we have
$$d({\bf A}) = d({\bf A}') = 1 + d((a_1,a_2,\dots, a_{m-1})) + d((b_2,\dots, b_{n-1}, b_n)).$$
Removing the last entry from $\bf a$ reduces its depth by at most $1$, and Lemma~\ref{reversing result} implies that removing the first entry from $\bf b$ also reduces its depth by at most 1. Therefore
$d({\bf A}) \ge d({\bf a})+d({\bf b})-1.$\\

\noindent{\bf Case II:} $|2c|\ge 4$. \\
Lemma~\ref{isolation lemma} implies that $d({\bf A}) = 1+d({\bf a})+d({\bf b}) \ge d({\bf a})+d({\bf b})-1$.\\

\noindent{\bf Case III:} $2c=\pm 2$. \\
The sequence of auxiliary data for $\bf A$ begins with the sequence of auxiliary data for $\bf a$ then has the auxiliary data for the entry $2c$, which we denote $(d',e')$, and then has auxiliary data some $(i,j) \in \{(0,1), (1,0), (1,1)\}$ for the first entry $b_1$ of $\bf b$. If we were to compute $d({\bf b})$ then the initial auxiliary data for $b_1$ should be $(1,1)$ if $|b_1|=2$ or $(1,0)$ if $|b_1|\ge 4$. First consider the case where $|b_1|=2$, Now,
\begin{align*}
d({\bf A})&=d({\bf a})+d'+d({\bf b}, ij)\\
&=d({\bf a})+d'+d({\bf b})+d({\bf b}, ij)-d({\bf b}, 11).
\end{align*}
If $ij=10$, then by Lemma~\ref{false depths}, the difference of the last two terms is either $-1$ or $0$, and because $d'$ is equal to either $0$ or $1$, we obtain the desired result. Similar arguments apply if  $ij \neq 10$  or $|b_1|
\ge 4$.
\end{proof}

Lemmas~\ref{aux data depth}--\ref{depth of adding one more tile} allow us to compare the depth of a vector $\bf a$ to the depth of a vector $\bf b$ that parses with respect to $\bf a$.  For example, consider ${\bf a} = [2,2,-2,2]$ which has auxiliary data $(1,1), (1,1), (0,1), (0,1)$.  Note that $d({\bf a}) = d({\bf a}^{-1})=2$ but that the auxiliary data for ${\bf a}^{-1}$ is $(1,1), (0,1), (0,1), (1,0)$. Different types of connectors in a vector that parses with respect to $\bf a$ change the auxiliary data and depth in ways reflected by the lemmas. For example, ${\bf b} = ({\bf a}, -2, {\bf a}^{-1})$ has auxiliary data $(1,1),(1,1),(0,1),(0,1),(0,1),(0,1),(0,1),(0,1),(1,0)$. This data starts with the auxiliary data for $\bf a$ but ends with data for ${\bf a}^{-1}$ that assumes initial data of $(0,1)$ (thus contributing $d({\bf a}^{-1},01)$ to the computation of depth). Since $d({\bf b})= 3 = d({\bf a}) + d({\bf a}^{-1}) -1$, this example illustrates that the inequality in Lemma~\ref{depth of adding one more tile} is sharp.

We are now prepared to prove Theorem~\ref{main theorem}.

\setcounter{theorem}{0}
\begin{theorem}
Suppose $K$ and $J$ are 2-bridge knots with $K>J$. Then $$\gamma(K)\ge 3 \gamma(J) -4.$$
\end{theorem}

\begin{proof} We may assume that $J$ corresponds to the fraction $p/q$ with $0<p<q$, $\gcd(p,q)=1$, $p$ is even, and $q$ is odd. Let $p/q=[{\bf a}]=[a_1, a_2, \dots, a_{2n}]$ be the unique even continued fraction expansion of $p/q$. Because $K>J$, it follows from Theorem~\ref{ORS theorem and converse} that $K$ corresponds to a fraction $p'/q'$ with continued fraction expansion given by
$$p'/q'=[{\bf b}]=[\epsilon_1{\bf a}, 2c_1, \epsilon_2{\bf a}^{-1}, 2c_2, \dots, 2c_{2k}, \epsilon_{2k+1}{\bf a}],$$
where each  $\epsilon_i \in \{-1,1\}$, each $c_i$ is an integer, and if $c_i=0$ then $\epsilon_i=\epsilon_{i+1}$. Moreover, $2k+1\ge 3$ because $K \neq J$.
If some connectors, $2c_i$, are equal to zero, then we will collapse them by Lemma~\ref{collapsing zeroes}, to arrive at a shorter vector ${\bf b}'$, which will then have all even and nonzero entries and hence will be the unique even continued fraction expansion for $p'/q'=[{\bf b}']$. As both vectors determine the same fraction, $d({\bf b})=d({\bf b}')$.

We first note that if $\bf a$ contains an entry equal to $\pm 2$, then so does ${\bf b}'$. Hence if $\gamma(J)=d({\bf a})$, then $\gamma(K)=d({\bf b}')$. To see this, assume that
$\bf a$ contains an entry that is $\pm 2$. If this entry is not the first or last entry of $\bf a$, then it appears somewhere in $\bf b$ and continues to appear in ${\bf b}'$ even after any zero-connectors are eliminated. If instead, the first or last entry of $\bf a$ is $\pm 2$, then so is either the first or last entry of $\bf b$, respectively,  and hence also, ${\bf b}'$. Thus ${\bf b}'$ contains an entry that is $\pm 2$.  The second part of the conclusion follows from Proposition~\ref{depth or depth plus one}.

We now consider two major cases.

\noindent{\bf Case I:} The vector $\bf a$ contains some entry equal to $\pm 2$.

By our previous observation, we have that $\gamma(J)=d({\bf a})$ and $\gamma(K)=d({\bf b})=d({\bf b}') $. We can build $\bf b$ in $2k$ steps by starting with $\bf a$ and then repeatedly appending $( 2c_i, \epsilon_{i+1}{\bf a}^{\pm 1})$. Applying Lemma~\ref{depth of adding one more tile} a total of $2k$ times, and using Lemma~\ref{reversing result}, we obtain $d({\bf b})\ge (2k+1)d({\bf a})-2k$. It then follows that
\vspace{-5pt}
\begin{align*}
\gamma(K) &\ge (2k+1) \gamma(J) - 2k\\
&= (2k+1)(\gamma(J)-1)+1 \\
&\ge 3 \gamma(J)-2
\end{align*}

\noindent since $2k+1 \ge 3$.

\noindent{\bf Case II:} No entry of the vector $\bf a$ is equal to $\pm 2$.

Because every entry of $\bf a$ has magnitude 4 or more, every entry has auxiliary data of $(1,0)$. Therefore,
$d({\bf a})=|{\bf a}|$, where $|{\bf a}|$ is the length of the vector $\bf a$, and moreover $\gamma(J)=d({\bf a})+1= |{\bf a}|+1$. We now break this case into two subcases.

\noindent{\bf Case IIa:} No entry of the vector $\bf a$ is equal to $\pm 2$ but some connector in $\bf b$ is equal to $\pm 2$.

Because some connector in $\bf b$ is $\pm 2$, after collapsing any zero-connectors, it is still the case that ${\bf b}'$ contains an entry equal to $\pm 2$. Thus  $\gamma(K)=d({\bf b}')$. We also have that every entry of  ${\bf b}'$, except possibly some connectors, has magnitude at least 4. Thus, all non-connector entries of ${\bf b}'$ have auxiliary data of $(1,0)$. Because any connector of magnitude 2 follows  an element of magnitude of 4 or more, it has auxiliary data of $(1,1)$. Therefore,  $d({\bf b}')=|{\bf b}'|$. If $z$ is the number of zero-connectors in $\bf b$, then we are assuming that $z\le 2k-1$ and hence that $-2z\ge -4k+2$. Since $2k+1 \ge 3$, we now have
\begin{align*}
\gamma(K)&=|{\bf b}'|\\
&=|{\bf b}|-2z\\
&=(2k+1)|{\bf a}|+2k-2z\\
&\ge(2k+1)|{\bf a}|-2k+2\\
&= (2k+1)(\gamma(J)-2)+3\\
 &\geq 3\gamma(J) - 3
\end{align*}

\noindent{\bf Case IIb:}  No entry of the vector $\bf a$ is equal to $\pm 2$ and no connector in $\bf b$ is equal to $\pm 2$.

In this case, the vector $\bf b$ does not contain an entry equal to $\pm 2$ and this remains true after collapsing any connectors which are equal to zero. Thus  $\gamma(J)=d({\bf a})+1$ and $\gamma(K)=d({\bf b}')+1$. Every entry of both $\bf a$ and ${\bf b}'$ have magnitude $4$ or more. Therefore, we have $d({\bf a})=|{\bf a}|$ and $d({\bf b}')=|{\bf b}'|$. Assuming that $\bf b$ has $z$ zero-connectors with $z\le 2k$, we have
\begin{align*}
\gamma(K)&=|{\bf b}'|+1\\
&=|{\bf b}|-2z+1\\
&=(2k+1)|{\bf a}|+2k-2z+1\\
&\ge(2k+1)|{\bf a}|-2k+1\\
&=(2k+1)(\gamma(J)-2)+2\\
&\ge 3 \gamma(J)-4
\end{align*}
\end{proof}

We point out that in the argument above, the inequality $\gamma(K)\ge 3 \gamma(J) -4$ is strict in both Case I and Case IIa. As a result, Case IIb is the only case where it is possible to achieve equality. Moreover, tracing through the argument in Case IIb, we obtain equality precisely when both $2k+1 = 3$ and every connector is zero. As a result, we have the following corollary.

\begin{corollary}
Suppose $K$ and $J$ are 2-bridge knots with $K>J$. If $\gamma(K)= 3 \gamma(J) -4,$ then $J$ corresponds to an even continued fraction $[{\bf a}] = [a_1, a_2, \ldots, a_{2n}]$ where each $|a_i|\geq 4$, and $K$ corresponds to the continued fraction $[{\bf a}, 0, {\bf a^{-1}}, 0, {\bf a}]$.
\end{corollary}

To illustrate the corollary, let $J_n$ be the 2-bridge knot corresponding to the fraction $\frac{2n}{4n^2+1}=[2n,2n]$ for $n>1$, and let $K_n$ be the 2-bridge knot corresponding to $\frac{32 n^3+6n}{64n^4+20n^2+1}=[2n,2n,0,2n,2n,0,2n,2n]=[2n,4n,4n,2n]$.  This gives infinitely many different pairs of knots, $(K_n, J_n)$, with $K_n>J_n$ by Theorem~\ref{ORS theorem and converse}.  Propositions~\ref{depth or depth plus one} and \ref{aux data depth} tell us that $\gamma(K_n)=5$ and $\gamma(J_n)=3$. Because $5=3\cdot 3-4$,  we see that the inequality of Theorem~\ref{main theorem} is sharp.

Finally, we summarize our work in the following algorithm to compute the crosscap number of any 2-bridge knot $K$.

\begin{algorithm}[]\label{HSV algorithm}
To compute the crosscap number $\gamma(K_{p/q})$ of the 2-bridge knot $K_{p/q}$, where  $0<p<q$, $\gcd(p,q)=1$,  $p$ is even and $q$ is odd.
\begin{enumerate}
\item Compute the unique even continued fraction expansion $p/q=[a_1, a_2, \dots, a_{2n}]$ where each $a_i$ is even and nonzero.
\item Compute the auxiliary data and $d(p/q)$ using  Lemma~\ref{aux data depth}.
\item If $a_i =\pm 2$ for some $i$, then $\gamma(K) = d(p/q)$; otherwise $\gamma(K) = d(p/q)+1$.
\end{enumerate}
\end{algorithm}

A Jupyter notebook containing a Python program that implements Algorithm~\ref{HSV algorithm} is included with the arXiv upload of this paper.

\begin{figure}
\begin{center}
\begin{tabular}{cc|rrrrrrrr|r}
\multicolumn{9}{c}{\hspace{1cm}Crosscap number, $\gamma(K)$}\\
& &1&2&3&4&5&6&7&8&Total\\
\hline
 &3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
 &4 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
 &5 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\
 &6 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 3 \\
 &7 & 1 & 2 & 4 & 0 & 0 & 0 & 0 & 0 & 7  \\
 &&&&&&&&&&\vspace{-2cm}  \\
 {\rotatebox[origin=c]{90}{Crossing number, cr(K)}}&  8 & 0 & 3 & 7 & 2 & 0 & 0 & 0 & 0 & 12 \\
 &&&&&&&&&&\vspace{-2cm}  \\
 &9 & 1 & 3 & 12 & 8 & 0 & 0 & 0 & 0 & 24 \\
 &10 & 0 & 4 & 17 & 21 & 3 & 0 & 0 & 0 & 45 \\
 &11 & 1 & 4 & 26 & 43 & 17 & 0 & 0 & 0 & 91 \\
 &12 & 0 & 5 & 33 & 78 & 53 & 7 & 0 & 0 & 176 \\
 &13 & 1 & 5 & 44 & 127 & 136 & 39 & 0 & 0 & 352 \\
 &14 & 0 & 6 & 53 & 194 & 278 & 150 & 12 & 0 & 693 \\
 &15 & 1 & 6 & 68 & 280 & 526 & 419 & 87 & 0 & 1387 \\
 &16 & 0 & 7 & 79 & 389 & 889 & 989 & 375 & 24 & 2752 \\
 \end{tabular}
\end{center}
\caption{Crosscap numbers by crossing number for 2-bridge knots with 16 or fewer crossings.}
\label{distribution}
\end{figure}

\setcounter{section}{3}
\section{Computations}

Using our implementation of Algorithm~\ref{HSV algorithm}, we computed the crosscap number of every 2-bridge knot with 16 or fewer crossings. Our computations agree with the data in \cite{knotinfo}, for knots up to 12 crossings (the limit of KnotInfo's table).  A table of crosscap numbers is given in \cite{Hirasawa_Teragaito:2006} for 2-bridge knots with 12 or fewer crossings. Our computations agree with their data as well. In Figure~\ref{distribution}, we give the distribution of crosscap numbers for all 2-bridge knots up to 16 crossings. It was proven in \cite{Murakami_Yasuhara_1995} that for any knot $K$
$$\gamma(K)\le \Bigl \lfloor \frac{cr(K)}{2} \Bigr \rfloor, $$
where $cr(K)$ is the crossing number of $K$ and $\lfloor x \rfloor$ is the floor of $x$, that is, the largest integer less than or equal to $x$. This inequality is confirmed by our computations and is borne out in Table~\ref{distribution}.

\bibliographystyle{plain}


\section{Introduction}
\footnotetext{\href{https://github.com/AKnightWing/ColdAsIce}{https://github.com/AKnightWing/ColdAsIce}}

$H_2O$ in its solid form, is found abundantly in nature. Therefore it is only natural that its structure has been of computational interest over the last century.
\\ \\In a water molecule, each oxygen atom shares a covalent bond with two hydrogen atoms and forms hydrogen bonds with two more hydrogen atoms. The protons are located between pairs of nearest neighbour oxygen atoms. The potential energy of such a proton has two possible minima as a function of distance on the line joining two oxygen atoms. In hexagonal ice, two oxygen atoms are 2.75{\AA} apart, and the most favourable position for each hydrogen atom is to be at 1{\AA} from each oxygen atom. Thus each proton has to choose between two positions 0.75{\AA} apart.
To build a coherent model of ice, we must make sure that the arrangement described above holds.

\section{Ice Rules}
To satisfy the conditions given in Section 1.; Bernar, Fowler and Pauling proposed the following rules for the arrangement of protons on bonds of the lattice:
\begin{enumerate}
	\item There is precisely one hydrogen atom on each hydrogen bond.
	\item There are precisely two hydrogen atoms near each oxygen atom.
\end{enumerate}
These two constraints are collectively known as the \textbf{ice rules}. In real ice, at finite temperatures, ice rules do not necessarily hold. For example, the first ice rule is violated if a hydrogen bond is populated by 0 or 2 protons. These defects are energetically highly unfavourable and only have a significant contribution to the overall structure at higher temperatures.
\\ The second ice rule is violated if one or three protons neighbour each oxygen. However, this defect is even more energetically unfavourable than the first and thus occurs rarely at lower temperatures.
\\Keeping in mind the relative frequency of occurence of these defects, we study a class of models called \textbf{ice models} which follow the ice rules exactly. At lower temperatures, the two ice rules serve as accurate constraints that provide a framework for calculating thermodynamic properties of ice.

\section{Residual Entropy}
In a micro-canonical ensemble, the entropy of the system is defined as $S = k_B \ln(\Omega)$ where $\Omega$ is the number of microstates of the system. Many systems studied in physics have a unique ground state - the state in which energy of the system is minimum.
\\Sometimes a system may have several degenerate ground states, such as the Ising model, in which case the system tends to have a non zero entropy at absolute zero since entropy goes as the logarithm of number of degenerate states.
\\Ice, is special, in the sense that it has many possible configurations dictated by the ice rules, and all these configurations have roughly the same energy. So, there are as many ground states as there are possible configurations of protons. This number increases exponentially with system size, which means that even in the thermodynamic limit, the system tends to have a non zero entropy at zero temperature, known as \textbf{Residual Entropy}.

\section{Monte Carlo Simulation}
Consider a dynamic physical system in the state $\mu$. If we consider some quantity $Q$ which takes the value $Q_{\mu}$ for the system in state $\mu$, then we define the expectation value of $Q$ at a given time $t$ as
\begin{equation}
\langle Q \rangle = \sum_{\mu} Q_{\mu} w_{\mu}(t)
\end{equation}
Now for the square ice model, the number of possible states of a system increases rapidly with lattice size and thus it's not computationally favourable to sample all possible states of a system. Monte Carlo techniques work by choosing a subset of states at random from some probability distribution $p_{\mu}$ which we specify. Suppose we choose to sample through $M$ such states, then our best estimate of a quantity we're trying to measure is:
\begin{equation}\label{sampling}
Q_M = \frac{\sum_{i = 1}^{M }Q_{\mu_{i}}p_{\mu_i}^{-1}e^{-\beta E_{\mu_i}}}{\sum_{j=1}^{M} p_{\mu_{j}}^{-1}e^{-\beta E_{\mu_j}}}
\end{equation}
where $\beta = 1/k_B T$
\subsection{Importance Sampling}
The question is, what probability distribution do we choose? We know that physical systems sample possible states with the Boltzmann probability distribution. With this in hindsight, we choose the probability that a particular state $\mu$ gets chosen for sampling as $p_{\mu} = Z^{-1}e^{-\beta E_{\mu}}$, where $Z$ is the partition function given by:
\begin{equation}
Z = \sum_{\mu}e^{-\beta E_{\mu}}
\end{equation}
Then, Eq.(\ref{sampling}) becomes:
\begin{equation}
Q_M =  \frac{1}{M} \sum_{i=1}^{M} Q_{\mu_i}
\end{equation}
\subsection{Markov Processes}
A Markov process is a mechanism  which, given a system in state $\mu$, generates a new state of that system $\nu$. The probability of generating the state $\nu$ from $\mu$ is called the \textbf{Transition Probability}: $P(\mu \rightarrow \nu)$. All transition probabilities in a Markov process must satisfy:\\
\\1. All P's are time independent.
\\2. They should depend only on the properties of the current states $\mu$ and $\nu$ and not on any other states the system has passed through.
This ensures that the probability of generating $\nu$ from $\mu$ is the same no matter where the system has come from. \\ \\
A constraint on the transition probabilities is  $\sum_{\nu}P(\mu \rightarrow \nu) = 1$
\subsection{Ergodicity}
The condition of ergodicity is the requirement that it should be possible for our markov process to reach any state of the system from any other state, if we run the process long enough.\\
Note: The Markov process is choosen specifically so that when we run it for long enough, starting from any state of a system, we will get a succession of states which appear with probabilities given by the Boltzmann distribution.
\subsection{Detailed Balance}
This is a condition we impose on our Markov process to ensure that at equilibrium, the system follows the Boltzmann probability distribution. At equilibrium, the rate at which a system makes transitions in and out of any state must be equal. Thus\\ $\sum_{\nu} p_{\nu}P(\mu \rightarrow \nu) = \sum_{\nu}p_{\nu}P(\nu\rightarrow\mu)$. We also know that $\sum_{\nu}P(\mu \rightarrow \nu) = 1$. Hence
\begin{equation}
p_{\mu} = \sum_{\nu}p_{\nu} P(\nu \rightarrow \mu)
\end{equation}
For any set of transition probabilities that satisfy Eq.(9), $p_{\mu}$ will be the probability distribution in equilibrium for the Markov process. We state without proof the desired condition for detailed balance in our case\cite{Barkema_1998}:
\begin{equation}
\frac{P(\mu \rightarrow \nu)}{P(\nu \rightarrow \mu)} = \frac{p_{\nu}}{p_{\mu}} = e^{-\beta(E_{\nu}-E_{\mu})}
\end{equation}
\subsection{Acceptance Ratios}
Write $P(\mu \rightarrow \nu) = g(\mu \rightarrow \nu)A(\mu \rightarrow \nu)$ where $g(\mu \rightarrow \nu)$ is the \textit{selection probability}. It is the probability that given an initial state $\mu$, our algorithm generates a new state $\nu$, and $A(\mu \rightarrow \nu)$ is the \textit{Acceptance Ratio}. It gives the probability of accepting a new state generated by our algorithm. Then, $A(\mu \rightarrow \nu) \in [0,1]$
\\Thus, Eq.(10) becomes
\begin{equation}
\frac{P(\mu \rightarrow \nu)}{P(\nu \rightarrow \mu)} = \frac{A(\mu \rightarrow \nu)}{A(\nu \rightarrow \mu)}\frac{g(\mu \rightarrow \nu)}{g(\nu \rightarrow \mu)}
\end{equation}

\section{Data Representation}
This section describes the data representation techniques we have used hereon.
\newline To construct a physical model out of the ice rules, we will consider a lattice of oxygen atoms placed on a 2-D plane. In Square Ice, oxygen atoms are arranged on the vertices of a square lattice. Thus, each oxygen atom has a hydrogen bond on all four sides, which are represented by the lines of the grid. Protons, which reside on bonds, are represented by arrows.
\\The direction of the arrow is such that it points towards the end of the bond nearest to the proton. This arrangement thus clearly satisfies the condition requiring oxygen to have coordination number equal to four. From the second ice rule, we further get the condition that each oxygen atom must have exactly two arrows pointing towards it, and two arrows pointing away from it. We thus conclude that for a singular lattice point, there are 6 possible configurations as given in Fig.(\ref{fig:6vertices}).
\\Further, we make the assumption that the \textbf{boundaries are periodic}. This means that the cell satisfies perfect two-dimensional tiling. This point will be crucial in the symmetry analysis later on. \textit{Because of the above restrictions, it is sufficient to label each $(i, j)^{th}$ oxygen atom with the configuration of the bond above and right to it}. The details of the bond below and left of the current atom can be determined from the labels of the $(i+1, j)^{th}$ and $(i, j-1)^{th}$ atoms respectively. For these 2 labels, we have used the convention where +1 denotes that the direction of the arrow is pointing away from the atom while -1 denotes that it is pointing towards the atom. Thus, for a grid of n $\times$ n, we have an array of shape (n, n, 2) when using our convention to label it. An example is given in Fig.(\ref{fig:datarep}). \newline This framework is thus capable of uniquely describing any possible configuration for an ice model and also makes visualising the lattice possible through a Python program.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{vertices.png}
	\caption{Six Possible vertex configurations}
	\label{fig:6vertices}
\end{figure}

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.132]{datarep.png}
	\caption{An example of data representation with periodic boundaries}
	\label{fig:datarep}
\end{figure}

\section{Long loop algorithm}
We will now consider using a Monte Carlo method to simulate an ice model. The first step in designing a Monte Carlo algorithm is to choose a set of moves that take us from one configuration to another, while making sure that both configurations satisfy the ice rules. This is what the Long loop algorithm does. The algorithm is as follows:
\newline \newline \textbf{Initialisation}
\\ We start with a correct configuration of the model which satisfies the ice-rule constraint. \\
\newline \textbf{Main algorithm}
\begin{enumerate}

\item We choose a vertex at random from the lattice. Ice rules ensure that this vertex has two arrows going in and two arrows going out. This will be the starting point.

\item We choose at random one of the two outgoing arrows from this vertex and reverse it.

\item Now, the initial vertex has only one outgoing arrow instead of two and the new
vertex at the other other end of the reversed arrow has three. Clearly, the resulting configurations on both the vertices violate the second ice rule.

\item We then fix this new vertex by choosing one of the two outgoing arrows (ignoring
the one we just reversed) and reversing that. This fixes one vertex but creates a
new defect at the other end of the flipped arrow. We repeat this process to deal with
the next vertex.

\item  Thus, each time we repeat this process, it fixes one vertex but alters the other one.

\end{enumerate}
\textbf{Termination}
\newline The process ends when we traverse a loop and return to the starting vertex. The configuration obtained at the end of these moves is one which satisfies the both the ice rules. Thus we have generated a new configuration of the system.
\newline A working model of the Long loop algorithm is shown in Fig.(\ref{fig:long_loop_report})

The Long loop algorithm is ergodic and also satifies the condition for Detailed Balance\cite{Barkema_1998}.
\begin{figure*}[h]
	\centering
	\includegraphics[scale=0.28]{long_loop_report.png}
	\caption{An example of a closed Long loop routine, gif available on \href{https://github.com/AKnightWing/ColdAsIce}{Github}}
	\label{fig:long_loop_report}
\end{figure*}

\section{Symmetry Analysis}

Symmetry analysis is a crucial part of counting the number of states. If two seemingly different states have some symmetry transformation between them, then both those states correspond to the same unique state. In order to count the total number of unique states/configurations, we need to take a look at various symmetries generated by the long loop algorithm and eliminate any duplicates of a particular unique state that arise due to symmetry.

There are three types of symmetries – \textit{rotation}, \textit{translation} and \textit{reflection}. We first look at the rotation and reflection symmetries. These correspond to the order of the Dihedral symmetry group of order $8$ (the symmetries of a square): $90^{\circ}$, $180^{\circ}$ and $270^{\circ}$ rotations about an axis that passes through the plane (z-axis), two $180^{\circ}$ flips about the horizontal axes (x and y-axes), two flips about the diagonal axes, and the identity transformation.

The translational symmetries arise due to the periodic boundary conditions which we have imposed on the states. For example, if we translate a configuration by one step downwards, we would get a configuration that looks different but still corresponds to the same unique state, as shown in Fig.(\ref{fig:translation})

\begin{figure*}[h]
	\centering
	\includegraphics[scale=0.23]{translation.png}
	\caption{Translational symmetry of a configuration}
	\label{fig:translation}
\end{figure*}

Periodic boundary conditions on all 4 sides of the ice map the 2D lattice onto a torus. Therefore, translation along any direction simply corresponds to a rotation of the torus along its primary axis.

All these symmetric states obey the ice rules and would be considered valid. This is fine if we simply wish to look at valid states but for the process of counting, it is important that we identify only one state and discard all of its symmetries.

\section{Counting States}
An immediate consequence of knowing the number of unique states of square ice is the knowledge of entropy of the system.
\\To weed out symmetries and repetitions, we describe a notation that helps us identify every unique state.
We assign a string containing a sequence of $1's$ and $-1's$. This string can be generated by traversing through the array containing the state in a lexicographical order and appending the value to the string. For example, the identity for the state given in Fig.(\ref{fig:datarep}) is '$ 11-11111-1111-1111-1-11$'. This is guaranteed to generate a unique identity to every state except for symmetries. A dictionary is created that catalogues all these states. This will be used in the time stepping loop described below.
The counting states algorithm is as follows:
\newline\newline\textbf{Initialization}
\newline Start with a configuration made entirely of Type 1 vertices. Use the Long loop algorithm on this configuration once. The output obtained is labelled as the initial state.
\newline\newline\textbf{Main algorithm}
\begin{enumerate}
\item Run the Long loop algorithm starting with the state generated at the previous step.
\item Generate the unique identification tag for the newly generated state.
\item Check through the dictionary containing all the unique states generated thus far by the long loop routine. If the current generated state is not present in the dictionary, it means that we have generated a new state and we append this to the dictionary. If the newly generated state is already present in this dictionary, we don’t do anything.
\item The process repeats by using the previously generated state as the new starting point for running the long loop routine again.
\end{enumerate}
\textbf{Termination}
\newline The loop terminates when the approximate error reduces below a threshold.
\newline \textbf{Note} that approximate error is defined as
\begin{equation}
\textrm{Approximate Error} = \frac{\textrm{Good iterations}}{\textrm{Total iterations}}
\end{equation}
where a Good iteration is when a Long loop routine arrives at a new state while a Bad iteration is when it does not. Total iterations is the sum of good and bad iterations.
\newline \newline At the end of this loop, we will have with us a dictionary that contains the identities of all unique states except for symmetries.
To remove symmetries we go through every state in the dictionary and find all possible rotational, translational and reflection symmetries for it described in Section 7.
We have written functions that generate these symmetries for any given input state. If any of these states are present in the dictionary, we delete it. We continue this process until we reach the last element of the dictionary.
At the end of this, we have a dictionary containing all the unique configurations of a lattice for a given number of atoms (for a 2x2 lattice, see Fig.(\ref{fig:2x2}) containing all 4 unique states).
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.45]{2x2.png}
	\caption{Unique Configurations of a 2x2 lattice}
	\label{fig:2x2}
\end{figure}
\section{Results: Non-energetic Ice}
Entropy is calculated by counting the number of unique states (modulo symmetries) and is shown as a function of lattice dimension in Fig.(\ref{fig:entropy}).
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{Entropy.png}
	\caption{Entropy as a function of lattice dimension}
	\label{fig:entropy}
\end{figure}
Mean number of steps of a Long loop routine to arrive at a new state is also plotted as a function of lattice dimension in Fig.(\ref{fig:mean_steps}). \newline\textit{\textbf{Note}}: We find a best fit curve for Fig.(\ref{fig:mean_steps}) as
\begin{equation}
\textrm{mean steps} \propto L^{1.655}
\end{equation}
This matches Barkema et al's result for the same algorithm.\cite{Barkema_1998}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{mean_steps.png}
	\caption{Mean number of Long loop steps v/s lattice dimension}
	\label{fig:mean_steps}
\end{figure}
Total number of iterations required to converge to an approximate error of $3\%$ is also plotted as a function of lattice dimension in Fig.(\ref{fig:num_iters}).
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{num_iters.png}
	\caption{Number of Long loop iterations v/s Lattice dimension}
	\label{fig:num_iters}
\end{figure}

\section{Metropolis Algorithm}
The aim of our endeavour is to develop an algorithm to calculate thermodynamic quantities for ice at non-zero temperatures. For this, we need to simulate thermal fluctuations in a system. In reality, thermal fluctuations in a system are small compared to the entire energy of a system. To effectively sample a large number of states we consider setting the acceptance ratio:
\begin{equation}\label{boltzmann}
A(\mu \rightarrow \nu)=\left\{
\begin{array}{@{}ll@{}}
e^{-\beta(E_{\nu} - E_{\mu})}, & \text{if}\ \Delta E>0 \\
1, & \Delta E\leq 0
\end{array}\right.
\end{equation}
\\The basis of Metropolis algorithm is as follows:
\newline\newline \textit{Given an initial state which satisfies the ice rules, we use the Long loop algorithm to generate a new state which also satisfies ice rules.
\newline If this state has a lower energy than our previous state, we redefine this state as our initial state and run the process again.
\newline If this state has a higher energy than our previous state, we accept this state as our initial state with a Boltzmann probability given by Eq.(\ref{boltzmann}).}
\newline \textit{We see that the probability to accept a transition to a higher energy state decreases exponentially with lowering temperatures. }
\section{Equilibration}
Starting from an initial state, we need to run our simulation for a suitably long period of time until it has come to equilibrium at the temperature we are intersested in - this period is called \textbf{Equilibration time}. All thermodynamic calculations hereon are done after ensuring that the system has equilibrated.
\newline A mark of equilibration is that the order parameter of the system saturates to a fixed value. The order parameter of our system is \textbf{Polarization} or the average direction of arrows, defined as :
\begin{equation}\label{polarisation}
P = \frac{1}{\sqrt{2}N}\sum_{i}\hat{n}_i
\end{equation}
where $\hat{n}_i$ is a unit vector in the direction of the $i^{th}$ arrow.

\section{Energetic Ice }
An interesting extension of the ice models developed so far is to assign energies to different configurations. We mentioned in Section 3 that at absolute zero, all possible configurations have roughly the same energy. However, this energy changes as a function of temperature. The aim of this section will be to study the behaviour of energetic ice at non zero temperatures. To do this, we first need a convention to decide the energy of a given configuration.
\\We start with a model introduced by Franz Rys \cite{Rys_1963} called the \textbf{F model}. In this model, the symmetric vertices, given by Type 5 and Type 6 in Figure \ref{fig:6vertices}, are favoured by giving them a lower energy $-\epsilon$ while the rest of the vertices are given zero energy.

The Hamiltonian for the \textbf{F model} is then given by:
\begin{equation}\label{energy}
H = -\epsilon \sum_{i}\left[\delta_{v_i,5}+\delta_{v_i,6}\right]
\end{equation}
where $v_i$ is the type of vertex at site $i$, labelled according to our data representations scheme.
\section{Fluctuations and Conjuagte Variables}
In classical thermodynamics; paramaters, constraints and fields interacting with the system each have conjugate variables which represent the response of the system to perturbations in the corresponding parameter. For example, the response of gas to a change in confining volume $V$ is a change in pressure $P$. Similarly, the magnetization $M$ of a magnet changes in response to the applied magnetic field $B$. Then $(P,V)$, $(M,B)$ are sets of conjugate variables. Classical thermodynamics also tells us that these conjugate variables are related to each other through derivatives of the Free energy $F$
\begin{equation}\label{conjugate}
\begin{split}
& P = -\frac{\partial F}{\partial V} \\ &
M = \frac{\partial F}{\partial B}
\end{split}
\end{equation}
Note that $F = -k_B T \ln(Z)$.

We may extend the above argument for any given thermodynamic variable $X$, to generate an equation like Eq.(\ref{conjugate}) which links $X$ to its conjugate field $Y$. Derivatives of this general form are produced by a term in the Hamiltonian of the form $-XY$, where $Y$ is a "field" whose value we fix and $X$ is the conjugate variable to which it couples.
\newline For example, the Hamiltonian of a magnet (consider the Ising model) has a term of the form $-MB$.
\newline The expectation value of $X$ can be written as:
\begin{equation}
\begin{split}
\langle X \rangle = & \frac{1}{Z} \sum_{\mu}X_{\mu}e^{-\beta E_{\mu}} \\ &
 = \frac{1}{\beta Z} \frac{\partial}{\partial Y}\sum_{\mu}e^{-\beta E_{\mu}}
\end{split}
\end{equation}
since $E_{\mu}$ contains a term of the form $-X_{\mu}Y$ which the $Y$ derivative acts on.
\begin{equation}
\begin{split}
\langle X \rangle &= \frac{1}{\beta}\frac{\partial \ln Z}{\partial Y} \\ &
= - \frac{\partial F}{\partial Y}
\end{split}
\end{equation}
\newline Now even if no field exists which couples to our variable $X$, we can simply make up a fictitious field $Y$ and add it to our Hamiltonian, perform the derivative to calculate the expectation of $X$, and then remove the term from the Hamiltonian again.
\newline A second derivative of the partion function with respect to $Y$ produces:
\begin{equation}
\begin{split}
-\frac{1}{\beta}\frac{\partial^2 F }{\partial Y^2} &= \frac{1}{\beta}\frac{\partial\langle X \rangle }{\partial Y} \\ &
= \langle X^2 \rangle - \langle X \rangle^2
\end{split}
\end{equation}
which we recognize as the mean square fluctuation in the variable $X$.
\newline The derivative $\partial \langle X \rangle/ \partial Y$, which measures the strength of the response of $X$ to changes in $Y$ is called the \textbf{susceptibility} of $X$ to $Y$.
\newline\newline The quantity of interest in our case is \textit{Polarization} $P$. The field that couples to it is an Electric Field $E$. Thus, we can define \textbf{Polarization Susceptibility} as:
\begin{equation}
\begin{split}
C_{P} & = \frac{\partial \langle P \rangle}{\partial E} \\ &
= k_B \beta L^2 (\langle P^2 \rangle - \langle P \rangle^2)
\end{split}
\end{equation}
\subsection{Phase Transitions}
A phase of a system under consideration is characterised by the uniformity of certain physical properties throughout it. Two phases can be differentiated by looking at an \textbf{Order Parameter}, a quantity which takes two different values in different phases. In this case, the order parameter is \textbf{Polarization}, defined in Eq.(\ref{polarisation}).
\\ Thermodynamic quantities show extreme behaviours at the critical point. For example, energy shows a discontinuous change at transition temperature, while generalised susceptibilities blow up.\cite{Callen}
\newline These behaviours cannot be reproduced accurately in numerical simulations. Instead, what we expect to see is a sharp change in energy near the critical point with a saturating behaviour on either side.
\newline Similarly, generalised susceptibilities encounter their maxima (finite) at the critical point.

\section{Results: Energetic Ice}
We focus on three thermodynamic quantities: Energy, Specific Heat and Polarisation; each of which is calculated per unit number of atoms.\\
\textbf{We set $\mathbf{k_B = 1}$ to simplify calculations}.
Also, the value of $\epsilon$ is set to be 0.15. The metropolis algorithm has been iterated $10000$ times before calculating any thermodynamic quantity.

\subsection{Ensuring Equilibration}
We find that 10,000 iterations are not enough to guarantee equilibration, especially at temperatures close to 0. This is because the Metropolis acceptance ratio for positive energy becomes exceedingly small at lower temperatures. This implies that for a large majority of Monte Carlo moves, the system only accepts flips to a lower energy state. Thus, the system tends to get stuck in a small region of the available phase space.
\newline An ideal scenario would be to run the metropolis algorithm for even longer; from our tests, we find that 750,000 iterations aree enough to guarantee equilibration. However, this requires a lot of computation power.
\newline While 10,000 iterations aren’t always enough for equilibration, we theorize that there is a lower probability of the system requiring $>$10,000 iterations. From hereon, all the reported results have been obtained after taking a population mean over 15 identically generated samples for each temperature. This has helped in removing some of the pseudo-noise (due to the lower iteration size), and has helped us in characterizing the trends of the curve better.
\newline \newline Now, Specific Heat of a system is related to fluctuations in energy as:
\begin{equation}
C = \frac{k_B \beta^2}{N}\left[\langle E^2\rangle - \langle E \rangle^2 \right]
\end{equation}
\newline Energy is calculated by averaging over 100 equilibrated states at each temperature. A Plot of energy as a function of temperature is shown in Fig.(\ref{fig:energy})
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{energy_combined.png}
	\caption{Energy v/s Temperature for different lattice sizes}
	\label{fig:energy}
\end{figure}
We observe a sharp change in energy in between two saturated values for all lattice sizes.
\subsection{L = 10}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{SpHeat10.png}
	\caption{Specific Heat v/s Temperature for a $L=10$ Lattice}
	\label{fig:10SP}
\end{figure}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{Pol10.png}
	\caption{Polarization v/s Temperature for a $L=10$ Lattice}
	\label{fig:10P}
\end{figure}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{PolSus10.png}
	\caption{Polarization Susceptibility v/s Temperature for a $L=10$ Lattice}
	\label{fig:10PS}
\end{figure}
We also see that that Specific Heat for a $L = 10$ lattice attains its maxima in Fig.(\ref{fig:10SP}), which is also the temperature range in which energy goes through a change between two saturated values.
\newline Polarization is plotted as a function of temperature with error bars in Fig.(\ref{fig:10P})
\newline Polarization Susceptibility also peaks and then diminishes for higher temperatures in Fig.(\ref{fig:10PS}). This peak occurs in the temperature range in which Polarization undergoes a sharp change in Fig.(\ref{fig:10P}).
\newline \textbf{This is evidence for a Phase transition in the system}.
\subsection{L = 15}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{SpHeat15.png}
	\caption{Specific Heat v/s Temperature for a $L=15$ Lattice}
	\label{fig:15SP}
\end{figure}

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{Pol15.png}
	\caption{Polarisation v/s Temperature for a $L=15$ Lattice}
	\label{fig:15P}
\end{figure}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{PolSus15.png}
	\caption{Polarisation Susceptibility v/s Temperature for a $L=15$ Lattice}
	\label{fig:15PS}
\end{figure}
For $L=15$, we observe behaviour similar to the $L=10$ case in Fig.(\ref{fig:15SP}), Fig.(\ref{fig:15P}) and Fig.(\ref{fig:15PS}).

\subsection{L = 20}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{SpHeat20.png}
	\caption{Specific Heat v/s Temperature for a $L=20$ Lattice}
	\label{fig:20SP}
\end{figure}

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{Pol20.png}
	\caption{Polarisation v/s Temperature for a $L=20$ Lattice}
	\label{fig:20P}
\end{figure}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.55]{PolSus20.png}
	\caption{Polarisation Susceptibility v/s Temperature for a $L=20$ Lattice}
	\label{fig:20PS}
\end{figure}

The trend continues for higher lattice dimensions, with peaks in Polarization susceptibility and Specific Heat falling in the same temperature range as discontinuous changes in Polarization and Energy respectively.
\newline \textbf{The occurence of this behaviour for all 3 lattice sizes strongly hints at the presence of a phase transition in the system. This forms the central result of our text}.

\subsection{Equilibrium Configurations}
The \textbf{F model} favours Type 5 and Type 6 vertices by giving them a lower energy than the rest. These 2 vertices can cover the 2-D plane by themselves. As the ground state of the system is the state of least energy at any temperature, the least energy configuration obtained at absolute zero exclusively consists of Type 5 and Type 6 vertices arranged in a checkerboard pattern.
\newline The accuracy of the Metropolis algorithm can be seen from the acceptance ratios defined in Eq.(\ref{boltzmann}). The probability of acceptance of a state at higher energy becomes 0 at absolute zero. Thus no iteration of the algorithm results in an increased energy of the configuration.
\newline Note that there are two possible ground states, depending on which vertex(5 or 6) falls on an even site and which falls on the odd. At higher temperatures, both of these vertices are equally likely to fall into even and odd sites.
\newline Thus, \textit{on lowering the temperature the system undergoes a phase transition into one of the states. (In which Type 5 occupies odd sites and Type 6 occupies even sites or vice versa)}.
\newline With increasing temperatures, the system moves to states of higher energies, and hence we expect to see a higher concentration of Type(1-4) vertices.

Fig.(\ref{fig:temp_snapshots}) shows snapshots of configurations at various temperatures ranging from $T=0.1$ to $T=10.0$. These have been obtained by running the Metropolis algorithm till equilibration is achieved. We clearly see a decreasing concentration of Type (5-6) vertices and a corresponding increase in concentration of Type(1-4) vertices.
\begin{figure*}[h]
	\centering
	\includegraphics[scale=0.33]{temp_snapshots.png}
	\caption{Equilibrated configurations at different temperatures, GIF available on \href{https://github.com/AKnightWing/ColdAsIce}{Github}}
	\label{fig:temp_snapshots}
\end{figure*}
\section{Scope for future work}
Our immediate aim is to calculate finite temperature entropy for energetic ice by integrating the specific heat data generated. We also plan to study a 3D model of energetic ice. By implementing our algorithms for a pyrochlore lattice, we also plan to reproduce the work done by Ramirez et al.\cite{spin_ice} on spin ice systems.
\section{Aknowledgements}
We thank Dr.~Sunil Pratap Singh for suggestions on energetic ice models. We are also grateful to Dr.~Auditya Sharma and Mr.~Vedula Bharadwaj for their insights on Phase Transitions.
We are thankful to \href{https://www.kaggle.com/}{Kaggle} for providing computational resources.

\bibliographystyle{unsrt}