\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)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))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) 1$. Thus we can continue this reduction
process until $k = 1$.
\subsubsection{Case 2: $C/(W^k y)$ where $W = P_j$}
Since $W$ divides $f$ we must start with an apparent denominator of
the form $W^k y$. Letting $h = f/W$ we have
$$\left({{B f}\over{W^k y}}\right)^\prime =
{{B g - k W^\prime h}\over{W^k y}} +
{{B^\prime h}\over{W^{k-1} y}}$$
Thus we want to choose $B$ such that
$B g - k W^\prime h \equiv C\pmod{W}$. $W = P_j$ implies
$g \equiv (1 - e_j/n)W^\prime h \pmod{W}$. Thus we have
$B(1-k-e_j/n)W^\prime h \equiv C \pmod{W}$. Since $W^\prime h$ is
relatively prime to $W$ and $e_j < n$, this equation is solvable for
any $k$. Thus by repeated applications of this reduction step we can
eliminate all factors of $f$ from the denominators of our integrands.
\subsubsection{Case 3: $C/y$}
Here we will try to find a $B$ such that the reduced integrand has
lower degree. Let $B = b_j\theta^j$, with $b_j \epsilon {\bf F}$.
$$(b_j \theta^j f/y)^\prime =
b_j^\prime \theta^j f/y +
j b_j \theta^{j-1} \theta^\prime f/y +
b_j \theta^j g/y\eqno(2)$$
Letting $m = deg f$ we have two subcases depending on whether $d$ is
constant or not. If $d^\prime = 0$ then $degree(g) = m-1$ else
$degree(g) = m$. Let $C = \sum c_i \theta^i$.
We will first assume that $d^\prime = 0$. If $b_j^\prime=0$ then
equation (2) has degree $j+m-1$ else degree $j+m$. Thus equating
formally highest degree terms we obtain:
$$c_{j+m} = (j+1)b_{j+1} \theta^\prime +
b_{j+1}lcf(g) + b_j^\prime\eqno(3)$$
where $b_{j+1}$ is a constant. Lcf(g) is the leading coefficient of
$g$.
$$lcf(g) = \sum(1-e_i/n)lcf(P_i^\prime)$$
If $P_i = \theta^k + a_i \theta^{k-1} + \ldots$ then
$lcf(P_i^\prime) = k \theta^\prime +a_i^\prime$. If
$\theta^\prime = 1$ then equation (3) reduces to:
$$c_{j+m} = (j + 1 + \sum deg(P_i)(1-e_i/n))b_{j+1}\eqno(4)$$
If $j+1 \ge 0$ then the coefficient of $b_{j+1}$ will always be
nonzero. Thus we can always reduce $C$ until $deg(C) < m - 1$.
If $\theta = log(v)$ then equation (3) takes the form
$$c_{j+m} = b_{j+1}((j+1){{v^\prime}\over{v}} +
\sum (1-e_i/n)(deg(P_i) {{v^\prime}\over{v}} + a_i^\prime)) +
b_j^\prime\eqno(5)$$
The coefficient of $b_{j+1} v^\prime / v$ in equation (5) is precisely
the coefficient of $b_{j+1}$ in equation (4) and is therefore nonzero
if $j+1 \ge 0$. If the original problem is integrable then $c_{j+m}$
must be integrable. Just as in [45] $b_{j+1}$ is uniquely determined
since $\theta$ is a monomial over ${\bf F}$ while $b_j$ is determined
up to an additive constant. In this case we can reduce $C$ until
$deg(C) < m - 1$ only if either the original problem is integrable or
at least the necessary set of coefficients are integrable.
We will now treat the subcase where $d^\prime$ is nonzero. Note that
we must have $\theta = log(v)$ for this to hold. Here we must first
assume that there is no constant $s$ such that $sd$ has an $n^{th}$
root in ${\bf F}$. If there is such an $s$ then we can pick a new
generator $y(sd)^{-1/n}$ for $G$ that puts us back in the previous
subcase. Otherwise we have $deg(g) = deg(f)$ and after equating
leading terms we have
$c_{k+m} = b_k^\prime - {{d^\prime}\over{nd}} b_k$.
Our assumption about $d$ guarantees that this equation can have at
most one solution in ${\bf F}$. Thus we need to be able to solve first
order linear differential equations for a solution in ${\bf F}$. If
${\bf F}$ is a tower of monomial extensions then [45] shows how to do
this. If all the equations we set up have solutions we will reduce $C$
so that $deg(C) < m$.
\subsubsection{Case 4: $\theta = exp(v)$}
The distinguishing characteristic of the exponential function is that
it is a factor of its derivative. Thus we can no longer claim that a
square-free polynomial must be relatively prime to its derivative. It
will only be necessary to treat factors of the form $\theta^k$
specially. We begin by rewriting the square-free decomposition of
$P$. $P = d \theta^j \prod P_i^{e_i}$ where no $P_i$ is divisible by
$\theta$. We will again define $f = \prod P_i$, noting that now $f$ is
not divisible by $\theta$. We next verify that $(f/y)^\prime$ still is
of the form $g/y$ for some $g \epsilon {\bf F}[\theta]$.
$$\left({{f}\over{y}}\right)^\prime =
{{f}\over{y}}\left(\sum (1-e_i/n){{P_i^\prime}\over{P_i}}
- j/nv^\prime - {{d^\prime}\over{nd}}\right)
= {{g}\over{y}}$$
After performing a partial-fraction decompostion of the integrand, we
can deal with all denominators other than $\theta$ just as in the
previous cases. Thus we will now assume an integrand of the form
$C/(\theta^k y)$, and we again write $C = \sum c_i \theta^i$. We are
again trying to decrease $k$ and letting $B$ be an arbitrary
polynomial we compute:
$$\left({{Bf}\over{\theta^k y}}\right)^\prime =
{{B^\prime f + B g - k v^\prime B f}\over{\theta^k y}}$$
Requiring the numerator to be congruent to $C$ modulo $\theta$ is the
same as equating constant terms.
$$c_0 = b_0^\prime f_0 + b_0 g_0 - k v^\prime b_0 f_0$$
$f$ not divisible by $\theta$ implies $f_0$ is nonzero, thus we can
divide through by $f_0$. Again $\theta$ a monomial will force this
equation to have at most one solution in ${\bf F}$ for $k \ge 0$. As
long as the equation continues to have solutions, we can reduce $k$ to
$0$.
Finally we must deal with integrands of the form $C/y$ in the
exponential case. Here $deg(g) = deg(f)$ always, and we again assume a
solution of the form ${{B f}\over{y}}$ and equate leading terms.
$$c_{k+m} = b_k^\prime + k v^\prime b_k + b_k lcf(g)\eqno(6)$$
$$lcf(g) = {{-j}\over{n}} v^\prime - {{d^\prime}\over{n d}} +
\sum (1 - e_i/n)deg(P_i) v^\prime$$
Equation (6) will have at most one solution as long as the
coefficients of $v^\prime$ is nonzero. This coefficient is
${{k-j}\over{n}} + \sum (1 - e_i/n)deg(P_i)$. Since the third term is
always positive, $k > 0$ or if $j = 0$ then $k \ge 0$ is sufficient to
guarantee the $v^\prime$ is present in equation (6).
\subsection{Summary and Conclusions}
The reduction formulae in section 2 have enabled us to find the
rational part of our integral if it exists. If the original problem
was integrable, all the remaining integrands must generate the
transcendental portion of the integral. Note that cases 1 and 2 will
always reduce any integrand whether it be integrable or not. In
particular, for the case $\theta^\prime = 1$ we see that any integral
can be reduced to $\int A/(B y)$ where $B$ is square-free and
$deg(A) - deg(B) < deg(f) - 1$.
We have shown that the question of computing integrals in
${\bf F}(x,y)$ can be reduced to the problems of computing integrals
in ${\bf F}$ and that of solving first order linear differential
equations over ${\bf F}$. If ${\bf F}$ was constructed as a tower of
monomial extensions, then [45] shows that these problems are solvable.
We claim that the algorithms presented here form a natural extension
to those presented in [45]. By restricting ourselves to this special
but very important case, we are able to generate the integral using
nothing more than simple polynomial arithmetic. Although our formulas
are somewhat complicated, we require no additional machinery than
those necessary in Risch's original approach. [45] We have not worked
out the details of the logarithmic part of the integral, but the
techniques introduced in chapters 5 and 6 of this thesis should be
generalizable to deal with this situation. The major problems involve
dealing with poles at infinity which were finessed by a change of
variables in the purely algebraic case. The restriction to unnested
radicals guarantees no simple poles at branch places as in the purely
algebraic case. Formulae for the residue at infinity similar to
equation (7) of Chapter 5 are needed. The fact that the principal
parts of a function now only determines it up to a function in one
fewer variables instead of up to a constant could cause some
additional difficulty. We have presented what we hope are very usable
practical algorithms, and we intend to implement them in the near
future.
\begin{thebibliography}{99}
\bibitem{1} Abhyankar, Sheeram, ``Historical Ramblings in Algebraic
Geometry and Related Algebra,'' {\sl Amer. Math. Monthly}, Vol. 83, 6
(1976) pp. 409-448
\bibitem{2} Atiyah, M.F., and MacDonald, I.G., {\sl Introduction to
Commutative Algebra}, Addison Wesley Pub. Co., Reading, Massachusetts,
(1969)
\bibitem{3} Artin, Emil, {\sl Algebraic Numbers and Algebraic
Functions}, Gordon and Breach, N.Y., (1967)
\bibitem{4} Baldassarri, F. and Dwork, B., ``On second order linear
differential equations with algebraic solutions,'' {\sl American
Journal of Mathematics}, Vol. 101, 1 (1979) pp 42-76.
\bibitem{5} Barsotti, I., ``Varieta Abeliane su Corpi p-adici; Parte
Prima,'' {\sl Symposia Mathematica}, Vol. 1, (1968) pp 109-173
\bibitem{6} Berry, T.G., ``On Coates Algorithm,'' {\sl Sigsam
Bulletin}, Vol. 17, 2 (1983) pp 12-17.
\bibitem{7} Bliss, G.A., {\sl Algebraic Functions}, Dover, (1966),
first published as AMS Colloquium vol. XVI (1933)
\bibitem{8} Bois, G. Petit, {\sl Tables of Indefinite Integrals},
Dover, N.Y., (1961)
\bibitem{9} Cassels, J.W.S., ``Diophantine Equations with Special
Reference to Elliptic Curves,'' {\sl Journal of the London
Math. Society}, vol 41, (1966) pp 193-291
\bibitem{10} Chevalley, Claude, {\sl Algebraic Functions of One
Variable}, Math. Surveys Number VI, American Math. Society, N.Y.,
(1951)
\bibitem{11} Chou, Tsu-Wu Joseph, {\sl Algorithms for the Solution of
Systems of Linear Diophantine Equations}, Ph.D. thesis, University of
Wisconsin, (1979)
\bibitem{12} Chow, Wei-Liang, ``On the Principle of Degeneration in
Algebraic Geometry,'' {\sl Annals of Mathematics}, Vol 66, No. 1,
pp. 70-79, (1957)
\bibitem{13} Chow, W.-L., Lang, S., ``On the Birational Equivalence of
Curves under Specialization,'' {\sl American Journal of Math.},
Vol. 79, pp 649-652, (1957)
\bibitem{14} Coates, J., ``Construction of rational functions on a
curve,'' {\sl Proc. Camb. Phil. Soc.}, Vol 68, pp. 105-123, (1970)
\bibitem{15} Cohn, Harvey, {\sl A Classical Invitation to Algebraic
Numbers and Class Fields}, Springer-Verlag, N.Y., (1979)
\bibitem{16} Davenport, James, {\sl On the Integration of Algebraic
Functions}, Lecture Notes in Computer Science No 102, Springer-Verlag,
N.Y., (1981)
\bibitem{17} Davenport, James, {\sl Integration Formelle}, (1983)
\bibitem{18} Davenport, J. and Singer, M., Private communication, (1984)
\bibitem{19} Deuring, Max, ``Reduktion algebraischer Funktionenkorper
nach Primdivisoren des Konstantenkorpers,'' Math. Zeit. 47,
pp. 643-654 (1941)
\bibitem{20} Dieudonne, J., ``The Historical Development of Algebraic
Geometry,'' {\sl American Mathematical Monthly}, Vol. 79, 8
pp. 827-866 (1972)
\bibitem{21} Duval, Dominique, {\sl Une methode geometrique de
factorization des polynomes en deux indetermines}, Institute Fourier,
Grenoble, (1983).
\bibitem{22} Eichler, Martin, {\sl Introduction to the Theory of
Algebraic Numbers and Functions}, Academic Press, N.Y., (1966)
\bibitem{23} Ford, David James, {\sl On the Computation of the Maximal
Order in a Dedekind Domain}, Ph.D. thesis, Ohio State University,
Depart. of Mathematics, (1978)
\bibitem{24} Fulton, William, ``Hurwitz schemes and irreducibility of
moduli of algebraic curves,'' {\sl Annals of Mathematics}, vol 90,
pp. 542-575 (1969)
\bibitem{25} Hardy, G.H., {\sl The Integration of Functions of a
single variable (2nd ed.), Cambridge Tract 2}, Cambridge U. Press,
(1916)
\bibitem{26} Hartshorne, Robin, {\sl Algebraic Geometry},
Springer-Verlag, (1977)
\bibitem{27} Hasse, Helmut, {\sl Number Theory}, Springer-Verlag
(1980)
\bibitem{28} Hermite, E., ``Sur l'integration des fractions
rationnelles,'' {\sl Nouvelles Annales de Mathematiques}, 2 Ser.,
11(1872) pp. 145-148
\bibitem{29} Herstein, I.N., {\sl Topics in Algebra} Blaisdell,
Waltham, Mass., (1964)
\bibitem{30} Horowitz, E., {\sl Algorithms for Symbolic Computation of
Rational Functions}, Ph.D. Thesis, U. of Wisconsin, (1970)
\bibitem{31} Jacobson, Nathan, {\sl Basic Algebra II}, W.H. Freeman
and Co., San Francisco, (1980)
\bibitem{32} Katz, Nicholas, ``Galois Properties of Torsion Points on
Abelian Varieties,'' {\sl Inventiones Mathematicae}, vol 62,
pp. 481-502 (1981)
\bibitem{33} Lang, Serge, {\sl Algebra} Addison-Wesley, Reading,
Mass., (1971)
\bibitem{34} Lang, Serge, {\sl Algebraic Number Theory},
Addison-Wesley, Reading Mass., (1970)
\bibitem{35} Lang, Serge, {\sl Introduction to Algebraic Geometry},
Addison-Wesley, Reading, Mass., (1958)
\bibitem{36} Lang, S. and Tate, J., ``Principal Homogeneous Spaces
over Abelian Varieties,'' {\sl American Journal of Mathematics}, pp
659-684 (1960)
\bibitem{64} LeVeque, William J. {\sl Elementary Theory of Numbers}
Addison-Wesley (1962)
\bibitem{37} Liouville, J., ``Premier Memoire sur la Determination des
Integrales dont la Valeur est Algebrique,'' {\sl Jounal de l'Ecole
Polytechnique}, Vol. 22, (1833) pp 124-148
\bibitem{38} Lichtenbaum, Stephen, ``Curves over Discrete Valuation
Rings,'' {\sl American Journal of Mathematics}, Vol. 90, pp 380-405,
(1968)
\bibitem{39} Mack, D., {\sl On Rational Integration}, Computer Science
Dept. Utah Univ., UCP-38, 1975
\bibitem{40} Matsuda, Michihiko, {\sl First Order Algebraic
Differential Equations}, Lecture Notes in Mathematics, No. 804,
Springer-Verlag, (1980)
\bibitem{41} Moses, Joel, ``Symbolic Integration, The Stormy Decade,''
{\sl Communications of the ACM} Vol. 14, no. 8, pp. 548-560, (1971)
\bibitem{42} Mumford, David, {\sl Abelian Varieties}, Oxford
University Press, (1970)
\bibitem{43} Nering, Evar, ``Reduction of an Algebraic Function Field
Modulo a Prime in the Constant Field,'' {\sl Annals of Mathematics},
Vol 67, No. 3, (1958) pp 590-606
\bibitem{44} Newman, Morris, {\sl Integral Matrices}, Academic Press,
New York, (1972)
\bibitem{45} Risch, R.H., ``The Problem of Integration in Finite
Terms,'' {\sl Trans. AMS}, Vol 139, (1969) pp 167-189
\bibitem{46} Risch, R.H., {\sl On the Integration of Elementary
Functions which are built up using Algebraic Operations},
Rep. SP-2801/002/00, System Development Corp., Santa Monica, Calif.,
(1968)
\bibitem{47} Risch, R.H., ``The Solution of the Problem of Integration
in Finite Terms,'' {\sl Bulletin A.M.S}, Vol. 76, (1970) pp 605-608
\bibitem{48} Ritt, J.R., {\sl Integration in Finite Terms}, Columbia
U. Press, N.Y., (1948)
\bibitem{49} Rosenlicht, Maxwell, ``Differential Extensions Fields of
Exponential Types,'' {\sl Pacific Journal of Mathematics}, Vol 57, 1
(1975)
\bibitem{50} Rosenlicht, Maxwell, ``Integration in Finite Terms,''
{\sl American Mathematical Monthly}, Vol 79, 9 pp. 963-972 (1972)
\bibitem{51} Serre, J.-P., Tate, J., ``Good reduction of abelian
varieties,'' {\sl Annals of Math.}, pp. 492-517, (1968)
\bibitem{52} Schmidt, Wolfgang M., {\sl Equations over Finite Fields
an Elementary Approach}, Lecture Notes in Mathematics, No. 536,
Springer-Verlag, (1976)
\bibitem{53} Shafarevich, I. R., {\sl Basic Algebraic Geometry}, Die
Grundlehren der mathematichen Wissenschaften, Band 213,
Springer-Verlag, (1974)
\bibitem{54} Shimura, G., Taniyama, Y., {\sl Complex Multiplication of
Abelian Varieties and its Applications to Number Theory}, Mathematical
Society of Japan, (1961)
\bibitem{55} Trager, B.M., {\sl Algorithms for Manipulating Algebraic
Functions}, S.M. thesis M.I.T., (1976)
\bibitem{56} Trager, B.M., ``Algebraic Factoring and Rational Function
Integration,'' {\sl Proc. 1976 ACM Symposium on Symbolic and Algebraic
Manipulation}, pp. 219-226, (1976)
\bibitem{57} van der Waerden, B.L., {\sl Modern Algebra}, vol 1,
tr. Fred Blum, Frederick Ungar Publishing Co., New York, (1953)
\bibitem{58} Walker, Robert J. {\sl Algebraic Curves}, Dover, New
York, (1962)
\bibitem{59} Weil, Andre, {\sl Courbes algebriques et varietes
abeliennes}, Hermann, Paris, (1971), first published (1948) in {\sl
Actualites Scientifiques et Industrielles}, nos. 1041 and 1064.
\bibitem{60} Weil, Andre, {\sl Foundations of Algebraic Geometry},
Amer. Math. Society, N.Y., (1946)
\bibitem{61} Zariski, Oscar, and Pierre Samuel, {\sl Commutative
Algebra}, Vol 1\&2, D. Van Nostrand Co., Princeton, N.J., (1958)
\bibitem{62} Zassenhaus, Hans, {\sl Symposia Mathematica}, Vol. XV,
``On Hensel Factorization II,'' Academic Press, London and N.Y.,
(1975) pp. 499-513
\bibitem{63} Zassenhaus, Hans, ``On the Second Round of the Maximal
Order Program,'' {\sl Applications of Number Theory to Numerical
Analysis}, Academic Press, New York, (1972) pp. 389-431
\end{thebibliography}
\end{document}