\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}

\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}

\title{Continued fractions and the geometry of numbers}
\author{Burton Rosenberg}
\begin{document}
\maketitle

\subsection*{Introduction}

A continued fraction is an expansion of a number with certain relationship
to the euclidean algorithm. For a rational, it is exactly the euclidean algorithm.

{\em This is a work in progress:} the theory is not developed completely
to my liking. I will indicate, as much for my own future reference, where
the theory doesn't seem to hold together well.

Take a real $\alpha\ge 1$. Express it as integer and fractional part, 
$\alpha=\lfloor \alpha\rfloor + \alpha'$. If $\alpha'$ is not zero, its inverse
is greater than one. Write it $1/\alpha' = \lfloor\alpha\rfloor+\alpha''$, and so 
on.  If
the first integer part is $a_0$, the second is $a_1$, and so on, then,
\[
\alpha = a_0 +\frac{1}{a_1
     + \frac{1}{a_2
          +\frac{1}{a_3+ \ldots}
   }
}
\]
which we will write $\alpha=[a_0,a_1,a_2,\ldots]$.

For a rational $\alpha$ the continued fraction expansion is finite. The expansion
of $p/q$ follows the euclidean algorithm for $\gcd(p,q)$. From $p=a_0q+r$ we have
$p/q=a_0+r/q$, where $a_0$ is the integer part of $p/q$ and $r/q$ is the fractional
part. The next step of the algorithm gives $q/r=a_1+r'/r$, where $r'/r<1$.

For a expansion $[a_0,a_1,a_2,\ldots]$, the prefix expansions $p_i/q_i=[a_0,a_1,\ldots,a_i]$
are the convergents of the expansion.

\subsection*{Fundamentals}


At some point here there has to be a definition. The fractional linear transform
representation is not unique, and we talk about numbers resulting from a particular
computation. There needs to be ``computation invariant'' statements about
these numbers.

\begin{lemma}
Let $[a_0,a_1,\ldots,a_{i-1},\alpha]$ be a continued fraction, with the last entry a formal.
Then,
\[
[a_0,a_1,\ldots,a_{i-1},\alpha] = \frac{a\alpha+b}{c\alpha+d}
\]
with $a,b,c,d\in{\mathbb Z}$, non-negative, and $ad-bc=(-1)^i$.
\end{lemma}
       
{\bf Proof:} By induction. For $i=0$ verify $(1\cdot\alpha+0)/(0\cdot\alpha+1)$ 
satisfies the lemma. For $i>0$ we use the induction hypothesis on the
tail of the expansion.
\[
a_0+1/[a_1,\ldots,a_{i-1},\alpha] =a_0 +\left(\frac{a\alpha+b}{c\alpha+d}\right)^{-1}
= \frac{(a_0a+c)\alpha+a_0b+d
}{a\alpha+b}
\]
By various laws of determinates and the induction hypothesis,
\[
\det\left[\begin{array}{cc}a_0a+c&a_0b+d\\ a&b\end{array}\right]
=
-\det\left[\begin{array}{cc}a&b\\c&d\end{array}\right]=-(-1)^{i-1}
\]

Note that the modular determinate implies that $a$ and $b$ are
relatively prime, as are $c$ and $d$, as are $a$ and $c$, as well
as $b$ and $d$.

\begin{lemma}
For the continued fraction expansion,
\[[a_0,\ldots,a_{i-1},\alpha]=
\frac{p_{i-1}\alpha+p_{i-2}}{q_{i-1}\alpha+q_{i-2}}
\]
and,
\begin{eqnarray*}
p_{i} &=& p_{i-1}a_i+p_{i-2} \\
q_{i} &=& q_{i-1}a_i+q_{i-2}
\end{eqnarray*}
where $p_i/q_i$ is the $i$-th convergent (reduced to lowest terms).
\end{lemma}

{\bf Proof:}  Evaluate the form $(a\alpha+b)/(c\alpha+d)$
at $\alpha=0$. On the one hand this gives the convergent $p_{i-2}/q_{i-2}=
[a_0,\ldots,a_{i-2}]$ and on the other hand, the fraction $b/d$. Since
$b$ and $d$ are relatively prime,  $b=p_{i-2}$ and $d=q_{i-2}$.
Likewise, evaluation at $\alpha=\infty$ and consideration of relative
primality give $a=p_{i-1}$ and $b=q_{i-1}$.

Evaluation
at $\alpha=a_i$ gives $p_i/q_i=(p_{i-1}a_i+p_{i-2})/(q_{i-1}a_i+q_{i-2})$. 
To conclude that equality of ratios give actual equality of numerators and
denominators separately we need to show relative primality of the values
given by the linear forms in numerator and denominator.
From the previous lemma,
\[
p_{i-1}q_{i-2}-p_{i-2}q_{i-1}
=\det\left[\begin{array}{cc}
p_{i-1}&p_{i-2}\\ q_{i-1}&q_{i-2}\end{array}\right]
=\pm 1
\]
If numerator and denominator were not relatively prime then there would
be a prime $p$ such that $a_i$ is a solution to,
\[
 \left[\begin{array}{cc}
p_{i-1}&p_{i-2}\\ q_{i-1}&q_{i-2}\end{array}\right] 
\left[\begin{array}{c}x\\ 1 \end{array}\right] =\left[ 
\begin{array}{c} 0 \\ 0 \end{array}\right]
\pmod{p}
\]
which is impossible, since the matrix is invertible over ${\mathbb Z}_p$.


\begin{lemma}
The even convergents of $x$ are smaller
then $x$; the odd convergents are greater than $x$.
The error of a convergent $|x-p/q|$ is bound by $1/q^2$.
\end{lemma}

{\bf Proof:} 
Consider the continued fraction expansion and its fractional linear form
as a function of $\alpha$,
\[
f(\alpha) = [a_0, a_1,\ldots,a_{i},\alpha]
 = \frac{p_i\alpha+p_{i-1}}{q_i\alpha+q_{i-1}}
\]
Then,
\[
d f(\alpha)/d\alpha
= \frac{p_iq_{i-1}-p_{i-1}q_i}{(q_i\alpha+q_{i-1})^2}
\]
Hence $f$ is monotonic in $\alpha$, increasing or decreasing
depending on the sign of $p_iq_{i-1}-p_{i-1}q_i$.

Treating $f$ as a function, there is an $x'$ such that $x=f(x')$.
In fact, it will be the residual amount we are continuing each 
step in the evaluation of the $a_i$
So $f(0)=p_{i-1}/q_{i-1}$ and $f(\infty)=p_i/q_i$
will be on opposites sides of $x$.
Note that the 0-th covergent is simple $\lfloor x\rfloor$, so the
even convergents bound $x$ from below.

Furthermore the error of a convergent is bound by the
difference between it and its following convergent,
\[
\left| x-\frac{p_{i}}{q_{i}}\right| <
\left|
  \frac{p_i}{q_i}-\frac{p_{i+1}}{q_{i+1}}\right|
=
\left|
\frac{ p_iq_{i+1}-p_{i+1}q_i}{q_iq_{i+1}}\right|
=\frac{ 1}
{q_iq_{i+1}}<\frac{1}{q_{i}{}^2}
\]

This might be a proper place to establish the uniqueness of the continued
fraction representation, i.e. that distinct sequences of integers, when placed
as quotients in the continued fraction, give distinct reals.

\subsection*{The geometry of numbers}

Consider the lattice
${\mathbb Z}\times{\mathbb Z}$ in the real plane, that is, all points $(a,b)$ for integer
$a$ and $b$. The ratio $p/q$ is represented by the vector $(q,p)$, 
this vector has slope $p/q$.
To any number $\alpha$ the line through the origin with slope $\alpha$. The process
of continued fractions give a series of vectors with slope converging towards
$\alpha$. And they are constructed this way. 
\[
v_{i+1}=
  ({q_{i+1}},{p_{i+1}})=({q_ia_{i+1}+q_{i-1}},{p_ia_{i+1}+p_{i-1}})=
a_{i+1} v_i+v_{i-1}
\]
Geometrically speaking, recalling the alternation of approximations, beginning from 
$v_{i-1}$ which w.l.o.g. underestimates $\alpha$, we add multiples of $v_i$, which
consequently overestimates $\alpha$, until just before we pass through the line of
slope $\alpha$. This is the new convergent, $v_{i+1}$.

\subsection*{Approximation to any real}

We take this proof from Mika's book.

\begin{theorem}
Let $\alpha$ be a real, and $p/q$ a rational. If $ 0<|\alpha-p/q|\le 1/(2q^2)$ then $p/q$ is
a convergent of the continued fraction expansion of $\alpha$.
\end{theorem}

We first show a lemma: 

\begin{lemma}
Let $P, Q, P'$ and $Q'$ be integers such htat $Q>Q'>0$ and $PQ'-QP'=\pm 1$. We call
this last equality the determinate condition. If there
exists an $\alpha'\ge 1$ such that,
\[
\alpha = \frac{\alpha'P+P'}{\alpha'Q+Q'}
\]
then $P'/Q'$ and $P/Q$ are consecutive convergents in the continued fraction
expansion of $\alpha$.
\end{lemma}

{\bf Proof:}
Let $[a_0,\ldots, a_n]$ be the partial fraction expansion of $P/Q$. The determinate condition
implies that this fraction is in lowest terms and therefore $P=p_n$ and $Q=q_n$.
Therefore,
\[
p_nQ'-q_nP' = \pm 1 = \pm(p_nq_{n-1}-q_np_{n-1})
\]
We can manipulate the partial fraction expansion to be one longer or one shorter,
if necessary, to get the sign positive on the rightmost quantity.
\[
p_n(Q' -  q_{n-1}) = q_n(P'-p_{n-1})
\]
Again using relative primality, we have that $q_n|(Q'-q_{n-1})$. Since $q_n>Q',q_{n-1}>0$,
the difference must be less than $q_n$ and therefore zero. So $Q'-q_{n-1}$ and
consequently $P'=p_{n-1}$.
Hence we have,
\[
   \alpha = \frac{\alpha'p_n+p_{n-1}}{\alpha'q_n+q_{n-1}}
\]
Continue the expansion with $\alpha'=[a_{n+1},\ldots]$. The complete expansions of $\alpha$
therefore contains the desired convergents.

{\bf Proof (of theorem):} 
Expand $p/q=[a_0,\ldots,a_n]$. We may assume $p=p_n$ and $q=q_n$. Define,
\[
\alpha' = \frac{-\alpha q_{n-1}+p_{n-1}}{\alpha q_n-p_n}
\]
The inverse of a fractional linear transformation is again a fractional linear
transformation. In this case,
\[
\alpha = \frac{\alpha' p_n + p_{n-1}}{\alpha' q_n + q_{n-1}}
\]
So,
\[
\left|\frac{p_n}{q_n}-\alpha\right|
 =\left| \frac{p_n(\alpha' q_n+q_{n-1})-q_n(\alpha' p_n +p_{n-1})}
{q_n(\alpha'q_n+q_{n-1})}\right|
 =\left| \frac{\pm 1}{q_n(\alpha'q_n+q_{n-1})}\right| \le \frac{1}{2q_n{}^2}
\]
which implies,
\[
\alpha' \ge 2 - (q_{n-1}/q_n)>1
\]
So the lemma applies, and $p/q$ is a convergent of the expansion of $\alpha$.

\subsection*{Notes}

\begin{lemma}
Let $a,b\in{\mathbb Z}$ be relatively prime, and $s,t\in{\mathbb Z}$ be integers
such at $sa-tb=1$. Such integers are known to exist. Then all integer solutions to
$xa-yb=1$ are $\{\,(s+kb,t+ka)\,|\,k\in{\mathbb Z}\,\}$.
\end{lemma}

{\bf Proof:} If $sa-tb=s'a-t'b$ then $a(s-s')=b(t-t')$. So $b|(s-s')$ and $a|(t-t')$. Writing
$kb=s-s'$ and $k'a=t-t'$, we have $akb=bk'a$, so $k=k'$.

The notation $[a_0;a_1,\ldots]$ is preferable, since $a_i\in{\mathbb Z}^+$ for
$i>0$, and $a_0$ is zero only if the expansion is for a positive real less than one.

\begin{lemma}
The continued fraction $[a_0;a_1,\ldots,a_i,\alpha]$, with $a_i\in{\mathbb Z}^+$ and 
$\alpha$ a formal is the fractional linear transformation,
\[
[a_0;a_1,\ldots,a_i,\alpha] = \frac{p_i\alpha+p_{i-1}}{q_i\alpha+q_{i-1}}
\]
where $p_j/q_j=[a_0;a_1,\ldots,a_j]$, a ratio of positive integers
expressed in lowest terms, and furthermore,
$p_iq_{i-1}-p_{i-1}q_i=\pm 1$.
\end{lemma}

\begin{lemma}
With $[a_0;a_1,\ldots,a_i,\alpha]$ as above, and
$\alpha=[b_0;b_1,\ldots,b_j,\alpha']$. If $\alpha\ge 1$ then $b_0\ge 1$ and
$[a_0;a_1,\ldots,a_i,\alpha]=[a_0;a_1,\ldots,a_i,b_0,b_1,\ldots,b_j,\alpha']$.
\end{lemma}

\begin{lemma}[Construction lemma]
Suppose $x=[a_0;a_1,\dots,a_i,\alpha]$ is a continued fraction expansion of $x$ where
$\alpha$ is not an integer. Let 
$a_{i+1}=\lfloor\alpha\rfloor$, and $\alpha'=(\alpha-a_{i+1})^{-1}$.
Then
$x=[a_0;a_1,\dots,a_i,a_{i+1},\alpha']$ is also a continue fraction expansion of $x$.
\end{lemma}



 \end{document}