\section{Introduction}
This thesis will provide a practical decision procedure for the
indefinite integration of algebraic functions. Unless explicitly
noted, we will always assume $x$ to be our distinguished variable of
integration. An algebraic function $y$ of $x$ is defined as a solution
of a monic polynomial in $y$ with coefficients that are rational
functions in $x$. Each of these rational functions in $x$ can be
written as a quotient of polynomials in $x$ whose coefficients are
constants (i.e. not dependent on $x$). If we adjoin each of these
constant coefficients to our base field {\bf Q} (rational numbers),
then we have constructed a finitely generated extension of {\bf Q}
that we will call our coefficient field, {\bf K}. We can assume the
integral has the form $\smallint y dx$ where $f(x,y)$ is the unique
monic polynomial of least degree that $y$ satisfies. An elementary
function is one that can be expressed using combinations of algebraic
functions, exponentials and logarithms. We propose either to express
the integral as an elementary function or guarantee that this cannot
be done.
\subsection{Review of Previous Work}
During the $18^{th}$ and $19^{th}$ centuries this problem attracted
much interest[1]. Euler (1748) and others studied elliptic functions
and discovered they were not integrable in terms of elementary
functions. Abel (1826) first studied the integrals of general
algebraic functions, which later became known as abelian
integrals. Liouville [48] proved a key theorem that forms the basis
for the decision procedure. He showed that $\smallint y dx$, if
integrable in terms of elementary functions, could be expressed as
$$\int{y\ dx} = v_0 + \sum{c_i\ log\ v_i}\eqno(1)$$
where the $c_i$ are constants and the $v_i$ are rational combinations
of $x$ and $y$. The basic idea in his proof is that integration cannot
introduce any new functions other than constant multiples of logs
since differentiation would not remove them. Liouville (1833) also
gave an integration algorithm [37] for the special case of algebraic
integrals that could be expressed without logarithms, but he found no
method for solving the general problem. This problem was so difficult
that Hardy (1916) pessimistically stated [25] ``there is reason to
suppose that no such method can be given''.

The next major steps in this area were taken by Risch (1968). First he
gave a complete decision procedure for integrating elementary
functions that were free of algebraic functions [45]. Then he turned
his attention to the algebraic problem, and in [46] he sketched a
procedure that reduced algebraic integration to a problem in algebraic
geometry, determining a bound for the torsion subgroup of the divisor
class group of an algebraic function field. Finally in [47] by
referring to some recent results in algebraic geometry he outlined a
theoretical solution to the problem. While this indeed disproved
Hardy's undecidability conjecture, it did not really present a
practical algorithm that could be used to actually solve integration
problems. 

Risch refined equation (1) by showing one could assume 
$c_i \epsilon \overline {\bf K}$ and
$v_i \epsilon \overline {\bf K} (x,y)$ where $\overline {\bf K}$ is
the algebraic closure of {\bf K} (see also [49]). He also showed that 
$v_0 \epsilon {\bf K} (x,y)$. The integration problem is now reduced
to finding the $c_i$ and the $v_i$. The basic approach that Risch used
and that we will use is to construct these functions by analyzing
their singularities. By considering algebraic functions on their
Riemann surface, they are no longer multi-valued and have only a
finite number of poles as singularities. At each point of the Riemann
surface a function can be expressed locally as a Laurent series in
terms of some uniformizing parameter. When the parameter is expressed
as $(x - a)^{1/n}$ for some $a \epsilon {\bf K}$ and 
$n \epsilon {\bf N}$ the series is called a Puiseux expansion. The
finite initial segment composed of the terms with negative exponents
is called the principal part of the series expansion. If we compute
the principal parts of the integrand at all its poles, then we can
integrate these sums termwise. If we discard the log terms that arise
by integrating terms of the form $r_j (x-a)^{-1}$, then the remaining
terms form the principal parts of the expansions of $v_0$ at all of its
poles. Thus we make the key observation that the singular places of
$v_0$ are a subset of the singular places of the integrand. Now we are
in the position of trying to find a function with a given set of
principal parts. Since an algebraic function with no poles is
constant, this function is only determined up to an additive constant,
as expected from an integration problem. The least degree term of
each principal part specifies the order $n_j$ of the pole at that
place $p_j$ on the Riemann surface. This allows us to associate an
integer with each place if we agree to associate the integer $0$ with
places where the integrand was non-singular. The formal sum over all
places $\sum n_j p_j$ is called a $divisor$, and by the
Riemann-Roch theorem the set of algebraic functions with orders not
less than those specified by the divisor form a finite dimensional
vector space over $\overline {\bf K}$. Bliss [7] gives a technique for
finding a basis for this vector space. A general member of this vector
space can be expressed as a linear combination of basis elements with
indeterminate coefficients. By equating the principal parts of a
general member of the vector space with the principal parts of the
integral we get a system of linear equations that give a necessary and
sufficient condition for the existence of the algebraic part of the
integral.

To find the logarithmic part we now examine the terms of the form 
$r_j (x-a)^{-1}$ that we ignored earlier. The coefficients $r_j$ are
precisely the residues of the integrand at the singular places $p_j$
of the integrand. If the integral exists then it can be presented in a
form where the $c_i$'s form a basis for the {\bf Z}-module generated
by the residues. In fact as we shall show in chapter 6 the $c_i$
generate the minimal algebraic extension of the coefficient field
required to express the integral. The algorithms we present will avoid
Puiseux expansions and never introduce algebraic quantities not
required for the final answer.

To simplify our presentation of Risch's approach, we will now assume
all the residues are rational numbers. The general case will be
treated in chapter 6. Let $m$ be a least common denominator of all the
residues. We will now construct a divisor ${\bf D}$ from our set of
residues, in general we would have $k$ divisors where $k$ is the rank
of the ${\bf Z}$-module generated by the residues. We define the order
of ${\bf D}$ at each place $p$ to be $m$ times the residue of the
integrand at $p$. Thus ${\bf D} = \sum (m r_i) p_i$. Since there are
only a finite number of places where the integrand has non-zero
residue ${\bf D}$ is a well defined divisor. Since the sum of the
residues of the integrand is zero, $deg {\bf D} = \sum (m r_i) =
0$. For any function $f \epsilon {\bf K} (x,y)$ we have a divisor 
$div(f) = \sum (ord_p f) p$ where $ord_p f$ is the order of $f$ at
$p$. A divisor is called principal if it is the divisor of some
algebraic function. If the divisor associated with the residues is
principal describing a function $f$ then we have determined the log
term ${1 \over{m}} log f$. However, if the divisor is not principal it
is possible for some integer multiple of it to become principal. If
$k$ times a divisor ${\bf D}$ is principal with associated function
$v$, then we have a log term ${1 \over{m k}} log v$. This is the
fundamental theoretical obstruction to the integration of algebraic
functions. The integrand contains complete information about the
location and orders of the poles of the algebraic part of the
integral, but for the log parts the residues enable us to find reduced
divisors only (the coefficients of the places are relatively prime),
not necessarily the actual divisors of the logands. The ``points of
finite order problem'' is to find an integer bound ${\bf B}$ such that
if $k {\bf D}$ is not principal for some divisor ${\bf D}$ and all
integers $1 \le k \le {\bf B}$ then no integer multiple of ${\bf D}$
is principal. Under componentwise addition and subtraction of the
order coefficients the set of divisors becomes an abelian group. The
quotient of the group of divisors of degree zero by the subgroup of
principal divisors is called the divisor class group. The divisor
classes for which some multiple is principal form the torsion subgroup
of the divisor class group. Thus we can reformulate our question as
finding a bound for the torsion subgroup. In order for such a bound to
exist it is critical that our constant field be a finitely generated
extension of the rationals and not an algebraically closed field.

The approach that Risch outlined for determining the bound uses a
technique that has lately come into vogue in many areas of algebraic
manipulation. We take a difficult problem and homomorphically map it
into a simpler domain, hoping to find some technique for lifting the
solution back to the original domain. Although the original {\sl
points of finite order} problem seems quite difficult, Weil (1948)
showed that the problem is easily solvable for function fields in one
variable over finite fields [59]. For these fields the divisor class
group is finite and Weil's rationality formula for the zeta function
shows that the order of the class group can be computed by counting
points on a non-singular model. Using Weil's proof of the extended
Riemann hypothesis for such fields we can explicitly give bounds for
the divisor class group over a finite field. An upper bound is
$(\sqrt{q} + 1)^{2g}$ where $q$ is the order of the finite field and
$g$ is the genus, and we obtain a lower bound of 
$(\sqrt{q} - 1)^{2g}$. 

The natural approach to reducing our problem is ``reduction mod $p$,''
where $p$ is the prime ideal for some discrete valuation of our
constant field, e.g. if the constant field is ${\bf Q}$ then $p$ will
be a prime ideal in ${\bf Z}$. But we must verify when such a
reduction is ``good'', i.e. gives us useful information for
determining our bound. Risch observed [47] that if we get a projective
non-singular model for our function field and if its reduction mod $p$
is still non-singular then the reduction is good. This means that the
induced homomorphism of divisor class groups is injective for all
divisors whose order is relatively prime to the characteristic of the
finite field ([51] or [54]). Since the torsion subgroup is a finite
abelian group, it can be decomposed into a product of the group of
elements whose orders are relatively prime to $p$ and the $p$-sylow
subgroup. Thus if we find two distinct rational primes that give us
good reduction, we can multiply the bounds for the two divisor class
groups and get our desired bounds. Risch claimed that all of these
steps were known to be effective, but he provided no explicit
algorithms. Dwork and Baldassarri [4] independently duplicated Risch's
approach to this problem in the process of finding algebraic solutions
for second order linear differential equations.

James Davenport has independently investigated this problem. His
algorithms are constructed along the lines suggested by Risch. He uses
Puiseux expansions and Coate's [14] algorithm to construct a basis for
the multiples of a divisor. This construction is used for both the
algebraic and transcendental part of the answer. To bound the divisor
torsion he uses special purpose algorithms depending on whether the
curve is genus 1 and whether there are parameters present. In the case
there are parameters present, he produces an explicit test for torsion
without computing the bound. In the case of genus 1, he uses
arithmetic on the curve to compute the torsion. While these special
purpose tests can be reasonably efficient, in the general case, he
reverts to the Weil bound given previously. His algorithms are
general, but his implementation is currently limited to algebraic
functions that can be expressed with nested square roots.

Risch and Davenport depend on Puiseux expansions to unravel the
singularities of the function field defined by the integrand. Some
such mechanism is necessary to distinguish apparent poles from actual
ones. For example the function $y/x$ has an apparent pole at the
origin, but if $y^2 = x^2 (x + 1)$ then the function is actually
holomorphic there. We will use integral bases to determine the nature
of the poles of an algebraic function. An integral basis for an
algebraic function field of degree $n$ is a set of $n$ functions such
that an element of the function field can be expressed as a linear
combination of basis elements with polynomial coefficients if and only
if that element has no singularities in the finite plane, i.e. the
element is an integral algebraic function. Good algorithms for
computing integral bases are a subject of ongoing research [63]. Bliss
[7] shows that finding integral bases is no harder than computing
Puiseux expansions, and in the very important case of function fields
defined by a single radical, they are immediate.

In this thesis we present a new algorithm for integration of algebraic
functions. we rely on the construction of an integral basis to provide
an affine non-singular model for the curve. This will allow us to
construct the algebraic part of the answer by a generalization of
Hermite's algorithm for integrating rational functions. This integral
basis can also be used to test whether divisors are principal and to
test for good reduction.

A very serious problem in symbolic calculations is that intermediate
expressions are frequently much larger than the final answer and can
thus be very time and space consuming. One of the counterparts to
intermediate expression swell that we are forced to deal with in this
problem is intermediate constant field extensions. Risch and Davenport
make the simplifying assumption of an algebraically closed constant
field. Making unnecessary extensions of the constant field greatly
increases the cost of arithmetic. We will present an algorithm that
will perform all its operations in the minimum extension field in
which the answer can be expressed. Risch's more extensive use of
Puiseux expansions forced him to operate in an extension field of much
higher degree for his intermediate computations.

We will present a new algorithm for algebraic function integration
that is strongly analogous to recent efficient algorithms for rational
function integration [56]. Using integral bases to normalize the
problem, we will be able to reduce the finding of the algebraic part
of the integral to solving a set of linear equations. Finding the
logarithmic part is indeed more difficult and does involve determining
whether a given divisor is of finite order to guarantee termination of
the algorithm. In addition to obtaining bounds that guarantee
termination, we will present a novel algorithm for actually obtaining
the logand associated with a divisor. Unlike earlier approaches that
constructed this function from the divisor alone, we will use the
integrand to create the ideal of functions that are multiples of the
divisor in all finite places. Generators for this ideal can be derived
almost by inspection, and there remains only to determine whether
there is a principal generator.

Algebraic function integration is significantly more complicated than
rational function integration since one can no longer depend on unique
factorization. Ideals were created by Dedekind to restore unique
factorization to algebraic number fields. Since that time they have
been studied in increasingly abstract settings, to the point that
their origins are almost forgotten. We intend to actually use ideals,
as Dedekind intended 100 years ago, to combat the lack of unique
factorization in algebraic function fields. In addition, our explicit
generators for the ideal associated with a divisor will permit us to
reduce the generators and compute the exact order of this divisor mod
$p$. Thus instead of working with bounds for the torsion, we can
compute the exact order of torsion divisors. We then need only test
whether or not this particular power is principal, instead of testing
all powers up to some calculated bound. This will be shown to lead to
a very practical decision procedure for algebraic function
integration.

Finally we will investigate the possibility of extending this
procedure to include exponentials and logarithms enabling one to
determine whether the integral of any elementary function can be
expressed as an elementary function.

\subsection{Outline of Thesis}

Chapter Two will present an algorithm for computing an integral basis
for our function field. This is essentially the same algorithm
presented by Ford [23] for algebraic number fields, with proofs of
validity in this more general situation and extended to normalize the
basis elements at infinity. This fundamental construction will be used
throughout the thesis and effectively provides us with an affine
non-singular model for our function field. It enables us to determine
the poles of our integrand and characterize the form of the answer. We
will also use this integral basis to help find principal generators
for divisors and test for ``good reduction''.

Since the running time of many of our algorithms depends critically on
the degree of the defining relationship for our function field, it is
very useful to guarantee that our defining polynomial is irreducible
over the algebraic closure of our coefficient domain, i.e. is
absolutely irreducible. In Chapter Three we present a new algorithm
for finding an absolutely irreducible factor of a multivariate
polynomial that seems to be significantly better than other known
approaches. As pointed out by Duval [21], the number of absolutely
irreducible factors of the defining polynomial is the same as the
dimension of the vector space of functions that have no poles. We can
compute this simply using our normalized integral basis, and then we
only need to perform our factorization algorithm when it is known to
yield a lower degree factor. Since an irreducible polynomial will
usually be absolutely irreducible, this can prevent a lot of wasted
effort. 

Armed with a minimal defining polynomial and an integral basis we are
ready to find the purely algebraic part of the integral. Chapter Four
proceeds by analogy with the standard approaches to rational function
integration. It shows how Hermite's algorithm can be generalized to
deal with algebraic functions. This approach will always succeed in
reducing the integral to one with only simple finite poles and perhaps
poles at infinity. In fact we are able to show that if the original
problem had no poles at infinity, and after removing the algebraic
part we introduce poles at infinity, then the original problem was not
integrable. This approach has the advantage of allowing one to obtain
canonical reduced forms even for problems that are not integrable. In
this stage only linear congruence equations are solved and no new
algebraic numbers are generated. It is difficult to remove poles at
infinity by a Hermite-like method, so the original integral is
transformed by a simple change of variables so that there are no poles
at infinity. This simplifying transformation is one of the problems to
be overcome in trying to generalize this algorithm to handle mixed
transcendental as well as algebraic extensions.

If the original problem was integrable, the remaining simple finite
poles must be canceled by the derivative of a linear combination of
logarithmic terms. In the rational function case these log terms can
be found by factorization or by computing gcd's of
polynomials. Unfortunately algebraic function fields are not unique
factorization domains so this approach cannot be used. As described
earlier we will use the residues of the integrand to construct
divisors associated with each log term. In Chapter Five we present an
algorithm that computes a polynomial whose roots are all the residues
using resultants. This is an extension of the idea we used in [55] for
rational functions and does not use power series expansions or
extensions of the coefficient domain. Given this polynomial we finally
need to extend our coefficient domain to include its splitting
field. We show that this is the minimal extension required for
expressing the integral. After computing the {\bf Z}-linear basis for
the residues, we construct a model for the divisor associated with
each basis element. Our construction of the model appears new, and
provides us with a simple construction to find a principal generator
if one exists.

Finally in Chapter Six we are ready to address the ``points of finite
order problem''. We need to know for each of the divisors we have
constructed, whether there is some power of it that is principal. As
discussed in Risch [47] and Davenport [16], we will use the technique
of ``good reductions'' to solve this problem. However our explicit
representation of a divisor will allow us to compute the order of
individual divisors exactly instead of merely computing a bound on the
orders of all divisors. While we do perform a sequence of tests for
principality on powers of divisors, these tests are all performed over
finite constant fields and thus much less expensive then testing
successive powers of a divisor over our original coefficient
field. After computing what should be the order of our original divisor
if it were finite, we merely perform a single test for that power of
our divisor over the original function field. Both of these
improvements should make a substantial difference in running time.

In Chapter Seven we summarize our contributions and suggest ways to
extend the work done here. In an appendix we present one step toward a
complete algorithm for handling both transcendental and algebraic
extensions. 

\section{Integral Basis}

In later chapters we will be very concerned with the problem of
creating functions with prescribed singularities. It will be very
useful to be able to recognize and generate functions whose only poles
lie at places over infinity. Such functions are called integral
algebraic functions. In the field ${\bf K}(x)$ these are simply
polynomials in $x$, i.e. a rational function has a finite pole if and
only if it has a nontrivial denominator. Any function that is
algebraic over ${\bf K}(x)$ satisfies a unique monic irreducible
polynomial with coefficients in ${\bf K}(x)$.
$${\bf Z}^m + a_1 {\bf Z}^{m-1} + \cdots + a_m\eqno(1)$$
Such a function is integral over ${\bf K}[x]$ if and only if the
coefficients are in fact in ${\bf K}[x]$, i.e. polynomials in $x$. In
the rest of this thesis we will abbreviate ``integral over 
${\bf K}[x]$'' to ``integral''.

Let ${\bf K}(x,y)$ be a finite algebraic extension of degree $n$ over
${\bf K}(x)$, then the integral functions form a free module of rank
$n$ over ${\bf K}[x]$, i.e. any such function can be written as linear
combination of $n$ basis functions with coefficients that are
polynomials in $x$. Such a basis is called an {\sl integral basis}. If
we allow the coefficients to be rational functions in $x$ then these
same $n$ functions comprise a vector space basis for ${\bf K}(x,y)$
over ${\bf K}(x)$. Thus each element of ${\bf K}(x,y)$ has a unique
representation in terms of a particular integral basis, and has no
finite poles if and only if each coefficient is a polynomial, i.e. no
denominators. In this chapter we present an algorithm for computing an
integral basis.

One technique for finding such a basis is given in [Bliss]. What we
call an integral basis, he would term {\sl multiples except at
infinity of the divisor 1}. His basic technique involves Puiseux
expansions. We wish to avoid performing such expansions for two
reasons: (1) A large amount of code is required (2) Many algebraic
numbers need to be introduced to compute Puiseux expansions even
though none of them are actually required to express the final basis
elements. While Puiseux expansions are very useful in their own right,
we don't really need them and choose to avoid the time cost of doing
unnecessary algebraic number computations and the space cost of all
that additional code.

The algorithm we present here is based on work by Zassenhaus and Ford
[23]. They were primarily interested in the case of algebraic number
fields, but their algorithm also applies to function fields in one
variable. In fact since we will always assume the characteristic of 
${\bf K}$ is zero or greater than $n$, the algorithm can be somewhat
simplified. The algorithm presented here is a generalization to
function fields of the first of the two algorithms Ford presents. We
choose to use this one since it is much simpler and it avoids fully
factoring the discriminant.

We are given ${\bf K}(x,y)$ where ${\bf K}$ is a computable field, $x$
is a distinguished transcendental element, and $f(x,y)$ is an
irreducible separable polynomial of degree $n$ over ${\bf K}[x]$. 
Without loss of generality we can also assume $f$ monic. If not then
let $\hat y = a y$ where $a$ is the leading coefficient, then $\hat y$
satisfies a monic polynomial and generates the same function
field. The elements of ${\bf K}(x,y)$ that are integral over 
${\bf K}[x]$ form a ring called the integral closure of ${\bf K}[x]$
in ${\bf K}(x,y)$. As noted above this ring is also a free module of
rank $n$. Since $y$ is integral over ${\bf K}[x]$, and the sum or
product of integral elements are integral,
$[1,y,\ldots,{y^{n-1}}]$ constitutes a basis for an integral 
${\bf K}[x]$ module. This is our first ``approximation'' to an
integral basis. Each iteration of the algorithm will produce a basis
for a strictly larger integral ${\bf K}[x]$ module until the integral
closure is reached.

One important measure of the relative sizes of full (i.e. rank $n$)
sub-modules of the integral closure is given by the discriminant. Let
$[w_1,\cdots,w_n]$ be $n$ elements of ${\bf K}(x,y)$. Since 
${\bf K}(x,y)$ is a separable algebraic extension of ${\bf K}(x)$ of
degree $n$, there are $n$ distinct embeddings $\sigma_i$ into a given
algebraic closure. The images of an element under these mappings are
called the conjugates of that element. The conjugate matrix of
$\overline {\bf w} = [w_1,\ldots,w_n]$ is defined by
$$M_{\overline w} = \left[\matrix{
                      \sigma_1(w_1) & \cdots & \sigma_n(w_1)\cr
                      \vdots        &        & \vdots\cr
                      \sigma_1(w_n) & \cdots & \sigma_n(w_n)}
                     \right]\eqno(2)$$
The {\sl discriminant} of $\overline {\bf w}$ is the square of the
determinant of the conjugate matrix. The discriminant is non-zero if
and only if the $w_i$ generates a full module (i.e. they are linearly
independent). We can define the trace $(sp)$ of an element 
$w \epsilon {\bf K}(x,y)$ as $sp(w) = \sum \sigma_i(w)$. 
Since this is a symmetric function of the conjugate, it is an element
of ${\bf K}(x)$. If we re-express the discriminant as the determinant
of the product of the conjugate matrix and its transpose, we see that
the product entries are traces of products of the original matrix
entries. Thus the discriminant could be defined as
$determinant(sp(w_i w_j))$.
$$SP_{\overline w} = 
  \left[\matrix{
     \sigma_1(w_1) & \cdots & \sigma_n(w_1)\cr
     \vdots        &        & \vdots\cr
     \sigma_1(w_n) & \cdots & \sigma_n(w_n)}
  \right]
  \left[\matrix{
     \sigma_1(w_1) & \cdots & \sigma_1(w_n)\cr
     \vdots        &        & \vdots\cr
     \sigma_n(w_1) & \cdots & \sigma_n(w_n)}
  \right]$$
$$ =
  \left[\matrix{
     sp(w_1^2) & \cdots & sp(w_1 w_n)\cr
     \vdots        &        & \vdots\cr
     sp(w_n w_1) & \cdots & sp(w_n^2)}
  \right]\eqno(3)$$
If the $w_i$'s are integral functions then their traces are
polynomials, and thus the discriminant is a polynomial. If
$\overline {\bf v} = [v_1,\ldots,v_n]$ is a basis for a full module
that contains $\overline {\bf w}$ then each $w_i$ can be written as a
polynomial combination of the $v_i$, i.e. 
$\overline {\bf w} = A \overline {\bf v}$ where the change of basis
matrix $A$ is an $n x n$ matrix of polynomials. Thus the conjugate
matrix $M_{\overline {\bf w}} = A . M_{\overline {\bf v}}$ and 
$Disc(\overline {\bf w}) = det (A)^2 Disc(\overline {\bf v})$.
$\overline {\bf w}$ and $\overline {\bf v}$ generate the same module
if and only if A is invertible as a matrix over ${\bf K}[x]$, i.e. 
$det(A) \epsilon {\bf K}$. If $\overline {\bf v}$ strictly contains
$\overline {\bf w}$ then $det(A)$ is a polynomial $p$ of nonzero
degree and $Disc(\overline {\bf v}) = Disc(\overline {\bf w})/p^2$ thus
each time we are able to produce a strictly larger ${\bf K}[x]$
modules, we eliminate a squared factor from the discriminant and the
process can only continue for finitely many steps.

We will now state and prove the key algebraic result on which the
algorithm is based. Let ${\bf R}$ be a {\sl principal ideal domain},
in our case ${\bf K}[x]$ while Ford and Zassenhous assume 
${\bf R} = {\bf Z}$. Let ${\bf V}$ be a domain that is a finite
integral extension of ${\bf R}$. Then ${\bf V}$ is also a free module
of rank equal to the degree of ${\bf QF(V)}$ (the quotient field of 
${\bf V}$) over ${\bf QF(R)}$. Let 
$\overline {\bf v} = [v_1,\ldots,v_n]$ be a basis for ${\bf V}$ over 
${\bf R}$. The discriminant of $\overline {\bf v}$ generates an ideal in 
${\bf R}$ that we will call the discriminant of ${\bf V}$ over
${\bf R}$. The discriminant of any other basis of ${\bf V}$ over
${\bf R}$ differs by the square of a unit and thus generates the same
ideal. If $m$ is an ideal in a ring ${\bf S}$, we define the 
idealizer $Id(m)$ to be the set of all $u \epsilon {\bf QF(S)}$ 
such that $u m \subseteq m$. $Id(m)$ clearly contains ${\bf S}$ 
and is the largest ring in which $m$ is still an ideal.
\begin{theorem}
Under the above conditions {\bf V} is integrally
closed if only if the idealizer of every prime ideal containing the
discriminant equals {\bf V}.
\end{theorem}
\noindent
We will break this into a succession of small lemmas.
\begin{lemma}
If ${\bf m}$ is a nonzero ideal in {\bf V} the idealizer of ${\bf m}$ 
is integral over {\bf R}.
\end{lemma}
\begin{proof}
Since ${\bf V}$ is a finite ${\bf R}$-algebra ${\bf m}$ is finitely
generated over ${\bf R}$. Let $m_1,\ldots,m_k$ span ${\bf m}$ over 
${\bf R}$ and let $u \epsilon {\bf QF(V)}$ such that 
$u {\bf m} \subseteq {\bf m}$. Then $u m_i = \sum_j r_{i j} m_j$ with 
$r_{i j} \epsilon {\bf R}$. Let ${\bf M}$ be the matrix 
$r_{i j} - \delta_{i j} u$ where $\delta_{i j}$ is the Kronecker
index. Then ${\bf M}$ annihilates the vector $[m_1,\ldots,m_k]$ and if
we multiply by the adjoint of ${\bf M}$ we see that $det {\bf M}$
kills each of $m_i$ and thus annihilates ${\bf m}$. Since ${\bf V}$
is an integral domain, $det({\bf M})$ must be zero, but this gives a
monic polynomial over ${\bf R}$ that $u$ satisfies, and hence $u$ is
integral over ${\bf R}$.
\end{proof}

Next we define the {\sl inverse} of an ideal. If ${\bf m}$ is an ideal
in ${\bf V}$ then ${\bf m^{-1}}$ is the set of all 
$u \epsilon {\bf QF(V)}$ such that $u {\bf m} \subseteq {\bf V}$. This
notion is similar to the idealizer. The idealizer of an ideal is the
subset of the quotient field that sends an ideal into itself, while
the inverse of an ideal sends it into the ring ${\bf V}$. Having
defined the inverse of an ideal we will say that an ideal ${\bf m}$ is
{\sl invertible} if ${\bf m}{\bf m^{-1}} = {\bf V}$. By definition we
have ${\bf m}{\bf m^{-1}} \subseteq {\bf V}$. If ${\bf V}$ is
integrally closed then it is a Dedekind domain and has the property
that every non-zero ideal is invertible. By proposition 9.7 and 9.8 in
[2] p.97 we have
\begin{lemma}
If all the non-zero prime ideals in ${\bf V}$ are invertible the 
${\bf V}$ is integrally closed.
\end{lemma}
\begin{lemma}
Any prime ideal not containing the discriminant of ${\bf V}$ over
${\bf R}$ is invertible.
\end{lemma}
\begin{proof}
Let ${\bf m}$ be a prime ideal not containing the discriminant of 
${\bf V}$ over ${\bf R}$. Then if we localize at ${\bf m}$ the
discriminant becomes a unit and thus the local ring is integrally
closed and locally ${\bf m}$ is invertible, in fact principal. If we
localize at any other maximal ideal of ${\bf V}$ ${\bf m}$ contains
units and is its own inverse. Since the localization of ${\bf m}$ 
at each prime ideal is invertible then by proposition 9.6 [2] 
${\bf m}$ is invertible.
\end{proof}
\begin{corollary}
If ${\bf V}$ is not integrally closed there is some prime ideal
containing the discriminant that is not invertible.
\end{corollary}
\begin{proof}
By lemma 2.3 there is some prime ideal that is not invertible and by
lemma 2.4 it must contain the discriminant
\end{proof}

\noindent
The following lemma is proved in [31] p.607.
\begin{lemma}
If ${\bf V}$ properly contains an ideal ${\bf m}$ then ${\bf m^{-1}}$ 
properly contains ${\bf V}$.
\end{lemma}

\noindent
Now we are ready to finish the proof of theorem 2.1.
\begin{proof}
If ${\bf V}$ is integrally closed the idealizer of any non-zero ideal
equals ${\bf V}$ by lemma 2.2. If ${\bf V}$ is not integrally closed
there is some prime ideal ${\bf m}$ that contains the discriminant but
is not invertible. Thus ${\bf m^{-1}}{\bf m}$ is an ideal containing
${\bf m}$ but properly contained in ${\bf V}$. Since ${\bf m}$ is
maximal we must have ${\bf m^{-1}}{\bf m} = {\bf m}$. Thus in this
case ${\bf m^{-1}} = Id({\bf m})$. By lemma 2.6 we have the idealizer
of ${\bf m}$ properly contains ${\bf V}$.
\end{proof}

Using theorem 2.1 we could compute the integral closure by computing
the idealizer of the finitely many ideals that contain the
discriminant. Either the result in each case will be ${\bf V}$ in
which case ${\bf V}$ must be integrally closed, or we will find a ring
strictly larger than ${\bf V}$ that is integral over ${\bf V}$. This
can happen only a finite number of times since each such ring will
remove a squared non-unit factor from the discriminant. We will
improve this idea by dealing with all the ideals dividing the
discriminant at the same time. First we observe the following property
of idealizers:
\begin{lemma}
If ${\bf m}$ and ${\bf n}$ are ideals then the idealizer of the
product contains the idealizer of either ideal.
\end{lemma}
\begin{proof}
Any element of ${\bf m}{\bf n}$ is of the form $\sum m_i n_i$ where 
$m_i \epsilon {\bf m}$ and $n_i \epsilon {\bf n}$. If 
$u \epsilon Id({\bf m})$ then $u m_i \epsilon {\bf m}$ and thus
$u m_i n_i \epsilon {\bf m}{\bf n}$ 
\end{proof}
Next we must introduce the notion of the radical of an ideal. The
radical of an ideal ${\bf m} \subseteq {\bf V}$ is the set of all 
$u \epsilon {\bf V}$ such that some power of $u$ is in ${\bf m}$ and
can also be characterized as the intersection of all prime ideals
containing ${\bf m}$. Our algorithm is based on the following
corollary to theorem 2.1.
\begin{corollary}
${\bf V}$ is integrally closed if and only if the idealizer of the
radical of the discriminant equals ${\bf V}$.
\end{corollary}
\begin{proof}
Since all the non-zero prime ideals of ${\bf V}$ are maximaal, the
radical of the discriminant is also the product of all prime ideals
containing the discriminant. By theorem 2.1 if ${\bf V}$ is not
integrally closed the idealizer of one of these primes must be
strictly larger than ${\bf V}$. By lemma 2.7 the idealizer of the
radical contains the idealizer of that prime and thus must also
strictly contain ${\bf V}$. If ${\bf V}$ is integrally closed again
the idealizer of any ideal must equal ${\bf V}$.
\end{proof}

\noindent
Thus our algorithm for computing the integral closure of ${\bf V}$ is:
\begin{enumerate}
\item find the radical of the discriminant of ${\bf V}$ over ${\bf R}$
\item compute the idealizer ${\bf \widehat V}$ of that radical
\item If ${\bf \widehat V}$ is strictly larger than ${\bf V}$ then set 
${\bf V}$ to ${\bf \widehat V}$ and go to step (1)
\item return ${\bf V}$
\end{enumerate}

\noindent
Although this algorithm works, there are a few optimizations
possible. The first time through ${\bf V} = {\bf R}[\alpha]$ where
$\alpha$ satisfies equation (1). To compute the discriminant in this
case, one simply computes the resultant of equation (1) and its
derivative. Prime factors of the discriminant that appear only to the
first power can be ignored. When returning from step 3 to step 1 one
only needs to concentrate on the factors of the discriminant that have
actually been reduced in the previous iteration. Since if there is
some $p$ whose $p$-radical is invertible, it will stay that way
throughout the rest of the computation. This leads us to the following
improved version of the algorithm for computing the integral closure
of ${\bf V} = {\bf R}[\alpha]$ over ${\bf R}$ assuming f(X) is the
minimal equation of integral dependence for $\alpha$.
\begin{enumerate}
\item Let $d = Resultant(f,f^{\prime})$ and $k = d$
\item Let $q = \prod p_i$ such that $p_i$ is prime, $p_i \ \vert\  k$
and $p_i^2 \ \vert\ d$. If $q$ is a unit the return ${\bf V}$.
\item Find ${\bf J}_q({\bf V})$, the radical of (q) in ${\bf V}$
\item Find ${\bf \widehat V}$, the idealizer of ${\bf J}_q({\bf V})$
along with ${\bf M}$ the change of basis matrix from ${\bf \widehat V}$
to ${\bf V}$.
\item Let $k$ be the determinant of ${\bf M}$. If $k$ is a unit then
return ${\bf V}$
\item Set $d = d/k^2$ and ${\bf V} = {\bf \widehat V}$ and go to 1.
\end{enumerate}
\subsection{Radical of the Discriminant}
The discriminant is a principal ideal generated by some element $d$ of 
${\bf R}$. We wish to compute the radical of the ideal $d$ generates
in ${\bf V}$. Since ${\bf R}$ is a principal ideal domain it is also a
unique factorization domain. Let $(p_1,\ldots,p_k)$ be the distinct
prime factors of $d$ in ${\bf R}$. Since the radical of $(d)$ is the
intersection of the prime ideals containing $d$, it is also the
intersection of the radicals of the $p_i$. Let us therefore consider
how to compute the radical in ${\bf V}$ of a principal ideal generated
by a prime element $p$ of ${\bf R}$. Following Ford we call such an
ideal the {\sl p-radical} of ${\bf V}$.

$u$ is in the $p$-radical if and only if the coefficients $a_i$ in
equation (1) of the monic minimal polynomial for $u$ over ${\bf R}$
are divisible by $p$. ([2] Proposition 5.14 and 5.15). This gives us a
membership test, but we are looking for ideal generators. Zassenhaus
and Ford observed that under appropriate conditions the trace map from 
${\bf V}$ to ${\bf R}$ provides us with linear contraints on the
members of the $p$-radical. For any $u$ in ${\bf V}$ the degree of $u$
over ${\bf R}$ must divide the rank of ${\bf V}$ over ${\bf R}$ that
is also the degree of ${\bf QF(V)}$ over ${\bf QF(R)}$. If $m$ is the
degree of $u$ over ${\bf R}$ then $sp(u) = -(n/m) a_1$. Thus if
$u \epsilon$ $p$-radical then $p$ divides $sp(u)$. Again following
Ford we define the {\sl p-trace-radical} as the set of 
$u \epsilon {\bf V}$ such that for all $w \epsilon {\bf V}$,
$p\ \vert\ sp(u w)$. This leads us to the following lemma:
\begin{lemma}
$p$-radical $\subseteq$ $p$-trace-radical
\end{lemma}
\begin{proof}
If $u$ is in the $p$-radical then for any $w \epsilon {\bf V}$, 
$u w$ is in the $p$-radical. But the the previous argument shows that 
$sp(u w)$ is divisible by $p$.
\end{proof}

Now we find conditions under which the two sets of lemma 2.9 are the
same. If $w$ is in the $p$-trace-radical the 
$sp(w^k) \equiv 0\ mod\ p$
for all $k > 0$. Let $m$ be the degree of $w$ over ${\bf R}$. Then 
${\bf R}[w]$ is a free $R$-module of rank $m$ dividing $n$, the
rank of ${\bf V}$ over ${\bf R}$. There is a reduced trace map from 
${\bf R}[w]$ to ${\bf R}$ denoted by $sp_w$ satisfying 
$(n/m)sp_w(u) = sp(u)$ for any $u \epsilon {\bf R}[w]$. If 
$n/m \notin (p)$ then $p$ dividing $sp(u)$ implies $p$ divides
$sp_w(u)$ and thus the $p$-trace-radical of ${\bf R}[w]$ equals the
intersection of the $p$-trace-radical of ${\bf V}$ with ${\bf R}[w]$.
If n/m is zero in ${\bf R}/(p)$ then the characteristic of 
${\bf R}/(p)$ must divide $n$. To avoid this problem, we now make the
assumption that the characteristic of ${\bf R}/(p)$ is greater than
$n$ the rank of ${\bf V}$ over ${\bf R}$. In our application where 
${\bf R}= {\bf K}[x]$ the characteristic of ${\bf R}/(p)$ is the same
as the characteristic of ${\bf K}$, and we shall see that the
restriction will not cause any problems. In Ford and Zassenhaus' case
where ${\bf R} = {\bf Z}$, $p\ \epsilon\ {\bf Z}$ and the
characteristic of ${\bf R}/(p)$ equals $p$. Thus when the discriminant
has small prime factors, our assumption would be invalid, so they
compute the $p$-radical for small values of $p$ using the kernel of
powers of the Frobenious automorphism instead of the trace map.

Assume $w$ is in the $p$-trace-radical of ${\bf R}[w]$. Then 
$sp_w(w^k)$ is divisible by $p$ for all $k > 0$. We wish to relate the
traces of powers of $w$ to the coefficients of the minimal polynomial
for $w$ in equation (1). This is provided by Newton's identities ([29]
p. 208). If we let $s_k = sp_w(w^k)$ then for $1 \le k \le n$ we have:
$$s_k + a_1 s_{k-1} + \cdots + a_{k-1} s_1 = - k a_k \eqno(4)$$
Thus $a_1 = - s_1$ is divisible by $p$ and by induction assume $a_i$
is divisible by $p$ for all $i < k \le n$. Thus the left hand side of
equation (4) is divisible by $p$ and as long as the characteristic of 
${\bf R}/(p)$ is greater than $n$ we can divide by $k$ and $a_k$ must
also be divisible by $p$. Since the coefficients of its minimal
polynomial are divisible by $p$, $w$ must be in the $p$-radical by 
${\bf V}$, which proves the following partial converse to lemma 2.9.
\begin{theorem}
If the characteristic of ${\bf R}/(p)$ is greater than the rank of 
${\bf V}$ over ${\bf R}$, then the $p$-trace-radical of ${\bf V}$
equals the $p$-radical of ${\bf V}$.
\end{theorem}
\subsubsection{Computing the p-trace-radical}
Let $[w_1,\ldots,w_n]$ be a basis for ${\bf V}$ over ${\bf R}$.
The $p$-trace-radical ${\bf J}_p({\bf V})$ was defined as the set of 
$u \epsilon {\bf V}$ such that $p\ \vert\ sp(u w)$ for all 
$w \epsilon {\bf V}$.
$$sp(u w) \equiv 0\ mod\ p \ {\rm for\ all}\  w \epsilon {\bf V} \iff$$
$$sp(u w_i) \equiv 0\ mod\ p \ {\rm for}\  1 \le i \le n \iff$$
$$\sum_{j=1}^n u_j sp(w_j w_i) \equiv 0\ mod\ p \ {\rm for}
\  1 \le i \le n$$
Using the trace matrix ${\bf SP_{\overline w}}$ defined by equation (3)
we can write this as:
$${\bf SP}_{\overline w} \bullet {\overline u} =
  \left[\matrix{
     sp(w_1^2) & \cdots & sp(w_1 w_n)\cr
     \vdots        &        & \vdots\cr
     sp(w_n w_1) & \cdots & sp(w_n^2)}
  \right]
  \left[\matrix{u_1\cr
                \vdots\cr
                u_n}
  \right] \ \epsilon\ p {\bf R}^n\eqno(5)$$
where $p {\bf R}^n$ represents the set of vectors of length $n$ whose
elements are divisible by $p$. ${\bf J}_p({\bf V})$ is determined by
the solutions to (5) with $u_i \epsilon {\bf R}$. We actually wish to
compute ${\bf J}_q({\bf V})$ where $q$ is a certain product of
distinct primes dividing the discriminant.
$${\bf J}_q({\bf V}) = \bigcap_{p_i \vert q} {\bf J}_{p_i}({\bf V})$$
Thus we want to find all ${\overline u} \epsilon {\bf R}^n$ such that
the left side of equation (5) is in fact in $q {\bf R}^n$. We need to
add some equations to (5) to guarantee that each element $u_i$ of our
solution vectors must lie in ${\bf R}$ as opposed to ${\bf QF(R)}$. 
Let ${\bf I}_n$ be the $n \times n$ identity matrix. Then 
${\overline u} \epsilon {\bf R}$ if and only if 
$q {\bf I}_n \bullet {\overline u} \epsilon q {\bf R}^n$. Thus if we
let ${\bf M}_q$ be the vertical concatenation of 
${\bf SP}_{\overline w}$ and $q {\bf I}_n$, ${\bf J}_q({\bf V})$ is
the set of all $u \epsilon {\bf QF(V)}$ such that
${\bf M}_q \bullet {\overline u} \epsilon q {\bf R}^{2 n}$. If we left
multiply ${\bf M}_q$ by an invertible ${\bf R}$-matrix, the 
${\bf R}$-module of solutions remains unchanged. Invertible 
${\bf R}$-matrices are called unimodular, and are characterized by
having determinants that are units in ${\bf R}$. Since ${\bf R}$ is a
principal ideal domain, there is some unimodular matrix that converts
${\bf M}_q$ into an upper triangular matrix. ([44] Theorem II.2 gives
a constructive proof of this). This process allows us to reduce the 
$2 n$ relations imposed by ${\bf M}_q$ and equation (5) to an
equivalent set of $n$ independent relations. Once this is done, we
invert the square matrix determined by the first $n$ rows of the
reduced ${\bf M}_q$. The columns of this inverse matrix provide a
basis for the solutions to equation (5).

In our application we have the even stronger restriction that 
${\bf R}$ is a euclidean domain. This allows us to triangularize 
${\bf M}_q$ by elementary row operations only. This process is called
Hermitian row reduction and is somewhat analogous to gaussian
elimination that is used for matrices over fields. With gaussian
elimination any nonzero element can be used to zero out its entire
column. With hermitian row reduction one can only multiply by elements
of ${\bf R}$ and a nonzero element can reduce the other members of its
column to be smaller than it. Since ${\bf R}$ is a euclidean domain
this process can only continue for finitely many steps before we find
an element that divides everyone else in its column. Finally this
element can be used to clear the column. Let $d$ be the size function
associated with ${\bf R}$, for ${\bf R} = {\bf K}[x]$ we use the
degree, and for ${\bf R}= {\bf Z}$ we use absolute value. To simplify
the presentation of the following algorithm we define $d(0) =
\infty$. Let $nrows$ and $ncols$ be respectively the numbers of rows
and columns of a given matrix ${\bf M}$. We assume that 
$nrows \ge ncols$ and ${\bf M}$ has rank $ncols$ in the following
algorithm for hermitian row reduction.
\begin{enumerate}
\item loop for $j = 1$ thru $ncols$
\item \hskip .3in choose $k$ such that $d({\bf M}_{k j})$ is minimal for $j \le k \le nrows$.
\item \hskip .3in exchange rows $j$ and $k$
\item \hskip .3 in loop for $i = j + 1$ thru $nrows$
\item \hskip .6 in let $q$ be the polynomial part of ${\bf M}_{i j}/{\bf M}_{j j}$
\item \hskip .6 in replace ${\bf M}_i$ with ${\bf M}_i - q {\bf M}_j$
\item \hskip .3 in if there is some ${\bf M}_{i j} \ne 0$ for $j < i \le nrows$ then go to 2
\item return ${\bf M}$
\end{enumerate}
\subsection{Computing the Idealizer}

Given $(m_1,\ldots,m_n)$ that form an ${\bf R}$-basis for an ideal
${\bf m}$ in ${\bf V}$, we wish to compute an ${\bf R}$-basis for the
idealizer of ${\bf m}$. The idealizer of ${\bf m}$ was defined as the 
set of $u \epsilon {\bf QF(V)}$ such that 
$u {\bf m} \subseteq {\bf m}$. This concept is very similar to the
inverse ideal of ${\bf m}$, ${\bf m}^{-1}$, which was defined as the
set of $u \epsilon {\bf QF(V)}$ such that 
$u {\bf m} \subseteq {\bf V}$. Although we don't need to compute
inverses to find an integral basis, we will need them in chapter 5, and
we present both algorithms here to display their similarities. The
inverse procedure will be given first since it is slightly simpler.

We assume ${\overline {\bf v}} = (v_1,\ldots,v_n)$ forms a basis for
${\bf V}$ over ${\bf R}$ that we hold fixed throughout this section.
$u \epsilon {\bf m}^{-1}$ if and only if 
$u m_i = \sum r_{i j} v_j$ with $r_{i j} \epsilon {\bf R}$ 
for $1 \le i \le n$. Multiplication by $m_i$ is a linear
transformation on ${\bf V}$. Let ${\bf M}_i$ represent multiplication
by $m_i$ with respect to our fixed choice of basis 
${\overline {\bf v}}$. (for details on constructing ${\bf M}_i$ see
[55]) Since ${\overline {\bf v}}$ also forms a basis for ${\bf QF(V)}$
over ${\bf QF(R)}$, ${\bf u}$ can be represented as $\sum u_i v_i$ where
$u_i \epsilon {\bf QF(R)}$. Then ${\bf M}_i [u_1,\ldots,u_n]^t$ yields
the vector of coefficients of $u m_i$. 
${\bf u} \epsilon {\bf m}^{-1}$ if
and only if the product coefficients lie in ${\bf R}$ for all
$i$. Thus we are left with the linear algebra problem of finding a
basis for ${\bf R}$-module of vectors $[u_1,\ldots,u_n]$ such that 
${\bf M}_i([u_1,\ldots,u_n]^t)$ is a vector of elements of ${\bf R}$
for all $i$. Let ${\bf M}$ be the $n^2 \times n$ matrix that is the
vertical concatenation of the ${\bf M}_i$. Then we are looking for all
vectors ${\overline {\bf u}}$ over ${\bf QF(R)}$ such that 
${\bf M} {\overline {\bf u}}$ is an $n^2$ vector of elements of 
${\bf R}$. By Hermitian row reduction we can zero out the last 
$n^2 - n$ rows of ${\bf M}$, so we have reduced to an $n \times n$
matrix ${\widehat {\bf M}}$ such that 
${\bf M} {\overline {\bf u}} \epsilon {\bf R}^{n^2}$ if and only if
${\widehat {\bf M}} {\overline {\bf u}} \epsilon {\bf R}^n$.
The columns of ${\widehat {\bf M}}^{-1}$ form a basis for
${\bf m}^{-1}$.

Essentially the same approach will allow us to find the idealizer of 
${\bf m}$. Now we require that $u m_i = \sum r_{i j} m_j$ with
$r_{i j} \epsilon {\bf R}$. The ${\bf M}_i$ still represent
multiplication by $m_i$ but now the input and output bases are
different. The ${\bf M}_i$ necessary to compute the idealizer again
take inputs expressed in terms of ${\overline {\bf v}}$ but give
output vectors expressed in terms of the basis for ${\bf m}$. Other
than this one change the algorithm for idealizers is identical to the
previous one for inverses. A summary of both algorithms follows:

\begin{enumerate}
\item Let ${\bf M}_i$ be the matrix representing multiplication by 
$m_i$ with input base ${\overline {\bf v}}$ and output basis
${\overline {\bf v}}$ for computing inverses or ${\overline {\bf m}}$ 
for calculating the idealizer.
\item Let ${\widehat {\bf M}}$ be the first $n$ rows of the Hermitian
row reduction of the vertical concatentation of the ${\bf M}_i$.
\item Return the columns of ${\widehat {\bf M}}^{-1}$ as the result
expressed with respect to ${\overline {\bf v}}$.
\end{enumerate}
Note the transpose of ${\widehat {\bf M}}^{-1}$ is the change of basis
matrix required in step 3 of the integral basis algorithm.

\subsection{Normalize at Infinity}
In this section we return to the special case 
${\bf R} = {\bf K}[x]$. Having constructed an integral basis we can
recognize finite poles of functions, but we also need to deal with
singularities at ``infinity''. Given an arbitrary basis for a 
${\bf K}[x]$ module (an integral basis is a special case), we wish to
minimize the sum of the orders of the basis elements at infinity. A
characteristic property of an integral basis $[w_1,\ldots,w_n]$ is
that $\sum a_i (x) w_i$ is integral over ${\bf K}[x]$ if and only if
each $a_i(x)w_i$ is. In other words there is no cancellation of
singularities from different summands. We would like our basis to have
the same property with respect to the local ring of ${\bf K}(x)$ at
infinity and we will characterize this by saying that such a basis is
{\sl Normal at infinity}.

We will need the concept of a {\sl local ring} at a place $p$ of the
function field ${\bf K}(x)$. The local ring at $p$ is defined as the
set of functions in ${\bf K}(x)$ that have no pole at $p$. If $p$ is a
finite place centered at $x = a$ then the local ring at $p$ consists
of rational functions whose denominators are not divisible by 
$x - a$. The order of a rational function at {\sl infinity} is the
degree of its denominator less the degree of its numerator. Thus the
local ring of ${\bf K}(x)$ at $\infty$ consists of those rational
functions whose numerator degree does not exceed their denominator
degree. A function in ${\bf K}(x,y)$ is said to be integral over the
local ring at $p$.  (for brevity integral at $p$) if it satisfies a
monic polynomial with coefficients in the local ring at $p$. Analogous
to the global integral basis, there exists a local integral basis at
each place $p$ of ${\bf K}(x)$ such that all functions in 
${\bf K}(x,y)$ that are integral at $p$ can be written as a linear
conmbination of basis elements with coefficients in the local ring at
$p$ of ${\bf K}(x)$. We will find it convenient to introduce the
slightly weaker concept of a normal basis. $[w_1,\ldots,w_n]$ is a
normal basis at $p$ if there exist rational functions 
$r_j \epsilon {\bf K}(x)$ such that $r_i w_i$ form a local integral
basis at $p$. In other words there exists rational scaling factors
that convert a normal basis into an integral basis.

Armed with this terminology we see that a basis is normal at infinity
if and only if some rational multiple of the basis elements is a local
integral basis at infinity. Let $[w_1,\ldots,w_n]$ be a basis for a 
${\bf K}[x]$ module. Assume we are given a local integral basis at
infinity $[v_1,\ldots,v_n]$. We wish to modify the original basis to
make it normal at infinity without disturbing its basis properties
everywhere else. We first represent the $w_i$ in terms of the $v_j$:
$$w_i = \sum_{j=1}^n M_{i j} v_j \ \ 
{\rm where} \ \ M_{i j} \epsilon {\bf K}(x)$$
If $w_i$ were a normal basis at infinity there would be rational
functions $r_i$ such that the change of basis matrix $r_i m_{i j}$
would have a determinant that was a unit in the local ring of
${\bf K}(x)$ at infinity, i.e. a rational function whose numerator has
the same degree as its denominator.

Define the representation order, $k(w_i)$ of $w_i$ at infinity as the 
$min_j ord_\infty M_{i j}$ for $1 \le j \le n$. We will initially
choose $r_i = x^{-k(w_i)}$. This guarantees that $r_i w_i$ is integral
at infinity and its representation order is $0$. Note that the order
at infinity of the determinant of ${\bf M}$ is always 
$\ge \sum k(w_i)$. We will show that our basis becomes normal when
these numbers are equal. Let ${\widehat {\bf M}}$ be the change of basis
matrix for $r_i w_i$. Each row of ${\widehat {\bf M}}$ is just $r_i$
times the corresponding row of ${\bf M}$. $r_i w_i$ is an integral
basis if and only if the determinant of ${\widehat {\bf M}}$ has order
zero at infinity. Since this determinant is integral at infinity, this
is equivalent to it having a non-zero value at infinity. Let ${\bf N}$
be a matrix where $N_{i j}$ is the value of ${\widehat M}_{i j}$ at
infinity. Since taking determinants commutes with evaluation, the
determinant of ${\bf N}$ equals the value of the determinant of 
${\widehat {\bf M}}$ at infinity. Thus $r_i w_i$ is a local integral
basis at infinity if and only if ${\bf N}$ has nonzero determinant. If
the determinant of ${\bf N}$ is zero then there are a set of constants
$c_i \epsilon {\bf K}$ such that $\sum_{i=1}^n c_i N_{i j} = 0$ for 
$1 \le j \le n$. Let $i 0 = i$ such that $c_i \ne 0$ and $k(w_i)$ is
minimal. Define
$${\hat w}_{i0} = \sum_{i=1}^n c_i x^{k(w_{i0}) - k(w_i)} w_i$$
Then replacing $w_{i0}$ by ${\hat w}_{i0}$ still yields a global
integral basis. Similarly replacing ${\widehat M}_{i0 j}$ by
$\sum c_i {\widehat M}_{i j}$ yields a row whose orders are strictly
positive. Thus the representation order $k({\hat w}_{i0})$ is strictly
greater than $k(w_{i0})$. The order of the determinant of the change
of basis matrix is preserved by our new basis. After a finite number
of such steps this order will be equal to the sum of the
representation orders of our basis elements and the basis will be
normal. 

We have shown how to make an arbitrary basis normal at infinity given
a local integral basis at infinity. We next show how to compute the
later. If we replace $x = 1/z$ then infinity gets transformed to zero
in the $z$-space. In order to compute a local integral basis at zero,
we can use the algorithm of the previous section after making one
optimization . In the local ring at $0$ any polynomial not divisible
by $z$ is a unit. Thus we can replace the discriminant by the maximal
power of $z$ dividing it. After computing this local integral basis,
we merely substitute $1/x$ for $z$ and obtain a local integral basis
at infinity.

\subsection{Genus Computation}

Our integral basis algorithm will also afford us an easy way to
compute the genus of a function field. The global discriminant divisor
of ${\bf K}(x,y)$ over ${\bf K}(x)$ is the product of the local
discriminant divisors over each place of ${\bf K}(x)$. As a by-product
of our integral basis computation, we have computed two discriminants,
a polynomial $disc_{finite}(x)$ that is the product of the
discriminants over all finite places of ${\bf K}(x)$ and a monomial in  
$z = 1/x$, $disc_{\infty}(1/x)$ that is the local discriminant at
infinity. The degree of the discriminant divisor of our function field 
${\bf K}(x,y)$ over ${\bf K}(x)$ is the sum of degree of 
$disc_{finite}(x)$ and the order at infinity of $disc_{\infty}(1/x)$. 
If we call this total discriminant degree $d$ and we assume that 
${\bf K}$ is the exact constant field of ${\bf K}(x,y)$, then the
genus of our function field ${\bf K}(x,y)$ can be computed by the
following formula giving in [22] p 134:
$$g = d/2-[{\bf K}(x,y):{\bf K}(x)]+1$$
\subsection{Simple Radical Extensions}
If ${\bf F}$ is a field with $y$ algebraic over ${\bf F}$ of degree
$n$ such that $y^n \epsilon {\bf F}$, then we will call ${\bf F}(y)$ a
simple radical extension of ${\bf F}$. If the characteristic of 
${\bf F}$ is relatively prime to $n$, then extending ${\bf F}$ if
necessary we can assume that ${\bf F}$ contains $\omega$ a primitive
$n^{th}$ root of unity. There is a unique differential automorphism of 
${\bf F}(y)$ over ${\bf F}$ such that $\sigma(y) = \omega(y)$. Define
the operator
$$T_i = {1\over n}\sum_{j=0}^{n-1} {{\sigma^j}\over{\omega^{i j}}}$$
Note that $T_i(y^j) = y^j$ if $i = j$ else $0$. Thus letting 
$g = \sum g_i y^i$ with $g^i \epsilon {\bf F}$, we have
$T_i(g) = g_i y^i$. Since $\sigma$ sends integral functions to
integral functions, and sums and products of integral functions are
integral, we have that the operators $T_i$ map integral functions to
integral functions. If $g$ is an integral function this shows that
each $g_i y^i$ must also be integral, which means that the basis $y^i$
is normal everywhere proving the following:
\begin{proposition}
If ${\bf K}(x,y)$ is a simple radical extension of ${\bf K}(x)$ of
degree $n$ relatively prime to the characteristic, then the natural
basis, $1,y,\ldots,y^{n-1}$ is normal everywhere.
\end{proposition}

Without loss of generality we can assume that $y$ satisfies the
following equation:
$$y^n = \prod_{i=0}^{n-1} p_i^i$$
where $p_i \epsilon {\bf K}[x]$ and has no repeated factors. Thus to
convert our natural basis into an integral basis we have to find
polynomials $d_i(x)$ of maximal degree such that 
${{y^i}/{d_i(x)}}$ is integral. Raising this expression to the
nth power implies that $\prod p_j^{i j}/d_i^n \epsilon {\bf K}[x]$.
It is easy to show that the maximal $d_i(x)$ is the following:
$$d_i = \prod_{j=0}^{n-1} p_j^{[i j/n]}$$
Thus the following functions provide an integral basis for our simple
radical extension:
$${y^i}\over {d_i(x)}$$
\section{Absolute Irreducibility}
We have assumed that the defining polynomial $f(x,y)$ for the
integrand $y$ is irreducible over ${\bf K}(x)$, but during the
integration process we may need to extend our coefficient field 
${\bf K}$, and over the extended field $f$ may no longer be
irreducible. In fact, in order to compute our bound for the ``points
of finite order'', we need to be able to guarantee that $f$ will
remain irreducible. Another difficulty is the precise determination of
our coefficient field. Initially we defined our coefficient field 
${\bf K}$ to be the minimal extension of ${\bf Q}$ necessary to
express the defining polynomial. Any element of our function field
that is algebraic over $k$ could also have been considered part of the
coefficient field. For example, if $f(x,y) = y^4 - 2x^2$ then 
$y^2/x$ is a $\sqrt{2}$ and thus algebraic over ${\bf Q}$. Note that
once we adjoin $\sqrt{2}$ to ${\bf K}$, $f$ is no longer irreducible
and $y$ satisfies a polynomial of degree 2 over this extended
coefficient field. It will be advantagious to make our coefficient
field as large as possible since that will decrease the degree of our
function field and thus speed up our computation time that is strongly
dependent on this degree. We now define the {\sl exact coefficient
field } ${\bf K}^0$ of ${\bf K}(x,y)$ to be the set of all elements of 
${\bf K}(x,y)$ that are algebraic over ${\bf K}$, also called the
relative algebraic closure of ${\bf K}$ in ${\bf K}(x,y)$. From the
previous example the existence of elements of ${\bf K}(x,y)$ that are
algebraic over ${\bf K}$ seems connected with the question of the
absolute irreducibility of $f(x,y)$. In the next section we will prove
that this is indeed the case and in fact the process for finding an
absolutely irreducible polynomial for $y$ will lead us to discover the
true coefficient field of ${\bf K}(x,y)$.

As the previous example seems rather contrived, one might be led to
suspect that defining polynomials that are irreducible but not
absolutely irreducible are quite rare in practice. This is indeed the
case, however the integral basis computation from the previous chapter
can be used to perform a quick test for absolute irreducibility. The
integral basis for that example is $1,y,y^2/x,y^3/x$. Note that the
first and third of these functions have no poles anywhere and thus
have divisor (1). As observed by Duval in [21] the dimension of the
multiples of the divisor (1) is the number of absolutely irreducible
components of the function field. Since we have already computed an
integral basis that is normal at infinity, we merely need to test how
many of our basis elements have no poles at infinity. If the answer is
one, we can skip the algorithm derived in this chapter, since we are
guaranteed that our defining polynomial is absolutely irreducible.

In this chapter we will permit ${\bf K}$ to be a perfect field of
arbitrary characteristic. As a consequence if ${\bf F}$ is any finite
algebraic extension of ${\bf K}$, it can be generated by a single
element and is thus a simple extension of ${\bf K}$, 
${\bf F} = {\bf K}(\alpha)$. Assuming that $f(x,y)$ is irreducible
over ${\bf K}$, we will present a new algorithm for performing
absolutely irreducible factorizations, i.e. factorization over the
algebraic closure of ${\bf K}$, ${\overline {\bf K}}$. The initial
difficulty is that all current algebraic factoring algorithms only
operate over a finitely generated field and the algebraic closure of 
${\bf K}$ is not finitely generated. Thus we must find some subfield
of ${\overline {\bf K}}$ that is finitely generated and is sufficient
for performing the factorization. Risch showed the problem was
decidable in [45] p. 178. His approach was to convert a multivariate
polynomial to a univariate one by the Kronecker substitution ([57]
p. 135).
$$f(x_1,x_2,\ldots,x_v) \mapsto f(t,t^d,\ldots,t^{v-1})$$
The key property of this substitution is that different power products
of the $x_i$ go into different powers of $t$ assuming $d$ is chosen
larger than the degree of any variable appearing in $f$. Risch argued
that the splitting field of this univariate polynomial suffices for
the factorization. Assuming the original polynomial had $v$ variables
each with maximum degree $d$ then his splitting field can be an
algebraic extension of degree $d^v!$, whereas the algorithm presented
below can test for absolute irreducibility or find an absolutely
irreducible factor by operating over an extension of degree $d_{min}$,
the minimum of the degrees of all the variables. By examining the
algebraic structure of the fields involved, we will also discover some
quick tests for absolute irreducibility.

\subsection{Exact Coefficient Fields and Regular Extensions}

First we will need some purely algebraic results (see also [52] pp 
194-198). All fields are assumed to be contained in some universal
field. If ${\bf E}$ and ${\bf F}$ are fields then ${\bf E}{\bf F}$
is the composition that is the field generated by 
${\bf E} \cup {\bf F}$. If ${\bf K}$ is a finite algebraic
extension of $k$ then $[{\bf K}:k]$ denotes the degree of this
extension. From the previous section we see that determining the exact
coefficient field requires us to find the relative algebraic closure
of one field in another. The next lemmas give some properties of such
fields. 
\begin{lemma}
If $x$ is transcendental over $k$ then $k$ is algebraically closed in 
$k(x)$.
\end{lemma}
\begin{proof}
Let $y$ be an element of $k(x)$ that is not in $k$. $y$ can be written
as $u(x)/v(x)$ with $u,v \epsilon k[x]$. Then $x$ satisfies the
polynomial $P(X) = u(X)-v(X)y$. If $P$ is not identically zero, this
implies $x$ is algebraic over $k(y)$. Let $u(X) = \sum u_i X^i$ and
$v(X) = \sum v_i X^i$ and choose $j$ such that $v_j \ne 0$. If $P$
were identically zero then $u_j-yv_j = 0$, but since 
$u_j, v_j \epsilon k$ this implies $y \epsilon k$ contrary to the
assumptions. Thus $x$ is algebraic over $k(y)$ and $y$ cannot be
algebraic over $k$.
\end{proof}
\begin{lemma}
Let ${\bf K} \supseteq k$ be fields with $k$ algebraically closed in 
${\bf K}$ and $k(\alpha)$ a simple algebraic extension of $k$. Then
$[{\bf K}(\alpha):{\bf K}] = [k(\alpha):k]$.
\end{lemma}
\begin{proof}
Any factor of the monic minimal polynomial for $\alpha$ over $k$ has
coefficients that are polynomials in the conjugates of $\alpha$ and
thus algebraic over $k$. If these coefficients were in ${\bf K}$ they
would also be in $k$ since the latter is algebraically closed in the
former. 
\end{proof}
\begin{corollary}
Let $x$ be transcendental over $k$ and ${\bf F}$ be a simple algebraic
extension of $k$, then $[${\bf F}$:k] = [${\bf F}$(x):k(x)]$.
\end{corollary}

We are looking for a defining polynomial for $y$ that is irreducible
over ${\overline {\bf K}}$. Factoring the bivariate polynomial $f$
over ${\overline {\bf K}}$ is exactly the same as factoring it over
${\overline {\bf K}}(x)$ by Gauss's lemma. If a perfect field $k$ is
algebraically closed in ${\bf K}$, then ${\bf K}$ is said to be a 
{\sl regular} extension of $k$. Thus the search for an absolutely
irreducible defining polynomial is equivalent to finding a
presentation of our function field as a regular extension of the
coefficient field. We have the following key theorem that connects our
twin problems of absolute irreducibility and exact coefficient fields.
\begin{theorem}
If $f(x,y)$ is irreducible over a perfect field $k$ then it is
absolutely irreducible if and only if $k$ is algebraically closed in
$k(x,y)$, i.e. $k = k^0$
\end{theorem}
\begin{proof}
$f$ is absolutely irreducible if and only if it is irreducible over
any finite algebraic extension ${\bf F}$ of $k$. We wish to prove that
$f$ is irreducible over any such ${\bf F}$ if and only if $k$ is
algebraically closed in $k(x,y)$.
$$[{\bf F}(x,y):k(x)]
     = [{\bf F}(x,y):{\bf F}(x)][{\bf F}(x):k(x)]
     = [{\bf F}(x,y):k(x,y)][k(x,y):k(x)]\eqno(1)$$
By corollary 3.3 $[{\bf F}(x):k(x)] = [{\bf F}:k]$ and using equation
(1) we have:
$$[{\bf F}(x,y):{\bf F}(x)] = [k(x,y):k(x)] \Longleftrightarrow
    [{\bf F}:k] = [{\bf F}(x,y):k(x,y)]\eqno(2)$$
$f(x,y)$ is irreducible over ${\bf F}$ if and only if 
$[{\bf F}(x,y):{\bf F}(x)] = [k(x,y):k(x)]$, and using equation (2) we
have $f$ is absolutely irreducible if and only if\\
$[{\bf F}:k] = [{\bf F}(x,y):k(x,y)]$ for any finite algebraic
extension ${\bf F}$ of $k$.

If $k$ is algebraically closed in k(x,y) then by lemma 3.1 
$[{\bf F}(x,y):k(x,y)] = [{\bf F}:k]$ for any such ${\bf
F}$. Conversely if $f$ is absolutely irreducible then choose ${\bf F}$
to be the algebraic closure of $k$ in $k(x,y)$. Thus
$[{\bf F}(x,y):k(x,y)] = 1$ since ${\bf F} \subseteq k(x,y)$. By
equation (2) we have $[{\bf F}:k] = 1$ showing that $k$ is in fact
algebraically closed in $k(x,y)$.
\end{proof}
\begin{corollary}
If $f(x,y)$ is irreducible over $k^0$, the algebraic closure of $k$ in
$k(x,y)$, then $f$ is absolutely irreducible.
\end{corollary}
\eject
\begin{proof}
$k^0$ is algebraically closed in $k^0(x,y) = k(x,y)$. Thus $f$ is
absolutely irreducible by the theorem.
\end{proof}

\noindent
Corollary 2 gives us a finitely generated field to factor over.

Note that we have also demonstrated that $[{\bf K}^0:{\bf K}]$ divides 
$[{\bf K}(x,y):{\bf K}(x)]$. Our choice of $x$ as the independent
variable and $y$ as algebraic over $x$ was somewhat arbitrary. If we
reverse the roles we see that $[{\bf K}^0:{\bf K}]$ must divide both
$deg_y f$ and $deg_x f$. So if these two numbers are relatively prime
then $f$ must be irreducible. More generally for an irreducible
multivariate polynomial, if the gcd of all the degrees appearing in
the polynomial is $1$, then it must be absolutely irreducible.
\subsection{Algorithmic Considerations}

Armed with these algebraic results, we return to the question of
finding an absolutely irreducible equation for $y$. We now realize
that ${\bf K}^0$ is the field we want to factor over, but we have no
explicit presentation of ${\bf K}^0$. We know that 
${\bf K}^0 \subseteq {\bf K}(x,y)$ with each element of ${\bf K}^0$
algebraic over ${\bf K}$. Since each element of ${\bf K}^0$ is
independent of $x$, we can also view ${\bf K}^0$ as a subfield of the
field ${\bf K}(u,w)$ where $w$ satisfies $f(u,w) = 0$. Again as in
chapter 2 without loss of generality we will assume that 
$f(X,Y) \epsilon {\bf K}[X,Y]$ is monic as a polynomial in $Y$.

The minimal polynomial of each element of ${\bf K}^0$ is monic with
coefficients in ${\bf K}$. Thus ${\bf K}^0[u]$ is certainly an
integral algebraic extension of ${\bf K}[u]$. Let ${\bf A}$ be the
integral closure of ${\bf K}[u]$ in ${\bf K}(u,w)$. Any factorization
of $f(x,y)$ with coefficients in ${\bf K}^0$ yields a factorization
with coefficients in ${\bf A}$. By the results of the last chapter any
element of ${\bf A}$ can be written as a polynomial in $u$ and $w$
divided by the discriminant of ${\bf K}[u,w]$ over ${\bf K}[u]$. This
discriminant is a polynomial in $u$ and is the same as the
discriminant of $f(u,w)$ viewed as a polynomial in $w$. The
discriminant of a monic polynomial is non-zero if and only if the
polynomial is square-free, i.e. has no repeated factors. Since we have
assumed that ${\bf K}$ is perfect, any irreducible polynomial over 
${\bf K}$ must be square-free and hence the discriminant of $f$ is
non-zero. 

If ${\bf K}$ is sufficiently large then we can find a 
$u_0 \epsilon {\bf K}$ such that $disc(f)$ doesn't vanish at 
$u = u_0$. Then the map sending $u$ to $u_0$ is a well defined
homomorphism from ${\bf A}$ onto a ring ${\bf B}$. ${\bf B}$ can be
presented as ${\bf K}[w]$ modulo $f(u_0,w)$. Let $f_1(w)$ be an
irreducible factor of $f(u_0,w)$ over ${\bf K}$. There is a natural
homomorphism from ${\bf B}$ onto the field 
${\bf B}_1 = {\bf K}[w]/(f_1(w))$. If we have a non-trivial
factorization of $f$ with coefficients in ${\bf A}$, then applying
both of the above homomorphisms we arrive at a non-trivial
factorization with coefficients in ${\bf B}_1$. Our choice of an
irreducible factor of $f(u_0,w)$ was arbitrary, so we may as well
choose the factor of least degree. In particular, if there are any
linear factors, then $f(x,y)$ must already be absolutely
irreducible. In any case, we have found a presentation for an
algebraic extension of ${\bf K}$ that contains ${\bf K}^0$. Note that
it was unnecessary to compute $disc(f)$ to verify our choice of
$u_0$. $Disc(f)$ is zero if and only if $f$ has a repeated
factor. Thus we pick successive values of $u_0$ until we find one such
that $f(u_0,y)$ remains square-free. If $m$ is the degree of $f$ in
$u$, then we must test at worst $2mn$ values until we find one that
works. 

We have justified the following algorithm for finding an absolutely
irreducible factor of a polynomial $f(x,y)$ whose discriminant with
respect to $y$ is nonzero and irreducible over a sufficiently large
field ${\bf K}$.
\begin{enumerate}
\item If $gcd(deg_x f,deg_y f) = 1$ then return $f(x,y)$
\item Find an $x_0$ in ${\bf K}$ such that $f(x_0,y)$ is square
free. (may fail if ${\bf K}$ is finite)
\item Factor $f(x_0,y)$ over ${\bf K}$ and let $f_1(y)$ be a factor of
least degree
\item If $f_1(y)$ is linear return $f(x,y)$
\item Else factor $f(x,y)$ over ${\bf K}[w]/(f_1(w))$ and return a
factor of minimal degree
\end{enumerate}

For the more general problem of finding absolutely irreducible factors
of multivariate polynomials, the same approach works. Step 0 is
changed to take the gcd of the degrees of all variables present, and
in step 1 we must find values for all variables but one such that the
resulting univariate polynomial is square free and the leading
coefficient doesn't vanish. We have assumed that ${\bf K}$ is large
enough so that we can find substitution points that leave $f$ square
free. This may fail if ${\bf K}$ is a finite field. In that case if we
let $m$ be the gcd of the degrees of all variables present, then we do
know that $[{\bf K}^0:{\bf K}]$ divides $m$. Thus ${\bf K}^0$ is a
subfield of the unique extension of ${\bf K}$ of degree $m$. It
therefore suffices to factor over that extension.

Once we have found an absolutely irreducible defining polynomial for
$y$, then we adjoin the coefficients of all the monomials to ${\bf K}$
and this generates ${\bf K}^0$ the exact coefficient field.

\subsection{Binomial Polynomials}

If $f(x,y)$ is of the form $y^n - g(x)$ then a much simpler algorithm
exists for obtaining an absolutely irreducible factorization. This is
based on the following theorem proven in [Lang] p.221.
\begin{theorem}
Let $k$ be a field and $n$ an integer $\ge 2$. Let $a \epsilon k$,
$a \ne 0$. Assume that for all prime numbers $p$ such that $p \vert n$
we have $a \not \in k^p$, and if $4 \vert n$ then 
$a \not \in -\ 4k^4$. Then $X^{n-a}$ is irreducible in k[X].
\end{theorem}
We define square-free factorization of a polynomial 
$g(x) \epsilon {\bf K}[x]$ to be 
$$g(x) = c \prod g_i^{e_i}\eqno(3)$$
where $c \epsilon {\bf K}$, $gcd(g_i,g_j) = 1$ for $i \ne j$, and each
$g_i$ has no repeated factors. If we assume that ${\bf K}$ is perfect,
then $g_i(x) \epsilon {\bf K}[x]$ for all $i$. This leads us to the
following simple algorithm for finding an absolutely irreducible
factor of $y^n = g(x)$.
\begin{enumerate}
\item Compute a square-free factorization of $g(x)$ as in equation
(3).
\item Let $d$ be the gcd of all the $e_i$ and $n$.
\item If $d = 1$ then $f$ is absolutely irreducible and return it.
\item An absolutely irreducible factor of $y_n - g(x)$ is
$$y^{n\over d} - c^{1\over d} \prod g_i^{{e_i}\over d}$$
\end{enumerate}
\section{The Rational part of Integral}
By Liouville's theorem if the integral of an algebraic function is
expressible in terms of elementary functions, it can also be written
as the sum of an algebraic function and constant multiples of logs of
algebraic functions. We will label the sum of logs the {\sl
transcendental part} of the integral and the rest the {\sl rational
part}. This terminology is carried over from rational function
integration. We use it since we want to draw strong parallels between
our algorithms for algebraic function integration and the well known
ones for rational function integration.
\subsection{Rational Function Integration}
There are primarily three basic algorithms for finding the rational
part of the integral of a rational function, however they all share a
common first stage. Polynomial division is employed to convert the
integrand into the sum of a polynomial and a proper rational
function. (Proper means the degree of the numerator is less than that
of the denominator). The polynomial part can be trivially integrated
termwise. At this point the three algorithms diverge.
\subsubsection{Full factorization}
The simplest algorithm conceptually completely factors the denominator
of the reduced integrand over the algebraic closure of the constant
field. If only approximations to the roots were used this algorithm
would be acceptable, but we want exact solutions and this requires
constructing the splitting field of the denominator. This construction
involves algebraic factoring and can be very expensive. Then a
complete partial fraction decomposition is performed. Each term in the
result is easy to integrate, but the result contains many algebraic
quantities. They are all unnecessary since the rational part of the
integral can always be expressed without extending the constant field,
but the task of trying to eliminate the algebraics can be costly. This
algorithm is close in spirit to the one proposed by Risch in [46] and
partially implemented by Davenport in [16]. The similarity becomes
more evident if we reexpress the algorithm in terms of power
series. The portion of the partial fraction expansion involving a
particular root of the denominator is identical to the principal part
(negative degree terms) of the power series expansion of the integrand
at that root. Thus the algorithm can be expressed as power series
computation and termwise integration. The additional step in Risch's
algorithm involves reconstruction of the rational part of the integral
from the principal parts of its expansion at all its poles. This is a
fairly complex process for an algebraic function, however a rational
function is simply determined up to an additive constant as the sum of
its principal parts.
\subsubsection{Linear equations}
Another algorithm for rational function integration was proposed by
Horowitz [30]. This approach is global as contrasted with the local
techniques used above. First a square-free factorization of the
denominator is performed. 
$$D = \prod D_i^i, gcd(D_i,D_j) = 1 {\rm \ for\ } i \ne j\eqno(1)$$
and each $D_i$ is square-free (has no multiple factors). By observing
that the integral of $(x-c)^{-k-1}$ is ${-(x-c)^{-k}}/k$, we see that
integration reduces the order of a pole by one. Thus
$$\int{A\over{\prod D_i^i}} 
   = {B\over{\prod D_i^{i-1}}} 
   + \int {C\over{\prod D_i}}$$
where the last integral produces the transcendental part. The degrees
of $B$ and $C$ are constrained since both are numerators of proper
rational functions. By letting $B$ and $C$ be polynomials with
undetermined coefficients, differentiating both sides of the above
equation and equating coefficients of the same powers of $x$ we get a
system of linear equations for the coefficients of $B$ and $C$. Since
the rational part of the integral is uniquely determined up to an
additive constant and we have constrained the constant by requiring a
proper rational function, the above system has a unique solution. This
method is relatively insensitive to sparseness in the input or output.
\subsubsection{Hermite's algorithm}
The third technique is due to Hermite [28]. It attempts to reduce the
``complexity'' of the problem using a succession of linear first
degree congruence equations. Again we start by performing a
square-free factorization of the denominator. But now instead of
trying to find the entire rational part in a single step, we will
repeatedly find pieces of the rational part that can be used to reduce
the multiplicity of the denominator of the integrand. The algorithm we
present here treats the factors of the denominator one at a time. Mack
[39] presents a variant that treats all the factors at once, but his
algorithm would only make our formulas more complicated, and the
underlying theory is essentially the same.

Again we assume a square-free factorization of the denominator of the
integrand as in (1). Let $V = D_{j+1}$ for some $j>0$, i.e. $V$ is a
multiple factor of the denominator. Let $U$ be the cofactor of $V$, 
$U = D/V$. By (1) $U$ and $V$ are relatively prime and we can write
the integral as
$$\int {A\over{UV^{j+1}}}dz$$
We will attempt to repeatedly reduce the multiplicity of the
denominator while constructing portions of the final answer. We claim
that there exist polynomials $B$ and $C$ such that
$$\int {A\over{UV^{j+1}}}
   = {B\over{V^j}} 
   + \int {C\over{UV^j}}$$
After differentiating both sides and multiplying by $UV^{j+1}$ we get
$$A = UVB^{\prime} - jBUV^{\prime} + VC$$
This is a differential equation with two unknowns so it would seem
that we have made the problem more complicated. We will additionally
claim, however, that there is a unique solution $B$ such that 
$deg(B)<deg(V)$. We then reduce the equation modulo $V$. This
eliminates the $B^{\prime}$ and $C$ terms from the above equation and
we are left with
$$A \equiv - jBUV^{\prime}{\rm \ mod\ }V\eqno(2)$$
This equation will indeed have a unique solution as long as $j \ne 0$
and $gcd(V,V^{\prime}) = 1$. But $V$ is square-free by construction so
the latter requirement is satisfied. As long as $j>0$ we can find a
unique $B$ solving (2) and then subtracting $(B/V^j)^{\prime}$ from
the integrand will reduce the mulitiplicity of the denominator. By
repeating this process with all multiple factors of the denominator,
we see that the integral of any rational function can always be
expressed as the sum of a rational function and an integral whose
denominator has multiplicity one. The latter integral has no rational
part, i.e. it is expressible exclusively as a sum of logs.
\subsection{Algebraic Functions}
We choose to base our algorithm for finding the rational part of the
integral of an algebraic function on Hermite's method for rational
function integration. In fact all three of the algorithms presented in
the previous section can be generalized to handle algebraic
functions. The generalization of the first approach requires Puiseux
expansions and algebraic number computations that we wish to
avoid. The advantage of the third approach over the second is that we
are provided with insight into how an integral may fail to be
elementary and its step by step reductive nature will often allow us
to return partial results instead of returning ``not integrable''.

To simplify matters we will transform the integral so that there are
no poles or branch points at {\sl infinity}. We assume an integral of
the form $\int \sum R_i(x)y^i/Q(x) \ dx$ where $R_i$ and $Q$ are
polynomials and $y$ satisfies $f(y,x)=0$. Let $a$ be an integer that
is neither a root of $Q$ nor a root of the discriminant of $f$. We can
``move'' the point $a$ to $\infty$ by defining $z = 1/(x - a)$ or 
$x = a + 1/z$. Our new integral is
$$\int \sum {{R_i(a+1/z)y^i}\over{Q(a+1/z)}} ( - z^{-2}) dz$$
After performing the integration we can apply the inverse
transformation to express the answer in terms of $x$ instead of
$z$. If we let $m$ be the degree of $f$ in $x$, then the transformed
minimal polynomial for $y$ is $g(y,z)=z^m f(y,a+1/z)$. Using the
results of the last chapter, we can find a basis, 
$[w_1,\ldots,w_n]$ for the integral closure of ${\bf K}[z]$ in 
${\bf K}(z,y)$. In terms of this basis the integrand can be expressed
as $\sum A_i(z)w_i/D(z)$ where $D$ and $A_i$ are polynomials. Since
this integrand has no poles at $\infty$, $deg(A_i(z))<deg(D(z))$ for
all $i$.

We now attempt to imitate Hermite's algorithm for rational
functions. Again we start by performing a square-free factorization of
the denominator $D(z)$ yielding $D = \prod D_i^i$. Let $V = D_{k+1}$
for some $k>0$ and $U = D/V$. Following Hermite's algorithm we might
now look for polynomials $B_i$ and $C_i$ such that
$$\int \sum A_i {{w_i}\over{UV^{k+1}}} dz
   = \sum B_i {{w_i}\over{V^k}}
   + \int \sum C_i {{w_i}\over{UV^k}} dz\eqno(3)$$
Unfortunately we won't be able to find them in general without
additional restrictions on $U$. The difficulty is caused by the fact
that $y^{\prime}$ has a non-trivial denominator. Hermite depended on
the fact that the derivative of a polynomial is a polynomial, but this
is not necessarily true for algebraic functions. If $y$ satisfies 
$f(y,z) = 0$ then we can find $y^{\prime} = dy/dz$ by taking the total
derivative of the defining polynomial.
$${{\partial f}\over{\partial y}}dy 
+ {{\partial f}\over{\partial z}}dz = 0$$
$${{dy}\over{dz}} = 
   - {{\partial f / \partial z}\over
      {\partial f / \partial y}}$$
Thus $y^{\prime}$ is a rational function in $y$ and $z$. Similarly 
$w_i^{\prime}$ in general has a nontrivial denominator. Let $E$ be the
least common denominator of $w_i^{\prime}$ for all $i$. Then the
derivative of the second term in (3) will in general have $E$ as a
factor of its denominator. This will force us to permint $E$ to be a
factor in the denominator of the third term. We want to use (3)
iteratively; this means the third term on one iteration will become
the first term for the next iteration. Therefore we may as well assume
the denominator of the first term is also divisible by $E$. In the
last iteration $k = 1$ making the denominator of the third term $UV$,
so our additional restriction on equation (4) is that $E \ \vert \ UV$. 
We can always guarantee this by multiplying the $A_i$ and $U$ by a
suitable factor of $E$. Note that there is then an uncanceled gcd
between the numerator and denominator of the first term in (3). We
need to be sure that the new $U$ is still relatively prime to
$V$. This can only be guaranteed if we know $E$ to be
square-free. Fortunately that is always the case.
\begin{lemma}
If $v_p w \ge 0$ and $v_p (z - a) > 0$ 
then $v_p (z - a) w^{\prime} > 0$
\end{lemma}
\begin{proof}
$v_p w \ge 0$ implies $v_p d w \ge 0$, and $v_p (z - a) > 0$
implies $v_p (z - a) = v_p dz + 1$. ([Chev51] IV.8 Lemma 1)
But $dw = w^{\prime} dz$ and thus 
$0 \le v_p w^{\prime} dz < v_p (z - a) w^{\prime}$.
\end{proof}

We therefore begin with equation (3) with the following conditions:
$$E \ \vert \ UV, gcd(U,V) = 1, gcd(V,V^{\prime}) = 1\eqno(4)$$
Now as before we perform the differentiation and multiply through by
$UV^{k+1}$ yielding
$$\sum A_i w_i = U \sum \left( VB_i^{\prime} + B_iV^{k+1}
                         {\left({{w_i}\over{V^k}}\right)}^{\prime}
                        \right) + V \sum C_i w_i \eqno(5)$$
We then reduce the equation modulo $V$.
$$\sum A_i w_i = \sum B_i UV^{k+1}
    \left({{w_i}\over{V^k}}\right)^{\prime} \ {\rm mod} \ V\eqno(6)$$
We must show that this equation always has a unique solution. This is
equivalent to showing that the 
$S_i = UV^{k+1} \left( {{w_i}\over{V^k}} \right)^{\prime}$
is a local integral basis, i.e. any integral function can be expressed
as a linear combination of them with rational function coefficients
and denominator relatively prime to $V$. There are two ways this can
fail, either the $S_i$ are not linearly independent over ${\bf K}(z)$
or there exists an integral function whose representation requires a
factor of $V$ as a denominator. Since the former case implies that
zero is a nontrivial linear combination of the $S_i$, both cases may
be summarized by saying there exists an integral function that can be
represented as
$${{1}\over{V}} \sum T_i UV^{k+1}
       \left({{w_i}\over{V^k}}\right)^{\prime}
{\rm \ where \ }V
{\rm \ does\ not\ divide\ }UT_i
{\rm \ for\ some\ }i\eqno(7)$$ 
For purposes of generating a contradiction we assume that the $S_i$ do
not form a local integral basis and thus there exists an integral
function (7). We can add $\sum (UT_i)^{\prime} w_i$ to equation (7)
yielding a new integral function $G$ such that 
$$G = \sum V^k \left( (UT_i)^{\prime} {{w_i}\over{V^k}}
    + UT_i \left({{w_i}\over{V^k}}\right)^{\prime}\right)
    = V^k \sum \left( UT_i {{w_i}\over{V^k}}
               \right)^{\prime}\eqno(8)$$ 
Assuming that such an integral function $G$ exists implies there
exists a function for whom differentiation doesn't increase the order
of its poles; this is the source of the contradiction. Let 
$F = \sum UT_i w_i/V^k$. The restriction on the $T_i$ in (7) says that a
smaller value of $k$ would be insufficient, i.e. there is some place
$p$ such that $v_p F < v_p(1/V^{k-1})$ and $v_p V > 0$ where $v_p$ is
the order function at $p$.
\begin{lemma}
If $u$ is a nonzero function such that $v_p u \ne 0$ and $p$ is a
finite place (not over $\infty$) then 
$v_p u^{\prime} = v_p u - r$ where $r$ is the ramification index of
$p$ with respect to ${\bf K}(z)$.
\end{lemma}
\begin{proof}
We embed our function field in its $p$-adic completion and let $t$ be
a uniformizing parameter at $p$. We can then write
$$u = \sum_{i=j}^{\infty} c_i t^i$$
The coefficients in the series are algebraic over our constant field
and we can extend our derivation $d/dt$ uniquely to the completion
yielding: 
$$u^{\prime} = \sum_{i=j}^{\infty} i c_i t^{i-1} t^{\prime}$$
Since $j \ne 0$, $v_p u^{\prime} - j - 1 + v_p t^{\prime}$. Since $p$
is a finite place, the $p$-adic expansion of $z$ begins 
$z - a_0 + a_1 t^{\prime} + \cdots$ where $a_r \ne 0$ so 
$v_p (dz/dt) = r - 1$. Thus 
$v_p t^{\prime} = v_p(dt/dz) = 1 - r$ and
$v_p u^{\prime} = (j - 1) + (1 - r) = j - r$.
\end{proof}

\noindent
Since $V$ is a square-free polynomial in $z$ and $v_p V > 0$ we have
$v_p V = r$ and thus $v_p(1/V^k) = v_p(1/V^{k-1}) - r$. If $k > 0$
then $v_p F < v_p(1/V^{k-1})$ implies $v_p F < 0$. Using lemma 2 we
see that $v_p F^{\prime} < v_p(1/V^{k-1}) - r = v_p(1/V^k)$. But
according to equation (8) $F^{\prime}$ can be written as $G/V^k$ where
$G$ is an integral function. This contradicts the fact that 
$v_p F^{\prime} < v_p(1/V^k)$. Thus the $S_i$ do indeed form a local
integral basis, and equation (6) will have a unique solution modulo
$V$ as long as $k > 0$. 

By our choice of $E$ there must exist polynomials $M_{i j}$ such that
$$Ew_i^{\prime} = \sum_j M_{i j} w_j$$
Since $E\ \vert \ UV$ let $TE = UV$ for some polynomial $T$.
$$UVw_i^{\prime} = TEw_i^{\prime} = T \sum_j M_{i j} w_j\eqno(9)$$
Substituting (9) into equation (6) yields:
$$\sum_i A_i w_i \equiv
  \sum_i ( - kUV^{\prime}B_i ) w_i +
  \sum_i B_i T \sum_j M_{i j} w_j {\rm \ mod\ }V\eqno(10)$$
If we now equate the coefficients of $w_i$ on both sides of (10) we
get a set of linear congruence equations with $B_i$ as unknowns.
$$A_i \equiv - kUV^{\prime}B_i 
      + T \sum_j B_j M_{j i}{\rm \ mod\ }V\eqno(11)$$
We have shown that this system will always have a unique solution for 
$k > 0$. Thus the determinant of the coefficient matrix must be
relatively prime to $V$ and the system can always be solved,
e.g. using Cramer's rule.

For efficiency reasons it is important to recognize when the system
(11) decouples, i.e. each equation involves only one unknown. When
$V \ \vert \ T$ the summation in (11) vanishes and we are reduced to
solving a succession of equations of the form
$$A_i \equiv - kUV^{\prime}B_i {\rm \ mod \ }V$$
This case of algebraic integration is almost exactly the same as in
rational function integration. $V \ \vert \ T$ if and only if 
$gcd(V,E) = 1$. Thus it can become worthwhile to split $V$ into two
factors, one that divides $E$ and one relatively prime to $E$ and
treat each case separately.

The other situation in which the system decouples is when the matrix
$M_{i j}$ in (9) is diagonal. This means that 
$w_i^{\prime} = R_i w_i$ where $R_i$ is a rational function in $z$. We
can solve this differential equation, and the solution will be an
algebraic function if and only if $m_i^m \epsilon {\bf K}(z)$
[49]. Thus the matrix can be diagonal if and only if ${\bf K}(z,y)$ is
a compositum of single rational extensions.
\subsection{Poles at Infinity}
Repeated application of the reductions presented in the previous
section will leave us with an integral whose denominator is
square-free. One might hope that we have removed all singularities
from the integrand except those that should be cancelled by log terms
as in the rational function case. Unfortunately while we have been
reducing the order of the finite poles, we may have introduced poles
at $\infty$. In this section we will prove that if our basis is normal
at infinity the presence of such poles will prove that the original
problem was non-integrable.

The problem is caused by the second term in equation (3), 
$B= \sum B_i w_i / V^k$. By contruction we have the restriction that 
$deg(B_i) < Deg(V)$. Thus at each iteration of the previous algorithm,
the coefficients of the answer produced will be proper rational
functions, i.e. the degree of the numerator is less than the degree of
the denominator. This guarantees that the rational function
coefficients of the portion of the answer we have produced will have
positive order at $\infty$, but the $w_i$ themselves will in general
have poles at $\infty$. We will see that if this algebraic portion of
the answer has poles at infinity, then the original problem was not
integrable. 
\begin{lemma}
If $u$ is a nonzero function such that $v_p u \ne 0$ with $p$ a place
over $\infty$, then $v_p u^{\prime} = v_p u + r$ where $r$ is the
ramification index of $p$.
\end{lemma}
\begin{proof}
The proof is identical to Lemma 4.2 except that $v_p t^{\prime}$ is
different. The $p$-adic expansion of $z$ is 
$z = a_{-r} t^{-r} + \cdots$ so $v_p(dz/dt) = - r - 1$. Thus
$v_p t^{\prime} = v_p(dt/dz) = r + 1$ and
$v_p u^{\prime} = (v_p u - 1) + (r + 1) = v_p u + r$.
\end{proof}
\begin{lemma}
If $u$ is a nonzero function such that $v_p u \ne 0$ at some place
$p$, then $v_p du = v_p u - 1$.
\end{lemma}

Let us assume that the third term in equation (3) has poles at
infinity. Since the original integrand had zero residue at infinity,
and the derivative of any algebraic function has zero residue
everywhere this third term must also have zero residue at
infinity. Thus if it has poles there, they must be at least double
poles. If this term is integrable it must be expressible as an
algebraic function and a sum of constant multiples of logs. This
algebraic function can not have any finite poles, since the integrand
has only simple poles in the finite plane. Thus this algebraic
function must be expressible as a polynomial multiple of our basis
element $w_i$. Since this function has a pole at infinity, either one
of the coefficients is a polynomial of positive degree, or some
non-constant basis element has a non-zero coefficient. Although the
second term in equation (3) could also have poles at infinity, when we
add these functions those poles do not cancel. The coefficients of the
basis elements in the second term are all proper rational functions,
i.e. the degree of the numerator is less than the degree of the
denominator. This is a consequence of the fact that $deg(B_i)<deg(V)$
since each $B_i$ is computed modulo V. When we add this polynomial
multiple of our basis elements to the second term, we arrive at a
function with at least one coefficient that is an improper rational
function. If this coefficient has a pole at infinity then the function
itself has a pole at infinity since the basis is normal at infinity
and no basis elements have zeros at all places over infinity. If none
of the coefficients have poles at infinity, then some non-constant
basis function must have a coefficient of order zero at infinity. But
since any non-constant basis function must have a pole at infinity,
both possibilities imply the complete algebraic part of the integral
must have a pole at infinity. But by Lemma 4.4 this would imply
that the integrand would have a pole at infinity that contradicts our
initial assumption. Thus we see that if in the process of finding the
algebraic part, we introduce poles at infinity then the original
problem was not integrable and there is no need to try to remove these
poles. We have demonstrated the following theorem and corollary:
\begin{theorem}
If $gdx$ is a differential with zero residues and no poles at
infinity, then the algorithm of the previous section computes a
function $h$ such that $(g - h^{\prime})dx$ has no finite poles and is
zero if $gdx$ was integrable.
\end{theorem}
\begin{corollary}
If $gdx$ also has non-zero residues then $(g - h^{\prime})dx$ has only
simple poles in the finite plane and has no poles at infinity if $gdx$
was integrable.
\end{corollary}
\section{Log terms and Divisors}
In this chapter we will present algorithms for finding the logarithmic
or transcendental part of the integral. Using the results of the
previous chapter we can assume that the rational part has been removed
and the integrand has been reduced to a differential with only simple
poles. Using Liouville's theorem we know that if the integral is
expressible as an elementary function, then it can be written as
$$\int R(x,y)dx = \sum c_i {\rm \ log\ } v_i(x,y)\eqno(1)$$
where $c_i \epsilon {\bf K}^{\prime}$ and
$v_i \epsilon {\bf K}^{\prime}(x,y)$ with ${\bf K}^{\prime}$ a finite
algebraic extension of ${\bf K}$. To find the rational part of the
integral no extension of the ground field was necessary, but the same
is not true for the logarithmic part. We will show that the residues
of the integrand generate the unique ${\bf K}^{\prime}$ of minimal
degree over ${\bf K}$ sufficient to express the answer. Additionally
these residues provide us with clues about the orders of the poles and
zeros of the $v_i$.
\subsection{Properties of Logarithmic Differentials}
We will start by examining the relationship between 
$f \epsilon {\bf K}(x,y)$ and the differential ${{df}\over{f}}$. We
are interested in the local behavior at a place $p$ with $t$ as a
uniformizing parameter. If a function $f$ has order $k$ at $p$ then
$f = t^k g$ where $g$ is a function whose value at $p$ is finite and
nonzero. Any differential $fdg$ can be written as $hdt$ where
$h = f{{dg}\over{dt}}$. The order at $p$ of the differential $fdg$ is
defined to be the order of the function $h$ above. The residue at $p$
of the differential $hdt$ is the coefficient of the $t^{-1}$ term in
the series expansion of $h$ in powers of $t$. Both the residue and the
order of a differential are independent of the choice of uniformizing
parameter. 

Next we examine the properties of differentials of the form 
${{df}\over{f}}$ at a place $p$ with local uniformizing parameter $t$. 
If $f$ has order $k$ at $p$ it can be written as $f = t^k g$ for some
function $g$ of order $0$ at $p$ and similarly the differential can be
rewritten as 
$${{df}\over{f}} = k{{dt}\over{t}} + {{dg}\over{g}}$$
As shown in chapter four, since $g$ has no pole at $p$, $dg$ must have
non-negative order at $p$ also. By construction $g$ has order $0$ at
$p$ and thus ${{dg}\over{g}}$ has non-negative order at $p$. Since $t$
is a local uniformizing parameter at $p$ the order of
$k{{dt}\over{t}}$ is the same as the order of ${{k}\over{t}}$ that is
precisely $-1$ as long as $k$ is nonzero. Similarly the residue of
${{df}\over{f}}$ is always greater than or equal to $-1$, and its
residue at any place $p$ is the same as the order of $f$.

This leads to a solution to a special case of our original
problem. When can a differential be expressed in the form
${{df}\over{f}}$ for some function $f$ in our function field? The
following two necessary properties give quick failure tests:
\begin{enumerate}
\item The order of the differential must be greater than or equal to
-1 everywhere
\item The residues must all be integers since they correspond to the
orders of the desired function $f$.
\end{enumerate}
If a differential passes those tests, then we try to determine if
there exists a function whose order at every place is equal to the
residue of the differential at that place. Thus the residues of the
differential provide us with a formal specification of the location
and orders of the poles and zeros of the desired function. Since the
differential only has a finite number of poles, it can only have
nonzero residue at a finite number of places. A divisor is a formal
integer linear combination of places that has a finite number of
non-zero coefficients. Divisors that correspond to the orders of the
poles and zeros of actual functions are called principal divisors. A
differential with integer residues everywhere immediately provides us
with a divisor and we are left with the problem of determining whether
or not it is principal. An algorithm for answering this question will
be presented later in this chapter.

The solution to the problem discussed in the previous paragraph leads
to some compuational dificulties, but no great theoretical problems.
But if we generalize things slightly we arrive at a problem that many
mathematicians around the turn of the century worked on but were
unable to solve. In fact Hardy even went so far as to state ``there is
reason to believe that no solution exists''. The generalization
involves introducing one additional constant coefficient. Instead of
asking whether a given differential can be expressed as
${{df}\over{f}}$, we allow one more degree of freedom and try to
express it as $1/m{{df}\over{f}}$ for some integer $m$. By the same
reasoning as above we see that if we multiply all the residues of the
original differential my $m$ we arrive at the desired divisor for
$f$. But we don't know the value of $m$. This is the source of the
theoretical difficulty. We derive a divisor from the residues of the
integrand and we can test whether or not it is principal. If it is
then we are done. If it is not, however, perhaps by scaling all the
orders specified by two, we arrive at a principal divisor. If not try
scaling by three, \ldots etc. The real difficulty is knowing when to
stop. More formally given a divisor $D$ we need to be able to
determine a bound $M$ such that if for all positive integers
$j < M$, $jD$ is not principal, then we are guaranteed that there
exists no multiple of $D$ that is principal. It is only in the last
thirty years that a solution to the problem has been discovered using
the technique of good reduction from algebraic geometry. Basically the
original coefficient field is reduced to a finite field. There each
divisor has finite order, i.e. there is some finite value of $j$ such
that $jD$ is principal. This information is used to limit the
potential set of $j$'s that needs to be examined. We will present this
construction in the next chapter.

Armed with some intuition from the previous special cases, we will now
investigate the fully general problem indiciated by equation (1). We
wish to write the given differential as
$$R(x,y)dx = \sum c_i {{dv_i}\over{v_i}}\eqno(2)$$
for some constants $c_i$ and some rational functions $v_i(x,y)$. As
indicated earlier the constants $c_i$ and the coefficients of the
$v_i$ will in general lie in a finite algebraic extension 
${\bf K}^{\prime}$ of the field of constants of the original function
field. Our first step involves the construction of the minimal
extention of ${\bf K}$ sufficient to express the answer.

The decomposition of the $R(x,y)dx$ indicated by equation (2) is
certainly not unique. In fact let $b_j$ be another set of constants
such that each $c_i$ can be expressed as integer multiples of the
$b_j$, $c_i = \sum n_{i j} b_j$. Define new functions 
$w_j = \prod_i v_i^{n_i j}$ then:
$$\sum_i c_i {{dv_i}\over{v_i}} = \sum_j b_j {{dw_j}\over{w_j}}$$
Since a linear dependence among the coefficients implies we can
express the sum with fewer terms, the answer with the smallest number
of summands will have coefficients that are linearly independent over
the rationals.

We next investigate the relationship between the coefficients of the
log terms and the residues of the integrand. Since the residues of
${{dv}\over{v}}$ is always an integer for any function $v$, we see
that the residues of the integrand are always integer linear
combinations of the $c_i$'s. Thus the coefficients of the log terms
generate a ${\bf Z}$-module that contains all the residues of the
integrand. We will show that the $c_i$'s can be chosen so that they
generate the same vector space over the rationals that the residues of
the integrand do. Let $a_j$ form a basis for the vector space
generated by the residues. Let $b_k$ extend this basis to include the
coefficients of the log terms. Thus each $c_i$ can be written uniquely
as $\sum r_{i j} a_j + \sum s_{i k} b_k$ where the $r_{i j}$ and 
$s_{i k}$ are rational numbers. We will in fact assume the $r_{i j}$
and $s_{i k}$ are integers, which can be accomplished by suitably
scaling the basis elements. Then as shown in the previous paragraph,
we can construct functions $w_j$ and $u_k$ such that:
$$\sum c_i {{dv_i}\over{v_i}} 
 =\sum a_i {{dw_i}\over{w_i}}
 +\sum b_k {{du_k}\over{u_k}}\eqno(3)$$
Since however the $a_j$'s form a basis for the vector space containing
all the residues of the entire sum and the $b_k$'s and the $a_j$'s
form a linearly independent set by construction, the residues of each 
${{du_k}\over{u_k}}$ must be zero everywhere. This implies that each
$u_k$ has order zero everywhere, is thus a constant. Since the
differential of any constant is zero, the second sum in equation (3)
is identically zero.

We have shown that if a differential has a decomposition as in
equation (2), it has one where the coefficients form a basis for the
vector space spanned by the residues of $R(x,y)dx$. If we compute such
a basis $r_i$, then by lemma 1 [ambiguous in original text - tpd], we
are guaranteed that there exists integers $n_i$ such that 
${{r_i}\over{n_i}}$ can be chosen as the coefficients of the log
terms. Let ${\bf K}^{\prime}$ be ${\bf K}$ extended by all the
residues of the integrand. Assume we have found a representation for
the integrand $fdx$ as a sum of logarithmic differentials, 
$\sum c_i {{dv_i}\over{v_i}}$. We have shown that we can assume the
coefficients of the log terms $c_i$ lie in ${\bf K}^{\prime}$. We wish
to show that we can also assume that the 
$v_i \epsilon {\bf K}^{\prime}(x,y)$. If instead 
$v_i \epsilon {\bf E}(x,y)$ where ${\bf E}$ is a finite algebraic
extension of ${\bf K}^{\prime}$ of degree $j$ then by applying a trace
from ${\bf E}$ to ${\bf K}^{\prime}$, 
$tr_{{\bf E}\over{{\bf K}^{\prime}}}$ we arrive at a solution whose
constant field is exactly ${\bf K}^{\prime}$.
$$fdx = \sum c_i {{dv_i}\over{v_i}}$$
$$tr(fdx) = \sum tr(c_i {{dv_i}\over{v_i}})$$
Since $f \epsilon {\bf K}(x,y)$, $tr(fdx) = jfdx$ and $tr(d/v)$ is the
same as $d(Nv)/(N v)$ where N is the norm from ${\bf E}$ to 
${\bf K}^{\prime}$.
$$jfdx = \sum c_i {{dNv_i}\over{Nv_i}}$$
But $Nv$ is a rational function with coefficients in 
${\bf K}^{\prime}$, so we have shown if the integral can be expressed
over some algebraic extension of ${\bf K}$ then in fact it can be
expressed over the extention of ${\bf K}$ generated by the residues of
the integrand, and no smaller extension will suffice.
\subsection{Computing the Residues}
Now that we have demonstrated the importance of the residues of the
integrand, we need an efficient way to compute these residues. If the
differential is expressed in the form $fdt$ where $t$ is the local
uniformizing parameter for some place $p$, then the residue was
defined to be the coefficients of $t^{-1}$ in the series expansion of
$f$ at $p$. If $f$ is known to have order greater than or equal to
$-1$ at $p$, then we can just compute the value of $tf$ at $p$. Thus
we need to be able to find local uniformizing parameters for places,
and be able to compute the value of functions at places. We can view
the Riemann surface associated with the differential as a multisheeted
covering of the complex ${\bf X}$-plane. Thus each finite place $p_0$
can be associated with some x-value $x_0$ by projection. The order of
the line of projection at a place defines the branch index of that
place. Branch places are those where the line of projection is tangent
to the Riemann surface and thus have branch index greater than
one. Since $x = x_0$ is the equation of the line of projection from
$p$ to the ${\bf X}$-plane, the order of the function $x-x_0$ at $p$
is equal to the branch index of $p$. If $p$ is not a branch place,
$x-x_0$ has order 1 and can thus be used as a local uniformizing
parameter. 
\begin{theorem}
Let $fdx$ be a differential with order greater than or equal to $-1$
at some place $p$ with branching index $r$ centered at $x_0$. The
residue of $fdx$ at $p$ is equal to the value of the function 
$r(x-x_0)f$ at $p$.
\end{theorem}
\begin{proof}
Let $t$ be a uniformizing parameter at $p$. Since $x-x_0$ has order
$r$ at $p$, it can be written as 
$$x-x_0 = t^{\prime} g\eqno(5)$$
where $g$ has order zero at $p$
$$dx = (r t^{r-1} g + t^r {{dg}\over{dt}})dt$$
Since $dg/dt$ has non-negative order at $p$, $dx$ has order $r-1$ at
$p$ and $f$ must have order greater than or equal to $-r$ at $p$
$$fdx = r t^{r-1} fgdt + t^r f({{dg}\over{dt}})dt\eqno(6)$$
the second term on the right side of equation (6) is holomorphic at
$p$ so the residue of $fdx$ at $p$ is the same as the residue of the
first term on the right side of (6). By the argument of the preceding
paragraph, this residue can be computed by evaluating the function
$rt^{\prime}fg$ at $p$. Using equation (5) this function can be
written as $r(x-x_0)f$.
\end{proof}
\begin{theorem}
Let $fdx$ be a differential with at most simple poles in the finite
plane. Let $D(x)$ be a polynomial whose roots include the
x-projections of the poles at $f$. Let $g = fD$, then $gdx$ is
holomorphic in the finite plane and the residue of $fdx$ at any place
$p$ with branch index $r$ centered over a root of $D(x)$ is equal to
the value of $rg/D^{\prime}$ at that place.
\end{theorem}
\begin{proof}
Since $fdx$ has only simple poles in the finite plane, $gdx$ has no
finite poles. Let $p$ be a place over a root $x_0$ of $D(x)$. From the
previous theorem we only need to show that at $p$ 
$(x-x_0)f = {{g}\over{D^{\prime}}}$. Let $D(x)=(x-x_0)C(x)$. Then
since $f = {{g}\over{D^{\prime}}}$, $(x-x_0)f={{g}\over{C}}$. But
$D^{\prime} = C + (x-x_0)C^{\prime}$ and thus 
$D^{\prime}(x_0) = C(x_0)$ at $p$.
\end{proof}

We could use the previous theorem to compute separately each residue
of the integrand, but it will be more convenient to find them all at
once. We will construct a polynomial whose roots are rational
multiples of the residues of the differential $fdx$. $f$ is in general
a rational function of $x$ and $y$. After rationalizing the
denominator we can assume $f(x,y) = g(x,y)/D(x)$ where $g$ and $D$ are
polynomials. Let $Z$ be a new indeterminate and define 
$R(Z) = \prod Z D^{\prime} - g$ where the product is taken over all
places centered above the roots of $D$. The roots of $R$ are the
residues of $fdx$ divided by the branch orders. Since the branch
orders are always positive integers, the splitting field of $R$ is
precisely the minimum extension of ${\bf K}$ containing all the residues 
of the integrand, and thus the smallest extension of the coefficient
field in which the integration can be performed. Similarly a ${\bf Q}$-basis
for the roots of $R$ provides us with a ${\bf Q}$-basis for the residues. A
key observation is that $R$ can be computed without extending the
coefficient field. Let $F(x,y) = 0$ be the defining polynomial of our
function field. For a particular value of $x$, $x_0$, 
$\prod Z D^{\prime}(x_0) - g(x_0,y)$ taken over all places sitting
over $x_0$ is just the 
$resultant_Y (ZD^{\prime}(x_0) - g(x_0,Y),F(x_0,Y))$ 
both viewed as polynomials in $Y$. Extending that product over all
roots $x_0$ of $D$ is just another resultant of the previous result
with $D(x)$, both viewed as polynomials in $X$. Thus we can compute
$$R(Z) =resultant_X(resultant_Y(ZD^{\prime}(X)-g(X,Y),F(X,Y)),D(X))
  \eqno(7)$$

Since the roots of $R$ are nonzero rational multiples of the residues,
the splitting field of $R$ is the minimal extension containing all the
residues. We have found $R$ using only rational operations over 
${\bf K}$ but to actually compute the log terms we will have to work
in a coefficient field that contains all the roots of $R$. [55] gives
an algorithm for computing the splitting field of $R$ using algebraic
factoring. This step can be very expensive, since if $R$ has degree
$n$ the splitting field may be of degree $n$ factorial. However there
is no escaping this expense since this is the smallest extension in
which the answer can be expressed.

We next need to compute a basis for the vector space spanned by the
roots of $R$ over the rationals. If the coefficients of $R$ are all
rational numbers, then we can view the splitting field of $R$ as a
vector space over the rationals. Each root is thus a vector with
rational coefficients, and we are interested in finding a basis for
the space spanned by these vectors. This can be done using standard
techniques from linear algebra. In general however the coefficients of
$R$ will come from some finitely generated extension of ${\bf Q}$. This
occurs when the integrand contains additional parameters or algebraic
numbers. Let ${\bf K}$ be the field generated by the coefficients of
$R$. The splitting field of $R$ is a vector space over ${\bf K}$ and
thus each root of $R$ is representable as a vector of elements of
${\bf K}$ with respect to some chosen basis of the splitting field
over ${\bf K}$. We need to view these roots as elements of a finite
dimensional vector space over ${\bf Q}$. We will do this by replacing each
coefficient from ${\bf K}$ by a finite dimensional vector over
${\bf Q}$. Let $b_i$ be a basis for the splitting field of $R$ over 
${\bf K}$. Then the roots of $R$ can be represented as 
$r_j = \sum c_{i j} b_j$ where $c_{i j} \epsilon {\bf K}$. The
$c_{i j}$ will in general be rational quantities but by a different
choice of basis elements we can guarantee they are polynomials in the
generators of ${\bf K}^{\prime}$ over ${\bf K}$. Let $d_i$ be a common
denominator for the $i$th components of all the vectors, i.e. for 
$c_{i j}$ with fixed $i$. If we choose as a new basis for 
${\bf K}^{\prime}$ over ${\bf K}$, $b_i/d_i$ then with respect to this
basis all the coefficients will be polynomials. Now we have
represented the roots as vectors of multivariate polynomials with
rational coefficients. If we choose a basis for the set of monomials
appearing in these polynomials, then with respect to the tensor
product of this monomial basis and the original basis of
${\bf K}^{\prime}$ over ${\bf K}$, our roots are expressible as
vectors of rational numbers and can thus be viewed as elements of a
finite dimensional vector space over ${\bf Q}$. At this point we apply
gaussian elimination to this collection of vectors adjoined to an
identity matrix, to find a minimal basis over ${\bf Q}$, and the rational
linear equations expressing all the roots in terms of this basis set.
\subsection{Constructing Divisors}
The basis for the residues over ${\bf Q}$ become our candidates for
coefficients of the log terms. They are only candidates since they may
be integer multiples of the correct coefficients. For each candidate
we next proceed to compute an associated divisor. The minimum multiple
of this divisor that is principal will provide us with the appropriate
scaling of the candidate coefficient. We first need to construct a set
of building blocks from which we will construct our divisors. For each
root of $R$ we will construct a divisor that has order one at each
place where the integrand has that root as residue, and order zero
elsewhere. 

We assume the integrand is of the form $(G(x,y)/D(x))dx$ as above. In
order to simplify matters we will also assume that all places centered
above roots of $D$ are not branch places. In the next section we will
show how to convert the general problem to satisfy this
restriction. Under this assumption the roots of $R$ are precisely the
residues of the integrand, and at any place above the root $x_0$ of
$D$, $x-x_0$ is a local uniformizing parameter. By theorem 5.2
$G/D^{\prime}$ is a function whose value over all places centered
above roots of $D$ is the residue of the integrand. Let $r$ be a root
of $R$, then $G/D^{\prime}-r$ is a function that vanishes wherever the
integrand has residue equal to $r$ and at other places above roots of
$D$, has a nonzero value. Define $B(x)=D(x)/gcd(D,D^{\prime})$. Then
$B$ contains all factors of $D$ taken with multiplicity one.
\begin{proposition}
The minimum of the orders of $B(x)$ and $G-rD^{\prime}$ at any finite
place $p$ is equal to one if the integrand has residue $r$ at $p$ and
zero otherwise.
\end{proposition}
\begin{proof}
If the integrand has residue $r$ at $p$ then $G-rD^{\prime}$ vanishes
at $p$ and $B(x)$ vanishes to order one at $p$. If $p$ is any place
over a root of $D$ where the integrand has residue different from $r$
then $G-rD^{\prime}$ has order zero at $p$. If $p$ is a finite place
not centered over a root of $D$ then $B(x)$ has order zero at $p$.
\end{proof}

If our function field had unique factorization we would proceed by
computing the greatest common divisor of $B(x)$ and $G-rD^{\prime}$
and use these to build our divisors. But unless the function field
happens to have genus $0$, we are not guaranteed that the notion of
gcd is well defined. We will work instead with the ideal generated by
these two functions over the ring of integral algebraic functions. In
a gcd-domain this ideal would have a single generator but not in
general. 

Now that we have created these ideal building blocks, we need
algorithms for multiplication and division. In general a set of
generators for the product of two ideals can be computed simply as the
set cross products of generators from one times generators from the
other. This means that the product of two ideals with $m$ and $n$
generators respectively will require $mn$ generators. Our primitive
building blocks have only two generators, and we will first show how
this property can be maintained under multiplication and division.

First we will modify our building blocks slightly. We define the
support of a divisor as the set of places in the divisor with nonzero
order. Our building blocks are of the form $[h(x,y,r),B(x)]$. We know
that the zeros of $h$ at places over roots of $B$ coincide with the
zeros of the desired divisor, but $h$ can have zeros of multiplicity
greater than one, which is compensated in the ideal by the fact that
$B$ has only zeros of order one. Our first step is to modify $h$ so
that it has only simple zeros. This can be done by adding a random
integer multiple of $B$ to $h$. For all but a small finite number of
choices, this will produce an $h$ with only simple zeros at places
over the roots of $B$. To complete this step we only need a test to
guarantee our random integer was not ``unlucky''. The norm of $h$ is a
polynomial in $X$ whose degree is the sum of the order of the finite
zeros of $h$. For any chosen integer $j$ we can compute 
$N(x)=Norm(h+jB)$. We can split write $N=N_1 N_2$ where $N_2$ is the
part of $N$ that is relatively prime to $B$. We wish to choose $j$ so
that $N_1$ has as small a degree as possible. When this is done, the
degree of $N_1$ will be the same as the number of places where the
integrand had residue $r$ that is the same as the multiplicity of $r$
in $R(x)$. Thus $j$ is ``lucky'' as long as degree $N_1$ is the same
as the multiplicity of $r$ in $R(x)$.

Now we have divisor descriptions of the form $(h(x,y,r),A(x))$ for
divisor $D$ and satisfying the following properties:
\begin{enumerate}
\item order($h$) = order($D$) at all places over the roots of the
$A(x)$ 
\item order($D$)$=0$ at all other places
\item both $h$ and $A$ are multiples of $D$ except at infinity
\end{enumerate}
$(h,A)$ can be viewed as a locally principal model of the divisor $D$
since at any place either the order($D$)$=$order($h$) or 
order($D$)=order($A$). Given two such descriptions
$(h_1(x,y),A_1(x))$ for divisor $D_1$ and
$(h_2(x,y),A_2(x))$ for divisor $D_2$, where the support of $A_1$
equals the support of $A_2$ we claim the description 
$(h_1,h_2,A_1,A_2)$ is of the same form for divisor $D_1 D_2$.

Quotients of divisors are slightly more complicated. $h_1/h_2$
satisfies property 1 but not necessarily property 3. It may have
extraneous poles outside the support of $D_1$ and $D_2$. These can be
removed by rationalizing its denominator and removing any factors that
are relatively prime to $A_1$ or $A_2$. If we let $h_3$ be this
normalization of $h_1/h_2$ whose finite poles are all above $A_1$ or
$A_2$, then $(h_3,A_1,A_2)$ satisfies all three properties for the
divisor $D_1/D_2$.

Now that we have the basic building blocks, and the simple algorithms
for multiplying and dividing them, we are ready to construct the
divisors associated with each of the residue basis elements. Let $b_1$
be the $i$th basis element. Each root $r_j$ of $R(x)$ can be
represented uniquely as an integer linear combination of the basis
elements $r_j = \sum c_{i j} b_i$. Also each $r_j$ can be associated
with the set of places $P_j$ where the integrand had residue equal to
$r_j$. The divisor $D_i$ associated with basis element $b_i$ is
defined at $\prod P_j^{c_{i j}}$. We have seen how to represent $P_j$
as the basic building block associated with $r_j$, and we now
construct $D_i$ as appropriate products and quotients of the
$P_j$. This gives us a computable representation for the divisors
associated with our candidate logands. In the next chapter we will see
how to determine if there is some multiple of these divisors that are
principal and thus whose generators will furnish us with the desired
log terms.
\subsection{Dealing with Branch Places}
In the previous section we assumed that the branch places of the
function field did not lie above any of the poles of the integrand. We
now will show how to bring the integrand into this form. If the
integrand involves only a single unnested radical, then we claim this
assumption is guaranteed. In this case the defining polynomial for our
function field is of the form $Y^n = F(x)$. The integrand can be
written as $(\sum G_i(x) Y^i) dx$. As shown in the appendix, this is
integrable if and only if each summand is. Thus we are reduced to
integrands of the form $G(x)Ydx$ with possibly a different choice of
$Y$. We can also assume without loss of generality that $F(x)$ is a
polynomial whose roots all have multiplicity less than $n$. In this
case the finite branch places occur precisely at the places above the
roots of $F$. We claim that the integrand cannot have a nonzero
residue at any branch place. If $p$ is a branch place centered above a
root $x_0$ of $F$ with branch index $r$, then the order of $G(x)$ must
be a multiple of $r$ and the order of $dx$ is precisely $r-1$. But the
order of $Y$ is some positive integer $j$ less than $r$. In order for
the integrand to have a simple pole at $p$, we must have
$k*r+r-1+j= -1$. But this equation implies $j$ is divisible by $r$
contrary to our assumption. Thus with simple radicals we never have
nonzero residues at branch places.

In the more general situation we have to change our model of the
function field to achieve this condition. Branch places occur when the
line of projection from our defining curve down to the $x$-axis is
tangent to the curve. By a different choice of independent variable we
change tangency points and thus arrive at a different set of branch
points. For each pole of our integrand, there are only a finite number
of projection directions that are tangent to the curve. If we replace
$X$ by $X = mY$ for some random integer $m$ then for almost all
choices of $m$, the resulting function field will not have branch
places above any of the poles of our integrand. This can be checked by
computing the discriminant of an integral basis for the new
presentation of the function field. The branch places all lie above
roots of this discriminant so we wish to choose $m$ such that the
integrand has zero residue at all places above zeros of the
discriminant. If we let $D(x)$ be this new discriminant and let 
$g = fD(x)$ where $fdx$ is the integrand, then equation (7) computes
the residues of the integrand over all roots of $D(x)$. We then check
that $R(Z)$ has no non-zero roots, i.e. is a pure monomial in $Z$.
\section{Principal Divisors and Points of Finite Order}
In this chapter we will present a decision procedure for computing the
log term associated with each element of a ${\bf Q}$-basis for the
residues. In chapter five we showed how to construct a reduced divisor
that described the pole zero ratios for the desired log term. We need
to be able to test whether there exists some multiple of this divisor
that corresponds to an actual function in ${\bf K}^{\prime}(x,y)$.

We will first present an algorithm for determining whether the given
divisor is principal, i.e. is the divisor of a function in 
${\bf K}^{\prime}(x,y)$. If this algorithm succeeds then we are done,
but if not we need to try multiples of this divisor. If each of these
tests fails then we need to know when we can stop, i.e. when we are
guaranteed that there is no multiple of this divisor that is principal.
\subsection{Principal Divisors}
We start with a divisor description of the form $(h(x,y),g(x))$. This
describes a divisor whose order at places over $\infty$ is $0$, and
whose order at all other places is the minimum of the orders of
$h(x,y)$ and $g(x)$. We wish to determine if the divisor is principal,
i.e. if there is a single function that has exactly the same orders as
this divisor at all places in our function field. In particular such a
function is a multiple of our divisor, and we will base our
construction on the following proposition and corollary:
\begin{proposition}
Let $h_1,\ldots,h_k$ be functions and $D$ be a divisor such that 
${{min}\atop{i}} ord_p h_i = ord_p D$ at all finite places. Then the
ideal generated by $h_i$ over the ring of integral functions coincides
with the multiples of $D$ except at infinity.
\end{proposition}
\begin{proof}
This is a restatement of the isomorphism between fractional ideals in
an algebraic function field and multiples of divisors ignoring places
at infinity. [22]
\end{proof}

Using the proposition we see that our desired principal generator will
be an integral linear combination of $h(x,y)$ and $g(x)$. Every such
linear combination will be a multiple of $D$ except at infinity but
most of them will have poles at infinity. If we can find one that has
no poles at infinity then it will be a multiple of $D$
everywhere. Since the degree of $D$ is zero, any such function must
have orders exactly equal to those specified by $D$ and is thus
uniquely determined up to a scaling by a constant. This proves the
following:
\begin{corollary}
If $D$ is a divisor of degree $0$ with no places at infinity, and 
$h_1,\ldots,h_k$ are as in the proposition, then $D$ is principal if
and only if the ideal generated by the $h_i$ has an element with no
poles at infinity.
\end{corollary}

In chapter 2 we showed how to compute an integral basis 
$[w_1,\ldots,w_n]$ for our function field. Any integral multiple of
$g(x,y)$ can thus be written as $\sum a_i w_i g$ where 
$a_i \epsilon {\bf K}[x]$. Thus we can rewrite our ideal as the 
${\bf K}[x]$-module generated by 
$(w_1 g, \ldots, w_n g, w_1 h, \ldots, w_n h)$. We need to determine
whether this module contains a function that has no poles at
infinity. If we have a ${\bf K}[x]$-module basis for our ideal that is
normal at infinity then a linear combination of basis elements is
integral at infinity if and only if each summand is. Since each
summand is a polynomial times a basis element and a polynomial can
never have a zero at infinity, if the ideal contains a function with
no poles at infinity, one of the basis elements must have no poles at
infinity. Thus after computing a normal basis for our ideal, we only
have to check whether any of the basis elements have no poles at
infinity.
\begin{theorem}
If $D$ is a divisor of degree zero with no places at infinity, then $D$
is principal if and only if a normal basis for the ideal of multiples
of $D$ except at infinity has an element that is regular at infinity.
\end{theorem}
\subsection{Good Reduction}
The algorithm in the previous section will enable us to determine
whether any given divisor is principal, but we need to know whether
there is some power of the divisor that is principal. This problem
that was thought to be insoluable in the early 1900's will be solved
by the technique of ``good reductions''. Function fields in one
variable whose constant fields are finite fields have the property
that any divisor of degree zero has some power that is principal. Thus
if we start testing the successive powers of a divisor, we are
guaranteed that this process will terminate. Repeated applications of
the algorithm in the previous section will enable us to determine the
minimum power of any divisor that is principal. Thus we need to be
able to reduce the constant field of our function field to a finite
field in such a way that we can calculate the order of a divisor from
the order of its image.

If we assume the defining polynomial for our function field $f(x,y)$
is monic in $y$ and has integer coefficients, then its coefficients
can be reduced module $p$, a prime integer. As long as the reduced
polynomial remains irreducible, it defines a function field over the
finite field ${\bf Z}/p$. If the genus of the reduced field is the
same as the original then we will say that our original field has
``good reduction'' modulo p. It can be shown [22] for any particular
defining polynomial, $f(x,y)$, ${\bf Q}(x,y)$ has good reduction at
all but finitely many primes.

More generally if we have a discrete valuation of our coefficient
field, we can choose a defining polynomial for our function field that
is monic and such that all of its coefficients are contained in the
valuation ring. Then we can apply the natural homomorphism to the
residue class field of the valuation. If the resulting polynomial
remains absolutely irreducible and the genus of the reduced field is
unchanged, then we say we have ``good reduction'' at that
valuation. Again we will have good reduction at ``almost all''
valuations. In the rest of this chapter when we say reduction modulo
$p$, we mean reduction by a discrete valuation of the constant field,
which extends the natural $p$-adic valuation of the rationals.

If we have good reduction then there is a homomorphism between the
group of divisors of ${\bf K}(x,y)$ and their images. Since principal
divisors map to principal divisors, we in fact have a homomorphism of
the quotient group of divisors module principal divisors. Let $D$ be a
divisor of ${\bf K}(x,y)$ that has finite order $n$, i.e. such that
$D^n$ is principal. If $n$ is relatively prime to the characteristic
of the reduced field then a consequence of good reduction is that the
order of the image of $D$ under the reduction is also $n$. This is a
consequence of the key theorem observed by Risch [47] and Dwork and
Baldassarri [4] that makes ``good reduction'' useful.
\begin{theorem}
The homomorphism between divisor class groups under good reduction is
an isomorp