\documentclass[letterpaper]{article}
\usepackage{amsmath}
\usepackage[dvips]{graphicx}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corrolary}
\newtheorem{prop}{Proposition}
\newtheorem{conj}{Conjecture}

\newcommand{\fxi}{\lfloor \xi \rfloor}

\title{Rational Shifts of Linearly Periodic Continued Fractions}
\author{Tudor Dimofte}
\begin{document}

\maketitle
\newpage
\tableofcontents
\newpage

\section[Continued Fractions]{General Theory of Continued Fractions}
%
Much of this report will be concerned with ``linearly periodic'' continued fractions. Hence it may be useful to start with a quick overview of continued fractions.

\subsection{Notation}
%
A continued fraction is something of the form
\begin{equation} a_0 + \frac{1}{\displaystyle a_1 + \frac{1}{\displaystyle a_2 + \frac{1}{\displaystyle a_3 + \frac{1}{\ddots}}}}, \label{longcf} \end{equation}
where the coefficients $a_0, a_1, a_2, a_3, \ldots$  are numbers of some type. The expression may either terminate or continue infinitely. We can also write \eqref{longcf} in the neater, more compact notation
\begin{equation} [a_0,a_1,a_2,a_3,\ldots]. \label{compactcf} \end{equation}
Most of the time we shall only be concerned with \emph{simple} continued fractions, those for which all the coefficients are (strictly) positive integers, except perhaps $a_0$, which may be any integer. So from now on, ``continued fraction'' will be assumed to mean ``simple continued fraction'' unless otherwise noted. (The most common--or perhaps the only--exception will be a finite continued fraction whose last coefficient is not an integer.)

A \textbf{periodic} continued fraction is one in which the coefficients begin to repeat after a certain point. Certainly any periodic continued fraction is infinite. The continued fraction would be written as, eg,
\begin{equation} [a_0,a_1,\overline{a_2,a_3,a_4}] = [a_0,a_1,a_2,a_3,a_4,a_2,a_3,a_4,a_2,\ldots]. \label{percf} \end{equation}
We shall also define a \textbf{linearly periodic} continued fraction\footnote{these are also clearly infinite} of period $j$ and intoductory sequence length $l$ to be of the form
\begin{eqnarray} \label{lpcf} [ \ldots,a_{l-1},\overline{f_1(n),f_{2}(n),\ldots,f_{j}(n)} ],\qquad n=1,2,3,\ldots \label{lpercf} \\ = [\ldots,a_{l-1},f_1(1),f_{2}(1),\ldots,f_{j}(1),f_1(2),f_{2}(2),\ldots,f_{j}(2),f_1(3),\ldots], \nonumber \end{eqnarray}
where the functions $f_1,f_2,\ldots,f_j$ are linear in the sense that $f_i(n)=b_i n + c_i \; (\forall i)$. Since the coefficients must all be integers, the constants $b_i$ and $c_i$ must be integers as well. To see this, first note that $b_i(1)+c_i=b_i+c_i=m$ (for some integer $m$). Then $b_i(2)+c_i=m+b_i$ must also be an integer $\Rightarrow b_i$ is an integer. And from $c_i=m-b_i$ we have that $c_i$ is an integer. In fact, we must also have $b_i \geq 0$ and $c_i> -b_i \; (\forall i)$ if the coefficients are to be strictly positive. Note that any periodic continued fraction is also a linearly periodic continued fraction with $b_i = 0\,\forall i$. Also note that we could imagine defining all sorts of ``quasi-periodic'' continued fractions with \eqref{lpercf} if we take the $f_i$ to be various different types of integer-valued functions.
%
\subsection{A few pertinent results}
We shall now \emph{sketch} proofs of the following preliminary results\footnote{Ideas for the proofs were taken from \cite{class}, Chapters 5-8, 11 and \cite{comput}, Section 2.}:
\begin{itemize}
\item Every finite continued fraction is a rational number and every rational number can be written as a finite continued fraction.
\item Every infinite continued fraction converges to an irrational number and every irrational number can be written as an infinite continued fraction.
\item If we assume that the last coefficient of any finite continued fraction is not 1, then the continued fraction expansion of any number is unique.
\item A continued fraction is periodic if and only if it converges to a root of a quadratic.
\end{itemize}

For any (finite or infinite) continued fraction, define the $\mathbf{n^{th}}$ \textbf{convergent} $x_n$ to be \begin{equation} x_n=[a_0,a_1,\ldots,a_n]=\frac{p_n}{q_n}, \quad (p_n,q_n)=1\end{equation} where $n\leq N$ if the continued fraction is finite, $[a_0,a_1,\ldots,a_N]$, and $p_n$ and $q_n$ are polynomials in the $a_i$. Note that we have $p_0=a_0, p_1=a_0 a_1+1, q_0=1, q_1=a_1$. If we further define $p_{-1}=1$ and $q_{-1}=0$ we have
%
\begin{lemma} \label{pandq} For any $n\geq 1$, $p_n=a_np_{n-1}+p_{n-2}$ and $q_n=a_nq_{n-1}+q_{n-2}$. In other words,
\begin{eqnarray}
\left( \begin{array}{cc} p_n & p_{n-1} \\ q_n & q_{n-1} \end{array} \right) &=& \left( \begin{array}{cc} p_{n-1} & p_{n-2} \\ q_{n-1} & q_{n-2} \end{array} \right) \left( \begin{array}{cc} a_n & 1 \\ 1 & 0 \end{array} \right) \nonumber \\
&=& \left( \begin{array}{cc} a_0 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} a_1 & 1 \\ 1 & 0 \end{array} \right) \cdots \left( \begin{array}{cc} a_n & 1 \\ 1 & 0 \end{array} \right) \label{mx1}
\end{eqnarray} \end{lemma}
%
% It would be nice to change n to k sometime!
%
\emph{Proof.} We have already considered the cases $n=1,2$. Assume that for a given $n$ in the continued fraction $[a_0,a_1,\ldots,a_N,\ldots]$ with $N>n$ and possibly no coefficients after $a_N$ we have $p_n=a_np_{n-1}+p_{n-2}$ and $q_n=a_nq_{n-1}+q_{n-2}$, i.e.
\begin{equation} \label{pqinduction1} x_i=[a_0,\ldots,a_n]=\frac{a_np_{n-1}+p_{n-2}}{a_nq_{n-1}+q_{n-2}}. \end{equation}
Then we consider\footnote{The third step is slightly sloppy, since the last coefficient is no longer an integer. No great harm is done, and this can be interpreted as a continued fraction in the more general sense.}
\begin{eqnarray}
x_{n+1} = \frac{p_{n+1}}{q_{n+1}}&=&[a_0,a_1,\ldots,a_{n+1}] \nonumber \\
&=&a_0+\frac{1}{^{^{\displaystyle a_1+}} \frac{\ddots}{\textstyle a_n+\frac{1}{n+1}}} \nonumber \\ &=&[a_0,a_1,\ldots,a_n+ \textstyle \frac{1}{a_n+1}] \nonumber \end{eqnarray} \begin{eqnarray}
&=& \frac{ \left( a_n+\frac{1}{a_{n+1}} \right) p_{n-1}+p_{n-2}}{ \left( a_n+\frac{1}{a_{n+1}} \right) q_{n-1}+q_{n-2}} \qquad \qquad by \; (\ref{pqinduction1}) \nonumber \\
&=& \frac{(a_n a_{n+1}+1)p_{n-1}+a_{n+1}p_{n-2}}{(a_n a_{n+1}+1)q_{n-1}+a_{n+1}q_{n-2}} \nonumber \\ &=& \frac{a_{n+1}(a_np_{n-1}+p_{n-2})+p_{n-1}}{a_{n+1}(a_nq_{n-1}+q_{n-2})+q_{n-1}} \nonumber \\
&=& \frac{a_{n+1}p_{n}+p_{n-1}}{a_{n+1}q_{n}+q_{n-1}}.
\end{eqnarray}
The lemma follows by induction. $\diamondsuit$

\begin{cor} Taking determinants of the matrices in \eqref{mx1}, we get \begin{equation} \label{detrel1} p_n q_{n-1}-q_n p_{n-1} = (-1)^{n-1} \end{equation} \end{cor}

\begin{cor} Writing $p_n q_{n-2}-q_n p_{n-2} = (a_np_{n-1}+p_{n-2})q_{n-2}-(a_nq_{n-1}+q_{n-2})p_{n-2}=a_n(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})+(p_{n-2}q_{n-2}-p_{n-2}q_{n-2})=(-1)^{n-2}a_n$ we get \begin{equation} \label{detrel2} p_n q_{n-2}-q_n p_{n-2} = (-1)^n a_n. \end{equation} \end{cor}

\begin{cor} For any $n$ and any continued fraction (with more than $n+1$ coefficients) we have \begin{equation} (p_{n},q_{n})=1 \end{equation} \end{cor}
\emph{Proof.} Suppose $d | p$. Then $d$ divides the $LHS$ or \eqref{detrel1}, so we must have $d=\pm 1$. \\

\begin{cor} \label{qdiff} For any continued fraction (more than $n$ terms) we have $\forall n\geq 1$:
\begin{itemize}
\item[] $q_n \geq q_{n-1}$, strict inequality for $n>1$
\item[] $q_n \geq n$, strict inequality for $n>3$.
\end{itemize}
\end{cor}
\emph{Proof.} The first part follows from $q_0=1$, $q_1=a_1$, Lemma \ref{pandq}, and the fact that all coefficients after the first are strictly positive. The second part follows from the first and the fact that the coefficients are strictly positive. $\diamondsuit$

\begin{lemma} \label{xdiff} The sequences $x_{2i}$ and $x_{2i+1}$ are increasing and decreasing sequence, respectively. Moreover, we have $x_{2n}<x_{2n+1}$ for every $n$ (assuming of course that the continued fraction has more than $2n+1$ coefficients). \end{lemma}
\emph{Proof.} Taking into account that the coefficients (thus all $p_i$ and $q_i$ for $i \geq 0$) are strictly positive, and that equations \eqref{detrel1} and \eqref{detrel2} can be rewritten as
\begin{equation} \label{detrel3} x_n-x_{n-1}=\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{(-1)^{n-1}}{q_nq_{n-1}} \end{equation} and
\begin{equation} \label{detrel4} x_n-x_{n-2}=\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}=\frac{(-1)^{n}a_n}{q_nq_{n-2}}, \end{equation}
the right substitutions yield the Lemma. $\diamondsuit$
\\

We want to study one more aspect of continued fractions before we can really say things about the numbers they represent. Since any finite continued fraction can be written in two ways,
\begin{equation} [\ldots,a_N]=[\ldots,(a_N-1),1], \end{equation} let us adopt the convention that the last term is never 1. For a given continued fraction of more than $n$ terms, let $\alpha_n$ denote its ``tail end,'' $[a_n,a_{n+1},\ldots]$. If $\lfloor x \rfloor$ denotes the greatest integer $\leq x$, then we have
\begin{lemma} $\lfloor \alpha_n \rfloor = a_n$ for all $n$. \end{lemma}
\emph{Proof.} If the continued fraction is finite and $N=n$, the result is trivial. Otherwise, $\alpha_n = a_n+\frac{1}{a_{n+1}+\ldots}$. If the continued fraction is finite and $N=n+1$ then nothing follows $a_{n+1}$, which is $>1$ by the above convention, so the result follows. If not, then the ``\ldots'' are some other continued fraction, which is strictly positive because all the coefficients are strictly positive, so the denominator of $\frac{1}{a_{n+1}+\ldots}$ is strictly greater than 1 and the result follows. $\diamondsuit$

From this, we can prove the important result on uniqueness.
\begin{thm} \label{uniqueness}
Let $x=[a_0,\ldots,a_N]=[b_0,\ldots,b_M]$ be two finite continued fractions. Then $N=M$ and $a_i=b_i$ for all $i$. \end{thm}
\emph{Proof.} Certainly $\lfloor x \rfloor = a_0 = b_0$. Then \begin{eqnarray} \lfloor x \rfloor + \frac{1}{[a_1,\ldots,a_N]} &=& \lfloor x \rfloor + \frac{1}{[b_1,\ldots,b_M]} \\ \Rightarrow [a_1,\ldots,a_N]&=&[b_1,\ldots,b_M], \end{eqnarray} and the proof follows by induction. $\diamondsuit$
\begin{cor} \label{uniqueness2}
If two (convergent) infinite continued fractions are equal, $[a_0,a_1,\ldots]=[b_0,b_1,\ldots]$, then $a_i=b_i$ for all $i$. \end{cor}
\emph{Proof.} Pick an arbitrary integer $N$. Then the above induction argument can be used to show that the first $N+1$ coefficients of the two continued fractions are equal. Note that (as we shall demonstrate shortly) all the ``tail end'' continued fractions converge very nicely and pose no problem to the induction argument. $\diamondsuit$
\\

Now we are finally ready to prove the results on the continued fractions of rational and irrational numbers. To every real number $x$ we can associate a continued fraction in the following way. Let
\begin{equation} \label{xcf1} a_0 = \lfloor x \rfloor,\quad \alpha_1 =\frac{1}{x-a_0}.\end{equation} Then we will have \begin{equation} x=a_0+\frac{1}{\alpha_1}. \end{equation} We continue recursively, defining\footnote{Here we use $\alpha$ to denote the tail end of continued fractions. Note that in other parts of this paper we also use primed $a$'s. For example, we might write the continued fraction $[a_0,a_1,\ldots]$ as $[a_0,a_1']$ where $a_1'=\alpha_1=[a_1,a_2,\ldots]$.} \begin{equation} \label{xcf2} a_i = \lfloor \alpha_i \rfloor,\quad \alpha_{i+1} =\frac{1}{\alpha_i-a_i}. \end{equation}

 Certainly every finite continued fraction is a rational number, and by Theorem \ref{uniqueness} this continued fraction is unique. In the other direction,
\begin{thm} \label{rat}
The continued fraction expansion of every rational number is finite. \end{thm}
\emph{Proof.} In view of equations \eqref{xcf1}-\eqref{xcf2}, we want to show that the recursive process must terminate at some point.

Let $x=h/k$, $(h,k)=1$, $k$$>$$0$, be a rational number. Using the above recursion to find coefficients, we have $a_0=\lfloor x \rfloor$, so $h/k=a_0+\xi_0$ for some $0\leq\xi<1$. Then we can write $h=a_0k+\xi_0k$ and we see that the integer $\xi_0k$ is in fact the remainder of dividing $h$ by $k$--note that $0\leq\xi_0k<k$.

We can continued in this way. Let $k_1=\xi_0k$. Then
\begin{equation} \alpha_1=\frac{1}{x-a_0}=\frac{1}{\xi}=\frac{k}{k_1}=a_1+\xi_1 \end{equation}
with $0\leq\xi_1<1$, so $0\leq\xi_1k_1<k_1$. Then we define $k_2=\xi_1k_1$, and so on. We obtain a strictly decreasing sequence of nonnegative integers $k>k_1>k_2>\ldots$, which must eventully terminate. When this sequence terminates, we will have
\begin{equation} \alpha_n-\lfloor \alpha_n \rfloor = \xi_n = 0 \end{equation}
for some $n$, and the continued fraction will terminate. $\diamondsuit$ \\

For irrational numbers, the results are
\begin{thm} \label{irrat1} Every infinite continued fraction converges to an irrational limit. \end{thm}

\emph{Proof.} From Lemma \ref{xdiff} we know that the convergents to an infinite continued fraction satisfy $x_2,x_4,x_6,\ldots,x_5,x_3,x_1$, and both of the bounded monotone sequences $\{ x_{2n}\}$ and $\{ x_{2n+1}\}$ must converge to a real limit. But from Lemma \ref{xdiff} and Corollary \ref{qdiff} we have \begin{equation}
|x_{2n+1}-x_{2n}| = \frac{1}{q_{2n}q_{2n+1}} \leq \frac{1}{(2n)(2n+1)} \rightarrow 0 \quad as \; n \rightarrow \infty, \end{equation}
so the two limits must in fact be equal. And since we know that every rational number has a finite continued fraction expansion and continued fractions are (semi)unique, the limit of this infinite continued fraction must irrational. $\diamondsuit$


\begin{thm} \label{irrat2} Defined by the recursive method in equations \eqref{xcf1}-\eqref{xcf2}, the continued fraction expansion of an irrational number is infinite and converges to the number. \end{thm}

\emph{Proof.} If the expansion were finite, the recursive process would have to terminate somewhere. This means that the greatest integer of a rational function of $x$ involving just integer coefficients is zero, which is impossible. So the continued fraction of an irrational number must be infinite and must converge. We need to show that it actually converges to the number itself.

Let $x$ be irrational and denote by $[a_0,a_1,\ldots]$ its continued fraction expansion. We know that for any finite $n$ we will have $x=[a_0,\ldots,a_n,\alpha_{n+1}]$, with $\alpha_{n+1}$ defined as in equations\footnote{This is of course not a simple continued fraction.} \eqref{xcf1}-\eqref{xcf2}. The $(n+1)$st convergent to \emph{this} continued fraction is equal to the entire continued fraction, hence equal to $x$. So by Lemma \ref{pandq} we have
\begin{equation} x=\frac{\alpha_{n+1}p_n+p_{n-1}}{\alpha_{n+1}q_n+q_{n-1}} \end{equation}
and (by Corrolary \ref{detrel1})
\begin{eqnarray} \left| x-\frac{p_n}{q_n}\right|&=&\left|\frac{\alpha_{n+1}p_n+p_{n-1}}{\alpha_{n+1}q_n+q_{n-1}}-\frac{p_n}{q_n} \right| \nonumber \\
&=& \left| \frac{p_{n-1}q_n-p_nq_{n-1}}{q_n(\alpha_{n+1}q_n+q_{n-1})} \right| \nonumber \\
&=& \frac{1}{q_nq_{n+1}'}, \label{xconverg}
\end{eqnarray}
with $q_{n+1}'=\alpha_{n+1}q_n+q_{n-1}$. For any $n$, this is a measure of how well the $n$th partial convergent of the (simple) continued fraction of $x$ converges to $x$.

Since $a_{n+1}=\lfloor \alpha_{n+1} \rfloor<\alpha_{n+1}<a_{n+1}+1$ (strict inequality because the continued fraction is infinite) and $a_{n+2}\geq1$, we have
\begin{eqnarray}
&q_{n+1}=a_{n+1}q_n+q_{n-1}<q_{n+1}'<(a_{n+1}+1)q_n+q_{n-1}=q_{n+1}+q_n,& \nonumber \\
&q_{n+1}+q_n\leq a_{n+2}q_{n+1}+q_n=q_{n+2}& \nonumber \\
&\Rightarrow \; q_{n+1}<q_{n+1}'<q_{n+2}.&
\end{eqnarray}
Therefore, from \eqref{xconverg} and Corrolary \ref{qdiff} we have
\begin{eqnarray}
\label{convbound} &\displaystyle \frac{1}{q_nq_{n+2}}<\left| x-\frac{p_n}{q_n}\right| <\frac{1}{q_nq_{n+1}}& \\
&\Rightarrow \displaystyle \left| x-\frac{p_n}{q_n}\right| < \frac{1}{n^2} \, \rightarrow \, 0&
\end{eqnarray}
as $n\rightarrow \infty$. $\diamondsuit$ \\

The last result we want is
\begin{thm} \label{perquad} An irrational number $x$ has a periodic continued fraction if and only if it satisfies a quadratic equation $Ax^2+Bx+C=0$ with integer coefficients. \end{thm}

$\mathbf{\Rightarrow}$

Let $x=[a_0,a_1,\ldots,a_{l-1},\overline{a_l,\ldots,a_{l+k-1}}],$ a continued fraction with period $k$. Then \begin{equation} \alpha_l=[\overline{a_l,\ldots,a_{l+k-1}}] = [a_l,\ldots,a_{l+k-1},\overline{a_l,\ldots,a_{l+k-1}}] = [a_l,\ldots,a_{l+k-1},\alpha_l]. \nonumber \end{equation} If $\displaystyle \frac{p_i}{q_i}$ are the convergents to $\alpha_l$, then \begin{equation} \alpha_l=\frac{\alpha_l p_{k-2}+p_{k-3}}{\alpha_l q_{k-2}+q_{k-3}}, \end{equation} which translates into a quadratic equation for $\alpha_l$. But if $\frac{p_i'}{q_i'}$ are the convergents for $x$, then \begin{eqnarray} x&=&[a_0,\ldots,a_{l-1},\alpha_l] \nonumber \\ \; \Rightarrow x&=&\frac{\alpha_l p_{l-1}'+p_{l-2}'}{\alpha_l q_{l-1}'+q_{l-2}'} \nonumber \\ \Rightarrow \alpha_l &=& \frac{p_{l-2}'-xq_{l-2}'}{xq_{l-1}'-p_{l-1}'} \nonumber \\ \Rightarrow \alpha_l &=& \frac{\alpha_l p_{k-2}+p_{k-3}}{\alpha_l q_{k-2}+q_{k-3}} \cdot \frac{xq_{l-1}'-p_{l-1}'}{xq_{l-1}'-p_{l-1}'}, \nonumber
\end{eqnarray} which becomes a quadratic equation for $x$ with integer coefficients. Note that the leading coefficient must be non-zero, for otherwise $x$ would be rational and the continued fraction could not be infinite.

$\mathbf{\Leftarrow}$

Assume $x$ solves the irreducible quadratic
\begin{equation} ax^2+bx+c=0 \label{quadc1} \end{equation} with integer coefficients. Further assume that this is irreducible (otherwise, $x$ would be rational). Write
\begin{equation} x=[a_0,a_1,\ldots]=[a_0,\ldots,a_{n-1},\alpha_n] =\frac{\alpha_np_{n-1}+p_{n-2}}{\alpha_nq_{n-1}+q_{n-2}}. \end{equation}
By substituting this in \eqref{quadc1}, clearing denominators, and collecting terms, we get
\begin{equation} \label{quadc2} A_n(a_n')^2+B_na_n'+C_n=0, \end{equation} with (in particular)
\begin{equation} A_n=ap_{n-1}^2+bp_{n-1}q_{n-1}+cq_{n-1}^2\neq0, \quad C_n=A_{n-1} \end{equation} and
\begin{equation} \label{quadcdisc} B_n^2-4A_nC_n=b^2-4ac. \end{equation}
Note that $A_n\neq0$ because otherwise the rational $p_{n-1}/q_{n-1}$ would solve the irreducible \eqref{quadc1}.

Now, by \eqref{convbound} we can find $|\delta_{n-1}|<1$ such that
\begin{eqnarray}
&\displaystyle x-\frac{p_{n-1}}{q_{n-1}}=-\frac{\delta_{n-1}}{q_{n-1}^2},&\\
&\displaystyle p_{n-1}=xq_{n-1}+\frac{\delta_{n-1}}{q_{n-1}},
\end{eqnarray}
and we substitute this into the expression for $A_n$, expand, and take the absolute value (and note that $ax^2+bx+c=0$) to get
\begin{equation} |A_n|\leq 2|ax|+|b|+|a|. \end{equation}
Likewise, since $C_n=A_{n-1}$ we have
\begin{equation} |C_n|\leq 2|ax|+|b|+|a|, \end{equation}
and from \eqref{quadcdisc} we have
\begin{equation} B_n\leq \sqrt{|4A_nC_n|+|b^2-4ac|}\leq \sqrt{4(2|ax|+|b|+|a|)^2+|b^2-4ac|}. \end{equation}
Therefore (since these relations hold for all $n$), there exists a bound $M$ such that $|A_n|,|B_n|,|C_n|<M$ for all $n$.

Since there are only a finite number of possible values for the triplet $(A_n,B_n,C_n)$ and we go through infinite values of $n$, we must be able to find three values of $n$ that have the same triplet, say $n_1$, $n_2$, and $n_3$. So three tail ends $a_{n_1},a_{n_2},a_{n_3}$ all satisfy the nonzero quadratic \eqref{quadc2}. But this implies that two of them must be equal, which implies periodicity. $\diamondsuit$


\subsection{Kuzmin's Theorem}
This theorem will be important when we consider the distribution of coefficients in various linearly periodic continued fractions. The proof is rather intricate and has been left out; consult \cite{kuzmin}.
%
\begin{thm} Let $k$ be an integer $\geq 1$. Let $[a_0(x),a_1(x),\ldots]$ be the continued fraction of $x$. Then for \emph{almost any} number $x$, the probability that $a_n(x)=k$ is \begin{equation} P(a_n(x)=k) = \log_2 \left( 1+\frac{1}{k(k+2)} \right) +O\left( \frac{1}{k(k+1)}e^{-C \sqrt{n+1}} \right), \end{equation}
with $C$ independent of $n$ and $k$.
\end{thm}
This result was in fact be improved to \begin{equation} P(a_n(x)=k) = \log_2 \left( 1+\frac{1}{k(k+2)} \right) +O(e^{-C'n}) \end{equation} by Levy, which is nice though not entirely relevant to the problem at hand.

Note that no linearly periodic continued fraction, of the form \eqref{lpcf}, can satisfy Kuzmin's Theorem. All periodic coefficients $f_i(n)$ fall into one of two categories: coefficients which remain constant from period, and coefficients which increase by a fixed amount from period to period. If we pick any number $k$ that is greater than the constant coefficients, it may occur a finite number of times as a value of an increasing coefficient and then never again. So $P(a_n=k)=0$ for sufficiently large $n$. Likewise, $P(a_n=k)$ is non-zero but fixed for any of the constant coefficients. So the continued fraction cannot possibly satisfy the theorem. This observation, incidentally, implies that the set of all linearly periodic continued fractions has measure $0$; otherwise, Kuzmin's theorem could not fail.

Nevertheless, we \emph{will} be interested in the distribution of the constant periodic coefficients in comparison to Kuzmin's Theorem. For this we can simply take $n$ as large as we want and the error in the theorem as small as we want. For future reference, Table \ref{kprob} lists a few probabilities, disregarding error.\\
\begin{table}[!hbt] \label{kprob}
\begin{center}
\begin{tabular}{c|ccc|c}$\mathbf{k}$ & $\mathbf{P(a_n=k)}$ (\%)& \qquad & $\mathbf{k}$ & $\mathbf{P(a_n=k)}$ (\%) \\ \cline{1-2} \cline{4-5}
1&41.50&&11&1.01\\ \cline{1-2} \cline{4-5}
2&16.99&&12&0.86\\ \cline{1-2} \cline{4-5}
3&9.31&&13&0.74\\ \cline{1-2} \cline{4-5}
4&5.89&&14&0.64\\ \cline{1-2} \cline{4-5}
5&4.06&&15&0.56\\ \cline{1-2} \cline{4-5}
6&2.97&&16&0.50\\ \cline{1-2} \cline{4-5}
7&2.27&&17&0.45\\ \cline{1-2} \cline{4-5}
8&1.79&&18&0.40\\ \cline{1-2} \cline{4-5}
9&1.45&&19&0.36\\ \cline{1-2} \cline{4-5}
10&1.20&&20&0.33
\end{tabular}
\caption{Kuzmin Probabilities}
\end{center}
\end{table} \\

\section{The Lang-Trotter Algorithm}
The initial motivation behind studying rational shifts of linearly periodic continued fractions was the Lang-Trotter algorithm for finding continued fraction expansions of roots of a polynomial. In order to use Equations \eqref{xcf1}-\eqref{xcf2} to calculate the continued fraction of a number, one must know the number to very high accuracy (at least in order to retreive a significant number of coefficients). On the other hand, to use the following algorithm nothing needs to be known about an algebraic number except its polynomial and the greatest integer less than or equal to it.

\subsection{The algorithm\protect\footnote{taken from \cite{lang}}}

Let $\xi$ be an irrational root of a polynomial $p_0(x)$ of degree $d$ such that
\begin{enumerate}
\item the leading coefficient of $p_0(x)$ is positive \label{lcpos}
\item the root $\xi$ is simple \label{simple}
\item $\xi>1$ \label{gt1}
\item there are no other positive roots. \label{1pos}
\end{enumerate}
Then let $a_0=\lfloor \xi \rfloor=$ the greatest integer $k$ such that $p_0(k)<0$ (this is the case since a positive leading coefficient implies that $f_0(x)$ will go from negative to positive at its last real root) and let $q_0=p_0(x+a_0),\; p_1(x) =-x^d q_0(x^{-1})= -x^{d}p_0(a_0+x^{-1})$. The roots of $q_0(x)$ are exactly those of $p(x)$ shifted by $-a_0$ units. So $q_0(x)$ has the root corresponding to $\xi$ between 0 and 1 and no other positive roots. Then the roots of $p_1(x)$ are the reciprocals of those of $q_0(x)$, so $(\xi-a_0)^{-1} > 1$ and is the unique positive root of $p_1(x)$. Also notice that the leading coefficient of $p_1(x)$ is positive. Thus we have constructed another polynomial that satisfies (\ref{lcpos}) - (\ref{1pos}).

For all $i\geq1$ we define the recursion \begin{eqnarray} a_i&=&\lfloor p_i(x) \rfloor \nonumber \\ p_{i+1}(x)&=&-x^d p_i \big( \frac{1}{x}+a_i \big), \end{eqnarray} where $\lfloor p_i(x) \rfloor$ is the greatest integer $k$ such that $p_i(k)<0$. If we let $\xi_i$ denote the unique positive root of $p_i(x)$ then we have $a_i=\lfloor \xi_i \rfloor$. So, with $\xi_0=\xi$, the effects of our recursion are just \begin{equation} a_i=\lfloor \xi_i \rfloor,\qquad \xi_{i+1}=\frac{1}{\xi_i-a_i}, \end{equation} which is identical to equations \eqref{xcf1} - \eqref{xcf2}. Therefore, the algorithm simply generates the continued fraction coefficients of $\xi$.

\subsection{Loosening constraints}
%redo recursion with gr int of certain root
While it is nice that the $p_i(x)$ all satisfy conditions (\ref{lcpos}) - (\ref{1pos}), one might wonder whether, for practical applications, these conditions are really necessary. They certainly restrict the possibility of using the algorithm on any given algebraic number. We shall thus endeavor to eliminate most of them.

Let's begin with condition (\ref{lcpos}). The main advantage of having a positive leading coefficient is that a polynomial is negative to the left of its largest root and positive to its right. Then it is always possible to find the greatest integer less than that root by testing $p_i(k) \stackrel{?}{<} 0$ for $k=1,2,\ldots$. But we could simply test for a sign change instead and remove the condition. Or, with a program (such as \emph{Mathematica}) or an algorithm (such as Newton's method) that finds roots very precisely, we could find the largest positive root $\xi_i$ of $p_i(x)$ and take $\lfloor \xi_i \rfloor$. We remove condition (\ref{lcpos}) and reformulate the algorithm as:
\begin{eqnarray} largest\; root(p_i(x))&=&\xi_i \nonumber \\ a_i&=&\lfloor \xi_i \rfloor \nonumber \\ p_{i+1}(x)&=&x^d p_i \big( \frac{1}{x}+a_i \big). \label{reformulated} \end{eqnarray}

Now consider condition (\ref{simple}). If the root is not simple, then testing $f_i(k)$ for a sign change will not work. However, the reformulted algorithm will do just fine. So we can delete condition (\ref{simple}).

Granted, eliminating conditions (\ref{lcpos}) and (\ref{simple}) is not incredibly useful. A polynomial with negative leading coefficient could have been multiplied by $-1$ to satisfy (\ref{lcpos}). And we can try to factor the polynomial so that it no longer has simple roots. If we can find the irreducible polynomial for $\xi$, we know it cannot have any repeated irrational roots.\footnote{We are in a field of characteristic zero, so all polynomials are seperable.} But the reformulated algorithm will also allow us to loosen the other two conditions, which are much more limiting.

The idea of the algorithm is that it finds the greatest integer less than or equal to some root, shifts the polynomial so that the root is in $(0,1)$, and then inverts the polynomial so that the initial root becomes the largest positive root. Suppose we have a root $\xi$ of $p_o(x)$ such that all other real roots\footnote{Note we do not care about complex roots; the recursion will always preserve their complexity and they will not interfere with the process.} are at least one unit away. In other words, for all other roots $r_j$ we have $|\xi-r_j|>1$. We take $a_0=\lfloor \xi \rfloor$ as usual. Then $\xi$ becomes the only root of $q_0(x)=p_0(x-a_0)$ between 0 and 1; so $\xi_1=(\xi-a_0)^{-1}$ is the only root of $p_1(x)=x^d q_0(x^{-1})$ that is $>1$. Following the algorithm through to $p_2(x)$, we see that $\xi_2=(\xi_1-a_1)^{-1}>1$ is the single positive root of $p_2(x)$, so conditions (\ref{gt1}) and (\ref{1pos}) are satisfied from that point on. Therefore, we can weaken these conditions to
\begin{enumerate}
\item[$3'.$] For all roots $r_j\neq \xi$ of $p_0(x)$, $|\xi-r_j|>1$.
\end{enumerate}

We might even go a step further. For suppose we have a root $\xi$ of $f_0(x)$ and the two real roots closest to $\xi$,  $r_1<\xi <r_2$, satisfy
\begin{enumerate}
\item[$3''.$] There is an integer between $r_1$ and $\xi$, and
\item[$4''.$] If $a_0=\lfloor \xi \rfloor$, there is an integer between $\displaystyle \frac{1}{r_2-a_o}$ and $\displaystyle \frac{1}{\xi-a_0}$.
\end{enumerate}
Then because of ($3''$) the root $\xi_1=(\xi-a_0)^{-1}$ will be the largest positive root of $p_1(x)$ and by ($4''$) there is an integer separating $\xi_1$ and the next largest root. Thus $p_2(x)=x^d p_1(x^{-1}+\lfloor \xi_1 \rfloor)$ will have a unique positive root $>1$,  $\xi_2=(\xi_1-\lfloor \xi_1 \rfloor)^{-1}$ and the algorithm will work just fine from then on.

We have succeeded in \emph{almost} taking out all the original conditions, provided we keep track of where the first few roots are mapped to (before they become the unique positive root $>1$). But what happens if we let $\xi$ be \emph{any} root of \emph{any} polynomial $p_0(x)$?

\subsection{Can we do it?}
We generate incorrect continued fraction coefficients if there is \emph{not} an integer between a $\xi_i$ and the next largest root. Conditions ($3''$) and ($4''$) were sufficient to prevent this. But, \emph{in general}, they are also necessary.

\begin{prop} If ($3''$) does not hold, and we assume that the roots of $p_0(x)$ are randomly distributed\footnote{There are several ways roots that satisfy ($3''$) might be randomly distributed, leading to slightly different probability bounds. For now, we assume that ``randomly distributed'' means the points $(x,y)$ (see definitions in the beginning of the proof) are randomly distributed in the triangle below the diagonal $y=x$ of $(0,1) \times (0,1)$. This definition is best for applications of concepts that will be developed later in this section.} (mod 1) in $(0,1)$, then the probability that the algorithm will fail is at least $2-2\log 2 \approx .6137$ .  \end{prop}

\emph{Proof.} Suppose ($3''$) doesn't hold, and let $r \neq \xi$ be the smallest root (there may be several) such that $a_0= \lfloor \xi \rfloor = \lfloor r \rfloor$. After being shifted, both of these roots will end up in $(0,1)$; so $\xi_1=\frac{1}{\xi-a_0}$ and $r_1=\frac{1}{r-a_0}$ will both be positive roots $>1$, with $\xi_1<r_1$. If there is an integer between $\xi_1$ and $r_1$ the algorithm will fail, generating $a_1 = \lfloor r_1 \rfloor \neq \lfloor \xi_1 \rfloor$. We know that an integer will separate the two roots if $r_1-\xi_1 > 1$, so let's find the probability of this happening. Let $x = \xi-a_0=\xi$ (mod 1) and $y = r-a_0=r$ (mod 1). We want
\begin{eqnarray*}
\frac{1}{y}-\frac{1}{x} &>& 1 \\
\Rightarrow \frac{x-y}{xy} &>& 1 \\
\Rightarrow x-y&>&xy \\
\Rightarrow y &<& \frac{x}{x+1}.
\end{eqnarray*}
So, given $\xi$, the probability of $r_1-\xi_1 > 1$ should be $\textstyle \frac{\xi -\lfloor \xi \rfloor}{\xi-\lfloor \xi \rfloor+1}$. And averaging this over all possible values of $\xi$, i.e. all values of $x$, we get \begin{equation} Avg \, Prob = \int_0^1 \frac{x}{x+1}\, dx=1-\log 2 \approx .30685\, . \end{equation} But to obtain this we assumed that $r$ was randomly distributed in $(\lfloor \xi \rfloor, \lfloor \xi \rfloor +1)$, which is not quite true since we know by assumption that $r \in (\lfloor \xi \rfloor,\xi)$. If we take the definion of ``randomly distributed'' in the footnote to the Proposition, and consider points $(x,y)$ in the unit box $(0,1)\times (0,1)$ we see that what we have actually calculated is the area under the curve $y=x/(x+1)$. Our restriction (that these roots violate ($3''$)) implies that all possible points are situated (and randomly distributed) below the line $y=x$. So the lower bound on the probability of the algorithm failing is the fraction of points below $y=x$ that are also below $y=x/(x+1)$, which is just $2(1-\log 2)\approx 0.6137$. $\diamondsuit$

%To get a better bound, we can imagine finding a lower bound on the probability that there is no integer between $\xi_1$ and $r_1$, running a cycle of the algorithm, finding a lower bound on the probability that there is no integer between $\xi_2$ and $r_2$, running the algorithm again, and finding the probability that $r_3-\xi_3>1$. Such calculations are beyond our present scope (and perhaps beyond our present ability), but we will pursue the general idea a bit further. %
%Assume that $r$ is the \emph{only} other root between $\xi$ and $\lfloor \xi \rfloor$. To find (bounds on) probabilities of failure, we would look at the probabilities that $x_i$ and $r_i$ are separated by an integer for odd $i$. But we can also obtain bounds on probabilities of success by finding the probability that $x_i$ and $r_i$ are separated by an integer for even $i$. The idea is that if ($3''$) initially fails, we can keep iterating the algorithm until the first step for which ($3''$) holds. If this is an odd step, the algorithm has failed. If this is an even step, it will succeed. %So in fact it would be no surprise if the chance of success were very close to 50\%.
%\footnote{More, or less\ldots or exactly? This seems like a very interesting and very difficult problem. The answer to whether the probability is greater than or less than 50\% probably depends on the first iteration of the algorithm: is there more chance of success or failure? The lower bound argument we gave above does not provide too much insight.}
%We would expect a similar result if ($4''$) did not hold. %The above argument on probability should make it clear that it is very difficult, if not perhaps impossible, to formulate a condition that is absolutely necessary for the success of the algorithm. For a given $\xi$, the set of roots $r_1$ in $(\lfloor \xi \rfloor, \xi)$ and $r_2$ in $(\xi,\lfloor \frac{1}{\xi - \lfloor \xi \rfloor} \rfloor^{-1}+\lfloor \xi \rfloor)$ that allow the algorithm to succeed (or fail) may even be dense.\footnote{The second interval arose from the consideration that $\lfloor \frac{1}{\xi - \lfloor \xi \rfloor} \rfloor < \frac{1}{r_2-\lfloor \xi \rfloor} <  \frac{1}{\xi - \lfloor \xi \rfloor}$ violates ($4''$).}

Let's pursue success and failure of the algorithm a bit further. Suppose ($3''$) fails for a root $r$ such that $\lfloor \xi \rfloor <r<\xi$, and $r$ is the only root within a unit of $\xi$. As noted previously, the algorithm will certainly fail if there is an integer between $\frac{1}{\xi-\fxi}$ and $\frac{1}{r-\fxi}$ and \emph{may} succeed otherwise. So we have possible success if \begin{equation} \frac{1}{\xi-\fxi} < \frac{1}{r-\fxi} < \lfloor \frac{1}{\xi-\fxi} \rfloor +1. \end{equation} We solve this for $r$:
\begin{equation} \xi > r > \left( \lfloor \frac{1}{\xi-\fxi} \rfloor +1 \right)^{-1}+\fxi. \end{equation}
Now assume for the moment that $\fxi=0$, since we are essentially looking at things mod 1. So our condition is \begin{equation} \xi > r > \left( \lfloor \frac{1}{\xi} \rfloor +1 \right)^{-1}. \end{equation} If $\xi$ is the reciprocal of an integer, then the RHS is just 
$\displaystyle \left( \frac{1}{\xi}+1 \right)^{-1} = \frac{\xi}{\xi+1}$. Then if we change $\xi$ to be just a little less than the reciprocal of an integer, the RHS will remain constant. But if $\xi$ becomes just a little more than the reciprocal of an integer the RHS will jump to what it would have been for the next highest integer. In this way we can see that the algorithm fails if $(\xi,r)$ is below the step-like function in Figure 1, and \emph{may} succeed otherwise.
\begin{figure}[!htp] \caption[rless1]{Possible success, first cycle} \begin{center}
\includegraphics[scale=.65]{rless1}
\end{center} \end{figure}

Let's go another step, assuming ``possible success'' on the first cycle. If we run the algorithm again, the image of $\xi$ will be greater than the image of $r$, so there will be definite success if there is an integer between the two and definite failure otherwise. The condition for possible failure is:
\begin{eqnarray}
\lfloor \xi_2 \rfloor &<& r_2 \nonumber \\
\Rightarrow \lfloor \frac{1}{\xi_1 - \lfloor \xi_1 \rfloor} \rfloor &<& \frac{1}{r_1-\lfloor \xi_1 \rfloor} \nonumber \\
\Rightarrow r_1 &<& \left( \lfloor \frac{1}{\xi_1 - \lfloor \xi_1 \rfloor} \rfloor \right)^{-1} + \lfloor \xi_1 \rfloor \end{eqnarray} \begin{eqnarray}
\Rightarrow \frac{1}{r-\fxi} &<& \left( \lfloor \frac{1}{\frac{1}{\xi-\fxi} - \lfloor \frac{1}{\xi-\fxi} \rfloor} \rfloor \right)^{-1} + \lfloor \frac{1}{\xi-\fxi} \rfloor \nonumber \\
\Rightarrow r &>& \left( \left( \lfloor \frac{1}{\frac{1}{\xi-\fxi} - \lfloor \frac{1}{\xi-\fxi} \rfloor} \rfloor \right)^{-1} + \lfloor \frac{1}{\xi-\fxi} \rfloor \right)^{-1} + \fxi,
\end{eqnarray}
which we plot in Figure 2, along with the previous condition.
\begin{figure}[!htp] \caption[rless2]{Possible failure, second cycle} \begin{center}
\includegraphics[scale=.6]{rless2}
\end{center} \end{figure}
Observe that there is definite failure below the bottom step function, definite success between the two step functions, and possible failure between $\xi$ and the step functions.

We can continue in this way, alternating between conditions for definite failure (odd cycles) and definite success (even cycles). The algebra becomes more tedious, so the exact conditions are not included here.\footnote{Actually, the observation that the formulas are in fact continued fractions does allow them to be written explicitly in a nice way. See Proposition \ref{CfTr}.} \emph{Mathematica} notebook \textsf{rless.nb} can be used to generate the formulas. The notebook also generates plots of any iteration. Notice that after every even number of cycles, we are essentially in the same position we started from. So, given a plot of all the cycles, we would expect to see the same structure in a triangle derived from an even cycle as in the entire plot. Likewise, the interior of a triangle derived from an odd cycle should resemble the interior of any other triangle derived from an odd cycle. Figure 3 shows two plots of success and failure for the first five cycles of the algorithm.
\begin{figure}[!htp] \caption[rless5]{Fifth cycle} \begin{center}
\includegraphics[scale=.75]{rless5acc}
\end{center} \end{figure}
Observe that our prediction about the similar interiors of triangles is mostly valid. The triangle expanded in the bottom plot is similar (in the non-rigorous sense) to the entire top plot, but the relative sizes of the respective subtriangles are not to scale. The lengths of the largest subtriangle generated by the first cycle (the largest subtriangle in the top plot) are half the lengths of the triangle it is contained in (i.e. the bottom-right half of the entire plot). But the lengths of the largest subtriangle generated by the third cycle (the largest subtriangle in the bottom plot) are $2/5$ of the lengths of the triangle it is contained in. Whether this ratio remains $2/5$ for subtriangles of subsequent even cycles or changes is uncertain at the moment.

Now that we have a better understanding of the conditions for success or failure of the algorithm, we might hope to achieve better bounds on probabilities thereof. First, however, we show another interesting and helpful result.

\subsubsection{A visualization of continued fractions} \label{visual}

\begin{prop} Let $R_n(x)$ be the step-like function corresponding to the definite success or failure of the $n$th cycle of the algorithm. Then $R_n(x)=x$ if and only if the continued fraction expansion of $x$ has $\leq n$+1 coefficients. \label{CfTr} \end{prop}
Note that we are really looking at $\displaystyle \lim_{y \rightarrow x^{+}} R_n(y)$ with $y$ irrational since the algorithm will always ``fail'' for rational numbers after a finite number of steps, mapping the root $0$ to $\infty$. \\
Also note that although the algorithm is not applicable to transcendental irrationals, the $R_n(x)$ are definded for all reals (as we shall show). So for this proof we do not restrict ourselves to algebraic irrationals. \\
Finally note that this argument takes into account the duality of continued fraction notation. For any $x$ whose continued fraction has $n+1$ coefficients, we will have either $R_{n-1}(x)=x$ or $R_{n+1}(x)=x$ as well as $R_n(x)=x$.
\begin{cor} The set of numbers $x$ for which $R_n(x)=x$ (for some $n$) is precisely the set of rational numbers (by the results of Section 1). \end{cor}

\emph{Proof.} Recall that $\lfloor \xi_k \rfloor$ is the $k$th continued fraction coefficient of $\xi$ (provided the algorithm has not failed). Above we were looking at the algorithm's effect on a root $\xi$. Here $x$ takes the role of that root and to avoid confusion in this proof we formally define
\begin{eqnarray}
x_0=x,&& x_k=\frac{1}{x_{k-1}-\lfloor x_{k-1} \rfloor} \label{defx} \\
r_0=r,&& r_k=\frac{1}{r_{k-1}-\lfloor x_{k-1} \rfloor}. \label{defr}
\end{eqnarray}

The condition (for definite success\footnote{of course assuming the conditions for definite success or failure for all the other cycles have failed}) for the $n$th cycle, $n$ even, is
\begin{eqnarray} 
r_n &<& \lfloor x_n \rfloor \\
\Rightarrow r_{n-1} &>& \frac{1}{\lfloor x_n \rfloor} + \lfloor x_{n-1} \rfloor \nonumber \\
\Rightarrow r_{n-2} &<& \frac{1}{\frac{1}{\lfloor x_n \rfloor} + \lfloor x_{n-1} \rfloor} +\lfloor x_{n-2} \rfloor \nonumber \\
&\vdots & \nonumber \\
\Rightarrow r=r_0 &<&[\lfloor x \rfloor,\lfloor x_1 \rfloor,\ldots,\lfloor x_n \rfloor], \\
R^{(e)}_n(x)&=&[\lfloor x \rfloor,\lfloor x_1 \rfloor,\ldots,\lfloor x_n \rfloor]. \nonumber
\end{eqnarray}
Likewise the condition (for definite failure) for $n$ odd is
\begin{eqnarray}
r_n &>& \lfloor x_n \rfloor+1 \\
&\vdots & \nonumber \\
\Rightarrow r=r_0 &<& [\lfloor x \rfloor,\ldots,\lfloor x_{n-1} \rfloor,\lfloor x_n \rfloor+1], \\
R^{(o)}_n(x)&=& [\lfloor x \rfloor,\ldots,\lfloor x_{n-1} \rfloor,\lfloor x_n \rfloor+1]. \nonumber
\end{eqnarray}
So both conditions take the form of continued fractions. Now pick some irrational $x$ with continued fraction expansion $[a_0,a_1,\ldots]$. Then for even $n$, $R_n(x)$ is the rational number $[a_0,\ldots,a_n]$; and for odd $n$, $R_n(x)=[a_0,\ldots,a_{n-1},a_n+1]$. We can decrease $x$ by a very small amount (keeping it irrational) and $R_n(x)$ will not change. In fact, $R_n(x)$ will not change as long as $x>R_n(x)$. To see this, consider the fact that we can change an irrational number a little bit and not have its first $n+1$ continued fraction coefficients change. Or look at the triangles of Figure 3: the bottom edges of all the triangles are horizontal, so we can start on the bottom edge of any triangle and move to the left a little ways without changing $R_n(x)$.

Now (with $x=[a_0,\ldots]$ fixed as above) imagine taking \begin{equation} X_n(x)=\inf_{y \notin Q} \{ y:R_n(y)=R_n(x) \} \end{equation}. Note that two continued fractions of the same length are equal if and only if all their coefficients are equal.\footnote{It is irrelevant whether or not their final coefficients are 1, since they must be of the same length.} So to find $X_n(x)$, we slowly, \emph{continuously}, decrease $y$ until some coefficient(s) of the continued fraction $R_n(y)$ change (recall that for $y=x$, $R_n(y)=[a_0,\ldots,a_n(+1)]$). Since we are continuously varying $y$ and $R_n(y)$ is a monotonically increasing function of $y$, the change in the value of $R_n(y)$ must be the smallest one possible.\footnote{For this proof, we are not really interested in this change; but this observation is useful in further results.} Thus, the change occurs in the last continued fraction coefficient, or the last two if changing the last one is impossible.

Let $n$ be even, $R_n(x)=[a_0,\ldots,a_n]$. The value of a continued fraction is a (strictly) monotonically increasing function of its odd coefficients (eg, $a_0,a_2,\ldots$) and a (strictly) monotonically decreasing function of its even coefficients (eg, $a_1,a_3,\ldots$). As we cross the threshhold $X_n(x)$, the value of $R_n(y)$ decreases. If $a_n$ is greater than 1, it will simply be reduced by 1. In this case, we will have $X_n(x)=R_n(x)$. To see this, write $y=[a_0,\ldots,a_{n-1},b_n,b_{n+1}']$ with $b_{n+1}'$ some irrational number, the tail end of $y$. For $y=x$, we will have $b_n=a_n,\: b_{n+1}'=a_{n+1}'$. As we decrease $y$ continuously but do not cross the threshhold, $b_n$ must not change and $b_{n+1}'$ increases continuously. Our threshhold value is thus
\begin{eqnarray} X^{(e)}_n(x)&=& \lim_{b_{n+1}'\rightarrow \infty} [a_0,\ldots,a_{n-1},a_n,b_{n+1}'] \nonumber \\
&=&[a_0,\ldots,a_n+\frac{1}{\infty}] \nonumber \\
&=&[a_0,\ldots,a_n] \nonumber \\
&=&R_n(x). \label{thresh}
\end{eqnarray}
Immediately on the other side of this threshhold (the limit in the other direction), $R_n(y)$ is $[a_0,\ldots,a_n-1]$ and $y$ is $[a_0,\ldots,a_n-1,1']$, where $1'$ is a really a limit along irrationals greater than $1$.

In the case that $n$ is even and $a_n=1$, we cannot simply decrease $a_n$ by $1$. Nevertheless, Equation \ref{thresh} will still hold since, from the right, the same limiting process will determine $y$; the only way to decrease $y$ without affecting its first $n$+1 coefficients is to increase $b_{n+1}'$. But on the other side of the threshhold what we get is \begin{eqnarray*} y&=&\lim_{b_n'\rightarrow \infty} [a_0,\ldots,a_{n-1}+1,b_n'] \\ &=& [a_0,\ldots,a_{n-1}+1] \\ &=& [a_0,\ldots,a_{n-1},1].\end{eqnarray*} Note that this implies that $R_n(y)$ changes infinitesimally across the threshhold; approaching the threshhold from the left, it takes on values $[a_0,\ldots,a_{n-1}+1,b]$ for infinitely large integers $b$.

Now let $n$ be odd, $R_n(x)=[a_0,\ldots,a_{n-1},a_n+1]$. We use essentially the same techniques as with even $n$. With $y=[a_0,\ldots,b_n,b_{n+1}']$ as above, we find the threshhold value by starting with $y=x$ and continuously decreasing $y$ so that $R_n(y)$ does not change. This corresponds to continuously \emph{decreasing} $b_{n+1}'$ while keeping $b_n=a_n$ constant. Note that this means $b_{n+1}'>1$, since when $b_{n+1}'\leq 1$ we are effectively increasing the value of $b_n$. So the limit we want is
\begin{eqnarray}
X^{(o)}_n&=& \lim_{b_{n+1}'\rightarrow 1^+} [a_0,\ldots,a_n,b_{n+1}'] \nonumber \\
&=& [a_0,\ldots,a_n,1] \nonumber \\
&=& [a_0,\ldots,a_{n-1},a_n+1] \nonumber \\
&=& R_n(x),
\end{eqnarray}
the same result we get in the even $n$ case. We can also investigate values across the thresshold. On the right we have $R_n(y)=[a_0,\ldots,a_{n-1},a_n+1]$, and we want the smallest possible decrease in this, so on the left we will get $R_n(y)=[a_0,\ldots,a_{n-1},(a_n+1)+1]$ (we can always increase the last coefficient). The corresponding limit in $y$ is \begin{equation*} \lim_{b_{n+1}'\rightarrow \infty} [a_0,\ldots,a_{n-1},a_n+1,b_{n+1}'] = [a_0,\ldots,a_{n-1},a_n+1]. \end{equation*}

There is one more case that should be discussed. Suppose $n$ is odd and consider $R_n(x)=[a_0,\ldots,a_{n-1},1]$. This cannot really happen, since the final coefficient should be $1$ plus the corresponding coefficient of $x$, which is not $0$. Nevertheless, we can think of this as a limit of $R_n=[a_0,\ldots,a_{n-1}+1,b]$ as $b\rightarrow \infty$ along integers. Essentially, we are passing to the left through lots of threshhold values of the kind described in the preceding paragraph, spaced closer and closer together. As we continuously decrease $y=[a_0,\ldots,a_{n-2},b_{n-1},b_n']$ so that $b_{n-1}=a_{n-1}+1$ and $b_n' \rightarrow \infty$, we arrive at a limit
\begin{eqnarray*} X &=& [a_0,\ldots,a_{n-1}+1,\infty] \\
&=& [a_0,\ldots,a_{n-1}+1] \\
&=& [a_0,\ldots,a_{n-1},1].
\end{eqnarray*}
$X$ is a much ``stronger'' threshhold value than the infinitely many small ones crossed to get to it, because to its left we have $R_n(y)=[a_0,\ldots,a_{n-1},2]$, a significant change. (Taking the corresponding limit from the left is left to the reader.) Moreover, we do have $R_n(X)=X$, defined by a limit from the right. To see this, note that to get to $X$ we considered $y=[a_0,\ldots,a_{n-2},a_{n-1}+1,b_n']$ with very large $b_n'$. As $b_n'$ goes to infinity, $R_n(y)=[a_0,\ldots,a_{n-2},a_{n-1}+1,\lfloor b_n' \rfloor +1]$ also approaches $[a_0,\ldots,a_{n-2},a_{n-1}+1]=[a_0,\ldots,a_{n-2},a_{n-1},1]$, so \begin{equation}\lim_{y\rightarrow X^+} R_n(y)=X.\end{equation}

Before continuing with some more observations, we can finish the proof. We have shown that (for some $n$) every threshhold value $X$ is a value for which $R_n(X)=X$ (definited by a limit). Let $z$ be a rational number whose continued fraction has lengths $n$+1 and $n$+2 (with the final coefficient 1 in the latter case). If $n$ is even, we can find an irrational number $x$ whose first $n$+1 continued fraction coefficients are the same as those of $z$. Then $X_n(x)=z$ and $z$ is a threshhold value, hence a fixed point. But we can also consider the continued fraction of length $n$+2 whose final coefficient is $1$. When we consider $R_{n+1}(y)$, with $y$ an irrational infinitesimally greater than $x$, we are in the situation described the last case examined above. Taking the limit as $y \rightarrow z$ we arrive at a threshhold value for which $R_{n+1}(z)=z$.

If $n$ is odd and $z=[a_0,\ldots,a_{n-1},a_n]$, we take an irrational number $x=[a_0,\ldots,a_{n-1},\underline{a_n-1},b_{n+1}']$ slightly larger than $z$. Then $X_n(x)=z$ and $z$ must be a threshhold value and a fixed point. We can also consider the continued fraction of length $n$+2 and final coefficient $1$ (now we are at the even case). We pick an irrational $x$ slightly larger than $z$ which has the same first $n$+2 coefficients as $z$, say $x=[a_0,\ldots,a_{n-1},a_n-1,1,b_{n+2}']$ for some irrational $b_{n+2}'$ (much) greater than 1. Then $X_{n+1}(x)=z$. \\

So every irrational number with continued fraction expansions of lengths $n$+1 and $n$+2 is a threshhold value (hence a fixed point) of $R_{n}$ and $R_{n+1}$. For reasons that will soon become apparent, these fixed points are somewhat special. We also want to show that if $z$ has continued fractions of lengths $n$+1 and $n$+2 then it is a fixed point of $R_m$ for any $m\geq n$+2. To this end we will show that $R_m(y)\rightarrow z$ as $y\rightarrow z$, $y$ irrational (from either side).

Let $z=[a_0,\ldots,a_n]$, $a_n\neq 1$. Suppose $n$ is even. Pick an irrational $y$ a little larger than $z$ such that $y=[a_0,\ldots,a_n,b_{n+1},\ldots,b_m,b_{m+1}']$, with $b_{m+1}'$ irrational greater than 1. We have $R_m(y)=[a_0,\ldots,a_n,b_{n+1},\ldots,b_m(+1)]$, where the $(+1)$ is used if $m$ is odd. As $y$ continuously approaches $z$, the first $n$+1 coefficients of $y$ cannot change, but the tail end $b_{n+1}'=[b_{n+1},\ldots]$ will go to infinity, since
\begin{equation*}
\lim_{y\rightarrow z^+} y = \lim_{b_{n+1}'\rightarrow \infty} [a_0,\ldots,a_n+\textstyle \frac{1}{b_{n+1}'}] = \lim_{b_{n+1}'\rightarrow \infty} [a_0,\ldots,a_n, b_{n+1}'].
\end{equation*}
Therefore, with $b=[b_{n+1},\ldots,b_m(+1)]$, $y\rightarrow z^+$ will imply that $b\rightarrow \infty$ (note that the (+1) cannot have any fundamental effect on the entire tail end going to infinity), and we will have
\begin{eqnarray}
\lim_{y\rightarrow z^+} R_m(y) &=& lim_{b\rightarrow \infty} [a_0,\ldots,a_n,b] \nonumber \\
&=& \lim_{b\rightarrow \infty} [a_0,\ldots,a_n+\textstyle \frac{1}{b}] \nonumber \\
&=& [a_0,\ldots,a_n] \nonumber \\
&=& z.
\end{eqnarray}
We can also look at the limit from the left. In this case, we pick $y$ a little less than $z$, of the form $y=[a_0,\ldots,a_n-1,b_{n+1}']$ so that the irrational tail end $b_{n+1}'$ is very close to $1^+$. This is the same as writing $y=[a_0,\ldots,a_n-1,1,b_{n+2}']$ with $b_{n+2}'$ irrational and tending to infinity. We will have $R_m(y)=[a_0,\ldots,a_n-1,1,\ldots,b_m(+1)]$ and
\begin{eqnarray*}
y\rightarrow z^- &\Rightarrow& b_{n+2}'\rightarrow \infty \\
&\Rightarrow& [b_{n+2},\ldots,b_m(+1)] \rightarrow \infty \; \protect\footnote{Possibly there is only one coefficient in that continued fraction.} \\
&\Rightarrow& R_m(y) \rightarrow [a_0,\ldots,a_n-1,1] \\
&&=z.
\end{eqnarray*}

We can also quickly consider the case of $n$ odd, $z=[a_0,\ldots,a_n]$ with $a_n\neq 1$. If we take $y$ a little larger than $z$, we have $y=[a_0,\ldots,a_n-1,1,b_{n+2}']$ with $b_{n+2}$ large irrational. Then $R_m(y)=[a_0,\ldots,a_n-1,1,b_{n+2},\ldots,b_m(+1)]$ (where perhaps $m=n$+2). Since $b_{n+2}'=[b_{n+2},\ldots]\rightarrow \infty$ implies $b=[b_{n+2},\ldots,b_m(+1)] \rightarrow \infty$ and the former occurs when $y\rightarrow z^+$,
\begin{eqnarray}
\lim_{y\rightarrow z^+} R_m(y) &=& \lim_{b\rightarrow \infty} [a_0,\ldots,a_n-1,1,b] \nonumber \\
&=& \lim_{b\rightarrow \infty} [a_0,\ldots,a_n-1,1+\frac{1}{b}] \nonumber \\
&=& [a_0,\ldots,a_n-1,1] \nonumber \\
&=& [a_0,\ldots,a_n] =z.
\end{eqnarray}
Likewise, we can take $y$ a little less than $z$, say $y=[a_0,\ldots,a_n,b_{n+1}']$, with $b_{n+1}'=[b_{n+1},\ldots]$ large and irrational. Then $y\rightarrow z^-$ corresponds to $b_{n+1}'\rightarrow \infty$, which implies $b=[b_{n+1},\ldots,b_m(+1)]\rightarrow \infty$, and
\begin{eqnarray}
\lim_{y\rightarrow z^-} R_m(y) &=& \lim_{b\rightarrow \infty} [a_0,\ldots,a_n,b] \nonumber \\
&=& \lim_{b\rightarrow \infty} [a_0,\ldots,a_n+\frac{1}{b}] \nonumber \\
&=& [a_0,\ldots,a_n] =z.
\end{eqnarray}

Combined with previous results, this establishes that $z$ is a fixed point of $R_n$ whenever its continued fraction can be written to have at most $n$+1 coefficients. One direction of the proposition is finished. Conversely, we would like to show that (given $n$) all the fixed points of $R_n$ are rational numbers whose continued fractions can be written to have at most $n$+1 coefficients. This is much easier. For suppose $z=[a_0,\ldots,a_{n+1}']$ with $a_{n+1}'$ some real number strictly greater than 1 (so $z$ is either irrational or rational with a continued fraction of at least $n$+2 coefficients). Then we know that $R_n(z)=[a_0,\ldots,a_n(+1)]$, a continued fraction of length $n$+1. And the only way this could equal $z$, a continued fraction of length $\geq n$+2, is if we have $a_{n+1}'=1$, which is not true. So $z$ cannot be a fixed point of $R_n$. $\diamondsuit$ \\ \\


Now consider Figure 3 in light of this proof (in fact this discussion is concerned with the plot in which $R_n(x)$ is drawn for \emph{all} $n$, but Figure 3 will do for a visual aid). We have essentially derived its entire structure. We showed that every threshhold value, as defined in the cases that were discussed,\footnote{essentially a point where $R_n$ has a jump discontinuity} is also a fixed point. Since the fixed points of $R_n$ are all the rational numbers whose continued fractions can be of length $\leq n$+1, these are the only numbers that can be threshhold values. But we also showed that if $z$ has a continued fraction of length $\leq n$-1 then $\lim_{y\rightarrow z} R_n(y)=z$. So $R_n$ is continuous at such fixed points and they are not threshhold values. Therefore,
\begin{cor} \label{CfFig} Summary of threshhold values:
\begin{itemize}
\item The threshhold values of $R_n$ are precisely the rational numbers that have continued fractions of minimum lengths $n$ or $n$+1.
\item A rational number whose continued fraction has minimum length $n$+1 is a threshhold value for $R_n$ and $R_{n+1}$.
\item If a number is a threshhold value for $R_n$ but not for $R_{n-1}$ then its continued fraction has minimum length $n+1$.
\end{itemize} \end{cor}

Figure 3 is entirely characterized by the threshhold values of the $R_n$ and the magnitudes of the jump discontinuities that occur, since the $R_n$ are otherwise constant functions. Let an $n$-triangle refer to a triangle drawn by $R_n$. Note how the last case discussed in the section on threshholds, $n$ odd and $X=[a_0,\ldots,a_{n-1},1]$, corresponds to $R_n$ approaching\footnote{``approaching'' as in not being a horizontal line up to the diagonal but actually approaching it through infinitely many infinitesimally small triangles} the diagonal as it moves leftwards towards the lower corner of an ($n$-1)-triangle and then jumping down at the beginning of the next ($n$-1)-triangle. We can also see that the case $n$ even, $X=[a_0,\ldots,a_{n-1},1]$, corresponds to $R_n$ smoothly approaching the diagonal as it moves rightwards towards the upper corner of an ($n$-1)-triangle and then being constant in the next ($n$-1)-triangle.\footnote{If we define threshholds as jump discontinuities, this isn't technically a threshhold; but it makes sense to call it one and inner consistency is preserved if we do.} The other two cases, where $X=[a_0,\ldots,a_n]$ and $a_n\neq 1$ for $n$ even or odd, correspond to $R_n$ being constant (leftwards) up to the diagonal and then jumping to another constant value.

That each rational number is also a threshhold value for exactly two $R_k$ can also be seen in Figure 3 for a few threshold values with short continued fractions. If $X=[a_0,\ldots,a_n]=[a_0,\ldots,a_n-1,1]$ and $n$ is even, then going leftwards $R_n$ jumps from $[a_0,\ldots,a_n]$ to $[a_0,\ldots,a_n-1]$ and $R_{n+1}$ approaches horizontally and leaves in infinitesimally small triangles. Note that in this case we can also see that moving rightwards from the threshhold $R_n$ will jump to $[a_0,\ldots,a_n+1]$ at $[a_0,\ldots,a_n+1]$ while $R_{n+1}$ will jump much sooner, to $[[a_0,\ldots,a_n-1,2]$ at $[a_0,\ldots,a_n-1,2]$. If $n$ is odd then the situation is essentially reversed. Moving leftwards, $R_n$ approaches horizontally and jumps from $[a_0,\ldots,a_n]$ down to $[a_0,\ldots,a_n+1]$, while $R_{n+1}$ approaches in infinitesimally small triangles and jumps much less to $[a_0,\ldots,a_n-1,2]$.

This should explain much of what is going on in the plot. And now Figure 3 itself can tell us about the location of rational numbers with continued fractions of certain minumum lengths. By considering the third part of Corrolary \ref{CfFig}, we immediately see that the only numbers that have minimum continued fractions of length 2 are of the form $1/n$,\footnote{We are of course looking at everything (mod 1). By now it should be more than clear why we can do this.} with $m$ an integer. To actually prove this, we can use the fact that the right threshhold of the 0-triangle (the entire section below the diagonal) is $[1]=[0,1]$. To get the first ``1-threshhold'', we add 1 to the last continued fraction digit to get $[0,2]=1/2$. We continue in this way and get that $[0,n]=1/n$ is a threshhold of $R_1$ (but not of ``$R_0$'', the outline of the 0-triangle) for all $n\geq 2$. Since these are the only numbers generated and cover the entire interval they are the only numbers with continued fractions of minimum length 2 (yes, this is a rather obvious conclusion).

We can then find the numbers with continued fractions of minimum length 3 simply by looking at $R_2$. To actually find their formulas, we note that 2 is even\footnote{surprise!} and that the left threshholds of all the 1-triangles are of the form $[0,n]=[0,n-1,1]$, $n\geq 2$. So we move rightwards from each of these threshholds and find numbers with continued fractions of minimum length 3 are of the form
\begin{equation} [0,n-1,m]=\frac{m}{(n-1)m+1} \end{equation}
for $n,m\geq 2$. Continuing this way, we get that all numbers with continued fractions of minimum length $k+1$ are of the form
\begin{equation} [0,n_1,n_2,\ldots,n_k], \end{equation}
with $n_k \geq 2 $ and $n_i \geq 1 \; \forall i\neq k$. This is of course entirely obvious, just by a consideration of what the continued fraction coefficients could be. But it is very nice that we got this conclusion from the graph. And it is even more exciting that we can now visualize the locations of the numbers with continued fractions of a certain minimum length--we can think of their coefficients as indices describing which 1-triangle, 2-triangle, etc they belong to! For example, [0,2,3,1,5] is in the 2nd 1-triangle from the right, the 3rd 2-triangle from the left inside that 1-triangle, and the 1st 3-triangle from the right inside that 2-triangle. Inside the 3-triangle, it is the 4th 4-threshhold from the left. %This is very cool!

Now let's return to probabilities. \label{vissection}

\subsubsection{Improved probability bounds}

\begin{prop} \label{improvedprob} Given a point ($\xi-\fxi,r-\fxi$) randomly distributed below the diagonal of the unit square, the probability that the algorithm will fail is bounded by
\begin{equation*} 0.7101 \leq P(failure) \leq  0.7609. \end{equation*}
This of course implies that the probability of success is bounded by
\begin{equation*} 0.2391 \leq P(success) \leq 0.2899. \end{equation*}
\end{prop}

\emph{Proof.} For the \emph{exact} probabilities, we would consider $R_n(x)$ for all $n$. Recall that if $n$ is odd than points $(x,y)$ below $R_n(x)$ but above any other $R_m(x)$ with $m<n$ correspond to definite failure of the algorithm with $\xi-\fxi=x$ and $r-\fxi=r$ (as usual, we consider everything (mod 1)). Likewise, if $n$ is even, such points correspond to definite success of the algorithm. Note that defining $R_0(x)\equiv 0$ goes along with this--if a point is below $R_0$ than ($3''$) is no longer violated. Looking at the interval (0,1), i.e. a plot such as Figure 3, the probability of failure is 2 times the area of the regions of definite failure and the probability of success is 2 times the area of the regions of definite success. We multiply by two because we are for the moment ignoring the top half (triangle) of the graph; we assumes that the root $r$ violates ($3''$), so it is definitely located on the bottom half of the graph.

Though at the moment we are not going to find exact probabilities, we can imagine how we would go about doing so. We can find a lower bound on probability of failure from the $R_1$, a lower bound on probability of success from $R_2$, and so on. Since lower bounds for success correspond to upper bounds for failure, we would get two sequences, $\{P_n(failure)\}$ and $\{1-P_n(success)\}$, that converge monotonically to the same limit from below and above. This limit is of course the exact probability of failure.

For the first probability of failure, we can subdivide the are under $R_1$ (see Figure 1) into rectangles. Since we know the fixed points are at $1/n$, $n$ is an integer, the area we want is
\begin{eqnarray}
P_1(failure)&=& 2 \left[ \sum base \times height \right] \nonumber \\
&=& 2 \left[ \frac{1}{2} \left( \frac{1}{2} \right) + \left( \frac{1}{2}-\frac{1}{3} \right) \left( \frac{1}{3} \right) + \left( \frac{1}{3}-\frac{1}{4} \right) \left( \frac{1}{4} \right) + \cdots \right] \nonumber \\
&=& 2 \sum_{n=1}^{\infty} \left( \frac{1}{n}-\frac{1}{n+1} \right) \left( \frac{1}{n+1} \right) \nonumber \\
&=& 2 \left[ \sum_{n=1}^{\infty} \frac{1}{n(n+1)} - \sum_{n=1}^{\infty} \frac{1}{(n+1)^2} \right] \nonumber \\
&=& 2 \left[ \sum_{n=1}^{\infty} \left( \frac{1}{n} - \frac{1}{n+1} \right) - \left( \frac{\pi^2}{6}-1 \right) \right] \nonumber \\
&=& 2 \left( 2-\frac{\pi^2}{6} \right) = 4-\frac{\pi^2}{3} \\
&\approx& 0.7101 \; . \nonumber
\end{eqnarray}

Now we want the first bound on the probability of success, twice the area between $R_2$ and $R_1$. We know the fixed points are $m/((n-1)m+1)$ for integral $m,n$. In the ($n$-1)st 1-triangle, the area is
\begin{eqnarray}
A^2_n &=& \sum [base \times height] \nonumber \\
&=& \sum_{m=2}^{\infty} \left( \frac{m+1}{(n-1)(m+1)+1}-\frac{m}{(n-1)m+1} \right) \left( \frac{m}{(n-1)m+1} - \frac{1}{n} \right) \nonumber \\
&=& \sum_{m=2}^{\infty} \frac{m-1}{n((n-1)m+1)^2(m(n-1)+n)}, \label{r2lesssum}
\end{eqnarray}
so that
\begin{equation*} P_2(success)=2 \sum_{n=1}^{\infty} A^2_n. \end{equation*}
Since we know what the area under $R_1$ is, we could also just calculate the are under $R_2$ and subtract that under $R_1$:
\begin{eqnarray*}
Area \; under \; R_2 &=& \sum_{n=2}^{\infty} \sum_{m=1}^{\infty} \left( \frac{m+1}{(n-1)(m+1)+1}-\frac{m}{(n-1)m+1} \right) \left( \frac{m}{(n-1)m+1} \right) \\
&=& \sum_{n=2}^{\infty} \sum_{m=2}^{\infty} \frac{m}{((n-1)m+1)^2(m(n-1)+n)}, \\
P_2(success)&=&2 \left[ \sum_{n=2}^{\infty} \sum_{m=2}^{\infty} \frac{m}{((n-1)m+1)^2(m(n-1)+n)} -\left(2-\frac{\pi^2}{6} \right) \right].
\end{eqnarray*}
Unfortunately, there seems to be no easy way to explicitly evaluate this sum. Looking at what the terms refer to in the plot, we might expect the sum to converge fairly quickly. Unfortunately, this is not the case. A glance at the summand shows it is on the order of $1/m$. And if we call the summand in \eqref{r2lesssum} $C(n,m)$, we have
\begin{eqnarray*}
\sum_{n=2}^{25} \sum_{m=2}^{25} C(m,n) &\approx& 0.1008 \\
\sum_{n=2}^{50} \sum_{m=2}^{25} C(m,n) &\approx& 0.1102 \\
\sum_{n=2}^{100} \sum_{m=2}^{100} C(m,n) &\approx& 0.1153 \\
\sum_{n=2}^{200} \sum_{m=2}^{200} C(m,n) &\approx& 0.1179,
\end{eqnarray*}
which shows that the tail end is still contributing significantly. \emph{Mathematica} will not evaluate the infinite sum numerically. (Though we do know that the sum must \emph{somehow} converge, since it is bounded from above--it can only be a finite area.) The best result that could be achieved in a reasonable calculating time\footnote{about 2 hours on my PC} was
\begin{equation*} \sum_{n=2}^{500} \sum_{m=2}^{500} C(m,n) \approx 0.1196. \end{equation*} We might try to integrate $R_2(x)$ using \emph{Mathematica}'s numerical integration algorithms, which give
\begin{equation*} \int_0^1 R_2(x)\, dx - \left(2-\frac{\pi^2}{6}\right)\approx 0.1207,\end{equation*} but which also produced quite a few integral convergence errors.\footnote{Though I believe the integration route is in fact decently accurate, and certainly a better way to go than approximating the sums.}

Using the sum from 2 to 500, we know that $P_2$(success) $\geq 2*0.1196 = 0.2392$, which, combined with the result from $R_1$, gives us the bounds
\begin{equation} \label{failurebound}
0.7101 \leq P(failure) \leq 1- 0.2392 = 0.7609, \end{equation}
the assertion of the Proposition. $\diamondsuit$ \\

Achieving better bounds is on one hand straightforward--we can always write out the sum--and on the other hand very difficult because the resulting sums cannot be easily evaluated. By using \emph{Mathematica} to integrate the first ten $R_n$, we obtained the following \emph{estimate}\footnote{\emph{Mathematica}'s integration algorithms cannot actually prove anything!}:
\begin{eqnarray}
0.7498 < P(failure)< 0.7499 &or& P(failure) \approx 0.750 \\
0.2500< P(success) <0.2502 &or& P(success) \approx 0.250
\end{eqnarray}
These numbers are tantalizingly close to 1/4 and 3/4, so we might say that

\begin{conj} \label{exactprob} \label{probconj} $P(failure) = 3/4$ and $P(success)=1/4$.
\end{conj}
It would be great if this were actually proven.\footnote{In fact, see Section \ref{exactprobproof} for a proof, done later.}

Note that all these calculations can be found and rerun at the bottom of the notebook \textsf{rless.nb}.

Also note that we know now that the interiors of each (even or odd) triangle all have the same structure but no two are similar in the strict sense of the word. This was not actually proved explicitly, but when we consider the general form of threshhold values of $R_n$ (i.e., the general form of a continued fraction of length $n$+1), we see that there are no factors of previous indices that can be factored out. (This answers a question asked right before section \ref{visual})



\subsubsection{Other roots}

We have spent a good deal of effort investigating success and failure of the algorithm as a function of a \emph{single} root $r$ of the polynomial less than the sought root $\xi$. The situation is not greatly complicated by multiple roots less than $\xi$ which violate ($3''$). Each one individually must satisfy all the conditions mentioned previously--i.e. each one must be in a region of success on the plot in order for the algorithm to succeed. Using the results of Proposition \ref{improvedprob}, we can say that for $k$ roots that violate ($3''$) we will have
\begin{eqnarray}
&(0.2391)^k \leq P^k(success) \leq (0.2899)^k& \\
&1-(0.2899)^k \leq P^k(failure) \leq 1-(0.2391)^k.&
\end{eqnarray}

Of course we can also conjecture that
\begin{eqnarray}
& P^k(success)=(1/4)^k & \\
& P^k(failure)=1-(1/4)^k. &
\end{eqnarray}

We have also not discussed roots greater than the sought root $\xi$, i.e. roots for which ($4''$) is applicable. The calculations are almost identical to those used for roots that violate ($3''$), so for the most part they will be suppressed and various results will be given without complete (or any) proof.

Let $r$ be the only root of the polynomial greater than $\xi$. Let $x$=$\fxi$ and define $\xi_n$, $x_n$, and $r_n$ by equations \ref{defx} and \ref{defr}; note that we have $x_n=\xi_n$ for $n\geq1$. If ($4''$) is satisfied, we have definite success, and to satisfy ($4''$) we need
\begin{eqnarray*} &r_1 < \lfloor \xi_1 \rfloor& \\
&\Rightarrow r > \frac{1}{\lfloor \xi_1 \rfloor} + \fxi=[\fxi,\lfloor \xi_1 \rfloor].& \end{eqnarray*}
Therefore, we can define $Q_1(\xi)=[\fxi,\lfloor \xi_1 \rfloor]$ or
\begin{equation*} Q_1(x)=[\lfloor x \rfloor,\lfloor x_1 \rfloor]=[0,\lfloor x_1 \rfloor] \end{equation*} so that if $y=r-\fxi$ and $y>Q_1(x)$ we will have definite success.

We continue like this. For any odd $n$ we get
\begin{equation} Q_n(x)=[\lfloor x \rfloor,\lfloor x_1 \rfloor,\ldots,\lfloor x_n \rfloor]. \end{equation}
For any even $n$, we will have $r_n>x_n$. The condition for definite failure (given that all the previous conditions for definite success or failure have failed) will be $r_n>\lfloor x_n \rfloor +1$. Therefore, we get
\begin{equation} Q_n(x)=[\lfloor x \rfloor,\lfloor x_1 \rfloor,\ldots,\lfloor x_n \rfloor+1]. \end{equation} For definite failure in the even case, we must have $y>Q_n{x}$.
Notice that the exact opposite happens with the (+1) compared to the situation when $r$ was less than $\xi$.
The resulting plot\footnote{produced at the bottom of \textsf{rless.nb}} for the first five conditions appears in Figure \ref{rmorefig}. The conditions for $r$ less than $\xi$ are included below the diagonal in the bottom part.
\begin{figure}[!htp] \caption[rmore5]{r greater than $\xi$} \label{rmorefig} \begin{center}
\includegraphics[scale=.6]{rmore5}
\end{center} \end{figure}

All the results concerning the continued fraction expansion of $x$ and properties of the $R_n$ still hold for the $Q_n$. The proofs are almost identical, the main exception being that $Q_n(x)$, $x$ rational, is defined by $\lim_{y\rightarrow \underline{x^-}} Q_n(y)$. We have:

\begin{prop} The following results hold for $Q_n(x)$:
\begin{itemize}
\item $Q_n(x)=x$ if and only if the continued fraction expansion of $x$ has $\leq n$+1 coefficients
\item The set of numbers $x$ for which $Q_n(x)=x$ (for some $n$) is precisely the set of rational numbers
\item The threshhold values of $Q_n$ are precisely the rational numbers that have continued fractions of minimum lengths $n$ or $n$+1.
\item A rational number whose continued fraction has minimum length $n$+1 is a threshhold value for $Q_n$ and $Q_{n+1}$.
\item If a number is a threshhold value for $Q_n$ but not for $Q_{n-1}$ then its continued fraction has minimum length $n+1$.
\end{itemize} \end{prop}
And the $Q_n$ can be used to visualize the continued fraction expansion of rational numbers the same way as the $R_n$.

The plot of the $Q_n$ indicates that the $Q_n$ are in a sense inverse functions of the $R_n$, their reflections across the diagonal. This in fact follows from the fact that $Q_n$ and $R_n$ have the same threshhold values and all the threshhold values are fixed points. In a given step, $R_n$ must start at the diagonal (say the point ($x_0,x_0$)) and move (horizontally) to the right until it jumps up to the next step, which also starts at the diagonal. So the length of the jump is equal to the length of the step. But $Q_n$ has a fixed point at the jump since it has the same fixed points as $R_n$; and from there $Q_n$ moves horizontally to the left (note the different definition of $Q_n(x)$ for rational $x$) until it jumps down to its next step. But this jump must occur at the first threshhold value $Q_n$ hits, and since its threshhold values are the same as those of $R_n$ it must jump at $x_0$ and we are back where we started. Since all the threshhold values of $Q_n$ are fixed points, the length of this jump must have been the length of the step--equal to the length of the step and jump of $R_n$. We have traced out a square and shown that $Q_n$ must be the reflection or $R_n$. \\

As far as probabilities are concerned, there is definite success above every odd $Q_n$ (but below all the others) and definite failure above every even $Q_n$ (below all the others). In a sense we can say that success and failure invert when they are reflected across the diagonal. Therefore, given a point ($x,y$)=($\xi-\fxi,r-\fxi$) randomly distributed above the diagonal of the unit square, the bound on probability for success and failure of the algorithm are exactly the opposite of the bounds for a point below the diagonal. Hence we know
\begin{eqnarray}
& 0.7101 \leq P(success) \leq  0.7609 & \\
& 0.2391 \leq P(failure) \leq 0.2899&
\end{eqnarray}
and we can conjecture that
\begin{equation}
P(success) = 3/4,\quad P(failure) = 1/4.
\end{equation}

Given $k$ points randomly distributed in the unit square--essentially $k$ roots distributed\footnote{Perhaps not entirely randomly? Not completely sure at the moment.} in the interval [$\fxi,\fxi$+1)--we simply combine the results of $R_n$ and $Q_n$ to get bounds for probabilities of success and failure. For example, the conjectured probability values would predict\footnote{check this...}
\begin{eqnarray}
P(success) &=& \frac{1}{2^k}\Bigg[ \left( \frac{3}{4}\right)^k + {k \choose k-1} \left[ \left( \frac{3}{4}\right)^{k-1}+\left(\frac{1}{4}\right)^1 \right] + \cdots \nonumber \\
&&+ {k \choose 0} \left( \frac{1}{4}\right)^k \Bigg] \\
&&P(failure)=1-P(success). \nonumber
\end{eqnarray}

As a final remark, we now know there is no way to reformulate ($3''$) and ($4''$) to make them sufficient \emph{and} necessary for success of the agorithm.

\subsection{A possible practical fix}

We have shown in quite some detail that the Lang-Trotter algorithm will not work on any given irrational root of a random polynomial--the other roots surrounding it are always a potential problem. But why, for practical purposes, could we not adjust the initial polynomial $p_0(x)$ so that it satisfied ($3''$) and ($4''$), which \emph{are} sufficient for success?

Two solutions immediately come to mind. We might scale the polynomial $p_0(x)$ so that there are no other roots within an integer of the sought root $\xi$. To see how this would work, let $\{ r_j\}$ be the roots of $p_0(x)$ not equal to $\xi$ and take $\delta = \min |\xi-r_j|$. Since the roots of the polynomial $\tilde{p}_0(x)=p_0(\frac{x}{a})$ are $a$ times the roots of $p_0(x)$, the spacings between the roots of this scaled polynomial will be $a$ times the spacings of the roots of $p_0(x)$. If we take any $a>\frac{1}{\delta}$, the minimum spacing in $\tilde{p}_0(x)$ will be $a\delta>1$, and the polynomial will satisfy ($3'$).

Another, slightly trickier, solution is to shift (translate) $p_0(x)$ by some number $b$. The roots of $\hat{p}_0(x)=p_0(x+b)$ are the roots of $p_0(x)$ minus $b$. If ($3''$) and ($4''$) are not satisfied, there is no way to pick a $b$ to satisfy ($3'$); so the best we can hope for is a $b$ that satisfies ($3''$) and ($4''$). Let $r_1$ and $r_2$, $r_1<\xi<r_2$, be the roots of $p_0(x)$ closest to $\xi$. (Certainly one or the other may not exist, in which case they can be removed from the following argument.)
Since we are essentially looking at things mod 1, we may assume that $\lfloor \xi \rfloor$ doesn't change; so 
\begin{equation} b<\xi-\lfloor \xi \rfloor. \label{fix00} \end{equation}
To satisfy ($3''$), we need $r_1 < \lfloor \xi \rfloor$. If ($3''$) is already satisfied, there is no problem; but if not we want to pick a $b$ such that
\begin{eqnarray}
r_1-b &<& \lfloor \xi-b \rfloor = \lfloor \xi \rfloor \nonumber \\
\Rightarrow b &>& r_1-\lfloor \xi \rfloor. \label{fix3}
\end{eqnarray}

We also want to satisfy ($4''$), for which we need
\begin{equation} \label{shiftfix4}
\frac{1}{(r_2-b)-\lfloor \xi \rfloor} < \lfloor \frac{1}{(\xi-b)-\lfloor \xi \rfloor} \rfloor.
\end{equation}
As $b$ approaches $\xi-\fxi$, the RHS goes to infinity while the left hand side remains finite, so finding a $b$ that satisfies \eqref{shiftfix4} is always possible. Our problem, then, is finding the loosest possible constraint on $b$ that will ensure \eqref{shiftfix4}; unfortunately, since $b$ is inside the greatest integer function on the RHS, there is no simple solution. Three sufficient lower bounds on $b$ will thus be given. Let $\rho=r_2-\lfloor \xi \rfloor$ and $x=\xi-\lfloor \xi \rfloor$. If $b>0$ (which will be the case if we need to satisfy ($3''$)) then $0<\rho-b<1$ and it will be sufficient to satisfy
\begin{eqnarray} \frac{1}{x-b}&>&\frac{2}{\rho-b} \nonumber \\
\Rightarrow \rho-b&>&2x-2b \nonumber \\
\Rightarrow b&>&2x-\rho \nonumber \\
\Rightarrow b&>&2\xi-r_2-\fxi. \label{fix41}
\end{eqnarray}

For a better (though still not exact) bound we could also take
\begin{eqnarray*}
\frac{1}{x-b}&>& \frac{1}{\rho-b}+1 \\
\Rightarrow b^2-(x+\rho)b+x\rho+x-\rho&<&0
\end{eqnarray*}
Since the leading coefficient of this quadratic is positive, in the solution we must have $b$ between the two roots, which are
\begin{equation*}
b=\frac{\rho+x \pm \sqrt{(\rho-x)^2+4(\rho-x)}}{2}.
\end{equation*}
Taking into account the constraint in \eqref{fix00}, this condition reduces to
\begin{eqnarray}
b &>& \frac{\rho+x - \sqrt{(\rho-x)^2+4(\rho-x)}}{2} \nonumber \\
\Rightarrow b &>& \frac{\xi+r_2-2\fxi - \sqrt{(r_2-\xi)^2+4(r_2-\xi)}}{2} \label{fix42}
\end{eqnarray}
While this \emph{is} a looser constraint on $b$, the first constraint is much nicer to work with.

As a final option, consider the fact that if $b>0$ we will have $x-b<x$, so that $\lfloor \frac{1}{x} \rfloor \leq \lfloor \frac{1}{x-b} \rfloor$. Then to satisfy \eqref{shiftfix4} it suffices to have
\begin{eqnarray}
\frac{1}{\rho-b} &<& \left\lfloor \frac{1}{x} \right\rfloor \nonumber \\
\Rightarrow b &<& \rho-\left\lfloor \frac{1}{x} \right\rfloor^{-1} \nonumber \\
&=& \rho -Q_1(x) \nonumber \\
&=& r_2-\fxi - \left\lfloor \frac{1}{\xi-\fxi} \right\rfloor^{-1}.
\end{eqnarray}
Unfortunately, as can be seen from the definition in terms of $Q_1$, this condition may force $b$ to be negative, thereby contradicting itself. We will therefore focus on the first two conditions for the time being.

To summarize our results for shifts by $-b$:
\begin{center}
\begin{tabular}{|c|c|} \hline
General constraint & $b<\xi-\fxi$ \\ \hline \hline
($3''$) violated, $r_1  \geq \fxi$ & $b > r_1-\fxi$ \\ \hline 
($4''$) violated, $ \frac{1}{r_2 - \fxi} \geq \lfloor \frac{1}{\xi-\fxi} \rfloor$ & $b > \frac{1}{2} \left( \xi + r_2 - 2\fxi - \sqrt{(r_2-\xi)^2+4(r_2-\xi)}\right)$ \\ \hline
($4''$) violated and $b>0$ & $b > 2\xi-r_2-\fxi$ \\ \hline
\end{tabular}
\end{center}

We should check that these constraints are always (jointly) attainable. If the only problematic roots are less than $\xi$, we can certainly have both \eqref{fix00} and \eqref{fix3}, since we have $\fxi<r_1<\xi$. Now suppose the only problematic roots are greater than $\xi$ and \eqref{fix00} holds. Then 
we have (with $r=r_2-\fxi$)
\begin{eqnarray*}
&(r-x)^2+4(r-x) > (r-x)^2& \\
&\Rightarrow \sqrt{(r-x)^2+4(r-x)} > r-x& \\
&\Rightarrow r-\sqrt{(r-x)^2+4(r-x)} < x& \\
&\Rightarrow x+r-\sqrt{(r-x)^2+4(r-x)} < 2x& \\
&\Rightarrow 1/2\big(x+r-\sqrt{(r-x)^2+4(r-x)}\big) < x,&
\end{eqnarray*}
so we will always be able to apply \eqref{fix42} in conjunction with \eqref{fix00}. And since we have $x>0$ and $r>x$ $\Rightarrow$ $2x-r<x$ we see that we will also be able to apply either $b>0$ or \eqref{fix41}, whichever is more restrictive, in conjunction with \eqref{fix00}. Finally, suppose that there are problematic roots on both sides of $\xi$. Then the condition on $b$ is simply a combination of \eqref{fix3} and either \eqref{fix41} or \eqref{fix42}. Since all of these additional conditions bound $b$ from below and we can apply all of them individually, we can apply all of them together. \\

\subsubsection{Adding and multiplying continued fractions}

Now we know that either scaling or a shift will ``fix'' a polynomial so that we can use the algorithm on an \emph{adjusted} root $\tilde{\xi}$. But is this truly useful? The answer depend on what we need the continued fraction expansion of $\xi$ for. If need to be able to write $\xi$ to very high accuracy (i.e. the accuracy given by a great deal of continued fraction coefficients) than transforming the polynomial is not much of a problem. Scaling might be slightly awkward, since we would find the expansion of $\tilde{\xi}=a\xi$ and then have to divide by $a$; but a translation by a rational number would not be bad at all--we would just $b$ to the accurate expression of $\tilde{\xi}$.

On the other hand, what if we actually need the exact continued fraction coefficients of $\xi$, say for a statistical analysis or some other test--can we get them back? Just how significantly will multiplying by or adding a constant affect a continued fraction? Multiplying or adding continued fractions is very difficult and entirely nontrivial; no general answer to the question is known. Multiplying or shifting by a rational number seems somewhat less disastrous than multiplying or shifting by an irrational, though both might cause irrepairable damage. In the case of a root of a quadratic, we can say that multiplying or translating by a rational will still give a root of a quadratic, so the resulting continued fraction will still be periodic; yet it is unclear how to directly get one continued fraction from the other or how the period will change. And what if we have a number like $e$, with a very nice linearly periodic continued fraction.\footnote{$e=[2,1,2,1,1,4,1,1,6,1,1,...]=[2,\overline{1,2n,1}]$} What will happen to the continued fraction of $e+1/2$?

Thus arose the question of rational shifts or scaling of continued fractions, the topic which we shall pursue for the remainder of this paper now that we have put to rest most of the burning questions about the Lang-Trotter algorithm. In fact, we shall limit ourselves to the effects of rational multiplication and translation of linearly periodic continued fractions (and then primarily the latter) since such a nice family seems an excellent place to begin an investigation.


\section{Linearly Periodic Continued Fractions}

It turns out that $e+1/2$ also has a linearly periodic continued fraction which is just slightly more complex than the one for $e$. In fact, it seems that any linearly periodic continued fraction retains its linear periodicity under a rational scaling or shift, though no proof of this has yet been found. In order to actually quantify effects observed, we shall need to say a bit more about linearly periodic continued fractions in general.

\subsection{More terminology}
Since we shall be discussing linearly periodic continued fractions a great deal and the name is quite lengthy, they shall be referred to as LPCF's from here on.

Recall equation \ref{lpcf}, which defined an LPCF to be of the form
\begin{equation} \label{lpcf2} [a_0,\ldots,a_{l-1},\overline{f_1(n),f_{2}(n),\ldots,f_{j}(n)} ],\qquad n=1,2,3,\ldots.
\end{equation}
For each $f_i$ we have $f_i(n)=b_i n + c_i$, with $b_i$ and $c_i$ integers and $c_i>-b_i$. If all the $b_i$ are zero, than the continued fraction is an ordinary periodic one.

The \textbf{introductory sequence} of the LPCF in \eqref{lpcf2} is $(a_0,\ldots,a_{l-1})$ and has length $l$. In an LPCF, the introductory sequence is chosen to be as short as possible--it is the shortest possible sequence that cannot be included in the periodic rule.

The \textbf{period length} of the LPCF is $j$. Within the periodic sequence $(f_1(n),$ $f_{2}(n),\ldots,f_{j}(n))$, we find two kinds of functions, $f_i$ with $b_i=0$ and $f_i$ with $b_i\neq0$. The former form the \textbf{base} or base sequence of the LPCF, which can simply be written as $(c_{i_1},c_{i_2},\ldots,c_{i_m})$, where $m$ is the length of the base sequence. The latter form the \textbf{diagonals} of the LPCF. There is one diagonal for every unique value of $b_i\neq0$, and $b_i$ is called the slope of that diagonal (corresponding to how much the diagonal will increase per period). We can then talk about the length or number of points in a diagonal of slope $b$ as the number of $f_i$ with $b_i=b$. The \textbf{displacement} of these points is $c_i$. The diagonal with the lowest slope may often be referred to as the ``first diagonal'' or the ``base diagonal.''

Let's consider an example,
\begin{eqnarray*} &\tan (1)+1/2=[2,17,2,\overline{2,1,3n-2,2,12n-2,}&\\
& \qquad \qquad \overline{2,3n-1,1,2,1,3n-1,1,48n+48,1,3n,1}].&
\end{eqnarray*}
The introductory sequence has length 3 and the period length is 16. The base sequence is$(2,1,2,2,1,2,1,1,1,1)$. There are three diagonals, of slopes 3, 12, and 48. The first diagonal has four points (with displacements -2,-1,-1, and 0) and the other two have one point each.

\subsection{A set of measure 0}
By the results of the first section, we know that every LPCF is irrational, since every LPCF is infinite. So the LPCF's are a subset of the irrational numbers. But we also know that no LPCF will satisfy Kuzmin's Theorem, so in fact this set must have measure zero (is countably infinite). Here we give a much better proof that
\begin{prop}The set of linearly periodic continued fractions has measure zero. \end{prop}

\emph{Proof.} First, note that the direct product of a finite number of countable infinite sets is also countable infinite. To see this, let $S_1,\ldots,S_n$ countable infinite sets and enumerate their elements: $S_i=\{s^i_1,s^i_2,\ldots\}$. Then there is a 1-1 correspondence between elements of $S=S_1 \times \cdots \times S_n$ and lattice points with positive coordinates of $n$-dimensional Euclidean space, namely
\begin{equation*} (s^1_{a_1},s^2_{a_2},\ldots,s^n_{a_n}) \longleftrightarrow (a_1,a_2,\ldots,a_n). \end{equation*}
We can then count the elements $s$ of $S$ by first counting the finite number of elements with $|s|\leq1$, then those with $1<|s|\leq2$, and so on. Thus, $S$ is an infinitely countable set.

Also note that the union of finitely many countable sets is again countable. For if we set $S=\cup_{i=1}^{n}S_i$ with the $S_i$ countable and enumerate the elements of the $S_i$ as $\{a^i_1,a^i_2,\ldots\}$, we can count the elements of $S$ by first counting the $n$ $a^1_1,\ldots,a^n_1$ then the $n$ $a^1_2,\ldots,a^n_2$, and so on.

Now, an LPCF of introductory length $l$ and period $j$ has at most $l+2j$ parameters to be determined, namely $a_0,a_1,\ldots,a_{l-1}$, $b_1,\ldots,b_j$, and $c_1,\ldots,c_j$. Each of these parameters must be an integer, so the sets of possible $a_0$, etc, are all countably infinite, which implies that the set of continued fractions of introductory length $l$ and period $j$ is countable. Then if we pick an integer $m$ and consider all LPCF's with $l+j=m$ we see that this must also be a countable set, since it is the finite union of countable sets (i.e. $l$=0 and $j$=$m$, $l$=1 and $j$=$m$-1,\ldots,$l$=$m$ and $j$=0). And the set of all LPCF's with $l+j\leq m$ is a finite union of the sets with $l+j=m$ so it must be a countably infinite set. Since this is valid for all $m$, we can say that the set of all possible LPCF's is countably infinite. If this argument seems questionable, consider the fact that the set with $l+j\leq m+1$ has the same measure as the set with $l+j\leq m$. Of course we cannot extend this to $m=\infty$, and we wouldn't want to--we would then be proving that the real numbers are countable.

\subsection{Rational and quadratic numbers}
Our observations (and a few provable results) begin with two subsets of the LPCF's. If we allow the period of an LPCF to be 0, then the rational numbers are the subset with 0 period. What happens when we shift or scale rational number? If we shift or scale by another rational, than the result will be rational and we will get a continued fraction of some finite length. Just \emph{how} the length changes is quite another question. We would expect that if a rational $r$ was shifted or scaled by $m/n$, the length of the ensuing continued fraction would (most of the time) be an increasing function of $n$. For a large $n$ will produce a rational with a large denominator, necessitating a long continued fraction. Moreover, we might expect the ensuing length to be essentially independent of $m$, since it is the denominator that determines the ``precision'' of a continued fraction.

\textbf{insert guesses \& tests of the function}

If the period of an LPCF is strictly positive but there are no diagonals, then the LPCF is an ordinary periodic continued fraction, hence an irrational root of a quadratic, say $f(x)$. And if we scale or shift this root by a rational, it will be the root of a new quadratic, $f(x-m/n)$ or $f(x/a)$. So the transformed number will again have a periodic continued fraction. Now we again want to ask: how will the period change? In the case of shifts, it seems that the period changes just like it did in the rational case: it is an increasing function of $n$. Some supporting data are shown in --------. The case of scaling has not been investigated but we might expect similar results.


\subsection{Shifts of Tan(1)}
all we had time to investigate in any depth; and even then not much depth

\subsubsection{Effects on the period}
varies roughly as $n^{5/14}$

\subsubsection{Effects on the diagonals}
primes: 3 diagonals, slopes $4$, $4p^2$, $4p^4$\\

non-primes: much trickier, but get neat patterns that depend very directly on divisors


\subsubsection{Effects on the base sequence}
largest number is always $\leq n^2$ and almost always equal to $n^2$\\

tend to converge to Kuzmin probabilities (converge or fluctuate?)

\subsection{Other LPCF's}
- show a few things about $e$ \\
- shifts and scaling in general: shifts in ptic probably act like those of tan(1); compare to effects on rational and quadratic numbers \\
- great way to visualize things quickly: log-log graphs; include notebook \\ \\

There is much left to investigate \& many questions unanswered!


\section{Appendix}
\subsection{Proof of Conjucture \ref{exactprob}} \label{exactprobproof}

Consider the plot of the $R_n$, partially drawn in Figure 3. The total probability of failure is the area under $R_1$ plus the area between $R_2$ and $R_3$ plus\ldots. Likewise, the total probability of success is the area between $R_1$ and $R_2$ plus the area between $R_3$ and $R_4$ plus\ldots. But notice the apparent symmetry around $x=1/2$. It seems that the structure of the graph for $x < 1/2$ is reflected into the first 1-triangle ($x>1/2$). In the first 1-triangle, the lower boundary of this structure is $R_2$ while for $x<1/2$ the lower boundary is $R_1$. So \emph{if} the structure is reflected, all the success and failure regions are precisely inverted in the reflection. Therefore, we can imagine switching all the areas of success in the $x<1/2$ region with the corresponding areas of failure in the first 1-triangle. Then the 1-triangle has \emph{all} the areas of success and the remainder of the region below the diagonal has all the areas of failure. So certainly the total probability of failure is 3/4 and the total probability of success is 1/4.

For the proof, it is enough to establish the claimed symmetry. Considering the correlation between the $R_n$ and the continued fraction coefficients of rational numbers described at the end of Section \ref{vissection}, it is sufficient to show that we have
\begin{equation} 1-[0,1,a_2,a_3,\ldots]=[0,1+a_2,a_3,a_4,\ldots] \label{exactproof1} \end{equation}
for any continued fraction $[0,1,a_2,\ldots]$, or, equivalently, that
\begin{equation} 1-[0,a_1,a_2,\ldots]=[0,1,a_1-1,a_2,\ldots] \label{exactproof2} \end{equation}
for any continued fraction $[0,a_1,a_2,\ldots]$ with $a_1\neq1$. In the former, the LHS is the continued fraction representation of any number $1/2<x<1$ and the RHS is what we would like the continued fraction of its reflection about $1/2$ to be. The opposite is true in the latter. To establish \eqref{exactproof1}, note that the LHS can be written as
\begin{eqnarray*}
1-[0,1,a_2,a_3']&=&1-\frac{1}{1+\frac{1}{a_2+1/a_3'}} \\
&=&1-\frac{1}{1+\frac{a_3'}{a_2a_3'+1}} \\
&=&1-\frac{1}{\frac{a_2a_3'+1+a_3'}{a_2a_3'+1}} \\
&=&1-\frac{a_2a_3'+1}{a_2a_3'+1+a_3'} \\
&=&\frac{a_3'}{a_2a_3'+1+a_3'},
\end{eqnarray*}
and the RHS is
\begin{eqnarray*}
[0,1+a_2,a_3']&=&\frac{1}{1+a_2+\frac{1}{a_3'}} \\
&=&\frac{1}{\frac{a_3'+a_3'a_2+1}{a_3'}} \\
&=&\frac{a_3'}{a_3'+a_3'a_2+1},
\end{eqnarray*}
so the two sides are equal. Equation \ref{exactproof2} can obviously be established in a similar way.

Therefore, we can in fact say
\begin{thm} Given  polynomial with a root $\xi$ a single root $\fxi\leq r<\xi$ (and no roots $\xi<\rho<\fxi+1$) such that the point $(\xi-\fxi,r-\fxi)$ is randomly distributed below the diagonal of the unit square, the probability of success of the Lang-Trotter algorithm is 1/4 and the probability of failure is 3/4. \end{thm}

\subsection{Complete data for shifts of Tan(1)}
--

\subsection{Explanation of \emph{Mathematica} codes}
--

\begin{thebibliography}{99}
\bibitem{comput} R. P. Brent, A. J. van der Poorten, and H. J. J. te Riele. ``A Comparative Study of Algorithms for Computing Continued Fractions of Algebraic Numbers.'' \emph{Proceedings of the Second International Symposium on Algorithmic Number Theory}. Talence, France 1996.
\bibitem{kuzmin}A. Y. Khinchin, \emph{Continued Fractions}, Third
Edition, The University of Chicago Press, Chicago $1964$.
\bibitem{lang} S. Lang and H. Trotter. ``Continued fractions for some algebraic numbers.'' \emph{J. reine angew. Math.}, 225. 1972. p. 112-134.
\bibitem{class} R. Takloo-Bighash, S. J. Miller, H. Helfgott, and F. Spinu. Notes for Princeton Junior Seminar, Fall 2002: \emph{Diophantine Analysis and Roth's Theorem}. Princeton University 2002.
\end{thebibliography}
\end{document}
